Deep Graph Neural Networks with Shallow Subgraph Samplers
Authors: Hanqing Zeng
Muhan Zhang
Yinglong Xia
Ajitesh Srivastava
Rajgopal Kannan
Viktor Prasanna
Long Jin
Andrey Malevich
Ren Chen
Venue:  (2021)
Keywords: Graph Neural Networks
Graph Sampling
Network Embedding

Abstract: While Graph Neural Networks (GNNs) are powerful models for learning representations on graphs, most state-of-the-art models do not have significant accuracy gain beyond two to three layers. Deep GNNs fundamentally need to address: 1). expressivity challenge due to oversmoothing, and 2). computation challenge due to neighborhood explosion. We propose a simple "deep GNN, shallow sampler" design principle to improve both the GNN accuracy and efficiency --- to generate representation of a target node, we use a deep GNN to pass messages only within a shallow, localized subgraph. A properly sampled subgraph may exclude irrelevant or even noisy nodes, and still preserve the critical neighbor features and graph structures. The deep GNN then smooths the informative local signals to enhance feature learning, rather than oversmoothing the global graph signals into just "white noise". We theoretically justify why the combination of deep GNNs with shallow samplers yields the best learning performance. We then propose various sampling algorithms and neural architecture extensions to achieve good empirical results. Experiments on five large graphs show that our models achieve significantly higher accuracy and efficiency, compared with state-of-the-art. 

Under review as a conference paper at ICLR 2021
DEEP GRAPH NEURAL NETWORKS WITH SHALLOW SUBGRAPH SAMPLERS
Anonymous authors
Paper under double-blind review
ABSTRACT
While Graph Neural Networks (GNNs) are powerful models for learning repre- sentations on graphs, most state-of-the-ard models do not have significant accu- racy gain beyond two three layers. Deep GNNs fundamentally need to address: 1). expressivity challenge due to oversmoothing, and 2). computation challenge due to neighborhood explosion. We propose simple "deep GNN, shallow sam- pler" design principle to improve both the GNN accuracy and efficiency - to gen- erate representation of target node, within a shallow, localized subgraph. A properly sampled subgraph may exclude irrelevant or even noisy nodes, and still preserve the critical neighbor features and graph structures. The deep GNN then smooths the informative local signals to enhance feature learning. rather than oversmoothing the global graph signals into just "wwite noise". We theoretically justify why the combination of deep GNNs with shallow samplers yields the best learning performance. We then propose various sampling algorithms and neural architecture extensions to achieve good empirical results. Experiments on five large graphs show that our models achieve significantly higher accuracy and efficiency, compared with state-of-the-art.
deep GNN to pass messages only
INTRODUCTION
Graph Neural Networks (GNNs) have now become the state-of-the-as models for graph mining (Wu et al. 22020) Hamilton et al., [017b] Zhang et al. 2019)), facilitating applications such as social recommendation (Monti et al. 2017 Ying al. 2018 Pal et al. 2020), knowledge understanding (Schlichtkrull et al. 2018 Park et al. 2019; Zhang et al. 2020) and drug discovery (Stokes et al.,
2020 Lo et al. 2018). With the numerous architectures proposed (Kipf Welling [016)] Hamilton et al. 2a] Veličković et al. 2018), it still remains an open question how to effectively design deep GNNs. There are two fundamental obstacles that are intrinsic to the underlying graph structure:
Expressivity challenge: deep GNNs tend to oversmooth (Li et al. 2018). They collapse embed- dings of different nodes into a fixed low-dimensional subspace after repeated neighbor mixing. Computation challenge: deep GNNs recursively expand the adjacent nodes along message pass- ing edges. The neighborhood size may grow exponentially with model depth (Chen et al. 2017).
Due to oversmoothing, one of the most popular GNN architectures, Graph Convolutional Network (GCN) (Kipf & Welling 2016), has been theoretically proven as incapable of scaling deep layers Oono & Suzuki] 2020) Rong et al., 2020 Huang et al., 2020). Remedies to overcome the GCN limitations are toodeo. From the neural architecture perspective, researchers are actively seeking for more expressive neighbor aggregation operations (Veličković et al. 2018 Hamilton et al. 201 7a Xu et al. 2018a), or transferring design components (such as residual connection) from deep CNNs to GNNs (Xu et al. 2018b Li et al. 2019 Huang al.) 2018). From the data perspective, various works (Klicpera et al. 2019a b. Bojchevski et al. (2020) revisit classic graph analytic algorithms to reconstruct graph with nicer topological property. The two kinds of works also be combined to jointly improve the quality of message passing in deep GNNs.
All the above GNN variants take "global" view on the input graph G (V,E) - i.e., all nodes considered as belonging to the same G, whose size can often be massive. To generate the node embedding, no matter how modify the architecture and the graph structure, deep enough GNN

---

Under review as a conference paper at ICLR 2021
would always propagate the influence from the entire node set V into single target node. Intuitively, for a large graph, most nodes in V barely provide any useful information to the target nodes. We thus regard such "global view" on G as one of the root causes for both the expressivity and computation challenges discussed above. In this work, for the node embedding task, we take an alternative "local view" and interpret the GNN input as V Uvey Viu) and & Uwey Ely)- In other words, each larget node belongs to some small graph Gio), capturing the characteristics of only the node v. The entire imput graph G is observed as the union of all such local yet latent 9op). Such simple global-to- local switch of perspective enables us to address both the expressivity and computation challenges without resorting to alternative GNN architectures or reconstructing the graph.
Present work: SHADOw-GNN, We propose "Deep GNN, shallow sampler" design principle that helps improve the expressive power and inference efficiency of various GNN architectures. We break the conventional thinking that an I--layer (deep) GNN has to aggregate T--hop (faraway) neighbors. We argue that the GNN receptive field for a target node should be shallower than the GNN depth. In other words, an L-layer GNN should only operate on small subgraph Giu] surrounding the target node v, where Guj consists of (part of) the Lo-hop neighborhood. The deep vs. shallow SHADOW-GNN.
comparison is reflected by setting La < L. We name such GNN on Gu] We justify our design principle from two aspects. Firstly, why do we need the neighborhood to be shallow? As a motivating example, the average number of 4-hop neighbors for the egbn-proddctt graph (Hu et al. (020) is 0.6M, corresponding to 25% of the full graph size. Blindly encoding the 0.6M node features into single embedding vector can create the "information bottleneck" (Alon) & Yahav 2020). The irrelevant information from the majority of the 0.6M nodes may also "dilute" the truly useful signals from small set of close neighbors. A simple solution to the above issues is to manually create a shallow neighborhood by subgraph sampling. The second question regarding SHADow-GN is: why do we still need deep GNNs? Using more number of layers than the number of hops means the same pair of nodes may exchange messages with each other multiple times. Intuitively, this helps the GNN better absorb the subgraph information. Theoretically, we prove that a GNN deeper than the hops of the subgraph can be more powerful than the I-dimensional Weisfeiler- Lehman test (Shervashidze et al. 1001I. A shallow GNN, on the contrary, cannot accurately learn certain simple functions such as unweighted mean of the shallow neighborhood features. Note that with GCN as the backbone, a SHADOw- GCN still performs signal smoothing in each layer. However, the important distinction is that deep GCN smooths the full regardless of the target node while a SIIADow-GCN constructs a customized smoothing domain Giv] for each target v. The variance in those smoothing domains created by SIIADOW- GCN encourages variances in the node embedding vectors. With such intuition, our analysis shows that SHADow-GN GNN does not oversmooth. Finally, since the sizes of the shallow neighborhoods are independent of the GNN depth, the computation challenge due to neighhor explosion is automatically addressed.
We propose various subgraph samplers for SHADOW- GNN, including the simplest k-hop sampler and sampler based on personalized PageRank, to improve the inference accuracy and computation efficiency. By experiments on five standard benchmarks, our SHADOW-SAGE and SIAADOWGAT models achieve significant accuracy gains compared with the original GraphS and GAT models. In the meantime, the inference cost is reduced by orders of magnitude.
RELATED WORK AND PRELIMINARIES
Deep GNNS. Recently, numerous GNN models Kipf & Welling 2016 Defferrard et al., 2016 Hamilton et al. 2 Veličković et al. 2018 Xu et al. 2018b a) have been proposed. In general, the input to a GNN is the graph G, and the outputs are representation vectors for each node, cap- turing both the feature and structural information of the neighborhood. Most state-of-the
GNNs use shallow models (i.e.. 2 to 3 layers). As first proposed by Li et al. (2018) and further elaborated by Luan et al. (2019): Oono & Suzuki (2020); Zhao & Akoglu (2020): Huang et al. (2020), one of the major challenges to deepen GNNs is the "oversmoothing" of node features each layer aggre- gation pushes the neighbor features towards similar values. Repeated aggregation over many layers results in node features being averaged over the full graph. A deep GNN may thus generate indistin- guishable embeddings for different nodes. Viewing oversmoothing as limitation of the layer aggre- gation, researchers develop alternative architectures. AS-GCN (Huang et al., 2018). DeepGCN (Li et al. 2019) and JK-net (Xu et al. 2018b) use skip conneconnnttoon across layers. MixHop (Abu-El- Eljaajaa et al. 2019 Snowball (Luan et al. 2019) and DAGNN (Liu et al. 2020) enable multi-hop message
2

---

Under review as a conference paper at ICLR 2021
passing within a single layer. GraphSAGE (Hamilton et al. 2017a) and GCNII (Ming Chen al. 2020) encourage self-to-self message passing which effectively form an implicit skip-connection. GIN (Xu et al., (2018)) and DeeperGCN (Li et al. 2020a) propose more expressive neighbor aggre- gation operations. All the above focus on architectuaal exploration, which is a research direction orthogonal ours. We can construct the SHADOW version of these GNNs in plug-and-plan fash- ion. Lastly, DropEdge (Rong et al. 2020) and Bayesian- GDC (Hasanzadeh et al. (2020) propose regularization techniques by adapting dropout (Srivastava al. 2014) to graphs. Such techniques are only applied during training, and so oversmoothing during inference may not be alleviated.
Learning from structural information. Another line of research to go beyond the layer- layer-wise message passing and more explicitly utilize the graph structural information (Wu et al. 2019
Klicpera al., 2019a Bojchevski et al. 2020 Liu et al. 2020 Frasca al. 2020; You et al. 2019
Li al.] 2020b). .. In particular, APPNP K et al. (019a) and PPRGo (Bojchevski et al. 2020)
utilize the personalized PageRank (Page et al., 1999) algorithm to re-define neighbor connections
instead of propagating features along the (noisy) graph edges, any nodes of structural signifi- cance can directly propagate to the target node. Other related methods such as GDC (Klicpera et al.) 2019b) and AM-GCN (Wang al. 2020) reconstructs the adjacency matrix in each GNN layer to short-cut important multi-hop neighbors. Note that all the above methods takes a global view on and operate the neural networks on the full graph. On the other hand, the idea of using sub- graph samples to improve the GNN efficiency has also been explored. For example, SEAL (Zhang & Chen (2018) extracts local k-hop enclosing subgraphs to perform link prediction. GraphSAINT (Zeng et al. (020)) propose random walk samplers to construct minibatches during training.
Notations. We focus on the node classification task, although our design principle can be naturally extended to other tasks. Let G (V,& f, X) be an undirected graph, with node set V, edge set & C V and node feature matrix X E R The w-th row of X corresponds to the length-d feature of node u. Let A be the adjacency matrix of G where Au,e 1 if edge (u, v) E E and Au, otherwise. Denote À as the adjacency matrix after symmetric normalization (used by GCN), and A the one after random walk normalization (used by GraphS AGE). Let subscript "[u]" mark the quantities corresponding to a small subgraph surrounding node u. For example, the subgraph itself 9u.. For an L-layer GNN, let superscript "(E)" denote the layer-& quantities (1 S S L). Let d(
be the number of channels for layer E; (f-1) R xxxee 1; and H E R be the input and output feature matrices. Thus, (0) = X and d( = d. Further, let Y (L)), The operation of layer can be abstracted as (f) = (H A: W(0), where ((() are the learnable weights.
DEEP GNN, SHALLOW SAMPLER
"Deep GNN, shallow sampler" is a design principle improve the expressivity and effi- ciency of GNNs without modifying the layer architecture. Based on this principle, we construct SHADow-GNN by subgraph sam- pling. SHADoW-GNY uses the same sam- pling procedure during both training and in- ference. The inference algorithm is shown in Algorithm 1 In line 4, we use f² to denote the composition of the function I for the L layers. Operation [-le,: slices the e-th row of the matrix. We discuss in Section 3.2 how to design SAMPLE to return informative shallow neighborhood.
Algorithm SHADDW-GND inference algorithm
Input: G (VV& E, {); Target nodes V;; GNN model; Output: Node embedding matrix Y for Ve:
1: for u E V, do
2:
Get Giv (V/u), Eju, (x) by SAMPLE on G
3: Build L-layer GNN with layer operation f
4: yo + [ Am)))
Notice that the normal GNN is special kind of MADDw-GGNN Under the normal setup, the GNN operates on the full graph 9 and the layers propagate the influence from all the neighbors up to L hops away from the target node. Such GNN is equivalent to SHADOOw- GNN when SAMPLE returns the full L-hop subgraph. However, following our principle, a good SAMPLE should encourage most of Viui to concentrate within the Lo-hop neighborhood, where Lo < L. Figures 6 in Appendix show the difference in the neighborhood composition for normal GNN and SHADOW GNN. Section 3. discusses the benefits of making the subgraph shallow and the GNN deep.
3

---

Under review as a conference paper at ICLR 2021
3.1 ANALYSIS ON EXPRESSIVITY
The STIADOW-GNN design is motivated by the following:
1). A shallow neighborhood is sufficient for the GNN to learn good node representation;
2). A shallow neighborhood is necessary to reduce the effect of noise on the GNN;
3). A deep GNN is necessary to be expressive on the shallow neighborhood.
Point 1 is true in many real-world scenarios, and is also justified by the 7-decaying theorem ZZang & Chen 2018): to estimate various important graph metries of a node from its L-hop neighborhood. the estimation error decays exponentially with the number of hops L. The understanding on Point 2 is two-folded: real-world graphs are likely to include noisy nodes and edges due to erroneous graph construction (Klicpera et al.) 2019b). Additionally, even without errors, a node u may still be regarded as "white noise" " to the target node v, simply because u is far away from v and u's information is irrelevant. The first kind of noise may be handled by filtering
the high frequency components of the node signals (Wu et al. 2019) or enforcing low rank constraints on the adjacency matrix (Grover et al. 2019 Jin al. 2020). The second kind of noise cannot be filtered as long as the GNN aggregates the full Z-hop neighborhood. In this regard, sampling provides an additional mechanism deal with both kinds of noises. Also, since we customize different subgraphs for different target nodes, SAMPLE filters noise at the node level rather than the graph level. For Point 3. while theoretical understanding on the benefit of deep neural networks has been well established for Multi-Layer Perceptrons (MLPs) (Telgarsky) 2016), such conclusion does not directly transfer to GNNs. For SHADow-GNN we prove a deeper model is more expressive than a shallower one.
Expressivity comparison with "deep GNN, deep sampler". When increasing the depth of nor- mal GNN, the neighborhood around a target node (i.e., the full L-hop subgraph) also expands. Eventually, a deep normal GNN a connected G will propagate influence of all V into a single target node. As discussed in Point above, most V only act as "white noise" to a target node, thus causing difficulties in learning regardless of the layer propagation function.
We pick the GCN architecture for case study. When the GCN depth grows, we analyze how a shallow sampler can filter out the "white noise" in the neighborhood and help preserve target node specific information. Following the setup of [i et al. (2018); Luan et al. (2019): [Mng Chen et al. (2020); Zhao & Akoglu (2020), we study the asymptotic behavior of repeatedly applying the neighbor ag- gregation operation. Le., we analyze how much information is preserved in M limi,- A' X. Proposition 3.1. An oo-layer SHAADow-GOO generates the neighbor aggregation for as:
(x) = [el]] (e[x)X())
(1)
(1) where etyj is defined by [e[w]] 1/e (n) OT8) (u) returns the degree of in Glul plus 1.
OVERSMOOTHING OF NORMAL GCN With large enough L, the full L-hop neighborhood be- comes V (assuming connected 9). So V u, v, we have 9μ1 = 9 = G. implying e(u] = Elj) and [M) [M = X. From Proposition 3.1 the aggregation converges to a point where no feature and little structural information of the target is preserved. The only information in m)) is e's degree.
LOCAL-SMOOTHIE OF SHADOw-GCN With fixed shallow subgraph, matter how many times we aggregate using Avj. the many layers will not include the faraway irrelevant nodes. We can see Mej as a linear combination of the neighbor node features X Increasing the number of layers only pushes the coefficients of each neighbor features to the stationary values. The domain X(,) of such linear transformation is solely determined by SAMPLE and is independent of the layer depth. Intuitively, if SAMPLE picks non-identical subgraphs for two nodes and v. the aggregations should be different due to the different domains of the linear transformation. Therefore, information preserves local feature information whereas normal GCN preserves none. For structural in mjj. note that e'v] is a normalized degree distribution of the subgraph around and [e|=i] indicates the role of the target node in the subgraph. If we let SAMPLE return the 1-hop subgraph, then [e[]]] alone already contains all the information preserved by normal GCN, which is e's degree in G. Since eiv] additionally reflects the structure of u's ego-net, a deep SHADow-GCN with naive 1-hop SAMPLE preserves more structural information than a deep GCN.
4

---

Under review as a conference paper at ICLR 2021
Theorem 3.2. Let (i)) @g (v) mia where &g is any non-zero function only depending
the structural property of v. Let M = {mlyl v E V}. Given 9, SAMPLE and some continuous
probability distribution in RIVIX! to generate X, then mi + mi if Mui + Mol. almost surely.
Corollary 3.2.1. Consider SAMPLE; where Vu E V. Myil S n. Then |M| 2 [V] almost surely.
Corollary 3.2.2. Consider SAMPLE, where u. E V, VoJ # Viu. Then [ = V almost surely.
proves SHADow-GCN GCN does not oversmooth, 1). normal GCN pushes the aggrega- tion of same-degree nodes to the same point, while SHADow-GCN with SAMPLE, ensures any two nodes (even with the same degree) can have different aggregation; 2). normal GCN wipes out all the information in the initial node features after many times of aggregation, while SHADow-Ges GCN
Theorem 3.2
always preserves node feature information. In particular, if we set @g (v) = (b)) -1/2 GCN generates only one unique value of 7., while SHADow-GNN can still generate N for any dg.
a normal
Expressivity comparison with "shallow GNN, shallow sampler". Most state-of-the-art GNNs belong the "shallow GNN, shallow sampler" category. However, we argue that deep GNN is still desirable even though the neighborhood is shallow. In the following, we first give two examples showing when "shallow GNN, shallow sampler" fails to learn something that SHADOW- can. Then we prove that SHADOW- GNN is strictly more powerful than 1-dimensional Weisfeiler- Lehman test, thus more powerful than all standard "shallow GNN, shallow sampler" designs.
In Figure [ consider the 2-hop neighborhood (black dots) of some target node (blue star). In the first example. suppose another target node o' has slightly different 2-hop structure as reflected by an additional edge (red dashed line). Assume all nodes have identical features. Then any 2-layer GNN cannot distinguish v and v', while 3-layer GNN can. The red edge that distinguishes u and o' not having any influence on v' until three times of message passing. In the second example, we consider a simple task of learning the unweighted mean of neighbor features, T M Euen, Ex.
u, v
Figure 1: Example neighborhood
Suppose 9ju) consists of the star node, black nodes and black edges. Surprisingly, even with such a "regular" subgraph structure, normal L-layer GraphSAGE cannot learn accurately. The reasons are as follows. If L > 2, then normal GraphSAGE will include nodes outside Visi and the only way to always exclude the impact of these nodes is by setting the weights for that layer to 0- this effectively reduces the number of layers to 2. Now since 7 is linear, ReLU is not desirable, and should be bypassed by shifting X with the bias parameters. The output of the neural net then simplifies to <= --E A X
where L for normal GraphSAGE. For the given A(rj. there does [v) We e.:
not exist We for GraphSAGE satisfy т = < for any value of [i)) On the other hand, with SAMPLE returning 9iz]. BHADOW-SAGE can learn 7 with any precision if L is allowed to grow. The required T. for SHADow-S to reach the desired precision is determined by the mixing time of Apj. SIAADOw AAGE AGE can learn the unweighted mean because the eigenvector corresponding to the largest eigenvalue of A is uniform vector. In fact, a deep SHADow-SAGE can learn the unweighted feature mean on any neighborhood.
Theorem 3.3. Suppose we are given any GNN following the per-layer message passing design as:
h -0--f -19
1 (CD,
Σ 5 ((!
(n!C-1), ( )
where ( and ((1) are the layer-E update and message functions, respectively, implemented as MLPs; u v denotes is v's I-hop neighbor. Then, on the full L-hop subgraph, an L'-layer GNN is strictly more discriminative than an L-layer model, when L' > L. Moreover, with injective fi and fz. the GNN model described above (using L' > L layers on the L-hop subgraph) strictly more discriminative than the 1 !-dimensional Weisfeiler-Lemmnn test.
See Appendix A for the proof. By Theorem 3.3 given a shallow sampler, a deep GNN is strictly still "deeper" GNN to
more powerful than shallow one. Even given deep sampler, beat the "deep" GNN. Other practical concerns on deep GNNs include the difficulty in optimization and the computation cost. The optimal depth may be determined after considering such tradeoffs.
5

---

Under review as a conference paper at ICLR 2021
3.2 SAMPLER DESIGN
k-hop sampler. Starting from the target node v, the sampler traverses up to k hops. At hop-é node u, the sampler will add its hop-(! + 1) node set either all neighbors of u, or randomly selected neighbors of u. The subgraph [vj is induced from all the nodes selected by the sampler. Here depth k and budget are the sampling parameters. See Appendix for more analysis.
PPR sampler. Personalized PageRank (PPR) has been recently combined with graph learning (Klicpera et al.) 2019a, BBjehheskii et al., 2020 Li al., 2020b). However, none of the existing works have explored PPR in the context of subgraph sampling. Given a target v, our PPR sampler proceeds as follows: 1). Compute the approximate PPR vector n. E RM for v. 2). Select the neigh- borhood [/ such that for u E Vjj. the PPR score [T=]u large. 3). Construct the induced subgraph from Vio)- For step I), even though vector n. is of length- V/. most of the PPR values are close to zero. So we can use fast algorithm (Andersen el al. 2006) to compute the approximate PPR score by traversing only the local region around v. Throughout the n. computation, most of its entries remain as the initial value of O. Therefore, the PPR sampler is scalable and efficient w.r.t. both time and space complexity. For step 2), we can either select Viu] based on top-p values in "., or based on some threshold [_ > 0. Then p. 0 are hyperparameters. For step 3), notice that our PPR sampler only uses PPR scores as a node filter. The original graph structure is still preserved among v.,). due to the induced subgraph step. Such property differentiates our algorithm from existing ones such as APPNP (Klicpera et al.] (0019)), GDC (Klicpera et al. (2019b) and PPRGo (Bojchevski et al.) 2020). Specifically, the three related works all reconstruct the adjacency matrix by directly connecting the target with nodes of top PPR scores. Reconstruction promotes feature propagation from direct neighbors at the cost of losing structural information, since all Vin would become 1 1-hop away from We show in Section 3.3 further connections between SHADOw- and the prior arts.
The h-hop and PPR samplers each assume shortest path distance and random walk landing probability as important metrics for measuring neighbor relevance. Following such ratio- nale, we can design many more sampling algorithms. For example, instead of PPR scores, we can use Katz index (Katz) 1953) as our node filtering condition. This is another way to signify the im- portance of shortest path distance. If the number of common neighbors is important, we can filter Vis by SimRank (Jeh& & Widom, 2002]. Apart from structural information, SAMPLE can also utilize node features. For example, In the k- h-hop sampler, instead of randomly pick b neighbors, we can pick those with highest feature similarity (c.g.. by cosine similarity or heat kernel (Wang et al. 2020).
Extensions.
3.3 ARCHITECTURAL EXTENSION
Subgraph ensemble. From Section 3.2 each reasonable SAMPLE reveals some perspectives of the graph, and they altogether present the full picture. We may then combine the information from various SAMPLE. Assume a set of C' candidates {SAMPLE; each returning (G)))), We can either:
1). Construct a union-subgraph Oij for HHADOw-GNN to operate on, where Vi- - (Me)),s and E/j = U._,, (.) or Use C' parallel branches of L--laer GNN, each operating on (g.),. So e's output embedding each branch (i.e., a vector 2;) can be aggregated by attention mechanism:
(Zw)) - ((x())))
MLP (z;) T
yr
W
where f. is the function by the L-layer GNN at branch i; z; is a row vector of (Z(x).. corresponding to v; q is a learnable vector; ä is normalized from w by softmax. yo is the final embedding. We can use identical GNN structure for all the C' branches or even share weights among the branches.
(SAMPLE,) can also perform the same algorithm with different hyperparameters. For example, we can let SAMPLE, be the PPR sampler with different threshold 0,. A www.Doow-AG--eneeeee can imitate similar feature aggregation behavior as PPRGo (Bojchevski et al.] 2020). while still having the additional advantage of learning rich subgraph structural information. Note that PPRGo generates embedding by I-hop aggregation on the reconstructed graph: T = Ewer..) h. where
T_ [muly and h, MLP (x.). We can partition Vioi U Vig such that nodes in Viy have similar PPR scores approximated by 7. and Ro < 7.F1. So To x EE (p: Emevy Am)) where

---

Under review as a conference paper at ICLR 2021
P. = - my and V = U Vo:: Recall the discussion learning unweighted feature mean of any Moi (Section 3.1p. Setting मं and w; = Pt SHADOH-S can approximate Tv. As our PPR sampler also preserves local structure, our model can be more expressive than PPRGo.
Sampling the reconstructed graph. Another extension is to build SHADOw-Gi -NN on the graph reconstructed by graph diffusion (Klicpera et al. 2019b] Frasca et al., 2020). In the simplest case, we can apply our L-hop sampler on the reconstructed graph. and build a L'-layer GNN on the subgraph. When I. = I,, we recover GDC (Kliepera et al. 2019b). When I. < I/, we have SHADOW-GDC.
4 EXPERIMENTS
Setup. We perform node classification on five graphs: Flickr (Zeng et al., 2020), Reddit (Hamil- ton et al. 2 Yelp (Zeng et al. 2020), ogbn-arxiv (Hu et al.] 2020) and ogbn-products
(Hu et al. 2020). The graph sizes range from around 9K nodes (Flickr to 2.5M nodes (ogba-producta). Consistent with the original setup, we use the metric of "accuracy" for Flickr, Reddit, agbiv and ogbn-products, and "Fl-micro score" for Yelp. See Appendix D.I
We consider seven baselines and construct the corresponding SHADOW models: GCN (Kipf & Welling, 2016), GraphSAGE (Hamilton al. 2017a). GAT (Velččkvić al., 2018), JK-Net (Xu ct al. [0188b) GIN (Xu et al., 2018a), SGC (Wu et al. 2019) and GraphSAINT (Zeng et al. 2020).
The first six representatives of the state-of-the-an GNN architectures. They jointly cover various message aggregation functions as well as the skip connection design for facilitating deep GNN training. GraphSAINT is the state-of-the-art minibatch training algorithm for large graphs. The GraphSAINT training has been shown to work well with the GraphSAGE and GAT architectures. In Table 0 for the the rows of GCN, GraphSAGE and GAT, we train 3- and 5-layer models in the full batch fashion. However, for the large graphs, the GPU memory (15GB) is too small to store the full batch. We therefore further run experiments using the GraphSAINT minibatch training algorithm, where "GraphSAINT-RRW" denotes the random walk sampler recommended by Zeng et al. 2020).
For all the experiments, we fix the number of channels (i.e,, the hidden dimension) for each layer as d(t) 256. All accuracy results are measured by five runs without fixing random seeds. Detailed hyperparameter tuning procedure and architecture configuration are described in Appendix D.3
Comparison with ttafe-of-the-art. Tableessowy the performance comparison of SHADow-GND with statc-of-the-ar GNNs. We use the following metrics: test set accuracy Fl-micro score and inference cost. The inference cost defined as the average amount of computation to generate pre- diction for one test node - is purely a measure of computation complexity and is independent of hard- ware / implementation factors such as parallelization strategy, batch processing, distributed storage, etc. Thus, the metric reflects the feasibility of deploying each GNN on real-world workloads, where the graph sizes and hardware specifications can be different from our setup. For SHAAOW-GNN, the inference cost does not consider the sampling overhead. See Figure 2 for the sampling time measurement and Appendix B for the equations for calculating the inference cost. For the 3-layer and 5-layer models in Table 1 we simply stack the corresponding GNN layers. During training, we further apply the DropEdge technique (Rong et al.] (020) to both the baseline and SHADoW models. We observe that DropEdge helps improve the baseline accuracy by alleviating oversmoothing, and helps improves the SHADOW accuracy due to its regularization effects.
ACCURACY Comparing the normal GCN, GraphSAGE and GAT, SHADow-GNNs achieve sig- nificantly higher accuracy across all the five datasets. Since we use the identical backbone GNN architectures, the accuracy gains validate the efffcctivnness of our design principle of "deep GNN, shallow sampler". Note that that our subgraphs are truly shallow, since the the subgraphs generated by our 2-hop and PPR samplers contain no more than 200 nodes. For 3-layer, comparing the accu- racy of the normal GNN with the CHADow-GNN it is clear that shallow neighborhood contains sufficient information to generate good node embeddings. For 5-layer accuracy comparison, we ob- serve even higher gains- for normal GNNs, increasing from 3 layers to 5 layers sometimes results in accuracy degradation (even with DropEdge). For SHADOW DONN making the GNN deeper is beneficial most of the time. These observations validates our oversmoothing and expressivity anal- ysis in Section 3.T Finally, the higher accuracy achieved by the PPR sampler compared with the 2- 2-hop sampler demonstrates the importance of a good sampling algorithm.
7

---

Under review as a conference paper at ICLR 2021
Inference time per node (ms)
PPR
SAGE
GAT
Tradeoff analysis (5-layer)
SHW
3
100
SAGE
Test accuracy (%)
SHw
GAT
80
Normal
AALL
SAGE
60
Normal
GAT
Flickr
40
x Reddit
Flickr
Reddit
Yelp
arxiv
products
10
100
104
102
10a
arxiv
Inference time per node (ms)
* products
Figure 2: Inference time after paral- lelization on commodity hardware
Figure 3: Inference performance tradcoff. We test pre- trained models by subgraphs of various sizes.
INFERENCE COST From T the inference cost of SHADOw-GNN GNN is often orders of magnitude lower than that of the baselines. The high cost of the baselines reflects the "neighbor explosion" challenge for deep GNNs. In short, for normal GNN, since we do not enforce a fixed size subgraph, the inference computation complexity may grow exponentially with the depth of the GNN (Chen) et al. 2017 ). For example, the number of ε-hop neighbors may be 10x the number of (E - 1) hop neighbors. For SHADow-GNI GNN, it is clear that the inference cost only grows linearly with the GNN depth. From Table [ we observe that even when the GNN depth is only 5, the high computation cost already makes the inference of normal GNNs practically infeasible. The results show the high efficiency of our design. Finally, note that for GraphS AINT, its sampling is only applied during training. The inference computation of GraphSAINT falls back be identical as its backbone architecture (which samples the full L-hop neighborhood). On the other hand, for SHADow-GNN we apply the same sampling and batching strategy, whether it for training or for inference.
Table 1: Comparison on test accuracy / F1-micro score and inference cost tuned with DropEdge)
Method
Layers
Flickr
Reddit
Yelp
ogba-arxiv
ogba-producte
Aocuracy
Cost
Accuracy
Cost
F1-micro
Cost
Accuracy
Cost
Accuracy
Cost
0.516.0.002
2E0
0,053
6E1
0.402
2E1
0.707
180
0.756.1..002
5B0
0.522 +00002
2E2
0.949
1E3
00M
1E3
0.719
280
00M
9E2
GraphSAGE
3
0.504
SE0
0.965
9E1
0.617
3E1
0.719
180
0.785
8B0
0.515+00005
0.962+0.000
2F3
0OM
3E3
0.719+0.004
3R0
00M
2F3
3
10.003
3E1
0OM
5E2
0OM
3E2
0.720
180
0OM
6E1
GAT
0.51610.003
4E2
0OM
3E3
00M
4E3
0OM
5B0
00M
4E3
GraphiSAEE
3
0.517=0.003
SED
00067
9E1
0.645
3E1
0.710=0.000
180
0.792:000002
880
GrigHSAINT-RW
0.52010.003
3E2
0.967
2E3
0.00900.000
3E3
0.701 L0,002
3ED
0.79610.002
2E3
GAT
0.522+00.05
3E1
00067
0.645
0.697
0.802-00005
6R1
+ GriphSAINT-RW
0.515
4E2
00005
3E3
0.647
4E3
0.695
SE0
0.799
4E3
SHADOW-GCN
0.526-00002
(1)
000000
(1)
0.526
(1)
0.719
(1)
0.777
(1)
+PPR
0.002
LED
0.958 +0,000
FR0
0.527 +0.001
2F0
0.721 +0.003
2R0
78.000000
2F0
SHADOW-SAGE
0.529+0.001
2F00
0,966
2130
0.649
2130
0.716+0.000
2F0
0.799=0.001
2F00
+ 2-hopp
0.534L0.004
3ED
0.966
350
0.65010.000
380
0.71810.001
380
0.801 10.002
380
SHADOW-SAGE
3
0.534=0.002
2150
000090000000
2130
00.0100.000
2130
0.723++0:005
310
0.794=00002
2130
0.542 10.002
0.650
3120
0.725 10.001
0.8042
3130
SHADOW-GAT
+0.003
2FD
0.970+0.001
2R0
0.688+0.000
2F0
0.724+0.001
3R0
0.801 +0.000
2F00
PPR
0.534+0.002
312
0.97140.00
3150
0.654
3130
0.728
S100
0.809=0.000
310
S-SGC, F S- SGC, R
S-SGC, A
SHADOW SHADOW
SHADOW 8
SHADOW 15
SGC, F
SGC, SGC, A
--SINT
SAINT
-SAINTT SAINT
100
Validation accuracy
100
Test accuracy (%)
Validation loss
ogbn-prodde products
Redditt
0.8
80
GCN arch.
Arxiv
0.6
90
0.4
85
0.2
Flickr
40
80
0
20
40
100
200
100
200
Power on A or A(v)
Epoch
Epoch
Figure 4: Effect of increasing the model depth on the SGC and GCN architectures
8

---

Under review as a conference paper at ICLR 2021
Evaluation on PPR sampler. We evaluate the PPR sampler in terms of its execution time overhead and accuracy-timg time tradeoff. In Figure 2 we parallelize the sampler on a 40-core Xeon CPU and the GNN computation on NVIDIA PIOO GPU (See Appendix D.2. The sampler is lightweight: the sampling time is lower than the GNN computation time in most cases. Also, the sampling time per node does not necessarily grow with the full graph size. By Section [3.2] the approximate PPR computation achieves efficiency and scalability by only traversing a local region around each target node. To evaluate the accuracy-time tradeoff, we take the 5-layer models of aable[as the pretrained models. Then for CHADow-GNN, we vary the PPR budget p from 50 to 200 with stride 50. In 3 the inference time of SHADow- -ONG-NN has already included the PPR sampling time. Firstly, consistent with Table 1 inference of SHADow- GNNs, with orders of magnitude speedup as well. In addition, based on the application requirements (e.g., latency constraint), SHADow-GNe the need of retraining. For example, on Reddit and ogbn-arxiv directly reducing the subgraph size from 200 to 50 speeds up inference by 2 to 4x at the cost of less than 1% accuracy drop.
achieves higher accuracy than the normal
have the flexibility of adjusting the sampling size without
Evaluation on other architectures. In addition to the GCN, GraphSAGE and GAT models in Table [ we fur- ther compare JK-Net and GIN with their SHADOW versions in Table 2 Similar to DropEdge, the skip connec- tion (or "jumping knowledge") helps
Table 2: Test accuracy (%) on other architectures
Flickr
Reddit
ogon:
Nommal
SHADOW
Nurmal
SHADOW
Normal
SHADOW
JK (3)
49.45-+0.70
53.17-033
96.49++0.10
96.82-005
71. 00
22.11-0.17
JK (5)
49. 19.40:10.33
53.28 0:26
96. 40.13
96.85 0006
71.66..0.5
72.26:0:24
GIN (3)
51. 31.3260.31
$2.28 0.22
93.45
95.78
70 70.8700.16
71.73-0.29
GIN (5)
50,04:0067
52.55 2025
73,50
95.52
0:07
69 59.62
71.40:0:2
accuracy improvement on deeper models. Compared with the normal JK-Net, increasing the depth benefits SHA MHW-JWJJK more. The GIN architecture theoretically does not oversmooth. However, we observe that the GIN training is very sensitive to hyperparameter settings. We hypothesize that such challenge is due to the sensitivity of the sum aggregator on noisy neighbors (e.g., for TraphSAGE, a single noisy node can hardly cause a significant perturbation on the aggregation, due to the averag- ing over the entire neighborhood). The accuracy improvement of SHADOW- DONNGI compared with the normal GIN may thus be due to noise filtering by shallow sampling (see Section B.I). The impact of noises / irrelevant neighbors can be critical, as reflected by the 5-layer GIN accuracy on Reddit.
Effect of model depth. To validate Theorem 3.2 on the non- oversmoothing of SHADow-GCH larger GNN depth. In the left plot of Figure we run a normal SGC and a SHADow-SGC by varying the power on the adja- cency matrix from 1 to 40 (see Appendix [D.]] for the model details and setup). While SGC gradually collapses local infor- mation into global "white noise", accuracy of SHADOW-SGC does not degrade. In the middle and right plots, we train the standard GCN architecture without the SGC simplications. Since ogbn -rroductssutss is too large, we compare SHADow-Ger GCN with GCN- SAINT. For both methods, the deeper models converge slower. Deeper models (whether they are GNNs or other types of NNs) are generally harder to optimize. For SIIADOW-GE GCN,, the validation performance of the 15-layer model eventually catches up with the shallower ones. For GCN-SAINT, however, there consistently exists large performance gap between the 15-layer model and the shal- lower ones. Both experiments clearly show that shallow sampling prevents oversmoothing. Finally, for ogbn-products in in Table 3, we note that even through > 98% of the subgraph nodes are with 2 hops (see Figure 6). increasing the GNN depth can benefit accuracy for up to T,' = 7 layers.
Table 3: GCN test accuracy (%)
we experiment on much
1/
SAMPLE
Flsckr
agin-praducta
52.57-0:11
27.73-0.32
2hop
$2.10-0:23
27.94 27.94-0.30
5 PPR
52.73:10.20
78.36 78.36:0.344
Ensemble
53.04.0.17
78.55 -0.21
52:25-00:33
78.50:00.44
Evaluation on subgraph ensemble. Benefit of ensemble is shown via the 5-layer entries in Table 3 Different samplers, such as PPR and k--hop, preserve different kinds of local information. Rather than designing one "perfect" sampler, it may be more reasonable ensemble few simpler ones. Note that ensemble is only possible for subgraph based SHADow- G.N.. In Figure (see Appendix we show that even the simplest 1-hop sampler can benefit training after ensemble.
CONCLUSION
We have presented design principle, "deep GNNs, shallow samplers", enabling accurate and effi- cient inference for a wide range of GNN architectures. We have theoretically justified the expressiv- ity of SHADOw- GNN and empirically demonstrated its benefits under various setups and metries.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. arXiv preprint arXiv: (005:0/900000006 2019.
Uri Alon and Eran Yahav, On the bottleneck of graph neural networks and its practical implications, 2020.
Reid Andersen, Fan Chung, and Kevin Lang. Local graph partitioning using pagerank vectors. In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06), pp. 475- 486. IEEE, 2006.
Alcksandar 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, KDD '20, pp. 2464-2473, New York, NY, USA, 2020. Association for Computing Machinery. doi: 10.1 00.114453394488340033999
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction, 2017.
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.
Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Fed- crico Monti. SIGN: Scalable inception graph neural networks, 2020.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. In International Conference on Machine Learning, pp. 2434-2444444 2444, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs In Advances in neural information processing systems, pp. 1024-1034, 2017a
William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint 1700 2017b.
Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sam- pling, 2020.
Kurt Homiik, Maxwell Stinchcombe, Halbert White, et al. Multilayer feedforward networks universal approximators. Neural networks, 2(5):359-366, 1989.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs, 2020.
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.
Wenbing Huang. Yu Rong. Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over- smoothing for general Graph Convolutional Networks, 2020.
Glen Jeh and Jennifer Widom. Simrank: measure of structural-conter similarity. In Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 538 543, 2002.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '20 pp. 66-74, New York, NY, USA, 2020. Association for Computing Machinery. doi: 10. 1445339444864443044
10

---

Under review as a conference paper at ICLR 2021
Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-43, 1953.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 6980, 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classification graphs. In International Conference on Learning Representations, 9a.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing, 2019b.
Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. DeepGCNs: Can GCNs go deep as CNNs? In The IEEE International Conference on Computer Vision (ICCV), 2019.
Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. DeeperGCN: All you need to train deeper gens, 2020a.
Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding design provably more powerful gnns for structural representation learning, 2020b.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into Graph Convolutional Networks for semi-supervised learning. arXiv preprint 1rXiv:1801.07606 2018.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, Aug 2020. doi: 10.1145/3394486.4400000 34C3076
htLtttt:// dx www.....gg........ 20tg///...1/33334466666
Yu-Chen Lo, Stefano E Rensi, Wen Torng, and Russ B Altman. Machine learning in chemoinfor- matics and drug discovery. Drug discovery today, 23(8):1538-1555 2018.
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. In Advances Neural Information Processing Systems 32, pp. 10945-1000 10955. Curran Associates, Inc., 2019.
Zhewei Wei Ming Chen, Bolin Ding Zengfeng Huang, and Yaliang Li. Simple and deep graph convolutional networks. 2020.
Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with recur- rent multi-graph neural networks. In Advances in Neural Information Processing Systems, pp. 3697-3707, 2017.
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.
Aditya Pal, Chantat Eksombatchai, Yitong Zhou, Bo Zhao, Charles Rosenberg, and Jure Leskovec. PinnerSage: Multi-modal user embedding framework for recommendations at Pinterest. Pro- ceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug 2020. doi: 10. 1115/399488..44033
Namyong Park, Andrey Kan, Xin Luna Dong, Tong Zhao, and Christos Faloutsos. Estimating node importance in knowledge graphs using graph neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 596-606, 2019.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. DropEdge: Towards deep Graph Convolutional Networks on node classification. In International Conference on Learning Repre- sentations, 2020.
11

---

Under review as a conference paper at ICLR 2021
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-607. Springer, 2018.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borg- wardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, 15(1):1229-1958. 2014.
Jonathan M Stokes, Kevin Yang. Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar Bloom-Ackerman, et al. A deep learning approach to antibiotic discovery. Cell, 180(4):688-7000 2020.
Matus Telgarsky. Benefits of depth in neural networks. arXiv preprint arXiv:1602.04455 2016.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference Learning Representations, 2018.
Xiao Wang, Meiqi Zhu, Deyu Bo, Peng Cui, Chuan Shi, and Jian Pei. AM-GCN: Adaptive multi- channel graph convolutional networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '20, pp. 1243-1253, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450379984. doi: 10.1145/ 3394486.3403177
Felix Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu. and Kilian Q Weinherger. Simplifying graph convolutional networks. arXiv preprint 0rXiv:/902.07/55: 2019.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey graph neural networks. IEEE Transactions Neural Networks and Learning Systems, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1810.00826. 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks, 2018b.
Rex Ying. Ruining Hc, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 974 983, 2018
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. arXiv preprint arXiv:1906.0483 04817, 2019.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In International Conference on Learn- ing Representations, 2020.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information Processing Systems, pp. 5165-5175, 2018.
Shuai Zhang, Lina Yao, Aixin Sun, and Yi Tay. Deep learning based recommender system: A survey and new perspectives. ACM Computing Surveys (CSUR), 52(1):1-38, 2019.
Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks, 2020.
Lingxiao Zhao and Leman Akoglu. PainNorm: Tackling oversmoothing in gnns. In International Conference Learning Representations, 2020.
12

---

Under review as a conference paper at ICLR 2021
A PROOFS
The GCN model performs symmetric normalization on the adjacency ma- trix. SHADOw-GCN follows the same way normalize the subgraph adjacency matrix as:
Proof of Proposition 3.1
A (DM + 1) (Aiy) 1) (Div) +1)
(4)
where A1) NNN is the binary adjacency matrix for 91v)
A is real symmetric matrix and has the largest eigenvalue of Since SAMPLE ensures the subgraph giv) connected, the multiplicity of the largest eigenvalue is 1. By Theorem of Huang et al. 2020). we can bound the eigenvalues X by A A2 ...>. AN > ~11.
Performing eigen digepdeccomooiitioon on A(oj. we have
E (w)
AE
AE
(5)
where a diagonal matrix A, X; and matrix E(n) consists of the normalized eigenvectors.
We have:
A(1 E/o A [0]
Since Ax| < 1 when * 1, we have lim A/r = ewe where e, is the eigenvector corre-
sponding to Å1. It is easy to see that [e(w]] x v (u) (Huang et al. 2020). After normalization,
[ew]l 1 (w]
(w)
directly follows that mij
[epill [
(ui)) with value of eju defined above.
Proof of Theorem 3.2 We first prove the case of [p) m.) i.e., @g(()
According to Proposition
3.1 the aggregation for each target node equals min = [<]]]] c (()--
Let N [V]. Let ||o|
E
g.v1 be the vector expanded from Ejv)- such that [ěµ=) 0 if $ Vivl
and the rest of the non-zero elements of eij] are copied from e[u] accordingly.
We define:
= [e]ll | - [e(w] elyl
Suppose we only compute when two nodes u and v have non-identical sampled neighborhood. i.e., ViJ # Vis. Then given SAMPLE and some distribution to generate X. there are finite number of possible values. The reason is that G is finite and does not depend on X (where X itself can take infinitely many values). Each of the possible values defines a hyperplane in R-N- by x (where æ N). Let all such hyperplanes be H.
Now suppose we build -HADOw-GCN by performing SAMPLE on g and X. For any two e and
with Vin] * Vuj. suppose their aggregations are the same: miu] = miu]- Then we must have 6 X = 0. In other words, Vi, X., must fall on one the hyperplanes in H.
However, since X is generated from continuous distribution in TR Nxf, X., would not fall on all of the hyperplanes in H. almost surely. Therefore, for any v and u such that Voj # Vil.. m(x) A m almost surely.
For more general @g(v), since thg does not depend on X, the proof follows exactly the same steps as above.
Proof of Corollary 3.2.7 Note that Vu E V, u E Vi... For any node v. there are at most n - 1 other nodes in y with the same neighhorhood 1/o)- Such possible nodes are exactly those in V(u)-
13

---

Under review as a conference paper at ICLR 2021
By Theorem 3.2 Yu E V. there are at most n 1 other nodes in V having the same aggregation as mo). Equivalently, total number of possible aggregations is at least [[]]/]]
Proof of Corollary 3.2.2
By definition of SAMPLE2, any pair of nodes have non-identical neighbor- hood. By Theorem 3.2 any pair of nodes have non-identical aggregation. Equivalently, all nodes
have different aggregation and |M |
Proof of Theorem 3.3 Define gb: as the subgraph induced from all the Ł-hop neighbors of where 1 1 L.
We first prove that an L' L'-layer GNN is at least as expressive as an L-layer GNN on any L-hop subgraph. We note that for the target node v, the only difference between these two architectures is that an I--layer GNN exactly performs I. message passing iterations to propagate node information from at most L hops away, while an L'yyyr GNN has L' L more message passing iterations before performing the L message passings. Thanks to the universal approximation theorem (Hornik
itt al. 1989). we can let f(() (h! (n(--1, Euno (1()) (1( nu )) = he (f(11) v1 S <
since MLPs can model and learn such functions. Then, the L' L'-layer GNN will have the same output as the L-layer GNN.
Then, we show that an L'-layer GNN can learn something that an L-layer GNN cannot learn on some Q/)-- This can be proved exactly by the example given in Figure where the red edge is included in the subgraph. In this Pin around v', a 2-layer GNN fails to capture the red edge, and will output the representation of u' the same as when there is no red edge. In contrast, a GNN with more than 2 layers can capture the red edge immediately after the first message passing round. where the two end nodes of the red edge receive messages from each other. And after 3 message passing rounds, this captured additional information will be propagated to v', resulting representation different from that learned by the 2-layer GNN.
Finally, we prove that with injective fi and fz, the GNN model described above (using L' > L layers on the L-hop subgraph) is strictly more discriminative than the 1 1-dimensional Weisfeiler-Lehmal (1-WL) test. We first prove that no matter how many iterations T. 1-WL. runs, we can always run this GNN model on the L-hop subgraph with L' layers to get at least the same discriminative power as 1- WLL According to Xu et al. (2018a), an L-layer GNN on G% is theoretically as discriminative as 1L by being able to discriminate all nodes v that 1-WL with iterations of color update can discriminate. Suppose there are two node v, v' that 1-WL gives different colors to after L iterations. Then applying the L-layer GNN on 0%) and 0 will also return (.) * h Since f1 and fz are
injective, we know h (1++1) + h h (L++)) for any > 0, which means an L' llyer GNN (L' > L) can also discriminate the two nodes.
Then it suffices to give example where 1-WL always fails to distinguish two nodes no matter how many iterations runs, while the GNN model above can discriminate them with some L and L'. We construct very simple example, shown in Figure Consider an undirected graph with two connected components (CC). The first CC is hexagon. The second CC is triangle. Both CC are 2- regular. Suppose all nodes have identical attributes and edges are unweighted. Our goal is to discriminate node in the first CC from node u in the second CC. For 1-WL, no matter how many Figure 5: Example graph iterations L it runs, 1-WL always assigns the same label and v. For the GNN above, when we set L = 1 and L' = 2, we can already more expressive than 1-WL discriminate between the two nodes.
CCI
CC2
on which SHADOw-GiN DNN is
Remark Note that even though we discuss the (L + 1lllyyer case in the above proof, increasing the layer L' beyond L + can still be benefitial in many cases. Consider the following:
We revisit the GraphSAGE example on Figure 1 Suppose we use a L'-layer GraphSAGE to approximate a function the subgraph G We consider an example as computing the unweighted mean of the subgraph node features. In this case, the error of approximating T converges
CASE 1
14

---

Under review as a conference paper at ICLR 2021
to when L' goes to infinity. The error can still be significant if L' is not sufficiently larger than L. The desired depth L' is determined by the mixing time of the subgraph adjacency matrix.
CASE 2 Consider a more "powerful" GNN when fi and f2 of Equation perform injective map- ping. Recall the following two facts:
. On the full graph, such GNN of Lo layers is discriminative as the 1-WL test running
Lg iterations.
I-WL may take up to O(N) iterations to converge where N is the full graph size.
Now extend the SHADOw-GNN case. Consider two target nodes u and with their corresponding L-hop subgraphs // and 0% An L'-layer GNN will output different embeddings for and v, w's color assigned by I'-iteration 1-WL on ( different from v's color assigned by L'iiteration 1-WL on (/)-- The coloring of and keep changing for O(N) iterations (here N is the size of (i, and (..)). Thus, increasing the GNN depth on L-hop subgraphs can improve discriminative power for up to ((N) layers.
B INFERENCE COMPLEXITY CALCULATION
Here we describe the equations to compute the "inference cost" of Table Recall that inference cost is a measure of computation complexity to generate node embeddings for given GNN architecture.
The numbers Table D shows on average, how many arithmetic operations required generate the embedding for each node. For GNN layer f, denote the number of imput nodes as (f- and the number of output nodes (()) Denote the number of edges connecting the input and output nodes as m Recall that we use d(() to denote the number of channels, or, the hidden dimension.
In the following, we ignore the computation cost of non-linear activation, batch-normalization and applying bias, since their complexity is negligible compared with the other operations.
For the GCN architecture, each layer mainly performs two operations: aggregation of the neighbor features and linear transformation by the layer weights. So the number of mulipplication-addtiion (MAC) operations of a layer equals:
CLO (e((1) + (d (e-1))
(8)
Similarly, for GraphSAGE architecture, the number of MAC operations equals:
C. (lee-1) +2 (8) ((()))
where the factor due to the weight transformation on the self-features.
For GAT. suppose the number of attention heads is t. Then the layer contains t weight matrices (()) Wi, each of shape d(t-1) d- We first transform each of the (f-1) nodes by W Then for each edge (u, v) connecting the layer imput to the layer output 2, we obtain its edge weight (i.e., scalar) by computing the dot product between w's, v's transformed feature vectors and the model attention weight vector. After obtaining the edge weight, the remaining computation is to aggregate the n (f-1) features into the (8) nodes. The final output is obtained by concatenating the features of different heads. The number of MAC operations equals:
(00) =t (0-1) d(()
t + 2t m0)d d(e)
+ m000
(10)
=3m(0
(11)
15

---

On the same graph, GCN is less expensive than GraphSAGE. GraphSAGE is in general less expen- sive than GAT, due to (2(-1) > n()), In addition, we note that for architectures, C. grows proportionally with n(() and m For the normal GNN architecture, since we are using the full Under review as a conference paper at ICLR 2021
ê-hop neighborhood for each node, the value of (9) and m(() may grow exponentially with This is the "neighbor explosion" phenonemon and is the root cause the high inference cost of the Table I baselines.
For SIIADO--NNN, suppose the subgraph contains n nodes and m edges. Then n = n and ( = m. The inference cost of any SHADow-Gre OONNO ensured to only grow linearly with the depth of the GNN.
C DETAILS ON SAMPLERS
Here we present more detailed discussion on the proposed k-hopp and PPR samplers.
k-hop sampler. While previous works Hamilton et (0017)); Ying (2018) have proposed to randomly sub-sample the multi-hop neighborhood to improve GNN computation efficiency, none of them explicitly set the GNN depth to be larger than k.
For example, GraphS also uses k-hop sampler. In their case, the sampling improves the computation speed at the cost of accuracy drop. In our case, such a sampling process can lead to both accuracy gain and computation efficiency improvement - This is partially due to the exclusion of noisy neighbors by the sampler, and partially due the compensation the information loss by the higher expressivity of deeper models. More importantly, in the GraphSAGE design, the sampling depth grows with the model depth. Thus, "neighbor explosion" inevitable unless the sampling budget b is set to 1 (in such case, the sampler will likely return path, which does not contain much information).
Another difference between k-hop sampler and that of GraphSAGE is that SHADOw-GN runs on the induced subgraph of the k-hop neighbors. Compared with the normal GraphSAGE, SHADow-SAGE is able to discover more complicated structural information from the subgraph constructed by our k-hop sampler (See Theorem 3.3)
PPR sampler. In Sections 3.1 and 3.3 we have made detailed comparison between PPR-based SHADow-GNN and related works such as Klicpera et al. ();; Bojchevski et al. (2020). Here
would like to highlight that the approximate PPR algorithm proposed in Andersen al. (006) is both scalable and efficient. The number of nodes we need to visit to obtain the approximate PPR vector much smaller than the graph size. In addition, each visit only involves scalar update, which is orders of magnitude cheaper than the cost of neighbor propagation in GNN. Quanti- tatively, for the three largest datasets, Reddit, Yelp and pronupts, for each target node on average, the number of nodes touched by the PPR computation is comparable to the full 2-hop neigh- borhood size, as shown in Table 4 The statistics of Table also explains the empirical execution time measurement presented in Figure
Table 4: Average number of nodes touched by the approximate PPR computation
Dataset
Average 2-hop size
Average # nodes touched by PPR
Reddit
11093
27751
Yelp
2472
5575
ogondurosucts
3961
5405
D DETAILED EXPERIMENTAL SETUP
D. ADDITIONAL DATASET DETAILS
The statistics for the five benchmark graphs is listed in Table 5 may have multiple labels, and thus we follow the original paper (Zeng et al.) 2020) to report its
Note that for Yelp, each node
16

---

Under review as a conference paper at ICLR 2021
F1-micro score. For all the other graphs, node is only associated with single label, and report accuracy. Note that for Reddit and Flickr, other papers (Hamilton et al. 2017a Zeng et al.) 2020) also report Fi-micro score the metric. However, since each node only has single label, "F1 "mi-ro score" is exactly the same as "accuracy".
Table 5: Dataset statistics
Dataset
Setting
Nodes
Edges
Degree
Feature
Classes
Train / Val / Test
Flickr Reddit
Inductive
89,250
899.756
0.25 0.25
Inductive
232,965
11,606,919
50
41
0.66 0.10 0.24
Yelp
Inductive
716,847
6,977,410
10
100
0.75 0.10 0.15
ogbn-arxiv
Transductive
169,343
1,166,243
7
128
40
0.54
0.18 0.29
ogbn-products
Transductive
2,449.029
61,859,140
25
100
47
0.10/ 0.02/ 0.88
D.2 HARDWARE SPECIFICATION AND ENVIRONMENT
We run our experiments on a DGXI machine with Dual 20-core Intel Xeon CPUs (E5-2698 v4 @ 2.2Ghz) and eight NVIDIA Tesla P100 GPUs (15GB of HBM2 memory). The main memory is 512GB DDR4 memory. The code is written in Python 3. 6. (where the sampling part written with C++ parallelized by OpenMP, and the interface between C++ and Python is via PyBind11) We use PyTorch 1 1.4. 0 on CUDA 10.2 2 with CUDNN 7.2 to train the model on GPU.
When measuring the execution time of Figure 3 we the CPU (40-cores in total) to sample subgraphs in parallel and the GPU to execute the GNN layer operations.
D.3 HYPERPARAMETER SEARCIING PROCEDURE
For the experiments, as described in the "setup" paragraph of Section 4 we set the hidden mension be always dd 256. In addition, for all the GAT and SHADow GAT experiments, we set the number of attention heads to be t = 4. For all the GIN and SHADow-GID experiments, we use a 2-layer MI.P (with hidden dimension 256) to perform the injective mapping in each GIN layer. For all the JK-Net and SHA Dow-JK experiments, we use the concatenation operation to aggregate the hidden features of each layer in the JK layer.
For all the baseline and SHIADOW- GNNN experiments, we use Adam optimizer (Kingma & Ba 2014) We perform grid search on the hyperparameter space defined by:
Activation function: [ReLU, ELU}
Dropout: (0.00, 0.05, 0.10, 0.15, 0.20, 0.25, 0.30, 0.35, 0.40, 0.45, 0.50)
DropEdge: (0.00, 0.05, 0.10, 0.15, 0.20, 0.25, 0.30, 0.35, 0.40, 0.45, 0.50)
Learning rate: (0.01, 0.000, 0.0001, 0.00002)
The sampling hyperparameters are tuned as follows.
For the PPR sampler, we consider two versions: one based on fixed sampling budget p and the other based on PPR score thresholding 0.
If with fixed budget, we then we disable the 0 thresholding. We tune the budget by 0 E { {100, 125, 150, 175,2003.
If with thresholding, we set 0 E {0.01, 0.053. We still have an upper bound p on the subgraph size. So if there are nodes in the neighborhood with PPR score larger than 0, the final subgraph size would be max(p, g}. Such an upper bound eliminates the corner cases which may either 200 or 500 depending on the graph.
hardware inefficiency due very large In this case, set p to
For the k-hop sampler, we define the hyperparameter space as:
Depth
17

---

Under review as a conference paper at ICLR 2021
Table 6: Training configuration of SHADow-GNT for Table | (PPR sampler)
Arch.
Datasct
Laycrs
Learning Rate
Dropout
DropEdge
Budget p
Threshold 0
0.001
0.40
0.10
200
Flickr
0.001
0.40
0.10
200
0.00002
0.20
0.05
150
Reddit
0,00002
0.20
0.05
150
CHADOW-GCN
0.001
0.10
0.00
100
Yelp
0.001
0.10
0.00
100
0.00002
0.25
0.10
200
ogbn-arxiv
0.00002
0.25
0.10
200
0.002
0.40
0.05
150
ogba-products
0.002
0.40
0.05
150
0.001
0.40
200
Flickr
0.001
0.40
200
0.0002
0.20
0.10
150
Reddit
0.0002
0.20
150
SHADOW-SAGE
0.001
0.10
0.00
200
Yelp
0.001
0,10
0.00
200
0.0001
0.30
0.10
500
0.01
ogbn-arxiv
0.00002
0.25
0.15
200
0.01
0.002
0.40
0.15
1.50
ogba-products
0.002
0.40
0.15
150
0.001
0.40
0.00
200
Flickr
0.001
0.40
0.00
200
0.0001
0.20
0.00
150
Reddit
0.0001
0.20
0.00
150
SHADOW-GAT
0.001
0.10
100
Yelp
0.001
0.10
100
0.0001
0.20
0.00
175
ogbn-arxiv
0.0001
0.20
0.00
175
0.001
0.35
0.00
150
ogbn-products
0.001
0.35
0.00
150
Table 7: Training configuration of SHADow-GNN for Table (k-hop sampler)
Arch.
Dataset
Layers
Learning Rate
Dropout
DropEdge
Budget
Depth
0.001
0.40
0.00
Flickr
0.001
0.40
0.00
20
2
3
0.0001
0.20
0.00
15
2
Reddit
5
0.0001
0.20
0.00
15
2
SHADow-SAGE
0.01
0.10
0.00
Yelp
0.01
0.10
0.00
3
0.0001
0.20
0.00
10
2
ogbn-arxiv
5
0.0001
0.20
0.00
10
2
0.002
0.35
0.00
10
2
ogbu ogbu-uroducts
0.002
0.35
0.00
10
2
Budget 6 (5, 10, 15, 20}
The hyperparameters to reproduce the Table I SHADOw-G GNN results listed in Tables 6 and 7 The code will be shared with the reviewers at the end of the rebuttal period and released to public after paper acceptance.
18

---

Under review as a conference paper at ICLR 2021
D.4 SETUP OF THE EXPERIMENTS ON DEEPER MODELS
2019), we compute the SGC model Y SGC and SHADOW-SGC. Following Wu et al.
softmax A XxXW) where Á = AD and Á I + A. Matrix W is the only learnable
parameter. K is the power on the adjacency matrix and we vary it as K E [1,3, 3, 5, 10, 30, 40J in the Figure experiments. For SHADOw-SGG according Algorithm we compute the embed- ding for target ye softmax
[A X
SGC and SHADOw-SGE SGC are trained with the same hyperparameters (i.e,, learning rate equals 0.001 and dropout equals 0.1, across all datasets). SHADow-SGC uses the same sampler as the SHADow-GCN model in Table In the legend of Figure 4 due to lack of space, we use S-SGC to denote SHADow-SGC, We use "F", "R" and "A" to denote the datasets of Flickr, Reddit and ogbn-arxiv respectively.
SHADow-GCN and GCN-SAINT. For SHADOw-GCN and GCN-SAINT each, we first tune the 5-layer version to obtain the best-performing hyperparameter settings. Then we fix such hy- perparameters and change the number of layers to up to 15. Note that GraphSAINT also performs subgraph sampling (during training only). As specified in the "Setup" of Section 4 we use the mandom-walk sampler of GraphSAINT. We further tune the GraphSAINT sampling parameters to optimize its convergence quality. We obverse that GraphSAINT requires relatively large batch size to perform well (i.e., number of subgraph nodes around 20,000). This is also consistent with the configuration for ogbn-producte products in the official GraphSAINT repository.
One more thing to notice is that in the official GraphSAINT implementation, evaluates the valida- tion set performance as follows:
1). Propagate all the GNN layers using the full graph adjacency matrix (including all the train- ing, validation and test nodes);
2). Compute loss on the full graph. Use this loss as an approximation of the validation loss.
3). Mask out the predictions on the validation nodes and compute the validation accuracy.
Such a way of loss computation is due to the specific implementation design choices of Graph- SAINT. In the GraphSAINT official repository, it has clarified that such way of computing the validation loss is not very accurate. However, since the validation loss is neither used for back- propagation nor as the stopping criteria, such an approximate loss computation does not affect the optimization procedure at all. On the other hand, the impact to our experiments is that for the middle plot of Figure 4 the scale of the GraphSAINT loss curves may need to be adjusted to better reflect the actual validation loss values. Note that such adjustment, if performed, would equally affect all the GraphSAINT curves for different number of layers. Therefore, we can still conclude that increasing the number of layers have significant negative effect on the GCN-SAINT convergence (this conclusion can also be confirmed by the right plot of Figure 4 where the validation accuracy of SCN-SAINTYA is not obtained by approximation).
E ADDITIONAL EXPERIMENTAL RESULTS
E.
IS THE PPR SAMPLER REALLY "SHALLOW"?
The PPR sampler defines the neighborhood Viu] based on the magnitude of the PPR scores म,. Al- though it is possible that node far away from the target u may have high PPR score and be selected by SAMPLE, such case rarely happens in practice. Most of the nodes in V/s) are concentrated within the 2-hop neighborhood of v. Let dist (v, u) denote the shortest path distance between nodes u and Figure T shows the distribution of dist (v, u) for E Viu--
On the other hand, Figure 7 shows the composition of the neighborhood under the normal GNN. clear that most of the nodes propagated by the normal GNN are far away from the target node.
19

---

Under review as a conference paper at ICLR 2021
A
Ratio of nodes in Vil
Ratio nodes Vii
0.8
0.8
0.6
0.6
0.4
0.4
0.2
Flickr
Reddit
Yelp
ogbn ogbn-arxiv arrdiv
ogèn ogbn-proodee products
Flickr
Reddit
Yelp
ogbn -arriv
ogon products
Figure 6: PPR sampler for 5-layer SHADOW- GNN: Composition of nodes u in ViJ under various dist (u, v)
Figure 4-hop sampler for normal 4-layer GNN: Composition of nodes u in Viy under var- ious dist (u, v) k
E.2
EXAMPLE ON SUBGRAPH ENSEMBLE
PPR
1-hop
1PR+1-hop
0.74
Validation Accuracy
0.74
0.72
10
20
30
40
Epochs
Figure 8: Subgraph ensemble: SHADOw-SAGE on ogbn-arxiv
In addition to the Table rresulss SHADOw- Figure& shows how subgraph ensemble improves convergence quality with the SHA Dow-D model. We consider a PPR sampler with fixed threshold 0 = 0.01, a 1-hop sampler (which returns the full 1-hop neighbors) and the ensemble of these two. The 1-hop sampler incurs significant information loss since it preserves no multi-hop neighbors. As expected, its accuracy is low. Surprisingly,
observe accuracy gain when ensemble the 1-hop sampler and the PPR sampler by Equation [3] As discussed, different samplers preserve different kinds of local information. Rather than trying design one "perfect" sampler, it may be more reasonable to ensemble few simpler ones.
20


Reviews:
[{"review_id": "thd5yZa83t6", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "This paper proposes a new extension of GNNs to deep GNNs, which use subgraphs to keep the computational costs low for training large graphs. It addresses the two main reasons that GNNs have not previously been extended to deep GNNs: expressivity and computational cost. Increasing the number of layers in a GNN leads to averaging over more nodes, which in turn collapses the learned embeddings. The paper claims that using shallow graphs instead of the full graphs avoids this oversmoothing issue. Additionally, using the full graph is computationally expensive since the neighborhood sizes grow with the number of neighbors. Using shallow subgraphs instead allows the size of the neighborhoods to remain constant as the number of layers increase. To this end, the paper presents SHADOW-GNN, a Deep GNN with shallow sampling. They extend this framework to GraphSAGE and GAT models and show that it improves performance over the original model with a lower computational cost. Overall, this method seems well-motivated, and both theoretical and empirical results support their claims. There are a few points on which clarification from the authors would be helpful. \n\nStrengths: \n++ The paper presents 3 motivations - (1) shallow neighborhood is sufficient to learn graph representation (2) it is necessary to reduce over smoothing issues (3) One still needs a deep GNN model to learn effectively form the shallow neighborhood - and it supports these claims by providing examples and formal proofs in the form of Proposition 3.1, Theorem 3.2, and Theorem 3.3, respectively. \n\n++ The paper recommends using two main samplers for sampling the shallow neighborhoods of a node - (1) $k$-hop sampler, which randomly selects $b$ neighbors and (2) Personalized PageRank (PPR) sampler, which uses the induced subgraph from the largest PPR scores $\\pi$ for a node. According to the paper, both these methods are lightweight and scalable\n\n++ The method is applied to extend GraphSAGE and GAT models and the paper presents empirical results for 5 different datasets. The results are presented in terms of classification performance (F1-score) and computational cost (Inference cost). Benchmarked against 5 baseline models (including a subsampling algorithm), the SHADOW extension gives SOTA performance at a reduced computational cost. \n\n++ The ablation study in the paper, further demonstrates that using an ensemble of subgraphs improves performance and is feasible using the SHADOW framework. \n\n++ The paper is well written and does a good job of putting the work in context and motivating the problem. \n\nWeaknesses:\n-- The hyperparameters of the sampling algorithms, while mentioned in the Appendix tables, are not included in the tuning descriptions. I am curious to know if and how these hyperparameter choices affect the performance-cost tradeoff. \n\n-- Is there a performance-cost tradeoff for the subgraph ensemble setting suggested by the paper?\n\n-- Description of the inference cost calculation would be useful. \n\n-- While the paper mentions two other extensions - SHADOW-GCN and SHADOW-GDC, the results do not include them. Is there a reason for that? \n\nMinor comments:\n- Labeling Figure 1 with $v$ and $v'$ would make the example much clearer\n- The transitions between the theorems and the discussions are sometimes hard to follow. More connections between notation and interpretation would be helpful.\n- The “budget” term in the Appendix tables has not been connected to the hyperparameters of the sampling algorithms\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "rFBTVwIa3ua", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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 paper proposed a simple technique to improve the performance of message passing neural network models. The proposed idea is relatively simple, instead of applying GNN to the entire graphs, which leads to the over smoothing problem with enough number of layers, for each node, the model samples an ego-network of the target node, from which GNN can model representation of the node. The experimental results show the competitive results of the proposed method while preventing the over smoothing issue. Below, I listed some of my concerns about the paper:\n\n- Theorem 3.3 seems incorrect. The statement ' L'-layer GNN is strictly more discriminative than the 1-WL test' seems incorrect. If you run WL test with L iteration, this statement seems okay, however, in general, when you run the WL test, the minimum number of iteration is not set to L. The paper referred to in the proof also mentioned that only GNN is theoretically as discriminative as 1-WL when the depth of the layers is sufficient enough [Xu et al. 2018a] \n\n- The paper emphasizes the necessity of deep architecture whereas in experiments 3-layer and 5-layer architectures, which seem not very deep, are used. It would be interesting to see how the performance changes as one increase the depth of layers.\n\n- Experimental setup: Ablation study shows the best performance when multiple samplers are used, whereas the main results do not contain the result of the ensemble.\n\n- Consistency between table1 and table 2: In table 1 2-hop sampler is used to show the best performance while in the ablation study 1-hop sampler is used. Is there a reason why different k-hop samplers are used in these cases?\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NRo6CiTm1zt", "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": "\nTo address the oversmoothing problem and reduce the computational cost of GNNs, this paper proposes to train deep GNNs with shallow subgraph samplers. The following two theoretical proofs provide insightful motivations of Shadow-GNN: (1 )Obtaining node embeddings within shallow subgraphs can avoid oversmoothing; (2)Deep GNNs are strictly more expressive than a shallow one. Experiments are performed on five different graph datasets with 3 and 5 layer GNNs coupling with a k-hop sampler or a Personalized PageRank (PPR) sampler.\n\nPros:\n\n+ The paper is well-presented including nice illustrations and good examples;\n+ Theorem 3.2 and Theorem 3.3 provide nice motivations of designing shallow subgraph samplers and deep GNNs respectively;\n+ Variants of subgraph samplers and architectural extensions are discussed thoroughly, e.g., k-hop sampler, PPR sampler, subgraph ensemble and sampling the reconstructed graph.\n\nCons:\n\n- Regarding Theorem 3.3 and the example in  Figure 1, It seems for a L-hop subgraph L+1-layer GNN has enough expressivity. In other words, do we need a deeper L’-layer GNN with  L’ > L+1? Or does a L’-layer GNN with  L’ > L+1 strictly more expressive a L+1-layer GNN? If not, it can not prove we need models deeper than L+1 layers for learning on a L-hop subgraph.\n- Proposition 3.1 and Theorem 3.2 show a normal GNN suffers from over-smoothing as the number of layers approaches infinity but SHADOW-GNN does not. However, they are not well validated in the experiments for the following two reasons: (1) the assumed GNN formulate $\\mathbf{M} = \\text{lim}_{L\\to \\infty} \\widetilde{\\mathbf{A}}^{L} \\mathbf{X}$ is very different from SAGE  and GAT used in the experiments; (2) the number of layers experimented are 3 and 5 layers which are far from \"deep\" compared to the infinite layers condition. Thus, it would be great to have experiments to bridge the gap between the theory and the practice. For example,  training a SGC (Wu et al., 2019) model with more than 20 layers to show the effectiveness of  Shadow-GNN would be interesting.\n- Only comparing the inference cost of one node is not fair. For Shadow-GNN, each node will need to build one subgraph for the inference. This seems to be very computationally heavy. It would be great if there is a comparison of the inference time on the whole graph.\n\nMinor Comment:\n* The terms of Shadow-GNN and Shadow-GCN are used inconsistently. \n\nReferences:\n* Wu, F., Souza Jr, A.H., Zhang, T., Fifty, C., Yu, T. and Weinberger, K.Q., 2019, January. Simplifying Graph Convolutional Networks. In ICML.\n\n\n================================\n\nPost rebuttal Comments: \n\nThank the authors for the response. After reading the rebuttal, I decided to change my rating to 5 for the following reasons:\n\n* Theorem 3.3 in the original manuscript has a major flaw which is also mentioned in the review of reviewer 3. The remedied theorem is considered as a substantial change compared to the original one.\n* Experiments do not fully justify the superiority of the proposed method in training deep GNNs. The performance on ogbn-product degrades when the depth of GNNs goes to 15. It is not clear whether shallow subgraph samplers really help with training \"deep\" models. \n* The empirical results are not strong enough to support the theoretical claims. The best results achieved by shaDow-GNN on ogbn-arxiv and ogbn-product are 72.28 and 80.09 which rank 15th and 9th respectively on the OGB leaderboard. The results should be improved before being accepted.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0HFiG4lNsPg", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 simple but interesting new graph sampling method for graph neural networks, called “deep GNN, shallow sampler”. Centered on the target nodes, they only sample shallow subgraphs within $L_0$-hop neighborhood and then run an $L$-layer GNN ($L>L_0$) on these subgraphs and aggregate their embeddings.  In this way, they can limit the message passing only within a shallow neighborhood to exclude noisy nodes; and they can also improve the expressivity by using deep GNN. To my understanding, the two most similar works are GraphSAGE and GraphSAINT. Compared to GraphSAGE, it samples the subgraphs instead of just $l$-hop nodes (it means they may contain more edges/circles), and it can be more expressive; compared to GraphSAINT, it requires the samples to be centered around target nodes and shallow, and it also changes the way of subgraph ensemble and makes it applied to the testing phase. \nIn general, I think this paper has concentrated contributions and it could be impactful in practical use, but I still have some concern.\n1.\tWhen the authors compare the expressivity with “shallow GNN, shallow sampler”, it seems to me that $L=L_0+1$ is enough (we cannot have edges with distance more than $L_0+1$ to the target node). Adding more layers of GNN does not help with the expressivity. Even if my assumption is false and adding more layers is helpful, the authors also need to do more sensitive analysis on the impact of different numbers of GNN layers.  \n2.\tExperiments: 3-layer or 5-layer GNN can be regarded deep, we know directly running the original model does not perform well due to the over-smoothing issue. However, there are many tricks to solve it, such as Jumpingknowledge, Skip Connection, DropEdge. I think the baseline models should use one of these tricks to make the accuracy comparison more reasonable, and it will also be interesting to see whether these tricks are necessary for the proposed model. \n3.\tOne of the main advantages of graph sampling is its efficiency. In the experiments, the authors show the computation cost of each target node. This is OK but it seems to me that showing the running time is a more intuitive and better way. Also, it is better to add the comparison with GraphSAINT in terms of running time or epochs (e.g. adding the GraphSAINT results in Figure 2).\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors propose a simple yet interesting new graph sampling method for graph neural networks.  It addresses the two main problems that GNNs have not previously been extended to deep GNNs: expressivity and computational cost.  Through experiments, the authors show the effectiveness of the proposed algorithm. 

Overall, the proposed approach is interesting.  However, the reviewers were still not convinced by the response, and the paper is still below the acceptance threshold.  I encourage the authors to revise the paper based on the reviewer's comments and resubmit it to a future venue. 
Decision: Reject