# Graphlets over Time: A New Lens for Temporal Network Analysis

Deukryeol Yoon  KAIST AISeoulSouth Korea<EMAIL_ADDRESS>,  Dongjin
Lee  KAIST EEDaejeonSouth Korea<EMAIL_ADDRESS>,  Minyoung Choe
KAIST AISeoulSouth Korea<EMAIL_ADDRESS>and  Kijung Shin  KAIST AI
& EESeoulSouth Korea<EMAIL_ADDRESS>
###### Abstract.

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.

(a) Similarity between graphs w.r.t. graphlet transitions
(classification accuracy = 97.2%)

(b) Similarity between graphs w.r.t. graphlet occurrences (classification
accuracy = 83.3%)

Figure 1.  Real-world temporal graphs from the same domain share similar
evolution patterns captured by transitions between graphlets. The figures show
the pairwise similarity between 9 graphs from 3 domains (distinguished by text
colors) with respect to the transitions between graphlets (see (a)) and the
occurrences of graphlets (see (b)). The domains of graphs can be classified
more accurately in (a) than in (b). Specifically, with the best thresholds of
similarity, the classification accuracy is $97.2\%$ in (a) and $83.3\%$ in
(b). See Section 3.2 for details about the similarity measures.

##  1\. Introduction

Graphs are a simple yet powerful tool, and thus they have been used for
representing various types of interactions: email communications, online Q/As,
research collaborations, to name a few. Due to newly formed interactions, such
real-world graphs are temporal, i.e., they evolve over time with new nodes and
edges. Many studies have examined the dynamics of real-world temporal graphs
and revealed interesting patterns, including densification (Leskovec et al.,
2005), shrinking diameter (Leskovec et al., 2005), and temporal locality in
triangle formation (Lee et al., 2020).

Graphlets have been widely employed for analyzing local structures of graphs.
Graphlets (Pržulj, 2007) are defined as the sets of isomorphic small subgraphs
with a predefined number of nodes. Specifically, the relative counts of the
instances of different graphlets effectively characterize the local structures
of graphs, with successful applications in graph classification (Milo et al.,
2002, 2004), community detection (Arenas et al., 2008; Benson et al., 2016;
Tsourakakis et al., 2017), anomaly detection (Juszczyszyn and Kołaczek, 2011),
and node embedding (Liu et al., 2021; Lee et al., 2019; Yu et al., 2019).

As temporal graphs are pervasive, the concept of graphlets has been
generalized in a number of ways for temporal graph analysis. Temporal network
motifs (Paranjape et al., 2017; Kovanen et al., 2011) are sets of temporal
subgraphs that are (a) identical not just topologically but also temporally,
(b) composed of a fixed number of nodes, and (c) temporally local, i.e.,
composed of edges whose arrival times are close enough (see Section 6 for
details). Due to the last condition, they are suitable for analyzing short-
term changes of graphs but not for long-term changes in local structures,
which are the focus of this paper.

In this paper, we examine the long-term evolution of local structures captured
by graphlets, as a new lens for temporal graph analysis, in nine real-world
temporal graphs from three different domains. Our analysis is at three levels:
graphs, nodes, and edges.

At the graph level, we first investigate the changes in the distributions of
graphlet instances over time. We find out that the evolution patterns are
distinguished from those in randomized graphs that are obtained by randomly
shuffling edges. Moreover, the evolution patterns in graphs from the same
domain share some common characteristics. In order to compare the evolution
patterns in a systematic way, we introduce graphlet transition graphs, which
encode transitions between graphlets due to changes in graphs. As shown in
Figure 1(a), graphs from the same domain share similar graphlet-transition
patterns, which facilitates accurate graph classification, although the sizes
of the graphs vary.

(a) $13$ graphlets

(b) $30$ node roles (also known as, node orbits)

(c) $30$ edge roles (also known as, edge orbits)

Figure 2.  (a) The 13 graphlets (Pržulj, 2007) with three nodes. (b) The 30
node roles (Pržulj, 2007) within the graphlets (see the positions of black
nodes). (c) The 30 edge roles within the graphlets (see the positions of edges
from a red node to a blue node).

At the node and edge levels, we investigate how local structures around each
node and edge in their early stage signal their future importance.
Specifically, as local structures, we consider node roles (formally, node
automorphism orbits (Pržulj, 2007)) and edge roles (Hočevar and Demšar, 2016),
which are roughly sets of symmetric positions of nodes and edges within
graphlets. We also demonstrate that the counts of the roles taken by each node
and edge in their early stage are more informative than previously-used
features (Yang et al., 2014), and they are complementary to simple global
features (e.g., total counts of nodes and edges) for the task of predicting
future centralities (specifically, in-degree, betweenness (Freeman, 1977),
closeness (Bavelas, 1950), and PageRank (Page et al., 1999)).

We summarize our contributions as follows:

  * $\bullet$

Patterns: We make several interesting observations about the temporal
evolution of graphlets: a surprising similarity in graphs from the same domain
and local-structural signals regarding the future importance of nodes and
edges.

  * $\bullet$

Tool: We introduce graphlet transition graphs, which is an effective tool for
measuring the similarity of local dynamics in temporal graphs of different
sizes.

  * $\bullet$

Prediction: We enhance the prediction accuracy of the future importance of
nodes and edges by introducing role-based local features, which are
complementary to global features.

Reproducibility: The code and the datasets are available at
https://github.com/deukryeol-yoon/graphlets-over-time.

In Section 2, we introduce basic concepts, notations, and datasets. In Section
3, we present our graph-level analysis. In Section 4 and Section 5, we present
our node-level and edge-level analyses. In Section 6, we present a brief
survey of related works. In Section 7, we conclude our work.

##  2\. Basic Concepts, Notations, and Data

In this section, we first introduce some basic concepts and notations. Then,
we describe the nine datasets used in this paper.

###  2.1. Basic Concepts and Notations

Temporal Graph: A temporal graph
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{T})$ consists of a set of nodes
$\mathcal{V}$, a set of directed edges
$\mathcal{E}:=\\{e_{1},\cdots,e_{|\mathcal{E}|}\\}$, and a multiset of edge
arrival times $\mathcal{T}:=[t_{1},\cdots,t_{|\mathcal{E}|}]$. For each
directed edge $e_{i}\in\mathcal{E}$, we use $t_{i}\in\mathcal{T}$ to denote
the arrival time of $e_{i}$. We use $u\rightarrow v$ to denote a directed edge
from a node $u$ to a node $v$, and the nodes $u$ and $v$ are adjacent if
$u\rightarrow v$ or $v\rightarrow u$ exists. From now on, we will use the term
edge to indicate a directed edge when there is no ambiguity.

Table 1.  Table of symbols.

Notation | Definition
---|---
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{T})$ | temporal graph with nodes $\mathcal{V}$, edges $\mathcal{E}$, and times $\mathcal{T}$
$\mathcal{G}^{(t)}=(\mathcal{V}^{(t)},\mathcal{E}^{(t)})$ | snapshot of $\mathcal{G}$ at time $t$
$\mathcal{\tilde{G}}=(\mathcal{V},\mathcal{E},\mathcal{\tilde{T}})$ | a temporal graph randomized from $\mathcal{G}$
$\mathcal{\tilde{G}}^{(t)}=(\mathcal{\tilde{V}}^{(t)},\mathcal{\tilde{E}}^{(t)})$ | snapshot of $\mathcal{\tilde{G}}$ at time $t$
$m^{(t)}_{i}(v)$ | count of node role $i$ at a node $v$ in $\mathcal{G}^{(t)}$

Randomized Graph: A randomized graph
$\mathcal{\tilde{G}}=(\mathcal{V},\mathcal{E},\mathcal{\tilde{T}})$ of
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{T})$ is obtained by assigning
arrival times in $\mathcal{T}$ to edges in $\mathcal{E}$ uniformly at random
in a one-to-one manner. For each edge $e_{i}\in\mathcal{E}$, we use
$\tilde{t}_{i}\in\mathcal{\tilde{T}}$ to denote the arrival time assigned to
it.

Snapshot: We define the snapshot at time $t$ of
$\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{T})$ as
$\mathcal{G}^{(t)}=(\mathcal{V}^{(t)},\mathcal{E}^{(t)})$ where
$\mathcal{E}^{(t)}:=\\{e_{i}\in\mathcal{E}:t_{i}\leq t\\}$ and
$\mathcal{V}^{(t)}\subseteq\mathcal{V}$ is the endpoints of any edge in
$\mathcal{E}^{(t)}$. That is, $\mathcal{G}^{(t)}$ consists of the nodes and
edges arriving at time $t$ or earlier. Similarly, the snapshot at time $t$ of
$\mathcal{\tilde{G}}=(\mathcal{V},\mathcal{E},\mathcal{\tilde{T}})$ is
$\mathcal{\tilde{G}}^{(t)}=(\mathcal{\tilde{V}}^{(t)},\mathcal{\tilde{E}}^{(t)})$
where $\mathcal{\tilde{E}}^{(t)}:=$ $\\{e_{i}\in\mathcal{E}:\tilde{t}_{i}\leq
t\\}$ and $\mathcal{\tilde{V}}^{(t)}$ is the endpoints of any edge in
$\mathcal{\tilde{E}}^{(t)}$. We define the neighbors of a node
$v\in\mathcal{V}^{(t)}$ in a snapshot $\mathcal{G}^{(t)}$ as the nodes
adjacent to $v$ in $\mathcal{G}^{(t)}$. We define the degree of a node
$v\in\mathcal{V}^{(t)}$ in a snapshot $\mathcal{G}^{(t)}$, which is denoted by
$d^{(t)}(v)$, as the number of directed edges whose endpoints include $v$ in
$\mathcal{G}^{(t)}$. We simply use $d(v)$ to denote the degree of the node $v$
in the last snapshot $\mathcal{G}^{(t_{|\mathcal{E}|})}$.

Induced Subgraphs: A subgraph of a snapshot
$\mathcal{G}^{(t)}=(\mathcal{V}^{(t)},\mathcal{E}^{(t)})$ is induced if and
only if it consists of a subset of $\mathcal{V}^{(t)}$ and all of the edges
connecting pairs of the nodes in the subset. Two subgraphs $\mathcal{H}$ and
$\mathcal{H^{\prime}}$ are isomorphic if there exists a one-to-one mapping $f$
between the nodes of both graphs such that there exists an edge from a node
$u$ to a node $v$ in $\mathcal{H}$ if and only if there exists an edge from
the node $f(u)$ to the node $f(v)$ in $\mathcal{H^{\prime}}$.

Graphlets: A graphlet is the set of induced subgraphs that are isomorphic to
each other. In this paper, we limit our attention to the $13$ graphlets
consisting of three connected nodes. An induced subgraph is called an instance
of graphlet $k$ if it is isomorphic to the $k$-th graph in Figure 2(a).

Node Roles: Consider an induced subgraph $\mathcal{H}$ with a node set
$\mathcal{V}^{\prime}$. An automorphism of $\mathcal{H}$ is an isomorphism
between $\mathcal{H}$ and itself. i.e., an automorphism of $\mathcal{H}$ is a
one-to-one mapping between nodes of $\mathcal{H}$ such that there exists an
edge from a node $u$ to a node $v$ in $\mathcal{H}$ if and only if there
exists an edge from the node corresponding to $u$ to the node corresponding to
$v$ in $\mathcal{H}$. If denoting the set of automorphisms of $\mathcal{H}$ by
$Aut(\mathcal{H})$, the automorphism orbit of a node
$u\in\mathcal{V}^{\prime}$ is the set $\\{y\in\mathcal{V}^{\prime}:\exists
g\in Aut(\mathcal{H})\text{ s.t. }y=g(u)\\}$ of nodes (Pržulj, 2007).
Formally, node roles are node automorphism orbits, and roughly, they are sets
of symmetric positions of nodes within graphlets. Figure 2(b) (see the
positions of black nodes) shows all $30$ node roles in the $13$ graphlets that
we consider. We say a node $v$ “takes” node role $i$ in a graphlet instance if
there exists an isomorphism of the graphlet instance and the $i$-th graph in
Figure 2(b) that maps $v$ to the black node in the graph. We define the count
of node role $i$ at a node $v$ as the number of graphlet instances where $v$
takes $i$, and $m^{(t)}_{i}(v)$ denotes the count at a snapshot
$\mathcal{G}^{(t)}$.

Table 2.  Summary of nine real-world temporal graphs used throughout this
paper.

Domain | Dataset | $|V|$ | $|E_{T}|$ | Period
---|---|---|---|---
Citation | HepPh | $34,565$ | $346,849$ | 9 years
HepTh | $18,477$ | $136,190$ | 10 years
Patent | $3,774,362$ | $16,512,782$ | 25 years
Email/Message | Enron | $55,655$ | $209,203$ | 24 years
EU | $986$ | $24,929$ | 1.5 years
College | $1,899$ | $20,296$ | 0.5 years
Online Q/A |  Askubuntu | $159,316$ | $262,106$ | 6 years
Mathoverflow | $24,818$ | $90,489$ | 7 years
Stackoverflow | $2,601,977$ | $16,266,395$ | 8 years

Edge Roles: Consider an induced subgraph $\mathcal{H}$ with an edge set
$\mathcal{E}^{\prime}$. Based on the concepts defined above, we define the
edge role of an edge $u\rightarrow v$ is the set $\\{x\rightarrow
y\in\mathcal{E}^{\prime}:\exists g\in Aut(\mathcal{H})\text{ s.t.
}x=g(u)\wedge y=g(v)\\}$ of edges. Roughly, edge roles are the sets of
symmetric positions of edges within graphlets. Figure 2(c) (see the positions
of edges from a red node to a blue node) shows all $30$ edge roles in the $13$
considered graphlets. We say an edge $u\rightarrow v$ “takes” edge role $j$ in
a graphlet instance if there exists an isomorphism of the graphlet instance
and the $j$-th graph in Figure 2(c) that maps $u$ and $v$ to the red node and
the blue node, respectively, in the graph. We define the count of edge role
$j$ at an edge $e$ as the number of graphlet instances where $e$ takes $j$.

###  2.2. Datasets

Throughout this paper, we use the nine real-world temporal graphs from the
three domains, which are summarized in Table 2.

Citation Graphs: Each node is a paper or a patent. Each directed edge from a
node $u$ to a node $v$ means that $u$ cites $v$.

Email/Message Graphs: Each node is a user. Each directed edge from a node $u$
to a node $v$ indicates that $u$ sends $v$ emails (messages).

Online Q/A Graphs: Each node is a user. Each directed edge from a node $u$ to
a node $v$ means that $u$ answers $v$’s questions.

Table 3.  Ratios of graphlets over time. The colors in the plots are matched
with the colors of the graphlets in Figure 2, and the evolution ratio means
the fraction of edges added to graphs. The evolution patterns in real-world
graphs vary depending on domains (Observation 1), and they are clearly
distinguished from the evolution patterns in randomized graphs (Observation
2).

| Temporal graph $\mathcal{G}$ | Randomized graph $\mathcal{\tilde{G}}$
---|---|---
Citation |  |  |  |  |  |
Email/Message |  |  |  |  |  |
Online Q/A |  |  |  |  |  |

1

Input : Temporal Graph $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{T})$

Output : The count of the instances of each graphlet in $\mathcal{G}$

2

3Initialize the count of the instances of each graphlet to zero

4 Initialize $\mathcal{E}$ to an empty set

5

6for  _each edge $e_{i}=u\rightarrow v$ in arrival order_ do

7

8 $\mathcal{N}\leftarrow$ union of the neighbors of $u$ and the neighbors of
$v$ (except for $u$ and $v$)

9 for  _each $w\in\mathcal{N}$_ do

10 if  _$u$ , $v$ and $w$ form a graphlet instance_ then

11 decrement the count of the graphlet of the instance formed by $u$, $v$ and
$w$

12

13

14

15 add $u\rightarrow v$ to $\mathcal{E}$

16 for  _each $w\in\mathcal{N}$_ do

17 increment the count of the graphlet of the instance formed by $u$, $v$ and
$w$

18

19

20

21return count of the instances of each graphlet instances

Algorithm 1 Counting the Instances of Each Graphlet in a Temporal Graph

##  3\. Graph Level Analysis

In this section, we study the evolution of local structures in real-world
graphs. We examine the dynamics in the distribution of graphlet instances and
transitions between graphlets.

###  3.1. Global Level 1. Graphlets Over Time

We track how the ratio of the instances of each graphlet changes as the
considered real-world graphs evolve over time. Our tracking algorithm, which
is described in Algorithm 1, is adapted from StreaM (Schiller et al., 2015),
which maintains the counts of the instances of the $4$-node undirected
graphlets in a fully dynamic graph stream, where edges are not just added but
also deleted over time. The time complexity of Algorithm 1 is
$\Theta(\Sigma_{v\in\mathcal{V}}(d(v))^{2})$, as proven in Theorem 1. It
should be noticed that, by Lemma 2, the time complexity is $\Theta($the number
of instances of all graphlets in the last snapshot$)$, which is the optimal
time complexity achievable by any algorithm that counts graphlet instances by
enumerating them.

###### Theorem 1.

The time complexity of Algorithm 1 is
$\Theta(\Sigma_{v\in\mathcal{V}}(d(v))^{2})$.

###### Proof.

Since the number of nodes forming each graphlet instance is a constant,
finding the graphlet corresponding to a given instance and updating the
corresponding count (lines 1-1 and 1) take $O(1)$ time. Thus, the time
complexity of processing each incoming edge $e_{i}=u\rightarrow v$ is that of
computing the union of the neighbors of $u$ and $v$ (line 1), which is
$\Theta(d^{(t_{i}-1)}(u)+d^{(t_{i}-1)}(v))$. Hence, the total complexity is
$\Theta(\sum_{e_{i}=u\rightarrow v\in
E}(d^{(t_{i}-1)}(u)+d^{(t_{i}-1)}(v))=\Theta(\sum_{v\in\mathcal{V}}(d(v))^{2})$.
∎

###### Lemma 0.

The number of instances of all graphlets in a snapshot $\mathcal{G}^{(t)}$ is
$\Theta(\Sigma_{v\in\mathcal{V}^{(t)}}(d^{(t)}(v))^{2})$.

###### Proof.

Given a snapshot $\mathcal{G}^{(t)}=(\mathcal{V}^{(t)},\mathcal{E}^{(t)})$,
for each node $v\in\mathcal{V}^{(t)}$, if we count the instances of all
graphlets that consist of $v$ and its two neighbors, then the count of such
instances is $\Theta((d^{(t)}(v))^{2})$ for each node $v$, and since
$d^{(t)}(v)\geq 1$ for every node $v$, the total count $C$ is
$\Theta(\Sigma_{v\in\mathcal{V}^{(t)}}(d^{(t)}(v))^{2})$.

Lower Bound: Since each graphlet instance, which consists of three nodes, is
counted at most three times, $C$ is at most three times the number of
instances of all graphlets in $\mathcal{G}^{(t)}$. In other words, the number
of instances of all graphlets is at least $1/3$ of $C$, and thus it is
$\Omega(\Sigma_{v\in\mathcal{V}^{(t)}}(d^{(t)}(v))^{2})$.

Upper Bound: In each graphlet instance, there exists at least one center node,
who composes the graphlet together with its neighbors. Thus, each instance is
counted at least once, and thus $C$ is at least the number of instances of all
graphlets in $\mathcal{G}^{(t)}$. In other words, the number of instances of
all graphlets is at most $C$, and thus it is
$O(\Sigma_{v\in\mathcal{V}^{(t)}}(d^{(t)}(v))^{2})$. ∎

As seen in Table 3, the dynamics of the ratios depend on the domains of the
graphs, as summarized in Observation 1.

###### Observation 1.

The dynamics in the distributions of graphlet instances in graphs from the
same domain share some commonalities. $\bullet$ Instances of graphlet 4 are
more dominant in the citation graphs than other graphs. $\bullet$ Graphlets
with many edges (e.g., graphlets 8, 12, and 13) account for a larger fraction
in email/message networks than in other networks. $\bullet$ The fraction of
graphlet 1 increases over time only in the online Q/A graphs.

However, the dynamics are not exactly the same within domains. For example,
while graphlets 1, 2, and 4 are dominant compared to other graphlets in all
citation graphs, the ratios among them vary greatly in different graphs.

We also notice a consistent difference between the dynamics in real-world
graphs and those in randomized graphs (see Section 2.1), as summarized in
Observation 2.

###### Observation 2.

The ratios of graphlet instances change more linearly in randomized graphs
than in real-world graphs.

Table 4.  The non-linearity of the ratios of graphlet instances over time in
real-world graphs and randomized graphs. We describe in Section 3.1 how the
non-linearity is measured. The lower the non-linearity is, the more linear the
change of the ratio of the corresponding graphlet instances is. Note that the
ratios of graphlet instances change more linearly in randomized graphs than in
real-world graphs.

Dataset | HepPh | HepTh | Patent | EU | Enron | College | Math | Ask | Stack
---|---|---|---|---|---|---|---|---|---
real | 0.0027 | 0.0080 | 0.0093 | 0.0107 | 0.0042 | 0.0095 | 0.0028 | 0.0038 | 0.0047
random | 0.0003 | 0.0011 | 0.0000 | 0.0081 | 0.0017 | 0.0058 | 0.0007 | 0.0005 | 0.0001

In order to numerically support this observation, we measure the non-linearity
(Kroll and Emancipator, 1993; Hsieh and Liu, 2008) of the ratios of graphlet
instances over time. Specifically, we fit a linear regression model and a non-
linear polynomial regression model to each time series in Table 3, and then we
measure the average absolute difference between the predicted values of the
two models as the non-linearity of the time series.111We use the linearity
test implemented in Analyse-it (Ver. 5.65) and select a cubic model as the
non-linearity polynomial model, as suggested in the program. For computational
efficiency, we measure the absolute difference at 1,000 evolution ratios
sampled uniformly at equal intervals. Lastly, we average the non-linearity of
all time-series from each graph and report the results in Table 4. Note that
non-linearity is significantly higher in real-world graphs than in
corresponding randomized graphs. That is, the ratios of graphlet instances
change more linearly in randomized graphs than in real-world graphs.

Table 5.  Using graphlet transition graphs (GTGs) and characteristic profiles
(CPs) from GTGs, we can accurately characterize the dynamics of local
structures in real-world graphs. The colors of edges in GTGs indicate their
normalized weights. Note that GTGs and CPs are particularly similar in real-
world graphs from the same domains (Observation 3).

| Graphlet transition graphs (GTGs) | Characteristic profiles (CPs)
---|---|---
Citation |  |  |  |
Email/Message |  |  |  |
Online Q/A |  |  |  |

###  3.2. Global Level 2. Graphlet Transitions

In a temporal graph, an instance of a graphlet may transition to an instance
of another graphlet due to new edges added to it. In this subsection, we
examine the counts of such transitions between graphlets to characterize the
local dynamics in temporal graphs and also to make comparisons between them.

Graphlet Transition Graph: We define graphlet transition graphs (GTGs) to
encode transitions between graphlets.

###### Definition 0 (Graphlet transition graph).

A graphlet transition graph (GTG) $G=(V,E,W)$ of a temporal graph
$\mathcal{G}$ is a static directed weighted graph where the nodes are
graphlets and each edge indicates that the source graphlet is transformed into
the destination graphlet by an edge added to $\mathcal{G}$. The weight of
edges is the number of occurrences of the corresponding transitions. We use
$W=\\{w_{1},\cdots,w_{|E|}\\}$ to denote the edge weights.
Since we focus on the 13 graphlets in Figure 2(a), a GTG consists of the 28
types of transitions between these graphlets. In Table 5, we visualize the
GTGs from the real-world graphs. Algorithm 2 describes the computation of the
edge weights of a GTG. In a nutshell, for each edge in arrival order, we count
the transitions caused by it. Its time complexity is formalized in Theorem 4.

###### Theorem 4.

The time complexity of Algorithm 2 is
$\Theta(\Sigma_{v\in\mathcal{V}}(d(v))^{2})$ = $\Theta($the number of
instances of all graphlets in the last snapshot$)$.

###### Proof.

We can prove the complexity of $\Theta(\Sigma_{v\in\mathcal{V}}(d(v))^{2})$
similarly to Theorem 1, and by Lemma 2, it is $\Theta($the number of instances
of all graphlets in the last snapshot$)$. ∎

1

Input : Temporal graph $\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{T})$

Output : Edge weights of the graphlet transition graph of $\mathcal{G}$

2

3Initialize all edge weights to zero

4 Initialize $\mathcal{E}$ to an empty set

5 for  _each edge $e_{i}=u\rightarrow v$ in arrival order_ do

6 for  _each $w_{1}$ $\in$ neighbors$(u)$ $\setminus$ $\\{v\\}$ _ do

7 UPDATE(_$u,v,w_{1}$_)

8 for  _each $w_{2}$ $\in$ neighbors$(v)$ $\setminus\\{$neighbors$(u)$ $\cup$
$u\\}$_ do

9 UPDATE(_$u,v,w_{2}$_)

10 add $u\rightarrow v$ to $\mathcal{E}$

11

12return the edge weights

13Procedure  _UPDATE(_$u,v,w$_)_

14 if  _$u$ , $v$, and $w$ form a graphlet instance_ then

15 prev $\leftarrow$ graphlet of the instance $(u,v,w)$ without $u\rightarrow
v$

16 next $\leftarrow$ graphlet of the instance $(u,v,w)$ with $u\rightarrow v$

17 $i$ $\leftarrow$ index of the graphlet transition from prev to next

18 increase the weight of the edge $i$ (i.e., $w_{i}$) by $1$

19

Algorithm 2 Computing the Edge Weights of Graphlet Transition Graphs

Characteristic Profile (CP): We characterize the evolution of local structure
in a graph $\mathcal{G}$ using the significance of edge weights in its GTG
$G=(V,E,W)$. In order to measure the significance, we follow the steps in
(Milo et al., 2004) for measuring the significance of each graphlet itself. To
this end, we construct the graphlet transition graph $\tilde{G}$ of a
randomized graph $\mathcal{\tilde{G}}$. Then, we measure the significance
$SP_{i}$ of each edge weight $w_{i}$ in $G$ as follows:

(1) $SP_{i}:=\frac{w_{i}-\tilde{w}_{i}}{w_{i}+\tilde{w}_{i}+\epsilon},$

where $\tilde{w}_{i}$ is the corresponding edge weight in $\tilde{G}$, and
$\epsilon$ is a constant, which we fix to $4$. For $\tilde{w}_{i}$, we
generate 50 instances of randomized graphs and we use the average edge weights
in them. Lastly, we normalize each significance as follows:

(2) $CP_{i}:={SP_{i}}/{\sqrt{\Sigma_{i=1}^{|E|}SP_{i}^{2}}}.$

We characterize the evolution of local structures in $\mathcal{G}$ using the
vector of the normalized significances (i.e., $[CP_{1},\cdots,CP_{|E|}]$),
which we call characteristic profile (CP).

(a) $d_{\theta}=2$

(b) $d_{\theta}=4$

(c) $d_{\theta}=8$

Figure 3.  Example signals from the local structures of nodes regarding their
future importance. The ratios of some node roles (e.g., node roles 2 and 4) at
nodes monotonically increase with respect to the future in-degrees of the
nodes. The ratios are rescaled so that their maximum values are the same.

Comparison between CPs: We plot the CPs of the considered real-world graphs in
Table 5, and high levels of similarity are observed within domains. We
numerically measure the similarity between CPs using the Pearson correlation
coefficients, and the results are shown in Figure 1(a). The correlation
coefficients are particularly high between graphs from the same domain, and
specifically the domains can be classified with $97.2\%$ accuracy if we use
the best threshold of the correlation coefficient ($0.58$). The results
demonstrate that CPs accurately characterize the evolution of local
structures. Our observations are summarized in Observation 3.

###### Observation 3.

The evolution patterns of local structures are similar in real-world graphs
from the same domains.

Comparison with Other Methods: We evaluate three other graph characterization
methods, as we evaluate ours in the right above paragraph. In Figure 1(b), we
provide the correlation coefficients between the CPs obtained from the count
of the instances of each graphlet (Milo et al., 2004). Note that the
email/message graphs (blue) and the online Q/A graphs (green) are not
distinguished clearly. Numerically, with the best threshold of correlation
coefficient ($0.95$), the classification accuracy is $83.3\%$.

We also compute the similarity between the considered real-world graphs using
Graphlet-orbit Transition (GoT) (Aparício et al., 2018) and Orbit Temporal
Agreement (OTA) (Aparício et al., 2018), which are also based on transitions
between graphlets (see Section 6 for details). Our way of characterization has
the following major advantages over them:

  * $\bullet$

(1) Speed: Empirically, GoT and OTA are up to $10\times$ slower than our
method, as shown in Appendix A.1. The time complexity of them is proportional
to the sum of the counts of graphlet instances in all used snapshots, while
the time complexity of Algorithm 2 is proportional only the to the count of
graphlet instances in the last snapshot (Theorem 4).

  * $\bullet$

(2) Space Efficiency: GoT and OTA run out of memory in the two largest graphs
(Patent and Stackoverflow), as shown in Appendix A.1, while our method does
not. They need to store all graphlet instances in each considered snapshot for
comparison with those in the next snapshot, while Algorithm 2 maintains only
the latest snapshot without having to store graphlet instances.

  * $\bullet$

(3) Characterization Accuracy: The best classification accuracies computed
using the considered real-world graphs (except for Patent and Stackoverflow
for which GoT and OTA run out of memory) are $81.0\%$ (GoT) and $85.7\%$
(OTA), which is lower than our classification accuracy ($97.2\%$). Detailed
results are given in Appendix A.1. Note that GoT and OTA approximate the
counts of transitions between graphlets based on a small number of snapshots,
while Algorithm 2 exactly counts the transitions.

In summary, our way of characterizing temporal graphs using GTGs distinguishes
the domains of temporal graphs most accurately with the accuracy of $97.2\%$.
The accuracies of the other methods are $83.3\%$, $81.0\%$, and $85.7\%$.

##  4\. Node Level Analysis

In this section, we study how local structures around nodes are related to
their future importance. Then, we enhance the predictability of future node
centrality using the relations.

###  4.1. Patterns

We characterize the local structures of nodes using node roles and examine
their relation to the nodes’ future centrality.

Table 6.  The absolute value of the Spearman’s rank correlation coefficients
between node role ratios and future centralities (averaged over all node roles
and all datasets for each centrality measure) and each value of the threshold
$d_{\theta}$. As the number of node neighbors increases (i.e., $d_{\theta}$
increases), the local-structural signals about future centralities become
stronger (i.e., the absolute values increase).

$d_{\theta}$ | Degree | Betweenness | Closeness | PageRank | Edge Betweenness
---|---|---|---|---|---
2 | 0.640 | 0.697 | 0.682 | 0.663 | 0.546
4 | 0.721 | 0.723 | 0.712 | 0.704 | 0.558
8 | 0.816 | 0.793 | 0.759 | 0.701 | 0.599

Local Structures of Nodes: Given a temporal graph $\mathcal{G}$, we
characterize the local structure of each node $v$ in their early stage by
measuring the ratio of each node role at $v$ in the snapshot at time $t$ when
the in-degree of $v$ first reaches a threshold $d_{\theta}$. That is, each
node $v$ is represented as a $30$-dimensional vector whose $i$-th is
$m^{(t)}_{i}(v)/(\sum_{j=1}^{30}m^{(t)}_{j}(v))$ (see Section 2.1 for
$m^{(t)}_{i}(v)$).

Future Importance of Nodes: Given a temporal graph $\mathcal{G}$, as future
importance of each node, we measure its in-degree, node betweenness centrality
(Freeman, 1977), closeness centrality (Bavelas, 1950), and PageRank (Page et
al., 1999) in the last snapshot of $\mathcal{G}$. Based on each centrality
measure, we divide the nodes in $\mathcal{G}$ into six groups (Group 1: top
50-100%, Group 2: top 30-50%, Group 3: top 10-30%, Group 4: top 5-10%, Group
5: top 1-5%, and Group 6: top 0-1%).

Figure 4.  The Spearman’s rank correlation coefficient between node role
ratios (when nodes have in-degree four, i.e., $d_{\theta}$ = 4) and future
node centralities. The darker a cell is, the larger the absolute value of the
corresponding coefficient is. Note that the absolute values of most
coefficients are significantly greater than $0$.

Finding Signals: For each group, we average the ratio vectors of the nodes in
the group. Figure 3 shows some averaged ratios when in-degree is used as the
centrality measure. Note that the ratios of node roles 2 and 4 monotonically
grow as future centrality increases, regardless of $d_{\theta}$ values. That
is, the ratios of node roles 2 and 4 give a consistent signal regarding the
nodes’ future in-degree.

In Figure 4, we report the Spearman’s rank correlation coefficient (Zwillinger
and Kokoska, 1999) between each averaged ratio and the future centralities of
nodes (specifically, the above group numbers between 1 and 6). We also report
in Table 6 the absolute value of the coefficients (averaged over all node
roles and all datasets) for each centrality measure and each value of the
threshold $d_{\theta}$. Note that the average values are significantly greater
than $0$ and specifically around $0.7$; and they increase as $d_{\theta}$
increases, as summarized in Observation 4.

###### Observation 4.

In real-world graphs, the local structures of nodes in their early stage
provide a signal regarding their future importance. The signals become
stronger as nodes have more neighbors.

###  4.2. Prediction

Based on the observations above, we predict the future centrality of nodes
using the counts of their roles at them in their early stage.

Problem Formulation: We formulate the prediction problem as a classification
problem, as described in Problem 1.

###### Problem 1 (Node Centrality Prediction).

$\bullet$ Given: the snapshot $\mathcal{G}^{(t_{v,d_{\theta}})}$ of the input
graph when the in-degree of a node $v$ first reaches $d_{\theta}$, $\bullet$
Predict: whether the centrality of the node $v$ belongs to the top $20\%$ in
the last snapshot of $\mathcal{G}$.

As the centrality measure, we use in-degree, betweenness centrality, closeness
centrality, and PageRank. As $d_{\theta}$, we use $2$, $4$, or $8$.

Input Features: For each node $v$, we consider the snapshot
$\mathcal{G}^{(t)}$ of the input graph $\mathcal{G}$ when the in-degree of $v$
first reaches $d_{\theta}$. That is, $t=t_{v,d_{\theta}}$ and
$\mathcal{G}^{(t)}=\mathcal{G}^{(t_{v,d_{\theta}})}$. Then, we extract the
following sets of input features for $v$:

  * $\bullet$

Local-NR: The count of each node role at $v$ in $\mathcal{G}^{(t)}$. That is,
$[m^{(t)}_{1}(v),$ $m^{(t)}_{2}(v),\cdots,m^{(t)}_{30}(v)]$ (see Section 2.1
for $m^{(t)}_{i}(v)$).

  * $\bullet$

Local-NPP (Yang et al., 2014): In $\mathcal{G}^{(t)}$, we compute (1) the
count of triangles at $v$, (2) the count of wedges centered at $v$, (3) the
count of wedges ended at $v$.

  * $\bullet$

Global-Basic: Counts of nodes and edges in the snapshot.

  * $\bullet$

Global-NR: We compute the $30$-dimensional vector whose $i$-th entry
$m^{(t)}_{i}(v)/(\sum_{j=1}^{30}m^{(t)}_{j}(v))$ is the ratio of each node
role at $v$ in $\mathcal{G}^{(t)}$. Then, we standardize (i.e., compute the
$z$-score of) the role ratio vector using the mean and standard deviation from
the role ratio vectors (in $\mathcal{G}^{(t)}$) of all nodes with degree
$d_{\theta}$ in $\mathcal{G}^{(t)}$. The features in Local-NR are also
included.

  * $\bullet$

Global-NPP (Yang et al., 2014): In $\mathcal{G}^{(t)}$, we compute (1) the
number of edges not incident to $v$ and (2) the number of non-adjacent node
pairs where one is a neighbor of $v$ and the other is neither a neighbor of
$v$ nor $v$ itself. The features in Local-NPP are also included.

  * $\bullet$

ALL: All of Global-NR, Global-NPP, and Global-Basic.

Note that we categorize the above sets into global and local depending on
whether global information in $\mathcal{G}^{(t)}$ (i.e., the number of all
nodes in $\mathcal{G}^{(t)}$) is used or only local information at $v$ is
used.

Prediction Method: As the classifier, we use the random forest model from the
Scikit-learn library. The model has 30 decision trees with a maximum depth of
10.

Evaluation Method: We use $80\%$ of the nodes for training and the remaining
$20\%$ for testing. We evaluate the predictive performance in terms of
F1-score, accuracy, and Area Under the ROC curve (AUROC). A higher value
indicates better prediction performance.

Result: Table 7 shows the predictive performance from each set of input
features when $d_{\theta}=2$, and Table 8 shows how the performance depends on
the in-degree threshold $d_{\theta}$. In the tables, we report the mean of
each prediction performance over $10$ runs in the 7 datasets in Section 2.2
except for the two largest ones (i.e., Patent and Stackoverflow). From the
results, we draw the following observations.

###### Observation 5.

Among local features, the counts of node roles at each node (Local-NR) are
more informative than (Local-NPP) for future importance prediction.

###### Observation 6.

The considered sets of features are complementary to each other. Using them
all (ALL) leads to the best predictive performance in most cases.

###### Observation 7.

As nodes have more neighbors, their future importance can be predicted more
accurately.

Table 7.  F1-score, accuracy, and AUROC on the task of predicting future node
importance when $d_{\theta}=2$ averaged over the 7 considered real-world
graphs. Among local features, using Local-NR yields better performance than
using Local-NPP in all settings. Using ALL leads to the best performance in
most cases, indicating that the considered sets of features are complementary
to each other. Detailed results on each dataset can be found in Appendix C.3.

Target | Degree | Betweenness
---|---|---
Measure | F1-score | Accuracy | AUROC | F1-score | Accuracy | AUROC
Local-NR | 0.39 | 0.69 | 0.68 | 0.59 | 0.83 | 0.82
Local-NPP | 0.38 | 0.68 | 0.64 | 0.58 | 0.81 | 0.79
Global-NR | 0.57 | 0.74 | 0.78 | 0.64 | 0.84 | 0.85
Global-NPP | 0.57 | 0.73 | 0.77 | 0.64 | 0.84 | 0.85
Global-Basic | 0.50 | 0.72 | 0.73 | 0.24 | 0.73 | 0.67
ALL | 0.57 | 0.74 | 0.78 | 0.65 | 0.85 | 0.86
Target | Closeness | PageRank
Measure | F1-score | Accuracy | AUROC | F1-score | Accuracy | AUROC
Local-NR | 0.51 | 0.76 | 0.78 | 0.42 | 0.73 | 0.73
Local-NPP | 0.43 | 0.70 | 0.69 | 0.37 | 0.69 | 0.67
Global-NR | 0.68 | 0.82 | 0.87 | 0.54 | 0.75 | 0.79
Global-NPP | 0.66 | 0.80 | 0.85 | 0.54 | 0.74 | 0.78
Global-Basic | 0.59 | 0.75 | 0.79 | 0.47 | 0.71 | 0.74
ALL | 0.69 | 0.83 | 0.88 | 0.56 | 0.75 | 0.79

Feature Importance: Additionally, we measure the importance of each feature in
the set ALL using Gini-importance (Loh, 2011), and we report the top five
important features in Table 10 in Appendix B.2.

###### Observation 8.

Strong predictors vary depending on centrality measures. For example, for
betweenness centrality, the counts of node roles as bridges (i.e., Local NR-4
and Global NR-4) are strong.

Table 8.  Average F1-score, accuracy, and AUROC on the task of predicting
future node importance depending on $d_{\theta}$ (i.e., in-degree of nodes
when their input features are extracted). The overall performance improves
with respect to $d_{\theta}$ in most cases. That is, as nodes have more
neighbors, their future importance can be predicted more accurately. Detailed
results on each dataset can be found in Appendix C.3.

Target | Degree | Betweenness
---|---|---
Measure | F1-score | Accuracy | AUROC | F1-score | Accuracy | AUROC
ALL $(d_{\theta}=2)$ | 0.59 | 0.74 | 0.78 | 0.65 | 0.85 | 0.86
ALL $(d_{\theta}=4)$ | 0.69 | 0.78 | 0.79 | 0.73 | 0.83 | 0.87
ALL $(d_{\theta}=8)$ | 0.80 | 0.81 | 0.86 | 0.82 | 0.85 | 0.90
Target | Closeness | PageRank
Measure | F1-score | Accuracy | AUROC | F1-score | Accuracy | AUROC
ALL $(d_{\theta}=2)$ | 0.69 | 0.83 | 0.88 | 0.55 | 0.75 | 0.79
ALL $(d_{\theta}=4)$ | 0.78 | 0.83 | 0.89 | 0.73 | 0.77 | 0.80
ALL $(d_{\theta}=8)$ | 0.86 | 0.88 | 0.92 | 0.85 | 0.85 | 0.83

Figure 5.  The Spearman’s rank correlation coefficient between edge role
ratios (when endpoints have in-degree $4$ in total, i.e., $d_{\theta}$ = 4)
and future edge centralities. The darker a cell is, the larger the absolute
value of the corresponding coefficient is. Note that the absolute values of
many coefficients are significantly greater than $0$, while they tend to be
smaller than those in Figure 4.

##  5\. Edge Level Analysis

In this section, we investigate the signal of local structures of each edge
regarding their future centrality, and based on the signal, we predict the
future importance of edges.

We generally follow the procedures in Section 4, except for the following
differences: (a) we examine the ratios of edge roles at each edge
$u\rightarrow v$ when the sum of the in-degrees of $u$ and $v$ becomes
$d_{\theta}$, (b) we use edge betweenness centrality (Freeman, 1977) as the
importance measure, (c) we formulate the problem of predicting future edge
importance as described in Problem 2, (d) we extract feature sets Local-ER and
Global-ER using the (relative) counts of edge roles at edges as we extract
Local-NR and Global-NR, and (e) we union Global-ER and Global-Basic for ALL.

###### Problem 2 (Edge Centrality Prediction).

$\bullet$ Given: the snapshot $\mathcal{G}^{(t_{e,d_{\theta}})}$ of the input
graph when the sum of the in-degrees of the endpoints of each edge first
reaches $d_{\theta}$, $\bullet$ Predict: whether the centrality of each edge
belongs to the top $20\%$ in the last snapshot of $\mathcal{G}$.

From Figure 5, Table 6, and Table 9, we draw the following observations.

###### Observation 9.

In real-world graphs, the signals from the local structures of edges in their
early stage regarding their future importance are weaker, compared to the
signals that from the local structures of nodes (see Figure 5).

###### Observation 10.

However, the signals become stronger as the edges are better connected,
leading to better prediction performance (see Tables 6 and 9).

###### Observation 11.

The features from edge roles (Local-ER and Global-ER) are more informative
than simple global statistics (Global-Basic) for future importance prediction
(see Table 9).

Table 9.  F1-score, accuracy, and AUROC on the task of predicting future edge
importance averaged over the 7 considered real-world graphs. Using edge role-
based features (Local-ER and Global-ER) yields better performance than using
Global-Basic in most settings. The overall performance improves with respect
to $d_{\theta}$. That is, as edges are better connected, their future
importance is predicted more accurately. Detailed results on each dataset can
be found in Appendix D.4

Target | Edge betweenness
---|---
Measure | F1-Score | Accuracy | AUROC
Local-ER $(d_{\theta}=2)$ | 0.45 | 0.78 | 0.76
Global-ER $(d_{\theta}=2)$ | 0.47 | 0.81 | 0.78
Global-Basic $(d_{\theta}=2)$ | 0.42 | 0.79 | 0.73
ALL $(d_{\theta}=2)$ | 0.50 | 0.80 | 0.75
ALL $(d_{\theta}=2)$ | 0.50 | 0.80 | 0.75
ALL $(d_{\theta}=4)$ | 0.53 | 0.82 | 0.84
ALL $(d_{\theta}=8)$ | 0.52 | 0.85 | 0.85

##  6\. Related Work

Previous studies on temporal graph analysis are largely categorized into (a)
designing algorithms for streaming graphs (Lee et al., 2020; Eswaran et al.,
2018; Liben-Nowell and Kleinberg, 2007; McGregor, 2014), (b) discovering
temporal patterns in graphs (Leskovec et al., 2005; Akoglu et al., 2008; Beyer
et al., 2010; Akoglu and Dalvi, 2010; Bahulkar et al., 2016), and (c)
generating graphs with realistic dynamics (Barabási and Albert, 1999; Leskovec
et al., 2010; Akoglu et al., 2008). This work belongs to the second category.

Studies in this category have revealed (a) universal temporal patterns, such
as densification (Leskovec et al., 2005), shrinking diameter (Leskovec et al.,
2005), and power-laws between principle eigenvalues and edge counts (Akoglu et
al., 2008); and (b) domain-specific patterns in hyperlink networks (Broder et
al., 2011), metabolic networks (e.g., biochemical reactions and protein
interactions) (Beyer et al., 2010), communication networks (e.g., phone calls
and texts) (Hidalgo and Rodríguez-Sickert, 2008; Akoglu and Dalvi, 2010), and
friendship networks (Bahulkar et al., 2016).

In particular, for the analysis of local structures, the concept of graphlets
(Pržulj, 2007) (i.e., the sets of isomorphic small subgraphs with a predefined
number of nodes) has been extended to temporal graphs. The extensions, which
are called temporal network motifs, have multiple variants. Kovanen et al.
(Kovanen et al., 2011) defined them as sets of temporal subgraphs with a fixed
number of nodes that are (a) topologically equivalent, (b) temporally
equivalent (specifically, relative orders of constituent edges are identical),
(c) consecutive (specifically, constituent edges are consecutive for every
node), and (d) temporally local (specifically, arrival times of consecutive
edges are close enough). Hulovaty et al. (Hulovatyy et al., 2015) ignores (c);
and Paranjape et al. (Paranjape et al., 2017) ignores (c) and relaxes (d) by
restricting only the time difference between the first edge and the last edge.
Note that all these notions focus on temporally local subgraphs, and thus they
are suitable only for analyzing short-term dynamics.

For long-term dynamics in local structures, David et al. (Aparício et al.,
2018) proposed Graph-orbit Transition (GoT) and Orbit Temporal Agreement
(OTA), which characterize the dynamic of a temporal graph by approximately
counting the number of transitions between node roles. However, due to high
computational overhead, only a small fraction of snapshots can be compared for
estimating the counts of transitions, and as a result, their characterization
powers are significantly weaker than our characterization method using GTGs
(see Section 3.2). Recall that our method counts “every” transition between
graphlets, and it is still significantly faster than GOT and OTA (see Section
A.1 in Appendix).

For predicting the future in-degree of nodes, Yang et al. (Yang et al., 2014)
proposed to use five features obtained from graphlets with three nodes (see
Section 4.2 for descriptions). As shown empirically, our proposed features
tend to provide better prediction performance than these five features, and
more importantly, they are complementary to each other. Faisal and Milenković
(Faisal and Milenković, 2014) aimed to detect aging-related nodes, whose
topological properties (e.g,. graphlet counts) change highly over time, in the
gene expression process.

On the algorithmic aspect, a great number of algorithms have been developed
for the problem of counting the instances of each graphlet, which is also
known as the subgraph counting problem. As suggested in a survey on subgraph
counting (Ribeiro et al., 2021), subgraph-counting algorithms are largely
categorized into exact counting (Milo et al., 2002; Schiller et al., 2015;
Ortmann and Brandes, 2017; Ahmed et al., 2017) and approximated counting
(Wernicke, 2005; Aslay et al., 2018). Those in the first category are further
categorized into enumeration-based approaches (Milo et al., 2002; Schiller et
al., 2015), matrix-based approaches (Ortmann and Brandes, 2017), and
decomposition-based approaches (Ahmed et al., 2017). Algorithm 1 belongs to
the first subcategory, and it achieves the optimal time complexity achievable
by those in this subcategory, as discussed in the beginning of Section 3.1. It
is adapted from StreaM (Schiller et al., 2015), which maintains the counts of
the instances of $4$-node undirected graphlets in a fully dynamic graph stream
(i.e., a stream of edge insertions and deletions).

##  7\. Conclusion

In this work, we examined the long-term evolution of local structures captured
by graphlets at the graph, node, and edge levels. We summarize our
contribution as follows:

  * $\bullet$

Patterns: We examined various patterns regarding the dynamics of local
structures in temporal graphs. For example, the distributions of graphlets
over time in real-world graphs differ significantly from those in random
graphs, and the transitions between graphlets are surprisingly similar in
graphs from the same domains. Moreover, local structures at nodes and edges in
their early stages provide strong signals regarding their future importance.

  * $\bullet$

Tools: We introduced graphlet transition graphs, and we demonstrated that it
is an effective tool for measuring the similarity between temporal graphs of
different sizes.

  * $\bullet$

Predictability: We enhanced the accuracy of predicting the future importance
of nodes and edges by introducing new features based on node roles and edge
roles. The features are also complementary to global graph statistics.

Reproducibility: The code and the datasets are available at
https://github.com/deukryeol-yoon/graphlets-over-time.

Table 10.  Results of feature importance analysis. We report the five
strongest predictors and their Gini importance.

Centrality | Rank 1 | Rank 2 | Rank 3 | Rank 4 | Rank 5
---|---|---|---|---|---
Degree |  # of edges |  |  0.07 |  Global-NPP 2 |  |  0.06 |  # of nodes |  |  0.06 |  Global-NR 3 |  |  0.04 |  Global-NR 10 |  |  0.03
Betweenness |  Local-NPP 2 |  |  0.10 |  Local-NR 4 |  |  0.09 |  Global-NR 4 |  |  0.08 |  Local-NR 9 |  |  0.06 |  Global-NR 3 |  |  0.05
Closeness |  Global-NR 5 |  |  0.09 |  Local-NR 5 |  |  0.07 |  # of edges |  |  0.07 |  Global-NPP 2 |  |  0.06 |  # of nodes |  |  0.06
PageRank |  Local-NR 1 |  |  0.07 |  # of edges |  |  0.06 |  Global-NPP 2 |  |  0.06 |  # of nodes |  |  0.05 |  Global-NR 1 |  |  0.05
Edge betweenness |  Global-ER 7 |  |  0.11 |  Global-ER 2 |  |  0.09 |  Global-ER 3 |  |  0.09 |  # of nodes |  |  0.07 |  Local-ER 7 |  |  0.07

## References

  * (1)
  * Ahmed et al. (2017) Nesreen K Ahmed, Jennifer Neville, Ryan A Rossi, Nick G Duffield, and Theodore L Willke. 2017.  Graphlet decomposition: Framework, algorithms, and applications.  _KAIS_ 50, 3 (2017), 689–722.
  * Akoglu and Dalvi (2010) Leman Akoglu and Bhavana Dalvi. 2010.  Structure, tie persistence and event detection in large phone and SMS networks. In _MLG_.
  * Akoglu et al. (2008) Leman Akoglu, Mary McGlohon, and Christos Faloutsos. 2008\.  RTM: Laws and a recursive generator for weighted time-evolving graphs. In _ICDM_.
  * Aparício et al. (2018) David Aparício, Pedro Ribeiro, and Fernando Silva. 2018\.  Graphlet-orbit Transitions (GoT): A fingerprint for temporal network comparison.  _PloS one_ 13, 10 (2018), e0205497.
  * Arenas et al. (2008) Alex Arenas, Alberto Fernandez, Santo Fortunato, and Sergio Gomez. 2008.  Motif-based communities in complex networks.  _Journal of Physics A: Mathematical and Theoretical_ 41, 22 (2008), 224001.
  * Aslay et al. (2018) Çigdem Aslay, Muhammad Anis Uddin Nasir, Gianmarco De Francisci Morales, and Aristides Gionis. 2018\.  Mining frequent patterns in evolving graphs. In _CIKM_.
  * Bahulkar et al. (2016) Ashwin Bahulkar, Boleslaw K Szymanski, Omar Lizardo, Yuxiao Dong, Yang Yang, and Nitesh V Chawla. 2016.  Analysis of link formation, persistence and dissolution in NetSense data. In _ASONAM_.
  * Barabási and Albert (1999) Albert-László Barabási and Réka Albert. 1999.  Emergence of scaling in random networks.  _science_ 286, 5439 (1999), 509–512.
  * Bavelas (1950) Alex Bavelas. 1950\.  Communication patterns in task-oriented groups.  _The journal of the acoustical society of America_ 22, 6 (1950), 725–730.
  * Benson et al. (2016) Austin R Benson, David F Gleich, and Jure Leskovec. 2016\.  Higher-order organization of complex networks.  _Science_ 353, 6295 (2016), 163–166.
  * Beyer et al. (2010) Antje Beyer, Peter Thomason, Xinzhong Li, James Scott, and Jasmin Fisher. 2010.  Mechanistic insights into metabolic disturbance during type-2 diabetes and obesity using qualitative networks.  In _Transactions on Computational Systems Biology XII_. Springer, 146–162.
  * Broder et al. (2011) Andrei Broder, Ravi Kumar, Farzin Maghoul, Prabhakar Raghavan, Sridhar Rajagopalan, Raymie Stata, Andrew Tomkins, and Janet Wiener. 2011.  Graph structure in the web.  In _The Structure and Dynamics of Networks_. Princeton University Press, 183–194.
  * Eswaran et al. (2018) Dhivya Eswaran, Christos Faloutsos, Sudipto Guha, and Nina Mishra. 2018.  Spotlight: Detecting anomalies in streaming graphs. In _KDD_.
  * Faisal and Milenković (2014) Fazle E Faisal and Tijana Milenković. 2014.  Dynamic networks reveal key players in aging.  _Bioinformatics_ 30, 12 (2014), 1721–1729.
  * Freeman (1977) Linton C Freeman. 1977\.  A set of measures of centrality based on betweenness.  _Sociometry_ (1977), 35–41.
  * Hidalgo and Rodríguez-Sickert (2008) Cesar A Hidalgo and Carlos Rodríguez-Sickert. 2008\.  The dynamics of a mobile phone network.  _Physica A: Statistical Mechanics and its Applications_ 387, 12 (2008), 3017–3024.
  * Hočevar and Demšar (2016) Tomaž Hočevar and Janez Demšar. 2016.  Computation of graphlet orbits for nodes and edges in sparse graphs.  _Journal of Statistical Software_ 71, 1 (2016), 1–24.
  * Hsieh and Liu (2008) Eric Hsieh and Jen-pei Liu. 2008.  On statistical evaluation of the linearity in assay validation.  _Journal of biopharmaceutical statistics_ 18, 4 (2008), 677–690.
  * Hulovatyy et al. (2015) Yuriy Hulovatyy, Huili Chen, and Tijana Milenković. 2015\.  Exploring the structure and function of temporal networks with dynamic graphlets.  _Bioinformatics_ 31, 12 (2015), i171–i180.
  * Juszczyszyn and Kołaczek (2011) Krzysztof Juszczyszyn and Grzegorz Kołaczek. 2011.  Motif-based attack detection in network communication graphs. In _CMS_.
  * Kovanen et al. (2011) Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. 2011\.  Temporal motifs in time-dependent networks.  _Journal of Statistical Mechanics: Theory and Experiment_ 2011, 11 (2011), P11005.
  * Kroll and Emancipator (1993) Martin H Kroll and Kenneth Emancipator. 1993.  A theoretical evaluation of linearity.  _Clinical chemistry_ 39, 3 (1993), 405–413.
  * Lee et al. (2020) Dongjin Lee, Kijung Shin, and Christos Faloutsos. 2020.  Temporal locality-aware sampling for accurate triangle counting in real graph streams.  _VLDB_ 29, 6 (2020), 1501–1525.
  * Lee et al. (2019) John Boaz Lee, Ryan A Rossi, Xiangnan Kong, Sungchul Kim, Eunyee Koh, and Anup Rao. 2019\.  Graph convolutional networks with motif-based attention. In _CIKM_.
  * Leskovec et al. (2010) Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. 2010\.  Kronecker graphs: an approach to modeling networks.  _JMLR_ 11, 2 (2010).
  * Leskovec et al. (2005) Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. 2005\.  Graphs over time: densification laws, shrinking diameters and possible explanations. In _KDD_.
  * Liben-Nowell and Kleinberg (2007) David Liben-Nowell and Jon Kleinberg. 2007.  The link-prediction problem for social networks.  _JASIST_ 58, 7 (2007), 1019–1031.
  * Liu et al. (2021) Zhijun Liu, Chao Huang, Yanwei Yu, and Junyu Dong. 2021\.  Motif-Preserving Dynamic Attributed Network Embedding. In _WWW_.
  * Loh (2011) Wei-Yin Loh. 2011\.  Classification and regression trees.  _WIREs: data mining and knowledge discovery_ 1, 1 (2011), 14–23.
  * McGregor (2014) Andrew McGregor. 2014\.  Graph stream algorithms: a survey.  _ACM SIGMOD Record_ 43, 1 (2014), 9–20.
  * Milo et al. (2004) Ron Milo, Shalev Itzkovitz, Nadav Kashtan, Reuven Levitt, Shai Shen-Orr, Inbal Ayzenshtat, Michal Sheffer, and Uri Alon. 2004\.  Superfamilies of evolved and designed networks.  _Science_ 303, 5663 (2004), 1538–1542.
  * Milo et al. (2002) Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002\.  Network motifs: simple building blocks of complex networks.  _Science_ 298, 5594 (2002), 824–827.
  * Ortmann and Brandes (2017) Mark Ortmann and Ulrik Brandes. 2017.  Efficient orbit-aware triad and quad census in directed and undirected graphs.  _Applied network science_ 2, 1 (2017), 1–17.
  * Page et al. (1999) Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999.  _The PageRank citation ranking: Bringing order to the web._ Technical Report. Stanford InfoLab.
  * Paranjape et al. (2017) Ashwin Paranjape, Austin R Benson, and Jure Leskovec. 2017\.  Motifs in temporal networks. In _WSDM_.
  * Pržulj (2007) Nataša Pržulj. 2007\.  Biological network comparison using graphlet degree distribution.  _Bioinformatics_ 23, 2 (2007), e177–e183.
  * Ribeiro et al. (2021) Pedro Ribeiro, Pedro Paredes, Miguel EP Silva, David Aparicio, and Fernando Silva. 2021\.  A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets.  _CSUR_ 54, 2 (2021), 1–36.
  * Schiller et al. (2015) Benjamin Schiller, Sven Jager, Kay Hamacher, and Thorsten Strufe. 2015.  Stream-A stream-based algorithm for counting motifs in dynamic graphs. In _AlCoB_.
  * Tsourakakis et al. (2017) Charalampos E Tsourakakis, Jakub Pachocki, and Michael Mitzenmacher. 2017.  Scalable motif-aware graph clustering. In _WWW_.
  * Wernicke (2005) Sebastian Wernicke. 2005\.  A faster algorithm for detecting network motifs. In _WABI_. Springer, 165–177.
  * Yang et al. (2014) Yang Yang, Yuxiao Dong, and Nitesh V Chawla. 2014.  Predicting node degree centrality with the node prominence profile.  _Scientific reports_ 4, 1 (2014), 1–7.
  * Yu et al. (2019) Yanlei Yu, Zhiwu Lu, Jiajun Liu, Guoping Zhao, and Ji-rong Wen. 2019.  Rum: Network representation learning using motifs. In _ICDE_.
  * Zwillinger and Kokoska (1999) Daniel Zwillinger and Stephen Kokoska. 1999.  _CRC standard probability and statistics tables and formulae_.  Crc Press.

(a) Ours

(b) GoT

(c) OTA

Figure 6. Similarity matrices from ours, GoT, and OTA. The domains of graphs
(distinguished by colors) are classified more accurately by ours than by GoT
or OTA.

##  Appendix A.1 Comparison with GoT and OTA

We provide additional details regarding the comparison between our
characterization method based on graphlet transition graphs (GTGs) and
regarding the comparison with Graphlet-orbit Transition (GoT) and Orbit
Temporal Agreement (OTA).

Detailed Setting: Our experiments were conducted on a desktop with a 3.8 GHz
AMD Ryzen 3900x CPU and 128GB memory. We implemented our characterization
method based on GTGs in Java, and we used the official implementations for GoT
and OTA provided by the authors, which were implemented in C++. In each
dataset, we used $12$ snapshots with the same intervals for GoT and OTA.

Output Similar Matrix: Figure 6 shows the output similar matrices from our
characterization method based on GTGs, GoT, and OTA. GoT and OTA run out of
memory in the two largest datasets (Patent and Stackoverflow). Both GoT and
OTA fail to distinguish email/message graphs (blue) and online Q/A graphs
(green) clearly. Numerically, with the best thresholds of similarity, the
classification accuracies are $81.0\%$ (GoT) and $85.7\%$ (OTA), while the
accuracy is $97.2\%$ in ours.

Figure 7.  Running times of ours, GoT and OTA. Ours is consistently and
significantly faster than both competitors, which run out of memory in the two
largest datasets.

Speed Comparison: As seen in Figure 7, ours is faster than GoT and OTA in all
the graphs. Specifically, ours is $6.68\times$ faster than the others on
average.

##  Appendix B.2 Feature Important Analysis

We measure the importance of each feature in the set ALL (see Section 4.2 of
the main paper) using the Gini importance (Loh, 2011), and we report the top
five important features in Table 10.

Table 11.  F1-score on the task of predicting future node importance when
$d_{\theta}=2$.

Centrality | Feature | Citation Networks | Email/Message Networks | Online Q/A Networks | Average
---|---|---|---|---|---
HepPh | Hepth | Email-EU | Email-Enron | Message-College | Mathoverflow | Askubuntu
Degree | Local-NR | 0.11$\pm$0.008 | 0.20$\pm$0.014 | 0.36$\pm$0.092 | 0.68$\pm$0.007 | 0.27$\pm$0.027 | 0.38$\pm$0.017 |  0.73$\pm$0.002 | 0.39
Local-NPP | 0.12$\pm$0.013 | 0.19$\pm$0.016 | 0.40$\pm$0.102 | 0.60$\pm$0.011 | 0.27$\pm$0.040 | 0.36$\pm$0.016 |  0.72$\pm$0.003 | 0.38
Global-NR |  0.52$\pm$0.013 | 0.56$\pm$0.013 |  0.51$\pm$0.077 |  0.79$\pm$0.004 | 0.37$\pm$0.025 |  0.52$\pm$0.021 | 0.70$\pm$0.004 | 0.57
Global-NPP | 0.51$\pm$0.010 |  0.57$\pm$0.018 |  0.51$\pm$0.063 | 0.76$\pm$0.005 |  0.40$\pm$0.030 |  0.52$\pm$0.022 | 0.70$\pm$0.006 | 0.57
Global-basic | 0.36$\pm$0.014 | 0.38$\pm$0.024 | 0.44$\pm$0.073 |  0.77$\pm$0.008 | 0.34$\pm$0.050 |  0.51$\pm$0.022 | 0.71$\pm$0.003 | 0.50
ALL |  0.53$\pm$0.010 |  0.58$\pm$0.013 |  0.52$\pm$0.043 |  0.79$\pm$0.008 |  0.38$\pm$0.041 |  0.52$\pm$0.026 | 0.70$\pm$0.005 | 0.57
Betweenness | Local-NR | 0.59$\pm$0.011 | 0.88$\pm$0.009 | 0.34$\pm$0.063 | 0.49$\pm$0.011 | 0.34$\pm$0.033 |  0.74$\pm$0.011 |  0.73$\pm$0.007 | 0.59
Local-NPP | 0.58$\pm$0.010 | 0.87$\pm$0.006 | 0.35$\pm$0.076 | 0.45$\pm$0.010 | 0.36$\pm$0.073 |  0.74$\pm$0.011 |  0.73$\pm$0.007 | 0.58
Global-NR |  0.64$\pm$0.007 |  0.90$\pm$0.005 | 0.48$\pm$0.089 |  0.62$\pm$0.014 |  0.38$\pm$0.047 |  0.75$\pm$0.008 |  0.74$\pm$0.006 | 0.64
Global-NPP |  0.62$\pm$0.010 |  0.89$\pm$0.006 |  0.49$\pm$0.037 |  0.58$\pm$0.019 |  0.40$\pm$0.034 |  0.75$\pm$0.010 |  0.74$\pm$0.006 | 0.64
Global-basic | 0.01$\pm$0.003 | 0.27$\pm$0.028 | 0.40$\pm$0.079 | 0.36$\pm$0.017 | 0.25$\pm$0.038 | 0.32$\pm$0.013 | 0.10$\pm$0.013 | 0.24
ALL |  0.64$\pm$0.007 |  0.90$\pm$0.007 |  0.53$\pm$0.052 |  0.62$\pm$0.016 |  0.38$\pm$0.045 |  0.75$\pm$0.010 |  0.74$\pm$0.007 | 0.65
Closeness | Local-NR | 0.49$\pm$0.010 | 0.53$\pm$0.010 | 0.28$\pm$0.077 | 0.69$\pm$0.008 | 0.24$\pm$0.034 | 0.58$\pm$0.014 |  0.75$\pm$0.005 | 0.51
Local-NPP | 0.37$\pm$0.015 | 0.51$\pm$0.014 | 0.31$\pm$0.067 | 0.46$\pm$0.010 | 0.25$\pm$0.038 | 0.43$\pm$0.017 | 0.66$\pm$0.006 | 0.43
Global-NR |  0.84$\pm$0.006 |  0.75$\pm$0.007 | 0.47$\pm$0.046 |  0.83$\pm$0.008 |  0.38$\pm$0.055 |  0.69$\pm$0.024 |  0.81$\pm$0.002 | 0.68
Global-NPP | 0.83$\pm$0.008 | 0.74$\pm$0.007 |  0.52$\pm$0.047 |  0.76$\pm$0.008 |  0.39$\pm$0.022 |  0.64$\pm$0.019 | 0.71$\pm$0.005 | 0.66
Global-basic | 0.82$\pm$0.004 | 0.70$\pm$0.010 | 0.44$\pm$0.074 | 0.72$\pm$0.010 | 0.33$\pm$0.010 | 0.51$\pm$0.015 | 0.60$\pm$0.004 | 0.59
ALL |  0.85$\pm$0.008 |  0.76$\pm$0.008 |  0.53$\pm$0.043 |  0.83$\pm$0.007 | 0.36$\pm$0.051 |  0.69$\pm$0.022 |  0.81$\pm$0.003 | 0.69
PageRank | Local-NR | 0.44$\pm$0.013 | 0.15$\pm$0.018 | 0.42$\pm$0.069 | 0.64$\pm$0.008 | 0.25$\pm$0.038 | 0.46$\pm$0.016 | 0.58$\pm$0.009 | 0.42
Local-NPP | 0.41$\pm$0.012 | 0.18$\pm$0.017 | 0.43$\pm$0.086 | 0.39$\pm$0.009 | 0.25$\pm$0.040 | 0.41$\pm$0.013 | 0.53$\pm$0.008 | 0.37
Global-NR |  0.64$\pm$0.014 | 0.41$\pm$0.015 |  0.49$\pm$0.078 |  0.74$\pm$0.006 | 0.35$\pm$0.056 |  0.53$\pm$0.019 |  0.63$\pm$0.009 | 0.54
Global-NPP |  0.64$\pm$0.012 |  0.43$\pm$0.015 |  0.55$\pm$0.046 |  0.65$\pm$0.011 |  0.38$\pm$0.047 |  0.52$\pm$0.017 |  0.61$\pm$0.007 | 0.54
Global-basic |  0.63$\pm$0.010 | 0.31$\pm$0.023 | 0.41$\pm$0.054 |  0.65$\pm$0.007 | 0.28$\pm$0.035 | 0.49$\pm$0.010 | 0.54$\pm$0.008 | 0.47
ALL |  0.64$\pm$0.009 |  0.44$\pm$0.013 |  0.55$\pm$0.035 |  0.74$\pm$0.006 |  0.37$\pm$0.030 |  0.53$\pm$0.020 |  0.63$\pm$0.008 | 0.56

Table 12.  Accuracy on the task of predicting future node importance when
$d_{\theta}=2$.

Centrality | Feature | Citation Networks | Email/Message Networks | Online Q/A Networks | Average
---|---|---|---|---|---
HepPh | Hepth | Email-EU | Email-Enron | Message-College | Mathoverflow | Askubuntu
Degree | Local-NR | 0.71$\pm$0.008 | 0.72$\pm$0.006 |  0.80$\pm$0.024 | 0.62$\pm$0.006 |  0.77$\pm$0.019 | 0.66$\pm$0.008 | 0.58$\pm$0.003 | 0.69
Local-NPP | 0.71$\pm$0.010 | 0.72$\pm$0.007 | 0.79$\pm$0.031 | 0.55$\pm$0.006 | 0.75$\pm$0.020 | 0.65$\pm$0.016 | 0.58$\pm$0.002 | 0.68
Global-NR |  0.76$\pm$0.007 |  0.77$\pm$0.007 |  0.82$\pm$0.024 |  0.77$\pm$0.004 |  0.76$\pm$0.017 |  0.68$\pm$0.014 |  0.61$\pm$0.004 | 0.74
Global-NPP |  0.75$\pm$0.003 |  0.77$\pm$0.007 |  0.80$\pm$0.023 |  0.75$\pm$0.004 |  0.77$\pm$0.019 |  0.68$\pm$0.012 |  0.61$\pm$0.004 | 0.73
Global-basic | 0.73$\pm$0.006 | 0.74$\pm$0.008 | 0.77$\pm$0.028 |  0.75$\pm$0.006 | 0.74$\pm$0.019 |  0.67$\pm$0.011 |  0.60$\pm$0.003 | 0.72
ALL |  0.76$\pm$0.008 |  0.78$\pm$0.006 |  0.82$\pm$0.019 |  0.77$\pm$0.005 |  0.76$\pm$0.016 |  0.68$\pm$0.014 |  0.61$\pm$0.004 | 0.74
Betweenness | Local-NR | 0.79$\pm$0.005 |  0.93$\pm$0.005 | 0.78$\pm$0.017 | 0.82$\pm$0.006 |  0.76$\pm$0.019 |  0.86$\pm$0.005 |  0.90$\pm$0.003 | 0.83
Local-NPP | 0.79$\pm$0.004 | 0.92$\pm$0.004 | 0.75$\pm$0.028 | 0.81$\pm$0.005 | 0.65$\pm$0.032 |  0.86$\pm$0.005 |  0.90$\pm$0.003 | 0.81
Global-NR |  0.81$\pm$0.004 |  0.94$\pm$0.003 |  0.81$\pm$0.017 |  0.84$\pm$0.007 |  0.75$\pm$0.016 |  0.86$\pm$0.004 |  0.90$\pm$0.002 | 0.84
Global-NPP |  0.80$\pm$0.005 |  0.94$\pm$0.003 | 0.79$\pm$0.021 |  0.83$\pm$0.007 |  0.76$\pm$0.020 |  0.86$\pm$0.004 |  0.90$\pm$0.003 | 0.84
Global-basic | 0.71$\pm$0.005 | 0.73$\pm$0.010 | 0.75$\pm$0.033 | 0.77$\pm$0.007 | 0.70$\pm$0.019 |  0.67$\pm$0.008 |  0.77$\pm$0.004 | 0.73
ALL |  0.81$\pm$0.003 |  0.94$\pm$0.004 |  0.82$\pm$0.018 |  0.84$\pm$0.008 |  0.75$\pm$0.019 |  0.86$\pm$0.004 |  0.90$\pm$0.003 | 0.85
Closeness | Local-NR | 0.76$\pm$0.003 | 0.76$\pm$0.005 | 0.78$\pm$0.027 | 0.75$\pm$0.005 |  0.76$\pm$0.015 | 0.72$\pm$0.006 |  0.78$\pm$0.003 | 0.76
Local-NPP | 0.73$\pm$0.003 | 0.75$\pm$0.006 | 0.75$\pm$0.032 | 0.63$\pm$0.007 | 0.74$\pm$0.016 | 0.65$\pm$0.010 | 0.64$\pm$0.004 | 0.70
Global-NR |  0.91$\pm$0.003 |  0.86$\pm$0.004 | 0.80$\pm$0.018 |  0.85$\pm$0.006 |  0.75$\pm$0.019 |  0.77$\pm$0.011 |  0.82$\pm$0.002 | 0.82
Global-NPP |  0.90$\pm$0.005 |  0.85$\pm$0.002 |  0.81$\pm$0.013 |  0.80$\pm$0.007 |  0.76$\pm$0.011 |  0.73$\pm$0.010 | 0.73$\pm$0.003 | 0.80
Global-basic |  0.90$\pm$0.003 | 0.82$\pm$0.004 | 0.76$\pm$0.033 | 0.77$\pm$0.008 | 0.73$\pm$0.024 | 0.66$\pm$0.009 | 0.64$\pm$0.003 | 0.75
ALL |  0.91$\pm$0.004 |  0.86$\pm$0.004 |  0.82$\pm$0.020 |  0.85$\pm$0.005 | 0.75$\pm$0.017 |  0.77$\pm$0.011 |  0.82$\pm$0.002 | 0.83
PageRank | Local-NR |  0.76$\pm$0.007 | 0.72$\pm$0.009 | 0.80$\pm$0.020 |  0.74$\pm$0.006 |  0.75$\pm$0.017 | 0.66$\pm$0.011 | 0.65$\pm$0.006 | 0.73
Local-NPP | 0.74$\pm$0.007 | 0.72$\pm$0.007 | 0.77$\pm$0.023 | 0.65$\pm$0.018 | 0.73$\pm$0.023 | 0.63$\pm$0.005 | 0.62$\pm$0.006 | 0.69
Global-NR |  0.81$\pm$0.005 |  0.75$\pm$0.007 |  0.81$\pm$0.022 |  0.80$\pm$0.005 |  0.75$\pm$0.015 |  0.68$\pm$0.010 |  0.67$\pm$0.006 | 0.75
Global-NPP |  0.81$\pm$0.005 |  0.74$\pm$0.007 |  0.82$\pm$0.023 |  0.74$\pm$0.011 |  0.76$\pm$0.019 |  0.67$\pm$0.008 |  0.66$\pm$0.006 | 0.74
Global-basic |  0.81$\pm$0.004 | 0.73$\pm$0.008 | 0.75$\pm$0.021 |  0.74$\pm$0.006 | 0.70$\pm$0.025 | 0.65$\pm$0.007 | 0.59$\pm$0.006 | 0.71
ALL |  0.81$\pm$0.005 |  0.75$\pm$0.004 |  0.81$\pm$0.017 |  0.80$\pm$0.006 |  0.75$\pm$0.014 |  0.68$\pm$0.010 |  0.67$\pm$0.005 | 0.75

##  Appendix C.3 Detailed Results of Future Node Importance Prediction

In Tables 11-16, we provide the average predictive performances and standard
deviations over $10$ runs on the task of predicting future node centrality in
each real-world graph in terms of several evaluation metrics. The detailed
experimental settings can be found in Section 4.2 of the main paper.

##  Appendix D.4 Detailed Results of Future Edge Importance Prediction

In Tables 17-19, we provide the average predictive performances and standard
deviations over $10$ runs on the task of predicting future node centrality in
each real-world graph in terms of several evaluation metrics. The detailed
experimental settings can be found in Section 5 of the main paper.

Table 13.  AUROC on the task of predicting future node importance when
$d_{\theta}=2$.

Centrality | Feature | Citation Networks | Email/Message Networks | Online Q/A Networks | Average
---|---|---|---|---|---
HepPh | Hepth | Email-EU | Email-Enron | Message-College | Mathoverflow | Askubuntu
Degree | Local-NR | 0.69$\pm$0.006 | 0.70$\pm$0.006 | 0.80$\pm$0.037 | 0.67$\pm$0.007 | 0.69$\pm$0.020 | 0.65$\pm$0.012 | 0.58$\pm$0.006 | 0.68
Local-NPP | 0.64$\pm$0.005 | 0.67$\pm$0.007 | 0.75$\pm$0.032 | 0.56$\pm$0.007 | 0.64$\pm$0.025 | 0.63$\pm$0.012 | 0.56$\pm$0.004 | 0.64
Global-NR |  0.81$\pm$0.004 |  0.83$\pm$0.005 |  0.85$\pm$0.037 |  0.86$\pm$0.005 |  0.73$\pm$0.026 |  0.71$\pm$0.013 |  0.65$\pm$0.006 | 0.78
Global-NPP |  0.80$\pm$0.002 |  0.83$\pm$0.005 |  0.83$\pm$0.032 | 0.83$\pm$0.005 |  0.74$\pm$0.026 |  0.71$\pm$0.012 |  0.65$\pm$0.005 | 0.77
Global-basic | 0.74$\pm$0.004 | 0.74$\pm$0.007 | 0.82$\pm$0.035 |  0.84$\pm$0.006 | 0.68$\pm$0.037 |  0.68$\pm$0.009 |  0.62$\pm$0.005 | 0.73
ALL |  0.81$\pm$0.004 |  0.84$\pm$0.006 |  0.85$\pm$0.036 |  0.86$\pm$0.005 |  0.73$\pm$0.025 |  0.71$\pm$0.014 |  0.65$\pm$0.006 | 0.78
Betweenness | Local-NR | 0.84$\pm$0.006 |  0.98$\pm$0.002 | 0.79$\pm$0.033 | 0.80$\pm$0.007 | 0.70$\pm$0.029 |  0.83$\pm$0.010 |  0.82$\pm$0.005 | 0.82
Local-NPP | 0.83$\pm$0.006 |  0.98$\pm$0.003 | 0.73$\pm$0.031 | 0.68$\pm$0.008 | 0.65$\pm$0.041 | 0.82$\pm$0.010 | 0.81$\pm$0.006 | 0.79
Global-NR |  0.87$\pm$0.005 |  0.99$\pm$0.002 |  0.81$\pm$0.030 |  0.87$\pm$0.007 |  0.71$\pm$0.032 |  0.86$\pm$0.008 |  0.86$\pm$0.005 | 0.85
Global-NPP |  0.85$\pm$0.007 |  0.98$\pm$0.002 |  0.81$\pm$0.032 |  0.84$\pm$0.008 |  0.72$\pm$0.033 |  0.86$\pm$0.008 |  0.86$\pm$0.005 | 0.85
Global-basic | 0.62$\pm$0.008 | 0.74$\pm$0.013 | 0.76$\pm$0.042 | 0.74$\pm$0.005 | 0.63$\pm$0.038 | 0.63$\pm$0.014 | 0.60$\pm$0.007 | 0.67
ALL |  0.87$\pm$0.006 |  0.99$\pm$0.001 |  0.83$\pm$0.024 |  0.87$\pm$0.007 |  0.71$\pm$0.033 |  0.86$\pm$0.009 |  0.86$\pm$0.005 | 0.86
Closeness | Local-NR | 0.79$\pm$0.005 | 0.79$\pm$0.006 | 0.76$\pm$0.047 | 0.84$\pm$0.006 | 0.68$\pm$0.026 | 0.76$\pm$0.009 | 0.84$\pm$0.002 | 0.78
Local-NPP | 0.74$\pm$0.005 | 0.78$\pm$0.008 | 0.72$\pm$0.042 | 0.65$\pm$0.009 | 0.61$\pm$0.022 | 0.63$\pm$0.007 | 0.70$\pm$0.005 | 0.69
Global-NR |  0.97$\pm$0.002 |  0.93$\pm$0.005 |  0.82$\pm$0.035 |  0.93$\pm$0.003 |  0.73$\pm$0.024 |  0.83$\pm$0.011 |  0.89$\pm$0.002 | 0.87
Global-NPP |  0.96$\pm$0.003 | 0.92$\pm$0.004 |  0.83$\pm$0.028 |  0.88$\pm$0.004 |  0.73$\pm$0.026 |  0.79$\pm$0.011 | 0.81$\pm$0.003 | 0.85
Global-basic | 0.95$\pm$0.003 | 0.89$\pm$0.005 | 0.79$\pm$0.044 | 0.85$\pm$0.007 | 0.69$\pm$0.035 | 0.68$\pm$0.012 | 0.70$\pm$0.003 | 0.79
ALL |  0.97$\pm$0.002 |  0.94$\pm$0.005 |  0.82$\pm$0.027 |  0.93$\pm$0.004 |  0.75$\pm$0.028 |  0.83$\pm$0.010 |  0.90$\pm$0.001 | 0.88
PageRank | Local-NR | 0.77$\pm$0.006 | 0.65$\pm$0.010 | 0.80$\pm$0.031 | 0.81$\pm$0.004 |  0.67$\pm$0.011 | 0.69$\pm$0.015 | 0.70$\pm$0.006 | 0.73
Local-NPP | 0.75$\pm$0.004 | 0.63$\pm$0.008 | 0.77$\pm$0.031 | 0.63$\pm$0.010 | 0.62$\pm$0.024 | 0.64$\pm$0.009 | 0.67$\pm$0.006 | 0.67
Global-NR |  0.87$\pm$0.005 |  0.78$\pm$0.006 |  0.84$\pm$0.035 |  0.88$\pm$0.003 |  0.72$\pm$0.029 |  0.71$\pm$0.012 |  0.73$\pm$0.005 | 0.79
Global-NPP |  0.86$\pm$0.005 | 0.77$\pm$0.007 |  0.85$\pm$0.028 |  0.82$\pm$0.008 |  0.72$\pm$0.018 |  0.70$\pm$0.011 |  0.71$\pm$0.006 | 0.78
Global-basic |  0.86$\pm$0.005 | 0.73$\pm$0.010 | 0.81$\pm$0.033 | 0.81$\pm$0.008 | 0.66$\pm$0.026 | 0.66$\pm$0.011 | 0.62$\pm$0.004 | 0.74
ALL |  0.87$\pm$0.005 |  0.79$\pm$0.007 |  0.85$\pm$0.035 |  0.88$\pm$0.004 |  0.72$\pm$0.031 |  0.71$\pm$0.014 |  0.73$\pm$0.005 | 0.79

Table 14.  F1-score on the task of predicting future node importance depending
on $d_{\theta}$ (i.e., in-degree of nodes when their input features are
extracted).

Centrality | Feature | Citation Networks | Email/Message Networks | Online Q/A Networks | Average
---|---|---|---|---|---
HepPh | Hepth | Email-EU | Email-Enron | Message-College | Mathoverflow | Askubuntu
Degree | ALL $(d_{\theta}=2)$ | 0.53$\pm$0.010 | 0.58$\pm$0.013 |  0.52$\pm$0.043 | 0.19$\pm$0.005 | 0.38$\pm$0.041 |  0.52$\pm$0.026 | 0.70$\pm$0.005 | 0.59
ALL $(d_{\theta}=4)$ |  0.67$\pm$0.007 |  0.78$\pm$0.008 |  0.62$\pm$0.062 | 1.00* |  0.49$\pm$0.045 |  0.89$\pm$0.006 | 1.00* | 0.69
ALL $(d_{\theta}=8)$ |  0.82$\pm$0.006 |  0.93$\pm$0.006 |  0.74$\pm$0.036 | 1.00* |  0.71$\pm$0.022 | 1.00* | 1.00* | 0.80
Betweenness | ALL $(d_{\theta}=2)$ | 0.64$\pm$0.007 | 0.90$\pm$0.007 |  0.53$\pm$0.052 | 0.62$\pm$0.016 | 0.38$\pm$0.045 | 0.75$\pm$0.010 | 0.74$\pm$0.007 | 0.65
ALL $(d_{\theta}=4)$ |  0.72$\pm$0.012 |  0.94$\pm$0.007 | 0.52$\pm$0.066 |  0.75$\pm$0.006 |  0.50$\pm$0.042 |  0.84$\pm$0.009 |  0.84$\pm$0.008 | 0.73
ALL $(d_{\theta}=8)$ |  0.77$\pm$0.008 |  0.97$\pm$0.005 |  0.65$\pm$0.045 |  0.86$\pm$0.009 |  0.69$\pm$0.057 |  0.91$\pm$0.009 |  0.89$\pm$0.007 | 0.82
Closeness | ALL $(d_{\theta}=2)$ | 0.85$\pm$0.008 | 0.76$\pm$0.008 | 0.53$\pm$0.043 | 0.83$\pm$0.007 | 0.36$\pm$0.051 | 0.69$\pm$0.022 | 0.81$\pm$0.003 | 0.69
ALL $(d_{\theta}=4)$ |  0.87$\pm$0.008 |  0.85$\pm$0.010 |  0.55$\pm$0.072 |  0.91$\pm$0.006 |  0.54$\pm$0.032 |  0.85$\pm$0.013 |  0.91$\pm$0.004 | 0.78
ALL $(d_{\theta}=8)$ |  0.88$\pm$0.007 |  0.90$\pm$0.009 |  0.65$\pm$0.061 |  0.97$\pm$0.004 |  0.74$\pm$0.045 |  0.95$\pm$0.007 |  0.98$\pm$0.003 | 0.86
PageRank | ALL $(d_{\theta}=2)$ | 0.64$\pm$0.009 | 0.44$\pm$0.013 | 0.52$\pm$0.035 | 0.74$\pm$0.006 | 0.37$\pm$0.030 | 0.53$\pm$0.020 | 0.63$\pm$0.006 | 0.55
ALL $(d_{\theta}=4)$ |  0.74$\pm$0.008 |  0.71$\pm$0.010 |  0.62$\pm$0.037 |  0.87$\pm$0.006 |  0.48$\pm$0.040 |  0.79$\pm$0.008 |  0.89$\pm$0.003 | 0.73
ALL $(d_{\theta}=8)$ |  0.83$\pm$0.007 |  0.85$\pm$0.012 |  0.68$\pm$0.049 |  0.95$\pm$0.003 |  0.72$\pm$0.033 |  0.95$\pm$0.006 |  0.98$\pm$0.003 | 0.85
* All nodes satisfying the condition on $d_{\theta}$ have the same class, belonging to top $20\%$ in terms of the considered centrality measure.

Table 15.  Accuracy on the task of predicting future node importance depending
on $d_{\theta}$.

Centrality | Feature | Citation Networks | Email/Message Networks | Online Q/A Networks | Average
---|---|---|---|---|---
HepPh | Hepth | Email-EU | Email-Enron | Message-College | Mathoverflow | Askubuntu
Degree | ALL $(d_{\theta}=2)$ |  0.76$\pm$0.008 | 0.78$\pm$0.006 | 0.82$\pm$0.019 | 0.77$\pm$0.005 |  0.76$\pm$0.016 |  0.68$\pm$0.014 | 0.61$\pm$0.004 | 0.74
ALL $(d_{\theta}=4)$ |  0.76$\pm$0.006 |  0.80$\pm$0.009 |  0.83$\pm$0.028 | 1.00* | 0.70$\pm$0.046 |  0.81$\pm$0.009 | 1.00* | 0.78
ALL $(d_{\theta}=8)$ |  0.79$\pm$0.006 |  0.88$\pm$0.010 |  0.86$\pm$0.021 | 1.00* |  0.72$\pm$0.025 | 1.00* | 1.00* | 0.81
Betweenness | ALL $(d_{\theta}=2)$ | 0.81$\pm$0.003 | 0.94$\pm$0.004 |  0.82$\pm$0.018 |  0.84$\pm$0.008 |  0.75$\pm$0.019 |  0.86$\pm$0.004 |  0.90$\pm$0.003 | 0.85
ALL $(d_{\theta}=4)$ | 0.81$\pm$0.008 |  0.96$\pm$0.004 |  0.80$\pm$0.023 | 0.82$\pm$0.004 |  0.70$\pm$0.023 |  0.86$\pm$0.009 |  0.89$\pm$0.006 | 0.83
ALL $(d_{\theta}=8)$ | 0.81$\pm$0.004 |  0.98$\pm$0.004 |  0.82$\pm$0.019 |  0.85$\pm$0.009 |  0.70$\pm$0.049 |  0.88$\pm$0.010 | 0.88$\pm$0.006 | 0.85
Closeness | ALL $(d_{\theta}=2)$ | 0.91$\pm$0.004 | 0.86$\pm$0.004 |  0.82$\pm$0.020 | 0.85$\pm$0.005 |  0.75$\pm$0.017 | 0.77$\pm$0.011 | 0.82$\pm$0.002 | 0.83
ALL $(d_{\theta}=4)$ | 0.91$\pm$0.005 |  0.88$\pm$0.007 |  0.80$\pm$0.022 |  0.89$\pm$0.007 | 0.70$\pm$0.021 |  0.80$\pm$0.015 |  0.86$\pm$0.006 | 0.83
ALL $(d_{\theta}=8)$ | 0.91$\pm$0.006 |  0.89$\pm$0.009 |  0.82$\pm$0.020 |  0.94$\pm$0.006 |  0.73$\pm$0.046 |  0.91$\pm$0.013 |  0.95$\pm$0.006 | 0.88
PageRank | ALL $(d_{\theta}=2)$ |  0.81$\pm$0.005 |  0.75$\pm$0.004 | 0.81$\pm$0.017 | 0.80$\pm$0.006 |  0.75$\pm$0.014 |  0.68$\pm$0.010 | 0.67$\pm$0.006 | 0.75
ALL $(d_{\theta}=4)$ |  0.81$\pm$0.006 |  0.75$\pm$0.007 |  0.83$\pm$0.017 |  0.83$\pm$0.007 | 0.68$\pm$0.025 |  0.68$\pm$0.011 |  0.81$\pm$0.003 | 0.77
ALL $(d_{\theta}=8)$ |  0.83$\pm$0.005 |  0.81$\pm$0.012 |  0.82$\pm$0.023 |  0.92$\pm$0.004 |  0.72$\pm$0.025 |  0.91$\pm$0.011 |  0.96$\pm$0.003 | 0.85
* All nodes satisfying the condition on $d_{\theta}$ have the same class, belonging to top $20\%$ in terms of the considered centrality measure.

Table 16.  AUROC on the task of predicting future node importance depending on
$d_{\theta}$.

Centrality | Feature | Citation Networks | Email/Message Networks | Online Q/A Networks | Average
---|---|---|---|---|---
HepPh | Hepth | Email-EU | Email-Enron | Message-College | Mathoverflow | Askubuntu
Degree | ALL $(d_{\theta}=2)$ | 0.81$\pm$0.004 | 0.84$\pm$0.005 |  0.85$\pm$0.035 | 0.86$\pm$0.005 |  0.73$\pm$0.025 |  0.71$\pm$0.014 | 0.65$\pm$0.005 | 0.78
ALL $(d_{\theta}=4)$ |  0.83$\pm$0.005 |  0.87$\pm$0.006 |  0.85$\pm$0.036 | 1.00* | 0.72$\pm$0.027 |  0.68$\pm$0.018 | 1.00* | 0.79
ALL $(d_{\theta}=8)$ |  0.87$\pm$0.007 |  0.90$\pm$0.013 |  0.88$\pm$0.027 | 1.00* |  0.78$\pm$0.031 | 1.00* | 1.00* | 0.86
Betweenness | ALL $(d_{\theta}=2)$ | 0.87$\pm$0.005 |  0.99$\pm$0.001 |  0.83$\pm$0.024 | 0.87$\pm$0.007 | 0.71$\pm$0.033 | 0.86$\pm$0.009 | 0.86$\pm$0.005 | 0.86
ALL $(d_{\theta}=4)$ |  0.89$\pm$0.006 |  0.99$\pm$0.001 | 0.81$\pm$0.040 |  0.89$\pm$0.004 |  0.73$\pm$0.026 |  0.90$\pm$0.007 |  0.91$\pm$0.004 | 0.87
ALL $(d_{\theta}=8)$ |  0.90$\pm$0.003 |  1.00$\pm$0.001 |  0.84$\pm$0.026 |  0.93$\pm$0.006 |  0.77$\pm$0.044 |  0.94$\pm$0.009 |  0.94$\pm$0.006 | 0.90
Closeness | ALL $(d_{\theta}=2)$ | 0.97$\pm$0.002 | 0.94$\pm$0.005 |  0.84$\pm$0.033 | 0.93$\pm$0.004 | 0.73$\pm$0.028 | 0.83$\pm$0.010 | 0.90$\pm$0.002 | 0.88
ALL $(d_{\theta}=4)$ | 0.97$\pm$0.002 |  0.95$\pm$0.004 | 0.82$\pm$0.027 |  0.95$\pm$0.004 |  0.75$\pm$0.030 |  0.88$\pm$0.012 |  0.93$\pm$0.004 | 0.89
ALL $(d_{\theta}=8)$ | 0.97$\pm$0.003 |  0.96$\pm$0.006 |  0.88$\pm$0.024 |  0.98$\pm$0.004 |  0.79$\pm$0.043 |  0.92$\pm$0.016 |  0.95$\pm$0.013 | 0.92
PageRank | ALL $(d_{\theta}=2)$ | 0.87$\pm$0.005 | 0.79$\pm$0.008 |  0.85$\pm$0.035 | 0.88$\pm$0.004 |  0.72$\pm$0.031 |  0.71$\pm$0.014 |  0.73$\pm$0.005 | 0.79
ALL $(d_{\theta}=4)$ |  0.89$\pm$0.006 |  0.83$\pm$0.008 |  0.87$\pm$0.018 |  0.90$\pm$0.006 | 0.71$\pm$0.028 | 0.69$\pm$0.009 | 0.70$\pm$0.007 | 0.80
ALL $(d_{\theta}=8)$ |  0.91$\pm$0.005 |  0.87$\pm$0.013 |  0.87$\pm$0.034 |  0.95$\pm$0.009 |  0.79$\pm$0.018 |  0.73$\pm$0.040 |  0.71$\pm$0.049 | 0.83
* All nodes satisfying the condition on $d_{\theta}$ have the same class, belonging to top $20\%$ in terms of the considered centrality measure.

Table 17.  F1-score on the task of predicting future edge importance.

Centrality | Feature | Citation Networks | Email/Message Networks | Online Q/A Networks | Average
---|---|---|---|---|---
HepPh | Hepth | Email-EU | Email-Enron | Message-College | Mathoverflow | Askubuntu
Edge Betweenness | Local-ER $(d_{\theta}=2)$ | 0.68 $\pm$ 0.004 | 0.59 $\pm$ 0.011 | 0.14 $\pm$ 0.094 | 0.74 $\pm$ 0.013 |  0.41 $\pm$ 0.042 |  0.21 $\pm$ 0.038 |  0.40 $\pm$ 0.013 | 0.45
Global-ER $(d_{\theta}=2)$ |  0.69 $\pm$ 0.015 |  0.63 $\pm$ 0.041 | 0.18 $\pm$ 0.122 |  0.79 $\pm$ 0.051 | 0.38 $\pm$ 0.060 |  0.23 $\pm$ 0.058 |  0.39 $\pm$ 0.022 | 0.47
Global-Basic $(d_{\theta}=2)$ |  0.69 $\pm$ 0.013 | 0.51 $\pm$ 0.168 |  0.22 $\pm$ 0.132 | 0.75 $\pm$ 0.072 | 0.37 $\pm$ 0.064 | 0.15 $\pm$ 0.116 | 0.26 $\pm$ 0.180 | 0.42
ALL $(d_{\theta}=2)$ |  0.71 $\pm$ 0.005 |  0.68 $\pm$ 0.009 |  0.25 $\pm$ 0.186 |  0.84 $\pm$ 0.005 |  0.40 $\pm$ 0.062 |  0.23 $\pm$ 0.060 | 0.36 $\pm$ 0.018 | 0.50
ALL $(d_{\theta}=2)$ |  0.71 $\pm$ 0.005 | 0.68 $\pm$ 0.009 |  0.25 $\pm$ 0.186 |  0.84 $\pm$ 0.005 |  0.40 $\pm$ 0.062 | 0.23 $\pm$ 0.060 | 0.36 $\pm$ 0.018 | 0.50
ALL $(d_{\theta}=4)$ |  0.71 $\pm$ 0.007 |  0.72 $\pm$ 0.009 |  0.33 $\pm$ 0.104 |  0.77 $\pm$ 0.006 |  0.43 $\pm$ 0.086 |  0.29 $\pm$ 0.071 |  0.46 $\pm$ 0.014 | 0.53
ALL $(d_{\theta}=8)$ |  0.69 $\pm$ 0.004 |  0.75 $\pm$ 0.009 | 0.17 $\pm$ 0.079 | 0.72 $\pm$ 0.011 | 0.39 $\pm$ 0.052 |  0.31 $\pm$ 0.055 |  0.53 $\pm$ 0.023 | 0.52

Table 18.  Accuracy on the task of predicting future edge importance.

Centrality | Feature | Citation Networks | Email/Message Networks | Online Q/A Networks | Average
---|---|---|---|---|---
HepPh | Hepth | Email-EU | Email-Enron | Message-College | Mathoverflow | Askubuntu
Edge Betweenness | Local-ER $(d_{\theta}=2)$ | 0.66 $\pm$ 0.003 | 0.72 $\pm$ 0.005 |  0.87 $\pm$ 0.041 | 0.75 $\pm$ 0.012 |  0.70 $\pm$ 0.030 | 0.91 $\pm$ 0.008 | 0.91 $\pm$ 0.003 | 0.78
Global-ER $(d_{\theta}=2)$ |  0.68 $\pm$ 0.020 |  0.75 $\pm$ 0.023 |  0.88 $\pm$ 0.041 |  0.81 $\pm$ 0.058 |  0.70 $\pm$ 0.035 | 0.91 $\pm$ 0.009 | 0.91 $\pm$ 0.003 | 0.81
Global-Basic $(d_{\theta}=2)$ | 0.66 $\pm$ 0.036 | 0.72 $\pm$ 0.046 |  0.87 $\pm$ 0.040 |  0.79 $\pm$ 0.052 | 0.67 $\pm$ 0.053 | 0.91 $\pm$ 0.009 | 0.91 $\pm$ 0.008 | 0.79
ALL $(d_{\theta}=2)$ |  0.67 $\pm$ 0.037 |  0.73 $\pm$ 0.047 |  0.87 $\pm$ 0.042 |  0.81 $\pm$ 0.055 |  0.68 $\pm$ 0.052 | 0.91 $\pm$ 0.009 | 0.91 $\pm$ 0.007 | 0.80
ALL $(d_{\theta}=2)$ | 0.67 $\pm$ 0.037 | 0.73 $\pm$ 0.005 |  0.87 $\pm$ 0.042 |  0.81 $\pm$ 0.055 | 0.68 $\pm$ 0.052 | 0.91 $\pm$ 0.009 |  0.91 $\pm$ 0.007 | 0.80
ALL $(d_{\theta}=4)$ |  0.73 $\pm$ 0.006 |  0.79 $\pm$ 0.005 | 0.86 $\pm$ 0.050 | 0.78 $\pm$ 0.024 |  0.78 $\pm$ 0.024 |  0.93 $\pm$ 0.007 |  0.90 $\pm$ 0.004 | 0.82
ALL $(d_{\theta}=8)$ |  0.75 $\pm$ 0.003 |  0.81 $\pm$ 0.005 |  0.88 $\pm$ 0.046 |  0.82 $\pm$ 0.017 |  0.82 $\pm$ 0.017 |  0.94 $\pm$ 0.005 |  0.91 $\pm$ 0.002 | 0.85

Table 19.  AUROC on the task of predicting future edge importance.

Centrality | Feature | Citation Networks | Email/Message Networks | Online Q/A Networks | Average
---|---|---|---|---|---
HepPh | Hepth | Email-EU | Email-Enron | Message-College | Mathoverflow | Askubuntu
Edge Betweenness | Local-ER $(d_{\theta}=2)$ | 0.71 $\pm$ 0.003 | 0.77 $\pm$ 0.007 |  0.64 $\pm$ 0.080 | 0.82 $\pm$ 0.009 |  0.68 $\pm$ 0.035 |  0.85 $\pm$ 0.013 |  0.86 $\pm$ 0.006 | 0.76
Global-ER $(d_{\theta}=2)$ |  0.74 $\pm$ 0.027 |  0.80 $\pm$ 0.033 |  0.63 $\pm$ 0.092 |  0.88 $\pm$ 0.058 |  0.68 $\pm$ 0.032 |  0.85 $\pm$ 0.015 |  0.86 $\pm$ 0.007 | 0.78
Global-Basic $(d_{\theta}=2)$ | 0.71 $\pm$ 0.053 | 0.77 $\pm$ 0.055 |  0.64 $\pm$ 0.093 | 0.87 $\pm$ 0.049 | 0.65 $\pm$ 0.058 | 0.73 $\pm$ 0.164 | 0.76 $\pm$ 0.150 | 0.73
ALL $(d_{\theta}=2)$ |  0.72 $\pm$ 0.054 |  0.79 $\pm$ 0.057 |  0.64 $\pm$ 0.099 |  0.89 $\pm$ 0.051 |  0.66 $\pm$ 0.056 |  0.76 $\pm$ 0.150 |  0.78 $\pm$ 0.139 | 0.75
ALL $(d_{\theta}=2)$ | 0.72 $\pm$ 0.054 | 0.79 $\pm$ 0.057 | 0.64 $\pm$ 0.099 | 0.89 $\pm$ 0.051 | 0.66 $\pm$ 0.056 | 0.76 $\pm$ 0.150 | 0.78 $\pm$ 0.139 | 0.75
ALL $(d_{\theta}=4)$ |  0.80 $\pm$ 0.004 |  0.87 $\pm$ 0.004 |  0.75 $\pm$ 0.050 |  0.94 $\pm$ 0.002 |  0.74 $\pm$ 0.026 |  0.89 $\pm$ 0.016 |  0.89 $\pm$ 0.009 | 0.84
ALL $(d_{\theta}=8)$ |  0.82 $\pm$ 0.005 |  0.89 $\pm$ 0.005 |  0.70 $\pm$ 0.046 |  0.93 $\pm$ 0.002 |  0.79 $\pm$ 0.021 |  0.90 $\pm$ 0.011 |  0.90 $\pm$ 0.008 | 0.85