other information such as the local context matrix or even random features are
also used to enhance the performance of the GCN.

SMP. In order to improve the GCN’s performances on structure-related tasks,
Structural Message Passing (SMP) proposes to maintain a local context matrix
at each node, instead of a feature vector as in the vanilla GCN. Specifically,
each node is initialised as a one-hot encoding
$\boldsymbol{M}_{i}^{(0)}=\mathbbm{1}_{i}\in\mathbbm{R}^{n\times 1}$, and the
additional node feature $x_{i}$ of $v_{i}$ is appended at the $i$th row:
$M_{i}^{(0)}[i,:]=\left[1,x_{i}\right]\in\mathbbm{R}^{1+c_{X}}$. Then the
local context matrix of node $v_{i}$ at layer $l$ is formulated as:

(76)
$M_{i}^{(l)}=MLP_{1}^{(l-1)}\left(M_{i}^{(l-1)},AGG\left(\left\\{MLP_{2}^{(l-1)}\left(M_{i}^{(l-1)},M_{j}^{(l-1)},e_{ij}\right)\right\\}_{v_{j}\in
N_{i}}\right)\right).$

$AGG$ is an aggregation function which is by default a normalised sum
aggregator: $\left.\sum_{v_{j}\in
N_{i}}MLP_{2}^{(l-1)}\left(\boldsymbol{M}_{i}^{(l)},\boldsymbol{M}_{j}^{(l)},\boldsymbol{e}_{ij}\right)/d_{\mathrm{avg}}\right)$.
In this way, the $j$th row in $M_{i}$ is the representation node $v_{i}$ has
of node $v_{j}$. Finally, the vector form representation of node $v_{i}$ is
obtained through applying an equivariant neural network for sets on the rows
of its context matrix. Although node ordering is needed when constructing the
local context matrix, the learned representation is proven to be order-
invariant when $MLP_{1}$, $MLP_{2}$ and $AGG$ are permutation equivariant. SMP
is shown to excel in various tasks, such as the detection of structural
properties including distance, eccentricity connectivity, diameter, etc.

rGIN. Apart from various types of explicit structural features that are being
added to the GCN, another work (termed rGIN) proves that the expressive power
of the GCN can be enhanced by just adding random features to each node (Sato
et al., 2021). Specifically, rGIN first assigns a random value $r_{v}$ to each
node and concatenates it with the original node feature $x_{v}$, then performs
GIN’s convolutional operations:

(77) $\displaystyle
h_{v}^{(0)}=\operatorname{MLP}^{(0)}\left(CONCAT(x_{v},r_{v})\right),$
$\displaystyle
h_{v}^{(l)}=\operatorname{MLP}^{(l)}\left(\left(1+\varepsilon^{(l)}\right)h_{v}^{(l-1)}+\sum_{u\in\mathcal{N}(v)}h_{u}^{(l-1)}\right).$

With this simple modification on the initial node feature, rGIN is proven to
be able to distinguish any local structure with high probability. The idea of
injecting random features into nodes is that the GCN fails to distinguish
graphs with identical node features. For example, a GCN with the node degree
as an input feature cannot distinguish a node in a 3-cycle graph from a node
in a 6-cycle graph. rGIN is shown to perform well on structure-related tasks
such as learning the existence of triangles, learning the local clustering
coefficient, and learning the algorithm for the MDS (Minimum Dominating Set)
problem.

###  4.3. Learning scope

The third structural perspective on GCNs is regarding the learning scope or
the input graph. Whether it is full-batch or mini-batch training, most GCNs
still have the whole graph as an input, i.e., in an L-layer GCN, each node has
the scope of its L-hop neighbourhood in the original graph. A higher number of
layers leads to a neighbourhood explosion and thus higher computational cost.
To address this issue, many approaches limit the scope to subgraphs or
localised subgraphs while some other methods propose to run the GCN on
particular types of generated graphs. The taxonomy and related approaches are
given in Figure 12. Again, the block’s colour indicates the task the approach
is proposed for: grey represents a node classification, blue represents a link
prediction, and orange represents a network classification.

Figure 12. Taxonomy from the learning scope perspective.

####  4.3.1. Subgraphs

An intuitive idea is to limit the training scope to several selected subgraphs
instead of the original whole graph, so the neighbourhood is restricted within
the sphere of subgraphs no matter how many layers are stacked.

GraphSAINT. In order to enhance the scalability of the GCN, GraphSAINT
proposes to train a GCN model iteratively on several sampled subgraphs. Each
sampled subgraph $G_{s}\in\mathbb{G}$ is a mini-batch. The representation of
node $v$ in a sampled subgraph $G_{s}$ is formulated as:

(78) $h_{v}^{(l+1)}=\sum_{u\in
N_{v}|G_{s}}\frac{\tilde{A}_{v,u}}{\alpha_{u,v}}W^{(l)}h_{u}^{(l)},$

where $u$ is $v$’s neighbour in $G_{s}$, and $\alpha_{u,v}$ is a coefficient
to offset the biases from the sampler. Specifically, $\alpha_{u,v}$ is defined
as the probability of edge $(u,v)$ being sampled, divided by the probability
of node $v$ being sampled. Given a set of pre-sampled subgraphs $\mathbb{G}$,
$\alpha_{u,v}=\frac{C_{u,v}}{C_{v}}$, where $C_{u,v}$ and $C_{v}$ are the
number of times edge $(u,v)$ and node $v$ appear in $\mathbb{G}$,
respectively. Finally, the batch loss is calculated as: $L_{\text{batch
}}=\frac{1}{|\mathbb{G}|}\sum_{G_{s}\in\mathbb{G}}\sum_{v}\frac{L_{v}}{\lambda_{v}}$,
where $L_{v}$ is the loss on node $v$ in the GCN’s output layer, and
$\lambda_{v}$ is a loss normalisation term computed by the number of node $v$
appearing in $\mathbb{G}$ divided by the total number of nodes in the original
graph. Different samplers are integrated within the framework, such as random
node sampler, random edge sampler and random walk based sampler. According to
the experiment, the random walk based sampler tends to have the best
performance.

Cluster-GCN. Also to address the issue of neighbourhood explosion in large
graphs, a Cluster-GCN proposes to first partition the whole graph into several
clusters according to certain clustering algorithms, then run the GCN on those
clusters. Given $c$ clusters, the original adjacency matrix $A$ is
approximated as a list of submatrices $A_{11}$, $A_{11}$, …, $A_{cc}$ at
diagonal. The representation of nodes at layer $l$ in the $t$th cluster is
thus formulated as:

(79) $H_{t}^{(l)}=\hat{A}_{tt}H_{t}^{(l-1)}W^{(l-1)},$

where $\hat{A}_{tt}$ is the normalised version of $A_{tt}$. The loss is then
calculated as: $L_{t}=\frac{1}{\left|V_{t}\right|}\sum_{i\in
V_{t}}\operatorname{loss}\left(y_{i},h_{i}^{(L)}\right)$. At each iteration,
the model weights are updated based on the loss of the cluster. This way, no
matter how many convolutional layers are involved, the neighbourhood scope is
restricted to one cluster. In order to offset the bias of clustering
algorithms, a better version of the Cluster-GCN proposes to randomly form a
subgraph with several randomly chosen clusters, then at each iteration, run
GCN on one subgraph. Experiments on very large datasets show that the Cluster-
GCN is able to train a deeper GCN without time and space overhead and achieves
advanced performance.

LGCN. A learnable graph convolutional network (LGCN) proposes to transform
graph data into a grid-like data structure and apply the traditional
convolutional operation on it (Gao et al., 2018). As traditional CNN requires
a fixed number of ordered units in the receptive fields, the LGCN proposes to
sort features at each dimension and select the k-largest ones to form a grid
structure. The transformed data is then fed into a one-dimensional CNN to
generate the final representation of the focal node. Specifically, the nodes’
representation at layer $l$ is formulated as:

(80) $H^{(l+1)}=c(g(H^{(l)},A,k)),$

where $k$ is a hyper parameter, $g(\cdot)$ is the function that performs
k-largest selection to transfer the original graph data into grid data, and
$c(\cdot)$ is a one-dimensional CNN. Furthermore, as Cluster-GCN and
GraphSAINT, the LGCN also proposes to train the neural network on subgraphs.
Each subgraph is built from randomly selecting a few initial nodes and then
expanding adjacent nodes into it using a breadth-first-search algorithm. At
each training iteration, multiple subgraphs can be included in a mini-batch.
The subgraph training strategy is shown to be more time and space efficient,
with only negligible loss in performance.

####  4.3.2. Local subgraphs

Another popular idea to address the computational overhead is training the GCN
on local subgraphs. Note that local subgraphs are different from subgraphs in
that they are extracted around each node or link. In contrast, subgraphs, as
we have discussed earlier, have in general a wider range, without focusing on
a node or a link.

SEAL. SEAL is a GCN based framework specially designed for a link prediction
task (Zhang and Chen, 2018). Motivated by the fact that many successful link
prediction heuristics, such as the common neighbour, Adamic-Adar and resource
allocation, only involve the 1-hop or 2-hop neighbours around a node pair,
SEAL proposes to train a GCN on the local subgraphs extracted around each
target link. Specifically, the local subgraph is the induced graph from each
target node pair and their k-hop neighbours. After having constructed the
training data, it further introduces a node labelling procedure to give the
target node pair special weights as well as to distinguish the neighbouring
nodes in a given local subgraph. Specifically, it labels each node in the
target pair as 1, and assigns larger labels to other nodes according to their
distances to the target pair. The assigned labels are then concatenated with
other features to construct the feature matrix of the local subgraph. In the
final step, a GCN is trained on the local subgraphs and their label-enhanced
feature matrices. In the experimental implementation, SEAL chooses to use
DGCNN, a GCN model designed for graph classification (see Section 4.1.1), as
the default GCN model. Essentially, the link existence problem in the original
graph is modelled as a graph classification problem on the extracted local
subgraphs.

G-Meta. Motivated by the idea that local subgraphs may contain transferable
knowledge that can be adapted to unseen tasks, G-Meta proposes to leverage
local subgraph information in few-shot graph meta-learning (Huang and Zitnik,
2020). For the node classification task, local subgraphs are constructed as
induced graphs from each node and its k-hop neighbours; and when it comes to
link prediction, local subgraphs are built as in SEAL. Then a typical GCN is
used on these local subgraphs to generate graph embeddings. At last, a
prototypical loss and Model-Agnostic Meta-Learning (MAML) algorithm are used
to update the GCN’s parameters. Specifically, the prototype $t_{l}$ of label
$l$ is calculated through averaging over subgraph embeddings in the support
set: $t_{l}=\frac{1}{N_{l}}\sum_{y_{j}=l}\mathbf{h}_{j}$. Then for each local
subgraph $S_{u}$ in both support and query set, a class distribution vector
$\mathbf{p}$ is calculated as:
$\mathbf{p}_{l}=\frac{\exp\left(-\left\|\mathbf{h}_{S_{u}}-\mathbf{t}_{l}\right\|\right)}{\sum_{\hat{l}}\exp\left(-\left\|\mathbf{h}_{S_{u}}-\mathbf{t}_{\hat{l}}\right\|\right)}$.
Finally, the cross-entropy loss is formulated as:
$\mathrm{L}(\mathbf{p},\mathrm{y})=\sum_{j}\mathbf{y}_{j}\log\mathbf{p}_{j}$.
Experiments on synthetic and real networks show that local subgraphs are vital
for few-shot graph learning. It is worth mentioning that the best performance
is yielded when 2-hop neighbours are included.

Shadow-GNN. From the perspective of decoupling the scope (i.e., a receptive
field) and the depth (i.e., a number of layers) of the GCN, a Shadow-GNN also
proposes to adopt local subgraph as an input (Zeng et al., 2021). Typically on
a full graph, the scope of the GCN increases with the number of layers — an
L-layer GCN means an L-hop neighbourhood scope. As the GCN model is also
viewed as a form of Laplacian smoothing that mixes the feature of a node and
its neighbours, when the scope becomes too large, node features may be
oversmoothed (Li et al., 2018a). To address this problem, the Shadow-GNN
proposes to train the GCN on local subgraphs, so that the scope is bounded by
the range of the local subgraphs, regardless of the number of layers. In this
setting, the depth can be larger than the scope. It means that nodes in the
subgraphs may exchange information multiple times, which could lead to better
expressivity. Different subgraph extractors can be selected, such as an L-hop
neighbourhood extractor or a random-walk-based extractor. In actual
implementation, the scope is set as a 2- or 3-hop neighbourhood while the
depth is deeper (3 or 5 layers).

NGNN. A nested graph neural network (NGNN) proposes to apply the local
subgraph training strategy on a graph classification task (Zhang and Li,
2021). The extracted local subgraphs, termed rooted subgraphs, are also
induced subgraphs from each node and its k-hop neighbours. First, a base GCN
is applied on all rooted subgraphs. Taking root node $v$ for example, at layer
$l$, any node $u$ in its k-hop rooted subgraph $G_{v}^{k}$ is formulated as:

(81)
$h_{u,G_{v}^{k}}^{(l)}=UPDATE^{(l-1)}\left(h_{u,G_{v}^{k}}^{(l-1)},\sum_{w\in
N\left(u\mid
G_{v}^{k}\right)}MSG^{(l-1)}\left(h_{u,G_{v}^{k}}^{(l-1)},h_{w,G_{v}^{k}}^{(l-1)},e_{uw}\right)\right).$

Then, the final representation of root node $v$ at layer $L$ is set to be
equal to its rooted subgraph representation obtained from applying a subgraph
pooling on all nodes in the subgraph:
$h_{v}=h_{G_{v}^{k}}=POOL_{1}\left(\left\\{h_{u,G_{v}^{k}}^{(L)}\mid u\in
G_{v}^{k}\right\\}\right).$ With the same base GCN applied on all nodes’
rooted subgraphs, the representation of each node can be obtained, and the
graph representation can be generated from applying another GCN, termed outer
GCN, on those updated node representations. To make it simple, the outer GCN
can be just a graph pooling layer: $h_{G}=POOL_{2}({h_{v}\mid v\in G})$. The
work theoretically proves that a proper NGNN can discriminate almost all
$r$-regular graphs where the vanilla GCN cannot.

GNN-AK. GNN-As Kernel (GNN-AK) is another local subgraph based approach for a
graph classification problem (Zhao et al., 2021). Different from the NGNN
which directly uses the rooted subgraph embedding to represent each node, the
GNN-AK proposes to construct node representation from concatenating three
types of embedding, i.e., subgraph embedding, centroid embedding, and context
embedding. Centroid embedding is simply the root node representation in its
own subgraph, while context embedding is built from the representation of this
node in other nodes’ rooted subgraphs. It is argued that these two additional
embeddings contain information which is not captured in the subgraph
embedding. Formally, the representation of node $v$ at layer $l$ is:

(82)
$h_{v}^{(l)}=CONCAT(h_{v,\operatorname{centroid}}^{(l)},h_{v,\operatorname{subgraph}}^{(l)},h_{v,\operatorname{context}}^{(l)}),$

with $h_{v,\operatorname{centroid}}^{(l)}=h_{v\mid G_{v}^{k}}$,
$h_{v,\operatorname{subgraph}}^{(l)}=POOL_{1}(\\{h_{i\mid G_{v}^{k}}\mid
i\in\mathcal{N}_{k}(v)\\})$, and
$h_{v,\operatorname{context}}^{(l)}=POOL_{2}(\\{h_{v\mid G_{j}^{k}}\forall
j\text{ s.t. }v\in\mathcal{N}_{k}(j)\\})$. $h_{v\mid G_{u}^{k}}$ denotes the
representation of node $v$ in node $u$’s rooted subgraph. Then, the final
graph representation is obtained from another pooling at the output layer:
$h_{G}=POOL_{3}(\\{h_{v}^{L}\mid v\in V\\})$. It is worth mentioning that a
subgraph drop strategy is further introduced to improve the scalability of
GNN-AK so that the number of local subgraphs can be much smaller than the
number of nodes in the original graph.

####  4.3.3. Other types of graphs

Subgraphs or local subgraphs are still part of the original graphs. In the
third subcategory, we see approaches that use differently constructed graphs,
such as the coarsened graph and the feature graph.

DiffPool. Analogous to the idea of spatial pooling in a traditional CNN, a
DiffPool proposes to learn a graph representation in a hierarchical manner.
Nodes at layer $l$ will be collapsed into higher-level cluster nodes at layer
$l+1$ via a learned assignment matrix, and after stacking several hierarchical
layers, the singular node’s embedding at the final layer is viewed as the
representation for the whole graph. Concretely, node embedding matrices
$Z^{(l)}$ are learned from a GCN (called an embedding GNN), and an assignment
matrix $S^{(l)}$ is learned from another GCN, called a pooling GNN:

(83) $\displaystyle
Z^{(l)}=GNN_{\operatorname{embed}}^{(l)}(A^{(l)},X^{(l)}),$ $\displaystyle
S^{(l)}=\operatorname{softmax}(GNN_{\operatorname{pool}}^{(l)}(A^{(l)},X^{(l)})),$

where $A^{(l)}$ and $X^{(l)}$ are the coarsened adjacency matrix and the
cluster nodes feature matrix at layer $l$, respectively. The dimension of
assignment matrix $S^{(l)}$ is $n_{l}\times n_{l+1}$, so that each role is one
of the $n_{l}$ nodes at layer $l$ and each column is one of the cluster nodes
at layer $l+1$. Then, $A^{(l+1)}$ and $X^{(l+1)}$ which are used as the next
layer’s inputs are generated as:

(84) $\displaystyle X^{(l+1)}={S^{(l)}}^{T}Z^{(l)},$ $\displaystyle
A^{(l+1)}={S^{(l)}}^{T}A^{(l)}S^{(l)}.$

The assignment matrix $S^{(L-1)}$ at the penultimate layer is set to be a
vector of 1’s, so that all nodes will collapse into a single cluster node at
the final layer, and the corresponding node embedding is viewed as the
representation for the original graph. Note that the number of clusters is a
predefined hyperparameter, which is usually set as a percentage of the number
of nodes at the previous layer.

AM-GCN. An Adaptive Multi-channel Graph Conventional Network (AM-GCN) proposes
to not only run the GCN on the original (topological) graph, but also on a
feature graph constructed from a feature similarity matrix. Specifically, the
similarity matrix is computed using cosine similarity or heat kernel. Then,
edges will be added between each node and $k$ other nodes of top similarity
scores. The generated feature graph $G_{f}=(\mathbf{A}_{f},\mathbf{X})$ is
also called the k-nearest neighbour (kNN) graph. Therefore, the embeddings on
the feature graph are formulated as follows:

(85)
$\mathbf{H}_{f}^{(l)}=\operatorname{ReLU}\left(\hat{\mathbf{A}}_{f}\mathbf{H}_{f}^{(l-1)}\mathbf{W}_{f}^{(l)}\right),$

where $\hat{\mathbf{A}_{f}}$ is the normalised feature graph adjacency matrix.
Another GCN is used to generate node embeddings on the original graph
$G=(\mathbf{A},\mathbf{X})$:
$\mathbf{H}_{t}^{(l)}=\operatorname{ReLU}\left(\hat{\mathbf{A}}\mathbf{H}_{t}^{(l-1)}\mathbf{W}_{t}^{(l)}\right)$.
Further, in order to capture the correlation between a topological space and a
feature space, a common convolutional module is introduced as:
$\mathbf{H}_{ct}^{(l)}=\operatorname{ReLU}\left(\hat{\mathbf{A}}\mathbf{H}_{ct}^{(l-1)}\mathbf{W}_{c}^{(l)}\right)$;
$\mathbf{H}_{cf}^{(l)}=\operatorname{ReLU}\left(\hat{\mathbf{A}}_{f}\mathbf{H}_{cf}^{(l-1)}\mathbf{W}_{c}^{(l)}\right)$.
Note that the same weight matrix $\mathbf{W}_{c}^{(l)}$ is shared in
$\mathbf{H}_{ct}^{(l)}$ and $\mathbf{H}_{cf}^{(l)}$. Under this setting, node
features are propagated not only in a topological space but also in a feature
space. The final representation is then obtained through combining the above
four embeddings with an attention scheme:
$\mathbf{Z}=\alpha_{t}\cdot\mathbf{H}_{t}^{(L)}+\alpha_{f}\cdot\mathbf{H}_{f}^{(L)}+\alpha_{c}\cdot(\frac{\mathbf{H}_{ct}^{(L)}+\mathbf{H}_{cf}^{(L)}}{2})$,
where $\alpha_{t}$, $\alpha_{f}$ and $\alpha_{c}$ are attention vectors.

###  4.4. Discussion

####  4.4.1. Differences between layer-wise scope and overall learning scope

Here we emphasize the differences between layer-wise scope and overall
learning scope. Layer-wise message aggregation scope, or a receptive field, is
where a node receives the message from. It can be a 1-hop neighbourhood, k-hop
neighbourhood, random-walk neighbourhood, or subgraph neighbourhood according
to our taxonomy. Although the receptive field is usually small, distant nodes
can exchange messages after stacking multiple GCN layers, causing the well-
known neighbourhood explosion issue. Obviously, with a large enough number of
layers, a node can exchange information with any other node in the entire
graph. Overall learning scope, in contrast, is determined by the input graph,
which can be the entire original graph, extracted subgraphs or local
subgraphs, or coarsened graphs according to our taxonomy. Taking an extracted
local subgraph for example, no matter how large the receptive field is or how
many layers are stacked, a node can only exchange messages with other nodes in
the same subgraph. This naturally solves the neighbourhood explosion issue. A
large number of layers on a relatively small subgraph also means that nodes
may exchange information multiple times, which is argued to help the GCN
better absorb and embed information (Zeng et al., 2021).

####  4.4.2. Time and space complexity analysis

In the discussion about complexity, we focus on how the different definitions
of the neighbourhood in a convolutional layer influence the cost of
computation (corresponding to the layer-wise message scope taxonomy in Figure
10). The time and space complexities of each category are listed in Table 4.

Neighbourhood definition (representative approach) | Time complexity | Space complexity
---|---|---
1-hop neighbourhood (GCN) | $O\left(L\left(|V|^{2}C+|V|C^{2}\right)\right)$ | $O\left(\mathrm{L}|V|C+LC^{2}\right)$
1-hop neighbourhood (GraphSAGE) | $O(L|V|(sC+C^{2}))$ | $O\left(\mathrm{L}|V|C+LC^{2}\right)$
h-hop neighbourhood (MixHop) | $O\left(L\left(|V|^{2}Ch+|V|C^{2}\right)\right)$ | $O\left(\mathrm{L}|V|C+LC^{2}\right)$
h-hop neighbourhood (k-hop GNN) | $O(L|V|(k_{max}^{h}C+C^{2}))$ | $O\left(\mathrm{L}|V|C+LC^{2}\right)$
Random-walk neighbourhood (PinSage) | $O(L|V|(wl+vlogv+sC+C^{2}))$ | $O\left(\mathrm{L}|V|C+LC^{2}\right)$
k-node subgraph neighbourhood (k-GNN) | $O(L\binom{|V|}{k}(k|V|C+C^{2}))$ | $O(L\binom{|V|}{k}C+C^{2})$
Table 4. Time and space complexity from the perspective of a layer-wise
message scope. $|V|$ is the number of nodes in the graph, $C$ are node feature
channels (assuming the number of features is fixed for all layers), $L$ is the
number of convolutional layers, $s$ is the number of sampled nodes, $h$ is the
number of hops away from a focal node, $k_{max}$ is maximum node degree, $w$
is the number of random walks, $l$ is the length of a random walk, $v$ is the
number of visited nodes, and $k$ is the number of nodes in a subgraph.

First, according to the propagation rule of the vanilla GCN (Equation 49),
which is essentially the multiplication of three matrices
$A\in\mathbb{R}^{|V|\times|V|}$, $H\in\mathbb{R}^{|V|\times C}$, and
$W\in\mathbb{R}^{C\times C}$, the time complexity at each layer is
$O\left(|V|^{2}C+|V|C^{2}\right)$, and thus the overall complexity is
$O\left(L\left(|V|^{2}C+|V|C^{2}\right)\right)$. Certainly, when $|V|>>C$, and
when the sparsity of adjacency matrix is exploited (for instance through the
compressed sparse row format), its time complexity is sometimes expressed as
$O(L|E|C)$ (Chiang et al., 2019; Vignac et al., 2020). As the GCN’s space
complexity is concerned, we need to store the embeddings of all nodes plus the
weight matrix at each layer, which is $O(L|V|C+LC^{2})$, or $O(L|V|C)$ when
$|V|>>C$. GraphSAGE illustrates the same propagation procedure from a
microscopic view, with a fixed number, denoted $s$, of sampled neighbours
involved in the convolutional operation (Equation 51). The overall time
complexity of GraphSAGE is, therefore: $O(L|V|(sC+C^{2}))$. Notice that when
$s$ equals $|V|$, the time complexity of GraphSAGE is the same as the vanilla
GCN.

Then, when each node aggregates messages from its higher-order neighbours,
denoted h-hop neighbours here, the propagation rule can be put as:
$H^{(l)}=\sigma\left(\hat{A}^{h}H^{(l-1)}W^{(l)}\right)$. A typical
representative is MixHop (Abu-El-Haija et al., 2019) (refer to Section 4.1.2).
Thus, the time complexity at each layer is: $O(|V|^{2}Ch+|V|C^{2})$ or
$O(|V|^{2}Ch)$ when $|V|h>>C$, and the space complexity stays unchanged. From
a microscopic view, represented by the approach k-hop GNN (Nikolentzos et al.,
2020), the time complexity of involving h-hop neighbours in convolutional
operation would be $O(L|V|(k_{max}^{h}C+C^{2}))$, or $O(L|V|k_{max}^{h}C)$
when $k_{max}^{h}>>C$. Clearly, the time complexities of both macroscopic and
microscopic algorithms grow with $h$, and when $h$ equals one, they degrade to
the versions of 1-hop neighbourhood algorithms, i.e., the vanilla GCN and
GraphSAGE.

Thirdly, approaches with neighbourhood defined on random walks typically
include the following steps (represented by PinSage (Ying et al., 2018)):
performing $w$ times random walks of length $l$, ranking the visited $v$ nodes
based on the visited times, aggregating messages from the top $s$ nodes, and
finally applying weight matrix on node representations. Therefore, the overall
time complexity is termed as: $O(L|V|(wl+vlogv+sC+C^{2}))$. Normally, there is
no need to record all the random walks, so the space complexity is still
$O(L|V|C+LC^{2})$. Comparing the time complexity of PinSage with that of
GraphSAGE, we see that with the extra step of performing random walks and
ranking visited nodes, i.e., the term $wl$ and the term $vlogv$, PinSage is
more expensive in computation.

In the fourth subcategory, we take k-GNN (Morris et al., 2019) as an example
to analyse the complexity of having k-node subgraphs as neighbours. The
approach aims to learn embeddings for k-node tuples, and the neighbours of
each k-tuple are defined as other k-tuples containing one node that is not in
the focal k-tuple(refer to Section 4.1.4). Each k-tuple aggregates messages
from all its k-tuple neighbours, with a time complexity of $O(k|V|C)$.
Therefore, on all $\binom{|V|}{k}$ k-tuples and $L$ layers, the overall time
complexity is: $O(L\binom{|V|}{k}(k|V|C+C^{2}))$. To store the embeddings of
$\binom{|V|}{k}$ node tuples and the weight matrices at all layers, it
requires $O(L\binom{|V|}{k}C+C^{2}))$ space. This approach is essentially
different from the previous ones, in that it is to generate embeddings for
k-tuples instead of for each node, resulting in the term $\binom{|V|}{k}$
appearing in both its time and space complexities. Clearly, its complexity
grows combinatorially with $k$, and easily surpasses the complexities of all
other algorithms when $k$ is relatively large. In practice, however, the value
of $k$ generally does not exceed $3$.

Message (representative approach) | Time complexity | Space complexity
---|---|---
Node feature X (GCN) | $O\left(L\left(|V|^{2}C+|V|C^{2}\right)\right)$ | $O\left(\mathrm{L}|V|C+LC^{2}\right)$
Count of graphlets + X (GSN) | $O(|V|k_{max}^{|S|-1}+L(|V|^{2}(C+o)+|V|(C+o)^{2})$ | $O\left(\mathrm{L}|V|(C+o)+L(C+o)^{2}\right)$
Distance information + X (P-GNN) | $O(|V|^{3}+L|V|(Tn+C^{2}))$ | $O\left(\mathrm{L}|V|C+LC^{2}\right)$
Random feature + X (rGIN) | $O(L(|V|^{2}(C+r)+|V|(C+r)^{2})$ | $O\left(\mathrm{L}|V|(C+r)+L(C+r)^{2}\right)$
Table 5. Time and space complexity from the perspective of a message content.
$|V|$ is the number of nodes in the graph, $C$ is node feature channels
(assuming the number of features is fixed for all layers), $L$ is the number
of convolutional layers, $|S|$ is the maximum size of a set of graphlets, $o$
is the number of orbits in graphlets, $k_{max}$ is maximum node degree, $T$ is
the number of anchor sets, $n$ is the maximum number of nodes in an anchor
set, and $r$ is the length of the random feature vector.

In addition, Table 5 lists the time and space complexities of approaches that
include extra node features in the GNNs (corresponding to the message content
taxonomy in Figure 11). First, when the count of graphlets, or more
specifically, the count of node orbits is added to the node features
(represented by the approach GSN (Bouritsas et al., 2020)), it requires a
preprocessing step to count the number of each node orbit, then performing the
general convolutional operation. The cost of counting orbits depends on the
size of graphlet $|S|$ and the maximum degree of nodes $k_{max}$. Another
difference from the vanilla GCN is that the node feature dimension will
increase by the number of orbits, denoted $o$. Therefore, its time complexity
is $O(|V|k_{max}^{|S|-1}+L(|V|^{2}(C+o)+|V|(C+o)^{2})$, and its space
complexity is $O\left(\mathrm{L}|V|(C+o)+L(C+o)^{2}\right)$. Second, when
distance information is included, as in the approach P-GNN (You et al., 2019),
it requires first calculating the shortest path distances between all nodes
($O(|V|^{3})$ in the typical Floyd-Warshall algorithm), then aggregating
message from a number of anchor sets ($T$ anchor sets and each containing at
most $n$ nodes). Therefore the time complexity would be
$O(|V|^{3}+L|V|(Tn+C^{2}))$. Another less expensive version is to calculate a
limited-hop, e.g., h-hop, shortest path distance in the preprocessing step,
whose time complexity is $O(|V|k_{max}^{h})$. Third and lastly, when random
features are included, represented by the approach rGIN (Sato et al., 2021),
the impact on time complexity is mainly due to the increase in feature
dimension. This is because the cost of generating random features is generally
negligible.

We finally discuss the complexity of approaches that have different learning
scopes (corresponding to the taxonomy in Figure 10). For GCNs running on
subgraphs, represented by the GraphSAINT (Zeng et al., 2019), the cost
includes two steps, i.e., the subgraph sampling and the training. Given the
cost of sampling $T_{s}$ and a set sampled subgraphs $\mathbb{G}$ (maximum
number of nodes in sampled subgraphs denoted $|V_{s}|$), its complexity is:
$O(T_{s}+|\mathbb{G}|L(|V_{s}|^{2}C+|V_{s}|C^{2}))$. The cost $T_{s}$,
depending on the choice of the sampler, is normally less expensive than the
training. The key term is, therefore, $|\mathbb{G}|L|V_{s}|^{2}C$. When
$|V_{s}|<<|V|$, subgraph-based approaches significantly reduce the training
cost of the GCNs. Similarly, for GCNs running on local subgraphs, exemplified
by the Shadow-GNN (Zeng et al., 2021), the two steps are extracting local
subgraphs (extraction cost is denoted as $T_{e}$, the maximum number of nodes
in extracted local subgraphs is denoted as $|V_{l}|$), and training the GCN on
them. Therefore, the time complexity is
$O(T_{e}+|V|L(|V_{l}|^{2}C+|V_{l}|C^{2}))$. Note that local subgraphs are
usually extracted at each node, so the number of extracted subgraphs equals
the number of nodes $|V|$. Given that $|V_{l}|<<|V|$ (we should also have
$|V_{l}|<<|V_{s}|$), local subgraph based GCNs are generally much faster in
training than full graph or subgraph based GCNs.

##  5\. Discussion and Outlook

After reviewing the traditional structural measures and the graph
convolutional networks, we are set to answer the following research question:
How are these two classes of methods related, especially how traditional
structural measures of Network Science can inform GCN methods? In this
section, we first briefly discuss the performance of GCNs in major learning
tasks, then move on to drawing connections between GCNs and traditional
structure based approaches, and finally introduce three future directions.

###  5.1. GCN’s performance in learning tasks

Convolutional Neural Networks have been shown to be state-of-the-art in
various tasks in the area of image processing, including image classification,
object detection, and semantic segmentation (Li et al., 2021; Gu et al.,
2018b). GCNs have also achieved promising performances in various graph-
related tasks. As an extension of CNNs in graph data, GCNs, since their
appearance, have received a lot of attention and are viewed as state-of-the-
art by default. However, there are works showing that simple heuristics from
traditional network science achieve a comparative performance of GCNs (Zhang
and Chen, 2018; Yun et al., 2021), or even beat them in link prediction and
network reconstruction tasks (Mara et al., 2022). A recent paper shows that
simply feeding heuristics derived from nodes similarity scores in a logistic
regression model can achieve the best performance in link prediction among
many deep learning approaches, including GCNs (Mara et al., 2022). In
addition, Katz index is the top performer in the network reconstruction task,
followed by VGAE which uses GCN as the graph encoder (Kipf and Welling,
2016b).

Although the majority of GCN approaches focus on node classification and graph
classification tasks, they rarely include structural heuristic-based methods
as baselines in the experiment. This overlook could hinder a comprehensive
evaluation of the performance of graph convolutional networks. Additionally,
comparing GCN approaches with traditional heuristic-based methods could help
to better understand the strengths and limitations of GCNs. We believe a
closer integration of graph deep learning approaches and traditional network
science approaches would immensely benefit both communities, and revealing the
connections between the two classes of methods lays the foundation of this
integration.

###  5.2. Connections between traditional network science approaches and GCNs

Based on the current literature, the connections between GCNs and traditional
structure based approaches are observed via the following four aspects. The
first aspect covers the foundations of GCNs in traditional Network Science;
the second aspect focuses on their similarities in dealing with directed
networks; the third and final aspect cover two typical applications of
traditional structural information in GCNs: (i) number of graphlets and (ii)
distance information.

####  5.2.1. Message passing based approaches and GCN

As we have seen in message passing based approaches (Section 3.4), a node’s
influential score or centrality is calculated through iteratively aggregating
the scores of its neighbours until it converges. Taking the eigenvector
centrality, for example, the centrality of node $i$, denoted $x(i)$, is
formulated as:

$x(i)=c\sum_{j\in N(i)}x(j).$

$x$, a vector of all nodes’ centralities, is found to converge to the dominant
eigenvector of the adjacency matrix $A$, and $c$ converges to the reciprocal
of the dominant eigenvalue of $A$.

Interestingly, graph convolutional networks adopt the same idea of
neighbourhood aggregation, and the iteration process is implemented through
the usage of multiple layers. Taking the vanilla GCN for example, we have the
following convolutional operation:

$h_{v}^{(l)}=\sigma\left(\sum_{u\in\mathcal{N}(v)}\frac{1}{c_{vu}}h_{u}^{(l-1)}W^{(l)}\right).$

Comparing the above two expressions, one major difference is obviously the
appearance of weight matrices: in eigenvector centrality, the influential
score is directly calculated from forward propagation (e.g., a power
iteration), while in the GCN, weight matrices are updated in the backward
propagation with the help of labelled samples. Another subtle yet significant
difference is that GCNs allow rich node features (n-dimensional vector for
each node), while traditional message passing approaches, such as the
eigenvector centrality, alpha centrality or PageRank, only support using a
numeric value that represents the node’s importance or influence. These two
points are also the main reasons why GCNs have quickly gained popularity — the
learnable setting makes GCNs suitable for various types of tasks, and the
support of rich node features makes them appropriate for different types of
real-world data. Despite the advancements and popularity of graph
convolutional networks, traditional network science approaches remain
important in the field. They have a strong theoretical foundation, which can
provide insights into the underlying mechanisms of networked systems.
Furthermore, traditional approaches are often more computationally efficient
than deep learning approaches, making them more practical for certain types of
tasks or data. Overall, the continued use and development of traditional
network science approaches alongside newer methods, such as GCNs, can help to
deepen our understanding of complex networked systems and advance the field as
a whole.

####  5.2.2. Dealing with link direction

When directions of links are considered, we observe interesting connections
between the traditional message passing approach HITS (Kleinberg et al., 1998)
and the recent graph convolutional approach DGP (Kampffmeyer et al., 2019).
HITS proposes to distinguish two roles in webpages, i.e., authorities and
hubs. Authorities, being reliable information sources, are pointed by hubs
(based on incoming edges to the node), while hubs, acting as a home page or
library, point to authorities (based on outgoing edges from the node). An
authority score and a hub score are defined in a mutually dependent way:

$\displaystyle a(i)=\sum_{j\in N_{i}^{in}}h(j),$ $\displaystyle
h(i)=\sum_{j\in N_{i}^{out}}a(j).$

Interestingly, DGP, as a graph convolutional approach, proposes to distinguish
link direction through a two-phase propagation scheme, i.e., one phase
capturing outgoing connections and the other capturing incoming connections
(find more in Section 4.1.2):

$H=\sigma\left(\sum_{k=0}^{K}\alpha_{k}^{a}\hat{A}_{k}^{a}\sigma\left(\sum_{k=0}^{K}\alpha_{k}^{d}\hat{A}_{k}^{d}XW_{d}\right)W_{a}\right).$

Clearly, the major difference here is that in DGP one type of connection is
stacked on top of another, and therefore only one representation is learnt,
instead of two scores as in HITS. Besides, k-hop outgoing/incoming connections
are included at once in one convolutional layer. Another GCN approach that
applies exactly the same idea of distinguishing outgoing edges and incoming
edges is Asymmetric GNN, or AGNN (Tan et al., 2021). It proposes a one-way
message passing that only operates on the outgoing or incoming edges of a
graph. Two embeddings are then generated for each node to model their roles of
sending and receiving information. It is also possible to design a one-way GCN
at particular layers, while still considering both types of edges in other
layers, which could allow the model to focus on different aspects of the graph
structure at different stages of processing.

####  5.2.3. Number of graphlets

The number of graphlets, or more specifically, node orbits or edge orbits are
important topological features around individual nodes or edges (find more in
Section 2.2). In a traditional non-learning setting, a vector composed of the
counts of a chosen set of node orbits is used to distinguish the roles of
nodes (Milenković and Pržulj, 2008; Jia et al., 2022). Weights of the orbits,
when introduced, are calculated from hand-coded function. In graph
convolutional networks, the count of graphlets is added as additional features
in the message passing scheme, as we have seen in GSN (Bouritsas et al.,
2020), $\mathcal{F}$-MPNN (Barceló et al., 2021), and ID-GNN (You et al.,
2021). Taken GSN for example, node orbits $x_{V}(u)$, $x_{V}(v)$ or edge
orbits $x_{E}(u,v)$ are introduced as follow:

$\mathrm{h}^{l+1}(v)=\mathrm{MLP_{1}}\left(h^{l}(v),\sum_{u\in\mathcal{N}(v)}MLP_{2}\left(\mathbf{h}^{t}(v),\mathbf{h}^{t}(u),\mathrm{x}_{V}(v),\mathrm{x}_{V}(u),\mathrm{e}(u,v)\right)\right),$
$\mathrm{h}^{l+1}(v)=\mathrm{MLP_{1}}\left(h^{l}(v),\sum_{u\in\mathcal{N}(v)}MLP_{2}\left(\mathbf{h}^{t}(v),\mathbf{h}^{t}(u),\mathrm{x}_{E}(u,v),\mathrm{e}(u,v)\right)\right).$

Obviously, in a learning setting, the weights on all types of features,
including the count of graphlets, are learned in the training stage. Another
interesting difference between non-learning approaches and GCN approaches is
that the former chooses to include all node or edge orbits within a given
size, while the latter tends to focus on specific substructures like cycles or
cliques. One open problem in using graphlets or orbits in GCNs is determining
which ones to choose. Existing approaches have focused on using cliques and/or
cycles within a specific range (Bouritsas et al., 2020; Barceló et al., 2021;
You et al., 2021), without providing much rationale for this choice. While
these types of graphlets and orbits are crucial in some contexts, it is likely
that other types could also be exploited to improve the performance of GCN
models. There is still much to be explored in terms of the utility of
different graphlets and orbits in GCN models, and further research in this
area could lead to advances in the field.

####  5.2.4. Distance information

The path related information is largely used in traditional structural
measures, such as in closeness centrality, betweenness centrality,
$\kappa$-path centrality, etc. Taking the closeness centrality, for example,
it is defined as the reciprocal of the average shortest path from the focal
node $i$ to all other nodes:

$\Theta_{C}(i)=\frac{|V|-1}{\sum_{j\in V,j\neq i}d(i,j)}.$

The value of a node’s closeness centrality is directly used to describe the
node’s capacity of spreading information on the graph. Unsurprisingly, the
distance information is also made of use in graph convolutional networks, as
we have seen in P-GNN (You et al., 2019) and DE-GNN (Li et al., 2020). In
P-GNN, for example, the distance between a node and several anchor sets is
included in the convolutional operation:

$\displaystyle\mathbf{h}_{v}^{l}=\operatorname{AGG}^{(l)}\left(\mathcal{M}_{i}^{l-1},\forall
i\in[1,k]\right),$
$\displaystyle\mathcal{M}_{i}^{l-1}=\\{F(d_{uv},h_{u}^{l-1},h_{v}^{l-1}),\forall
u\in S_{i}\\}.$

In DE-GNN, the distance information between node $v$ and a target node set $S$
is used as an extra initial node feature:
$h_{v}^{(0)}=CONCAT(x_{v},\zeta(v\mid S))$. Recall that this idea of including
extra structural features as additional initial node features is also found in
$\mathcal{F}$-MPNN (Barceló et al., 2021), ID-GNN (You et al., 2021), and rGIN
(Sato et al., 2021).

###  5.3. Future directions

Although recent years have witnessed the great success of graph convolutional
networks in various domains, there are still many open problems to be solved
and a lot of room for further exploration (Bronstein et al., 2017; Zhou et
al., 2020; Zhang et al., 2020). Except for the frequently mentioned
directions, such as proposing GCNs for more complicated types of networks or
to further increase the expressivity or scalability of GCNs, we would like to
point out three potential directions which combine the traditional graph
analysis approaches and GCN approaches.

Exploring the applicability of more structural measures in GCNs. We have seen
appearances of various structural measures in GCNs, from the simplest node
degree (Hamilton et al., 2017a) to the much more complicated distance
information (You et al., 2019) and graphlet orbits (Bouritsas et al., 2020).
However, there are many other traditional structural measures that have yet to
be fully explored in the context of GCNs. For example, subgraph formation
based measures, such as the clustering coefficient (Watts and Strogatz, 1998)
and the closure coefficient (Yin et al., 2019; Jia et al., 2020), could be
incorporated as node-level features or used to weight the edges of the graph
(Veličković et al., 2017). Global path based measures, such as the closeness
or betweenness centrality measures, can be used to guide the sampling of
nodes, edges or subgraphs when constructing the training set for a GCN (Zhou
et al., 2020). For example, we could use closeness centrality to select the
nodes that are most influential in the graph and build subgraphs based on
these nodes as the input to the GCN. It would be interesting to see how these
and other structural measures could be utilised in GCNs to improve performance
on certain tasks or in particular types of networks.

Improving the explainability of GCNs / Guiding the choice of GCNs via
traditional structural measures. When it comes to the explainability of GCN
models, existing methods, represented by perturbation-based methods, mostly
focus on generating explanations for a trained GCN (Ying et al., 2019; Yuan et
al., 2022). There are, however, still many questions to be answered, such as
how different GCNs perform differently on different types of networks, and
what are the reasons for these differences. An analysis from a structural
information perspective can provide more insights into how different GCN
models extract and utilise graph structural information, and how the
information may differ across different GCN models and graph types. This can
help to better understand the strengths and limitations of different GCN
models and how to effectively apply them in different scenarios. Moreover, in
view of the large collection of GCN models and their composition modules, it
is difficult to decide which one to choose and how to set it up for the
targeted dataset and task (Hu et al., 2020). Traditional structural measures
could be used as indices for selecting the appropriate GCN model and the
related modules. For example, for graphs that are rich in triangles, a
particular GCN would be a better choice, while for graphs where quadrangles
are overrepresented, another GCN model should be selected.

Integrating edge features in GCNs. While the vanilla GCN primarily focuses on
aggregating and passing information from neighbouring nodes, it is important
to consider the role of edge attributes in many real-world networks. For
example, in consumer review networks, the ratings of products are often
labelled on the edges, and in social networks, the type and frequency of
interactions are labelled on the edges. Integrating edge features into GCNs
could not only enhance the applicability of the model but also increase the
accuracy and relevance of its predictions. There are works that naively
include edge features in GCN or propose a tailor-made model to encompass them
(Bouritsas et al., 2020; Gong and Cheng, 2019). However, there is still much
to be learned about the utility of traditional edge-level structural measures
in GCN models, such as the edge orbits (Hočevar and Demšar, 2016), the edge
clustering coefficient (Wang et al., 2011), the local path index (Lü et al.,
2009), etc. Further research in this area is likely to yield valuable insights
and improvements to the performance of GCN models.

##  6\. Conclusion

The complexity of graph data mainly comes from its intricate topological
structures. Mining and exploiting graph structural information have always
been one of the focal points in the study of graphs. A large amount of work in
traditional network science proposes various types of structural measures,
especially local structural measures, to characterise and study complex
networks. When more nodes or edges are involved, such approaches, however,
become infeasibly complicated. Graph convolutional networks, on the other
hand, are proposed to automatically extract relevant features from nodes’
neighbourhoods, and in this manner, avoid choosing and manually calculating
structural metrics.

In order to reveal the connections between the two classes of methods,
especially how traditional structural measures can inform GCNs, in this paper,
we first reviewed the traditional structure-based approaches in Network
Science and proposed a new taxonomy encompassing many seemingly unrelated
concepts from a structural perspective. With this prerequisite knowledge, we
then extend the scope to the prominent and powerful graph convolutional
networks, and provide a Network Science perspective on them — review and
classify GCNs from three structural angles, which are the layer-wise message
aggregation scope, the message content, and the overall learning scope.
Furthermore, we extensively discuss the connections between the traditional
structural approaches and the graph convolutional networks and suggest three
future research directions in the joint research area. We believe that the
well-established foundations of traditional structure-based approaches in
Network Science not only form the basis for GCNs but also could, and probably
should, serve as a driving force for their future advances.

###### Acknowledgements.

The authors thank Yu-Xuan Qiu, Joakim Skarding and Xiaohan Zhang for their
helpful comments and discussions. This work was supported by the Australian
Research Council, Grant No. DP190101087: Dynamics and Control of Complex
Social Networks.

## References

  * (1)
  * Abadal et al. (2021) Sergi Abadal, Akshay Jain, Robert Guirado, Jorge López-Alonso, and Eduard Alarcón. 2021\.  Computing graph neural networks: A survey from algorithms to accelerators.  _ACM Computing Surveys (CSUR)_ 54, 9 (2021), 1–38.
  * Abdo and de Moura (2006) Alexandre H Abdo and APS de Moura. 2006.  Clustering as a measure of the local topology of networks.  _arXiv preprint physics/0605235_ (2006).
  * Abu-El-Haija et al. (2019) Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. 2019.  Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In _international conference on machine learning_. PMLR, 21–29.
  * Ahajjam and Badir (2018) Sara Ahajjam and Hassan Badir. 2018.  Identification of influential spreaders in complex networks using HybridRank algorithm.  _Scientific reports_ 8, 1 (2018), 1–10.
  * Ahmad et al. (2020) Iftikhar Ahmad, Muhammad Usman Akhtar, Salma Noor, and Ambreen Shahnaz. 2020.  Missing link prediction using common neighbor and centrality based parameterized algorithm.  _Scientific reports_ 10, 1 (2020), 1–9.
  * Ahnert and Fink (2008) Sebastian E Ahnert and Thomas MA Fink. 2008.  Clustering signatures classify directed networks.  _Physical Review E_ (2008).
  * Alahakoon et al. (2011) Tharaka Alahakoon, Rahul Tripathi, Nicolas Kourtellis, Ramanuja Simha, and Adriana Iamnitchi. 2011\.  K-path centrality: A new centrality measure in social networks. In _Proceedings of the 4th workshop on social network systems_. 1–6.
  * Albawi et al. (2017) Saad Albawi, Tareq Abed Mohammed, and Saad Al-Zawi. 2017\.  Understanding of a convolutional neural network. In _2017 international conference on engineering and technology (ICET)_. Ieee, 1–6.
  * Aleja et al. (2019) David Aleja, Regino Criado, Alejandro J García del Amo, Ángel Pérez, and Miguel Romance. 2019.  Non-backtracking PageRank: from the classic model to Hashimoto matrices.  _Chaos, Solitons & Fractals_ 126 (2019), 283–291.
  * Aleskerov et al. (2016) Fuad T Aleskerov, Natalia Meshcheryakova, and Sergey Shvydun. 2016\.  Centrality measures in networks based on nodes attributes, long-range interactions and group influence.  _Long-Range Interactions and Group Influence_ (2016).
  * Aparicio et al. (2016) David Aparicio, Pedro Ribeiro, and Fernando Silva. 2016\.  Extending the applicability of graphlets to directed networks.  _IEEE/ACM transactions on computational biology and bioinformatics_ 14, 6 (2016), 1302–1315.
  * Bae and Kim (2014) Joonhyun Bae and Sangwook Kim. 2014.  Identifying and ranking influential spreaders in complex networks by neighborhood coreness.  _Physica A: Statistical Mechanics and its Applications_ 395 (2014), 549–559.
  * Barabási et al. (2016) Albert-László Barabási et al. 2016\.  _Network science_.  Cambridge university press.
  * Barceló et al. (2021) Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. 2021.  Graph Neural Networks with Local Graph Parameters.  _arXiv preprint arXiv:2106.06707_ (2021).
  * Barrat et al. (2004) Alain Barrat, Marc Barthelemy, Romualdo Pastor-Satorras, and Alessandro Vespignani. 2004.  The architecture of complex weighted networks.  _PNAS_ (2004).
  * Basaras et al. (2017) Pavlos Basaras, George Iosifidis, Dimitrios Katsaros, and Leandros Tassiulas. 2017.  Identifying influential spreaders in complex multilayer networks: A centrality perspective.  _IEEE Transactions on Network Science and Engineering_ 6, 1 (2017), 31–45.
  * Battiston et al. (2017) Federico Battiston, Vincenzo Nicosia, Mario Chavez, and Vito Latora. 2017.  Multilayer motif analysis of brain networks.  _Chaos: An Interdisciplinary Journal of Nonlinear Science_ 27, 4 (2017), 047404.
  * Bell et al. (1997) Michael GH Bell, Yasunori Iida, et al. 1997\.  Transportation network analysis.  (1997).
  * Bhagat et al. (2011) Smriti Bhagat, Graham Cormode, and S Muthukrishnan. 2011\.  Node classification in social networks.  In _Social network data analytics_. Springer.
  * Bianconi (2018) Ginestra Bianconi. 2018\.  _Multilayer networks: structure and function_.  Oxford university press.
  * Blondel et al. (2008) Vincent D Blondel, Jean-Loup Guillaume, Renaud Lambiotte, and Etienne Lefebvre. 2008.  Fast unfolding of communities in large networks.  _Journal of statistical mechanics: theory and experiment_ 2008, 10 (2008), P10008.
  * Boccaletti et al. (2014) Stefano Boccaletti, Ginestra Bianconi, Regino Criado, Charo I Del Genio, Jesús Gómez-Gardenes, Miguel Romance, Irene Sendina-Nadal, Zhen Wang, and Massimiliano Zanin. 2014.  The structure and dynamics of multilayer networks.  _Physics reports_ 544, 1 (2014), 1–122.
  * Bonacich (1972) Phillip Bonacich. 1972\.  Factoring and weighting approaches to status scores and clique identification.  _Journal of mathematical sociology_ 2, 1 (1972), 113–120.
  * Bonacich (1987) Phillip Bonacich. 1987\.  Power and centrality: A family of measures.  _American journal of sociology_ 92, 5 (1987), 1170–1182.
  * Bonacich and Lloyd (2001) Phillip Bonacich and Paulette Lloyd. 2001.  Eigenvector-like measures of centrality for asymmetric relations.  _Social networks_ 23, 3 (2001), 191–201.
  * Borgatti and Everett (2006) Stephen P Borgatti and Martin G Everett. 2006.  A graph-theoretic perspective on centrality.  _Social networks_ 28, 4 (2006), 466–484.
  * Bouritsas et al. (2020) Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. 2020\.  Improving graph neural network expressivity via subgraph isomorphism counting.  _arXiv preprint arXiv:2006.09252_ (2020).
  * Brandes (2008) Ulrik Brandes. 2008\.  On variants of shortest-path betweenness centrality and their generic computation.  _Social networks_ 30, 2 (2008), 136–145.
  * Bright et al. (2015) David A Bright, Catherine Greenhill, Michael Reynolds, Alison Ritter, and Carlo Morselli. 2015\.  The use of actor-level attributes and centrality measures to identify key actors: A case study of an Australian drug trafficking network.  _Journal of contemporary criminal justice_ 31, 3 (2015), 262–278.
  * Brin and Page (1998) Sergey Brin and Lawrence Page. 1998.  The anatomy of a large-scale hypertextual web search engine.  _Computer networks and ISDN systems_ 30, 1-7 (1998), 107–117.
  * Bródka et al. (2011) Piotr Bródka, Krzysztof Skibicki, Przemysław Kazienko, and Katarzyna Musiał. 2011\.  A degree centrality in multi-layered social network. In _2011 International Conference on Computational Aspects of Social Networks (CASoN)_. IEEE, 237–242.
  * Bronstein et al. (2017) Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. 2017.  Geometric deep learning: going beyond euclidean data.  _IEEE Signal Processing Magazine_ 34, 4 (2017), 18–42.
  * Brust et al. (2012) Matthias R Brust, Damla Turgut, Carlos HC Ribeiro, and Marcus Kaiser. 2012.  Is the clustering coefficient a measure for fault tolerance in wireless sensor networks?. In _2012 IEEE International Conference on Communications (ICC)_. IEEE, 183–187.
  * Caldarelli et al. (2004) Guido Caldarelli, Romualdo Pastor-Satorras, and Alessandro Vespignani. 2004\.  Structure of cycles and local ordering in complex networks.  _The European Physical Journal B_ 38, 2 (2004), 183–186.
  * Candeloro et al. (2016) Luca Candeloro, Lara Savini, and Annamaria Conte. 2016\.  A new weighted degree centrality measure: The application in an animal disease epidemic.  _PloS one_ 11, 11 (2016), e0165781.
  * Cao et al. (2015) Shaosheng Cao, Wei Lu, and Qiongkai Xu. 2015.  Grarep: Learning graph representations with global structural information. In _Proceedings of the 24th ACM international on conference on information and knowledge management_. 891–900.
  * Carmi et al. (2007) Shai Carmi, Shlomo Havlin, Scott Kirkpatrick, Yuval Shavitt, and Eran Shir. 2007\.  A model of Internet topology using k-shell decomposition.  _Proceedings of the National Academy of Sciences_ 104, 27 (2007), 11150–11154.
  * Chakrabarti et al. (1998) Soumen Chakrabarti, Byron Dom, Prabhakar Raghavan, Sridhar Rajagopalan, David Gibson, and Jon Kleinberg. 1998.  Automatic resource compilation by analyzing hyperlink structure and associated text.  _Computer networks and ISDN systems_ 30, 1-7 (1998), 65–74.
  * Chami et al. (2020) Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. 2020\.  Machine learning on graphs: A model and comprehensive taxonomy.  _arXiv preprint arXiv:2005.03675_ (2020), 1.
  * Chen et al. (2012) Duanbing Chen, Linyuan Lü, Ming-Sheng Shang, Yi-Cheng Zhang, and Tao Zhou. 2012.  Identifying influential nodes in complex networks.  _Physica a: Statistical mechanics and its applications_ 391, 4 (2012), 1777–1787.
  * Chen et al. (2013) Duan-Bing Chen, Hui Gao, Linyuan Lü, and Tao Zhou. 2013\.  Identifying influential nodes in large-scale directed networks: the role of clustering.  _PloS one_ 8, 10 (2013), e77455.
  * Chen and Chen (2021) Jun Chen and Haopeng Chen. 2021.  Edge-featured graph attention network.  _arXiv preprint arXiv:2101.07671_ (2021).
  * Chen et al. (2018) Jie Chen, Tengfei Ma, and Cao Xiao. 2018.  Fastgcn: fast learning with graph convolutional networks via importance sampling.  _arXiv preprint arXiv:1801.10247_ (2018).
  * Chiang et al. (2019) Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. 2019\.  Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks. In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 257–266.
  * Cohen (2008) Jonathan Cohen. 2008\.  Trusses: Cohesive subgraphs for social network analysis.  _National security agency technical report_ 16, 3.1 (2008).
  * Costantini and Perugini (2014) Giulio Costantini and Marco Perugini. 2014.  Generalization of clustering coefficients to signed correlation networks.  _PloS one_ (2014).
  * Das et al. (2018) Kousik Das, Sovan Samanta, and Madhumangal Pal. 2018\.  Study on centrality measures in social networks: a survey.  _Social network analysis and mining_ 8, 1 (2018), 1–11.
  * De Domenico et al. (2013a) Manlio De Domenico, Albert Solé-Ribalta, Emanuele Cozzo, Mikko Kivelä, Yamir Moreno, Mason A Porter, Sergio Gómez, and Alex Arenas. 2013a.  Mathematical formulation of multilayer networks.  _Physical Review X_ 3, 4 (2013), 041022.
  * De Domenico et al. (2013b) Manlio De Domenico, Albert Solé-Ribalta, Elisa Omodei, Sergio Gómez, and Alex Arenas. 2013b.  Centrality in interconnected multilayer networks.  _arXiv preprint arXiv:1311.2906_ (2013).
  * De Domenico et al. (2015) Manlio De Domenico, Albert Solé-Ribalta, Elisa Omodei, Sergio Gómez, and Alex Arenas. 2015\.  Ranking in interconnected multilayer networks reveals versatile nodes.  _Nature communications_ 6, 1 (2015), 1–6.
  * De Meo et al. (2012) Pasquale De Meo, Emilio Ferrara, Giacomo Fiumara, and Angela Ricciardello. 2012.  A novel measure of edge centrality in social networks.  _Knowledge-based systems_ 30 (2012), 136–150.
  * Defferrard et al. (2016) Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016.  Convolutional neural networks on graphs with fast localized spectral filtering.  _Advances in neural information processing systems_ 29 (2016).
  * Deng et al. (2009) Hongbo Deng, Michael R Lyu, and Irwin King. 2009.  A generalized co-hits algorithm and its application to bipartite graphs. In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_. 239–248.
  * Dimitrova et al. (2020) Tamara Dimitrova, Kristijan Petrovski, and Ljupcho Kocarev. 2020.  Graphlets in multiplex networks.  _Scientific reports_ 10, 1 (2020), 1–13.
  * Donges et al. (2011) Jonathan F Donges, Hanna CH Schultz, Norbert Marwan, Yong Zou, and Jürgen Kurths. 2011\.  Investigating the topology of interacting networks.  _The European Physical Journal B_ 84, 4 (2011), 635–651.
  * Donges et al. (2009) Jonathan F Donges, Yong Zou, Norbert Marwan, and Jürgen Kurths. 2009.  Complex networks in climate dynamics.  _The European Physical Journal Special Topics_ 174, 1 (2009), 157–179.
  * Durón (2020) Christina Durón. 2020\.  Heatmap centrality: A new measure to identify super-spreader nodes in scale-free networks.  _Plos one_ 15, 7 (2020), e0235690.
  * Egghe (2006) Leo Egghe. 2006\.  Theory and practise of the g-index.  _Scientometrics_ 69, 1 (2006), 131–152.
  * Eguiluz and Klemm (2002) Victor M Eguiluz and Konstantin Klemm. 2002.  Epidemic threshold in structured scale-free networks.  _Physical Review Letters_ 89, 10 (2002), 108701\.
  * Estrada et al. (2009) Ernesto Estrada, Desmond J Higham, and Naomichi Hatano. 2009\.  Communicability betweenness in complex networks.  _Physica A: Statistical Mechanics and its Applications_ 388, 5 (2009), 764–774.
  * Estrada and Rodriguez-Velazquez (2005) Ernesto Estrada and Juan A Rodriguez-Velazquez. 2005\.  Subgraph centrality in complex networks.  _Physical Review E_ 71, 5 (2005), 056103.
  * Fagiolo (2007) Giorgio Fagiolo. 2007\.  Clustering in complex directed networks.  _Physical Review E_ (2007).
  * Ford and Fulkerson (2015) Lester Randolph Ford and Delbert Ray Fulkerson. 2015.  _Flows in networks_.  Princeton university press.
  * Freeman (1977) Linton C Freeman. 1977\.  A set of measures of centrality based on betweenness.  _Sociometry_ (1977), 35–41.
  * Freeman (1978) Linton C Freeman. 1978\.  Centrality in social networks conceptual clarification.  _Social networks_ 1, 3 (1978), 215–239.
  * Freeman et al. (1991) Linton C Freeman, Stephen P Borgatti, and Douglas R White. 1991.  Centrality in valued graphs: A measure of betweenness based on network flow.  _Social networks_ 13, 2 (1991), 141–154.
  * Fronczak et al. (2002) Agata Fronczak, Janusz A Hołyst, Maciej Jedynak, and Julian Sienkiewicz. 2002.  Higher order clustering coefficients in Barabási–Albert networks.  _Physica A: Statistical Mechanics and its Applications_ (2002).
  * Gao et al. (2018) Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. 2018.  Large-scale learnable graph convolutional networks. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 1416–1424.
  * Gao et al. (2014) Shuai Gao, Jun Ma, Zhumin Chen, Guanghui Wang, and Changming Xing. 2014.  Ranking the spreading ability of nodes in complex networks based on local structure.  _Physica A: Statistical Mechanics and its Applications_ 403 (2014), 130–147.
  * Girvan and Newman (2002) Michelle Girvan and Mark EJ Newman. 2002.  Community structure in social and biological networks.  _PNAS_ (2002).
  * Gleich (2015) David F Gleich. 2015\.  PageRank beyond the web.  _Siam Review_ 57, 3 (2015), 321–363.
  * Gong and Cheng (2019) Liyu Gong and Qiang Cheng. 2019.  Exploiting edge features for graph neural networks. In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_. 9211–9219.
  * Grover and Leskovec (2016) Aditya Grover and Jure Leskovec. 2016.  node2vec: Scalable feature learning for networks. In _KDD_.
  * Gu et al. (2018b) Jiuxiang Gu, Zhenhua Wang, Jason Kuen, Lianyang Ma, Amir Shahroudy, Bing Shuai, Ting Liu, Xingxing Wang, Gang Wang, Jianfei Cai, et al. 2018b.  Recent advances in convolutional neural networks.  _Pattern recognition_ 77 (2018), 354–377.
  * Gu et al. (2018a) Shawn Gu, John Johnson, Fazle E Faisal, and Tijana Milenković. 2018a.  From homogeneous to heterogeneous network alignment via colored graphlets.  _Scientific reports_ 8, 1 (2018), 1–16.
  * Guan et al. (2020) Jun Guan, Yafei Li, Lizhi Xing, Yan Li, and Guoqiang Liang. 2020.  Closeness centrality for similarity-weight network and its application to measuring industrial sectors’ position on the Global Value Chain.  _Physica A: Statistical Mechanics and its Applications_ 541 (2020), 123337\.
  * Halu et al. (2013) Arda Halu, Raúl J Mondragón, Pietro Panzarasa, and Ginestra Bianconi. 2013.  Multiplex pagerank.  _PloS one_ 8, 10 (2013), e78293.
  * Hamilton et al. (2017a) William L Hamilton, Rex Ying, and Jure Leskovec. 2017a.  Inductive representation learning on large graphs. In _Proceedings of the 31st International Conference on Neural Information Processing Systems_. 1025–1035.
  * Hamilton et al. (2017b) William L Hamilton, Rex Ying, and Jure Leskovec. 2017b.  Representation learning on graphs: Methods and applications.  _arXiv preprint arXiv:1709.05584_ (2017).
  * Hashimoto (1989) Ki-ichiro Hashimoto. 1989\.  Zeta functions of finite graphs and representations of p-adic groups.  In _Automorphic forms and geometry of arithmetic varieties_. Elsevier, 211–280.
  * Hirsch (2005) Jorge E Hirsch. 2005\.  An index to quantify an individual’s scientific research output.  _Proceedings of the National academy of Sciences_ 102, 46 (2005), 16569–16572.
  * 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 (2016), 1–24.
  * Hoffman et al. (2019) Beth L Hoffman, Elizabeth M Felter, Kar-Hai Chu, Ariel Shensa, Chad Hermann, Todd Wolynn, Daria Williams, and Brian A Primack. 2019.  It’s not all about autism: The emerging landscape of anti-vaccination sentiment on Facebook.  _Vaccine_ 37, 16 (2019), 2216–2223.
  * Holme and Saramäki (2012) Petter Holme and Jari Saramäki. 2012.  Temporal networks.  _Physics reports_ 519, 3 (2012), 97–125.
  * Hoshino et al. (2020) Tatsuhiko Hoshino, Hideyuki Doi, Go-Ichiro Uramoto, Lars Wörmer, Rishi R Adhikari, Nan Xiao, Yuki Morono, Steven D’Hondt, Kai-Uwe Hinrichs, and Fumio Inagaki. 2020.  Global diversity of microbial communities in marine sediment.  _Proceedings of the national academy of sciences_ 117, 44 (2020), 27587–27597.
  * Hu et al. (2020) Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020\.  Open graph benchmark: Datasets for machine learning on graphs.  _Advances in neural information processing systems_ 33 (2020), 22118–22133.
  * Hu et al. (2019) Xinxin Hu, Shuxin Liu, Sheng Chang, and Haitao Li. 2019\.  A quad motifs index for directed link prediction.  _IEEE Access_ 7 (2019), 159527–159534.
  * Huang and Zitnik (2020) Kexin Huang and Marinka Zitnik. 2020.  Graph meta learning via local subgraphs.  _Advances in Neural Information Processing Systems_ 33 (2020).
  * Huang et al. (2018) Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. 2018\.  Adaptive sampling towards fast graph representation learning.  _arXiv preprint arXiv:1809.05343_ (2018).
  * Huber et al. (2007) Wolfgang Huber, Vincent J Carey, Li Long, Seth Falcon, and Robert Gentleman. 2007.  Graphs in molecular biology.  _BMC bioinformatics_ 8, 6 (2007), 1–14.
  * 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.
  * Jackson et al. (2017) Matthew O Jackson, Brian W Rogers, and Yves Zenou. 2017\.  The economic consequences of social-network structure.  _Journal of Economic Literature_ 55, 1 (2017), 49–95.
  * Jia et al. (2021a) Mingshan Jia, Maité Van Alboom, Liesbet Goubert, Piet Bracke, Bogdan Gabrys, and Katarzyna Musial. 2021a.  Analysing Ego-Networks via Typed-Edge Graphlets: A Case Study of Chronic Pain Patients. In _International Conference on Complex Networks and Their Applications_. Springer, 514–526.
  * Jia et al. (2020) Mingshan Jia, Bogdan Gabrys, and Katarzyna Musial. 2020\.  Closure Coefficient in Complex Directed Networks. In _International Conference on Complex Networks and Their Applications_. Springer, 62–74.
  * Jia et al. (2021b) Mingshan Jia, Bogdan Gabrys, and Katarzyna Musial. 2021b.  Directed closure coefficient and its patterns.  _Plos one_ 16, 6 (2021), e0253822.
  * Jia et al. (2021c) Mingshan Jia, Bogdan Gabrys, and Katarzyna Musial. 2021c.  Measuring Quadrangle Formation in Complex Networks.  _IEEE Transactions on Network Science and Engineering_ (2021).
  * Jia et al. (2022) Mingshan Jia, Maité Van Alboom, Liesbet Goubert, Piet Bracke, Bogdan Gabrys, and Katarzyna Musial. 2022.  Encoding edge type information in graphlets.  _PloS one_ 17, 8 (2022), e0273609.
  * Jiang et al. (2021) Lixin Jiang, Longkun Tang, and Jinhu Lü. 2021\.  Controllability of multilayer networks.  _Asian Journal of Control_ (2021).
  * Jiang et al. (2020) Xiaodong Jiang, Ronghang Zhu, Sheng Li, and Pengsheng Ji. 2020\.  Co-embedding of nodes and edges with graph neural networks.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ (2020).
  * Jin et al. (2020) Yilun Jin, Guojie Song, and Chuan Shi. 2020.  GraLSP: Graph neural networks with local structural patterns. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 4361–4368.
  * Kampffmeyer et al. (2019) Michael Kampffmeyer, Yinbo Chen, Xiaodan Liang, Hao Wang, Yujia Zhang, and Eric P Xing. 2019\.  Rethinking knowledge graph propagation for zero-shot learning. In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_. 11487–11496.
  * Katz (1953) Leo Katz. 1953.  A new status index derived from sociometric analysis.  _Psychometrika_ (1953).
  * Kim and Anderson (2012) Hyoungshick Kim and Ross Anderson. 2012.  Temporal node centrality in complex networks.  _Physical Review E_ 85, 2 (2012), 026107.
  * Kim et al. (2012) Hyoungshick Kim, John Tang, Ross Anderson, and Cecilia Mascolo. 2012.  Centrality prediction in dynamic human contact networks.  _Computer Networks_ 56, 3 (2012), 983–996.
  * Kipf and Welling (2016a) Thomas N Kipf and Max Welling. 2016a.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ (2016).
  * Kipf and Welling (2016b) Thomas N Kipf and Max Welling. 2016b.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ (2016).
  * Kitsak et al. (2010) Maksim Kitsak, Lazaros K Gallos, Shlomo Havlin, Fredrik Liljeros, Lev Muchnik, H Eugene Stanley, and Hernán A Makse. 2010.  Identification of influential spreaders in complex networks.  _Nature physics_ 6, 11 (2010), 888–893.
  * Kivelä et al. (2014) Mikko Kivelä, Alex Arenas, Marc Barthelemy, James P Gleeson, Yamir Moreno, and Mason A Porter. 2014.  Multilayer networks.  _Journal of complex networks_ 2, 3 (2014), 203–271.
  * Kleinberg et al. (1998) Jon M Kleinberg et al. 1998\.  Authoritative sources in a hyperlinked environment.. In _SODA_ , Vol. 98. Citeseer, 668–677.
  * Korn et al. (2009) A Korn, A Schubert, and Andras Telcs. 2009.  Lobby index in networks.  _Physica A: Statistical Mechanics and its Applications_ 388, 11 (2009), 2221–2226.
  * Kovács et al. (2019) István A Kovács, Katja Luck, Kerstin Spirohn, Yang Wang, Carl Pollis, Sadie Schlabach, Wenting Bian, Dae-Kyum Kim, Nishka Kishore, Tong Hao, et al. 2019\.  Network-based prediction of protein interactions.  _Nature communications_ 10, 1 (2019), 1–8.
  * 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.
  * Krivelevich and Sudakov (2003) Michael Krivelevich and Benny Sudakov. 2003.  The largest eigenvalue of sparse random graphs.  _Combinatorics, Probability and Computing_ 12, 1 (2003), 61–72.
  * Krzakala et al. (2013) Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang. 2013\.  Spectral redemption in clustering sparse networks.  _Proceedings of the National Academy of Sciences_ 110, 52 (2013), 20935–20940.
  * Kunegis et al. (2009) Jérôme Kunegis, Andreas Lommatzsch, and Christian Bauckhage. 2009.  The slashdot zoo: mining a social network with negative edges. In _WWW_.
  * Li et al. (2018b) Gaoshi Li, Min Li, Jianxin Wang, Yaohang Li, and Yi Pan. 2018b.  United neighborhood closeness centrality and orthology for predicting essential proteins.  _IEEE/ACM transactions on computational biology and bioinformatics_ 17, 4 (2018), 1451–1458.
  * Li et al. (2020) Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. 2020\.  Distance encoding: Design provably more powerful neural networks for graph representation learning.  _arXiv preprint arXiv:2009.00142_ (2020).
  * Li et al. (2018a) Qimai Li, Zhichao Han, and Xiao-Ming Wu. 2018a.  Deeper insights into graph convolutional networks for semi-supervised learning. In _Thirty-Second AAAI conference on artificial intelligence_.
  * Li et al. (2014) Qian Li, Tao Zhou, Linyuan Lü, and Duanbing Chen. 2014\.  Identifying influential spreaders by weighted LeaderRank.  _Physica A: Statistical Mechanics and its Applications_ 404 (2014), 47–55.
  * Li et al. (2021) Zewen Li, Fan Liu, Wenjie Yang, Shouheng Peng, and Jun Zhou. 2021.  A survey of convolutional neural networks: analysis, applications, and prospects.  _IEEE transactions on neural networks and learning systems_ (2021).
  * Li et al. (2019) Zhe Li, Tao Ren, Xiaoqi Ma, Simiao Liu, Yixin Zhang, and Tao Zhou. 2019\.  Identifying influential spreaders by gravity model.  _Scientific reports_ 9, 1 (2019), 1–7.
  * Liao et al. (2017) Hao Liao, Manuel Sebastian Mariani, Matúš Medo, Yi-Cheng Zhang, and Ming-Yang Zhou. 2017\.  Ranking in evolving complex networks.  _Physics Reports_ 689 (2017), 1–54.
  * Liben-Nowell and Kleinberg (2007) David Liben-Nowell and Jon Kleinberg. 2007.  The link-prediction problem for social networks.  _Journal of the American society for information science and technology_ (2007).
  * Lind et al. (2005) Pedro G Lind, Marta C Gonzalez, and Hans J Herrmann. 2005\.  Cycles and clustering in bipartite networks.  _Physical review E_ (2005).
  * Liu et al. (2018) Qiang Liu, Yu-Xiao Zhu, Yan Jia, Lu Deng, Bin Zhou, Jun-Xing Zhu, and Peng Zou. 2018\.  Leveraging local h-index to identify and rank influential spreaders in networks.  _Physica A: Statistical Mechanics and its Applications_ 512 (2018), 379–391.
  * Liu and Zhou (2020) Zhiyuan Liu and Jie Zhou. 2020.  Introduction to graph neural networks.  _Synthesis Lectures on Artificial Intelligence and Machine Learning_ 14, 2 (2020), 1–127.
  * Lü et al. (2016a) Linyuan Lü, Duanbing Chen, Xiao-Long Ren, Qian-Ming Zhang, Yi-Cheng Zhang, and Tao Zhou. 2016a.  Vital nodes identification in complex networks.  _Physics Reports_ 650 (2016), 1–63.
  * Lü et al. (2009) Linyuan Lü, Ci-Hang Jin, and Tao Zhou. 2009.  Similarity index based on local paths for link prediction of complex networks.  _Physical Review E_ 80, 4 (2009), 046122.
  * Lü et al. (2011) Linyuan Lü, Yi-Cheng Zhang, Chi Ho Yeung, and Tao Zhou. 2011\.  Leaders in social networks, the delicious case.  _PloS one_ 6, 6 (2011), e21202.
  * Lü et al. (2016b) Linyuan Lü, Tao Zhou, Qian-Ming Zhang, and H Eugene Stanley. 2016b.  The H-index of a network node and its relation to degree and coreness.  _Nature communications_ 7, 1 (2016), 1–7.
  * Ma et al. (2016) Ling-ling Ma, Chuang Ma, Hai-Feng Zhang, and Bing-Hong Wang. 2016\.  Identifying influential spreaders in complex networks based on gravity formula.  _Physica A: Statistical Mechanics and its Applications_ 451 (2016), 205–212.
  * Ma and Ma (2017) Qian Ma and Jun Ma. 2017\.  Identifying and ranking influential spreaders in complex networks with consideration of spreading probability.  _Physica A: Statistical Mechanics and its Applications_ 465 (2017), 312–330.
  * Ma and Gao (2012) Xiaoke Ma and Lin Gao. 2012\.  Biological network analysis: insights into structure and functions.  _Briefings in functional genomics_ 11, 6 (2012), 434–442.
  * Ma and Ma (2019) Xiaojian Ma and Yinghong Ma. 2019.  The local triangle structure centrality method to rank nodes in networks.  _Complexity_ 2019 (2019).
  * Ma and Tang (2021) Yao Ma and Jiliang Tang. 2021.  _Deep learning on graphs_.  Cambridge University Press.
  * Mara et al. (2022) Alexandru Cristian Mara, Jefrey Lijffijt, and Tijl De Bie. 2022\.  An Empirical Evaluation of Network Representation Learning Methods.  _Big Data_ (2022).
  * Martin et al. (2014) Travis Martin, Xiao Zhang, and Mark EJ Newman. 2014\.  Localization and centrality in networks.  _Physical review E_ 90, 5 (2014), 052808.
  * Martínez et al. (2016) Víctor Martínez, Fernando Berzal, and Juan-Carlos Cubero. 2016.  A survey of link prediction in complex networks.  _ACM computing surveys (CSUR)_ 49, 4 (2016), 1–33.
  * Micali and Zhu (2016) Silvio Micali and Zeyuan Allen Zhu. 2016.  Reconstructing markov processes from independent and anonymous experiments.  _Discrete Applied Mathematics_ 200 (2016), 108–122.
  * Milenković and Pržulj (2008) Tijana Milenković and Nataša Pržulj. 2008\.  Uncovering biological network function via graphlet degree signatures.  _Cancer informatics_ 6 (2008), CIN–S680.
  * 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_ (2002).
  * Møller and Schwartzbach (2012) Anders Møller and Michael I Schwartzbach. 2012.  Static program analysis.  _Notes. Feb_ (2012).
  * Mones et al. (2012) Enys Mones, Lilla Vicsek, and Tamás Vicsek. 2012.  Hierarchy measure for complex networks.  _PloS one_ 7, 3 (2012), e33799.
  * Morone and Makse (2015) Flaviano Morone and Hernán A Makse. 2015.  Influence maximization in complex networks through optimal percolation.  _Nature_ 524, 7563 (2015), 65–68.
  * Morris et al. (2019) Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. 2019\.  Weisfeiler and leman go neural: Higher-order graph neural networks. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 33. 4602–4609.
  * Muhammet et al. (2020) Balcilar Muhammet, Renton Guillaume, Héroux Pierre, Gaüzère Benoit, Adam Sébastien, and Paul Honeine. 2020\.  When spectral domain meets spatial domain in graph neural networks. In _Thirty-seventh International Conference on Machine Learning (ICML 2020)-Workshop on Graph Representation Learning and Beyond (GRL+ 2020)_.
  * Muscoloni et al. (2018) Alessandro Muscoloni, Ilyes Abdelhamid, and Carlo Vittorio Cannistraci. 2018.  Local-community network automata modelling based on length-three-paths for prediction of complex network structures in protein interactomes, food webs and more.  _bioRxiv_ (2018), 346916\.
  * Musiał and Kazienko (2013) Katarzyna Musiał and Przemysław Kazienko. 2013.  Social networks on the internet.  _World Wide Web_ 16, 1 (2013), 31–72.
  * Neville and Jensen (2000) Jennifer Neville and David Jensen. 2000.  Iterative classification in relational data. In _Proc. AAAI-2000 workshop on learning statistical models from relational data_. 13–20.
  * Newman (2018) Mark Newman. 2018\.  _Networks_.  Oxford university press.
  * Newman (2005) Mark EJ Newman. 2005\.  A measure of betweenness centrality based on random walks.  _Social networks_ 27, 1 (2005), 39–54.
  * Nicosia et al. (2013) Vincenzo Nicosia, John Tang, Cecilia Mascolo, Mirco Musolesi, Giovanni Russo, and Vito Latora. 2013\.  Graph metrics for temporal networks.  In _Temporal networks_. Springer, 15–40.
  * Niepert et al. (2016) Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. 2016\.  Learning convolutional neural networks for graphs. In _International conference on machine learning_. PMLR, 2014–2023.
  * Nikolentzos et al. (2020) Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. 2020.  k-hop graph neural networks.  _Neural Networks_ 130 (2020), 195–205.
  * Onnela et al. (2005) Jukka-Pekka Onnela, Jari Saramäki, János Kertész, and Kimmo Kaski. 2005.  Intensity and coherence of motifs in weighted complex networks.  _Physical Review E_ (2005).
  * Opsahl et al. (2010) Tore Opsahl, Filip Agneessens, and John Skvoretz. 2010\.  Node centrality in weighted networks: Generalizing degree and shortest paths.  _Social networks_ 32, 3 (2010), 245–251.
  * Ou et al. (2016) Mingdong Ou, Peng Cui, Jian Pei, Ziwei Zhang, and Wenwu Zhu. 2016.  Asymmetric transitivity preserving graph embedding. In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_. 1105–1114.
  * Paranjape et al. (2017) Ashwin Paranjape, Austin R Benson, and Jure Leskovec. 2017\.  Motifs in temporal networks. In _Proceedings of the tenth ACM international conference on web search and data mining_. 601–610.
  * Pavlopoulos et al. (2011) Georgios A Pavlopoulos, Maria Secrier, Charalampos N Moschopoulos, Theodoros G Soldatos, Sophia Kossida, Jan Aerts, Reinhard Schneider, and Pantelis G Bagos. 2011.  Using graph theory to analyze biological networks.  _BioData mining_ 4, 1 (2011), 1–27.
  * Perozzi et al. (2014) Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. 2014\.  Deepwalk: Online learning of social representations. In _KDD_.
  * 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.  _ACM Computing Surveys (CSUR)_ 54, 2 (2021), 1–36.
  * Risselada et al. (2016) Hans Risselada, Peter C Verhoef, and Tammo HA Bijmolt. 2016\.  Indicators of opinion leadership in customer networks: self-reports and degree centrality.  _Marketing Letters_ 27, 3 (2016), 449–460.
  * Rodrigues (2019) Francisco Aparecido Rodrigues. 2019\.  Network centrality: an introduction.  In _A mathematical modeling approach from nonlinear dynamics to complex systems_. Springer, 177–196.
  * Rossi et al. (2020) Ryan A Rossi, Nesreen K Ahmed, Aldo Carranza, David Arbour, Anup Rao, Sungchul Kim, and Eunyee Koh. 2020.  Heterogeneous graphlets.  _ACM Transactions on Knowledge Discovery from Data (TKDD)_ 15, 1 (2020), 1–43.
  * Said et al. (2018) Anwar Said, Rabeeh Ayaz Abbasi, Onaiza Maqbool, Ali Daud, and Naif Radi Aljohani. 2018.  CC-GA: A clustering coefficient based genetic algorithm for detecting communities in social networks.  _Applied Soft Computing_ 63 (2018), 59–70.
  * Salavati et al. (2018) Chiman Salavati, Alireza Abdollahpouri, and Zhaleh Manbari. 2018\.  BridgeRank: A novel fast centrality measure based on local structure of the network.  _Physica A: Statistical Mechanics and its Applications_ 496 (2018), 635–653.
  * Salehi et al. (2015) Mostafa Salehi, Rajesh Sharma, Moreno Marzolla, Matteo Magnani, Payam Siyari, and Danilo Montesi. 2015\.  Spreading processes in multilayer networks.  _IEEE Transactions on Network Science and Engineering_ 2, 2 (2015), 65–83.
  * Sato et al. (2021) Ryoma Sato, Makoto Yamada, and Hisashi Kashima. 2021\.  Random features strengthen graph neural networks. In _Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)_. SIAM, 333–341.
  * Skarding et al. (2021) Joakim Skarding, Bogdan Gabrys, and Katarzyna Musial. 2021\.  Foundations and modeling of dynamic networks using dynamic graph neural networks: A survey.  _IEEE Access_ 9 (2021), 79143–79168.
  * Stephenson and Zelen (1989) Karen Stephenson and Marvin Zelen. 1989.  Rethinking centrality: Methods and examples.  _Social networks_ 11, 1 (1989), 1–37.
  * Tan et al. (2021) Zhuo Tan, Bin Liu, and Guosheng Yin. 2021.  Asymmetric Graph Representation Learning.  _arXiv preprint arXiv:2110.07436_ (2021).
  * Tang et al. (2013) Xiwei Tang, Jianxin Wang, Jiancheng Zhong, and Yi Pan. 2013\.  Predicting essential proteins based on weighted degree centrality.  _IEEE/ACM Transactions on Computational Biology and Bioinformatics_ 11, 2 (2013), 407–418.
  * Taylor et al. (2017) Dane Taylor, Sean A Myers, Aaron Clauset, Mason A Porter, and Peter J Mucha. 2017.  Eigenvector-based centrality measures for temporal networks.  _Multiscale Modeling & Simulation_ 15, 1 (2017), 537–574.
  * Tong et al. (2020) Zekun Tong, Yuxuan Liang, Changsheng Sun, David S Rosenblum, and Andrew Lim. 2020.  Directed graph convolutional network.  _arXiv preprint arXiv:2004.13970_ (2020).
  * Trolliet et al. (2020) Thibaud Trolliet, Nathann Cohen, Frédéric Giroire, Luc Hogie, and Stéphane Pérennes. 2020\.  Interest clustering coefficient: a new metric for directed networks like twitter. In _International Conference on Complex Networks and Their Applications_. Springer, 597–609.
  * Veličković et al. (2017) Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. 2017.  Graph attention networks.  _arXiv preprint arXiv:1710.10903_ (2017).
  * Vignac et al. (2020) Clement Vignac, Andreas Loukas, and Pascal Frossard. 2020\.  Building powerful and equivariant graph neural networks with structural message-passing.  _arXiv preprint arXiv:2006.15107_ (2020).
  * Wang and Zou (2018) Dingjie Wang and Xiufen Zou. 2018.  A new centrality measure of nodes in multilayer networks under the framework of tensor computation.  _Applied Mathematical Modelling_ 54 (2018), 46–63.
  * Wang and Cheng (2012) Jia Wang and James Cheng. 2012.  Truss decomposition in massive networks.  _arXiv preprint arXiv:1205.6693_ (2012).
  * Wang et al. (2011) Jianxin Wang, Min Li, Huan Wang, and Yi Pan. 2011\.  Identification of essential proteins based on edge clustering coefficient.  _IEEE/ACM Transactions on Computational Biology and Bioinformatics_ (2011).
  * Wang et al. (2017) Yafei Wang, Guanghui Yan, Qingqing Ma, Yu Wu, and Dan Jin. 2017.  Identifying influential spreaders on weighted networks based on ClusterRank. In _2017 10th International Symposium on Computational Intelligence and Design (ISCID)_ , Vol. 2. IEEE, 476–479.
  * Wasserman et al. (1994) Stanley Wasserman, Katherine Faust, et al. 1994\.  Social network analysis: Methods and applications.  (1994).
  * Watts and Strogatz (1998) Duncan J Watts and Steven H Strogatz. 1998.  Collective dynamics of ‘small-world’networks.  _nature_ (1998).
  * Weisfeiler and Leman (1968) Boris Weisfeiler and Andrei Leman. 1968.  The reduction of a graph to canonical form and the algebra which appears therein.  _NTI, Series_ 2, 9 (1968), 12–16.
  * White and Borgatti (1994) Douglas R White and Stephen P Borgatti. 1994.  Betweenness centrality measures for directed graphs.  _Social networks_ 16, 4 (1994), 335–346.
  * Wijesinghe and Wang (2021) Asiri Wijesinghe and Qing Wang. 2021.  A New Perspective on” How Graph Neural Networks Go Beyond Weisfeiler-Lehman?”. In _International Conference on Learning Representations_.
  * Wu et al. (2019) Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019\.  Simplifying graph convolutional networks. In _International conference on machine learning_. PMLR, 6861–6871.
  * Wu et al. (2020) Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020\.  A comprehensive survey on graph neural networks.  _IEEE transactions on neural networks and learning systems_ 32, 1 (2020), 4–24.
  * Xie et al. (2022) Yaochen Xie, Zhao Xu, Jingtun Zhang, Zhengyang Wang, and Shuiwang Ji. 2022.  Self-supervised learning of graph neural networks: A unified review.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ (2022).
  * Xing and Ghorbani (2004) Wenpu Xing and Ali Ghorbani. 2004.  Weighted pagerank algorithm. In _Proceedings. Second Annual Conference on Communication Networks and Services Research, 2004._ IEEE, 305–314.
  * Xu et al. (2021) Fengli Xu, Quanming Yao, Pan Hui, and Yong Li. 2021\.  Automorphic Equivalence-aware Graph Neural Network.  _Advances in Neural Information Processing Systems_ 34 (2021), 15138–15150.
  * Xu et al. (2018) Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2018\.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ (2018).
  * Xu and Wang (2017) Shuang Xu and Pei Wang. 2017.  Identifying important nodes by adaptive LeaderRank.  _Physica A: Statistical Mechanics and its Applications_ 469 (2017), 654–664.
  * Yin et al. (2018) Hao Yin, Austin R Benson, and Jure Leskovec. 2018.  Higher-order clustering in networks.  _Physical Review E_ 97, 5 (2018), 052306.
  * Yin et al. (2019) Hao Yin, Austin R Benson, and Jure Leskovec. 2019.  The local closure coefficient: A new perspective on network clustering. In _WSDM_.
  * Yin et al. (2020) Hao Yin, Austin R Benson, and Johan Ugander. 2020.  Measuring directed triadic closure with closure coefficients.  _Network Science_ 8, 4 (2020), 551–573.
  * Ying et al. (2018) Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. 2018\.  Graph convolutional neural networks for web-scale recommender systems. In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_. 974–983.
  * Ying et al. (2019) Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. 2019.  Gnnexplainer: Generating explanations for graph neural networks.  _Advances in neural information processing systems_ 32 (2019).
  * You et al. (2021) Jiaxuan You, Jonathan Gomes-Selman, Rex Ying, and Jure Leskovec. 2021.  Identity-aware graph neural networks.  _arXiv preprint arXiv:2101.10320_ (2021).
  * You et al. (2019) Jiaxuan You, Rex Ying, and Jure Leskovec. 2019.  Position-aware graph neural networks. In _International conference on machine learning_. PMLR, 7134–7143.
  * Yuan et al. (2022) Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. 2022\.  Explainability in graph neural networks: A taxonomic survey.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ (2022).
  * Yun et al. (2021) Seongjun Yun, Seoyoon Kim, Junhyun Lee, Jaewoo Kang, and Hyunwoo J Kim. 2021.  Neo-gnns: Neighborhood overlap-aware graph neural networks for link prediction.  _Advances in Neural Information Processing Systems_ 34 (2021), 13683–13694.
  * Zeng et al. (2021) Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. 2021.  Decoupling the depth and scope of graph neural networks.  _Advances in Neural Information Processing Systems_ 34 (2021), 19665–19679.
  * Zeng et al. (2019) Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. 2019\.  Graphsaint: Graph sampling based inductive learning method.  _arXiv preprint arXiv:1907.04931_ (2019).
  * Zhang and Horvath (2005) Bin Zhang and Steve Horvath. 2005.  A general framework for weighted gene co-expression network analysis.  _Statistical applications in genetics and molecular biology_ (2005).
  * Zhang (2009) Chun-Ting Zhang. 2009\.  The e-index, complementing the h-index for excess citations.  _PLoS One_ 4, 5 (2009), e5429.
  * Zhang et al. (2011) Han Zhang, Marcelo Fiszman, Dongwook Shin, Christopher M Miller, Graciela Rosemblat, and Thomas C Rindflesch. 2011.  Degree centrality for semantic abstraction summarization of therapeutic studies.  _Journal of biomedical informatics_ 44, 5 (2011), 830–838.
  * Zhang and Chen (2018) Muhan Zhang and Yixin Chen. 2018.  Link prediction based on graph neural networks.  _Advances in Neural Information Processing Systems_ 31 (2018), 5165–5175.
  * Zhang et al. (2018) Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. 2018\.  An end-to-end deep learning architecture for graph classification. In _Thirty-Second AAAI Conference on Artificial Intelligence_.
  * Zhang and Li (2021) Muhan Zhang and Pan Li. 2021.  Nested graph neural networks.  _Advances in Neural Information Processing Systems_ 34 (2021), 15734–15747.
  * Zhang et al. (2008) Peng Zhang, Jinliang Wang, Xiaojia Li, Menghui Li, Zengru Di, and Ying Fan. 2008\.  Clustering coefficient and community structure of bipartite networks.  _Physica A: Statistical Mechanics and its Applications_ (2008).
  * Zhang et al. (2013a) Qian-Ming Zhang, Linyuan Lü, Wen-Qiang Wang, Tao Zhou, et al. 2013a.  Potential theory for directed networks.  _PloS one_ 8, 2 (2013), e55437.
  * Zhang et al. (2019) Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. 2019\.  Graph convolutional networks: a comprehensive review.  _Computational Social Networks_ 6, 1 (2019), 1–23.
  * Zhang et al. (2013b) Xiaohang Zhang, Ji Zhu, Qi Wang, and Han Zhao. 2013b.  Identifying influential nodes in complex networks with community structure.  _Knowledge-Based Systems_ 42 (2013), 74–84.
  * Zhang et al. (2020) Ziwei Zhang, Peng Cui, and Wenwu Zhu. 2020.  Deep learning on graphs: A survey.  _IEEE Transactions on Knowledge and Data Engineering_ (2020).
  * Zhao et al. (2021) Lingxiao Zhao, Wei Jin, Leman Akoglu, and Neil Shah. 2021\.  From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness.  _arXiv preprint arXiv:2110.03753_ (2021).
  * Zhao et al. (2016) Yuxin Zhao, Shenghong Li, and Feng Jin. 2016.  Identification of influential nodes in social networks with community structure based on label propagation.  _Neurocomputing_ 210 (2016), 34–44.
  * Zhou et al. (2020) Jie Zhou, Ganqu Cui, Shengding Hu, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. 2020.  Graph neural networks: A review of methods and applications.  _AI Open_ 1 (2020), 57–81.
  * Zhou et al. (2021) Tao Zhou, Yan-Li Lee, and Guannan Wang. 2021.  Experimental analyses on 2-hop-based and 3-hop-based link prediction algorithms.  _Physica A: Statistical Mechanics and its Applications_ 564 (2021), 125532\.
  * Zhou et al. (2005) Tao Zhou, Gang Yan, and Bing-Hong Wang. 2005.  Maximal planar networks with large clustering coefficient and power-law degree distribution.  _Physical Review E_ 71, 4 (2005), 046141.