  Graphs are widely used for modeling various types of interactions, such as
email communications and online discussions. Many of such real-world graphs are
temporal, and specifically, they grow over time with new nodes and edges.
  Counting the instances of each graphlet (i.e., an induced subgraph
isomorphism class) has been successful in characterizing local structures of
graphs, with many applications. While graphlets have been extended for temporal
graphs, the extensions are designed for examining temporally-local subgraphs
composed of edges with close arrival times, instead of long-term changes in
local structures.
  In this paper, as a new lens for temporal graph analysis, we study the
evolution of distributions of graphlet instances over time in real-world graphs
at three different levels (graphs, nodes, and edges). At the graph level, we
first discover that the evolution patterns are significantly different from
those in random graphs. Then, we suggest a graphlet transition graph for
measuring the similarity of the evolution patterns of graphs, and we find out a
surprising similarity between the graphs from the same domain. At the node and
edge levels, we demonstrate that the local structures around nodes and edges in
their early stage provide a strong signal regarding their future importance. In
particular, we significantly improve the predictability of the future
importance of nodes and edges using the counts of the roles (a.k.a., orbits)
that they take within graphlets.
