# A Network Science perspective of Graph Convolutional Networks: A survey

Mingshan Jia<EMAIL_ADDRESS>1234-5678-9012 ,  Bogdan Gabrys
<EMAIL_ADDRESS>and  Katarzyna Musial  katarzyna.musial-
<EMAIL_ADDRESS>University of Technology Sydney15
BroadwaySydneyNSWAustralia2007

###### Abstract.

The mining and exploitation of graph structural information have been the
focal points in the study of complex networks. Traditional structural measures
in Network Science focus on the analysis and modelling of complex networks
from the perspective of network structure, such as the centrality measures,
the clustering coefficient, and motifs and graphlets, and they have become
basic tools for studying and understanding graphs. In comparison, graph neural
networks, especially graph convolutional networks (GCNs), are particularly
effective at integrating node features into graph structures via neighbourhood
aggregation and message passing, and have been shown to significantly improve
the performances in a variety of learning tasks. These two classes of methods
are, however, typically treated separately with limited references to each
other. In this work, aiming to establish relationships between them, we
provide a network science perspective of GCNs. Our novel taxonomy classifies
GCNs from three structural information angles, i.e., the layer-wise message
aggregation scope, the message content, and the overall learning scope.
Moreover, as a prerequisite for reviewing GCNs via a network science
perspective, we also summarise traditional structural measures and propose a
new taxonomy for them. Finally and most importantly, we draw connections
between traditional structural approaches and graph convolutional networks,
and discuss potential directions for future research.

Graph Convolutional Networks, Network Science, graph structural measures

††copyright: acmcopyright††doi: 10.1145/1122445.1122456††conference: Woodstock
’18: ACM Symposium on Neural Gaze Detection; June 03–05, 2018; Woodstock,
NY††ccs: Networks Topology analysis and generation††ccs: Networks Network
structure††ccs: Computing methodologies Machine learning

##  1\. Introduction

Networks or graphs are a general language for modelling and analysing complex
systems that are abstracted as entities and their connections (Barabási et
al., 2016; Newman, 2018). In the representation of networks, domain data is no
longer only being a set of isolated data points but also contains important
information about the relationships among them. The entities are related to
each other according to the structure of the network, and modelling these
relational structures allows us to build more accurate models of the domain
data. Various types of real-world data can naturally be modelled as networks,
such as social networks representing social actors and their relationships
(Musiał and Kazienko, 2013), molecular graphs representing chemical atoms and
their bonds (Huber et al., 2007), transportation networks representing
infrastructures and traffic flow (Bell et al., 1997), control flow graphs
representing code blocks and their executions (Møller and Schwartzbach, 2012),
etc.

Although networks are very powerful at modelling relational data, processing
them is significantly more difficult, mainly due to their intricate
topological structures. Compared to other common data formats such as images
or text, network data does not have a starting or an ending point that can be
defined in Euclidean space, nor the essential notion of spacial locality and
proximity. Therefore, understanding and exploiting graph structure has always
been a core theme in analysing complex networks. Traditional network science
approaches are mostly structure-related heuristics, such as various types of
node centralities (Lü et al., 2016a) for node-level analysis, common
neighbours similarity and its variants (Martínez et al., 2016) for link-level
analysis, and motifs (Milo et al., 2002) and significance profile (Milo et
al., 2004) for graph-level analysis. These methods, along with others, have
become the standard tools for analysing graphs and have been used in all kinds
of networks. Certainly, these approaches have their limitations. First is
their applicability — each is effective for examining specific properties but
falls short of capturing other structural aspects. Another drawback is that
most heuristic approaches focus on graph structures while overlooking the rich
information that could be contained in nodes or on edges (Liu and Zhou, 2020).

Another mainstream class of methods is grounded in deep learning on graphs,
especially the recently emerging and quickly gaining in popularity graph
convolutional networks (GCNs) (Wu et al., 2020). GCNs are generalised from the
notion of Convolutional Neural Networks (CNNs) (Albawi et al., 2017),
redefining them for non-Euclidean graph data. GCNs ingeniously combine graph
structure and node/edge features via neighbourhood message aggregation and a
structure-based propagation scheme. Being a rapidly evolving area of research,
a large number of graph convolutional network approaches have emerged in
recent years, aiming to improve its expressivity, scalability, or targeting
specific tasks or types of networks (Abadal et al., 2021). However, there are
still many challenges and opportunities in this field. Some of the key open
problems include developing more powerful and efficient GCN architectures,
extending these models to handle temporal, multi-layered, or other more
complex graph data, and improving the interpretability and transparency of GCN
models.

Figure 1. Taxonomy of graph convolutional networks from structural
perspectives.

Traditional structural measures of Network Science are direct and efficient
tools for analysing and understanding complex networks, while graph
convolutional networks are deep learning models designed specifically for
graph data in order to address various learning problems. As discussed, the
two classes of methods have their own strengths and weaknesses. Surprisingly,
they are very often treated separately with relatively limited references to
each other. Network science researchers may be sceptical about the lack of
explainability of deep learning approaches, while deep learning researchers
tend to overlook the advance in traditional non-learning approaches. We
believe, however, that with the established foundations of traditional
structural measures in Network Science, and GCNs emerging as a new powerful
class of methods, there would be great benefits to be realised from a closer
integration and awareness of the two communities. On the one hand, GCNs
gracefully incorporate node features, which are largely overlooked in
traditional structural measures, into the structure of graphs, and achieve
state-of-the-art performances in various tasks. On the other hand, traditional
network science notions, being the foundations of understanding and
characterising complex networks, are also indispensable in studying GCNs.
Different types of structural measures are being exploited in the recent
advance of GCNs as well (Bouritsas et al., 2020; Jin et al., 2020; Li et al.,
2020; Xu et al., 2021). Therefore, in this work, we aim to link the two
classes of methods together by comprehensively reviewing each of them,
proposing new taxonomies and discussing their connections.

Along with the phenomenal development of GCNs, many survey articles appeared
to summarise and review them. Some have a broad scope that covers graph
representation learning (Hamilton et al., 2017b) or graph deep learning
(Bronstein et al., 2017; Zhang et al., 2020; Wu et al., 2020) in general. Some
others are focused on specific aspects, such as the design pipeline or the
composition modules of graph neural networks (Zhou et al., 2020), the dynamic
mechanisms (Skarding et al., 2021), or the learning on limited labelled
samples (Xie et al., 2022). However, there still lacks an examination that
focuses on how graph structure information (which is the main focus of
traditional network science approaches), is exploited in graph convolutional
networks. Thus, in this work, we propose new taxonomies of GCNs from the
perspective of graph local structure, and at the same time, review the latest
works that improve graph neural networks through exploiting local structural
information. Specifically, we propose to summarise graph convolutional
networks from three structural angles, i.e., the scope of layer-wise message
aggregation, the content of the message being passed on, and the overall scope
of learning on graphs (Figure 1).

Moreover, a systematic understanding of traditional graph structural
approaches is the prerequisite for thoroughly reviewing GCNs via a network
science perspective. Therefore, before jumping into the sphere of graph neural
networks, we first summarise and classify non-learning graph structural
measures. The study of graph structures is so ubiquitous that they often
appear in different terms, such as the big family of centrality measures (Lü
et al., 2016a; Rodrigues, 2019; Das et al., 2018), the popular notion of
motifs (Milo et al., 2002) and graphlets (Milenković and Pržulj, 2008) and the
set of subgraph formation measurements such as the clustering coefficient
(Watts and Strogatz, 1998), the closure coefficient (Yin et al., 2019), the
square clustering coefficient (Lind et al., 2005), etc. Existing surveys on
structure measurements only cover one or two sets of those notions, and fail
to unite them from an overarching perspective or to draw connections and
comparisons between them. Therefore, in this work with a focus on graph
structure, we also propose a new taxonomy that brings all these concepts
together. Specifically, we group existing graph structural measures into five
categories: subgraph count based measures, subgraph formation based measures,
global path based measures, message passing based measures, and hybrid
measures ( Figure 2). More importantly, through summarising both the
traditional structural measures and the graph convolutional network
approaches, we could draw connections between the two, strengthen the
understanding and analysis of GCNs and lead to insightful discussions about
potential research avenues.

Figure 2. Structural measures on graphs.

To summarise, the main contributions of this survey are as follows:

  * •

We propose a new taxonomy that brings together various types of traditional
structure-based approaches. We make a clearer distinction between the concepts
of local and global, and we first introduce and summarise the category of
subgraph formation based approaches.

  * •

We propose a novel taxonomy of graph convolutional networks, with a focus on
the exploitation of graph structural information. The taxonomy categorises
GCNs from three structural information angles, i.e., the layer-wise message
aggregation scope, the message content, and the overall learning scope. We
review and summarise the latest GCN approaches with a structural focus, and
provide a thorough analysis of the time and space complexities.

  * •

We draw connections between the graph convolutional networks and the
traditional structure-based approaches, and discuss three potential future
research avenues in the joint area.

The rest of this survey is organised as follows: In Section 2, we introduce
and compare two pairs of concepts, i.e., local and global, and motifs and
graphlets. In Section 3, we present the five categories of graph structural
measures and discuss four open problems. In Section 4, we introduce the novel
taxonomy of graph convolutional networks, and discuss their time and space
complexities. In Section 5, we discuss the connections between the traditional
structural measures and the graph convolutional networks, and present some
potential research directions. Finally, we conclude the article in Section 6.

##  2\. Preliminaries and Background

This section introduces preliminary concepts that are helpful for
understanding the proposed taxonomies.

###  2.1. Local vs. Global

When discussing graph structural measures, we need first to distinguish what
is local and what is global. Previous works (Donges et al., 2009; Jackson et
al., 2017; Martínez et al., 2016; Ma and Gao, 2012) either only focus on where
the measures are defined by dividing them into two or three categories: (i)
the ”local”, ”micro” or ”individual” level; (ii) the ”global”, ”macro” or
”aggregate” level; and (iii) sometimes at the ”mesoscopic”, ”quasi-local” or
”subnetwork” level; or they are defined solely based on the scope of
information involved in their computation. This, however, leads to some
confusion. For example, the betweenness centrality is defined for nodes (at
the node-level) but requires global information to compute. Should it be
termed a local measure or a global measure? Similarly, the average clustering
coefficient is defined at the network-level, but only needs local information
at each node — calculating the local clustering coefficient at each node, then
averaging over all nodes.

Therefore, we propose the following terms to distinguish both at what level
the measures are defined and the scope of information that is needed to
calculate them:

  * •

Local-level measure is a measurement defined on a node-level or link-level
(the link here also includes the non-existing or potential link which is often
used in a link prediction task). Thus, it can be further divided into a node-
level measure and a link-level measure.

  * •

Network-level measure is a measurement defined for the entire network.

  * •

Local structural measure is a measurement whose computation only involves the
nearby neighbourhood of a node, i.e., within a range of k-hop away from a
node. In most cases, k is less than or equal to $4$. Many traditional measures
only care about the immediate neighbourhood around a node, and we name them as
Strict-local structural measures.

  * •

Global structural measure is a measurement that involves the global
information in computation. This type of measurement often involves the
computation of paths between nodes in the network.

Now, when we revisit the betweenness centrality, it is both a local-level and
a global structural measure. The average clustering coefficient, on the other
hand, is both a network-level measure and a local structural measure. Notice
that the average clustering coefficient involves the extra step of averaging
over all nodes. Indeed, it is $n$ times the complexity of computing the local
clustering coefficient at a single node. However, any local-level measure can
easily have an extended definition at the network-level through averaging over
all nodes or edges. Moreover, in the practice of network analysis, local-level
measures are often calculated for the entire network, looping over all nodes
or all edges. Therefore, when defining local or global structural measures, we
choose to exclude this aggregation or averaging step.

To summarise, we use the terms local-level and global-level to distinguish
where the measure is defined, and we use the terms local structural and global
structural to distinguish the scope of information involved in the
computation, before the aggregation/averaging step.

###  2.2. Motifs vs. Graphlets

Next, we distinguish three similar concepts that are later used in our
taxonomies, i.e., subgraphs, motifs and graphlets. A subgraph, as the name
implies, is a smaller graph whose node set and edge set are subsets of those
of the original graph. We then recap the notions of motifs (Milo et al., 2002)
and graphlets (Milenković and Pržulj, 2008) according to the papers that
proposed them.

Table 1. Some 3-node and 4-node motifs in directed networks(Milo et al., 2002). Motifs containing bidirectional edges are not included.  Motif | Designation | Type of network
---|---|---
| 3-node feed-forward loop |  | Gene regulation network
---
Neural network
Electronic circuits (forward logic chips)
| 3-chain | Food webs
| 3-node feedback loop |  | Gene regulation network
---
Neural network
Electronic circuits (forward logic chips)
| Bi-fan |  | Gene regulation network
---
Neural network
Electronic circuits (forward logic chips)
Electronic circuits II
| Bi-parallel |  | Neural network
---
Food webs
Electronic circuits (forward logic chips)
| 4-node feedback loop | Electronic circuits II

Network motifs (Milo et al., 2002) are subgraphs that recur much more
frequently in the real network than in an ensemble of randomised networks.
They are defined at the network-level, in order to uncover the basic building
blocks of directed networks across domains. Subgraphs having a $p$-value less
than $0.01$ are deemed as motifs, where $p$ is the probability of the subgraph
appearing more times in randomised networks than in the real network. The
statistical significance of a motif can also be captured by the Z-score, which
is calculated as follows:

$Z_{i}=\left(N_{i}^{\mathrm{real}}-\bar{N}_{i}^{\mathrm{rand}}\right)/\operatorname{std}\left(N_{i}^{\text{rand
}}\right),$

where $N_{i}^{\mathrm{real}}$ is the number of subgraphs of type $i$ in the
real network, and $N_{i}^{\text{rand }}$ is the number of subgraphs of type
$i$ in a randomised network. A natural downside of this approach, however, is
that it needs to generate a large number of random networks (e.g. 100s or
1000s) using a certain configuration model. The original work only focuses on
3-node and 4-node directed subgraphs, finding that particular subgraphs such
as 3-node feed-forward loop, 3-node feedback loop, bi-fan, bi-parallel, and
4-node feedback loop are significant building blocks in several different
types of directed networks (Table 1).

Graphlets (Milenković and Pržulj, 2008), are nonisomorphic induced subgraphs
around a focal node. In the original work, it is defined for undirected
networks. A key difference between motifs and graphlets is that graphlets are
defined at node-level. The term automorphism orbits, or orbits for short, are
used to distinguish different positions of the focal node in a subgraph.
Therefore, when subgraph size is limited to a range of 2 to 5 nodes, there are
73 different orbits on 30 different subgraphs. We recap graphlets with the
orbits in Figure 3 (in order to save some space, the majority of 5-node
graphlets are omitted). It is worth mentioning that the idea of counting
induced subgraphs is also extended to the link-level, leading to the notion of
edge orbits (Hočevar and Demšar, 2016). Taking graphlet $G_{1}$ in Figure 3
for example, there exist two (node) orbits denoted ’1’ and ’2’, respectively.
In contrast, there is only one edge orbit in it since the two edges are
structurally equivalent.

Figure 3. Graphlets and their orbits (Milenković and Pržulj, 2008)

To summarise, motifs and graphlets are both small induced subgraphs, but they
are different in the following aspects (Figure 4): motifs are defined at the
network-level while graphlets are defined at the node-level; motifs are
proposed for directed networks while graphlets are for undirected networks;
motifs are discovered from comparing real networks to randomised networks with
the same degree sequence while graphlets are calculated on the network itself;
lastly, motifs contain 3 - 4 nodes while graphlets have 2 -5 nodes. Notice
that most of the analyses stop at 4 or 5 nodes because a subgraph containing
more than 5 nodes would become too complicated for us to enumerate and
interpret all possible subgraphs or orbits. For example, a 6-node induced
subgraph leads up to 112 different types of subgraphs and 407 different
orbits. Taking link directions into consideration, there are $1,530,843$
subgraphs and $9,031,113$ orbits (Ribeiro et al., 2021).

Figure 4. Motifs vs. Graphlets

##  3\. Graph structural measures

In order to set up the context of reviewing graph convolutional networks from
a Network Science perspective, we first summarise traditional graph structural
measures and propose a novel taxonomy for them, which will later be used in
our categorisation and analysis of GCNs. Specifically, We divide existing
structural measures into five categories (see Figure 2):

  * •

Subgraph Count Based Approaches. These measures are defined based on the
number of a particular subgraph or subgraphs.

  * •

Subgraph Formation Based Approaches. In this category, the measures are
defined by the ratio of the numbers of two subgraphs: one contains fewer edges
(or nodes) and is viewed as the formation base of another.

  * •

Global Path Based Approaches. As the name implies, these measures are based on
unbounded paths. They involve the calculation of shortest paths or all paths
originating from a node to any node in the entire graph.

  * •

Message Passing Based Approaches. Unlike previous categories, message passing-
based approaches utilise graph structural information in an implicit manner:
every node is initialised with an importance score. Then iteratively, each
node updates its score through aggregating the scores of its neighbours. Graph
Neural Network approaches (see more in Section 4) can be viewed as
transforming this traditional message passing approach into a learnable
process.

  * •

Hybrid Approaches. These measures are simply some combinations of the previous
four categories.

We now explain the logic behind our taxonomy. The first two categories both
cover a local area of the whole network (within a certain distance from the
focal node, or containing a limited number of nodes and edges). The first
category — subgraph count based approaches — is built from counting the number
of particular local structures. For example, the number of neighbours, local
paths or subgraphs. The second category — subgraph formation based approaches
— is uniquely defined based on the ratio of two subgraphs and thus bears the
meaning of measuring the formation of certain local structures. To have both
of them in the taxonomy instead of combining them into one category is to
stress their differences.

Then, the third category expands its scope to the entire network. We name it
global path based approaches instead of just global approaches. This is
because all global approaches involve either the calculation of shortest paths
or all paths originating from a node to any other node in the entire graph.
Notice here that a path is also a particular type of subgraph. However, a
local path or bounded path, such as a 2-path or 3-path, belongs to the
category of subgraph count based measures, whereas a global path or unbounded
path is in this category. We choose to differentiate the third category from
the previous two categories from the perspective of the covered scope.

Next, the fourth category — message passing based approaches — is based on the
idea of propagating information along the edges. It is a different form to the
abovementioned three categories because it does not calculate any type of
subgraphs or global paths. Instead, the structure is utilised in an implicit
way. Every node is initialised with an importance score. Then iteratively,
each node updates its score through aggregating the scores of its neighbours.
Although these four categories are largely different from each other, there
are many approaches that combine them together, which are naturally put into
the fifth category — mixed approaches.

###  3.1. Subgraph Count Based Approaches

Subgraph count based measures are based on the number of a particular subgraph
or subgraphs. We further divide them into three subclasses, i.e., measures
defined on 1-hop neighbours, measures defined on k-hop neighbours/local paths,
and measures defined on multi-subgraphs. Figure 5 gives the detailed
categorisation. The colour of the block differentiates where the approach is
defined: grey is on the node-level, blue is on the link-level, and orange is
on the network-level.

Figure 5. Subgraph count based measures.

####  3.1.1. 1-hop neighbours

As the name implies, the calculations within this category only require the
immediate neighbourhood around a node or a link.

  * –

Degree centrality. Through calculating the number of nodes directly connected
to a node, the degree centrality is an easy and straightforward way to assess
the importance or influence of the node(Freeman, 1978). In order to render it
within the range of (0,1], it is often normalised by the size of the network
minus one. Mathematically, the normalised degree centrality of node $i$ is
defined as:

(1) $\Theta_{D}(i)=\frac{d_{i}}{n-1}.$

Despite being so simple, the degree centrality has been widely applied in
various domains. For example, in customer networks, the degree centrality is
used to find opinion leaders (Risselada et al., 2016), and in biomedical
semantic networks, it is effective in selecting crucial information for
summarising a disease treatment (Zhang et al., 2011). Some interesting
extensions of the degree centrality include the in-degree/out-degree
centrality in directed networks, the strength centrality and weighted strength
centrality in weighted networks (Candeloro et al., 2016) and the cross-layer
degree centrality in multi-layered networks (Bródka et al., 2011).

  *   * –

$h$-index/$g$-index. $h$-index is proposed to evaluate the impact of an
individual’s research output: A researcher has an index of $h$ if $h$ of his
or her papers have at least $h$ citations (Hirsch, 2005). It is then used as a
centrality measure in networks, and named as lobby index or $l$-index (Korn et
al., 2009). The $l$-index of a node is the largest integer $k$ such that the
node has at least $k$ neighbours with a degree of at least $k$. Egghe argued
that the influence of highly cited papers is underplayed in the $h$-index, and
proposed a $g$-index to overcome this disadvantage (Egghe, 2006). After
ranking a researcher’s papers according to their citations, the $g$-index is
defined as the highest rank $g$ such that the top $g$ papers together have at
least $g^{2}$ citations. From its definition, the $g$-index is always greater
than or equal to the $h$-index. To address the same issue, an $e$-index is
proposed to complement the $h$-index for excess citations(Zhang, 2009).
Recently, a local $h$-index centrality is proposed to identify influential
spreaders by simultaneously considering the $h$-index values of the node and
its neighbours (Liu et al., 2018): $\Theta_{LH}(i)=h(i)+\sum_{j\in Ni}h(j)$.

  *   * –

$k$-core (Kitsak et al., 2010). Instead of only calculating the number of
1-hop neighbours at one node (as in the degree centrality) or at both the node
and its neighbours (as in the $h$-index), a $k$-core or coreness takes into
account the number of neighbours at every node. Specifically, the $k$-core is
defined as a subgraph in which all nodes of a degree smaller than k have been
removed and the remaining nodes have a degree of at least $k$. A node located
in a higher $k$-core is deemed more important than a node in a lower $k$-core.
The $k$-core is calculated through the $k$-shell decomposition (Carmi et al.,
2007) which incrementally (from 1 to $k$) removes nodes with degree less than
$k$ (which in turn results in lowering the degree of remaining nodes) until no
more nodes need to be removed. Given that the degree centrality, the $h$-index
and the coreness are all based on the number of 1-hop neighbours, Lü et al.
further revealed their relationships through proposing the high-order
$h$-indices (Lü et al., 2016b). Bae et al. further propose a neighbourhood
coreness that considers both the degree of a node and the coreness of its
neighbours (Bae and Kim, 2014):

(2) $\Theta_{NC}(i)=\sum_{j\in N(i)}ks(j).$

The assumption is that a node having more connections to the neighbours
located in the core of the network is more influential.

  *   * –

$k$-truss/Common neighbours. A $k$-truss is a subgraph where every edge is
contained in at least $k-2$ triangles(Cohen, 2008; Wang and Cheng, 2012). It
is found through counting the number of common neighbours of a pair of nodes
that forms an edge, i.e., the number of triangles that the edge participates
in. The $k$-truss is also a $(k+1)$-core. Counting common neighbours around a
pair of nodes that have not formed an edge (a non-edge) is also a basic
approach in a link prediction task (Liben-Nowell and Kleinberg, 2007). There
is a big family of similar approaches based on the number of neighbours around
non-edges, such as the Adamic-Adar index, the resource allocation index, the
preferential attachment index, among others (Martínez et al., 2016). Notice
that both $k$-truss and Common Neighbours-like approaches are defined at the
link-level. The block colour is therefore blue in Figure 5.

####  3.1.2. local paths/k-hop neighbours

The group of methods in this category requires the calculation of local paths
or k-hop neighbours.

  * –

$k$-betweenness centrality (Borgatti and Everett, 2006). The $k$-betweenness
centrality or bounded-distance betweenness centrality is a variation of the
well-known betweenness centrality that limits the length of shortest paths to
a predefined value $k$. Specifically, the $k$-betweenness centrality of any
node $i$ is calculated by:

(3) $\Theta_{B_{k}}(i)=\sum_{s,t\in V}\frac{\sigma_{k}(s,t\mid
i)}{\sigma_{k}(s,t)},$

where $\sigma_{k}(s,t)$ is the number of shortest paths of length at most $k$
between a node pair $s$ and $t$, and $\sigma_{k}(s,t\mid i)$ is the number of
those paths that pass through node $i$. The reason for proposing a bounded-
distance betweenness centrality is that in some networks, long paths are
rarely used for the propagation of influence.

  *   * –

$\kappa$-path centrality (Alahakoon et al., 2011). Instead of limiting the
length of shortest paths between node pairs, the $\kappa$-path centrality
assumes that message traversals are along random simple paths of length at
most $k$, and proposes to calculate the sum of the probability that a message
originating from any possible node goes through the focal node. The
$\kappa$-path centrality of node $i$ is defined as:

(4) $\Theta_{P_{k}}(i)=\sum_{s\in V}\frac{\sigma_{k}(s\mid
i)}{\sigma_{k}(s)},$

where $s$ are all the possible source nodes, $\sigma_{k}(s\mid i)$ is the
number of $k$-paths originating from $s$ and passing through $i$, and
$\sigma_{k}(s)$ is the overall number of $k$-paths originating from $s$. In
order to calculate it more efficiently in large networks, a randomised
approximation algorithm called RA-$\kappa$path is also proposed. (Alahakoon et
al., 2011)

  *   * –

$\kappa$-path edge centrality (De Meo et al., 2012). Moving the $\kappa$-path
centrality definition to link-level, we then have the $\kappa$-path edge
centrality. The $k$-path edge centrality of any given edge $e$ is defined as
the sum of the frequency with which a message originated from any possible
node traverses $e$, assuming that the message traversals are along random
simple paths of length at most $k$:

(5) $\Theta_{P_{k}}(e)=\sum_{s\in V}\frac{\sigma_{k}(s\mid
e)}{\sigma_{k}(s)}.$

Quite similar to Equation 5, only here $\sigma_{s}^{\kappa}(e)$ is the number
of $\kappa$-paths originating from $s$ that go over the edge $e$. The original
$\kappa$-path edge centrality is very expensive to compute in large networks
with a big $k$, therefore two randomised approximations have been further
proposed, i.e., ERW-$\kappa$path and WERW-$\kappa$path (De Meo et al., 2012).

  *   * –

Local centrality (Chen et al., 2012). Local centrality, sometimes summarised
as LocalRank (Lü et al., 2016a) utilises the information within a node’s 4-hop
neighbourhood. Concretely, the local centrality of node $i$ is defined as:

(6) $\displaystyle\Theta_{LR}(i)=\sum_{j\in N(i)}Q(j),$ $\displaystyle
Q(j)=\sum_{k\in N(j)}R(k),$

where $N(i)$ and $N(j)$ are the set of 1-hop neighbours of node $i$ and $j$,
and $R(k)$ is the number of both 1-hop and 2-hop neighbours of node $k$. It is
said to perform better than betweenness centrality and almost as well as
closeness centrality to identify influential nodes under the setting of a SIR
model, with only a time complexity of $O(n\langle k\rangle^{2})$.

  *   * –

Collective influence (Morone and Makse, 2015). Collective influence (CI) is
another interesting method that takes higher-order neighbourhoods into
consideration. The idea is to find those nodes that will cause the biggest
drop in the energy function when removed. Specifically, the level $k$
collective influence of a node $i$ is defined as:

(7) $\Theta_{{CI}_{k}}(i)=(d_{i}-1)\sum_{j\in N_{k}(i)}(d_{j}-1),$

where $N_{k}(i)$ is $k$-hop neighbours of a node $i$. After applying the
collective influence score, the paper finds that a large number of previously
neglected weakly connected nodes (nodes of lower degree) emerge among the
optimal influencers (Morone and Makse, 2015).

####  3.1.3. Multi-subgraphs

Methods of this category involve the count of multiple different subgraphs.
They can be at the node level, the link level or the network level.

  * –

Graphlet degree (Milenković and Pržulj, 2008). As discussed in Section 2.2,
graphlets are nonisomorphic induced subgraphs around a node. Graphlet degree
is a 73-dimensional vector formed by all different orbits in the subgraphs of
size 2-5 nodes. The paper discovers that in PPI networks, nodes grouped
together under this measure belong to the same protein complexes, perform the
same biological functions and have the same tissue expressions. Some
interesting extensions of graphlets include the dynamic graphlets for temporal
networks(Hulovatyy et al., 2015), the directed graphlets for directed
networks(Aparicio et al., 2016), the coloured graphlets for heterogeneous
networks(Gu et al., 2018a), and the typed-edge graphlets for edge-labelled
networks (Jia et al., 2022).

  *   * –

Subgraph centrality (Estrada and Rodriguez-Velazquez, 2005). Subgraph
centrality focuses on subgraphs captured by closed walks of different lengths
around a given node. For example, when the walk length is $4$, three types of
subgraphs are covered, which are $2$-cliques, $2$-paths, and $4$-cycles. The
number of closed walks of length $k$ around node $i$ can be calculated from
the $i$th diagonal entry of the $k$th power of the adjacency matrix. When the
walk becomes unbounded, the subgraph centrality of node $i$ is calculated by:

(8) $\Theta_{S}(i)=\sum_{k=0}^{\infty}\frac{\mu_{k}(i)}{k!},$

where $\mu_{k}(i)=\left(\mathbf{A}^{k}\right)_{ii}$. It is shown to be more
discriminative than many popular centrality measures such as the degree
centrality, the betweenness and the eigenvector centrality.

  *   * –

Local path index (Lü et al., 2009). Extended from common neighbours, the local
path index counts both the number of $2$-paths and $3$-paths between a pair of
nodes. The approach is proposed for link prediction, and therefore focuses on
non-connected node pairs. Concretely, the local path index of a node pair $i$
and $j$ is defined as:

(9) $\Theta_{LP}(i,j)=A_{ij}^{2}+\epsilon A_{ij}^{3},$

where $\epsilon$ is a weigh parameter for $3$-paths. The paper finds out that
the local path index remarkably outperforms common neighbours and can reach a
competitive accuracy to the Katz index where all paths are considered. Some
other works compare 3-paths approaches against 2-paths approaches in link
prediction and find out that $3$-path approaches perform better in PPI
networks and food webs (Muscoloni et al., 2018; Kovács et al., 2019; Zhou et
al., 2021).

  *   * –

Potential theory/Quad motifs index. The potential theory aims to predict links
in directed networks. By counting the numbers of $4$ different directed
2-paths and $8$ different directed 3-paths around a pair of nodes, the paper
finds out that a link has a higher probability of appearing if it could
generate more bi-fan subgraphs (Zhang et al., 2013a). Very similar to the idea
of potential theory, the quad motifs index proposes to count particularly
three types of directed open-quadriad (3-paths) subgraphs: two of them are the
bases for bi-parallel subgraphs and the other one is for bi-fan (Hu et al.,
2019). Specifically, the quad motifs index of a pair of nodes $i$ and $j$ is
defined as:

(10) $\Theta_{QM}(i,j)=\alpha\times
s_{F}(i,j)+\frac{(1-\alpha)}{2}\left(s_{P1}(i,j)+s_{P2}(i,j)\right),$

where $s_{F}(i,j)$ is the contribution from the bi-fan base while
$s_{P1}(i,j)$ and $s_{P2}(i,j)$ are the contributions from two bi-parallel
bases. Together with the local path index, it is interesting to see that
$3$-path subgraphs are of particular importance in link prediction.

  *   * –

Triad significance profile/Subgraph ratio profile (Milo et al., 2004).
Extended from network motifs (Milo et al., 2002), the triad significance
profile (TSP) is constructed from normalised $Z$ scores of $13$ different
directed 3-node subgraphs.

(11) $\displaystyle TSP=\\{SP_{1},SP_{2},...,SP_{13}\\},$
$\displaystyle\mathrm{SP}_{i}=\nicefrac{{Z_{i}}}{{\left(\Sigma
Z_{i}^{2}\right)^{1/2}}}.$

$Z_{i}$ is in turn calculated from comparing with an ensemble of randomised
networks with the same degree sequence, i.e.,
$Z_{i}=\left(N_{i}^{\mathrm{real}}-\bar{N}_{i}^{\mathrm{rand}}\right)/\operatorname{std}\left(N_{i}^{\text{rand
}}\right)$. Subgraph ratio profile (SRP), on the other hand, is built from $6$
undirected $4$-node subgraphs ($G_{3}$ to $G_{8}$ in Figure 3) :

(12) $\displaystyle SRP=\\{SRP_{1},SRP_{2},...,SRP_{6}\\},$
$\displaystyle\mathrm{SRP}_{i}=\nicefrac{{\Delta_{i}}}{{\left(\Sigma\Delta_{i}{}^{2}\right)^{1/2}}}.$

Unlike TSP, SRP uses the abundance of each subgraph relative to random
networks, i.e., $\Delta_{i}=\frac{N\mathrm{real}_{i}-\left\langle
N\mathrm{rand}_{i}\right\rangle}{N\mathrm{real}_{i}+\left\langle
N\operatorname{rand}_{i}\right\rangle+\varepsilon}$. Previously seemingly
unrelated networks are found to belong to several superfamilies with very
similar significance profiles. Notice also that these two approaches are
defined on network-level, not on node or link-level as we have seen often.

###  3.2. Subgraph Formation Based Approaches

Subgraph formation based measures view a subgraph being built from another
less complex subgraph, i.e., with one link, multiple links, or one node less.
We further divide them into three categories according to the size of the
subgraph, 3-node, 4-node and 4-node plus (Figure 6). Most of these approaches
are defined at node-level, except that the edge clustering coefficient is at
link-level and the interest clustering coefficient is at network-level.

Figure 6. Subgraph formation based measures.

####  3.2.1. 3-node subgraph

The 3-node subgraph is the simplest yet most important category in the
taxonomy.

  * –

Clustering coefficient (Watts and Strogatz, 1998). The clustering coefficient
is the first and most influential measure in this category. It measures the
extent to which the neighbours of a node connect to each other. From a
structural formation perspective, it measures the formation of triangles upon
open-triads (also called wedges). Specifically, the clustering coefficient of
node $i$ is defined as the ratio between the number of triangles containing
node $i$ (denoted $T(i)$) and the number of open triads (denoted $OT(i)$):

(13) $\mathcal{C}_{C}(i)=\frac{T(i)}{OT(i)}=\frac{\frac{1}{2}\sum_{j\in
N(i)}|N(i)\cap N(j)|}{\frac{1}{2}d_{i}\left(d_{i}-1\right)}.$

Due to its significance and simplicity in definition, the clustering
coefficient has been widely applied in studying complex networks (Pavlopoulos
et al., 2011; Brust et al., 2012; Said et al., 2018) and extended to directed
networks (Fagiolo, 2007; Ahnert and Fink, 2008), weighted networks (Barrat et
al., 2004; Onnela et al., 2005; Zhang and Horvath, 2005) and signed networks
(Kunegis et al., 2009; Costantini and Perugini, 2014).

  *   * –

Closure coefficient (Yin et al., 2019). The closure coefficient measures the
formation of triangles from a new perspective, i.e., with the focal node
located at the end of an open-triad. Different from the ordinary centre node
perspective in clustering coefficient (orbit 2 of $G_{1}$ in Figure 3, denoted
as $G_{1}^{(2)}$), the focal node in closure coefficient serves as the end
node of an open triad (orbit type $G_{1}^{(1)}$). The closure coefficient of
node $i$ is calculated as the fraction of open triads ($OT_{E}(i)$), where $i$
serves as the end node, that actually forms triangles:

(14) $\mathcal{C}_{E}(i)=\frac{2\cdot T(i)}{OT_{E}(i)}=\frac{\sum_{j\in
N(i)}|N(i)\cap N(j)|}{\sum_{j\in N(i)}(d_{j}-1)}.$

Despite this subtle difference in definition, the closure coefficient has very
different properties compared to the clustering coefficient. It has been
extended to directed networks (Yin et al., 2020; Jia et al., 2020) and
weighted networks (Jia et al., 2021b).

  *   * –

Edge clustering coefficient (Wang et al., 2011). Defined on link-level, the
edge clustering coefficient (ECC) evaluates to what extent nodes cluster
around the focal edge. From a structure formation view, it measures the
formation of triangles upon this link. The edge clustering coefficient of an
edge $e_{ij}$ is defined as:

(15) $\mathcal{C}_{e}(i,j)=\frac{T(i,j)}{\min\left(d_{i}-1,d_{j}-1\right)},$

where $T(i,j)$ is the number of triangles that $e_{ij}$ participates, and
$\min\left(d_{i}-1,d_{j}-1\right)$ is the number of triangles that edge could
possibly form. Based on ECC, a node centrality measure is then defined as the
sum of the edge clustering coefficients of all edges connected to it, i.e.,
$\mathcal{C}_{N}(i)=\sum_{j\in N_{i}}\mathcal{C}_{e}(i,j)$. This measure has
been proven to be more efficient for identifying essential proteins than many
other centrality measures.

  *   * –

Weighted degree centrality (Tang et al., 2013). Weighted degree centrality
(WDC) is also proposed to identify essential proteins. Although this name
seems to suggest a close relation to the degree centrality, it is in fact an
extension of the edge clustering coefficient. This approach is different in
that it takes into account not only the PPI graph data but also the gene
expression data. Specifically, a weight of an interaction is calculated as:

(16) $\mathcal{C}_{w}(i,j)=\mathcal{C}_{e}(i,j)+r(i^{\prime},j^{\prime}),$

where $\mathcal{C}_{e}(i,j)$ is the edge clustering coefficient from the graph
data, and $r(i^{\prime},j^{\prime})$ is the Pearson correlation coefficient
calculated from the gene expression data. Similarly, the weighted degree
centrality of a node is then defined as: $\Theta_{W}(i)=\sum_{j\in
N_{i}}\mathcal{C}_{w}(i,j)$. This approach essentially integrates node
features when analysing networks.

####  3.2.2. 4-node subgraph

4-node subgraphs are much more complicated than the 3-node subgraphs. There
are in total 6 different subgraphs and 11 different orbits in 4-node subgraphs
(Figure 3).

  * –

Quadrangle coefficients (Jia et al., 2021c). Many real networks (such as PPI
networks, neural networks and food webs) are naturally rich in quadrangles.
Quadrangle coefficients, or i-quad coefficient and o-quad coefficient, are
thus proposed to measure the formation of quadrangles upon open-quadriads
(3-paths). As there are two orbits in an open-quadriad ($G_{3}^{(5)}$ and
$G_{3}^{(4)}$), i-quad coefficient has the focal node at $G_{3}^{(5)}$ while
o-quad coefficient has the focal node at $G_{3}^{(4)}$. Specifically, the
quadrangle coefficients of node $i$ are defined as:

(17) $\displaystyle\mathcal{C}_{I}(i)=\frac{2Q(i)}{OQI(i)},$
$\displaystyle\mathcal{C}_{O}(i)=\frac{2Q(i)}{OQO(i)},$

where $Q(i)$ is the number of quadrangles; $OQI(i)$ and $OQI(i)$ are number of
open-quadriads with $i$ as the inner node and outer node respectively. They
are found to be more efficient than 3-node measures in classifying networks
and predicting links.

  *   * –

Grid coefficients (Caldarelli et al., 2004). Grid coefficients, including the
primary grid coefficient and the secondary grid coefficient, also aim to
measure the formation of 4-cycles. The primary grid coefficient measures the
formation of primary quadrilaterals upon a node and three of its 1-hop
neighbours, which is essentially the formation of chordal cycles ($G_{7}$)
from tailed-triangles (orbit $G_{6}^{(11)}$). Concretely, the primary grid
coefficient of node $i$ is defined as:

(18) $\mathcal{C}_{G_{p}}(i)=\frac{Q_{p}(i)}{d_{i}(d_{i}-1)(d_{i}-2)/2},$

where $G_{p}(i)$ is the number of chordal-cycles containing $i$ and the
denominator is the number of possible chordal-cycles built from a node and its
three neighbours. The secondary coefficient measures the formation of
secondary quadrilaterals from a node, two of its 1-hop neighbours and one of
its 2-hop neighbours:

(19) $\mathcal{C}_{G_{s}}(i)=\frac{Q_{s}(i)}{d_{i,2nd}d_{i}(d_{i}-1)/2}.$

Notice, however, in this definition the 2-hop neighbour could be at orbit
$G_{3}^{(4)}$ or at orbit $G_{10}^{(20)}$. The latter essentially involves 5
nodes in total.

  *   * –

Square clustering coefficient. As triangles (3-cycles) are absent in bipartite
networks, the square clustering coefficient is proposed to measure the
formation of 4-cycles in the context of bipartite networks (Lind et al.,
2005). What is unusual about this approach is that it views 4-cycles being
built from node overlapping instead of node connection. Specifically, the
square coefficient of node $i$, with a pair of its neighbours $m$ and $n$, is
calculated as:

(20)
$\mathcal{C}_{S}(i|m,n)=\frac{Q_{imn}}{(d_{m}-\eta_{imn})(d_{n}-\eta_{imn})+Q_{imn}},$

where $Q_{imn}$ is the number of 4-cycles containing nodes $i$, $m$, $n$; and
$\eta_{imn}=1+q_{imn}$ if $m$ and $n$ are not connected (or
$\eta_{imn}=2+q_{imn}$ if $m$ and $n$ are connected). Zhang et al. (Zhang et
al., 2008) later proposed a modified version of square clustering coefficient:
$\mathcal{{C}}_{S_{Z}}(i|m,n)=\frac{Q_{imn}}{(d_{m}-\eta_{imn})+(d_{n}-\eta_{imn})+Q_{imn}}$.
With this minor change at the denominator, 4-cycles are now built from
connecting nodes. It is mainly applied in community detection.

  *   * –

Interest clustering coefficient (Trolliet et al., 2020). An interest
clustering coefficient is introduced to measure the clustering of interest
links in directed social networks. It argues that the best way of defining a
relationship between two individuals is through common interests, i.e., two
individuals having links towards a common neighbour will have a higher chance
to follow other common neighbours. From a structural view, the interest
clustering coefficient essentially measures the formation of bi-fan subgraphs
(Table 1) upon open bi-fans:

(21) $\mathcal{C}_{I}=\frac{4\cdot\\#\;\mbox{bifan}}{\\#\;\mbox{open-bifan}}.$

Note that this metric is defined at network-level. The paper finds out that
the interest clustering coefficient of Twitter is higher than the traditional
directed clustering coefficient, and further proves its usage in a link
recommendation task.

Table 2. Metrics for 3-node and 4-node subgraph formation. | 3-node/4-node
---
subgraph formation
Undirected networks | Directed networks | Weighted networks
| clustering coef.(Watts and Strogatz, 1998) | directed clustering coef.(Fagiolo, 2007; Ahnert and Fink, 2008) |  | wgted. clustering coef.(Barrat et al., 2004; Onnela et al., 2005; Zhang and Horvath, 2005)
---
wgted. signed clustering coef.(Kunegis et al., 2009; Costantini and Perugini,
2014)
wgted. directed clustering coef.(Fagiolo, 2007)
| closure coef.(Yin et al., 2019) | directed closure coef. (Yin et al., 2020; Jia et al., 2020) | weighted closure coef. (Jia et al., 2021b)
| edge clustering coef.(Wang et al., 2011) | reNTE-1tNTE-1lNTE-1r  | reNTE-2tNTE-2lNTE-2r
|  | higher-order clustering
---
coef. (Fronczak)(Fronczak et al., 2002)
higher-order clustering
coef. (Abdo)(Abdo and de Moura, 2006)
None | None
|  | square clustering coef.
---
(Lind (Lind et al., 2005), Zhang (Zhang et al., 2008))
i-quad coef. (Jia et al., 2021c)
primary grid coef. (Caldarelli et al., 2004)
None | None
| o-quad coef. (Jia et al., 2021c) | None | weighted o-quad coef. (Jia et al., 2021c)
|  | higher-order clustering
---
coef. (Yin)(Yin et al., 2018)
None | None
|  | higher-order closure
---
coef. (Yin)(Yin et al., 2019)
None | None

pNTE-2bpNTE-2b

####  3.2.3. Beyond 4-node subgraph

Some approaches are introduced with a variable subgraph size. In actual usage,
however, due to high complexity, they seldom go beyond the size of 6 nodes.

  * –

Higher-order clustering coefficientsF (Fronczak et al., 2002). Fronczak et al.
propose the higher clustering coefficients to evaluate the probabilities that
the shortest paths between any two neighbours of node $i$ equals $k$, when all
paths passing through node $i$ are neglected. Particularly, a clustering
coefficient of order $k$ for node $i$ is calculated as:

(22) $\mathcal{C}_{H_{F}}(i\mid k)=\frac{2E(i\mid k)}{d_{i}(d_{i}-1)},$

where $E(i\mid k)$ denotes the number of shortest paths of length $k$ between
$i$’s neighbours. When $k$ equals 1, it degrades to the standard clustering
coefficient, and when $k$ equals 2, it measures the formation of 4-cycles.
Note that each pair of neighbours could have multiple shortest paths of the
same length, and only one of them should be counted so that the value of
higher-order clustering coefficients is bounded by 1.

  *   * –

Higher-order clustering coefficientY (Yin et al., 2018). The higher-order
clustering coefficient proposed by Yin et al. is another generalisation of the
traditional clustering coefficient. It aims to measure the formation of
higher-order cliques. Specifically, a $k$th-order clustering coefficient of
node $i$ is defined as the probability that a $k$-clique plus an edge incident
to $i$ (termed as $k$-wedge) forms a $(k+1)$-clique:

(23) $\mathcal{C}_{H_{Y}}(i\mid
k)=\frac{k\cdot|C_{k+1}(i)|}{|W_{k}(i)|}=\frac{k\cdot|C_{k+1}(i)|}{(d_{i}-k+1)|C_{k}(i)|},$

where $C_{k+1}(i)$ is the set of $(k+1)$-cliques containing node $i$, and
$W_{k}(i)$ is the set of $k$-wedges with $i$ as the centre node. The
properties of higher-order clustering coefficient in random graph and the
small-world model have also been thoroughly investigated (Yin et al., 2018).

  *   * –

Higher-order closure coefficient (Yin et al., 2019). Higher-order closure
coefficient measures the formation of higher-order cliques from a different
perspective, i.e., the focal node being the end-node of a $k$-wedge (instead
of the centre-node). The $k$th-order closure coefficient of node $i$ is thus
defined as the fraction of end-node based $k$-wedges that are closed (a closed
$k$-wedge is a $(k+1)$-clique):

(24) $\mathcal{C}_{H_{E}}(i\mid
k)=\frac{k\cdot|C_{k+1}(i)|}{|W_{k}^{\prime}(i)|}=\frac{k\cdot|C_{k+1}(i)|}{\sum_{j\in
N(i)}\left[C_{k}(j)-(k-1)C_{k}(i)\right]},$

where $C_{k+1}(i)$ is the set of $(k+1)$-cliques containing node $i$, and
$W_{k}(i)^{\prime}$ is the set of $k$-wedges with $i$ as the end-node. Higher-
order closure coefficient is proven to be useful in finding seeds for
personalised PageRank community detection.

An illustrative summary for most abovementioned approaches is given in Table
2.

###  3.3. Global Path Based Approaches

Global path based approaches require structural information across the whole
network in the form of unbounded paths between nodes. One set of methods is
based on the paths from one node to all other nodes, such as the well known
closeness centrality and Katz index; another set of methods is based on paths
between all node pairs, represented by the betweenness centrality (Figure 7).

Figure 7. Global path based measures.

####  3.3.1. One-to-all

The approaches of this type involve the paths from one node to all other
nodes. They are also referred to as radial measures.

  * –

Closeness centrality (Freeman, 1978). Being one of the most classic centrality
measures, closeness centrality is defined as the reciprocal of the average
shortest path distance from a focal node $i$ to all other nodes:

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

Obviously, the original definition is not suitable for graphs with more than
one connected component. To address this problem, a modified version of the
closeness centrality is defined as (Wasserman et al., 1994):

(26)
$\Theta_{C^{\prime}}(i)=\frac{n-1}{|V|-1}\frac{n-1}{\sum_{j=1}^{n-1}d(i,j)},$

where $n$ is the number of nodes in one connected component. Due to its
intuitiveness in definition, the closeness centrality keeps being applied and
extended in various fields. Some recent works include the neighbourhood
closeness centrality in predicting essential proteins (Li et al., 2018b), and
the backward/forward closeness in studying global value chains (Guan et al.,
2020).

  *   * –

Katz index (Katz, 1953). Unlike the closeness centrality that focuses on
shortest paths, Katz centrality of a node considers all paths reaching other
nodes with longer paths contributing less. Concretely, the Katz centrality of
a node $i$ is calculated as:

(27) $\Theta_{K}(i)=\sum_{j}\sum_{k=1}^{\infty}\beta^{k}\mathbf{A}_{ij}^{k},$

where $k$ is a path length and $\beta$ is an attenuation parameter in a range
$(0,\frac{1}{\lambda})$, $\lambda$ being the largest eigenvalue of
$\mathbf{A}$. Further, the overall matrix
$\mathbf{M}=\sum_{k=1}^{\infty}(\beta\cdot\mathbf{A})^{k}$ is an weighted
ensemble of all paths. Thus, $\mathbf{M}_{ij}$ represents the weighted sum of
paths from $i$ to $j$ in all possible hops. Note that this definition is
naturally suitable in directed networks and a recent work proposes to generate
node embedding of a directed graph by performing a singular value
decomposition on the Katz index matrix (Ou et al., 2016).

  *   * –

Gravity model (Li et al., 2019) /Gravity centrality (Ma et al., 2016) .
Inspired by Newton’s gravity law formula, a gravity model is proposed by
viewing the degree of a node as its mass and the shortest path length between
two nodes as their distance:

(28) $\Theta_{G}(i)=\sum_{j\in V,j\neq i}\frac{d_{i}\cdot d_{j}}{d(i,j)^{2}}.$

In order to make it easier to compute in large networks, a modified version
limits the radius from the entire network to a certain length. Adopting a
similar idea, the gravity centrality is introduced by regarding the coreness
of a node as its mass, and the shortest path length between nodes as their
distance:

(29) $\Theta_{G}^{\prime}(i)=\sum_{j\in N_{k}(i)}\frac{ks(i)\cdot
ks(j)}{d(i,j)^{2}},$

where $N_{k}(i)$ is the neighbourhood of node $i$ within $k$-hops, and $ks(i)$
is the coreness of node $i$. The two approaches are shown to be effective in
identifying influential spreaders through analyses of the SIR model on real
networks.

  *   * –

Heatmap centrality (Durón, 2020). Heatmap centrality measures the influence of
a node by comparing the farness of the node with the average farness of its
neighbours. Farness, the reciprocal of closeness, is defined as the sum of the
lengths of shortest paths from a node to all other nodes, i.e.,
$f(i)=\sum_{j\in V,j\neq i}d(i,j)$. Therefore, the heatmap centrality of node
$i$ is quantified as:

(30) $\Theta_{HM}(i)=f(i)-\frac{\sum_{j\in N(i)}f(j)}{|N(i)|}.$

The intuition of this metric is that if a node has a smaller farness than its
neighbours, the probability of information passing through it is higher. Note
that according to heatmap centrality, a top-ranked node of influence should
have the most negative value. Although the definition of heatmap centrality is
more related to the closeness centrality, it is revealed that it is highly
correlated with the betweenness centrality.

  *   * –

Reaching centrality (Mones et al., 2012). Reaching centrality aims to rank the
influence of a node in directed networks. Intuitively, the reaching centrality
of node $i$ is quantified as the proportion of nodes that can be reached by
the node via outgoing edges, i.e., the number of nodes with a directed
distance from $i$, divided by $|V|-1$. Further, a global reaching centrality
is then defined as:

(31) $GRC=\frac{\sum_{i\in V}[\Theta_{R}^{max}-\Theta_{R}(i)]}{|V|-1},$

where $\Theta_{R}^{max}$ is the largest reaching centrality of all nodes. The
meaning of $GRC$ is the difference between the maximum reaching centrality and
the average reaching centrality. Global reaching centrality is used as a
hierarchy measure for directed networks and is shown to be capable of
capturing the degree of hierarchy in both synthetic and real networks.

####  3.3.2. All-to-all

The approaches here involve the count of paths between all node pairs, and
among them the ones that pass through a focal node or edge. They are also
referred to as medial measures.

  * –

Betweenness centrality (Freeman, 1977). Betweenness centrality, or more
precisely, the shortest-path betweenness centrality is one of the best-known
centrality measures. The betweenness centrality of node $i$ is quantified as
the sum of the fraction of all-pairs shortest paths going through $i$:

(32) $\Theta_{B}(i)=\sum_{s,t\in V}\frac{\sigma(s,t\mid i)}{\sigma(s,t)},$

where $\sigma(s,t\mid i)$ is the number of shortest paths between node pair
$s$ and $t$ that pass through node $i$, and $\sigma(s,t)$ is the number of all
shortest paths between $s$ and $t$. It is often normalised by
$\frac{(|V|-1)(|V|-2)}{2}$, in order to be compared in different networks. The
betweenness centrality has also been generalised to directed networks(White
and Borgatti, 1994) and weighted networks (Opsahl et al., 2010).

  *   * –

Edge betweenness centrality (Girvan and Newman, 2002). With a small
modification on the original betweenness centrality, Girvan and Newman propose
an edge betweenness centrality in order to detect a community structure in
complex networks. The edge betweenness centrality of an edge $e$ is quantified
as the sum of the fraction of all-pairs shortest paths passing through $e$:

(33) $\Theta_{B}(e)=\sum_{s,t\in V}\frac{\sigma(s,t\mid e)}{\sigma(s,t)},$

According to the definition, edges which lie between communities will have
large edge betweenness. Therefore, the underlying communities of the network
would be uncovered by removing edges of high edge betweenness centrality. It
has been widely applied in a community detection task, and some recent
applications include the study of anti-vaccination sentiment on Facebook
(Hoffman et al., 2019) and the analysis of microbial diversity in marine
sediment (Hoshino et al., 2020).

  *   * –

Flow betweenness centrality (Freeman et al., 1991)/ Communicability
betweenness centrality (Estrada et al., 2009). A major limitation of the
betweenness centrality is that it exclusively focuses on the shortest paths.
In real situations, however, information often takes a more circuitous path
randomly or intentionally (Stephenson and Zelen, 1989). The flow betweenness
addresses this issue by considering all paths between nodes. Specifically, the
flow betweenness centrality of a node $i$ is defined as:

(34) $\Theta_{F}(i)=\sum_{s,t\in V}\frac{\phi(s,t\mid i)}{\phi(s,t)},$

where $\phi(s,t\mid i)$ is the maximum flow between $s$ and $t$ that passes
through $i$, and $\phi(s,t)$ is the total flow between $s$ and $t$. The
maximum flow is in turn calculated by the minimum cut capacity (Ford and
Fulkerson, 2015). Having established the notion of capacity on links, the flow
betweenness centrality is naturally suitable for weighted networks. Instead of
treating each path equally, the communicability betweenness centrality
proposes to reduce the weight for longer paths:

(35) $\frac{2}{(n-1)(n-2)}\sum_{s,t\in
V}\frac{\sum_{k=0}^{\infty}\frac{1}{k!}\mu^{k}(s,t\mid
i)}{\sum_{k=0}^{\infty}\frac{1}{k!}\mu^{k}(s,t)},$

where $\mu^{k}(s,t\mid i)$ is the number of paths between $s$ and $t$ passing
$i$ with length $k$, and $\mu^{k}(s,t)$ is the number of paths between $s$ and
$t$ with a length $k$.

  *   * –

Random-walk betweenness centrality (Newman, 2005). A random-walk betweenness
centrality, also known as a current-flow betweenness centrality, is another
popular variant of the betweenness centrality. It models information spreading
in a network analogous to an electrical current flow in a circuit. Concretely,
the current-flow betweenness centrality of node $i$ is defined as the amount
of current flowing through $i$, averaged over all node pairs:

(36) $\Theta_{CF}(i)=\frac{\sum_{s,t\in V}I(s,t\mid i)}{(1/2)n(n-1)},$

where $I(s,t\mid i)$ is the current flowing from $s$ to $t$ that passes $i$.
The paper then proves that a message spreading along random walks is
equivalent to the above definition.

###  3.4. Message Passing Based Approaches

The above mentioned approaches depend solely on the topological information of
a network, such as the number of particular subgraphs, the ratio between two
subgraphs, the length of shortest paths, or the number of paths. Message
passing based approaches further consider the information contained in each
node. From a microscopic point of view, in one iteration, only local
information is needed at each node. It is worth noticing that the popular
graph convolutional network is also based on this idea, i.e, iteratively
gathering information from nearby nodes.

Figure 8. Message passing based approaches.

  * –

Eigenvector centrality (Bonacich, 1987). The eigenvector centrality is another
classic centrality measure. The idea is that a node’s centrality depends on
the centralities of its neighbours:

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

where $c$ is a normalisation constant. The equation is recursive and computed
by starting with a set of initial influence scores and iterating the
computation until it converges. In a vectorised form, i.e.,
$\vec{x}=c\textbf{A}\vec{x}$, $\vec{x}$ is found to converge to the dominant
eigenvector of $\mathbf{A}$ and $c$ converges to the reciprocal of the
dominant eigenvalue of $\mathbf{A}$. The eigenvector centrality has some
problems in very sparse networks, i.e., the leading eigenvector is localised
around nodes of the highest degree and diminishes the effectiveness of
quantifying nodes’ importance (Krivelevich and Sudakov, 2003).

  *   * –

Nonbacktracking centrality (Martin et al., 2014). The nonbacktracking
centrality is proposed to address the above mentioned localisation issue. The
same as in the eigenvector centrality, a node’s centrality is the sum of its
neighbours’ centralities, but now the neighbours’ centralities are calculated
without the influence of this node. This is achieved by using the
nonbacktracking matrix (Hashimoto, 1989). The nonbacktracking matrix
$\mathbf{B}$, is a $2m\times 2m$ matrix, defined on the directed edges of the
graph (undirected edges are converted to bidirectional edges), and elements
$\mathbf{B}_{i\rightarrow j,k\rightarrow l}=\delta_{i,l}(1-\delta_{jk})$,
where $\delta$ is the Kronecker delta. Then, $e_{j\rightarrow i}$ of the
leading eigenvector of $\mathbf{B}$ gives the centrality of node $j$ ignoring
the contribution of $i$. Finally, the nonbacktracking centrality of node $i$
is $x(i)=\sum_{j}\mathbf{A}_{ji}e_{j\rightarrow i}$. The eigenvalues of the
nonbacktracking matrix are also found to be useful in a community detection
task (Krzakala et al., 2013).

  *   * –

Alpha centrality (Bonacich and Lloyd, 2001). When the eigenvector centrality
is applied in directed networks, a node’s centrality is determined by those
who pointed at it. Thus, the vector form becomes:
$\vec{x}=\frac{1}{\lambda}\textbf{A}^{T}\vec{x}$. The problem is that nodes
with no incoming edges would have zero centrality value. The alpha centrality
proposes to solve this problem by taking into account the ”external status
characteristics”. The equation then becomes:

(38) $\vec{x}=\alpha\textbf{A}^{T}\vec{x}+\vec{e},$

where $\vec{e}$ is a vector of the exogenous sources of characteristics and
$\alpha$ is a parameter which reflects the relative importance of a
topological structure versus exogenous factors.

  *   * –

PageRank (Brin and Page, 1998). PageRank, a popular variation of the
eigenvector centrality, is proposed to rank the importance of web pages. Web
pages and the links among them are modelled as a directed network, and a page
should have a high rank if the sum of the ranks of pages that point to it is
high. Specifically, the rank of page $i$ is calculated as:

(39) $r(i)=c\sum_{j\in N_{i}^{in}}\frac{r(j)}{d_{j}^{out}},$

where $N_{i}^{in}$ is the set of pages pointing to $i$ ($i$’s in-neighbours),
and $d_{j}^{out}$ is out-degree of page $j$. In order to deal with the rank
sink problem, where several pages form a loop without other outgoing links, a
source of the rank is introduced over all pages (also viewed as a random
jumping factor), denoted as a vector $\vec{e}$. Therefore, the rank of page
$i$ becomes: $r(i)=c(\sum_{j\in N_{i}^{in}}\frac{r(j)}{d_{j}^{out}}+e(i))$,
and the corresponding vector form is
$\vec{r}=c(\mathbf{A}^{T}+\vec{e}\times\mathbf{1})\vec{r}$. The PageRank has
also been extended to weighted networks (Xing and Ghorbani, 2004), on
nonbacktracking matrix (Aleja et al., 2019), and applied to many different
areas (Gleich, 2015).

  *   * –

HITS (Kleinberg et al., 1998). Unlike the PageRank which focuses on pages
having many incoming links, HITS, abbreviated from a hyperlink induced topic
search, proposes to distinguish two roles in the hyperlink structure, i.e.,
authorities and hubs. Authorities are reliable information sources, and hubs
are the websites pointing to them. Based on the intuition that an authority
should be pointed to by hubs and a hub should point to authorities, an
authority weight and a hub weight of page $i$ are thus defined in a mutually
dependent manner:

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

The corresponding vector forms are: $\vec{a}=\mathbf{A}^{T}\vec{h}$, and
$\vec{h}=\mathbf{A}\vec{a}$. $\vec{a}$ and $\vec{h}$ are updated iteratively,
and it is proven that $\vec{a}$ converges to the leading eigenvector of
$\mathbf{A}^{T}\mathbf{A}$, and $\vec{h}$ converges to the leading eigenvector
of $\mathbf{A}\mathbf{A}^{T}$. Based on HITS, ARC (Automatic Resource
Compilation) later proposes to incorporate textual information around the link
by assigning each link a weight (Chakrabarti et al., 1998), and Co-HITS
proposes to extend the idea to bipartite networks (Deng et al., 2009).

  *   * –

LeaderRank (Lü et al., 2011). In order to solve the above mentioned rank sink
problem, the LeaderRank proposes to add a ground node that connects to other
nodes via bidirectional links. In the beginning, each node other than the
ground node is initialised by one unit of score, and the ground node is
initialised to zero. Then, the same as the PageRank, at each iteration, the
score of node $i$ is calculated as: $s(i)^{(t)}=c\sum_{j\in
N_{i}^{in}}\frac{s(j)^{(t-1)}}{d_{j}^{out}}$. After the scores of all nodes
reach a steady state, the score of the ground node will be distributed evenly
to other nodes, and thus the final score of node $i$ is:

(41) $s(i)=s(i)^{c}+\frac{s(g)^{c}}{|V|},$

where $s(i)^{c}$ is the steady score of node $i$, and $s(g)^{c}$ is the steady
score of the ground node. A major advantage of the LeaderRank is that it has
no additional parameter that needs to be optimised. Some interesting
extensions of the LeaderRank include the weighted LeaderRank that assigns
degree-dependent weights onto links associated with the ground node (Li et
al., 2014) and the adaptive LeaderRank that introduces H-index into the
weighted mechanism (Xu and Wang, 2017).

  *

###  3.5. Hybrid Approaches

The methods in the fifth and final category are combinations of previously
introduced approaches.

Figure 9. Hybrid Approaches.

  * –

ClusterRank (Chen et al., 2013). Previous studies have shown that a large
clustering coefficient may slow the spreading process of disease in the entire
network (Eguiluz and Klemm, 2002; Zhou et al., 2005). A ClusterRank thus
proposes to consider not only the number of a node’s neighbours, but also the
negative effect of local clustering when identifying influential nodes. The
ClusterRank score of node $i$ is defined as:

(42) $\Theta_{CR}(i)=f(c_{i})\sum_{j\in N_{i}^{out}}(d_{j}^{out}+1),$

where $c_{i}=\frac{\sum_{j\in N_{i}^{out}}|N^{out}(i)\cap
N(j)|}{d_{i}^{out}(d_{i}^{out}-1)}$ is a modified version of clustering
coefficient in directed networks. $f(c_{i})$ is a function that is negatively
correlated with $c_{i}$, for example an exponential function
$f(c_{i})=10^{-c_{i}}$. Although the ClusterRank is proposed for directed
networks, it can be easily extended to undirected networks (Chen et al., 2013)
and weighted networks(Wang et al., 2017). Experiments on several real networks
demonstrate that the ClusterRank score outperforms the PageRank and the
LeaderRank while being more efficient in computation.

  *   * –

Local structural Centrality (Gao et al., 2014). Aiming to evaluate the
spreading ability of nodes, a local structural centrality essentially extends
the local centrality (section 3.1.2) by further considering the connections
between higher-order neighbours. The idea is that a node has a better
spreading ability when its neighbours are better connected because a neighbour
node can be affected directly by the source node or indirectly by another
neighbour node. The local structural centrality of node $i$ is defined as:

(43) $\Theta_{LS}(i)=\sum_{j\in
N_{i}}(\alpha|N_{j}^{1,2}|+(1-\alpha)\sum_{k\in N_{j}^{1,2}}c(k)),$

where $N_{j}^{1,2}$ is the node set of 1-hop and 2-hop neighbours of node $j$,
and $c(k)$ is the clustering coefficient of node $k$. $\alpha$ is a tunable
parameter between $0$ and $1$, balancing a direct and indirect spreading
contribution. Notice that the part of the clustering coefficient is multiplied
in the ClusterRank when evaluating spreading speed, but added up here when
measuring the spreading ability.

  *   * –

Local triangle structure centrality (Ma and Ma, 2019). A local triangle
structure centrality (LTSC) proposes to include the triangle proportion of a
node, instead of its clustering coefficient when evaluating a node’s spreading
ability. The triangle proportion is able to indicate the location of a node,
whether it is located in a denser or sparser part of a network. LTSC
partitions the spreading ability into two parts, i.e., inner spreading ability
and outer spreading ability. Specifically, the local triangle structural
centrality of node $i$ is defined as:

(44) $\Theta_{TS}(i)=\sum_{j\in N_{i}}(d_{j}(1+TP(j))+(\sum_{k\in
N_{j}}d_{k}-d_{j})),$

where $TP(j)$ is the triangle proportion of node $j$, calculated by the number
of triangles containing $j$ divided by the total number of triangles in the
network. For each neighbour $j$ of a given node $i$, the part of
$d_{j}(1+TP(j)$ is to measure its inner spreading ability, and the part of
$\sum_{k\in N_{j}}d_{k}-d_{j}$ is to measure its outer spreading ability.
Finally, the local triangle structure centrality of node $i$ is the sum of the
spreading abilities of its neighbours.

  *   * –

Hybrid degree centrality (Ma and Ma, 2017). The spreading probabilities of
networks describing diseases, opinions, and rumours should obviously differ.
Most existing centrality measures, however, fail to take that into
consideration. The performance of centrality measures is sensitive to the
spreading probability. The degree centrality, for example, works best with
modest spreading probabilities, while the local centrality (section 3.1.2)
works better with higher ones (Gao et al., 2014). In order to alleviate the
sensitivity to different spreading probabilities, a hybrid degree centrality
is introduced by integrating the degree centrality and a modified local
centrality. The hybrid degree centrality of node $i$ is defined as:

(45)
$\Theta_{HD}(i)=(\beta-p)\cdot\alpha\cdot\Theta_{D}(i)+p\cdot\Theta_{LR}^{\prime}(i),$

where $\Theta_{LR}^{\prime}(i)=\Theta_{LR}(i)-2\sum_{j\in N_{i}}|N_{j}|$ is
the modified local centrality, $p$ is the spreading probability, $\alpha$ and
$\beta$ are two tunable parameters. The part contributed by the degree
centrality is viewed as a near-source influence, and the part of modified
local centrality is a distant influence.

  *   * –

HybridRank (Ahajjam and Badir, 2018). A HybridRank proposes to identify
influential spreaders by combining the neighbourhood coreness centrality
(section 3.1.1) and the eigenvector centrality. The reason for integrating
these two measures is that they both regard a node as influential if the node
is connected to other influential nodes. The hybrid centrality of node $i$ is
defined as:

(46) $\Theta_{HR}(i)=\Theta_{NC}(i)\times\Theta_{E}(i),$

where $\Theta_{NC}(i)=\sum_{j\in N_{i}}ks(j)$ is the neighbourhood coreness of
$i$, and $\Theta_{E}(i)$ is the eigenvector centrality of node $i$. The
HybridRank algorithm further suggests that when selecting influential
spreaders, the neighbours of selected ones should be neglected in order to
maximise the spreading range. The effectiveness of the HybridRank has also
been tested in real networks using a SIR model.

  *   * –

BridgeRank (Salavati et al., 2018). In order to lower the time complexity of
the closeness centrality while keeping comparable performance, a BridgeRank
proposes to compute the shortest paths to just a few core nodes in the
network. In the BridgeRank algorithm, at first, communities are identified by
the Louvain algorithm (Blondel et al., 2008). Then, core nodes are discovered
through calculating the betweenness centralities within each community (one
core node per community). Finally, the BridgeRank centrality of each node is
defined as a filtered closeness centrality to these core nodes:

(47) $\Theta_{BR}(i)=\frac{1}{\sum_{j\in\mathcal{C}}d(i,j)},$

where $\mathcal{C}$ is the set of identified core nodes in each community. The
time complexity is therefore reduced from $O(|V|^{3})$ to $O(|V|log|V|)$. A
modified version that allows multiple core nodes being selected in a community
is also introduced (Salavati et al., 2018). Other community structure based
methods include $k$-medoid that uses information transfer probabilities
between any node pairs (Zhang et al., 2013b), and the influence maximization
algorithm based on label propagation (Zhao et al., 2016).

  *   * –

CCPA (Ahmad et al., 2020). A common neighbour and centrality based
parameterised algorithm, or CCPA, is an approach for a link prediction. It
aims to bring together two essential properties of nodes, i.e., the common
neighbours and the closeness centrality. The similarity score between a pair
of nodes $i$ and $j$ is defined as:

(48) $s(i,j)=\alpha\cdot(|N_{i}\cap
N_{j}|)+(1-\alpha)\cdot\frac{|V|}{d(i,j)}.$

$|N_{i}\cap N_{j}|$ is obviously the part of common neighbours.
$\frac{|V|}{d(i,j)}$, reciprocal of the normalised distance between two nodes,
is deemed as the closeness centrality of them, since it has a similar form as
the classic node closeness centrality. $\alpha\in[0,1]$ is a user-defined
parameter controlling the weight of the two parts. Experiments on real-world
datasets suggest that the change in performance (measured in average AUC)
caused by the change of $\alpha$ is not significant.

###  3.6. Discussion and Outlook

To end this section, we further discuss graph structural measures in different
types of networks and highlight some research avenues for future studies. We
then briefly talk about the importance and role of reviewing traditional
structural measures in the following part of the survey on GCNs.

Dynamic Networks. Most approaches covered in the survey assume that networks
are static or time-independent. Many real-world networks, however, are in fact
dynamic, nodes and edges appearing and disappearing over time (Holme and
Saramäki, 2012; Liao et al., 2017). In telecommunication networks, the
connection between agents is often bursty and fluctuates across time; in
social networks, relationships among people are typically intermittent and
recurrent; in transportation networks, the frequency of public transport
service is usually higher in rush hours. This extra dimension of time adds
richness and complexity to the graph representation of a system, necessitating
the development of more advanced approaches that can leverage temporal
information. Many studies have generalised the classic graph structural
measures to dynamic networks, including temporal degree centrality(Kim et al.,
2012), temporal clustering coefficient (Nicosia et al., 2013), temporal
closeness and betweenness centrality (Kim and Anderson, 2012), temporal
eigenvector centrality (Taylor et al., 2017), temporal Katz centrality
(Nicosia et al., 2013), temporal motifs (Kovanen et al., 2011; Paranjape et
al., 2017) and temporal graphlets (Hulovatyy et al., 2015). Despite the large
number of structural measures proposed for dynamic networks, there are still
many open questions to be tackled. For example, what is the impact of the
temporal network’s structure on the dynamics of processes that occur on it;
how to apply temporal measures in inferring spreading chains in incomplete
temporal networks, etc.

Multilayer Networks. Sometimes, systems are so complicated that multiple-
layered networks are needed to better represent and study them (De Domenico et
al., 2013a; Kivelä et al., 2014; Boccaletti et al., 2014; Bianconi, 2018). For
example, a multilayer social network incorporates both friendship and
financial relationships among individuals; a multilayer brain network contains
both the anatomical brain layer and functional brain layer, and a multilayer
transportation network integrates all sorts of transportation. Since
interlayer connections cause new structural and dynamic correlations between
components, neglecting them or simply aggregating over layers will alter the
original topological properties. Therefore, it is desirable to develop
structural measures taking interlayer relationships into consideration. Not
surprisingly, fundamental single-layer approaches have been largely
generalised to multilayer networks, such as multilayer degree, clustering
coefficient, closeness and betweenness centralities, (Donges et al., 2011; De
Domenico et al., 2013a; Boccaletti et al., 2014), multilayer motifs and
graphlets (Battiston et al., 2017; Dimitrova et al., 2020), multilayer
eigenvector, PageRank and HITS centralities (De Domenico et al., 2015; Halu et
al., 2013; De Domenico et al., 2013b). Some tailor-made approaches for
multilayer networks are also recently introduced, for example, the minimal-
layers power community index (Basaras et al., 2017), and the singular vector
of tensor centrality (Wang and Zou, 2018). The study of multilayer structures,
however, is still in an early stage. There is still much room for developing
new cross-layer structural approaches that better model inter-layer spreading
processes (Salehi et al., 2015) and captures multiplex dynamics, and
controllability (Jiang et al., 2021).

Node/edge attributes. Network data, besides the pure topological presence, are
often accompanied by rich information on node attributes and/or edge
attributes, and they are also referred to as labelled networks or attributed
networks. Most structural measures, as the name suggests, focus solely on
capturing the part of topological properties. Theoretically, message passing
approaches are able to include numeric node attributes, such as the initial
rank and source of rank in the PageRank (Brin and Page, 1998), or the
endogenous and exogenous status in the alpha centrality (Bonacich and Lloyd,
2001). In practice though, these features are usually set to identical values
for all nodes, for example, all ones for the initial rank and $0.15$ for the
source of rank in the PageRank. Multidimensional features are not supported in
message passing approaches either. There have also been attempts to integrate
node/edge attributes with other graph structural measures. For instance, the
degree and betweenness centralities are combined with node attributes in
studying criminal networks (Bright et al., 2015); nodes’ attributes are used
as a threshold in LRIC index (Aleskerov et al., 2016); and node/edge
attributes are fused into graphlets (Rossi et al., 2020; Jia et al., 2021a).
We believe there is still great potential for developing novel structural
approaches that integrate rich information on nodes and/or edges. It is also
worth mentioning that one reason for the popularity of graph neural networks
is that it naturally enables integrating node attributes and some recent works
also propose to take edge attributes into account in GNNs (Gong and Cheng,
2019; Jiang et al., 2020; Chen and Chen, 2021).

Finally, we discuss how the traditional structure-based approaches are linked
to GCNs. The importance and role of reviewing traditional structural measures
in the survey of GCNs are Multifaceted. First, traditional structural
approaches, the outcome of decades of Network Science studies, are the
precursors and foundations of graph neural networks. For example, the key idea
of neighbourhood aggregation and message passing in GCNs can trace back to
1972 when Bonacich proposed the eigenvector centrality (Bonacich, 1972). Basic
network science notions such as the clustering coefficient, motifs and
graphlets are utilised in GCNs as well. Second, the taxonomy of traditional
approaches from the perspective of structure information inspired us to
develop a new taxonomy for GCNs. We will see later how the taxonomy of GCNs
from a layer-wise message aggregation scope is similar to that of subgraph
count based measures in Section 3.1. Third and last, a comprehensive review of
traditional structural measures not only helps in revealing their connections
to GCN approaches but also benefits the discovery of knowledge gaps. We will
see that some GCN approaches are inspired by the traditional message passing
based approaches, and that many subgraph count based approaches find their
usages in GCNs. However, the connections between GCNs and subgraph formation
based or global path based approaches are still largely left undiscovered.

##  4\. Structure information in Graph Convolutional Networks

After summarising the traditional Network Science structural measures, we are
set to review the graph convolutional networks from a novel perspective of
graph structural information.

In recent years, graph neural networks, especially graph convolutional
networks, have become one of the most prominent research areas in the study of
complex networks. It extends the traditional convolutional neural networks to
graph data and enables an effective combination of the rich node features
information and graph topological structure. Graph convolutional networks have
been successfully applied in different types of graph learning tasks,
including node classification, link prediction, graph classification and graph
clustering. Amongst the large family of graph deep learning approaches (Zhang
et al., 2020; Ma and Tang, 2021), we particularly focus on graph convolutional
networks not only because they have a wider range of applicability, but also
because they are the bases of many other graph deep learning approaches,
including graph autoencoders, graph reinforcement learning, graph adversarial
methods, etc.

There exist several comprehensive surveys on graph neural networks. Bronstein
et al. (Bronstein et al., 2017) provide a thorough review of geometric deep
learning, which presents its problems, difficulties, solutions and
applications. Hamilton et al. (Hamilton et al., 2017b) develop a unified
encoder-decoder framework for graph representation learning approaches,
bringing together matrix factorisation-based methods, random-walk-based
algorithms and graph neural networks. Chami et al. (Chami et al., 2020) later
extend the framework by including more recent advancements in the area. Zhang
et al. (Zhang et al., 2019) propose a comprehensive review specifically on
graph convolutional networks. Zhou et al. (Zhou et al., 2020) introduce a
detailed taxonomy after dividing GNNs into several modules, including the
propagation module, the sampling module and the pooling module. Wu et al. (Wu
et al., 2020) propose to divide GNNs into four categories, i.e., recurrent
GNNs, convolutional GNNs, graph autoencoders and spatial-temporal GNNs.

These reviews, when introducing convolutional neural networks, usually focus
on the domain of convolutional operations and propose a dichotomy, i.e., the
spectral-based methods and the spatial-based methods. However, the line
between the two is sometimes blurred. For example, GCN is an approximation of
spectral graph convolutions, but it operates directly on graphs — applying
filters acting on the k-hop neighbourhood of the graph in the spatial domain
(Bronstein et al., 2017). Another recent work also proves that spectral
convolutional graph neural networks can be viewed as a particular case of
spatial convolutional neural networks (Muhammet et al., 2020).

Different from existing reviews, in this survey we primarily, but not
exclusively, focus on how local structure plays its role in graph
convolutional networks. we propose to categorise GCN approaches from three
different perspectives, which are the layer-wise message aggregation scope,
the message content, and the overall learning scope.

  * •

Layer-wise message aggregation scope. Analogous to convolutional neural
networks, multilayer architecture is one of the key features in graph
convolutional networks. Taking the vanilla GCN for example, at each layer, a
node gathers information from its 1-hop neighbours. Then from stacking $k$
layers, the node would convolve its $k^{th}$-order neighbourhood. Thereafter,
many other approaches propose to apply different scope at each layer,
including 2-hop neighbourhood, k-hop neighbourhood, local-random-walk
neighbourhood, subgraph neighbourhood, etc. This first structural perspective
in GCN design can be summarised into the following question: From where a node
aggregates message at each layer? The detailed taxonomy of GCNs from the
perspective of layer-wise message aggregation scope and related approaches are
given in Subsection 4.1.

  * •

Message content. Compared to traditional deep learning models such as CNNs and
RNNs, the strength of GCNs comes from the ingenious integration of graph
structure and node features — node features are passed through the edges of
the graph. In many cases, the feature of nodes is independent of graph
structure, such as numerical ratings, word vectors generated from sentences,
positional gene sets, immunological signatures, and more. Meanwhile, there are
emerging works that include other structural information as part of node
features, from the simplest node degree to more complicated distance or
subgraph information (Hamilton et al., 2017a; Li et al., 2020; Bouritsas et
al., 2020). This second structural perspective in GCN design can be summarised
into the question: What structural information is included in the node feature
when initialising or running the message passing scheme? The detailed taxonomy
from the message content perspective and the related approaches are given in
Subsection 4.2.

  * •

Learning scope. Traditional graph representation learning approaches are
generally based on matrix factorisation, which thus requires the fixed whole
graph. Although the original GCN approach also takes the whole graph’s
adjacency matrix as input, it has soon been extended to various settings, such
as subgraphs, localised subgraphs, and more. To put in a question format, the
third structural perspective in a GNN design is: Where GCNs are trained on? or
What is/are the input graph/graphs in GCNs? The detailed taxonomy of GCNs from
the learning scope perspective and the related approaches are given in
Subsection 4.3.

###  4.1. Layer-wise message scope

To begin with, we discuss in detail the first structural perspective in a GCN
design, i.e., a layer-wise message scope. By answering the question of where a
node aggregates message from at each layer, we divide existing GCN approaches
into four categories, which are 1-hop neighbourhood approaches, k-hop
neighbourhood approaches, local-random-walk neighbourhood approaches, and
subgraph neighbourhood approaches. The taxonomy and representative approaches
are given in Figure 10. The colour of the block indicates what task the
approach is proposed for: grey is the most common node classification task,
orange is a network classification, and blue is the link prediction task which
will appear later in Section 4.2. Notice that a graph representation can be
readily obtained via graph pooling, so approaches proposed for a node
classification can potentially be applied in a network classification task.
Likewise, some approaches proposed for the network classification also
generate node representations, making them possible to be used in the node
classification.

Figure 10. Taxonomy from the Layer-wise Message Aggregation Scope perspective.

####  4.1.1. 1-hop neighbourhood approaches

Many influential GCN approaches adopt the 1-hop neighbourhood aggregation
strategy, where a node’s representation is iteratively updated through
aggregating representations of its neighbours. One iteration happens at one
convolutional layer, and after stacking multiple layers, the node’s
representation is able to capture a wider range of neighbourhoods.

GCN. Motivated by the first-order approximation of localised spectral filters
on a graph (Defferrard et al., 2016), GCN proposes the following layer-wise
propagation rule operating directly on graphs:

(49) $H^{(l)}=\sigma\left(\hat{A}H^{(l-1)}W^{(l)}\right)$

, where $\hat{A}=\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$,
$\tilde{A}$ is adjacency matrix with added self-connections, and $\tilde{D}$
is degree matrix of $\tilde{A}$. $H^{(l)}$ is the representations at the
$l^{th}$ layer, and $W^{(l)}$ is the learnable weight matrix at $l^{th}$
layer. $\sigma$ denotes a nonlinear activation function such as ReLU. The
multiplication of the normalised self-connection added adjacency matrix
$\hat{A}$ and the nodes’ representation matrix $H$ represents a normalised sum
of neighbouring nodes’ (and self node’s) representation. From a microscopic
point of view, the representation of node $v$ at layer $l$ is calculated as:

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

where $\mathcal{N}(v)$ is the set of node $v$’s one-hop neighbours (with added
self-loops to each node),
$c_{vu}=\sqrt{|\mathcal{N}(v)|}\sqrt{|\mathcal{N}(u)|}$ is the normalization
constant based on the node degree. The loss is then computed as:
$\mathcal{L}=-\sum_{l\in\mathcal{Y}_{L}}\sum_{f=1}^{F}Y_{l}\ln Z_{lf}$, where
$\mathcal{Y}_{L}$ is the set of labelled nodes, $Z$ is the output embedding
and $F$ are the feature maps. Successfully bringing convolutional operations
on graphs, GCN has become one of the most popular graph representation
learning approaches. It is worth mentioning that the Iterative Classification
Algorithm (ICA) also uses neighbourhood information to train a model (Bhagat
et al., 2011; Neville and Jensen, 2000). The model is then used to iteratively
update the labels of nodes in the test set. Obviously, without a multi-layer
convolutional network, the scope of ICA in the training stage is strictly
limited within the immediate neighbourhood.

GraphSAGE. Hamilton et al. later proposed the GraphSAGE framework, which
extends the GCN to a more general setting that supports a mini-batch approach
and different aggregation functions (Hamilton et al., 2017a). Specifically,
the representation of node $v$ at layer $l$ is given by:

(51) $\displaystyle\mathbf{h}_{\mathcal{N}(v)}^{l}\leftarrow\text{ AGGREGATE
}_{l}\left(\left\\{\mathbf{h}_{u}^{l-1},\forall
u\in\mathcal{N}(v)\right\\}\right),$
$\displaystyle\mathbf{h}_{v}^{l}\leftarrow\sigma\left(\mathbf{W}^{l}\cdot\operatorname{CONCAT}\left(\mathbf{h}_{v}^{l-1},\mathbf{h}_{\mathcal{N}(v)}^{l}\right)\right)$

The framework thus gives us the flexibility to choose different aggregator
functions, such as mean aggregator (equivalent to GCN), LSTM aggregator and
pooling aggregator. Further, unlike GCN which requires full batch gradient
descent, GraphSAGE enables mini-batch setting and therefore can also be
applied to unseen nodes (also known as inductive learning). In addition,
GraphSAGE proposes to sample a fixed-size of neighbours around each node in
their aggregation scheme, instead of using all neighbours, which helps to keep
the computational cost of each batch fixed.

GIN. Although GCN and GraphSAGE have achieved excellent performances in graph
learning tasks, especially in node classification tasks, they are unable to
distinguish some simple graph structures due to their limits in the
neighbourhood aggregation scheme. Graph Isomorphism Network architecture (GIN)
(Xu et al., 2018) is proposed to overcome this shortcoming and is proven to be
as powerful as the Weisfeiler-Lehman graph isomorphism test (Weisfeiler and
Leman, 1968). Specifically, in order to achieve the same discriminative power
as the Weisfeiler-Lehman test, the representation of node $v$ at layer $l$
should be as:

(52)
$h_{v}^{(l)}=\phi^{(l)}\left(h_{v}^{(l-1)},f^{(l-1)}\left(\left\\{h_{u}^{(l-1)}:u\in\mathcal{N}(v)\right\\}\right)\right),$

where $f^{(l-1)}$ is a function operating on multisets and $\phi^{(l)}$ is an
injective function. The choice of multiset on neighbourhood information
aggregation, instead of mean pooling in GCN or max pooling in GraphSAGE,
enables it to better preserve neighbourhood structural information. The above
representation is then proven to be equivalent to:

(53)
$h_{v}^{(l)}=\operatorname{MLP}^{(l)}\left(\left(1+\epsilon^{(l)}\right)\cdot
h_{v}^{(l-1)}+\sum_{u\in\mathcal{N}(v)}h_{u}^{(l-1)}\right),$

where $\epsilon^{(l)}$ is a scalar representing the importance of the focal
node, and MLP is used to model the composition of the function $f$ and $\phi$.

GAT. Although in the aggregation scheme of the GCN, nodes from the same
neighbourhood are assigned different weights by introducing the normalisation
term ($c_{vu}$ in Equation 50), the approach lacks the flexibility of
introducing other weight mechanisms. To overcome this shortcoming, GAT
proposes to use a masked self-attentional layer on graphs. Masked means that
only 1-hop neighbours, rather than all other nodes, of a given node, are
included in the attention scheme. Specifically, the attention coefficient of
an edge $e_{vu}$ at layer $l$ is given by:

(54)
$\alpha_{vu}^{(l)}=\frac{\exp\left(e_{vu}^{(l)}\right)}{\sum_{w\in\mathcal{N}(v)}\exp\left(e_{vw}^{(l)}\right)},e_{vu}^{(l)}=\operatorname{LeakyReLU}\left(\vec{a}^{(l)}[\mathbf{W}^{(l)}h_{v}^{(l)}\|\mathbf{W}^{(l)}h_{u}^{(l)}]\right),$

where $a^{(l)}$ is a shared feedforward neural network parameterised by a
weight vector $\vec{a}$, and $\mathbf{W}^{(l)}$ is a shared linear
transformation of input or hidden features. Then the representation of node
$v$ at layer $(l+1)$, is obtained through applying the attention coefficients
on $v$’s neighbour nodes:

(55)
$h_{v}^{(l+1)}=\sigma\left(\sum_{j\in\mathcal{N}(i)}\alpha_{vu}^{(l)}\mathbf{W}^{(l)}h_{u}^{(l)}\right)$

FastGCN. One issue of the GCN’s neighbourhood aggregation scheme is the quick
neighbourhood expansion across layers, which largely limits its scalability in
large and dense graphs. To address this problem, FastGCN (Chen et al., 2018)
proposes to sample a fixed number of nodes at each layer while applying
neighbourhood aggregation, so the number of involved nodes is up-bounded by
the sample size. Concretely, the representation of nodes at layer $l$ is given
by:

(56)
$H^{(l+1)}(v,:)=\sigma\left(\frac{n}{s}\sum_{j=1}^{s}\hat{A}\left(v,u_{j}^{(l)}\right)H^{(l)}\left(u_{j}^{(l)},:\right)W^{(l)}\right),$

where $s$ is the sample size and $n$ is the total number of nodes in a graph.
Compared to the node-wise sampling strategy proposed by GraphSAGE, this layer-
wise sampling method further improves the computational efficiency of the
model. For example, in a 2-layer setup, when 10 nodes are sampled from a
node’s neighbourhood, there will be a total of $10^{2}=100$ nodes involved. In
contrast, when 10 nodes are sampled at each layer, the total number of
involved nodes is at most $10*2=20$.

GraphSNN. A common feature of the above-mentioned approaches is that each node
gathers information from its neighbours, that is to say treating the
neighbourhood as a 1-hop subtree. A recent work argues that this scheme
ignores the rich structure information among the neighbour nodes, and
therefore proposes a model named GraphSNN to treat the neighbourhood as a
1-hop subgraph by including the connections among neighbours (Wijesinghe and
Wang, 2021). Concretely, the work first defines structure coefficients for
each node and its neighbours and generate a weighted adjacency matrix
$A_{vu}=w\left(S_{v},S_{vu}\right)$, where $S_{v}$ is 1-hop neighbourhood
subgraph of node $v$, and $S_{vu}$ is overlap subgraphs of node $v$ and $u$.
$w$ is a function on $S_{v}$ and $S_{vu}$ exhibiting properties of local
closeness and local denseness, which is designed as
$\frac{\left|E_{vu}\right|}{\left|V_{vu}\right|\cdot\left|V_{vu}-1\right|}\left|V_{vu}\right|^{\lambda}$
in the paper. $\lambda$ is a positive value chosen by users. Then, the
representation of node $v$ at layer $l$ is generated by:

(57)
$h_{v}^{(l)}=\operatorname{MLP}^{(l)}\left(\gamma^{(l-1)}\left(\sum_{u\in\mathcal{N}(v)}\tilde{A}_{vu}+1\right)h_{v}^{(l-1)}+\sum_{u\in\mathcal{N}(v)}\left(\tilde{A}_{vu}+1\right)h_{u}^{(l-1)}\right),$

where $\gamma^{(l-1)}$ is a learnable scalar parameter, and $\tilde{A}_{vu}$
is the normalised weighted adjacency matrix. The part before $h_{v}^{(l-1)}$
signifies the focal node’s self-importance while the part
$\sum_{u\in\mathcal{N}(v)}\left(\tilde{A}_{vu}+1\right)$ before
$h_{u}^{(l-1)}$ is to apply different weights on different neighbours based on
the overlap subgraph between the focal node and the neighbour node. From this
perspective, GraphSNN is also an attention-like scheme that takes the 1-hop
subgraph structure into account.

DGCNN. In order to apply a GCN on graph-level learning tasks, Deep Graph
Convolutional Neural Network (DGCNN) proposes to sort and pool the nodes’
representations from multiple graph convolutional layers, then pass them to a
traditional CNN architecture, i.e., a one-dimensional convolutional layer
followed by dense layers before the final softmax output layer (Zhang et al.,
2018). As the GCN can be viewed as a differentiable and parameterised
generalisation of the 1-dim Weisfeiler-Lehman algorithm (Kipf and Welling,
2016a), each node’s representation can be viewed as a continuous colour at
that layer. The order of nodes in DGCNN is thus calculated according to the
nodes’ representations, i.e., nodes’ colours, at the graph convolutional
layers (first comparing the representations at the last layer, then the
representations at the second-to-last layer when some nodes have the same
representation, and so on). Next, in order to fit into the following CNN
architecture, the sorted nodes’ representation needs to be truncated or
extended, which is done by deleting excessive rows or adding zero rows. This
bridge layer between GCN and CNN is also known as SortPooling.

####  4.1.2. k-hop neighbourhood approaches.

A natural idea to improve the performance of the GCN is to expand its message
aggregation scope at each layer. This leads us to the second subcategory,
i.e., k-hop neighbourhood approaches.

MixHop. The layer-wise message passing scope of the vanilla GCN is limited to
1-hop neighbours and therefore lacks the ability to mix latent information
from neighbours at different distances. MixHop is proposed to address this
issue through a higher-order message passing scheme that aggregates
information from further neighbours (Abu-El-Haija et al., 2019). Concretely,
the convolutional layer is defined as:

(58) $H^{(i+1)}=\sigma\left(\biggr{\|}_{j\in
K}\widehat{A}^{j}H^{(i)}W_{j}^{(i)}\right),$

where $K$ is a set of integers representing the scope, and $\|$ denotes
column-wise concatenation. When $K={1}$, the operation degrades to the vanilla
GCN. The paper also proves theoretically that the vanilla GCN cannot recover a
2-hop delta operator and thus cannot represent a general layer-wise
neighbourhood mixing. In contrast, MixHop is able to learn a general mixing of
information from neighbours at various distances. Their experiments on a
synthetic dataset show that MixHop performs significantly better than several
baselines on graphs of low levels of homophily.

k-hop GNN. A simple example of the limitation of the 1-hop neighbourhood
aggregation is that it cannot distinguish regular graphs of the same size and
degree. In order to improve the expressivity of the vanilla GCN, k-hop GCN
also proposes to take k-hop neighbours into consideration in the layer-wise
aggregation scheme (Nikolentzos et al., 2020). The general model is presented
as:

(59) $\displaystyle
a_{v}^{(l)}=\operatorname{AGGREGATE}^{(l)}\left(\left\\{h_{u}^{(l-1)}\mid
u\in\mathcal{N}_{k}(v)\right\\}\right),$ $\displaystyle
h_{v}^{(l)}=\operatorname{MERGE}^{(l)}\left(h_{v}^{(l-1)},a_{v}^{(l)}\right),$

where $\mathcal{N}_{k}(v)$ denotes the k-hop neighbourhood of node $v$.
Specifically, it adopts an outside-to-inside updating scheme in the
aggregation part: gradually updating neighbouring nodes from the furthest to
the immediate ones. Each neighbour node $u$ at a distance $d$ from the focal
node $v$ goes through two update functions successively:

(60) $\displaystyle
x_{u}=\operatorname{UPDATE}_{d,across}^{(l)}(u,\mathcal{N}_{1}(u)\cap
R_{d+1}(v)),$ $\displaystyle
x_{u}=\operatorname{UPDATE}_{d,within}^{(l)}(u,\mathcal{N}_{1}(u)\cap
R_{d}(v)),$

where $R_{d+1}(v)$ or $R_{d}(v)$ denote the set of nodes that are at a
distance $d+1$ or $d$ from node $v$. The first function learns representation
from node u’s neighbours that are $(d+1)$-hop away from node $v$; and the
second function learns from node u’s neighbours that are $d$-hop away from
node $v$. The update functions are defined as:
$\operatorname{UPDATE}(u,S)=\operatorname{MLP}_{1}\left(\operatorname{MLP}_{2}\left(x_{u}\right)+\sum_{w\in
S}\operatorname{MLP}_{3}\left(x_{w}\right)\right)$. Finally, the
representation of a node $v$ is calculated as:
$h_{v}^{(l)}=\operatorname{UPDATE}_{0,across}^{(l)}\left(v,\mathcal{N}_{1}(v)\right)$.
Although this model can capture structural information from the k-hop
neighbourhood at a single layer, it requires up to $2k$ update functions and
the aggregation scheme is much more complicated and computationally expensive.

Adapt. Similar to the FastGCN, Adaptive Sampling GCN (abbreviated as Adapt)
adopts the layer-wise sampling strategy in order to accelerate the training of
the GCN (Huang et al., 2018). Lower layer sampling is conditioned on the
higher layer. Compared to node-wise sampling, layer-wise sampling not only has
a fixed number of nodes at each layer but also preserves the connections
between lower-layer neighbours and higher-layer parent nodes. Furthermore, the
approach proposes to aggregate information from distant nodes via skip
connections, i.e., connecting layer $l+1$ with layer $l-1$. Specifically, the
skip-connection representation of node $v$ at layer $(l+1)$ is formulated as:

(61) $h_{v_{\text{skip
}}}^{(l+1)}=\sum_{s\in\mathcal{V}^{(l-1)}}\hat{a}_{skip}\left(v,s\right)h_{s}^{(l-1)}W_{\text{skip
}}^{(l-1)},$

where $s$ denotes sampled nodes at layer $(l-1)$,
$\hat{a}_{skip}\left(v,s\right)=\sum_{u\in\mathcal{V}^{(l)}}\hat{a}\left(v,u\right)\hat{a}\left(u,s\right)$,
and $W_{\text{skip }}^{(l-1)}=W^{(l-1)}W^{(l)}$. The part of skip-connection
is then added to the classic GCN layer before a nonlinear transformation.
Therefore, the overall representation of node $v$ is:

(62)
$h_{v}^{(l+1)}=\sigma\left(\sum_{u\in\mathcal{V}^{(l)}}\hat{a}\left(v,u\right)h_{u}^{(l)}W^{(l)}+h_{v_{\text{skip
}}}^{(l+1)}\right).$

That is to say, each node gathers information from both its 1-hop neighbours
and 2-hop neighbours. Their experiments on the Cora dataset show that although
skip connection does not lead to significant improvement in accuracy, it helps
to speed up the convergence.

DGP. Aiming to improve the performance of zero-shot learning tasks on
knowledge graphs (directed graphs), Dense Graph Propagation (DGP) proposes to
adopt a two-phase propagation scheme on two separate connectivity patterns
(one having nodes connected to their ancestors and the other having nodes
connected to their descendants) (Kampffmeyer et al., 2019). Furthermore, at
each phase, DGP introduces a weighting scheme to include the contributions
from distant nodes. Concretely, the overall representation is formulated as:

(63)
$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),$

where $\hat{A}_{k}^{a}$ and $\hat{A}_{k}^{d}$ denote the normalised adjacency
matrices containing k-hop connections to ancestors and to descendants,
respectively. $\alpha_{k}^{a}$ and $\alpha_{k}^{d}$ are learnable weights
denoting contributions from nodes that are k-hop away from a given node. We
see from the above equation that DGP can be viewed as consisting of two
convolutional layers where the inner layer aggregates information from 1 to
k-hop out-neighbours, and the outer layer aggregates information from 1 to
k-hop in-neighbours.

DGCN. Directed Graph Convolutional Networks (DGCN) is another attempt to
extend the GCN to directed graphs (Tong et al., 2020). It proposes to expand
the receptive field of convolutional operation by considering the first- and
second-order proximities. Specifically, they first define the notions of
second-order in-degree proximity matrix and second-order out-degree proximity
matrix as:

(64) $\displaystyle A_{S_{\text{in
}}}(u,v)=\sum_{w}\frac{A_{w,u}A_{w,v}}{\sum_{x}A_{w,x}},$ $\displaystyle
A_{S_{\text{out }}}(u,v)=\sum_{w}\frac{A_{u,w}A_{v,w}}{\sum_{x}A_{x,w}}.$

The idea is that if two nodes (a given node and its 2-hop neighbour) share
many common in-neighbours (or out-neighbours), they have higher second-order
in-degree (or out-degree) proximity. When capturing first-order proximity,
they choose to make the adjacency matrix symmetric by ignoring link
directions. Then the overall representation at layer $l$ is formulated as:

(65)
$\mathrm{H}^{(l)}=Concact\left(\sigma\left(\hat{\mathrm{A}}_{\mathrm{F}}\mathrm{H}^{(l-1)}\Theta^{(l-1)}\right),\sigma\left(\hat{\mathrm{A}}_{\mathrm{S}_{\mathrm{in}}}\mathrm{H}^{(l-1)}\Theta^{(l-1)}\right),\sigma\left(\hat{\mathrm{A}}_{\mathrm{S}_{\text{out
}}}\mathrm{H}^{(l-1)}\Theta^{(l-1)}\right)\right),$

where $\hat{\mathrm{A}}_{\mathrm{F}}$,
$\hat{\mathrm{A}}_{\mathrm{S}_{\mathrm{in}}}$ and
$\hat{\mathrm{A}}_{\mathrm{S}_{\mathrm{out}}}$ are normalised first-order
proximity matrix, normalised second-order in-degree proximity matrix and
normalised second-order out-degree proximity matrix, respectively. Notice that
although DGP also considers 2-hop neighbours in directed graphs when $k$
equals $2$, DGCN and DGP have different definitions of directed 2-hops.

SGC. In order to improve the efficiency and scalability of GCN, Simple Graph
Convolution (SGC) proposes to remove the nonlinear transformation between
layers (Wu et al., 2019). They argue that the main advantage of GCN lies in
its neighbourhood aggregation scheme, not the nonlinearity between
convolutional layers. After removing all nonlinear activations, the final
output of the SGC model is represented as follows:

(66)
$\hat{Y}=\operatorname{softmax}\left(\hat{A}\ldots\hat{A}\hat{A}H^{(0)}W^{(1)}W^{(2)}\ldots
W^{(L)}\right)=\operatorname{softmax}\left(\hat{A}^{L}H^{(0)}W\right),$

where $\hat{A}$ is the normalised self-connection added adjacency matrix,
$H^{(0)}$ is the input node feature matrix, and $W$ is a single weight matrix.
This output representation thus only requires learning a single weight matrix,
and the term $\hat{A}^{L}H^{(0)}$ can be computed directly. Note that the
meaning of $\hat{A}^{L}H^{(0)}$ is the sum of features from k-hop neighbouring
nodes. Therefore, the SGC model is actually equivalent to a single
convolutional layer where nodes aggregate information from their k-hop
neighbours.

PATCHY-SAN (Niepert et al., 2016). Traditional image-based convolutional
networks can be viewed as traversing a node sequence, i.e., a receptive field
moving from left to right and from top to bottom. In order to employ the
convolutional architecture to graphs where spatial order is missing, PATCHY-
SAN proposes to first impose an order on nodes according to a certain ranking
algorithm, then construct receptive fields from a fixed number of neighbour
nodes for each node in a preselected node sequence. Note here the neighbour
nodes are selected by performing a breadth-first search, so it can go beyond
1-hop neighbours. The receptive fields, after being normalised, will then be
fed into a one-dimensional convolutional layer and other dense layers.
Comparing this CNN-like approach with the GCN, we see that it requires an
extra procedure to rank nodes, and there are more hyper parameters to tune,
such as the length of node sequence, the stride and the number of neighbour
nodes in the receptive field.

####  4.1.3. Random-walk neighbourhood approaches

Instead of defining neighbourhood based on the distance to the focal node,
some GCN approaches adopt a random-walk based neighbourhood, which might
enable them to capture random processes on certain types of graphs.

PinSage. In order to apply GCN to web-scale recommender systems, PinSage
proposes to construct neighbourhoods via random walks, also referred to as
importance-based neighbourhoods (Ying et al., 2018). The convolutional
operation is similar to that of GraphSAGE:

(67)
$\displaystyle\mathbf{h}_{\mathcal{N}_{r}(v)}^{l}\leftarrow\gamma\left(\left\\{\sigma\left(\mathbf{Q^{l}}h_{u}\right)\mid
u\in\mathcal{N}_{r}(v)\right\\},\boldsymbol{\alpha}\right),$
$\displaystyle\mathbf{h}_{v}^{l}\leftarrow\sigma\left(\mathbf{W}^{l}\cdot\operatorname{CONCAT}\left(\mathbf{h}_{v}^{l-1},\mathbf{h}_{\mathcal{N}_{r}(v)}^{l}\right)\right),$

where ${\mathcal{N}_{r}(v)}$ is a random-walk neighbourhood, $\gamma$ is an
aggregation function, $h_{u}$ is a set of embeddings of nodes in the
neighbourhood, $\boldsymbol{\alpha}$ is a set of weights on nodes in the
neighbourhood, $\mathbf{Q^{l}}$ and $\mathbf{W^{l}}$ are learnable model
parameters. Specifically, ${\mathcal{N}_{r}(v)}$ comes from simulating a
random walk starting from the focal node and calculating the
$L_{1}$-normalised count of visited nodes, then the top $T$ nodes with the
highest counts are selected as the neighbourhood in the layer-wise message
passing. There are two benefits in this neighbourhood definition: first, the
number of nodes involved in the aggregation is fixed, so the cost of the
algorithm is predictable; second, the normalised visit counts can be directly
used as weights to represent the importance of each node in the neighbourhood.
PinSage also introduces some strategies to improve the model’s scalability,
such as the producer-consumer minibatch construction and a MapReduce pipeline.
Notice that PinSage is originally designed for recommender systems which are
bipartite networks.

GraLSP. Based on the idea that anonymous walks can capture structures through
reconstructing local subgraphs (Micali and Zhu, 2016), GraLSP proposes to
adopt random anonymous walks into the neighbourhood aggregation scheme (Jin et
al., 2020). It also combines some other techniques to enhance the model
performance, such as adaptive receptive radius, attention and channel-wise
amplification. Specifically, the convolutional layer is formulated as:

(68)
$\displaystyle\mathbf{a}_{v}^{(k)}=\operatorname{MEAN}_{\mathbf{wk}\in\mathcal{W}^{(i)},p\in\left[1,r_{\mathbf{wk}}\right]}\left(\lambda_{v,\mathbf{wk}}^{(k)}\left(\mathbf{q}_{v,\mathbf{wk}}^{(k)}\odot\mathbf{h}_{\mathrm{wk}_{p}}^{(k-1)}\right)\right),$
$\displaystyle\mathbf{h}_{v}^{(k)}=\operatorname{ReLU}\left(\mathbf{W}^{(k)}\mathbf{h}_{v}^{(k-1)}+\mathbf{U}^{(k)}\mathbf{a}_{v}^{(k)}\right),$

where $wk$ denotes a walk from the set of random walk sequence
$\mathcal{W}^{(i)}$, $wk_{p}$ is the $p$-th node in walk $wk$. $r_{wk}$,
$\lambda_{v,\mathbf{wk}}$ and $\mathbf{q}_{v,\mathbf{wk}}$ denote receptive
radius, attention coefficient and amplification coefficient, respectively.
Adaptive radius is introduced in order to regulate the scope of walks so that
nodes that are too far away in the constructed subgraph are excluded while
nodes in clustered subgraphs are included. Concretely, it is defined as
$r_{wk}=\left\lfloor\frac{2l}{C_{wk}}\right\rfloor$, where $l$ is walk length
and $C_{wk}$ is the number of distinct nodes visited by the walk. Finally, the
attention coefficient is introduced to assign different importance to visited
nodes, and the channel-wise amplification is used to model the selection of
node features.

####  4.1.4. Subgraph neighbourhood approaches

In addition to the fixed-hop neighbourhood and random-walk neighbourhood
definition in layer-wise message aggregation, some approaches view the
neighbourhood as k-node tuples or subgraphs.

k-GNN. As the ability of the GCN to distinguish nonisomorphic graphs is
equivalent to that of the 1-dimensional Weisfeiler-Leman algorithm (1-WL), a
k-GNN is proposed to achieve a higher expressivity as that of a k-WL (Morris
et al., 2019). Different from the vanilla GCN where each node gathers
information from a defined neighbourhood, the k-GNN works on the level of node
tuple. Accordingly, the neighbourhood of a k-tuple is defined as other
k-tuples containing one node that is not in the focal k-tuple. Specifically,
the neighbourhood of k-tuple $s$ is defined as:
$N_{k}(s)=\left\\{t\in[V]^{k}||s\cap t\mid=k-1\right\\}$, where $[V]^{k}$ is a
set of all k-tuples in a given graph. The convolutional operation at layer $l$
is then defined as:

(69) $h^{(l)}(s)=\sigma\left(h^{(l-1)}(s)\cdot W_{1}^{(l)}+\sum_{u\in
N_{k}(s)}h^{(l-1)}(u)\cdot W_{2}^{(l)}\right).$

At the beginning, $h^{(0)}(s)$ is set as $h^{iso}(s)$, which is a one-hot
encoding of the isomorphism type of induced subgraph of $s$. To improve the
model’s scalability and avoid overfitting, a more restricted k-tuple
neighbourhood $LN_{k}(s)$, named local neighbourhood, is defined as the tuples
in $N_{k}(s)$ also satisfying $(u,v)\in E$ for $u\in s\backslash t$ and $v\in
s\backslash t$. In other words, the non-overlapped nodes in a given k-tuple
and a neighbouring k-tuple needs to be connected so that the neighbouring
k-tuple is a local neighbourhood. Notice that as k-GNN is defined on the
k-tuple level, it is unsuitable for node-level tasks.

GRAPE. In order to improve GCN’s ability to discriminate graph isomorphism,
GRAPE proposes to consider specific subgraph patterns in its layer-wise
neighbourhood aggregation (Xu et al., 2021). First, nodes of a given subgraph
pattern are grouped into different sets according to their egocentric
automorphic equivalences, abbreviated as the Ego-AE set. For example, in a
triangle subgraph, the focal node is in one set, and the other two nodes are
in another set. Then, different weights are learned for each Ego-AE set.
Concretely, node $v$’s Ego-AE sets in a given subgraph $S$ are denoted as:
$\left\\{\mathcal{AE}_{S,1}\left(v\right),\ldots,\mathcal{AE}_{S,i}\left(v\right),\ldots,\mathcal{AE}_{S,m}\left(v\right)\right\\}$,
where $m$ is the total number of AE-set. The convolutional operation for
subgraph $S$ is then formulated as:

(70)
$h_{S}^{l}(v)=\operatorname{MLP}\left(\sum_{i}\beta_{S,i}\cdot\sum_{u\in\mathcal{AE}_{S,i}\left(v\right)}h_{S}^{l-1}\left(u\right)\right),$

where $\beta_{S,i}$ are learnable weights representing the importance of each
set $\mathcal{AE}_{S,i}$. Note that the focal node $v$ also belongs to an Ego-
AE set. The final embedding of node $v$ at layer $l$ is then achieved through
combining embeddings from a set of different subgraph patterns:
$h^{l}(v)=\sum_{S\in\Omega}\alpha^{l}_{S}\cdot h_{S}^{l}(v)$, where $\Omega$
denotes the set of subgraph patterns, and $\alpha^{l}_{S}$ is learnable weight
on a given subgraph pattern. This way GRAPE is able to differentiate
neighbouring nodes according to their structural roles captured by Ego-AE.
Certainly, the approach involves an extra step of choosing subgraph patterns.

Approach | Layer-wise aggregation scope | Aggregator | Task | Batch size | Type of graph
---|---|---|---|---|---
GCN | 1-hop neighbourhood | Sum/Mean | Node & Graph level | full-batch | General
GraphSAGE | 1-hop neighbourhood with sampling | Flexible choice | Node & Graph level | mini-batch | General
GIN | 1-hop neighbourhood | Multiset | Node & Graph level | mini-batch | General
GAT | 1-hop neighbourhood with attention scheme | Weighted sum/mean | Node & Graph level | mini-batch | General
FastGCN |  | 1-hop neighbourhood with
---
layer-wise sampling
Sum/Mean | Node & Graph level | mini-batch | General
GraphSNN |  | 1-hop neighbourhood with
---
structural coefficients
Sum/Mean | Node & Graph level | mini-batch | General
DGCNN | 1-hop neighbourhood | Sum/Mean | Graph level | full-batch | Directed
MixHop | k-hop neighbourhood | Sum/Mean | Node & Graph level | full-batch | General
k-hop GNN | k-hop neighbourhood | Outside-to-insides scheme | Node & Graph level | mini-batch | General
Adapt | 2-hop neighbourhood | Sum/Mean | Node & Graph level | mini-batch | General
DGP | k-hop neighbourhood | Sum/Mean | Node & Graph level | full-batch | Directed
DGCN | 2-hop neighbourhood | Sum/Mean | Node & Graph level | full-batch | Directed
SGC | k-hop neighbourhood | Sum/Mean | Node & Graph level | mini-batch | General
Patchy-SAN | fixed number of nodes | CNN-like (weighted sum) | Graph-level | mini-batch | General
PinSage | random-walk neighbourhood | Weighted sum/mean | Node & Graph level | mini-batch | Bipartite
GraLSP | random-walk neighbourhood | Sum/Mean | Node & Graph level | mini-batch | General
k-GNN | k-tuple neighbourhood | Sum | Graph-level | mini-batch | General
GRAPE | subgraph neighbourhood | Weighted sum | Node & Graph level | mini-batch | General
Table 3. Summary of approaches in the first category.

###  4.2. Message Content

The superior performance of the GCN lies in its ingenious combination of node
attributes and a graph structure with node attributes used as initial
representations and then subsequently propagated on the graph through certain
convolutional operations. In contrast, some learning approaches only exploit
structural information, such as the matrix decomposition based methods (Cao et
al., 2015; Ou et al., 2016) and the random walk based methods (Perozzi et al.,
2014; Grover and Leskovec, 2016). In situations where no node attributes are
provided, a simple structural metric like the node degree is often used as
initial representations in the GCNs (Hamilton et al., 2017a). Another group of
approaches further propose to improve the GCN’s distinguishability through
injecting more complicated structural features into the node representations,
such as the count of graphlets, distance-based information, etc. The taxonomy
and representative approaches are given in Figure 11.

####  4.2.1. Count of subgraphs.

The number of certain subgraphs or substructures is often used as a node
feature in traditional network studies (Milenković and Pržulj, 2008). Some
approaches thus propose to include this type of structural information as part
of a node representation in the GCN’s message passing scheme.

Figure 11. Taxonomy from the message content perspective.

GSN. Graph Substructure Network (GSN) proposes to capture structural features
by counting the appearance of particular graphlet orbits and include them as
part of node features in the convolutional operation (Bouritsas et al., 2020).
Specifically, node $v$’s representation at layer $l$ is defined as:

(71)
$\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),$

where $\mathrm{x}_{V}(v)$ and $\mathrm{x}_{V}(u)$ are structure features of
nodes $v$ and $u$, respectively. $\mathrm{e}(u,v)$ is an edge feature if
provided. The structural feature is a vector containing the counts of node
orbits. For example, if subgraphs 2-path and 3-clique are considered ($G_{1}$
and $G_{2}$ in Figure 4), the counts of three node orbits will be included in
the vector. GSN further introduces a version based on edge orbits, which is
formulated as:
$\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)$,
where $\mathrm{e}(u,v)$ denotes the edge structural feature, i.e., a vector
containing the count of edge orbits. The GSN has been proven to be strictly
more powerful than the 1-WL test when the chosen subgraphs are not star
graphs. Certainly, the choice of subgraphs is the core of this approach, and a
larger subgraph will lead to higher computational complexity in a
preprocessing step.

$\mathcal{F}$-MPNN. A local graph parameter enabled GNN ($\mathcal{F}$-MPNN)
also proposes to include a subgraph count into the GCN (Barceló et al., 2021).
$\mathcal{F}=\\{P_{1}^{r},...,P_{k}^{r}\\}$ is a set of pre-selected subgraph
patterns with $r$ referring to a node. The homomorphism count of each pattern
$P_{i}^{r}$ for node $v$ in the original graph $G$ is denoted as
$hom(P_{i}^{r},G^{v})$, which is actually equivalent to the count of a given
node orbit (see Section 2.2). Then a structural feature vector
$(hom(P_{1}^{r},G^{v}),...,hom(P_{k}^{r},G^{v}))$ is added to the one-hot
encoding of node $v$’s label, serving as $v$’s initial feature vector.
Concretely, the framework is formulated as:

(72)
$\displaystyle\mathbf{h}_{v}^{(0)}:=\left(x_{v},\operatorname{hom}\left(P_{1}^{r},G^{v}\right),\ldots,\operatorname{hom}\left(P_{\ell}^{k},G^{v}\right)\right),$
$\displaystyle\mathbf{h}_{v}^{(l)}:=\operatorname{MERGE}\left(\mathrm{x}_{v}^{(l-1)},\operatorname{AGGREGATE}\left(\left\\{\left\\{\mathrm{x}_{u}^{(l-1)}\mid
u\in N(v)\right\\}\right\\}\right)\right),$

where $x_{v}$ is the one-hot encoding of node $v$’s label, MERGE and AGGREGATE
are two MLPs. Since this structural feature is only applied to enhance the
initial feature of nodes, it can be used as an add-on to any GCN architecture.
Similar to the GSN, the choice of subgraph patterns is the core of
$\mathcal{F}$-MPNN. Cycles of length smaller than $10$ and cliques of size
smaller than $5$ are used as subgraph patterns in the experiment.

ID-GNN. Identity-aware GNN (ID-GNN) proposes to improve the expressivity of
the GCN through distinguishing the root node of the extracted computation
graphs from other nodes in its message passing scheme (You et al., 2021). It
contains two major steps: the first step, named inductive identity colouring,
is to uniquely colour the root node in its k-hop ego network; then in the
second step, a heterogeneous message passing is applied to all the extracted
ego networks. Specifically, the representation of any node $v$ in an extracted
computation graph $G_{r}$ (rooted at node $r$) is formulated as:

(73)
$\displaystyle\mathbf{m}_{u}^{(l)}=\operatorname{MSG}_{1[u=r]}^{(l)}\left(\mathbf{h}_{u}^{(l-1)}\right),$
$\displaystyle\mathbf{h}_{v}^{(l)}=\operatorname{AGG}^{(l)}\left(\left\\{\mathbf{m}_{u}^{(l)},u\in\mathcal{N}(v)\right\\},\mathbf{h}_{v}^{(l-1)}\right).$

$\operatorname{MSG}_{1[u=r]}^{(l)}(\cdot)$ means that
$\operatorname{MSG}_{1}^{(l)}(\cdot)$ is applied to the root node while
$\operatorname{MSG}_{0}^{(l)}(\cdot)$ is applied to other nodes. In this way,
the representation of the root node is different from that of other nodes and
will help distinguish other nodes when propagated to later layers. The
approach is inductive since the colouring is based on the extracted
computation graphs instead of the original graph. Further, in order to avoid
the overhead of extracting ego-networks, ID-GNN-Fast proposes to use the count
of cycles as an augmented node feature. Therefore the input node feature is
built from concatenating the original node feature and the augmented node
feature.

####  4.2.2. Distance information.

Distance measures such as shortest paths between nodes are widely used in
traditional network studies (Brandes, 2008). Naturally, some approaches
propose to enhance the performance of the GCN through including distance
information in their message passing scheme or as an additional initial node
feature.

P-GNN. Position-aware graph neural network (P-GNN) proposes to let each node
aggregate information from several randomly chosen subsets of nodes, instead
of its own 1-hop neighbours (You et al., 2019). As every node shares the same
neighbourhood in P-GNN, distance information is included to indicate the
relative position of each node to those subsets. Specifically, given $k$
randomly sampled subsets, $S_{i}$ denoting the $i$th subset, the
representation of node $v$ at layer $l$ is formulated as:

(74)
$\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}\\}.$

$F$ is a message computation function accounting for both distance information
and feature information of a pair of nodes. The output at the last layer is
constructed with $\mathcal{M}_{i}$ being the $i$th embedding dimension, thus
making the final representation position aware. Note that the subsets are
resampled at each convolution layer, so that each node can aggregate
information from different sets of nodes at each layer.

DE-GNN. Distance-Encoding GNN (DE-GNN) also proposes to improve the GCN’s
expressivity through adding distance information (Li et al., 2020).
Intuitively, for any given node set $S$ whose representation is to be learnt,
other nodes are encoded with their distances to each node of $S$. Formally, DE
of node $u$ with regard to the target node set $S$ is defined as:

(75) $\displaystyle\zeta(u\mid S)=\operatorname{AGG}(\\{\zeta(u\mid v)\mid
v\in S\\}),$ $\displaystyle\zeta(u\mid
v)=f\left(\left((M)_{uv},\left(M^{2}\right)_{uv},\ldots,\left(M^{k}\right)_{uv},\ldots\right)\right),$

where $M=AD^{-1}$ is a matrix of landing probabilities through random
walks,$f$ can be a heuristic function or a learnable neural network. Different
distance measures can be captured by the above equation such as the shortest
path distance or the generalised PageRank score. DE is denoted as DE-$|S|$
according to the size of set $S$. For example, DE-2 when $|S|=2$. One way of
improving the GCN through distance encoding is to use it as an extra node
feature: $h_{v}^{(0)}=CONCAT(x_{v},\zeta(v\mid S))$. Another approach is to
use DE-1 in the layer-wise aggregation:
$h_{v}^{(l+1)}=f_{1}\left(h_{v}^{(l)},\operatorname{AGG}\left(\left\\{(f_{2}\left(h_{u}^{(l)}\right),\zeta(u\mid
v))\right\\}_{u\in V}\right)\right)$. Although DE-GNN adopts minibatch
training, the distance information needs to be computed for every node set and
for all nodes in its extracted L-hop ego-network, leading to a higher
computational cost. Also note that DE-GNN is flexible for tasks on different
levels: DE-1 for node-level tasks, DE-2 for link prediction tasks and DE-3 for
triangle prediction tasks. To highlight that the DE-GNN is suitable for both
node and link-level tasks, we use two colours in its block in Figure 11.

####  4.2.3. Other approaches

Apart from the count of certain subgraphs and the distance information, some