# PolicyClusterGCN: Identifying Efficient Clusters for
Training Graph Convolutional Networks

Saket Gurukar Work done when the author was a graduate student at OSU. The
Ohio State University, Columbus, Ohio, USA  Shaileshh Bojja Venkatakrishnan
The Ohio State University, Columbus, Ohio, USA  Balaraman Ravindran  Indian
Institute of Technology Madras, Chennai, India  Robert Bosch Centre for Data
Science and AI, Chennai, India  Srinivasan Parthasarathy  The Ohio State
University, Columbus, Ohio, USA

###### Abstract

Graph convolutional networks (GCNs) have achieved huge success in several
machine learning (ML) tasks on graph-structured data. Recently, several
sampling techniques have been proposed for the efficient training of GCNs and
to improve the performance of GCNs on ML tasks. Specifically, the subgraph-
based sampling approaches such as ClusterGCN and GraphSAINT have achieved
state-of-the-art performance on the node classification tasks. These subgraph-
based sampling approaches rely on heuristics – such as graph partitioning via
edge cuts – to identify clusters that are then treated as minibatches during
GCN training. In this work, we hypothesize that rather than relying on such
heuristics, one can learn a reinforcement learning (RL) policy to compute
efficient clusters that lead to effective GCN performance. To that end, we
propose PolicyClusterGCN, an online RL framework that can identify good
clusters for GCN training. We develop a novel Markov Decision Process (MDP)
formulation that allows the policy network to predict “importance" weights on
the edges which are then utilized by a clustering algorithm (Graclus) to
compute the clusters. We train the policy network using a standard policy
gradient algorithm where the rewards are computed from the classification
accuracies while training GCN using clusters given by the policy. Experiments
on six real-world datasets and several synthetic datasets show that
PolicyClusterGCN outperforms existing state-of-the-art models on node
classification task.

##  1 Introduction

Graph convolution networks (GCNs) learn high-quality node representations of
graph-structured data. Such representations allow GCN to achieve state-of-the-
art performance on several graph-based machine learning tasks such as node
classification [Perozzi et al., 2014], link prediction [Kipf and Welling,
2016b], molecular graph generation [You et al., 2018], and recommendation
systems [Ying et al., 2018]. However, GCN cannot easily operate on large-scale
graphs as it requires $O(nfl)$ memory [Chiang et al., 2019] where $n,f,$ and
$l$ are the number of nodes, features, and GCN layers, respectively.

Figure 1: Overview of PolicyClusterGCN (best viewed in color)

To improve the efficiency and scaling of GCNs, several sampling-based models
have been proposed recently [Liu et al., 2021]. Liu et al. categorize these
sampling methods as node-wise, layer-wise, and subgraph-based sampling models.
The recent subgraph-based sampling models such as ClusterGCN [Chiang et al.,
2019] and GraphSAINT [Zeng et al., 2019] have shown superior performance on
node classification tasks as compared to GCNs and other sampling models. These
subgraph-based models identify subgraphs (clusters) that are treated as
minibatches for GCN training. The resultant mini-batch training helps improve
the performance (such as node classification) of the GCN and also helps in
scaling GCNs to large graphs.

Subgraph-based based sampling models rely on predetermined heuristics – such
as graph partitioning via edge cuts, or communication volume minimization – to
identify subgraphs (clusters). For instance, ClusterGCN [Chiang et al., 2019]
and DistDGL [Zheng et al., 2020] relies on the clustering algorithm, Metis
[Karypis and Kumar, 1997] to identify clusters while Aligraph [Zhu et al.,
2019] relies on four graph partitioning algorithms to identify clusters.
GraphSAINT [Zeng et al., 2019], on the other hand, relies on random subgraph
sampling techniques to identify subgraphs. These techniques achieve better
performance than GCN by either avoiding the neighborhood expansion problem
[Chiang et al., 2019] in GCN training or by mitigating the high variance in
GCN training through normalization [Zeng et al., 2019].

To the best of our knowledge, such heuristics are oblivious to impact of
formed clusters on GCN training effectiveness. The optimization objective of
GCN [Kipf and Welling, 2016a] suggests that its training performance through
clusters is dependent on both the graph structure of the clusters and the
distribution of labels within the clusters. However, it is difficult to know
apriori which heuristics will lead to the identification of efficient clusters
for a given input graph. Here, a cluster configuration is efficient if it
results in good GCN performance.

Identifying efficient clusters is a hard problem: for $k$ clusters, there
exists $k^{n}$ possible cluster configurations where $n$ is the number of
nodes. Training GCN on $k^{n}$ cluster configurations to find the best
performance is not computationally feasible. Hence, we require systematic
exploration of the possible configurations. To that end, we propose
PolicyClusterGCN, an online reinforcement learning framework that relies on a
novel Markov Decision Process (MDP) formulation for computing clusters. The
MDP policy is parameterized with a neural network. However, using RL approach
to compute efficient clusters is a challenging problem. For instance, a
straightforward approach of designing a policy that directly assigns nodes to
clusters would lead to clusters with a large fraction of nodes without an
immediate edge between them. Hence, we design our policy neural network such
that it predicts an “importance" weight for each edge. Edges that are deemed
unimportant are assigned a low weight and vice-versa by the policy. A standard
edge-cut-based graph partitioning algorithm would then output different
cluster configurations based on the edge weights of the graph. This novel
setup allows the exploration of a diverse set of clusters while including
nodes that are immediately connected in the same clusters. We train the policy
network using a standard policy gradient algorithm where the rewards are
computed from the classification accuracies while training GCN using clusters
given by the policy. Our contributions can be summarized as follows:

  1. 1.

We discover that the choice of clusters has a significant impact on GCN
performance.

  2. 2.

To compute efficient clusters for GCN training, we formulate a novel MDP in
which policy predicts edge weights that are utilized by a clustering algorithm
to compute clusters.

  3. 3.

Our experiments show that GCN trained on clusters identified by
PolicyClusterGCN outperforms existing methods on five real-world datasets.

  4. 4.

We also analyze the clusters computed by PolicyClusterGCN by studying their
graph structure (via synthetic datasets) and label distribution (via label
entropy metric [Chiang et al., 2019]).

##  2 Notations

Notations: Let $G(V,E)$ be the input graph $G$ with $|V|$ and $|E|$ number of
nodes and edges, respectively. Each edge $e=(u,v,w)$ consists of nodes $u$ and
$v$ and has edge weight $w\in\mathbb{Z}^{+}$ that denotes the strength of
connection. Let $A\in\mathbb{R}^{|V|\times|V|}$ and
$\hat{A}\in\mathbb{R}^{|V|\times|V|}$ be the adjacency matrix and normalized
adjacency matrix of graph $G$, respectively. Let $F\in\mathbb{R}^{|V|\times
f}$ be the node features. Let $Z^{(l)}$ be the node embedding at layer $l$
with $Z^{0}=F$ and $W^{(l)}$ be the learning parameters of GCN. The node
labels are denoted by $y_{L}$. Let $\mathcal{T_{G}}$ be the training graph
consisting of all the training nodes and edges incident on those training
nodes. Similarly, let $\mathcal{V_{G}}$ and $\mathcal{T}e_{\mathcal{G}}$ be
the validation and test graphs.

##  3 Methodology

###  3.1 MDP formulation

The overview of PolicyClusterGCN is shown in Figure 1. At a step $t$ in MDP,
the agent selects an action that updates all the edge weights of the graph in
state $s_{t}$. As a result, the MDP transitions to new state $s_{t+1}$. Our
MDP is nonepisodic that continuously trains during each step. We experimented
with episodic MDP formulations, however, we empirically found our presented
MDP design to work better.

Algorithm 1 PolicyClusterGCN

Input: $\mathcal{T_{G}}$ : train graph, $\mathcal{V_{G}}$ : validation graph,
$k$ : num clusters, iters: clustergcn iterations, $\alpha$ : set of discrete
edge weights, $y_{T_{L}}$ and $y_{V_{L}}$: train and validation node labels,
respectively.
Parameters: $\gamma$, $\theta$, $w$, $\alpha^{\theta}$, $\alpha^{w}$,
$\epsilon$, $\epsilon_{start},\epsilon_{end},\epsilon_{decay}$
Output: Cluster configuration.

1: for t = 0, 1, 2, … $T$ do

2: Assign edge weight of edge $i$ where $1\leq i\leq|E|$
$w_{i}=\begin{cases}\pi_{\theta}(s_{t})[i]&\text{with }1-\epsilon\text{
prob.}\\\ random(\alpha)&\text{with }\epsilon\text{ prob.}\end{cases}$

3: Decay $\epsilon$ at each step

4: Update graph $(\mathcal{T_{G^{{}^{\prime}}}})$ with new edge weights.

5: Identify $k$ clusters from $(\mathcal{T_{G^{{}^{\prime}}}})$. Change edge
weight of $k$ clusters to that of $\mathcal{T_{G}}$

6: Train ClusterGCN in Algorithm 2 on the identified clusters of
$\mathcal{T_{G}}$.

7: Compute validation score from the above trained ClusterGCN on
$\mathcal{V_{G}}$.

8: if validation-score $>$ best-validation-score: then

9: cluster_configuration = identified clusters

10: best-validation-score = validation-score

11: end if

12: Compute score of edge i = (u,v) as $sc_{i}=sc_{u}+sc_{v}$
$sc_{u}=\begin{cases}+1&\text{if node label predicted correctly }\\\
-1&\text{otherwise}\end{cases}$

13: $r_{t}=\frac{1}{|E|}\sum sc_{i}$ where $1\leq i\leq|E|$

14: Update parameters $\theta$ and $w$ using equations 1 and 2.

15: end for

16: return cluster_configuration

Agent: Let $\mathcal{S}$ and $\mathcal{A}$ be the state space and action
space, respectively. In this work, a state represents the graph. Let $\alpha$
be the set of possible discrete edge weights on an edge and
$a=(e_{1},\ldots,e_{|E|})$ be the selected edge weights where
$e_{i}\in\alpha$. The edge placement policy can then be defined as a mapping
$\pi:\mathcal{S}\rightarrow\mathcal{A}$ that assigns an edge weight to all the
edges where $\mathcal{A}=\alpha^{|E|}$. The goal of the policy network is to
find a placement policy $\pi$ that results in efficient clusters.

Environment: The environment accepts a graph and its edge weights computed by
the agent as its input. It then partitions the graph into several clusters
based on the edge weights and trains the GCN model on each cluster.

State: A state observation $s\in S$ comprises of training graph
$\mathcal{T_{G}}$ with the following features on each edge $e=(u,v)$ : (1)
concatenation of node features of nodes $u$ and $v$; (2) concatenation of node
embeddings of nodes $u$ and $v$. Here, we utilize an unsupervised graph
representation learning method (UGRL), node2vec [Grover and Leskovec, 2016] to
learn the node embeddings (later, we show in the experiments section, that one
can also choose other UGRL methods for this step); (3) concatenation of
embeddings of 1-hop neighbor nodes of nodes $u$ and $v$. A node’s neighbor
embeddings are aggregated with sum operation. We choose the sum operation as
it allows us to capture the graph neighborhood in an expressive manner [Xu et
al., 2018]; (4) the previous $m$ number of edge weights taken by the policy
$\pi$; (5) the previous $m$ number of rewards received from the environment.
At the initial state $s_{0}$, the previous $m$ edge weights and previous $m$
edge rewards are assigned a value of 1 and 0, respectively.

Action: An action at step $t$ is given by the policy $\pi$:
$a_{t}=\pi(s_{t})=(e_{1},\ldots,e_{|E|})$. To accelerate the exploration phase
through actions, we utilize exponential edge weights. In exponential edge
weights, if there are $p$ number of possible actions, an action $i$ would
correspond to edge weight $2^{i}$ where $0\leq i\leq p$. An edge with $2^{p}$
weight would have the strongest connection and would be less likely to be
eliminated during graph partitioning. The choice of discrete edge weights
instead of continuous edge weights for the actions is primarily due to the
restriction-induced by graph partitioning algorithms (e.g. Metis [Karypis and
Kumar, 1997], Graclus [Dhillon et al., 2007], and MLR-MCL [Satuluri and
Parthasarathy, 2009]).

Algorithm 2 ClusterGCN

Input: $\mathcal{T_{G}}_{1},\mathcal{T_{G}}_{2},...\mathcal{T_{G}}_{k}$ ;
iters, $l$

1: Let
$\mathcal{B}=\\{\mathcal{T_{G}}_{1},\mathcal{T_{G}}_{2},...\mathcal{T_{G}}_{k}\\}$

2: for iter = 1, … $\leq$ iters do

3: $\mathcal{B}\leftarrow$ Permute $\mathcal{B}$ in an uniform random manner.

4: for x in $\mathcal{B}$ do

5: $Z_{x}^{(l+1)}=\sigma(\hat{A}_{\mathcal{G}x}Z_{x}^{(l)}W^{(l)})$ where
$Z_{x}^{(0)}=F_{x}$

6: minimize $\mathcal{L}=\frac{1}{|y_{L}|}{\sum}_{i\in
y_{L}}loss(y_{i},Z_{x,i}^{L})$

7: end for

8: end for

Datasets | Nodes | Edges | Feats | L/C | train/ val/ test | References
---|---|---|---|---|---|---
Romania | 41,773 | 996,404 | 16 | 84 | 0.60 / 0.10 / 0.30 | [Rozemberczki et al., 2019, Wang et al., 2019, Rozemberczki et al., 2020, Yang et al., 2021, Bianconi et al., 2021, Zhou et al., 2022, Auletta et al., 2019, Bouyer and Beni, 2022]
Hungary | 47,538 | 445,774 | 16 | 84 | 0.60 / 0.10 / 0.30
Croatia | 54,573 | 251,652 | 16 | 84 | 0.60 / 0.10 / 0.30
Twitter | 2,403 | 37,154 | 9,073 | 73 | 0.55 / 0.20 / 0.25 | [He and Chan, 2018, He et al., 2018, Yao and He, 2021]
Facebook | 4,039 | 88,234 | 1,283 | 84 | 0.60 / 0.20 / 0.20 | [He and Chan, 2018, Hu et al., 2021, Tang et al., 2022]
Blogcatalog | 5,196 | 343,486 | 8189 | 6 | 0.55 / 0.20 / 0.25 | [Huang et al., 2019, 2018, 2017a, 2017b]

Table 1: Dataset statistics. Feats denotes number of features. L/C denotes
number of labels or classes.

Reward: Now, to identify a good cluster configuration from the space of all
possible cluster configurations, we require a reward signal about the goodness
of a given cluster configuration. Here, we treat the performance (such as node
classification) of GCN on training nodes as the reward signal by training GCN
for a few iterations ($iters$) over the computed clusters. We train GCN for a
small number of iterations (for example, 50 iterations in our experiments) to
get rewards in a short amount of time. Once the GCN model is trained, we
compute a score for each edge $e=(u,v)$ of the training graph by summing
scores of nodes $u$ and $v$. Here, a score for a node is +1 if the node label
is predicted correctly by the trained GCN while -1 otherwise. In the case of
multilabel classification, we compute the score for each label and then sum
the scores. We compute the reward as the mean of all the scores across all the
edges.

###  3.2 Policy Network Architecture

PolicyClusterGCN learns the good cluster configuration of a graph by
parameterizing the MDP policy using a neural network. Here, one could design
the policy network using GCN. However, GCN has a huge memory requirement for
large graphs. Hence, we select a two-layer neural network as our policy
network. The input to the network is the state of edge $i$ and the output of
the network is the predicted edge weight. This design allows the
parallelization of the edge weight prediction task. This policy network design
can also perform the edge weight prediction task for large graphs. The policy
network is trained with a standard policy gradient algorithm.

###  3.3 Training

PolicyClusterGCN is trained with a standard policy gradient algorithm - actor-
critic [Konda and Tsitsiklis, 1999]. Let $\theta$ and $w$ be the policy
parameters (actor) and state-value function parameters (critic), respectively.
Let $r_{t}$ be the received reward obtained by following policy $\pi_{\theta}$
at step $t$. Then the actor and critic parameters are updated as follows:

$\delta\leftarrow r_{t}+\gamma\hat{v}(s_{t+1},w)-\hat{v}(s_{t},w),$ (1)

where $\gamma$ is the discount factor and $\hat{v}$ is the value function and,

$\displaystyle w\leftarrow$ $\displaystyle\textnormal{
}w+\alpha^{w}\delta\textnormal{ }\nabla_{w}\textnormal{ }\hat{v}(s_{t},w)$ (2)
$\displaystyle\theta\leftarrow$ $\displaystyle\textnormal{
}\theta+\alpha^{\theta}\delta\textnormal{ }\nabla_{\theta}\textnormal{ ln
}\pi(a_{t}|s_{t},\theta),$

where $\alpha^{w}>0$ and $\alpha^{\theta}>0$ are the step sizes for actor and
critic parameters and $\mathcal{A}_{t}$ denotes the actions taken by step $t$.

The training algorithm of PolicyClusterGCN is presented in Algorithm 1. In
each step, we update the edge weights of all the edges. Here, given the state
$s_{t}$ at step $t$, we employ an $\epsilon$-greedy method for exploring the
edge weights. We set the edge weight of an edge $i$ to one of the possible
edge weights in a uniform random manner with $\epsilon$ probability and set
the edge-weight of the edge given by the policy network
($\pi_{\theta}(s_{t})[i]$) with $1-\epsilon$ probability. We decay the
$\epsilon$ values as
$\epsilon_{end}+(\epsilon_{start}-\epsilon_{end})\times\exp(-1\times
t/\epsilon_{decay}))$. We update the training graph $\mathcal{T_{G}}$ with the
predicted edge weights.

The change in the edge weights of the graph allows us to explore different
cluster configurations. We identify clusters using a multi-level graph
partitioning algorithm, Graclus [Dhillon et al., 2007] that allows the
identification of imbalanced clusters. Metis [Karypis and Kumar, 1997], on the
other hand, has a load balance constraint that allows limited exploration of
diverse cluster configurations. Once, we identify the clusters, we change the
edge weight of the non-cut edges to that of the original graph. This change is
important as we are interested in identifying good cluster configuration
rather than modifying the input graph.

Next, to compute the reward signal we train the ClusterGCN model (shared in
Algorithm 2). In ClusterGCN, given $k$ clusters, we form
$\mathcal{T_{G}}_{1},\mathcal{T_{G}}_{2},...\mathcal{T_{G}}_{k}$ subgraphs.
Let $\hat{A}_{\mathcal{G}x}\in\mathbb{R}^{n_{x}\times n_{x}}$ be the
normalized adjacency matrix of subgraph $x$ with $n_{x}$ number of nodes. Let
$Z_{x}^{(l)}\in\mathbb{R}^{n_{x}\times f}$ be the node embedding at layer $l$
with $Z_{x}^{0}=F_{x}$ where $F_{x}$ is the initial node features. While
$W^{(l)}$ are the learnable parameters. Then, we train GCN by following the
training procedure outlined in ClusterGCN [Chiang et al., 2019]. The
ClusterGCN training process also includes a parameter ($bsize$) to enable a
stochastic multi-partition approach and we follow the same approach in our
implementation (approach [Chiang et al., 2019], not shown in Algorithm 2 for
expository simplicity). Once we train ClusterGCN, we compute the reward by
following the procedure mentioned in “MDP formulation" section. We also
compute the validation score on the supervised task (such as node
classification) and store the clusters that resulted in the best validation
score. The policy and critic networks are then trained using equations 1 and
2.

##  4 Experiments

Sampling Strategy | Model | Croatia | Romania | Hungary | Facebook | Twitter | Blogcatalog
---|---|---|---|---|---|---|---
| GCN | 0.343 | 0.340 | 0.384 | 0.500 | 0.150 | 0.940
|  | ($\pm$ 0.030) | ($\pm$ 0.034) | ($\pm$ 0.036) | ($\pm$ 0.031) | ($\pm$ 0.015) | ($\pm$ 0.012)
Node wise sampling | GraphSage | 0.355 | 0.352 | 0.399 | 0.478 | 0.132 | 0.933
| ($\pm$0.011) | ($\pm$0.017) | ($\pm$0.024) | ($\pm$0.022) | ($\pm$0.022) | ($\pm$0.005)
| VR-GCN | 0.338 | 0.366 | 0.396 | 0.525 | 0.156 | 0.953
|  | ($\pm$ 0.026) | ($\pm$ 0.030) | ($\pm$ 0.030) | ($\pm$ 0.010) | ($\pm$ 0.055) | ($\pm$ 0.010)
Layer wise sampling | LADIES | 0.403 | 0.377 | 0.422 | 0.459 | 0.137 | 0.889
| ($\pm$ 0.040) | ($\pm$ 0.043) | ($\pm$ 0.043) | ($\pm$0.024) | ($\pm$0.023) | ($\pm$0.006)
| FAST-GCN | 0.404 | 0.375 | 0.383 | 0.368 | 0.115 | 0.832
|  | ($\pm$ 0.075) | ($\pm$ 0.070) | ($\pm$ 0.056) | ($\pm$0.009) | ($\pm$0.034) | ($\pm$0.032)
Subgraph sampling | RippleWalk | 0.359 | 0.358 | 0.406 | 0.466 | 0.144 | 0.877
| ($\pm$ 0.027) | ($\pm$ 0.030) | ($\pm$ 0.0340) | ($\pm$ 0.046) | ($\pm$ 0.052) | ($\pm$ 0.011)
GraphSaint | 0.459 | 0.467 | 0.485 | 0.537 | 0.164 | 0.959
|  | ($\pm$0.005) | ($\pm$0.002) | ($\pm$0.001) | ($\pm$0.007) | ($\pm$0.014) | ($\pm$0.005)
| ClusterGCN | 0.403 | 0.387 | 0.420 | 0.510 | 0.148 | 0.950
|  | ($\pm$0.012) | ($\pm$0.005) | ($\pm$0.043) | ($\pm$0.006) | ($\pm$0.032) | ($\pm$0.004)
| ClusterHOGCN | 0.453 | 0.469 | 0.488 | 0.557 | 0.171 | 0.951
|  | ($\pm$0.003) | ($\pm$0.006) | ($\pm$0.001) | ($\pm$0.013) | ($\pm$0.022) | ($\pm$0.004)
Proposed | PolicyClusterGCN | 0.428 | 0.413 | 0.453 | 0.515 | 0.155 | 0.952
| ($\pm$0.009) | ($\pm$0.001) | ($\pm$0.007) | ($\pm$0.008) | ($\pm$0.024) | ($\pm$0.006)
| PolicyClusterHOGCN | 0.463 | 0.478 | 0.497 | 0.563 | 0.189 | 0.956
|  | ($\pm$0.003) | ($\pm$0.003) | ($\pm$0.001) | ($\pm$0.001) | ($\pm$0.016) | ($\pm$0.006)

Table 2: Test Micro-f1 score on the node classification task. Results averaged
over five independent runs for all the models.

###  4.1 Datasets

We evaluate PolicyClusterGCN on six frequently evaluated datasets. The
statistics of these datasets are presented in Table 1. The column
train/val/test in Table 1 refers to the size of training, validation, and test
splits of the dataset. The Romania, Hungary, and Croatia datasets were
introduced in [Rozemberczki et al., 2019] and extensively used in the
literature. We evaluate models on multilabel classification tasks on Romania,
Hungary, Croatia, Twitter, and Facebook datasets and multiclass classification
on the Blogcatalog dataset. In the case of Twitter and Facebook datasets,
certain labels are present in only a few nodes, hence in our evaluation, we
consider only those labels that are present in at least 10 nodes. Node
attributes are not present for Romania, Hungary, and Croatia datasets. Hence,
we factorize the adjacency matrix of these datasets and treat the 16 left
singular vectors as node attributes [Cukierski et al., 2011].

###  4.2 Baselines

We consider state-of-the-art GCN training models including several models that
perform efficient sampling for GCN training [Liu et al., 2021].

  * •

GCN [Kipf and Welling, 2016a] : Initial graph convolutional network.

  * •

GraphSAGE [Hamilton et al., 2017] : A node sampling based GCN that samples few
l-hop neighbors of nodes to learn the node embeddings.

  * •

VR-GCN [Chen et al., 2018a]: A node sampling based GCN that utilizies
historial activations to sample a smaller number of node’s neighbors.

  * •

FAST-GCN [Chen et al., 2018b]: A layer sampling based GCN that samples new
node neighbors at each layer of GCN.

  * •

LADIES [Zou et al., 2019]: A layer sampling based GCN that utilizes importance
sampling to sample neighbor-dependent nodes at each layer of GCN.

  * •

RippleWalk [Bai et al., 2021]: A subgraph sampling based GCN that propose a
random process to form a subgraph for GCN training.

  * •

GraphSaint [Zeng et al., 2019]: A subgraph sampling based GCN that proposed
samplers for forming subgraph and introduce normalization techniques to
eliminate bias and reduce variance.

  * •

ClusterGCN [Chiang et al., 2019]: A subgraph sampling based GCN that
partitions graphs into multiple clusters and treat each cluster as minibatch
for GCN training.

  * •

PolicyClusterGCN: Our proposed algorithm that performs efficient training of
GCN.

  * •

PolicyClusterHOGCN: Our proposed algorithm where instead of GCN we train
Higher Order GCN (HOGCN) model [Zeng et al., 2019]. Each layer in HOGCN
combines GraphSAGE-concat [Hamilton et al., 2017] layer with MixHop [Abu-El-
Haija et al., 2019] layer. We tune the same HOGCN parameters for both
GraphSaint and PolicyClusterHOGCN.

###  4.3 Training Details

PolicyClusterGCN is implemented in PyTorch. For baselines we utilize the code
provided by the authors. For PolicyClusterGCN we apply Graclus [Dhillon et
al., 2007] partitioning method to formulate clusters.

We set the number of GCN layers to 2 for all the baselines. We tune the
following hyper-parameters for all the baselines: learning rates = [0.01,
0.001], dropouts = [0.0, 0.1, 0.2] and embedding dimensions = [128, 512,
1024]. The number of epochs is set to 1500 for all the models. For GraphSAINT,
we also tune the normalization parameters = [“norm", “norm-nn"] and embedding
aggregation process = [“mean", “concatenation"]. For ClusterGCN and
PolicyClusterGCN, we tune the number of clusters = [4, 8, 16, 32] and number
of clusters for each batch = [1, 4, 8]. For all the models, we perform the
evaluation on the same five train/val/test splits and report the average test
micro-f1 score over five runs. For PolicyClusterGCN, we set the number of
previous edge weights and the number of the previous edge rewards value $m$ to
5. To get the node embeddings, we set the node2vec parameters as walk-
length=40, context-size=5, walks-per-node=20, p=1.0, q=1.0. During
development, we played with the parameters of node2vec and found that
PolicyClusterGCN is not sensitive to those parameters. We train
PolicyClusterGCN on the cluster configuration identified by Algorithm 1.

PolicyClusterGCN parameters: We set the $eps\\_decay$ value to 100. The step
sizes of $\alpha^{w}=0.001$ and $\alpha^{\theta}=0.001$. The discount factor
$\gamma$ is set to 0.95. During development, we played with the following
node2vec parameters: walk-length=[20, 40, 80], context-sizes=[3,5], walks-per-
node=[20, 40]. However, we did not find PolicyClusterGCN to be sensitive with
respect to node2vec parameters.

All the experiments are conducted on a machine with an NVIDIA Tesla V100 (32
GB memory), an Intel Xeon E5-2680 CPU (28 cores, 2.40GHz), and 128 GB of RAM.

##  5 Results

###  5.1 Performance

We compare the node classification performance of PolicyClusterGCN with other
baselines in Table 2. The values in the parenthesis in Table 2 represents
standard deviation. We rely on the Micro-f1 metric for evaluation as it is a
frequently used metric in the literature. We observe that our proposed
PolicyClusterHOGCN outperforms state-of-the-art models on five out of six
real-world datasets. Moreover, our proposed PolicyClusterHOGCN and
PolicyClusterGCN outperform ClusterHOGCN and ClusterGCN on all the datasets.
This result suggests that our approach is able to identify strong cluster
configurations than prior state-of-the-art approaches. The difference in
performance between PolicyClusterHOGCN and other baselines is statistically
significant with a standard paired t-test at a significance level of 0.05.
Another observation is that with HOGCN, the performance of ClusterHOGCN is
close to or often better than that of GraphSAINT. Note that our proposed
framework is not limited to GCN or HOGCN and one can experiment with other
graph convolutional networks design [You et al., 2020] for further improvement
in the supervised task.

(a) Facebook

(b) Twitter

Figure 2: Mean edges reward per PolicyClusterHOGCN step

|  | Croatia | Romania | Hungary | Facebook | Twitter | Blogcatalog
---|---|---|---|---|---|---|---
PolicyClusterHOGCN | Node2vec | 0.463 | 0.478 | 0.497 | 0.563 | 0.189 | 0.956
M-NMF | 0.461 | 0.476 | 0.497 | 0.556 | 0.163 | 0.956
Net-MF | 0.462 | 0.478 | 0.498 | 0.562 | 0.168 | 0.956

Table 3: Robustness: state embedding methods.

|  | Croatia | Romania | Hungary | Facebook | Twitter | Blogcatalog
---|---|---|---|---|---|---|---
PolicyClusterHOGCN | Actor-critic | 0.463 | 0.478 | 0.497 | 0.563 | 0.189 | 0.956
Reinforce | 0.461 | 0.479 | 0.488 | 0.562 | 0.177 | 0.955

Table 4: Robustness: policy gradient methods.

###  5.2 Reward Analysis

Figure 2 shows the mean of mean edge rewards received over five independent
runs. We observe that as the policy network’s training progresses,
PolicyClusterGCN can identify better cluster configurations that result in the
improvement in GCN training performance.

###  5.3 Robustness: State Embedding Methods

We test the sensitivity of the proposed PolicyClusterGCN framework with
respect to the choice of state embedding methods. We consider three UGRL
methods: a random-walk based method, node2vec [Grover and Leskovec, 2016], a
community aware embedding method, M-NMF [Wang et al., 2017], and a matrix
factorization based approach, NetMF [Qiu et al., 2018]. The average results
over five independent runs are presented in Table 3. We observe that
PolicyClusterHOGCN achieves similar performance on all of the six real-world
datasets and is robust to the choice of state embedding method.

LFRμ | ClusterGCN | PolicyClusterGCN | % diff.
---|---|---|---
0.10 | 0.711 | 0.731 | +2.00
0.15 | 0.739 | 0.753 | +1.40
0.20 | 0.552 | 0.561 | +0.90
0.25 | 0.452 | 0.472 | +2.05
0.30 | 0.223 | 0.237 | +1.40
0.35 | 0.193 | 0.201 | +0.80
0.40 | 0.135 | 0.144 | +0.90

Table 5: Synthetic Dataset: LFR. LFRμ corresponds to percentage of inter
cluster links.

###  5.4 Robustness: Policy Gradient Methods

Next, we test the sensitivity of our framework with respect to the training
algorithm. Here, we train PolicyClusterHOGCN with reinforce [Williams, 1992]
and actor-critic [Konda and Tsitsiklis, 1999] algorithms. Table 4 shows the
performance of PolicyClusterHOGCN. We observe that PolicyClusterHOGCN trained
with actor-critic often outperforms PolicyClusterHOGCN trained with the
reinforce algorithm. The performance improvement is likely due to the better
ability of the actor-critic algorithm to reduce gradient variance [Sutton and
Barto, 2018].

###  5.5 Synthetic Datasets

We compare the performance of PolicyClusterHOGCN and ClusterHOGCN on the
synthetic LFR datasets [Lancichinetti et al., 2008]. Each LFR dataset consists
of a set of communities and $\mu$ percentage of inter-community connections.
In this section, we study how the performance of PolicyClusterHOGCN and
PolicyClusterHOGCN changes as we change the value of $\mu$ from 0.1 to 0.4
with a 0.05 step size. We keep the rest of the parameters of the LFR dataset
the same (number of nodes=5,000, average degree=5, min community size=50,
power law exponent for the degree distribution and community size distribution
to 3 and 1.5, respectively). We use cdlib library [Rossetti et al., 2019] for
generating the datasets. A node’s cluster is set as its class and we perform
multi-class classification. For node features, we factorize the adjacency
matrix of these datasets and treat 16 left singular vectors as node
attributes. The test Micro-f1 scores are shared in Table 5. We observe that
PolicyClusterHOGCN is consistently able to identify better clusters as
compared to ClusterHOGCN for all $\mu$ values. However, as the percentage of
inter-community edges increases, the performance between PolicyClusterHOGCN
and ClusterHOGCN decreases. This result is not terribly surprising since at
that point noise (represented by inter-cluster edges) tends to dominate the
signal (represented by node clusters).

(a) Croatia

(b) Croatia

(c) Romania

(d) Romania

(e) Hungary

(f) Hungary

(g) Facebook

(h) Facebook

(i) Twitter

(j) Twitter

(k) Blogcatalog

(l) Blogcatalog

Figure 3: Label Entropy

###  5.6 Cluster Analysis: Label Entropy

The performance of GCN is dependent on both cluster structure and node label
distribution in the cluster. Here, we compare and contrast the node labels
present in the clusters identified by ClusterHOGCN and PolicyClusterHOGCN. For
comparison, we rely on the label entropy metric utilized elsewhere [Chiang et
al., 2019]. To compute a cluster’s label entropy, we assume labels are
independent and a node’s label can have 0 or 1 value. For $q$ labels, cluster
$c$’s label entropy can then be calculated as
$S_{c}=H(X_{1},X_{2},...,X_{q})=H(X_{1})+H(X_{2})+...+H(X_{q})$ where $X_{i}$
is Bernoulli random variable. A dataset’s label entropy is represented through
the distribution of cluster label entropies and consists of $k$ number of
clusters. Since we report the results over five independent runs, our reported
distribution size is $k$ times five. Figure 3 presents the distribution of
cluster label entropies using the kernel density estimation algorithm for six
real-world datasets. We observe that, in general, the distribution of label
entropies of ClusterHOGCN has high variance as compared to that of
PoliyClusterHOGCN which has low variance – see Figure 3a vs 3b, Figure 3e vs
3f, Figure 3k vs 3l. The low variance or high saturated label entropy’s
suggests that PolicyClusterGCN identifies clusters with high label uncertainty
in the clusters.

##  6 Related Work

Graph convolutional neural networks (GCNs) have shown promising results on
several machine learning tasks on graph-structured data. However, GCNs require
the full normalized adjacency matrix of the graph, and hence scaling them on
large networks becomes challenging [Hamilton et al., 2017, Chiang et al.,
2019, Zheng et al., 2020].

A plethora of efficient sampling methods has been proposed to solve the
scalability bottleneck and improve the GCN training [Liu et al., 2021]. The
sampling-based techniques can be categorized as node sampling vs layer
sampling vs subgraph sampling. In node sampling techniques, one usually
samples a fixed number of neighbors per node and forms a subgraph consisting
of multiple connected nodes and their sampled neighbors [Hamilton et al.,
2017]. VR-GCN utilizes the historical activations of nodes in GCN training to
efficiently sample a much smaller number of neighbors per node. Layer
sampling-based method sample usually diverse nodes per GCN layer [Chen et al.,
2018b]. LADIES [Zou et al., 2019] improved the sampling process through
importance sampling.

Subgraph sampling-based GCN approaches have achieved state-of-the-art
performances on the node classification task. These approaches often perform
clustering using graph partitioning algorithms [Chiang et al., 2019, Zheng et
al., 2020, Zhu et al., 2019] and the identified subgraph is treated as a
minibatch for GCN training. RippleWalk [Bai et al., 2021] proposed a novel set
expansion-based subgraph sampling method to construct minibatches. GraphSAINT
[Zeng et al., 2019] proposed several subgraph samplers to identify subgraphs
and also introduced several normalization techniques to reduce the bias and
variance of GCN training.

While we have not evaluated its use for the placement of operations on
computational devices we believe PolicyClusterGCN can be used for such a
purpose (see Placeto [Addanki et al., 2019]). Placeto [Addanki et al., 2019]
learns efficient placement of node (tensorflow operations) on a compute device
(GPUs). Placeto’s single episode has an episode length equal to the number of
nodes in the graph. One episode step places a node to a different cluster and
then passes the modified graph to the environment to get the reward –
rendering the training process to be quite expensive. We believe
PolicyClusterGCN can simplify this task and plan to examine such ideas in the
future.

## Conclusion

We propose PolicyClusterGCN, an online RL based approach, to identify such
efficient cluster configuration for GCN training. PolicyClusterGCN’s policy
network modifies the edge weights of the graph that allows it to explore
diverse cluster configurations. We train the policy network using an actor-
critic algorithm where the reward signal is received through GCN performance.
We perform experiments on six real-world datasets and show that our proposed
model can outperform state-of-the-art baselines.

In the future, we plan to explore two directions for PolicyClusterGCN: add
generalizability functionality and improve scalability. To add the
generalizability functionality, we propose to transform the nodes embedding of
different graphs into a common embedding space and devise an efficient
training algorithm for PolicyClusterGCN. To improve scalability, we plan to
explore multi-level frameworks that rely on graph coarsening to significantly
reduce the size of the graph [Deng et al., 2019, Liang et al., 2021].

##  7 acknowledgements

This material is partially supported by the National Science Foundation (NSF)
under grants CNS-2112471, OAC-2018627, and CCF-2028944. Any opinions, fndings,
and conclusions in this material are those of the author(s) and may not refect
the views of the respective funding agencies.

## References

  * Abu-El-Haija et al. [2019] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan.  Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing.  In _international conference on machine learning_ , pages 21–29. PMLR, 2019.
  * Addanki et al. [2019] Ravichandra Addanki, Shaileshh Bojja Venkatakrishnan, Shreyan Gupta, Hongzi Mao, and Mohammad Alizadeh.  Placeto: Learning generalizable device placement algorithms for distributed machine learning.  _arXiv preprint arXiv:1906.08879_ , 2019.
  * Auletta et al. [2019] Vincenzo Auletta, Diodato Ferraioli, Valeria Fionda, and Gianluigi Greco.  Maximizing the spread of an opinion when tertium datur est.  In _Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems_ , pages 1207–1215, 2019.
  * Bai et al. [2021] Jiyang Bai, Yuxiang Ren, and Jiawei Zhang.  Ripple walk training: A subgraph-based training framework for large and deep graph neural network.  In _2021 International Joint Conference on Neural Networks (IJCNN)_ , pages 1–8. IEEE, 2021.
  * Bianconi et al. [2021] Ginestra Bianconi, Hanlin Sun, Giacomo Rapisardi, and Alex Arenas.  Message-passing approach to epidemic tracing and mitigation with apps.  _Physical Review Research_ , 3(1):L012014, 2021\.
  * Bouyer and Beni [2022] Asgarali Bouyer and Hamid Ahmadi Beni.  Influence maximization problem by leveraging the local traveling and node labeling method for discovering most influential nodes in social networks.  _Physica A: Statistical Mechanics and its Applications_ , 592:126841, 2022.
  * Chen et al. [2018a] Jianfei Chen, Jun Zhu, and Le Song.  Stochastic training of graph convolutional networks with variance reduction.  In _International Conference on Machine Learning_ , pages 941–949, 2018a.
  * Chen et al. [2018b] Jie Chen, Tengfei Ma, and Cao Xiao.  Fastgcn: fast learning with graph convolutional networks via importance sampling.  _arXiv preprint arXiv:1801.10247_ , 2018b.
  * Chiang et al. [2019] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh.  Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks.  In _Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining_, pages 257–266, 2019.
  * Cukierski et al. [2011] William Cukierski et al.  Graph-based features for supervised link prediction.  In _The 2011 International joint conference on neural networks_ , pages 1237–1244. IEEE, 2011.
  * Deng et al. [2019] Chenhui Deng, Zhiqiang Zhao, Yongyu Wang, Zhiru Zhang, and Zhuo Feng.  Graphzoom: A multi-level spectral approach for accurate and scalable graph embedding.  _arXiv preprint arXiv:1910.02370_ , 2019.
  * Dhillon et al. [2007] Inderjit S Dhillon, Yuqiang Guan, and Brian Kulis.  Weighted graph cuts without eigenvectors a multilevel approach.  _IEEE transactions on pattern analysis and machine intelligence_ , 29(11):1944–1957, 2007.
  * Grover and Leskovec [2016] Aditya Grover and Jure Leskovec.  node2vec: Scalable feature learning for networks.  In _Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 855–864, 2016.
  * Hamilton et al. [2017] Will Hamilton, Zhitao Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  _Advances in neural information processing systems_ , 30, 2017.
  * He and Chan [2018] Tiantian He and Keith CC Chan.  Discovering fuzzy structural patterns for graph analytics.  _IEEE Transactions on Fuzzy Systems_ , 26(5):2785–2796, 2018.
  * He et al. [2018] Tiantian He, Keith CC Chan, and Libin Yang.  Clustering in networks with multi-modality attributes.  In _2018 IEEE/WIC/ACM International Conference on Web Intelligence (WI)_ , pages 401–406. IEEE, 2018.
  * Hu et al. [2021] Lun Hu, Xiangyu Pan, and Xin Luo.  Incorporating generalized momentum method to accelerate clustering analysis of complex networks.  In _2021 IEEE 17th International Conference on Automation Science and Engineering (CASE)_ , pages 2051–2056. IEEE, 2021.
  * Huang et al. [2017a] Xiao Huang, Jundong Li, and Xia Hu.  Accelerated attributed network embedding.  In _Proceedings of the 2017 SIAM international conference on data mining_ , pages 633–641. SIAM, 2017a.
  * Huang et al. [2017b] Xiao Huang, Jundong Li, and Xia Hu.  Label informed attributed network embedding.  In _Proceedings of the tenth ACM international conference on web search and data mining_ , pages 731–739, 2017b.
  * Huang et al. [2018] Xiao Huang, Qingquan Song, Jundong Li, and Xia Hu.  Exploring expert cognition for attributed network embedding.  In _Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining_ , pages 270–278, 2018.
  * Huang et al. [2019] Xiao Huang, Qingquan Song, Yuening Li, and Xia Hu.  Graph recurrent networks with attributed random walks.  In _Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 732–740, 2019.
  * Karypis and Kumar [1997] George Karypis and Vipin Kumar.  Metis: A software package for partitioning unstructured graphs, partitioning meshes, and computing fill-reducing orderings of sparse matrices.  1997\.
  * Kipf and Welling [2016a] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  _arXiv preprint arXiv:1609.02907_ , 2016a.
  * Kipf and Welling [2016b] Thomas N Kipf and Max Welling.  Variational graph auto-encoders.  _arXiv preprint arXiv:1611.07308_ , 2016b.
  * Konda and Tsitsiklis [1999] Vijay Konda and John Tsitsiklis.  Actor-critic algorithms.  _Advances in neural information processing systems_ , 12, 1999.
  * Lancichinetti et al. [2008] Andrea Lancichinetti, Santo Fortunato, and Filippo Radicchi.  Benchmark graphs for testing community detection algorithms.  _Physical review E_ , 78(4):046110, 2008.
  * Liang et al. [2021] Jiongqian Liang et al.  Mile: A multi-level framework for scalable graph embedding.  In _Proceedings of the International AAAI Conference on Web and Social Media_ , volume 15, pages 361–372, 2021.
  * Liu et al. [2021] Xin Liu, Mingyu Yan, Lei Deng, Guoqi Li, Xiaochun Ye, and Dongrui Fan.  Sampling methods for efficient training of graph convolutional networks: A survey.  _IEEE/CAA Journal of Automatica Sinica_ , 9(2):205–234, 2021.
  * Perozzi et al. [2014] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena.  Deepwalk: Online learning of social representations.  In _Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 701–710, 2014.
  * Qiu et al. [2018] Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang.  Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vec.  In _Proceedings of the eleventh ACM international conference on web search and data mining_ , pages 459–467, 2018.
  * Rossetti et al. [2019] Giulio Rossetti, Letizia Milli, and Rémy Cazabet.  Cdlib: a python library to extract, compare and evaluate communities from complex networks.  _Applied Network Science_ , 4(1):1–26, 2019.
  * Rozemberczki et al. [2019] Benedek Rozemberczki, Ryan Davies, Rik Sarkar, and Charles Sutton.  Gemsec: Graph embedding with self clustering.  In _Proceedings of the 2019 IEEE/ACM international conference on advances in social networks analysis and mining_ , pages 65–72, 2019.
  * Rozemberczki et al. [2020] Benedek Rozemberczki, Oliver Kiss, and Rik Sarkar.  Little ball of fur: a python library for graph sampling.  In _Proceedings of the 29th ACM International Conference on Information & Knowledge Management_, pages 3133–3140, 2020.
  * Satuluri and Parthasarathy [2009] Venu Satuluri and Srinivasan Parthasarathy.  Scalable graph clustering using stochastic flows: applications to community discovery.  In _Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 737–746, 2009.
  * Sutton and Barto [2018] Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Tang et al. [2022] Zehai Tang, Lun Hu, and Xiangyu Pan.  Detection of link communities in attributed graphs via an approximate bayesian generative model.  In _2022 5th International Conference on Artificial Intelligence and Big Data (ICAIBD)_ , pages 315–320. IEEE, 2022.
  * Wang et al. [2019] Lichen Wang, Bo Zong, Qianqian Ma, Wei Cheng, Jingchao Ni, Wenchao Yu, Yanchi Liu, Dongjin Song, Haifeng Chen, and Yun Fu.  Inductive and unsupervised representation learning on graph structured objects.  In _International conference on learning representations_ , 2019.
  * Wang et al. [2017] Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang.  Community preserving network embedding.  In _Thirty-first AAAI conference on artificial intelligence_ , 2017\.
  * Williams [1992] Ronald J Williams.  Simple statistical gradient-following algorithms for connectionist reinforcement learning.  _Machine learning_ , 8(3):229–256, 1992.
  * Xu et al. [2018] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  _arXiv preprint arXiv:1810.00826_ , 2018.
  * Yang et al. [2021] Hanxuan Yang, Qingchao Kong, Wenji Mao, and Lei Wang.  Boosting hidden graph node classification for large social networks.  In _2021 IEEE International Conference on Intelligence and Security Informatics (ISI)_ , pages 1–6. IEEE, 2021.
  * Yao and He [2021] Lizhong Yao and Tiantian He.  Fuzzy community detection with multi-view correlated topics.  In _IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology_ , pages 307–313, 2021.
  * Ying et al. [2018] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec.  Graph convolutional neural networks for web-scale recommender systems.  In _Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining_, pages 974–983, 2018.
  * You et al. [2018] Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec.  Graph convolutional policy network for goal-directed molecular graph generation.  _Advances in neural information processing systems_ , 31, 2018.
  * You et al. [2020] Jiaxuan You, Zhitao Ying, and Jure Leskovec.  Design space for graph neural networks.  _Advances in Neural Information Processing Systems_ , 33:17009–17021, 2020.
  * Zeng et al. [2019] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna.  Graphsaint: Graph sampling based inductive learning method.  _arXiv preprint arXiv:1907.04931_ , 2019.
  * Zheng et al. [2020] Da Zheng, Chao Ma, Minjie Wang, Jinjing Zhou, Qidong Su, Xiang Song, Quan Gan, Zheng Zhang, and George Karypis.  Distdgl: distributed graph neural network training for billion-scale graphs.  In _2020 IEEE/ACM 10th Workshop on Irregular Applications: Architectures and Algorithms (IA3)_ , pages 36–44. IEEE, 2020.
  * Zhou et al. [2022] Fang Zhou, Chang Su, Shuqi Xu, and Linyuan Lv.  Influence fast or later: Two types of influencers in social networks.  _Chinese Physics B_ , 31(6):068901, 2022.
  * Zhu et al. [2019] Rong Zhu, Kun Zhao, Hongxia Yang, Wei Lin, Chang Zhou, Baole Ai, Yong Li, and Jingren Zhou.  Aligraph: a comprehensive graph neural network platform.  _arXiv preprint arXiv:1902.08730_ , 2019.
  * Zou et al. [2019] Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu.  Layer-dependent importance sampling for training deep and large graph convolutional networks.  _Advances in neural information processing systems_ , 32, 2019.