Local Clustering Graph Neural Networks
Authors: Jiezhong Qiu
Yukuo Cen
Qibin Chen
Chang Zhou
Jingren Zhou
Hongxia Yang
Jie Tang
Venue:  (2021)
Keywords: Graph Neural Networks
Local Clustering
Random Walk on Graphs
Open Graph Benchmark

Abstract: Graph Neural Networks (GNNs), which benefit various real-world problems and applications, have emerged as a powerful technique for learning graph representations. The depth of a GNN model, denoted by $K$, restricts the receptive field of a node to its $K$-hop neighbors and plays a subtle role in the performance of GNNs. Recent works demonstrate how different choices of $K$ produce a trade-off between increasing representation capacity and avoiding over-smoothing. We establish a theoretical connection between GNNs and local clustering, showing that short random-walks in GNNs have a high probability to be stuck at a local cluster. Based on the theoretical analysis, we propose Local Clustering Graph Neural Networks (LCGNN), a GNN learning paradigm that utilizes local clustering to efficiently search for small but compact subgraphs for GNN training and inference. Compared to full-batch GNNs, sampling-based GNNs and graph partition-based GNNs, LCGNN performs comparably or even better, achieving state-of-the-art results on four Open Graph Benchmark (OGB) datasets. The locality of LCGNN allows it to scale to graphs with 100M nodes and 1B edges on a single GPU.

Under review as a conference paper at ICLR 2021
LOCAL CLUSTERING GRAPH NEURAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs), which benefit various real-world problems and applications, have emerged powerful technique for learning graph represen- tations. The depth of a GNN model, denoted by K, restricts the receptive field of node to its K K-hop neighbors and plays subtle role in the performance of GNNs. Recent works demonstrate how different choices of K produce a trade-off between increasing representation capacity and avoiding over-smoothing. We es- tablish a theoretical connection between GNNs and local clustering, showing that short random-walks in GNNs have a high probability to stuck at local clus- ter. Based on the theoretical analysis, we propose Local Clustering Graph Neural Networks (I.CGNN), a GNN learning paradigm that utilizes local clustering to ef- ficiently search for small but compact subgraphs for GNN training and inference. Compared to full-batch GNNs, sampling-basee GNNs and graph partition -aseed GNNs, LCGNN performs comparably
better, achieving state-of-ther ahr results on four Open Graph Benchmark (OGB) datasets. The locality of LCGNN allows it to scale graphs with 100M nodes and IB edges on single GPU.
INTRODUCTION
Recent emergence of the Graph Neural Networks (GNNs). exemplified by models like ChebyNet (Defferrard al., 2016). GCN (Kipf Welling 2017). GraphSAGE (Hamilton et al. 2.17 GAT (Veličković et al. al. 2018). and GIN (Xu et al.) 2019), has drastically reshaped the land- scape of the graph learning research. These methods generalize traditional deep learning algorithms to model graph-structured data by combining graph propagation and neural networks. Despite its conceptual simplicity, GNNs have reestablished the new state-of-the-an methods in various graph learning tasks. such as node classification, link prediction, and graph classification (Hu et al.) 20200] Dwivedi et al., 2020), also served as key contributors to many real-world applications, such as rec- ommendation system (Ying et al. 2018), smart transportation (Luo et al. 2020). visual question answering (Teney et al. (017)) and molecular de-novo design (You et al. 2018).
With the growth of real-world social and information networks (Leskovec al. 2005 there is an urgent need to scale GNNs to massive graphs. For example, the recommendation systems in Alibaba (Zhu et al. (209)) and Pinterest (Ying et al. 2018) require training and inferring GNNs on graphs with billions of edges. Building such large-scale GNNs, however, is a notoriously expensive process. For instance, the GNN models in Pinterest are trained on 500GB machine with 16 Tesla K80 GPUs, and served on Hadoop cluster with 378 d2. 8xlarge Amazon AWS machines.
Although one may think model parameters are the main contributors the huge resource con- sumption of GNNs, previous work (Ma et al. 2019) suggests the main bottleneck actually comes from the entanglement between graph propagation and neural networks, which leads to a large and irregular computation graph for GNNs. This problem is further exacerbated by the small-world phe- nomenon (Watts & Strogatz, 1998), i.e., even a relatively small number of graph propagation can involve full-graph computation. For example, in Facebook college graphs of John Hopkins (Traud ct al. 2012), the 2-hop neighbors of node I, as shown in Fig. la covers 74.5% of the whole graph.
A common strategy reduce the overhead of GNNs is to make the graph smaller but may bring side effects. For instance, graph sampling techniques, such as neighborhood sampling in Graph- SAGE (Hamilton al. 2017). may lead to the high variance issue (Chen al.) 2018a). Alter- natively, graph partition techniques, such as METIS (Karypis & Kumar 1998) that adopted by Cluster-GCN (Chiang et al. 2019) and AliGraph (Zhu et al. 2019), essentially involves extra full-

---

Under review as a conference paper at ICLR 2021
(a) 2-hop neighbors of node covers 74.5% of the graph. (b) A local cluster around node 1.
Figure Motivating examples from the John Hopkins graph.
graph computation for preprocessing. Besides reducing graph size, a recent attempt (Wu et al. 2019) to scale up GNNs is to decouple graph propagation and neural networks. However, such simplification may sacrifice certain performances.
In this work, we explore a theoretically guaranteed strategy, local clustering (Spielman & Teng 2013 Anndersen et al., 2006), intending to design a lightweight, effective and scalable GNN frame- work. We establish connection between GNNs and local clustering theory, showing that the graph propagation in GNNs (i.e., short random-walk) has high probability to be stuck at a local clus- ter (a.k.a, community), and the escaping probability is proportional to the conductance of the local cluster. We propose Local Clustering Graph Neural Networks (LCGNN), which utilizes local clus- tering algorithms to seek local and dense subgraphs (e.g.. Fig. Tbb for GNN training and inference. Different from full-batch and graph partition- methods, LCGNN does not incur full- full-graph processing and can be conducted locally. Compared to various baselines, LCGNN achieves state- of-the-art results in four Open Graph Benchmark (Hu et al.) (220)) datasets. Moreover, the locality nature of LCGNN allows it to scale to graphs with 100M nodes and IB edges on a single GPU.
The rest of the paper is organized follows. Section 2 givess brief background summary followed by a survey of related works in section 3 In section 4 and section we establish the connection between GNNs and local clustering, and then describe our LCGNN framework. Section 6 presents the experimental results and ablation study. Finally, we concludes this work in section
2 BACKGROUND
In this section, bring the necessary background about graph, graph convolutional net- works (GCN), (lazy) random walk on graphs, and graph conductance.
The graph G (V, E, A) consists of [V| nodes and |E| = edges. A E RTx" is the adjacency matrix where its entry Aii,j), if nonzero, denote there is an edge between node and j with edge weight A,j In this work, we assume the input graph is undirected and unweighted, and our analysis can be generalized to the weighted graph case easily. For undirected graph, the degree matrix D e diag(d(1),
Graph Notations
d(n)) is a diagonal matrix where d(i) Σ, Aii, is the degree of node i. Moreover, each node in G is associated with F F-dimensional feature vector, denoted by a; E TR. The entire feature matrix X E R= the concatenation of node feature vectors. There are two matrices that play importance roles in the design and analysis of GCN (Kipf) & &Welling, 2017) the normalized graph Laplacian L A D D-1/2 1-2//AD AD-1/2
1/2 and the random walk transition probability matrix P AD- Note that the entry j(i,j) indicates the probability that the random walk goes from node j to node
Graph Convolutional Networks (GCN) GCN (Kipf & Welling 2017) initializes the node repre- sentation as the input feature matrix O)) + X, and iteratively apply non-linear transformation and graph propagation on node representation: (k) <- ReL.U (k (w()), where left multiply- ing H (k-1) by normalized graph Laplacian L acts as the graph propagation, and right multiplying H (k-1) by W as well as the ReLU GGooro et al. 2011)) activation acts as the non-linear transfor- mation. For the node classification task, K-layer GCN predicts node labels Y with softmax
2

---

Under review as a conference paper at ICLR 2021
classifier: Y softmax
Take two-layer GCN (K 2) as a running exam- ple, the predicted node labels Y is defined as Y +- softmax (LReLU (LH w
Lazy Random Walk In practice, many GNNs add (weighted) self-loops to the graphs (A <- A +.,, Kipt & Welling (2077); : Xu et (2019) create residual connections (He et a 2016) in neural networks (Li et al. 2019 Dehmamy et al. 2019). Such techniques can be viewed as variants of lazy random walk on graphs at every step, with probability 1/2 the walker stays the current node (through a self-loop) and with probability 1/2 the walker travels to neighbor. The transition matrix of lazy random walk is M - (I + AD 1/2. In this work, we mainly consider lazy random walk. Because has several desired properties and it is consistent with the actual situation.
Graph Conductance For an undirected unweighted graph G = (V, E, A), the graph volume of any non-empty node set S C V is defined as vol(S) - Eies d(i), which measures the total number of edges incident from S. The conductance of non-empty node set S C V is defined as Eies Ejev-s A(t,)) Roughly speaking, conductance ((S) is the ratio of the number of ((S) min voll(
edges across and V - to the number of edges incident from S. measuring the clusterability of subset S. Low conductance indicates a good cluster because its internal connections are significantly richer than its external connections. Although it is NP-hard to minimize conductance (Síma & Schaeffer 2006). there have been theoretically-guarattee clusters near a given node that satisfy target conductance condition, such as Spielman & Teng (2013) Andersen et al. (2006); (hhngg(2007).
approximation algorithms that identity
3 RELATED WORK
The design of scalable GNNs has attracted wide attention from the machine learning community. We review related work from three perspectives: (1) full-batch GNNs with co-design of systems and algorithms; (2) sampling-basee -based GNNs; (3) graph partition-based GNNs.
Full-batch GNNs A full-batch GNN takes whole graph as input for forward and backward. Consequently, its computational cost is proportional to the graph size. Earlier GNN models (Kipt & Welling 2017 Veličković et al. 2018) evaluated on relatively small graphs. thus can be trained in a bull-batch manner. Scaling full-batch GNNs to large graphs requires the co-design of ML systems and MI. algorithms (Tiang al. 2020 Zhang et al. 2020 Ma et al. 2019). For example, NeuGraph (Ma et al.) 2019) runs futl-batch GNN models on graph with 8.6M nodes and 231.6M edges on an eight-PI00-GEP It simplifies GCN by conducting graph propagation and classification separately and efficiently. However, such simplification may sacrifice performance in some downstream tasks.
server. SGC (Wu et al. 2019) is another attempt at full-batch GNN.
GNNs based on Graph Sampling GraphSAGE (Hamilton et al. 2017) first proposed the idea of neighborhood sampling, and later was applied in real-world recommendation system by Pin- SAGE (Ying et al.) 2018). At each GNN layer, GraphSAGE computes node representation by first down-sampling its neighborhoods and then aggregating the sampled ones. As a randomized algo- rithm, Neighborhood Sampling was further improved by FastGCN (Chen et al. 2018b), Stochastic GCN (Chen et al. 2018a) and Adaptive Sampling (Huang et al. 2018) for variance reduction. A recent work about sampling-bass based GNN is GraphSAINT (Zeng et al. 2020). which samples sub- graphs (Leskovec & Faloutsos 2006) and run full-batch GNN on sampled subgraphs.
GNNs based on Graph Partition Cluster-GCN (Chiang et al., 2019) is the most related work to ours. Cluster-GCN adopts global graph partition algorithms, METIS (aryypis & Kumar 1998), to partition the input graph into subgraphs, and run a GNN on each subgraph. A similar idea was also proposed in AliGraph (Zhu et al., (019).. However, global graph partition algorithms involve additional whole graph computation. Moreover, global graph partition algorithms vulnerable to dynamic and evolving graphs (Xu et al. 2014 /Vaquero et al. 2014), with nodes and edges being constantly added and removed, which are very common in real-world applications.
3

---

Under review as a conference paper at ICLR 2021
4 SHORT RANDOM WALK AS LOCAL CLUSTERING
Most GNNs adopt short random walks to explore graph. For example, the default 2-1ayer GCN in Kipf & Welling (2117) can be viewed as enumerating all length-2 paths and aggregating them with neural network; Hamilton et al. (0177) uses a 2-hop neighborhood sampling method, a variant of 2- hop random walk, to sample neighbors each GraphSAGE layer. GraphS (Zeng et al. 2020) samples subgraphs by 2-hop random walks and then build a full-batch GCN on them. SGC (Wu cet al. 2019) conducts 2-hop feature propagation and then apply node-wise logistic regression.
We reveal the theoretical connection between short random walk and local clustering. To be more formal, let g(k) be the K-th step lazy random-walk distribution starting from an arbitrary node according to transition probability matrix M, i.c., q(k) <- M Iy We want to study the proba- bility vector g(K) in terms of K, especially when K is small (e.g.. = 2). Due to the the small world phenomenon (Watts & Strogatz 1998), for most social/information networks, g(k) can have Onn) non-zeros, even K is small, e.g., K = 2 or 3. However, the following theorem shows that the probability that a random walk escaping from a local cluster can be bounded by its conductance:
Theorem 1 (Escaping Mass, Proposition 2.5 in Spielman & Teng (003)). For all K 2 and all S C V. the probability that any K K-step lazy random walk staring in S escapes S is at most ($) Le., the escaping probability satisfies q (V - S) < (5))22
The key point of Theomre His to relate the K-th step random- walk probability to graph conductance for node u. suppose there exists subset S such that (I) E S and (2) (SS) is small (low conductance), Theorem [ guarantees that the probability that a lazy random walk starting from node is very likely to be stuck S, revealing the following facts and potential problems of existing GNNs: (1) for full-batch GNNs, although its receptive field induced by K-hop neighbors may cover the whole graph, most probability mass still concentrates around local cluster (if exists), and the remaining probabilities (i.e., escaping mass) are small and bounded. Consequently, the computation methods can be viewed a randomized and implicit version of finding a local clustering, however, with their sample-effiiinncy and variance non- -uaranaandtee.. The above facts encourage us to design local flustering-based GNNs.
cost of full-batch GNNs can be largely reduced; (2) Sampling-
A crucial question about the above analysis is the existence of a low-conductance S for every node (or most nodes in the graph). This is generally not true for arbitrary graphs, e-g., a complete graph. However, evidence from network science and social science agrees with our assumption. For example, (1) Many networks of interest in the sciences are found to divide naturally into com- munities (Girvan & Newman 2002 Newman 2006); (2) Real-world social networks consist of compact communities with size scale of around 100 nodes (Leskovec et al., 2209);; (3) Roughly 150 individuals the upper limit the size of well-functioning human community (Dunbar 1998).
LOCAL CLUSTERING GRAPH NEURAL NETWORKS (LCGNN)
The analysis in section lays the theoretical foundation of the design of our LCGNN framework. In the section, we formally introduce LCGNN. Roughly speaking, framework consists of two steps. In the first step, for each node u E V, we run local clustering to produces local cluster S, surrounding it. In the second step, we feed the subgraph induced by S, to GNN encoder.
5.1 LOCAL CLUSTERING
Local clustering algorithms find a small cluster near given seed(s). Different from global graph partition methods involving full-graph computation, local clustering conducts local exploration in the graph and its running time depends only on the size of the output cluster. Over the past two decades, many local clustering algorithms have been developed (Spielman & Teng 2013 Andersen
et al., 2006 Chung 2007 Li et al.) 2015) Kloster Gleich| 2014 Kloumann & Kleinberg 2014] Whang et al. 2013 Yin et al., 2017| Fountoulakis
al. 2019). In this works, we mainly focus on Nibble (Andersen et al. 2006), one of the most popular spectral- based local clustering al- gorithms among the above methods. As its name indicates, PPR-Nibble adopts the personalized PageRank (PPR) vector for local clustering. The PPR vector p.. of a node u is given by equation Pr. al, + - a:) Pp... which is the stationary distribution of the following random walk: at each
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1: Approximate-PRR
Input Graph G (V, E, A), seed node u, teleportation parameter a, tolerance 6;
Output An e-approximate PPR vector p.::
Pu <- r < 1,;
while r(v)/d(o) 2 e for some V do
p o+ r(v) 2 dd(v;; (v) + Pu(v) + op: r(o) _d(r);
for each (u, u) E E do
r(u) + r(u) + A(v.u) (1 a)pp
d(o)
return p.::
Algorithm 2: PPR-Nibble.
Input Graph G = (V, E, A). seed node u, teleportation parameter a, tolerance e; Output A local cluster $ C V:
Pa. < Approximate-PPRO (PRii, u, c); a, f i-th largest entry of D 'P:
return S' arg ming, (S²).. where S (01, oz):
step of the random walk, with probability a the walker teleports back to the node u, and with prob- ability 1 1-c a the walker performs a normal random walk. However, PPR vector is a dense vector and thus computationally expensive. Andersen et al. (2006) developed an efficient algorithm, named Approximate-PPP1 to compute its sparse approximation Pa, so that (v))
(c)))/((v) S for each node t. As shown in Algorithm [1 the key idea is to gradually push probabilities from residual vector to approximate PPR vector P.. (Line 5-7 of Algorithm 1. After computing the approximate PPR vector Pu. a sweep procedure
then adopted to extract a cluster with small conductance (S)). More formally, the sweep procedure first sort nodes according to D Pu in descending order (Line 4 of Algorithm 2 and then evaluate the conductance of each node prefix in the sorted list and output the one with smallest conductance (Line 5 of Algorithm 2).
Note that PPR-Nibble is local algorithm (Spielman & Teng 2013) with theoretical guarantee- - (1) The input to the algorithm is a starting node u, (2) At each step of Approximate-PPP in Algorithm I it only examines nodes connected to those it has seen before. The following theorems characterize the complexity and error bounds of Approximate-PPR of PPR-Nibble, respectively.
Theorem (Lemma in Andersen al. (006)). Algorithm runs in time O ( (dc). and the number of non-zeros in P., satisfies anz(P.))
ae
Theorem 3 (Theorem in Zhu et al.] (013);; Theorem 4.3 in Yin et al. (017)). Let S C V be some unknown targeted cluster, inverse mixing time of the random walk on the subgraph induced by S. Then there exists $ C S
trying retrieve from an unweighted graph. Let be the
with vS9 Z vol(S)/2, such that for any seed E S9, Algorithm 2 with O(1) and
outputs set S with ((S) < δ minn { (VO(T), (()()))((I)))))
[0 vol[T]
5.2 LOCAL CLUSTER ENCODER
For each node u E V, PPR-Nibble in Algorithm 2 produces a local cluster S. C V with |Sa| < 1 We denote G,, to be the subgraph induced by the cluster S,,. which is then encoded to hidden representation via an encoder (usually a GNN model): h,, + ENCODER The encoded hidden representation can be further used for various graph learning tasks. For the node classification task, we predict the label of node u with a softmax classifier: yo + softmax hh,,, + b): For the link prediction task, we measure the likelihood of link e (u, v) by first element-wisely multiplying h and h, and then feeding it to a MLP encoder, i.e., <- MLP(h,, @ h.).
The choice of the encoder is flexible. In this work, we mainly examine four candidate encoders:
GCNGATT/GaaPSSGG encoders Our first candidate encoders are traditional GNNs such as GCN, GAT, and GraphSAGE, We denote them L.GNNNGCC...ATTSAGGE respectively.
5

---

Under review as a conference paper at ICLR 2021
Table 1: Statisties of datasets for node classification and link prediction tasks.
Category
Name
#Nodes
#Edges
Split Ratio
Metric
products
2,449,029
61,859,140
10/02/88 54/18/28
Accuracy
Node ogbn-
arxiv
169,343
1,166,243
Accuracy
papers100M
111,059,956
1,615,685,877
78/8/14
Accuracy
Link
ppa
576,289
30,326,273
70/20/10
Hits@r 100 50
collah
235,868
1,285,465
92/4/4
ogbl-
citation
2,927,963
30,561,187
98/1/1
MRR
Transformer Encoder We also examine more complex and powerful encoder based Trans- former (Vaswani et al. 2017). Our hypothesis that low conductance subgraphs extracted by local clustering have such rich internal connections that Thus we adopt the Transformer encoder whose attention mechanism allows dense interaction within subgraph. We initialize the positional embedding in Transfomer the pre-trained Node2vec em- bedding on the input graph. We denote the Transformer-baan encoder as LCGNN-Transfonne
almost treat them complete graphs.
EXPERIMENTS
In this section, we conduct experiments on two major tasks of graph learning, node classification and link prediction. For each task, we use the datasets from Open Graph Benchmark (OGB) (Hu et al. 2020). which presents significant challenges of scalability to large-scale graphs and out-of- distribution generalization. The dataset statistics are summarized graph classification, is not explored in our experiments because it is unnecessary utilize local clustering for small graphs with only hundreds of nodes. The average and standard deviation of test performance under 10 different seeds are reported in all experiments. For the local cluster- ing algorithm, we use the software provided by Fountoulakis et al.] (2018). We set a = 0,15 in Approximate-PPRs and constraint the maximum cluster size be 64 128 in the PPR-Nibble step, i.e, the sweep procedure only examines the prefix of first 64 (128) nodes in Algorithm g Detailed hyper-parameter configuration of LCGNN can be found in Appendix A.2
Table [ Another graph task,
6.1 NODE CLASSIFICATION
Node classification datasets include products, arxiv, and pupers/00M at different scales. We train LCGNN on a single GPU on all three datasets. Limited by space, the results of the arxiv dataset are reported in the Appendix A.l because relatively small datasets are not target scenario.
Baselines. The OGB team provides MLP, Node2vec (Grover Leskoved 2016), GCN (Kipf & Welling, 2017). GraphSAGE (Hamilton et al., 2017) as the common baselines for products and arxiv datasets. For the large-scale papersI00M dataset, the OGB team only provides MLP, Node2vec, and SGC (Wu et al.) 2019). Other teams and researchers also contribute numerous models to the leaderboards: For the products dataset, three GAT-based models with different mini-batch training techniques are also reported. DeeperGCN (Li et al.) 2020) explores how to design and train deep GCNs. UniMP (Shi al. 2020) is a most recent mode which combines feature propagation and label propagation.
Results. The results of products and papers100M datasets are listed in the Table and Table 3 respectively. In papers100M dataset, SGC (Wu et al. 2019) is the only reported GNN model that can handle this large-scale dataset with more than billion edges. SGC gets better performance than Node2vec and MLP due to the expressive power of (simplified) graph convolution. Com- pared with SGC, LCGNN uses a semi-supervised manner and can learn feature transformation in the training procedure. Our proposed LCGNN obtains better performance than SGC with 2.73% absolute improvement, which shows stronger expressiveness of our model. In products dataset, gets comparable results with other state-of-the-art GNN models.
our LCGNN (rank in Table 2 The arxiv dataset is relatively small and well-tuned full-bath GNNs achieve the best results. Our
UniMP was submitted OGB leaderboard on Sep 8, 2020, in month before ICLR 2021 deadline.

---

Under review as a conference paper at ICLR 2021
Table 2: ogbn-products leaderboard (collected on Oct. 1, 2020). Limited by paper space, we only list top results. denotes that the results are submitted in one month before ICLR 2021 deadline.
Method
Test Accuracy
Validation Accuracy
#Params
GCN
0.7564 + 0.0021
0,9200 0.0003
103,727
GraphSAGE
0.7850 + 0.0014
0.9224 0.0007
206,895
ClusterGCN (SAGE aggr)
0.7897 + 0.0033
0.9212 0.0009
206,895
GraphSAINT (SAGE aggr)
0.7908 + 0.0024
0.9162 + 0.0008
206,895
NeighborSampling (GAT aggr)
0.7945 + 0.0059
1,51,557
GraphSAINT (GAT aggr)
0.8027 + 0.0026
331,661
DeeperGCN
0.8098 + 0.0020
0.9238 0.0009
253,743
UniMP
0.8256 + 0.0031
0.9308 0.0017
1,475,605
LCGNN-GGE
0.7683 + 0.0035
0.9259 0.0009
132,015
LOGNN-SAGE
0.7858 1 0.0027
0.9254 0.0009
194,479
LCGNN-GAT
0,8080 1 0.0025
0.9285 1 0.0013
329,263
LCGNN- LCGNN-Transtormer
0.8131 1 0.0059
0.9249 0.0008
85,167
Table 3: ogbn-papers 100M leaderboard (collected on Oct. 1, 2020)
Method
Test Accuracy
Validation Accuracy
#Params
MLP
0.4724 = 0.0031
0.4960 0.0029
144,044
Node2vec
0.5560 = 0.0023
0,5807 = 0.0028
14,215,818,411
SGC
0.6329 + 0.0019
0.6648 + 0.0020
144,044
LCGNN- Transformer
0.6602 + 0.0007
0.6930 = 0.0006
437,036
LCGNN gets comparable results to full-batch GNNs and achieves better results than sampling-based GNNs (such as GAT with neighbor sampling), as shown in the Table 7 in the Appendix A.
Ablation Study. Table 2 suggests that LCGNN-GCN and LCGNN-SAGE surpass the correspond- ing full-batch GCN and GraphSAGE. Furthermore, ACGNN-SAGE and LCGNN-GAT perform competitively or even better on products dataset comparing to corresponding GraphSAGE and GAT models with other training and sampling techniques, including Neighborhood Sampling (Hamilton) et al. 2017). ClusterGCN (Chiang et al. 2019), and GraphSAINT (Zeng et al. 2020).
6.2 LINK PREDICTION
We evaluate LCGNN on three link prediction tasks ppa, collab, and citation. We use a single GPU to train on the collab dataset and use multi-GPUs train on the ppa and citation datasets (5 GPUs for ppa and 4 GPUs for citation).
Baselines. The OGB team provides Matrix Factorization, Node2vec (Grover & Leskoved 2016), GCN (Kipf & Welling 2017), GraphSAGE (Hamilton et al. 2017) as the common baselines. For the citation dataset, GCN/SAGE- are also provided by the OGB team. Other researchers also contribute some state-of-the-an mod- els to the leaderboards. DeepWalk (Perozzi et al., 2014) submitted by other researchers using DGL. (Wang et al.) 2019). LRGA+GCN (Puny et al.) (020) is a recently proposed model which aligns 2-folklore Weisfeiler-Lehnee algorithm improve the generalization of GNNs.
models with three different mini-batch training techniques
Table 4: ogbl-ppa leaderboard (collected on Oct. 1, 2020)
Method
Test Hits 100
Validation Hits @ 100
#Params
GraphSAGE
0.105511.00200
0.1724 +0.0264
424,449
GCN
0.1867=0.0132
0.1845 +0.0140
278,529
Node2vee
0.2026=:0.0083
0.2253 10.0088
73,878,913
DeepWalk
0..055-
130,138,741
Matrix Factorization
0.3229++000994
0.3228 +-0.0488
147,662,849
IRRAA GCN
0.3426+000110
L.GNN- Transformer
0.3535 + 0.0115
0.3569 + 0.0129
306,304

---

Under review as a conference paper at ICLR 2021
Table 5: ogbl-collab leaderboard (collected on Oct. 2020)
Method
Test Hits@ 50
Validation Hits @0 50
#Params
Matrix Factorization
0.3886=0.0022
0.4896+10.0029
60,514,049
GCN
0.4475=0.0107
0.5263=+0.0115
296,449
GraphSAGE
0.4810=0.0081
0.5688++000007
460,289
Node2vec
0.0005
0.5703++0.0052
30,322,945
DeepWalk
0.5037=+000034
61, 1877
LRGA + GCN
0.5221=0.0072
0.608810.0059
1,069,489
LCGNN-GCN
0.5351 + 0.0202
0.6009 0.0190
50,304
LCGNN-SAA -SAGE
0.5315 + 0.0124
0,5997 + 0.0141
99,840
LCGNN- Transformer
0.5485 + 0.0068
0.6432 1 0.0074
414,848
Table 6: ogbl-citation leaderboard (collected Oct. 1, 2020)
Method
Test H0
Validation Hits @50
#Params
Matrix Factorization
0.5316 0.0565
0,531 0.0565
281,113,505
Node2vec
0.5964 0.0011
0.5944 0.0011
374,911,100
GraphSAINT (GCN aggr)
0.7943 1 0.0043
0.7933 1 0.0046
296,449
ClusterGCN (GCN aggr)
0.8021 + 0.0029
0.7999 + 0.0027
296,449
NeiphborSampling (SAGE aggr)
0.8048 = 0.0015
0.8048 + 0.0015
460,289
GraphSAGE
0.8228 0.0084
0.8217 0.0086
460,289
WeepWalk
0.8284 = 0.0005
757. ,19,
GCN
0.8456 + 0.01 10
0.8449 + 0.0108
296,449
LCGNN-Transformes
0.8524 = 0.0046
0.8510 + 0.0046
315,264
Results. The results of ppa, collab, and citation datasets are listed in the Table 5 and respec- tively. We compare LCGNN with a recently developed model, LRGA+GCN (Puny as well as traditional baselines. For all three datasets for link prediction, our proposed LCGNN achieves the best results over ttat--ff-the-art models with 0.68% 2.64% absolute improvements, showing the ability of local clustering and Transfomer encoder to boost link fik-prediction performance.
2020)
Ablation Study. We report the results the collab when the Transformer encoder is replaced with GCN and GraphSAGE encoders. Compared with full-batch GCN and GraphSAGE, our LCGNN- GCN and LCGNN-SAGE obtains much better performance, which suggests the significance of graph local clustering. ACGNN-Transfoone SAGE due to the powerful expressiveness the Transformer encoder.
gets better results than LCGNN-GCN and LCGNN-
Overall, not only LCGNN achieves four first places ogbl-citation) and one second place (ogbu-products) on OGB datasets, also improves the scalabil- ity of GNN models for large-scale graphs.
1omper100,, 00m, ogbl-ppa, ogbl-collab, and
7 CONCLUSION
In this work, we present Local Clustering Graph Neural Networks (LCGNN), a lightweight, effec- tive, and scalable GNN framework with theoretical guarantees. LCGNN combines local clustering algorithms and graph neural network models to achieve state-of-the too-the-art performance on four Open Graph Benchmark (OGB) datasets. By incorporating local clustering algorithms, LCGNN can run on compact and small subgraphs without conducting full-graph computation, scaling to graphs with 100 million nodes and I billion edges on a single GPU. the future, it would be interesting to try advanced local clustering algorithms other than the Pib-Nib Applying LCGNN in real-world applications, such as the recommendation system, is also a promising direction.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. In FOCS '06, 2006.
Lukas Biewald. Experiment tracking with weights and biases, 2020. Software available from wandb.com.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In ICML '18, 2018a.
Jie Chen, Tengfei Ma and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. ICLR '8, 2018b.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. /CML '20, 2020.
Wei-Lin Chiang, Xuanqing Liu, Si Si. Yang Li. Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In KDD '19, 2019.
Fan Chung. The heat kernel as the pagerank of graph. PNAS '07, 2007.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurlPS '1, 2016.
Nima Dehmamy, Albert-László Barabási, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. In NeurlPS '19, 2019.
Chenhui Deng, Zhiqiang Zhao, Yongyu Wang. Zhiru Zhang, and Zhuo Feng. Graphzoom: multi- level spectral approach for accurate and scalable graph embedding. ICLR '20, 2020.
Robin Dunbar. Grooming, gossip, and the evolution of language. Harvard University Press, 1998.
Vijay Prakash Dwivedi, Chaitanya K Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. arXiv preprint arXiv:2003.00982 2020.
Kimon Fountoulakis, David F Gleich, and Michael W Mahoney. A short introduction to local graph clustering methods and software. Book of Abstracts for 7th International Conference on Complex Networks and Their Applications, 2018.
Kimon Fountoulakis, Farbod Roosta- Roosta-Khorann Khorasani, Julian Shun, Xiang Cheng, and Michael W Ma- honey. Variational perspective on local graph clustering. Mathematical Programming. 174(1-2): 553-573, 2019.
Michelle Girvan and Mark EJ Newman. Community structure in social and biological networks. PNAS '0, 2002.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In AISTATS '11, 2011.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. KDD '16 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In NeurlPS 11, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR 16, 2016.
Weihua Hu, Mauthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurlPS '20, 2020.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In NewrIPS '1, 2018.

---

Under review as a conference paper at ICLR 2021
Jiawei Jiang, Pin Xiao, Lele Yu, Xiaosen Li, Jiefeng Cheng, Xupeng Miao, Zhipeng Zhang, and Bin Cui. Psgraph: How tencent trains extremely large-scale graphs with spark? In ICDE '20, 2020.
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning irreg- ular graphs. SIAM Journal scientific Computing, 1998.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. ICLR 17, 2017.
Kyle Kloster and David F Gleich. Heat kernel based community detection. In KDD '14, 2014.
Isabel M Kloumann and Jon Kleinberg. Community membership identification from small seed sets. In KDD '4, 2014.
Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In KDD '06, 2006.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graphs over time: densification laws, shrink- ing diameters and possible explanations. In KDD '05, 2005.
Jure Leskovec, Kevin J Lang, Anirban Dasgupta, and Michael W Mahoney, Community structure in large networks: Natural cluster sizes and the absence of large well-defined clusters. Internet Mathematics, 2009.
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In ICCV "19, 2019.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprini arXiv:2006.077338 2020.
Yixuan Li, Kun He, David Bindel, and John Hopcroft. Uncovering the small community structure in large networks: A local spectral approach. In WWW '15, 2015.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In KDD '20, 2020.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. In ICLR '19, 2019.
Wenjuan Luo, Han Zhang, Xiaodi Yang, Lin Bo, Xiaoqing Yang. Zang Li, Xiaohu Qie, and Jieping Ye. Dynamic heterogeneous graph neural network for real-time event prediction. In KDD '20, 2020.
Lingxiao Ma, Zhi Yang, Youshan Miao, Jilong Xue, Ming Wu, Lidong Zhou, and Yafei Dai. Neu- graph: parallel deep neural network computation on large graphs. In USENIX ATC '19, 2019.
Mark EJ Newman. Modularity and community structure in networks. PNAS '06, 2006.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In KDD '14, 2014.
Omri Puny, Heli Ben-Hamu, and Yaron Lipman. From graph low-rank global attention to 2-fwl approximation. ICML 2020 Workshop of Graph Representation Learning and Beyond, 2020.
Yunsheng Shi, Zhengjie Huang, Shikun Feng, and Yu Sun. Masked label prediction: Unified mas- sage passing model for semi-supervised classification. arXiv preprint arXiv:2009.03500) 2020.
Jifí Šíma and Satu Elisa Schaeffer. On the np-completeness of some graph cluster measures. In International Conference on Current Trends in Theory and Practice of Computer Science, 2006.
Daniel A Spielman and Shang-Hua Teng. A local clustering algorithm for massive graphs and its application to nearly linear time graph partitioning, SIAM Journal on computing. 2013.
Damien Teney, Lingqiao Liu, and Anton Den Hengel. Graph-structured representations for visual question answering. In CVPR 17, 2017.
Amanda Traud, Peter J Mucha, and Mason A Porter. Social structure of facebook networks.
Physica A: Statistical Mechanics and its Applications, (116))):165--118 2012.
10

---

Under review as a conference paper at ICLR 2021
Luis M Vaquero, Felix Cuadrado, Dionysios Logothetis, and Claudio Martella. Adaptive partitioning for large-scale dynamic graphs. In ICDCS '14, 2014.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NeurIPS '17, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR '1, 2018.
Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang- Deep graph library: A graph-centrie, highly-performan package for graph neural networks. arXiv preprint arXiv: 1909.01315, 2019.
Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world" networks. Nature, 1998.
Joyce Jiyoung Whang, David F Gleich, and Inderjit S Dhillon. Overlapping community detection using seed set expansion. CIKM 11, 2013.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simpli- fying graph convolutional networks. In ICML 19, 2019.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. ICML '18 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? ICLR 2019.
Ning Xu, Lei Chen, and Bin Cui. Loggp: a log-based dynamic graph partitioning method. VLDB 144 2014.
Hao Yin, Austin R Benson, Jure Leskovec, and David F Gleich. Local higher-order graph clustering. In KDD '17, 2017.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. KDD '18, 2018.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In NewrIPS '18, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. ICLR '20, 2020.
Dalong Zhang, Xin Huang, Ziqi Liu, Zhiyang Hu, Xianzheng Song, Zhibang Ge, Zhiqiang Zhang, Lin Wang, Jun Zhou, and Yuan Qi. Agl: a scalable system for industrial-purpose graph machine learning. VLDB '20, 2020.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Din Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. UA/ '18, 2018.
Rong Zhu, Kun Zhao, Hongxia Yang. Wei Lin, Chang Zhou, Baole Ai, Yong Li, and Jingren Zhou. Aligraph: a comprehensive graph neural network platform. VLDB '19, 2019.
Zeyuan Allen Zhu, Silvio Lattanzi, and Vahab Mirrokni. A local algorithm for finding well- connected clusters. In ICML '1, 2013.
11

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 EXPERIMENTAL RESULTS
We report the results of the ogbn-arxiv dataset in the Table 7 There are some models that are only evaluated on the smallest dataset (i.e., ogbn-arxiv), including GraphZoom (Deng et al., 2020) GaAN (Zhang et al. 2018). DAGNN (Liu et al. 2020), JKNet (Xu al. 2 GCNII (Chen al. 2020). Most of these models cannot handle ogbn-products with millions of nodes. Our LCGNN models get comparable results with most state-of-the-ard GNN models with and without mini-batch training techniques.
Table 7: ogbn-arxiv leaderboard (collected Oct. 1, 2020). denotes that the result is run by ourselves. denotes that the results are submitted one month before ICLR 2021 deadline.
Method
Test Accuracy
Validation Accuracy
#Params
MLP
0.5550 11 0.0023
0.5765 0.0012
110,120
Node2vec
0.7007 1:: 0.0013
0.7129 0.0013
21,818,792
GraphZoom (Node2vec)
0.7118 1:: 0.0018
0.7220
0.0007
8,963,624
GraphSAGE
0.7149 + 0.0027
0.7277 = 0.0016
218,664
GCN
0.7174 = 0.0029
0.7300 0.0017
142,888
DeeperGCN
0.7192 0.0016
0.7262 0.0014
491,176
GaAN
0.7197 + 0.0024
1,471,506
DAGNN
0.7209 + 0.0025
0.7290 + 0.0011
43,857
NeighhorSampling (GAT aggr)f
0.7211 + 0.0030
0.7308 + 0.0014
762,256
JKNet (GCN)
0.7219 + 0.0021
0.7335 0.0007
89,000
GCNII
0.7274 1 0.0016
2,148.648
GCN*
0.7306 1 0.0024
0.7442 0.0012
238,632
UniMPs
0.7311 + 0.0020
0.7450 + 0.0005
473,489
GAT
0.7365 - 0.0011
0.7504 0.0006
1,628,440
UniMP large"
0.7379 + 0.0014
0.7475 0.0008
1,162,515
LCGNN-GCN
0.7198 = 0.0018
0.7357
0.0012
171,560
LCGNN-SAGE
0.7210 0.0025
0.7342 0.0019
204,328
LCGNN-GAY
0.7213 + 0.0011
0.7346
0.0011
172,200
LCGNN-Trransfomnn
0.7222 + 0.0022
0.7303 0.0010
136,936
A.2 EXPERIMENTAL SETUP
A.2.1 RUNNING ENVIRONMENT
We run our experiments on a single machine with Intel Xeon CPUs (Platinum 8163 @ 2.50GHz), 330GB memory, and 8 NVIDIA Tesla V100 (16GB). The code is written in Python 3.6. We use PyTorch 1.5.1 on CUDA 10.1 to train our models.
A.2.2 HYPERPARAMETER CONFIGURATION
For our models, the optimizer used in our experiments is AdamW (Loshchilov Hutter 2019) with 31 0.9, 82 0.999, and eps 10 For CEGGNN-GCNSSGG/GGANN no warmup steps. But for LCGNN, we use the following learning rate scheduler with warmup steps, similar to Transformer (Vaswani et al. 2017) except extra hyper- parameer Ir_scale:
use this optimizer with
Ir = Ir.scale d min(step.num 0.5
step_num warmup_steps 11.3
We use the wandb (Biewald 2020) tool to help track experiments and search the hyperparameters. The final papee-parameters used for our models listed in the Table and Table
12

---

Under review as a conference paper at ICLR 2021
Table 8: Hyper-pan paree-parameters for JCGNN-Transformes on OGB datasets. denotes that it is trained on multi-GPUs of a single machine (5 GPUs for ppa and 4 GPUs for citation).
ogbn-
ogbl- collab
Hyper-parameters
products
arxiv
papers 100M
ppa
citation
number of layers
3
5
4
number of heads
2
1
maximum cluster size
64
64
64
64
128
64
hidden size
64
128
input dropout
0.2
0.2
0.2
0.1
0.1
0.1
hidden dropout
0.5
0.5
0.4
0,4
0.4
0.4
batch size
256
256
512
5120*
128
6000*
Ir scale
1.0
1.0
2.0
0.5
weight decay
0.05
0.05
0.0005
0.0005
warmup steps
20000
10000
10000
5000
20000
10000
Table dyper-parameters for LCGNN-GCNVSAGEGGAT on OGB datasets
ogbn-arxiv
ogbl-collab
parameeparreetess
GCN
SAGE
GAT
GCN
SAGE
GAT
GCN
SAGE
number of layers
4
4
3
5
4
5
number of heads
1
1
maximum cluster size
128
128
128
128
128
hidden size hidden dropout batch size
128
128
256
128
128
128
128
128
0.3
0.3
0.4
0.4
0.4
0.3
0.0
0.0
512
512
512
512
512
512
512
512
learning rate
0.002
0.002
0.002
0.004
0.002
0.002
0.001
0.001
weight decay
0.0005
0.0005
0.005
0.0005
0.0
0.005
batch norm
True
True
True
True
True
True
True
True
residual connection
True
True
True
True
True
True
False
False
13


Reviews:
[{"review_id": "vKmg1NmLAR1", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nThe authors proposed to first extract a subgraph $G_u$ for each node $u$. Then use GNNs to extract the hidden representation $h_u = GNN(G_u)$. The subgraph extraction uses PPR-Nibble with is a conductance based local clustering method. \n\nPros:\n1.\tThe model seems to be more efficient compare to GNN with global clustering method such as Cluster-GCN.\n2.\tUsing local clustering method to determine the subgraph for each node might be better than random neighborhood sampling in some cases.\n\nCons:\n1.\tThe intuition on using short random walk is problematic. (See detailed comments)\n2.\tThe experimental results are insufficient to verify the proposed method.\n3.\tInsufficient related work on local clustering and PageRank-based methods.\n4.\tWhile the authors claim that they have theoretical analysis, all stated theorems are from the other papers. I do not aware of any theoretical contribution as claimed by the authors. \n\nDetailed comments:\n\nThe main weakness of the paper is the claim that short random walk is sufficient to extract topology information from graph. This contradicts to both [1] and [2]. In [1], the authors used Personalized PageRank (PPR) to build their GNN (APPNP) which shows that large propagation step is helpful ($K=10-20$). Notably, they show that using $K\\geq 10$ gives significant improvement on Cora and PubMed dataset for node classification problem compare to using $K\\leq 5$. On the other hand, the authors of [2] study the generalized PageRank method for local clustering (seed-set community detection) problem. They show that using large step propagation ($K\\geq 10$) leads to better local clustering performance compare to small steps. These works show that using merely short random walk is insufficient to fully extract the topological information from graphs and thus the claim by the authors seems questionable to me.\n\nThe other weakness of this paper is their experimental results are insufficient to verify the proposed method outperforms the sampling-base method. For example, in Table 2 the test accuracy of LCGNN-SAGE is actually lower than GraphSAINT (SAGE aggr). Even if we compare LCGNN-GAT with GraphSAINT(GAT-aggr) the gain is not obvious. The model proposed by the authors that has the best performance is LCGNN-Transformer. However, it is not clear whether the performance gain is due to the local clustering procedure or the transformer.\n\nMinor comments:\nAs the authors mentioned, the local clustering methodology is only reasonable for graphs that has low conductance with respect to all \"cluster\" (nodes with same label). This is exactly the \"Homophily principle\" which is true for most of the popular benchmark datasets such as citation networks (Core, Citeseer and PubMed). However, as pointed out in [3], there are also practical graphs that are heterophilic or low homophily. Although this is not the main theme of this paper, the existence of heterophilic graph should not be ignored.\n\nReference:\n\n[1] “Predict then Propagate: Graph Neural Networks meet Personalized PageRank,” Klicpera et al., ICLR 2018.\n\n[2] “Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection,” Li et al., NeurIPS 2019.\n\n[3] “Geom-GCN: Geometric Graph Convolutional Networks,” Pei et al., ICLR 2020.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "dP5KCOFiBa_", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary:\nThis paper proposes to utilize local clustering to efficiently search for small but compact subgraphs for Graph Neural Networks (GNN) training and inference. The existing PPR-Nibble is adopted for the local clustering search. Experiments validate the effectiveness of the proposed method.\n\n##########################################################################\n\nPros:\n+ The paper is clear and well organized. \n+ The idea of using local clustering to design a lightweight, effective and scalable GNN framework is interesting.  \n+ The analysis of the connection between GNNs and local clustering is also interesting. \n+ Extensive experiments are conducted to validate the effectiveness of the proposed method.\n\n##########################################################################\n\nCons:\n- One major concern about the paper is the lack of novelty. Although the idea of using local clustering is very interesting, it is straightforward to apply an existing local clustering algorithm into GNN especially considering the existing methods that utilize the global graph partition.   \n\n- In the introduction, it is claimed that the graph sampling techniques may lead to the high variance issue, while from the experiment, we can see that compared to SOTA sampling methods (e.g. GraphSAINT), the proposed method has larger variance actually. The reason for this should be given.\n\n- The advantage of the proposed method over the methods based on global graph partition (e.g., ClusterGCN) is not well illustrated. \n\n- In Table 6, only the result with \"LCGNN-Transformer\" is provided, and it is not clear whether the improvement is caused by the transformer encoder. The comparison of the learning paradigm is missing. For better comparison, especially with ClusterGCN, the result of \"LCGNN-GCN\" is expected. \n\nMinor issues:\n- In the paper, it is claimed that \"Compared to full-batch GNNs, sampling-based GNNs and graph partition-based GNNs, LCGNN performs comparably or even better...\", while from the experiments, we can see that it can be worse for some tasks. Moreover, the improvement may be not mainly caused by LCGNN itself. It is better to make this clearer.\n\n##########################################################################\n\nQuestions during the rebuttal period:\nPlease address and clarify the cons above.", "extra_scores": {}, "extra_text": {}}, {"review_id": "_tX2xrxgwG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This is an interesting work on GCN. The idea is to form local graph for each node using PPR-Nibble, a local clustering method proposed before, and then use transformer on top of the local graph as encoder for node classification and link prediction. The algorithm is simple and easy to understand. I have several concerns for this paper:\n\n1) It seems that the local clustering+transformer encoder performs best, while it is hard to tell whether local clustering is the key to this improvement. In Table 2, local clustering + GCN encoder performs even worse than most of GCN methods, which might indicate the local clustering is not useful. In other words, what if other comparing GCN methods are also using transformer encoder? Without this study, it is hard to tell what is the novelty of this paper and whether the local clustering is useful.\n\n2) What is the time complexity of this method? It seems the proposed method is very computation expensive. As it needs to form transformer for each node in the graph, not even to mention the time for PPR-Nibble for each node as well. This method might be even slower than GCN itself.\n\n3) All the theorems are not derived by this paper, but from other papers on PPR-Nibble. Will these theorems have assumptions about the underlying graphs? And will this theorem works for the graphs in the experiment parts? Do the proposed method only work with nodes with small numbers of neighbors? \n\n4)  Besides PPR-Nibble, there are many local clustering methods or even using on-line clustering so that the whole graph is not needed to fit into the memory to form the clustering, it will be interesting to see how various clustering methods work under the framework. \n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "5Ky7GL1uR0H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[Summary]\nIn this paper, the authors study the connection between GNNs and local clustering, and find that short random-walks in GNNs have a high probability to be stuck at a local cluster. Based on this, they propose a light and scalable GNN learning framework called LCGNN, which first adopts the local clustering method PPR-Nibble to partition full graph into subgraphs, then use GNN modules on subgraphs for training and inference. The authors evaluate LCGNN on six OGB datasets, and the proposed approach outperforms the competitors on node classification and link prediction tasks.\n\n[Pros]\n+ The paper is well organized and easy to follow.\n+ The idea of incorporating local clustering algorithms for GNN learning is simple but effective in terms of scalability.\n\n[Cons]\n- The proposed method is somewhat incremental since it only adds a local clustering step (with an existing clustering method) before adopting GNN models.\n- The experiment is not very sufficient and supportive. \n  1. From Table 2, it seems that the improvement of incorporating local clustering (comparing LCGNN-GCN/LCGNN-SAGE with naïve GCN/SAGE) is not very large, and we could not find how much the local clustering improves Transformer. Similar problems appear in Table 3, 4, 6 – most performance improvement seems to come from the adoption of Transformer.\n  2. How do clustering hyperparameters $\\alpha$ and the maximum cluster size affect the results?\n  3. No visualization for the clustering results or the learned node embeddings, which could help understand the effect of local clustering, is presented. \n- Time and space complexity of the proposed framework is not provided. Intuitively the proposed method might enjoy better time and space complexity than existing methods, but some theoretical analysis or runtime evaluation would be better to illustrate the main claim of this paper.\n- Could LCGNN handle the situation when nodes and edges are constantly added and removed?\n- The authors claim that ‘the locality nature of LCGNN allows it to scale to graphs with 100M nodes and 1B edges on a single GPU’ but use 8 NVIDIA Tesla V100 in their experiments. Some results or explanation might be helpful to support this claim.\n- There are many typos to be corrected.\n  (a) Page 1: covers => cover\n  (b) Page 2: we concludes => we conclude\n  (c) Page 2: importance roles => important roles\n  (d) Page 4: the the small world phenomenon => the small world phenomenon; staring in S => starting in S; I.e., => i.e., (cannot be used at the beginning of the sentence); The key point of Theomre 1 => The key point of Theorem 1; In this works => In this work\nOther minor issues: It would be better to highlight the second best value in Table 2.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper considers using local spectral graph clustering methods such at the PPR-Nibble method for graph neural networks.  These local spectral methods are widely used in social networks, and understanding neural networks from them is interesting.

In many ways, the results are interesting and novel, and they deserve to be more widely known, but there are several directions to make the work more useful to the community.   These are outlined in the reviewer comments, which the authors answered partially but not completely satisfactorily.  Much of this has to do with explaining how/where these (these very fundamental and ubiquitous) methods are useful in a particular application (GNNs here, and node embeddings below).  An example of a paper that successfully did this is "LASAGNE: Locality And Structure Aware Graph Node Embedding, E. Faerman, et al.  Proc. 2018 Conference on Web Intelligence."  (That is mentioned not since it is directly relevant to this paper, but since it provides an example of how to present the use of a method such as PPR-Nibble for the community.
Decision: Reject