Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences
Authors: Meng Liu
Shuiwang Ji
Venue:  (2021)
Keywords: Graph representation learning
large-scale
sequence

Abstract: Modern Graph Neural Networks (GNNs) follow a recursive neighbor-wise message passing scheme and have achieved great success in many fields. However, this recursive design brings expensive computation and huge memory usage, making it difficult to deploy on large-scale graphs. In this work, we propose Neighbor2Seq, which transforms the hierarchical neighborhood of each node into an ordered sequence and enables the subsequent utilization of general deep learning operations, such as convolution and attention. Neighbor2Seq grants our proposed models, i.e., Neighbor2Seq-Conv and Neighbor2Seq-Attn, the ability to learn on arbitrarily large graphs as long as the Neighbor2Seq step can be precomputed. Another potential advantage obtained by the way is that Neighbor2Seq can alleviate the over-squashing issue existing in modern GNNs. We conduct thorough experiments on a massive graph with more than 111 million nodes and 1.6 billion edges, as well as several medium-scale graphs, to evaluate our proposed method. Experimental results demonstrate that our proposed method is scalable to the massive graph and achieves superior performance across datasets.

Under review as a conference paper at ICLR 2021
NEIGHBOR2SEQ: DEEP LEARNING ON MASSIVE GRAPHS BY TRANSFORMING NEIGHBORS TO SE- QUENCES
Anonymous authors Paper under doublc-blind review
ABSTRACT
Modern graph neural networks (GNNs) use message passing scheme and have achieved great success in many fields. However, this recursive design inherently leads to excessive computation and memory requirements, making it not applica- ble to massive real-world graphs. In this work, we propose the Neighbor2Seq to transform the hierarchical neighborhood of each node into sequence. This novel transformation enables the subsequent use general deep learning operations, such as convolution and attention, that designed for grid-like data. Therefore, our Neighbor2Seq naturally endows GNNs with the efficiency and advantages of deep learning operations on grid-like data by precomputing the Neighbor2Seq transformations. In addition, our Neighbor2Seq can alleviate the over-squashing issue suffered by GNNs based on message passing. We evaluate our method on a massive graph, with more than 111 million nodes and 1.6 billion edges, as well as several medium-scal graphs. Results show that our proposed method scalable to massive graphs and achieves superior performance across massive and medium- scale graphs.
INTRODUCTION
Graph neural networks (GNNs) have shown effectiveness in many fields with rich relational struc- tures, such as citation networks (Kipf & Welling 2016; Veličković et al. 2018). social net- works (Hamilton et al. 2017). drug discovery (Gilmer al.) 2017 Stokes et al. 2020), physical systems (Battaglia et al. (016)) and point clouds (Wang et al. 2019). Most current GNNs follow a message passing scheme (Gilmer et al. 2017 Battaglia et al. 2018), in which the representation of each node is recursively updated by aggregating the representations of its neighbors. Various GNNs (Li et al. 2016 Kipf & Welling, 2016 Veličković et al. 2018 Xu et al. 2019) mainly differ in the forms of aggregation functions.
Real-world applications usually generate massive graphs, such as social networks. However, mes- sage passing methods have difficulties in handling such large graphs the recursive message pass- ing mechanism leads to prohibitive computation and memory requirements. To date, sampling meth-
ods (Hamilton et al.] [2017] Ying et al. [2018; Chen al. 2018a bl Huang al. 2018 Zou et al.) 2019 Zeng et al. 2200 Gao et al. 2018 Chiang et al. 2019 Zeng et al. 2020) and precomput- ing methods (Wu al. 2019 Rossi al. 2020 Bojchevski et al. 2020) have been proposed to scale GNNs on large graphs. While the sampling methods can speed up training, they might result in redundancy, still incur high computational complexity, lead to loss performance, or introduce bias (see Section 2.2). Generally, precomputing methods can scale to larger graphs as compared to sampling methods as recursive message passing is still required in sampling methods.
In this work, we propose the Neighbor2Seq that transforms the hierarchical neighborhood of each node to a sequence a precomputing step. After the Neighbor2Seq transformation, each node and its associated neighborhood tree are converted to an ordered sequence. Therefore, each node can be viewed as an independent sample and is no longer constrained by the topological structure. This novel transformation from graphs grid-like data enables the use of mini- batch training for subsequent models. As a result, our models can used on extremely large graphs, as long as the Neighbor2Seq step can be precomputed.

---

Under review as a conference paper at ICLR 2021
As radical departure from existing precomputing methods, we consider the hierarchical neighbor- hood of each node as an ordered sequence. The order information corresponds to hops between nodes. As result of our Neighbor2Seq transformation, generic deep learning operations for grid- like data, such as convolution and attention, can be applied in subsequent models. In addition, our Neighhor2Seq can alleviate the over-squashing issue (Alon & Yahav| 2020) suffered by current GNNs. Experimental results indicate that our proposed method can be used on a massive graph, where most current methods cannot be applied. Furthermore, our method achieves superior perfor- mance as compared with previous sampling and precomputing methods.
ANALYSIS OF CURRENT GRAPH NEURAL NETWORK METHODS
We start by defining necessary notations. A graph is formally defined as G = EV, where V is the set of nodes and E' S V x V is the set of edges. We use n [V| and m = =E] to denote the numbers of nodes and edges, respectively. The nodes are indexed from 1 to n. We consider a node feature matrix X E R= where each row I; R is the d-dimensional feature vector associated with node i. The topology information of the graph is encoded in the adjacency matrix A E R=x*, where A (..)) = 1 if an edge exists between node and node j, and A A(s.)) = 0 otherwise.
2.1 GRAPH NEURAL NETWORKS VIA MESSAGE PASSING
There are two primary deep learning methods on graphs (Bronstein et al.): those are, spectral meth- ods and spatial methods. The spectral method in Bruna al. (2014) extends convolutional neural networks (LeCun et al. 1989) to the graph domain based on the spectrum of the graph Laplacian. The main limitation of spectral methods is the high complexity. ChebNet (Defferrard et al. 2016) and GCN (Kipf& & Welling (016) simplify the spectral methods and can be understood from the spa- tial perspective. In this work, we focus on the analysis of the current mainstream spatial methods. Generally, most existing spatial methods, such as ChebNet (Defferrard et al.) 2016), GCN (Kipf & Welling 20166) GG-NN (Li al.) 2016). GAT (Veličković et 2018). and GIN (Xu et al., 2019), can be understood from the message passing perspective (Gilmer et al. 2017 Battaglia et al., 2018 Specifically, we iteratively update node representations by aggregating representations from its immediate neighbors. These message passing methods have been shown to be effective in many fields. However, they have inherent difficulties when applied on large graphs due to their excessive computation and memory requirements, as described in Section 2.2
2.2 GRAPH NEURAL NETWORKS ON LARGE GRAPHS
The above message passing methods are often trained in full batch. This requires the whole graph, i.e., all the node representations and edge connections, to be in memory to allow recursive message passing on the whole graph. Usually, the number of neighbors grows very rapidly with the increase of receptive field. Hence, these methods cannot be applied directly on large-scale graphs due to the prohibitive requirements on computation and memory. To enable deep learning on large graphs, two families of methods have been proposed; those methods based on sampling and precomputing.
To circumvent the recursive expansion of neighbors across layers, sampling methods apply GNNs on sampled subset of nodes with mini-batch training. Sampling methods can be further divided into three categories. First, node-wise sampling methods perform message passing for each node in its sampled neighborhood. This strategy is first proposed in GraphS (Hamilton et al. 2017). where neighbors are randomly sampled. This is extended by PinS AGE (Ying et al. 2018). which selects neighbors based on random walks. VR-GCN (Chen et al. 2018a) further proposes to use variance reduction techniques to obtain convergence guarantee. Although these node-wise sam- pling methods can reduce computation, the remaining computation still very expensive and some redundancy might have been introduced, as described in HHung et al.] (2018). Second, layer-wise sampling methods sample a fixed number of nodes for each layer. In particular, FasIGCN (Chen) et al. 201 8b) samples fixed number of nodes for each layer independently based on the degree of each node. AS-GCN (Huang et al. 2018) and LADIES (Zou et al. (219)) introduce between- layer dependencies during sampling, thus alleviating the loss of information. Layer- wise sampling meth- ods can avoid the redundancy introduced by node-wise sampling methods. However, the expensive sampling algorithms that aim to ensure performance may themselves incur high computational cost,
2

---

Under review as a conference paper at ICLR 2021
pointed out in Zeng al. (2020). Third, graph wise sampling methods build mini mini-batches on sampled subgraphs. Specifically, LGCN (Gao et al. 2018) proposes to leverage mini- maiihbbtch training on subgraphs selected by Sreadth-First-Searee algorithms. ClusterGCN (Chiang et al., (019)) con- ducts mini-batch training on sampled subgraphs that are obtained by graph clustering algorithm. GraphSAINT (Zen et al., 2020) proposes to derive subgraphs by importance-sampling and intro- duces normalization techniques to eliminate biases. These graph-wise sampling methods usually have high efficiency. The main limitation is that the nodes in a sampled subgraph are usually clus- tered together. This implies that two distant nodes in the original graph usually cannot be feeded into the GNNs in the same mini-batch during training, potentially leading to bias in the trained models.
The second family of methods for enabling GNNs training on large graphs are based on procomput- ing. Specifically, SGC (Wu al., 2019) removes the non-linearity between GCN layers, resulting in a simplification as Y = softmax (A (A*X W)). In this formulation, À = AD is the sym- metrically normalized adjacency matrix, Á = A + is the adjacency matrix with self-loops, D is the corresponding diagonal node degree matrix with D(i.)) = E, A(..)- is the size of receptive field (i.e., the number of considered neighboring hops), which is the same as a L-layer GCN, Y is the output of the softmax classifier. Since there is no learnable parameters in Á X. this term can be precomputed as a feature pre-processing step. Similarly, SIGN (Rossi al. 2020) applies an inception-like model the precomputed features Å for & E {1,-.., L}. where Ls the prede- fined size of receptive field. Instead of precomputing the smoothing features as in SGC and SIGN, PPRGo (Bojchevski al. 2020) extends the idea of PPNP (Klicpera et al. 2018 by approximately precomputing the personalized PageRank (Page et al. 1999) matrix, thereby enabling model training on large graphs using bati-batches. Generally, the precomputing methods can scale larger graphs than sampling methods because the latter still needs to perform the recursive message passing during training. Differing from these precomputing methods, we consider the hierarchical neighborhood of each node as ordered sequence, thus retaining the useful information about hops between nodes and enabling subsequent powerful and efficient operations.
3 THE PROPOSED NEIGHBOR2SEQ METHOD AND ANALYSIS
In this section, we describe our proposed method, known as Neighbor2Seq, which transforms the hierarchical neighborhood of each node into ordered sequence, thus enabling the subsequent use of general deep learning operations. We analyze the scalability of our method (See Section 3.5) and describe how our method can alleviate the over-squashing issue suffered by current message passing methods (See Section 3.6).
3.1 OVERVIEW
As described in Section 2.1 existing message passing methods recursively update each node's 's rep- resentation by aggregating information from its immediate neighbors. Hence, what these methods aim capturing for each node is essentially its corresponding hierarchical neighborhood, i.e., the neighborhood tree rooted at current node, as illustrated in Figure (b). In this work, we attempt go beyond the message passing scheme to overcome the limitations mentioned in Section 2 We propose to capture the information of this hierarchical neighborhood by transforming it into an or- dered sequence, instead of recursively squashing into a fixed-length vector. Our proposed method is composed of three steps. First, we transform neighborhood to sequence for each node. Second, we apply a normalization technique to the derived sequence features. Third, we use general deep learning operations, i.e., convolution and attention, to learn from these sequence features and then make predictions for nodes. the following, we describe these three steps in detail.
3.2 NEIGHBOR2SEQ: TRANSFORMING NEIGHBORHOODS TO SEQUENCES
The basic idea of Neighbor2Seq is to transform the hierarchical neighborhood of each node to an ordered sequence by integrating the features of nodes in each layer of the neighborhood tree. Fol- lowing the notations defined in Section 2 we let z/ ... 2 denote the resulting sequence for node i, where L is the height (i.e., the number of hops we consider) of the neighborhood tree rooted node 2 Rdd denotes the (-th feature of the sequence. The length of the resulting sequence for
3

---

Under review as a conference paper at ICLR 2021
(a)
(b)
Neighbor2Scq Conv
Average Pool
Normaliattion
Post ona ancoding
Learnable
Neighhor2Soq
Query
(d)
Figure 1: (a) An illustration of the original graph. The current node is denoted as two concentric
circles. (b) Message passing in the neighborhood (c) Our proposed Neighbor2Seq. (d) Our
proposed models: Neighbor2Seq+Com and Neighbor2Seq+Attn.
each node is L + 1. Formally, for each node i, our Neighbor2Seq can be expressed as
n
Σ w(i,,,,)a,, v 10,
2/
where w(i,j, E) denotes the number of walks with length between node i and j. n is the number of nodes in the graph. We define w(i,j, 0) for = and 0 otherwise. Hence, z is the original node feature Intuitively, zt is obtained by computing weighted sum of features of all nodes with walks of length to i, and the numbers of qualified walks are used as the corresponding weights. Our Neighbor2Seq is illustrated in Figure (c). Note that the derived sequence has meaningful order information, indicating the hops between nodes. After we obtain ordered sequences from the original hierarchical neighborhoods, sequences, as detailed below.
generic deep learning operations to learn from these
3.3 NORMALIZATION
Since the number of nodes in the hierarchical neighborhood grows exponentially as the hop number increases, different layers in the neighborhood tree have drastically different numbers of nodes. Hence, feature vectors sequence computed by Equation ( have very different scales. order to make the subsequent learning easier, we propose layer to normalize the sequence features. We use normalization technique similar to layer normalization (Ba al.) 2016). In particular, each feature of sequence is normalized based on the mean and the standard deviation of its own feature values. Formally, our normalization process for each node can be written as
y
M O Yt
y! We
0
+ Br, vl (0, 1,2,
o/
d'
1 1 d'
vild.
of
wvll wb)
We first apply linear transformation We Bd' xd to produce low-dimensional representation o Rdd for the f-th feature of the sequence, since the original feature dimension d is usually
4

---

Under review as a conference paper at ICLR 2021
large. pa E R and of E R are the mean and standard deviation of the corresponding representation yi. Ye Rd and Be 12d denote the learnable affine transformation parameters. denotes the element-wise multiplication. Note that the learnable parameters in this normalization layer is asso- ciated with E, implying that each feature of the sequence is normalized separately. Using this nor- malization layer, we obtain the normalized feature vector oj E IRd for every E (0,1,2,'.. ,...
3.4 NEIGHIBOR2SEQ+CCNN AND NEIGHIBOR2SEEQ+ATN
After obtaining ordered sequence for each node, view each node in the graph sequence of feature vectors. We can use general deep learning techniques to learn from these sequences. In this work, we propose two models, namely Neighbor2Seq+Cone and Neighbor2Seqt in which convolution and attention are applied on the sequences of each node.
As illustrated in Figure (d), Neighbor2Seq+Conn applies a I-D convolutional neural network to the sequence features and then use an average pooling to yield a representation for the sequence. Formally, for each node i,
CNN (o (o) 0j. ... 06) CNN
of....... ,0),,
E=
where CNN(.) denotes 1-D convolutional neural network. r² denotes the obtained representation of node that used as the input to a linear classifier to make predictions for this node. Specifically, we implement CNN(.) as a 2-layer convolutional neural network composed of two 1-D convolutions.
The kernel size is set according to the length of input sequence. The activation function between layers is ReLU (Krizhvssky et al. 2012).
Incorporating attention is another natural idea to learn from sequences. As shown Figure T (d), Neighbor2Seq+AAtn uses attention mechanism (Bahdanau et al., 2015) integrate sequential feature vectors in order to derive a representation. Unlike convolutional neural networks, the vanilla attention mechanism cannot make use of the order of the sequence. Hence, add positional codings (Vaswani et al. (2017) to the features such that the position information of different features in the sequence can be incorporated. Formally, for each node i, we add positional encoding for each feature in the sequence as
sin
m7 = 2n
10000 #
ki - o pblm]
cos
m = 2n +
10000 3
The positional encoding for 2-th feature of node is denoted as p E R.d"", m E (1,2....., the dimensional index. Intuitively, a position-dependent vector is added to each feature such that the order information can be captured. Then we use the attention mechanism with learnable query (Yang et al. 2016) to combine these sequential feature vectors to obtain the final representations r for each node 1. Formally.
dd' is
T exp(k)" 9) ΣL expeexppk
acki aj
(5)
q E IR' is the learnable query vector that is trained along with other model parameters. The derived representation r' will be taken as the input to linear classifier to make prediction for node i.
3.5 ANALYSIS OF SCALABILITY
Precomputing Neighbor2Seq. well-known fact is that the value of w(i, j, E) in Equation can be obtained by computing the power of the original adjacency matrix A. Following GCN, add self-loops to make each node connected itself. Concretely, w(i,j,e) the Neighbor2Seq (0, 1,2, ... L}. Since there is no learnable parameters in the Neighbor2Seq step, these matrix mul- tiplications can be precomputed sequentially for large graphs on CPU platforms with large memory.
A Hence, be implemented by computing the matrix multiplications Á'X for VŁ
5

---

Under review as a conference paper at ICLR 2021
This can be easily precomputed because the matrix Á is usually sparse. For extremely large graphs, this precomputation can even be performed on distributed systems.
Enabling mini-batch training. After obtain the precomputed sequence features, each node in the graph corresponds to a sequence of feature vectors. Therefore, each node can be viewed as an independent sample. That is, we no longer restricted by the original graph connectivity anymore. Then, we can randomly sample from all the training nodes to conduct mini-batch training. This is more flexible and unbiased than sampling methods as reviewed in Section 2.2 Our mini-batches can be randomly extracted over all nodes, opening the possibility that any pair of nodes can be sampled in the same mini-batch. In contrast, mini-batches in sampling methods are usually restricted by the fixed sampling strategies. This advantage opens the door for subsequent model training on extremely large graphs, as long as the corresponding Neighhor2Seq step can precomputed.
Computational complexity comparison. We com- pare our methods with several existing sampling and precomputing methods in terms of computational complexity. We let L denote the number of hops we consider. For simplicity, we assume the fea- ture dimension d is fixed for all layers. For sam- pling methods, s is the number of sampled neigh- bors for each node. The computation of Neigh- bor2Seq+Conv mainly lies in the linear transfor- mation (i.e. (LL in the normalization step and the I-D convolutional neural networks (i.e.. (LLkLn)) where k is the kernel size). Hence, the computational complexity for the forward pass of Neighbor2Seq+Conv is ((Ld + Lkd)))). Neighbor2Seq+AAun has a computational complexity of (((Ld' - md) because the attention mechanism is more efficient than 1-D convolutional neural networks. As shown in Table the forward pass complexities of precomputing methods, including our Neighbor2Seq+Com and Neighbor2Seq+aan Attm, are all linear with respect to the number of nodes n and do not depend on the number of edges m. Hence, the training processes of our models are computationally efficient.
Table I: Comparison of computational com- plexity for precomputing and forward pass corresponding to entire epoch.
Method
Precomputing
Forward Pass
GCN
O(Tdm + I.Pr)) (l++(P)))
GraPOSAGE
O(shn))
ClustrGCN
O(m)
O(Ldm + Lifre)
GripSSIINT
Oisn)
O(Ldm LdPn)
SGC
(LLmm)
Old O(LPP))
SIGN
(Ldmm)
(Laom)
OILL + Ld)
Neighhor2Sequ/AAm
((Tdm)
OuTT.P 4 Idyn)
3.6 ALLEVIATING THE OVER- WEER-QQUSHHING ISSUE
An inherent problem in message passing methods is known as the over-squashing (Alon Yahav 2020). In particular, recursively propagating information between neighbors creates a bottleneck because the number of nodes in the receptive field grows exponentially with the number of layers. This bottleneck causes the over-squashing issue; that is, information from the exponentially-gronn growiig receptive field is compressed into fixed-length vectors. Consequently, message passing methods fail to capture the message flowing from distant nodes and performs poorly when long- rangrrange information is essential for the prediction tasks. Note that the over-squashing issue is not identical to the over- smoothing issue. Over-smoothing is related to the phenomenon that node representations converge to indistinguishable limits when the number of layers increases (Li et al., 2018 Wu et al. 2019 NT
& Macharal 2019 Liu al. [2020a] Oono & Suzuki, 2020 Cai & Wang 2020 Chen et al. (020))
The virtual edges added in Gilmer et al. (2017) and recent non-local aggregations (Pei et al. 2020
Liu et al.) 2020b) can be viewed as attempts to alleviate the over-squashing issue by incorporating
distant nodes. Another study (Ma et al. 2019) considers message passing along all possible paths between two nodes, instead of propagating information between neighbors.
Our Neighbor2Seq can alleviate the over-squashing issue because we transform the exponentially- growing nodes in hierarchical neighborhoods into an ordered sequence, instead of recursively squashing them into a fixed-size vector. With our Neighbor2Seq. capturing long-range informa- tion on graphs becomes similar to achieving this on sequence data, such as texts.
DISCUSSIONS
4.1 INFORMATION LOSS IN NEIGHBOR2250
As shown in Figure D (c), Neighbor2Seq obtains the sequence by integrating features of nodes in each layer of the neighborhood tree. This transformation may lose the cross-layer dependency

---

Under review as a conference paper at ICLR 2021
information in the tree. Specifically, the Neighbor2Seq ignores the identities of nodes that each walk passes through and only considers what are the nodes in each layer of the neighborhood tree. Nevertheless, this information neither be captured by message passing methods because the aggregation is usually permutation-invariant, This implies that messages from different neighbors cannot be distinguished, Table 5 our models without this information can outperform message passing methods, such as GCN, It intriguing to have in-depth exploration of whether such information is useful and how it can be captured.
pointed in Pei al. (2020). According to experimental results in
4.2 RELATIONS WITH THE WEISFEILER-LEHMA. HIERARCHY
As shown in Xu et al. 2019). most of current GNNs are at most as powerful as the Weisfeiler- Lehman (WL) graph isomorphism test WWeisfeiler & Lehman 1968) in distinguishing graph struc- tures. Our Neighbor2Seq is still under the WL hierarchy because the neighborhood tree used to obtain the sequence is indeed the one that the WL test to distinguish different graphs. We would be interested in exploring how Neighbor2Seq can be extended to go beyond the WL hierar- chy as a future direction.
4.3 BRIDGING THE GAP BETWEEN GRAPH AND GRID-LIKE DATA
The main difference between graph and grid-like data lies in the notion and properties of locality. Specifically, the numbers neighbors differ for different nodes, and there is no order information among the neighbors of a node in graphs. These the main obstacles preventing the of generic deep learning operations on graphs. Our Neighbor2Seq is an attempt to bridge the gap between graph and grid-like data. Base on our Neighbor2Seq, many effectivee strategies for grid-like data can be naturally transferred to graph data. These include self-supervised learning and pre-training on
graphs (Hu al. 2019 Velickovic et al. 22019) Sun al. 2019 Hassani & Khasahmadi 2020 You
et al. 2020 Hu et al. 2020b;; Qiu et al. 2020 Jin et al.) 2020).
We notice an existing work AWE [vanov Burnaev (0188) which also embed the information in graph as a sequence. In order to avoid confusion, we make a clarification about the fundamental and significant differences between AWE and our Neighbor2Seq. First, AWE produces a sequence embedding for the entire graph, while our Neighbor2Seq yields sequence embedding for each node in the graph. Second, each element in the obtained sequence in AWE is the probability of an anonymous walk embedding. In our Neighbor2Seq, each feature vector in the obtained sequence for one node is computed by summing up the features of all nodes in the corresponding layer of the neighborhood tree. This point distinguishes these two methods fundamentally.
EXPERIMENTAL STUDIES
5.1 EXPERIMENTAL SETUP
Datasets. We evaluate our proposed models on 1 massive-scale graph and 4 medium-scale graphs using node classification tasks. The massive-scale graph ogbn-papers100k. provided by the Open Graph Benchmark (OGB) (Hu et al. 2020a) is the existing largest benchmark dataset for node classification. Medium-scafe graphs include ogbn-products (Hu et al., 2020ap, Reddit (Hamilton) et al.) 2017), Yelp Zeng et al. (2020), and Flickr ZZng et al. (2020). These tasks cover inductive and transductive settings. The statistics of these datasets are summarized in Table 2 description of these datasets are provided in Appendix A.
The detailed
Table 2: Statistics of datasets. "m" denotes multi-label classification.
Dataset
Scale
#Nodes
#Edges
Avg. Deg.
#Features
#Classes
Train/Val/Test
ogbn-papers100M
Massive
111, 059, 956
615, 683, 872
128
172
0.78/0.08/00
/5//0088/0.14
ogbn-preddccs
Medium
2, 449, 029
61, 869, 140
100
47
0.08/0.02/0090
Reddit
Medium
232, 965
606, 919
50
602
41
0.66/0.10/0.00
Yelp
Medium
716, 857
6, 9.9997 410
10
300
100(m)
0.75/0.10/00
Flickr
Medium
89, 250
899, 756
500
0.50/00.25/00
Implementation. We implemented our methods using Pytorch (Paszke et al. 2017) and Pytorch
Geometric (Fey & Lenssen 2019). For our proposed methods, conduct the precomputation
7

---

Under review as a conference paper at ICLR 2021
the CPU, after which we train our models a GeForce RTX 2080 Ti GPU. We perform a grid search for the following hyperparamettes: number of hops L, batch size, learning rate, hidden dimension d', dropout rate, weight decay, and convolutional kernel size k. The chosen hyperparameters for our Neighbor2Seq+ and Neighbor2Seq Attn Attn are summarized in Appendix A.2 for reproducibilityy
5.2 RESULTS ON MASSIVE-SCALE GRAPHS
Since gybn-papers/00M. is mas- sive graph with more than 111 mil- lion nodes and 1.6 billion edges, most existing methods have difficulty han- dling such a graph. We consider three baselines that have available results evaluated by OGB: Multilayer Per- ceptron (MLP), Vede2Vec (Grover & Leskovee 2016), and SGC (Wu et al.) 2019). The results under transductive setting is reported in Table 3 Fol- lowing OGB, we report accuracies for all models on training, validation, and test sets. The previous state-of-the- art result on ogbn-papers 100M is ob- tained by the precomputing method SGC. Our models outperform the baselines consistently in terms of training, validation, and test, which demonstrates the expressive power and the generalization ability of our method on massive graphs.
Table 3: Results on ogbn paperss0000 in terms of classi- fication accuracy (in percent). The reported accuracy is averaged over 10 random runs. Note that existing sam- pling methods cannot scale this massive graph. Dur- ing precomputation, both SGC and our models have to ran- domly remove 40% edges avoid memory overflow on CPU. This implies that the performance could be further improved if more advanced precomuting platform used.
Method
Training
Validation
Test
ML.P
54.8420.43
49.60=2.20
40.24
Node2vec
58.07
55.60
SGC
67.54.0.43
66.48
63. 10.19
Neighbor2Seq+Conv
69.87 +0.81
64.04 67.46-0.16
Neighbor2Seqt-Atm
68.83+0.30
66.90=0.10 10
63.59=0.17
5.3 RESULTS ON MEDIUM-SCALA GRAPII
We also evaluate our models on medium-scad scale graphs, thus enabling comparison with more existing works. We conduct transductive learning on ogbn-products, a medium-scale graph from OGB, We also conduct inductive learning on Reddil, Yelp, and Flickr, which are frequently used for inductive learning by the community. The following baselines are considered: MLP, Node2 (Grover &
Leskovee 2016). GCN (Kipf& & Welling 2016). SGC Wu et al. (2019). GraphSAGE (Hamilton
ct al. 2017), FastGCN (Chen et al. 2018bb. VR-GCN (Chen et al. 2018a), AS-GCN (Huang et al.
2018 ClusterGCN (Chiang et al. 2019), GraphSAINT (Zeng al. 2020), and SIGN (Rossi al. 2020
Table 4: Results on ogbn-products in terms of classification accuracy (in percent). The re- ported accuracy is averaged over 10 random runs Obtaining the results of GCN requires a GPU with 33GB of memory.
Table 5: Results for inductive learning on three datasets in terms of F1-micro score. The re- ported score is averaged over 10 random runs. The results of baselines are partially obtained
from Zeng et al. (2020); Rossi et al. (2020).
Method
Training
Validation
Test
Method
Reddi
Flickr
Yelp
MLP
81.03=0.05
75.51=0.14
G1 61.06ee..6
GCN
0.933
0.492220.00
0.378=.0001
Node2vec
93.39
90.32=.000
72.49+0.30
FastGCN
0.924_..0
0.504_o.m
0.265
GCN
93.56=0.0b
92. 02.00=0.03
75. 75.61+0.21
VR-GCN
0.964=amm
0.482-0om
0.660==0.oz
ClusterGCN
GraphSAINT
GrapUSAGE
93.75..0.13
92.96-0.07
20.71
92. 12.12....
91.70.0.00
22.622..mm
78.971..33
78.70+0..0
29.08
GraphSAINT
GrahhSAGE
ClusterGCN
AS-GCN
0.
0.953
0.95L=0000
0.966-00.00
0.481=00005
0.504_0000
0.511=00001
0.501:0013
0.6344..00s
0.653=0.000 003
0.60990..05
SGC
91.191..00 92.60_.0.10
72.4610.27
SGC
0.9:9
(.5022=0000
0.358=0.005
SIGN
96.92.0.80 86
os 93.10..000
77.6010-13
SIGN
0.968-00000
0.511=00001
0.631=0.003
Seig
95.12
92.02
79.67
Neighbor2Seq-Coom
0.967 Loune
0.527 10.000
0.642
10.00s
NeighborZSeq+Aiin
92.82.0.14
92.220
29.35
Noighbor2Sqq4AAm
0.967
0.523
0.647
The gebn-products dataset challenging because the splitting is not random. The splitting pro- cedure is more realistic. The nodes (i.e., products) are sorted according to their sales ranking and the top 8% nodes are used for training, next 2% for validation, and the rest 90% for testing. This matches the real-world application where manual labeling is prioritized to important nodes and mod- els are subsequently used to make prediction on less important nodes. Hence, agbn-products is an ideal benchmark dataset to improve uut-of-distribution prediction. As shown in Table 4 our Neigh- bor2Seq+Conv and Neighbor2Seq+ outperfom baselines on test set (i.e., 90% nodes), which further demonstrates the generalization ability of our method.
8

---

Under review as a conference paper at ICLR 2021
The results inductive tasks are summarized in Table 5 than all sampling methods and achieve the competitive result as SIGN. On Flickr, our models obtain significantly better results. Specifically, our Neighbor2Seq+Conv outperforms the previous state-of- the-art models by an obvious margin. Although our models perform not as good as GraphSAINT on Yelp, outperform other sampling methods and the precomputing model SIGN consistently on this dataset.
On Reddit, our models perform better
5.4 COMPARISONS OF COMPUTIONAL EFFICIENCY
In order show the com- putational efficiency, conduct an empirical com- parison with existing meth- ods in terms time com- suming during preprocess- ing, training, and infer- ence. We consider the fol- lowing representative sam- pling methods and precom- puting methods: ClusterGCN Chiang et al. (2119). GraphSAINT Zeng et al. (2020), SGC Wu et al.
Table 6: Computational efficiency in terms of preprocessing, training (per epoch), and inference times (in seconds) on ogbn-products. The reported time is averaged over 10 runs.
Method
Preprocessing (1)
Training ())
Inferenece (L)
Test Accuracy (t)
ClusterGCN GraphSAINT
44. 1520.7
11.87
87 87.03
78.97=0033
80,78+33
4.29
107.26+0054
79.00 79.08=0.24
SGC SIGN
163.36
0.15
1.08
72.46
151.47.3.5
1.22
2.93
77.60_0.13
Noighbor2Seq+Conv
153.42ea.
4.09
31 11.52e1.44
79.67
NeighbborSeeq4Aun
153.42es.2
2.67
31 31.2000001
79.35=0.17
(2019), and SIGN Rossi et al. (2020). The comparison performed on ogbn-products and the similar trend can be observed other datasets. As demonstrated in Table 6 our approaches, like existing precomputing methods, are more computationally efficient than sampling methods in terms of training and inference. Compared with existing precomputing methods, our methods achieve better balance between performance and efficiency.
5.5 ABLATION STUDY ON ORDER INFORMATION
Table 7: Comparison of models with and without capturing order information. Neighbor2Seq+AAthn w/o PE denotes the Neighbor2Seq+AAtn without adding positional encoding.
Model
Order ogbn-papersI00M
ogbn-products
Reddit
Flickr
Yelp
Neighboz2Sc4+Con
64.04-0.22
=9.67
=0.0700.00
0.527 =0.003
0.647
2cighbor2Seq+AAmm
63.59-0.17
79.35=0.17
0.967
0.020
0.647
Neighbor2Seq w/o PE
63.61-0.09
78.54_0.25
0.965.10.000
0.521
0.64610.001
Intuitively, the order information in the sequence obtained by Neighbor2Seq indicates the hops between nodes. Hence, we conduct an ablation study to verify the significance of this order in- formation. We remove the positional encoding in Neightor2Seq4AAttn leading to a model without the ability to capture the order information. The comparison is demonstrated that Neighbor2Seq+Attu and Neighbor2Seq+AAttn w/o PE have the same number of parameters. Hence, Comparing the results of these two models, we can conclude that the order information is usually necessary. Neighbor2Seq+Com and Neighbor2Seq+Attn both can capture the order infor- mation. There are two possible reasons why Neighbor2Seq+Conv performs better. First, Neigh- bor2Seq+Conv has more learnable parameters than Neighbor2S++Attn, which only has a learnable query. Second, the convolutional neural network in Neighbor2Seq+Com can additionally investi- gate the dependencies between feature dimensions because each feature dimension of the output depends on every feature dimension of the input.
Table 7 Note
6 CONCLUSIONS AND OUTLOOK
In this work, we propose Neighbor2Seq, for transforming the heirarchical neighborhoods to ordered sequences. Neighbor2Seq enables the subsequent use of powerful general deep learning operations, leading to the proposed Neighbor2Seq+Cony and Neighbor2SeqtAttm Our models can be deployed on massive graphs and trained efficiently. The extensive expriments demonstrate the scalability and the promising performance of our method. As discussed in Section 4 based on our Neighbor2Seq. several significant directions can be further explored in the future research.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Uri Alon and Eran Yahav, On the bottleneck of graph neural networks and its practical implications. arXiv preprint arXiv:2006.05200 2020.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. vrXiv:1607.064500 2016.
arXiv preprint
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning align and translate. In International Conference Learning Representations, 2015.
Peter Battaglia, Razvan Pascanu, Matthew Lai, Danilo Jimenez Rezende, et al. Interaction networks for learning about objects, relations and physics. In Advances in neural information processing systems, pp. 4502-4510 2016.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sunchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv: arXiv:/806.0123 1806.0/26,, 2018.
Kush Bhatia, Kunal Dahiya, Himanshu Jain, Yashoteja Prabhu, and Manik Varma. The extreme classification repository: multi-label datasets & code. URL http://annivvrmaa (og/loonlous/CC//MLLeesssss html, 2016.
Aleksandar Bojchevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 2464-2473, 2020.
Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geomet- ric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In International Conference on Learning Representations, 2014.
Chen Cai and Yusu Wang. A note on over-smoothing for graph neural networks. arXiv preprint arXiv:2006. 13318, 2020.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In Thirty-fourth AAAI Conference on Artificial Intelligence, pp. 3438-3445, 2020.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In International Conference on Machine Learning, pp. 942-950, 201 8a.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018b.
Wei-Lin Chiang, Xuanqing Liu, Si Si. Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen. An efficient algorithm for training deep and large graph convolutional networks. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 257-266, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. Advances neural information processing systems, pp. 3844-3852. 2016.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv:1903.02423 2019.
Hongyang Gao. Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1416-1424, 2018.
10

---

Under review as a conference paper at ICLR 2021
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Gaamnnng-Volume 70, pp. 1263-1272, 2017.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference Knowledge discovery and data mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi-view representation learning graphs. International Conference on Machine Learning, 2020.
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. International Conference on Learning Representations, 2019.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.0066 2020a.
Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai- Wei Chang, and Yizhou Sun. Gpt-gnn: Generative pre-training of graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 1857-1867, 2020b.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in neural information processing systems, pp. 4558-4567, 2018.
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In Jennifer Dy and An- dreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings Machine Learning Research, pp. 2191-2200, Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR. URL
press/
(V8C/ivanovi 1tt.vll8...mml1111.mmmmmm html
Wei Jin, Tyler Derr, Haochen Liu, Yiqi Wang, Suhang Wang, Zitao Liu, and Jiliang Tang. Self-supervised learning graphs: Deep insights and new direction. arXiv preprint arXiv:2006. 10141, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105, 2012.
Yann LeCun, Bernhard Boser, John S Denker, Donnie Henderson, Richard E Howard, Wayne Hub- bard, and Lawrence Jackel. Backpropagation applied to handwritten zip code recognition. Neural computation, 1(4):541-551, 1989.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for sumi-super learning. In Proceedings of the -hirry-Second AAAI Conference on Artificial In- telligence (AAAI-18), pp. 3538-3545. Association for the Advancement of Artificial Intelligence, 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In International Conference Learning Representations, 2016.
11

---

Under review as a conference paper at ICLR 2021
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 338- 348, 2020a.
Meng Liu, Zhengyang Wang, and Shuiwang Ji. Non-local graph neural networks. arXiv preprint arXiv:2005. 14612, 2020b.
Zheng Ma, Ming Li, and Yuguang Wang. Pan: Path integral based convolution for deep graph neural networks. arXiv preprint arXiv: 10996, 2019.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed represen- tations of words and phrases and their compositionality. In Advances neural information pro- cessing systems, pp- 3111-3111 19, 2013.
Hoang NT and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. arXiv preprint arXhv:/905.09550, 2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020.
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary DeVito, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2020.
Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pp. 1532-1543, 2014.
Jiezhong Qiu, Qibin Chen, Yuxiao Dong, Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gee: Graph contrastive coding for graph neural network pre-training. In Pro- ceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1150-1160, 2020.
Emanuele Rossi, Fabrizio Frasca, Ben Chamberlain, Davide Eynard, Michael Bronstein, and Fed- erico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. 11188 2020.
Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig MacNair, Shawn French, Lindsey A Carfrae, Zohar aaceemmn,,,,n, et al. A deep learning approach to antibiotic discovery. Cell, 180(4):688-702 2020.
Fan-Yuu Yun Sun, Jordan Hoffman, Vikas Verma, and Jian Tang. Infograph: Unsupervised and semi- supervised graph-level representation learning via mutual information maximization. In Interna- tional Conference on Learning Representations, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser. and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Petar Velickovic, William Fedus, William I. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In International Conference Learning Representations, 2019.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396- 413, 2020.
12

---

Under review as a conference paper at ICLR 2021
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph enn for learning on point clouds. Acm Transactions On Graphics (tog), 38(5): 1-12, 2019.
Boris Weisfeiler and Andrei A Lehman. reduction of graph canonical form and algebra arising during this reduction. Chunchno-Tcchnichsskayd Informatsia, 2(9):12-16, 1968.
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In International Conference on Machine Learning, pp- 6861-6871, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? International Conference on Learning Representations, 2019.
Zichao Yang, Diyi Yang, Chris Dyer, Xiaodong He, Alex Smola, and Eduard Hovy. Hicrarchical attention networks for document classification. In Proceedings of the 2016 conference of the North American chapter of the association for computational linguistics: human language technologies, pp. 1480-1489, 2016.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974 983, 2018.
Yuning You, Tianlong Chen, Zhangyang Wang, and Yang Shen. When does self-supervision help graph convolutional networks? In International Conference on Machine Learning, 2020.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. International Conference on Learning Representations, 2020.
Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Leyer-dependent importance sampling for training deep and large graph convolutional networks. In Advances in Neural Information Processing Systems, pp. 1 1124--1125, 2019.
13

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1 DATASET DESCRIPTIONS
agbn-papees (Hu al. 2020a the existing largest benckmark dataset for node classifica- tion. It is a directed citation graph of 111 million papers indexed by Microsoft Academic Graph (MAG) (Wang et al.) 2020). For simplicity, it is converted an undirected graph in baselines and our method. Each node is a paper and each directed edge indicates that one paper cites an- other one. Each node associated with 128-dimensional feature vector obtained by averaging the word2vec (Mikolov et al. 2013) embeddings of words in its title and abstract. Among the node set, approximately 1.5 millione of them are ARXIV papers, each of which has a label with one of ARXIV's subject areas. The rest nodes (i.e., non-ARXIv papers) are not associated with label infor- mation. The task is to leverage the entire citation graph to infer the labels of the ARXIV papers. The time-based splitting is used the splitting strategy. To be more specifical, the training nodes all ARXIV papers published until 2017, while the validation nodes are the ARXIV papers published in 2018, and the ARXIV papers published since 2019 are treated as test nodes.
ogbn-products (Hu et al., 2020a) is an undirected Amazon product co-purchasing graph (Bhatia al., 2016). Nodes denote products and edges between two nodes indicate that the corresponding products are purchased together. Node features are derived by extracting bag-of-words representa- tions from the product descriptions. Further, a Principal Component Analysis applied these features to reduce the dimension to 100. The task is to predict the category of a product. A realistic splitting scheme is used in this data. Specifically, the products are firstly sorted according to their sales ranking, and then the top 10% products are used for training, next 2% for validation, and the rest for testing. This strategy matches the real-world situation where manual labeling is prioritized to important nodes and models are subsequently deployed to predict the less important ones.
Reddit (Hamilton et al. 2017). Yelp (Zeng et al. 2020), and Flickr (Zeng et al., 2020) are widely used datasets for inductive learning. During training, only the node features of training nodes and the edges between training nodes are visible. Reddit is a social netowork extracted from Reddit forum. Nodes represent posts and edges between two posts indicate the same comments both posts. Node features are fromed by GloVe CommonCrawl word vectors Pennington et al. (2014) of the posts. The task is to predict which community different posts belong to. The splitting is also time-based. Yelp is a social netowork constructed from Yelp website. Nodes are users and edges between two nodes indicate they are friends. Node features of users are obtained by the word2vec embeddings of their corresponding reviews. The task is to predict the categories of businesses reviewed by different users, which multi-label classification task. Flickr a social network based on Flickr, photo sharing website. Nodes represent images and there is edge between two nodes two images share some common properties. The node features are fromed by the bag-of-words representations of the images. The task is to predict the category each image belongs to.
A.2 HYPERPARAMETER CONFIGURATIONS
We conduct a grid search for hyperparameters. Table summarizes the chosen hyperparameters for our models.
14

---

Under review as a conference paper at ICLR 2021
Table 8: The chosen hyperparameters for models on all datasets.
Model
Hyperparameter
ogbn-paperst00M
ogbn-products
Reddit
Flickr
Yelp
number of hops kidden dimension d'
7
10
512
512
256
256
512
convolutional kernel size &
7
5
7
Noighhor2Sc4+Conv
learning rate batch size
5e-4
2c-5
8e-5
8c-4
5e-4
12288
64
32768
24576
8192
weight decay dropout rate
5c-5
5e-5
0.5
number of hops L hidden dimension learning rate batch size weight decay dropout
7
10
512
512
256
256
512
5c-4
1c-3
20-3
20-3
5c-4
Neighbor2SeqtAAttn
3072
32768
Se-6
5e-5
Se-5
0.25
0.5
0.5
0.5
15


Reviews:
[{"review_id": "zeZAcIWQZgk", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "The authors proposed a neighborhood to sequence construction & pre-training approach to handling graph representation learning on large graphs.\n\nThe merits of this work include:\n\n1. provide a decent attempt toward solving the computation bottleneck for representation learning on large graphs;\n2. discusses and shows the benefits of the pre-training based on (unsupervised) sequence learning.\n\nThe limitations, on the other hand, is obvious:\n\n1. Pre-training is a relatively standard technique for representation learning on large graphs, and the schema proposed in this paper has very limited novelty;\n2. The application of attention mechanism for sequence learning is also a standard practice that has been widely adopted in this domain;\n3. The only part where this paper may distinguish itself from the previous work is how the sequence is constructed from the neighborhood. However, minimal theoretical discussion and empirical ablation study are provided to reveal the guarantees & benefits of the proposed method.\n\nTherefore, the limited novelty and contribution of this paper clearly outweigh its merits.\n\n=======================================\n\nAfter reviewing the response from the authors, I decide to change my evaluation score and confidence score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "djSub53-m6g", "reviewer": "AnonReviewer1", "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": "Overall, the paper propose an interesting approach for computing node embeddings in a scalable way.\nHowever, the contribution is incremental as the idea of embedding nodes using sequences is not new; moreover, the discussion with prior works is very weak.\n\nConcretely, important related works are missing. \nThere is an ICML 2018 paper, \"Anonymous Walk Embeddings\" (https://arxiv.org/pdf/1805.11921.pdf). There are many following up papers as well. The idea of this line of works is to embedding node/graphs by random walk sequences. While the approaches are not exactly the same as  Neighbor2Seq, the idea of embedding nodes using sequences is not new. However, none of these works are mentioned in this paper. The authors should compare these papers in the experiments as the baselines. Without such comparison, it is hard to evaluate the performance gain of the proposed Neighbor2Seq.\n\nAdditionally, the discussion with prior works is very weak.\nThe paper misleads the readers by arguing \"However, they have inherent difficulties when applied on large graphs due to their excessive computation and memory requirements\" in Section 2.1. The paper refers \nHowever, existing approaches can scale to huge graphs. For example in the PinSage paper (https://arxiv.org/pdf/1806.01973.pdf), they can scale their GNN model to 3 billion nodes. Failing to mentioning this point is misleading for the readers, and is exaggerating the motivation of this paper.\n\nMore comments:\n1 The exact configuration of the Neighbor2Seq model is not mentioned. Providing an algorithm will greatly help.\n\n2 I can imagine multiple ways for sampling sequences from a node's neighborhood. However, they are not discussed in the paper.\n\n3 How does the expressive power of Neighbor2Seq compares with WL test? I assume Neighbor2Seq is theoretically less expressive than WL test. \n\n4 I guess there will be failure cases of this kind of Neighbor2Seq, when the topology of node neighborhood structure matters for the final performance. For example, Neighbor2Seq probably won't perform well for graph isomorphism tests. I suggest mentioning potential limitations in the paper.", "extra_scores": {}, "extra_text": {}}, {"review_id": "b56qZbP3WGh", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "\n# Summary\n\nThis paper proposed a simple graph neural network architecture that is easy to scale up and perform stochastic training. Instead of performing message passing as commonly used GNN, this paper first performs weighted combinations of node features per each hop of the neighbors of a center node, and then performs either CNN or attention mechanism to aggregate the features and obtain center node embedding. Since the feature aggregation can be performed offline, and the computation can easily be decomposed and stochastic training is straightforward, the method can easily scale up to graphs with 10M nodes. Experiments on median size or large size graphs show the comparable or better performance than alternatives. \n\n# Pros\n\n- The idea is simple and easy to implement, while being effective at the same time. \n- The new design of the architecture \n- Experiments on large scale graphs are convincing.\n\n# Cons\n\n- some comparisons are incomplete\n- Not sure how general this approach would be\n- time/memory cost can be reported and compared\n\n\n# Details\n\nOverall I lean towards accepting the paper. \n\nThis paper provides a simple yet efficient and effective approach for graph node embedding calculation. It enjoys similar computation efficiency as the SGC, but is a bit more expressive in the design, where the CNN or attention is introduced on top of the per-hop embeddings. I like such a simple design that adds the expressiveness without too much additional cost. \n\nIt is also good to see the large scale experiments on OGB graphs. \n\nThere are several aspects that can potentially be improved:\n\n1. The SGC results are not presented in Table 4 or Table 5. It is necessary to include, as this might be the most relevant/comparable baseline.\n\n2.  Would this approach be useful for graph classification? I understand that the main purpose of this approach is scalability, but it would also be good to know the potential limitation on its parameterization. Also it would be more comprehensive to see the results on small benchmarks like Cora, Pubmed, etc,. This is mainly to polish the paper and get a better understanding for users. It would be fine if the results are worse on these small graphs. \n\n3. The runtime (during preprocessing, stochastic training, etc) and memory cost can be reported.\n\n# Questions\n\nI’d like to see the replies to my questions above. \n\n# Improvement\n\nIt would be good to include additional experiments as mentioned above, to make the paper more comprehensive. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1E8Ky5POIc", "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": "The paper proposes a method called neighbor2seq that converts the hierarchical structure of the center node to a sequence during message passing in graph neural networks. The proposed method aims to mitigate the issue of excessive computation and memory requirement of training graph neural networks. The proposed models Neighbor2Seq+Conv and Neighbor2Seq+Attn are tested on several datasets including a large scale benchmark dataset (ogbn-papers100M). The result shows some improvement especially on ogbn-papers100M while the improvement is not very obvious on other datasets.\n\nStrength:\n1. The idea of converting the graph topology to a sequence that could be tackled with methods designed for grid-like data is good. \n2. The proposed method shows improvement on a large scale dataset. There are also ablation studies that are useful to understand different components in the method, for example, removing the sequence information (position encoding here) clearly hurts the model performance. But it's surprising to see that Neighbor2Seq+Conv is better than Neighbor2Seq+Attn. I think there could be more information/experiment/insights added to explain why this is the case.\n\nWeakness:\n1. Since the proposed model is trying to mitigate the excessive computation and memory requirement issues, make it more efficient, and alleviate over-squashing, I'm expecting to see more in-depth analysis and empirical/theoretical justification with regard to those issues that the method is trying to solve. However, there's only some time complexity comparison and some argument about over-squashing. Can you provide the comparison of space complexity since memory requirement mitigation is one of your motivation? Also, Neighbor2Seq does not seem to improve upon the computation as compare with most of the methods listed in table 1? For the argument of alleviating over-squashing, can you provide more details? Why is converting to a sequence alleviating over-squashing? It seems that some sequence models also suffer from over-squashing, isn't it (trying to squash the whole sequence information into a single vector)? Please provide more explanation/analytical results, etc.\n2. The experiment results do not seem to improve a lot compared with existing models for some datasets and tasks. It seems that Neighbor2Seq+Conv consistently performs better than Neighbor2Seq+Attn in all experiment. Can you provide analysis of the number of parameters of your proposed model (2 variants) compared with existing models? Since people usually see that attention based approach performs better, is it because conv based one has more parameters. Does the proposed method have more parameters than existing models in general? Can you also provide some empirical comparison on the training time of your model compared with baseline models?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents a way to aggregate and precompute node features on a graph to enable fast parallel training of neural models on massive graphs for various node prediction tasks.  We have seen quite a few papers in this line of work (precompute node features without training, and then treat the nodes as independent during training) recently and this is a continuation in this trend.

Most reviewers lean toward rejection.  The main concern is the lack of novelty and the marginally better results reported in the experiments.  In some sense, the proposed method could be thought of as replacing the concatenation operation of node features across multiple hops used in the SIGN paper with a sequence model, either conv + pool, or attention.  Given this, the novelty of this paper is indeed a bit limited.  Additionally, it is unclear why this sequence model perspective is better than concatenation, which should be in principle more expressive and in practice faster and more efficient (as also reported in Table 6).

I recommend rejecting this paper, but do encourage the authors to position their work better with respect to prior work and really consider what’s the defining advantage of their approach compared to alternatives, like SIGN.
Decision: Reject