Decoupling the Depth and Scope of Graph Neural Networks
Authors: Hanqing Zeng
Muhan Zhang
Yinglong Xia
Ajitesh Srivastava
Andrey Malevich
Rajgopal Kannan
Viktor Prasanna
Long Jin
Ren Chen
Venue: NeurIPS 2021 Poster (2021)
Keywords: Graph Representation Learning
Subgraph Mining
Expressive Power
Scalability

Abstract: State-of-the-art Graph Neural Networks (GNNs) have limited scalability with respect to the graph and model sizes. On large graphs, increasing the model depth often means exponential expansion of the scope (i.e., receptive field). Beyond just a few layers, two fundamental challenges emerge:  1. degraded expressivity due to oversmoothing, and 2. expensive computation due to neighborhood explosion. We propose a design principle to decouple the depth and scope of GNNs – to generate representation of a target entity (i.e., a node or an edge), we first extract a localized subgraph as the bounded-size scope, and then apply a GNN of arbitrary depth on top of the subgraph. A properly extracted subgraph consists of a small number of critical neighbors, while excluding irrelevant ones. The GNN, no matter how deep it is, smooths the local neighborhood into informative representation rather than oversmoothing the global graph into “white noise”. Theoretically, decoupling improves the GNN expressive power from the perspectives of graph signal processing (GCN), function approximation (GraphSAGE) and topological learning (GIN). Empirically, on seven graphs (with up to 110M nodes) and six backbone GNN architectures, our design achieves significant accuracy improvement with orders of magnitude reduction in computation and hardware cost.

Decoupling the Depth and Scope of Graph Neural Networks
Hanqing Zeng USC
Muhan Zhang Peking University, BIGAI muhan@pku. edu. en
Yinglong Xia Facebook AI yxia@fb. com
Ajitesh Srivastava USC a Ajiteshs@usc.edi
zengh@usc.
Andrey Malevich
Rajgopal Kannan US ARL rajgopal kannan civêmail... mil
Viktor Prasanna USC prasannaQusc.edu
Facebook AI
amalevich@fb.com com
Long Jin
Ren Chen
Facebook AI longj in@fi.n..ccco com
Facebook AI
renchen@fb.com com
Abstract
State-of-the-art Graph Neural Networks (GNNs) have limited scalability with spect to the graph and model sizes. On large graphs, increasing the model depth often means exponential expansion of the scope (i.e., receptive field). Beyond just a few layers, two fundamental challenges emerge: degraded expressivity due to oversmoothing, and 2. expensive computation due to neighborhood explosion. We propose design principle to decouple the depth and scope of GNNs to generate representation of target entity (i.e., node subgraph as the bounded-sizz scope, and then apply a GNN of arbitrary depth on top of the subgraph. A properly extracted subgraph consists of small number of critical neighbors, while excluding irrelevant ones. The GNN, no matter how deep it is, smooths the local neighborhood into informative representation rather than oversmoothing the global graph into "white noise". Theoretically, decoupling improves the GNN expressive power from the perspectives graph signal pro- cessing (GCN), function approximation (GraphSAGEr and topological learning (GIN). Empirically, on seven graphs (with up 10M nodes) and six backbone GNN architectures, our design achieves significant accuracy improvement with orders of magnitude reduction in computation and hardware cost.
edge), first extract localized
Introduction
Graph Neural Networks (GNNs) have now become the state-of-the- art models for graph mining 4X
13
facilitating applications such as social recommendation 35 37 knowledge understanding
40 38
59
and drug discovery 44 [2]. With the numerous architectures proposed [22 12 44 49
still remains an open question how to effectively scale up GNNs with respect to both the model size and graph size. There are two fundamental obstacles when we increase the number of GNN layers:
Expressivity challenge (i.e., oversmoothing features collapses embedding vectors of different nodes into a fixed, low-dimensional subspace.
36
39
iterative mixing of neighbor
Conrespondence to: Muhan Zhang, muhan@pku. edu. cn
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Scalability challenge (i.e., neighbor explosion о 9 55 ) recursive expansion of multi- hop e
neighborhood results in exponentially growing receptive field size (and thus computation cost).
To address the expressivity challenge, most remedies focus on neural architecture exploration: propose more expressive aggregation functions when propagating neighbor features. [3 use residue-style design components to construct flexible and dynamic receptive fields. Among them, [50 28 [8] use skip-connection across multiple GNN layers, and
44
12
49
29
50
28
18
34
34 [3 encourage multi-hop message passing within each single layer. As for the scalability challenge, sampling methods have been explored to improve the training speed and efficiency.
Importance based layer-wise sampling [ [T] and subgraph-based sampling [54 9 55 alleviate
neighbor explosion, while preserving training accuracy. Unfortunately, such sampling methods
cannot be naturally generalized to inference without accuracy loss (see also Section
The above lines of research have only guided us to partial solutions. Yet what is the root cause of both the expressivity and scalability challenges? Setting aside the design of GNN architectures or sampling schemes, we provide an alternative perspective by interpretting the data in a different way.
Two views on the graph. Given input graph 9 with node set V, the most straightforward way to understand G is by viewing it as single global graph. So any two nodes w and belong to the same G. and if u and v lie in the same connected component, they will ultimately see each other in their own neighborhood no matter how far away u and v are. Alternative to the above global view, we can take a local view on G. For each node v. there is a latent Glv surrounding it which captures the characteristics of just v itself. The full G is observed (by the data collection process) as the union of all such 9pe. Consequently, Vis] rather than V defines v's neighborhood: if u & Vioj. V will never consider u as a neighbor. Our "decoupling" design is based on the local view.
Scope of GNNs. Both the expressivity and scalability challenges are closely related the en- largement of the GNN's scope (i.e., receptive field). More importantly, how we define the scope is determined by how we view G. With the global view above, an L-layer GNN has the scope of the full L-hop neighborhood. With the local view, the GNN scope is simply Vio] regardless of the GNN depth. The two existing lines of research, one on architectural exploration and the other on sampling, both take the global view. Consequently. the depth (i.e., number of layers) and scope of such GNNs are rightly coupled. Such coupling significantly limits the design space exploration of GNNs with various depths [53]. Consider the example of geon-products, a medium-scale graph in Open Graph Benchmark [16]. The average number of 4-hop neighbors around 0.6M, corresponding to 25% of the full graph size. To generate representation of single target node, a 4-layer coupled GNN needs to propagate features from the 0.6M neighbors. Such propagation can be inefficient or even harmful since most nodes in the huge neighborhood would be barely relevant to the target node.
Decoupling the GNN depth and scope. Taking the local view on G, we propose general design principle to decouple the GNN depth and scope. To generate the representation of the target node v, we first extract from G a small subgraph Guj surrounding v. On top of Giv). we apply a GNN whose number of layers and message passing functions can be flexibly chosen. "Decoupling" means we treat the scope extraction function and GNN depth as two independently tuned parameters effectively we introduce a new dimension in the GNN design space. We intuitively illustrate the benefits of decoupling by an example GNN construction, where the scope is the L-hop neighborhood and depth is L' (L' L). When we use more layers (L') than hops (L), each pair of subgraph nodes may exchange messages multiple times. The extra message passing helps the GNN better absorb and embed the information within scope, and thus leads to higher expressivity. We further justify the above intuition with multifaceted theoretical analysis. From the graph signal processing perspective, we prove that decoupled-GCh, performs local-smoothing rather than oversmoothing, as long as the scopes of different target nodes are different. From the function approximation perspective, we construct a lincar target function on neighbor features and show that decoupling the GraphSAGE model reduces the function approximation error. From the topological learning perspective, we apply deep GIN-style message passing to differentiate non-regular subgraphs of regular graph. As result, our model is more powerful than the 1-dimensional Weisfeiler- Heesfeiler--ehhan test [41].
The decoupling principle leads to practical im- plementation, SHA Decoupled GNN on a shallow subgraph. In SHADOW-GND scope is a shallow yet informative subgraph, only containing a fraction of the 2- or 3-hop neighbors of G (see Section 5). On the other hand, the model of SHADOW-GNN is deeper (e.g., T,' = 5). To efficiently construct the shallow scope commodity hardware, we propose various subgraph
Practical implementation: SHADOW-
the
2

---

extraction functions. To better utilize the subgraph node embeddings after deep message pass- ing, we propose neural architecture extensions such as pooling and ensemble. Empirically, our "decoupling" design improves both the accuracy and scalability. On seven benchmarks (includ- ing the largest ogbn-papers1 1000pers100MMM graph with 111M nodes) and across two graph learning tasks, SHADOw-GNNS achieve significant accuracy gains compared to the original models. Meanwhile, the computation and hardware costs are reduced by orders of magnitude. Our code available at htt.ab..cco/accbboooeeeeaaaa ch/ shaDow_ GNN
2 Preliminaries
Let 9 (V, X) be an undirected graph, with node set V, edge set & _ V x V and node feature matrix Let denote the set of v's direct neighbors in G. The wh row of X corresponds to the
X E R xd length-d feature of node u. Let A be the adjacency matrix of G where Au, 1 if edge (u, v) E
and Au, 0 otherwise. Let D be the diagonal degree matrix of A. Denote Á D. - A. as the adjacency matrix after symmetric normalization ("*" means augmented with self-edges), and Ā D- A (or D.-A,, A..) as the one after random walk normalization. Let subscript "[u]" mark the quantities corresponding to a subgraph surrounding node u. For example, the subgraph itself is Giv)- Subgraph matrices X [m] and Apr have the same dimension as the original X and A. Yet, row vector
[o]] 0 for & Viul- Element [A[ii] n,w 0 if either & Vloj w & Vin--
For an T-layer GNN, let superscript "(t)" denote the layer-& quantities. Let d()) be the number of be the input and output features. So ()) X and d( d. Further, let a be the activation and (( be the learnable weight. For example, GCN layer performs (1) (Āt (AH()))(())) A GraphSAGE layer performs H o H (w( +
channels for layer E; (t(1)) E R (g))) and () E &R (Vl
(w!()
Our analysis Section mostly focuses on the node classification task. Yet our design can be generalized to the link prediction task, as demonstrated by our experiments in Section S
Definition 2.1. (Depth of subgraph) Assume the subgraph Giv] is connected. The depth of 9ui is defined as maxueMy. d (u, v). where d (u, v) denotes the shortest path distance from u to v.
The above definition enables us make comparison such as "the GNN is deeper than the subgraph". For "decoupling the depth and scope", we refer to the model depth rather than the subgraph depth.
3 Decoupling the Depth and Scope of GNNs
"Decoupling the depth and scope of GNNs" is a design principle to improve the expressivity and scalability of GNNs without modifying the layer architecture. We name a GNN after decoupling SHADOW-GNN (see Section (36 for explanation of the name). Compared with a normal GNN, SHADOw-GNN contains an additional component: the subgraph extractor EXTRACT. To generate embedding of a target node v, SHADOw-GNN proceeds as follows: We use EXTRACT (u, 9) to return connected Gjj). where Glu is a subgraph containing v, and the depth of 9lu) is L. 2. We build an L'-layer GNN on Gi-] by treating 9iv] as the new full graph and by ignoring all nodes / edges not in Goj- So Gjv is the scope of SHADOW-GNN The key point reflecting "decoupling" is that L' > L.
A normal GNN is closely related to a SHADOW-GNN Under the normal setup, an L-layer GNN operates on the full G and propagates the influence from all the neighbors up to L hops away from v. Such GNN is equivalent to model where EXTRACT returns the full L-hop subgraph and L' L.
We theoretical demonstrate how SHADOw-GNN improves expressivity from three different angles. On SHADow-GE GCN (Section 3.1. we come from the graph signal processing perspective. The GCN propagation can be interpreted as applying filtering on the node signals [47]. Deep models correspond to high-pass filters. Filtering the local graph G preserves richer information than the global G. On MAADOW-SAGE (Section 3.2), we view the GNN as a function upproximator. We construct a target function and study how decoupling reduces the approximation error. On SHADow-GIn (Section 3.3), we focus on learning topological information. We show that decoupling helps capture local graph structure which the ID Weisfeiler-Lehman test fails to capture.
3

---

3.1 Expressivity Analysis on SHADow-GCN: Graph Signal Processing Perspective
Each GCN layer smooths the features of the direct (i.e., 1-hop) neighbors, and many GCN layers smooths the features of the full graph. Eventually, such repeated smoothing process propagates to any target node just the averaged feature of all V. "Oversmoothing" thus incurs significant information loss by wiping all local information.
GCNs 22
suffer from "oversmoothing" 30
Formally, suppose the original features X reside in a high- -ige--imensional space RDxxxd Oversmoothing pushes X towards a low-dimensional subspace R|V] kd' where d' < d. Corresponding analysis comes from two perspectives: oversmoothing by a deep GCN, and oversmoothing by repeated GCN- style propagation. The former considers the full neural network with non-linear activation, weight and bias. The later characterizes the aggregation matrix M lim, A' X.X. It is shown that with the vanilla architecture, a deep GCN with bias parameters does not oversmooth [17]. In addition, various tricks (60) 39 34] can prevent oversmoothing from the neural network perspective. However, a deep GCN still suffers from accuracy drop, indicating that the GCN-style propagation (rather than other GCN components like activation and bias) may be the fundamental reason causing difficulty in learning. Therefore, we study the asymptotic behavior of the aggregation matrix M under the normal and SHADOW design. In other words, here in Section 3.1] we ignore the non-linear activation and bias parameters. Such setup is consistent with many existing literature such as [30 33 34 60).
Proposition 3.1. Do number feature propagation by SHADOw- leads to
(p)o) = [[em] (e]
(1)
where evj defined by [[pi]
(w) V Eweyy (1n] Opp (u) returns the degree of in 910] plus
Oversmoothing by normal GCN propagation. With a large enough L, the full L-hop neighbor- hood becomes V (assuming connected g). So V u, v have 9in 9in) G. implying C(u eiu) and x. [[) X. From Proposition 3.1] the aggregation converges to a point where no feature and litile structural information of the target preserved. The only information in myy is v's degree.
Local-smoothing by SHA DOW-GCN propagation. With a fixed subgraph, no matter how many times we aggregate using A,) the layers will not include the faraway irrelevant nodes. From Proposition 3.1 m[j is a linear combination of the neighbor features [(j]- 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 EXTRACT and is independent of the model depth. Intuitively, if EXTRACT picks non-identical subgraphs for two nodes u and v. the aggregations should be different due to the different domains of the linear transformation. Therefore, SHADOw-GCN preserves local feature information whereas normal GCN preserves none. For structural information in m(e), note that Ejo] is a normalized degree distribution of the subgraph around v. and [e|il] indicates the role of the target node in the subgraph. By simply letting EXTRACT return the 1-hop subgraph, [e[w]] alone already contains all the information preserved by a normal GCN, which is e's degree in G. For the general EXTRACT, C(n) additionally reflects v's ego-net structure. Thus, deep SHADOW GCN preserves more structural information than deep GCN.
Theorem 3.2. Let myy = og (v)- mpp where Φg is any non-zero function only depending on the structural property of u. Let M = =m, e E V}. Given 9, EXTRACT and some continuous probability distribution in IRIVixd to generate X, then mi( + miy if V # V(sl. almost surely.
Corollary 3.2.1. Consider EXTRACT, where Vu E V, [M]] S n. Then [M] 2 y
a.s.
Corollary 3.2.2. Consider EXTRACT, where V u E, Vio) A Viuj- Then M
| a.s.
Theorem proves SHADOw-GOS does not oversmooth: 1. A normal GCN pushes the aggregation of same-degree nodes to the same point, while SHADOw-GCN with EXTRACT, ensures any two nodes (even with the same degree) have different aggregation. 2. A normal GCN wipes out all information in X after many times of aggregation, while SHADoW-GCT always preserves feature information. Particularly, with og (v) (fj, (v)) -1/2 normal GCN generates only one unique value of m for all v. By contrast, SHADOw- GNN generates | different values for any og function.

---

3.2 Expressivity Analysis on SHADOW-SAGE: Function Approximation Perspective
We compare the expressivity by showing 1. SHADoW-SAGE can express all functions GraphSAGE can, and 2. SHADoW-SAGE can express some function GraphSAGE cannot. Recall, GraphSAGE
layer performs the following: he = a ((w/") he f + (W3") (AAt EuEN. ho n
We can prove Point by making an Llayye SHADOW- SAGE identical an L-layer GraphSAGE with the following steps: 1. let EXTRACT return the full L-hop neighborhood, and 2. set W = I,
W(())
for L + < S L'. For point 2, we consider a target functioo: (X, (x.991))
C
E Euen. 6(u) (u) T for some neighborhood Gly.. scaling constant C and 8lu] (w) as defined in
Proposition 3.1 An expressive model should be able to learn well this simple linear function T.
GraphSAGE cannot learn T accurately, while SHADoW- SAGE can. We first show the GraphSAGE case. Let the depth of 900 be L. Firstly, we need GraphS perform message passing for exactly L times (where such a model can be implemented by, e.g. L layers or L' layers with W₂ 0 for L' - L layers). Otherwise, the extra L' - L message passings will propagate influence from nodes v E Viuj. violating the condition that is independent of v'. Next, suppose GraphSAGE can learn
function such that on some Ko... we have C (9(x) = (g()) We construct another 9% by adding an extra edge e connecting two Lepth-L nodes in 9/.j- Edge e changes the degree distribution أ1v] (-), and thus T (9 # (9%) On the other hand, there is no way for GraphSAGE: to propagate the influence of edge e to the target v, unless the model performs at least + message passings. So S (Gi)) (9%) regardless of the activation function and weight parameters. Therefore, Ç T.
For SHADOW-SAGE, let EXTRACT return G/p)- Then the model can output Ç'
[ M
X
after
a,;
we 1. set W and wi(0) for all layers, and 2. either remove the non-linear activation or bypass ReLU by shifting X with bias. With known results in Markov chain convergence theorem
27 derive the following theorem by analyzing the convergence of Á when L' 00.
Theorem 3.3. SHADOW-SAGE can approximate T with error decaying exponentially with depth.
We have the following conclusions from above: SHADoW-SAGE is more expressive than Graph- SAGE. 2. appropriate EXTRACT function improves SHADOW- GNN expressivity. 3. There exists cases where it may be desirable set the SHADOw-GNN depth much larger than the subgraph depth.
3.3 Expressivity Analysis on SHA DOW-GGNIN:: Topological I. Learning Perspective
While GCN and GraphSAGE popular architectures in practice, they not the theoretically most discriminative ones. The work in [4] establishes the relation in discriminativeness between GNNs and 1- I-dimensional Weiseeiler-Lehman test (i.e., 1-WL). And GIN [49] is example architecture achieving the same discriminativeenss as 1-WL. We show that applying the decoupling principle can further improve the discriminnaiveensss of such GNNs, making them more powerful than 1-WL.
1-WL is a graph isomorphism test aiming at distinguishing graphs of different structures. A GNN as expressive as W- thus well captures the topological property of the target node. While 1-WL is already very powerful, it may still fail in some cases. e.g., it cannot distinguish certain non-isomorphic, regular graphs. To understand why MILADOw-GNN works, we first need to un- derstand why 1-WL fails. In a regular graph, all nodes have the same degree, and thus the "regular" property describes global topological symmetry among nodes. Unfortunately, 1-WL (and the corresponding normal GNN) also operates globally on G. Intuitively, on two different regular graphs, there no way for 1-WL (and the normal GNN) assign different labels by breaking such symmetry.
u
G
Figure 1: Example 3-regular graph and the 1-hop subgraphs of the target nodes u and
On the other hand, SHA SHADOW-GNTY can break such symmetry by applying decoupling. In Section T] have discussed how HHADDw-GNNH is built from the local perspective on the full graph. The
5

---

key property benefiting SHADow-Giy is that subgraph of a regular graph may not be regular. Thus, SHADOW- GNN can distinguish nodes in a regular graph with the non-regular subgraphs as the scope. We illustrate the intuition with the example in Figure [ The graph G is 3-regular and we assume all nodes have identical features. Our goal is to discriminate nodes u and v since their neighborhood structures are different. No matter how many iterations L-WL. runs, or how many layers the normal GNN has, they cannot distinguish u and v. On the other hand, a SHADOW-GNN with I-hop EXTRACT and at least 2 layers can discriminate and v.
Theorem 3.4. Consider GNNs whose layer function is defined by
10 = 519)
1 (n! ΣS (n!-" D- (.--))
(2)
MEN,
where J and (10) are the updute and message functions of layer-t, implemented as MLPs. Then, such SHADOW-GNN is more discriminative than the I-dimensional Weisfeiler-Lehman test.
The theorem also implies that SHADow-GIN is more discriminative than normal GIN due the correspondence between GIN and 1-WL. See Appendix A for the proof of all theorems in Section 3
3.4 Subgraph Extraction Algorithms
Our decoupling principle does not rely on specific subgraph extraction algorithms. Appropriate EXTRACT can be customized given the characteristic of G. and different EXTRACT leads to different implementation of our decoupling principle. In general, we summarize three approaches to design EXTRACT: 1. heuristic based, where we pick graph metrics that reflect neighbor importance and then design EXTRACT by such metries; 2. model based, where we assume generation process 9 and set EXTRACT as the reverse process, and 3. learning based, where we integrate the design of EXTRACT as part of the GNN training. In the following, which we also empirically evaluate in Section 5 We leave detailed evaluation on the model based and learning based EXTRACT future work. See also Appendix C for details.
present several examples on heuristic based EXTRACT,
Example heuristic based EXTRACT. The algorithm is derived from the selected graph metrics. For example, with the metric being shortest path distance, we design a L-hop extractor. i.e., EXTRACT returns the full set or randomly selected subset of the target node's L-hop neighbors in G. Picking the random walk landing probability as the metric, we can design PPR- based extractor. i.e., first run the Personalized PageRank (PPR) algorithm on G to derive the PPR score of other nodes relative to the target node. Then EXTRACT define V/n by picking the top-K nodes with the highest PPR scores. The subgraph Gui the node-induced subgrap/ of & from Ve--- One can easily extend this approach by using other metrics such as Katz index [20]. SimRank
[9 and feature similarity.
3.5 Architecture
Subgraph pooling. For normal GNN performing node classification, the multi-layer message passing follows a "tree structure". The nodes at level of the tree correspond to the L-hop neighbor- hood. And the tree root outputs the final embedding of the target node. Thus, there is no way to apply subgraph pooling or READOUT on the final layer output, since the "pool" only contains a single vector. For SHADow-GNY since decouple the th layer from the L-hop neighborhood, it is natural to let each layer (including the final layer) output embeddings for all subgraph nodes. This leads to the design READOUT all the subgraph node embeddings as the target node embedding.
We can understand the pooling for SHADow-GNE from another perspective. In a normal GNN, the target node at the final layer receives messages from all neighbors, but two neighbor nodes may not have a chance to exchange any message to each other (e.g., two nodes L-hop away from the target may be 2Lphop away from each other). In design, SHADOW- GNN can pass messages between any pair of neighbors when the model depth is large enough. Therefore, all the subgraph node embeddings at the final layer capture meaningful information of the neighborhood.
In summary, the power of the decoupling principle lies in that establishes the connection between the node- / line-level task and the graph-level task. e.g., to classify a node is seen as to classify
Unlike other PPR-base models 23 6 which rewire the graph by treating top PPR nodes as direct neighbors. PPR neighborhood preserves the original multi-hop topology by returning node-induced subgraph.

---

the subgraph surrounding the node. From the neural architecture perspective, we can apply any subgraph pooling/ READOUT operation originally designed for graph classification (e.g. [57 24 4
to enhance the node classification / link prediction of SHA DOWDGWGN In particular, in the vanilla SHADOW-GNN, we can implement a trivial READOUT as "discarding all neighbor embeddings", corresponding to performing center pooling. See Appendix D
and F.3 for algorithm and experiments.
Subgraph ensemble. It may be challenging in practice to design a single EXTRACT capturing all
meaningful characteristics of the neighborhood. We can use multiple EXTRACT to jointly define the receptive field, and then ensemble multiple SHADow-Gii GNN at the subgraph level. Consider R candidates {EXTRACT:). J. each returning %.g. To generate v's embedding, we first use R branches of
L' L'-layer GNN to obtain intermediate embeddings for each g and then aggregate the R embeddings by some learnable function In practice, we design y as attention based aggregation function (see Appendix D.2). Subgraph ensemble is useful both when (EXTRACT; consists of different algorithms and when each EXTRACT; performs the same algorithm under different parameters.
CASE STUDY Consider -PR-b EXTRACT, with different threshold 0g on the neighbor PPR score. A
can approximate PPRGo [6.. PPRGo generates embedding as: &v- Eney,,) Tuky, where Tu is u's PPR score and h, MLP (æ.).. We can partition V/ob = U (0) s.t.
nodes in [/] have similar PPR scores denoted by n. and म. S 7 So &. = -E Ps (Enevy hu where A = म; Ejer 3 and V = U Mo-- Now for each branch of SHADOW- GNNNGGNNN---nnnn let parameter 02 = n; so that EXTRACT, returns V/ The GNN on V can then learn Σnev h. (e-g., by a simple "mean" READOUT). Finally, set the ensemble weight as Pi. SHA SHADow-GNN-emae GNN-ensemble learns E.,. As EXTRACT also preserves graph topology, our model can be more expressive than PPRGo.
3.6 Practical Design: SHADOw-GNN
We now discuss the practical implementation of decoupled GNN MONNSHAAN SHADOw-GNN, As the name suggests, in SHADow-Gi GNN, the scope is shallow subgraph (i.e., with depth often set or 3).
In many realistic scenarios (e.g., citation networks, social networks, product recommendation graphs), shallow neighborhood is both necessary and sufficient for the GNN to learn well. On "sufficiency", we consider the social network example: the friend of a friend of a friend may share little commonality with you, and close friends may be most 2 hops away. Formally, by the 7-decaying theorem (56), shallow neighborhood is sufficient to accurately estimate various graph metrics. On "necessity" since the neighborhood size may grow exponentially with hops, a deep neighborhood would be dominated by nodes irrelevant to the target. The corresponding GNN would first need to differentiate the many useless nodes from the very few useful ones, before it can extract meaningful features from the useful nodes. Finally, a shallow subgraph ensures scalability by avoiding "neighborhood explosion".
Remark on decoupling. So far have defined decoupled model having the model depth L' larger than the subgraph depth L. Strictly speaking, a decoupled model also admits L' = L. For example, suppose in the full L-hop neighborhood, there are 70% nodes L hops away. Applying decoupling, the EXTRACT excludes most of the L-hopp neighbors, and the resulting subgraph 9 contains only 20% nodes L hops away. Then is reasonable to consider an L-layer model on such a depth-L L subgraph as also a decouple model. Compared with an L-layer model on the full L-hop neighborhood, an L-layer model on such a depth-L G propagates much less information from nodes L hops away. So the L message passings are indeed decoupled from the full L-hop neighborhood.
Remark neighborhood. The "sufficiency" and "necessity" in shallow neighborhood not universal. In many other applications, long-range dependencies can be critical, as studied in [2]. In such cases, our practical implementation of SHADOW-GNN would incur accuracy loss. However, our decoupling principle in general may still be beneficial "shallow subgraph" is a practical guideline rather than a theoretical requirement. We leave the study on such applications future work.
4 Related Work
Deep GNNs. To improve the GNN performance while increasing the model depth, various layer architectures have been proposed. AS-GCN 18), DeepGCN (28). JK-net (50), MixHop (. Snowball (33), DAGNN (31] and GCNII (34) all include some variants of residue connection, either
7

---

across multiple layers or within a single layer. In principle, such architectures can also benefit the feature propagation of a deep SHADOW-GNNY since their design does not rely on specific neighborhood (e.g. I.-hop). In addition to architectures, DropEdge [9] and Bayesian-GDD [14] propose regularization techniques by adapting dropout [42] to graphs. Such techniques are only applied during training, and inference may still suffer from issues such as oversmoothing.
Sampling based methods. Neighbor or subgraph sampling techniques have been proposed to improve training efficiency. FasIGCN (8. VR-GCN 17]. AS-GCN [8], LADIES [6 and MVS-
GNN I0] sample neighbor nodes per GNN layer. Cluster-GCN 9 and GraphSAINT [55] sample a subgraph as the training minibatch. While sampling also changes the receptive field, all the above methods are fundamentally different from ours. The training samplers aim at estimating the quantities related to the full graph (e.g., the aggregation of the full L-hop neighborhood), and so the inference model still operates on the full neighborhood to avoid accuracy loss. For SHADOW-GN the decoupling principle is derived from a local view on G, our EXTRACT does not estimate any full neighborhood quantities. Consequently, the sampling based methods only improve the training efficiency, while SHAADW-GGN addresses the computation challenge for both training and inference.
since
Re-defining the neighborhood. Various works reconstruct the original graph and apply the GNN on the re-defined neighborhood. GDC [23] views the reconstructed adjacency matrix as the diffusion matrix. SIGN [T] applies reconstruction for customized graph operators. AM-GGN 446 utilizes the reconstruction to separate feature and structure information. The above work re-define the neighborhood. However, they still have tightly coupled depth and scope. SHADOw-GiD GNN can also work with the reconstructed graph G' by simply applying EXTRACT on G'.
Experiments
Setup. We evaluate SHADoW GNNN on seven graphs. Six of them are for the node classification
task: Flickr [55] Reddit [12], Yelp 55 ogbn-arxiv, pron-ptssuccss and ogbn-paperss 100M
[6]. The remaining is for the link prediction task: ogbl-collab [16]. The sizes the seven graphs 00M). Flickr, Reddit t and Yelp are ogbn- gebn-products and ogbn-papers10NN are transductive. measure "Fl-micro"
range from 9K nodes (Flickr) to 10M nodes
under the inductive setting. ogbn-arxic
Consistent with the original papers, for the graphs on node classification, score for Yelp and "accuracy" for the remaining five graphs. For the link prediction task, we use "Hits @50 50" the metric. See Appendix E. for details. We use W&B [5] for experiment tracking.
We construct SHA SHADOW with six backbone models: GCN [22], GraphSAGE [12. GAT 44), JK-Net [50], GIN 49, SGC [7]. The first five are representatives of the of-te-of-the-arr art GNN architectures, jointly covering various message aggregation functions as well as the skip connection design. SGC simplifies normal GCN by moving all the neighbor propagation to the pre-processing step. Therefore, SGC is suitable for evaluating oversmoothing. The nonSSHADOW models are trained with both full-batch and GraphSAINT minTiaintattch (55). Due to the massive size of the full L-hop neighborhood, we need to perform sampling when training normal GNNs in order to make the computation time tractable. GraphSAINT is suitable for purpose since 1. it is the state-of-the- art minibatch method which achieves high accuracy, and 2. it supports various GNN architectures and scales well to large graphs. On the other hand, for SHADow-Ca GNN, both training and inference are always executed in minibatches. One advantage of SHADow-GE GNN is that the decoupling enables straightforward minibatch construction: each target just independently extracts the small subgraph its own.
We implement two EXTRACT described in Section 3.4 "PPR", where we set the node budget as (200, 400} for the largest ogbn-paperse 100M and K < 200 for all other graphs; 2. "T-hop", where we set the depth as 21, We implement various subgraph pooling functions: "mean" " and "max" evaluated in this section and others evaluated in Appendix F.3 For the model depth, since L' = 3 is the standard setting in the literature (e.g., see the benchmarking in OGB [6)), we start from L' = 3 and further evaluate a deeper model of L' 5. All accuracy are measured by 5 runs without fixing random seeds. Hyperparameter tuning and architecture configurations are in Appendix E.4
SHADOw-GNN neighborhood. For both normal and SHADOW GNNs, Figure shows on average how many neighbors are L hops away from the target. For a normal GNN, the size of the neighborhood grows rapidly with respect to L,, and the nodes 4 hops away dominate the neighborhood. For Dow- using the EXXTRCC, most neighbors concentrate within 2 hops. small number of nodes are 3 hops away. Almost no nodes are 4 or more hops away. Importantly, not
8

---

Ratio of nodes at different hop P.
4-layer GNN
Any layer SHADOw (PPR)
S-SGC, F SGC,F F
S-SG, A
SGC, A
SGC, R
SGC, A
0.8
{= 1
Test accuracy
Reddit
0.6
i 2
0.8
Arxiv
0.4
0.2
i 4
0.6
Flickr
Reddit
Yelp
arxiv
products
Flickr
Reddit
Yelp
arxiv
products
Flickr
20
Power on A or Alol
Figure 2: Neighborhood composition
Figure 3: SGC oversmoothing
only does the composition of the two kinds of neighborhood differ significantly, but also the size of SHADoW-GNY scope is much smaller (see also Table Such small subgraphs are essential to high computation efficiency. Finally, we can ignore the very few distant neighbors (7. 2 4), and regard the (effective) depth of SHADow-GNN subgraph as I. (or most 3). Under such practical value of L, a model with L' 2 3 is indeed a SHADOW- GNNN (see "Remark on decoupling" in Section 3.6).
Table 1: Comparison on test accuracy //1F/FFmmooo -icro score and inference cost (tuned with DropEdge)
Method
Layers
Flickr
Reddit
Yalp
agim-arsiv
oghe-prodacts
Accumay
Cost
Accuncy
Fl-micro
Cost
Aocumey
Accurcc
Cost
GUN
0.5217400016
0.5159
2ED
0.9532-000008
6E1
0,4028-H0001
2F11
0.7186:000017
0,7170+00006
IE1
0.7567=00008
SED
GCN-SAINT
0,5155 2OU027
280
0.8523
GEL
0.51101::012
261
0.7093
IEL
SEO
0.5165 L00006
262
0.9523
1E3
0.5012
163
0,7039 10.000
IE3
0.79921000011
9E2
SHADOw-GCN
0.5231100009
(1)
0.9576L000000
(1)
0.5291 L10.000
(1)
0.7180L000024
(1)
0.77 L00007
(I)
(PPR)
0.5268+30000
1E0
0.9564
0
260
0.7206-00.025
260
0,7821
+00043
2ED
-Pooling
1.624-000002
0.5393
0.7223
0,7914
GrapiSAGE
4
3FD
0.9653
SRI
0.6178-00003
2F-1
0,7192-00007
181
0.7858-H0001
4FD
0,5144000052
0.9626
SAGE-SAINT
0,5176580U002
L000002
262
3E0
0.9670
SEI
1E3
0.64
0.639410.003
263
261
0,7013
000003
IEL
IE3
0,7923+00003
0.796410.0022
4E0
1E3
SHA DOW-SAGE
00001
1ED
0.9672 HO 0008
1E0
0.6542 0002
180
0.7163
00
100
0.7935 10
1ED
(2 hop)
2ED
0.9675 HOLD00
0.6825 1-25--0000
250
0,7180
0.7998+00000
2FD
SHADOW-SAGE
0
0.9688
0.6838
(1)
0.0222
0.7905 #0U006
(1)
(PPR)
2E0
0.9692-000007
210
0.6518-000022
250
0.7238
2E0
0.8005 2000040
2E0
-Pooling
3/5
LOU0015
2E0
0,9703
250
0..064
150
0.7258 1000011
250
0.80671000077
IE0
GAT
000000
L.516410000
2F2
2EL
0OM
COM
2E3
1E2
0OM
COM
283
262
0.7201 LO
COM
3E3
IE2
0OM
COM
2E3
3EI
GAT SAINT
0.515R#000004
0,5225+00055 00
2F2
2F1
0.9651 H0000024
0-9671-000008
2E3
3F2
0.6459
0.6478+000022
2E3
2F2
0.6954
3E3
1F2
0.7990+00002
H0
2E3
3F1
DOA-OOTAAT
0,5349-00003
(1)
0.9707=000000
(1)
0.7238H00000
000006
(1)
(PPR)
0.5352+001028
280
0.9713:00004
2100
0.655
250
0.7274
280
0.8071 +00000
2ED
-Pooling
3/5
1.9364100000
1E0
0.9710-500004
2150
0.8506-10.000
150
2E0
0,8142 20.0011
1E0
Comparison with baselines. Table shows the performance comparison of SHADOw-GNN with the normal GNNs. All models on all datasets have uniform hidden dimension of 256. We define the metric "inference cost" as the average amount of computation to generate prediction for one test node. Inference cost is measure of computation complexity (see Appendix B for the calculation) and is independent of hardware/ / implementation factors such as parallelization strategy, batch processing. etc. For cost of SHA DIWDDWGGNN we do not include the overhead on computing EXTRACT, since it hard to calculate such cost analytically. Empirically, subgraph extraction much cheaper than model computation (see Figure 8 9
for time evaluation on CPU and GPU). During training, we apply DropEdge [39] to both the bascline and SHADOW models. DropEdge helps improve the baseline accuracy by alleviating oversmoothing, and benefits SHADOw-GNN due to its regularization effects. See Appendix F2 for results on other architectures including GIN and JK-Net.
ACCURACY We aim at answering the following questions: 1. Can we improve accuracy by decoupling a baseline model? 2. What architecture components can we tune to improve accuracy of a decoupled model? 3. What EXTRACT can we tune to improve the accuracy of decoupled model? To answer Q1, we fix the backbone architecture and remove pooling. Then we inspect "3-layer normal GNN vs. 3-layer CHADOW-GNNY and "5-layer normal GNN vs. 5-layer SHADOW-GN -NN".. Clearly, SHADOW-GNNY (with scope size no more than 200) in general achieve significantly higher accuracy than the normal GNNs. This indicates that a shallow neighborhood contains sufficient information,

---

and customizing the scope can benefit accuracy even without architecture changes (from Figure 2 depth-3 (m)) differs significantly from the 3-hop neighborhood). To answer QI, we focus on the PPR EXTRACT and thus compare the rows in blue background. We use the 3-layer SHADOW-GNN without pooling as the baseline and analyze the effects of 1. increasing the GNN depth without expanding scope, and 2. adding subgraph pooling. Comparing among the rows in light blue background, we observe that in many cases, simply increasing the depth from 3 to 5 leads to significant accuracy gain. Comparing the ligh blue rows with the dark blue rows, we observe that sometimes pooling can further improve the accuracy of SHADOW GONO. In conclusion, both types of architecture Finally, to answer Q3, we compare the
tuning are effective ways of optimizing a SHADOw- light blue rows with the light yellow rows. In general, PPR EXTRACT leads to higher accuracy than 2-hop EXTRACT, demonstrating the importance of designing good EXTRACT.
INFERENCE COST Inference cost of SHADOw-GNN is orders of magnitude lower than the normal GNNs (a 5-layer SHAADWw-GN is still much cheaper than 3-layer normal GNN), The high cost of the baselines is due to the "neighborhood explosion" with respect to more layers. SHADOW-GNT is efficient and scalable as the cost only grows linearly with the model depth. Note that GraphS AINT only improves efficiency during training since its inference operates on the full L-hop neighborhood.
Scaling to 100 million nodes. We further
Table 2: Leaderboard comparison papers 100M
scale SHADOW- GNN ogbn-papers 00M,
Method
Test accusacy
Val accuracy
Neigh size
one of the largest public dataset. Even through the full graph size is at least two orders of mag- nitude larger than the graphs in [ the lo-
GrapSAGFFiinep SIGN XL SGC
0.6706-0.0017
0.7032+00001
4R5
0.0019900019
0.6984
4ES
0.0019
0.6648 +00000
> 4F5
SHADOW-
0.7019 0.661100.001
262
calized scope of HIADOW-GNN barely needs to increase. Since SHADOW-GNN performs
SHADOW-GAT
0.6708 000001
0.7073 20.011
3E2
minibatch computation, a low-end GPU with limited memory capacity can compute SHADOW GNN on ogbn- 1atess100000 100M efficiently. We show in Appendix [F. that we can train and inference our model with as little as 4GB GPU memory consumption. This infeasible using normal GNNs. Table 2 summarizes our comparison with the top leaderboard methods [45] I1 47 We only include those methods that do not use node labels as the model input (i.e., the most standard setup). We achieve at least 3 orders of magnitude reduction in neighborhood size without sacrificing accuracy. For SIGN-XL and SGC, their neighborhood is too large to count the exact size. Also, their preprocessing consumes 5x more CPU memory than SIIADOW-GN GNNN (Appendix F.I.
Extending to link-level task. We further show that CHADow-GNN is general and can be extended to the link prediction task. There are two settings of ogbl-collab. We follow the one where validation edges cannot be used in training updates. This the setting which most leaderboard methods follow. Table 3 shows the comparison with the top GNN models under the same setting. SHADOW-SAGE outperforms the rank-/ model with significant margin.
Table 3: Leaderboard comparison on collab
Method
Test H0
Val Ho
SEAL
0.6389 00.004
DeeperGCN
0.5273=0.0047
06187=00.005
LRGA+GON
0.5221 10.0072
0.6088 10.009
SHADOW-SAGE
0.5492=000002
0.6524+0.0017
Oversmoothing. To validate Theorem 3.2 we pick SGC the backbone architecture. SGC with power L is equivalent to L-layer GCN without activation. Performance comparison between SGC and SHADow- SGC thus reveals the effect of oversmoothing without introducing other factors due to optimizing deep neural networks (e.g.. vanishing gradients). In Figure 3 we vary the power of SGC and SHADow-SGC from 1 to 40 (see Appendix E.. for details). While SGC gradually collapses local information into global "white noise", accuracy of SHA SHADow-SGG does not degrade. This validates our theory that extracting local subgraphs prevents oversmoothing.
Conclusion
We have presented a design principle to decouple the depth and scope of GNNs. Applying such a principle on various GNN architectures simultaneously improves expressivity and computation scalability of the corresponding models. We have presented thorough theoretical analysis on expres- sivity from three different perspectives, and also rich design components (e.g., subgraph extraction functions, architecture extensions) to implement such design principle. Experiments show significant performance improvement over a wide range of graphs, GNN architectures and learning tasks.
10

---

References
[1] Sami Abu-El-Haija Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. arXiv preprint (rXiv:1905.00000 2019.
[2] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
[3] 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, pages 475 486. IEEE, 2006.
[4] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, pages 874-883. PMIR, 2020.
[5] Lukas Biewald. Experiment tracking with weights and biases, 2020. Software available from wandb.com.
[6] 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. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '20, page 2464-2473, New York, NY, USA, 2020. Association for Computing Machinery.
[7] Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction, 2017.
[8] Jie Chen, Tengfei Ma, and Cao Xiao. FastGCN: Fast learning with graph convolutional networks via importance sampling. In International Conference on Learning Representations, 2018.
[9] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen. An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD '19 page 257-266
New York, NY, USA, 2019. Association for Computing Machinery.
[10] Weilin Cong, Rana Forsati, Mahmut Kandemir, and Mehrdad Mahdavi. Minimal variance sampling with provable guarantees for fast training of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, KDD '20, page 1393-1403, New York, NY, USA, 2020. Association for Computing Machinery.
[11] Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. SIGN: Scalable inception graph neural networks, 2020.
[12] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in neural information processing systems, pages 1024-1034, 2017.
[13] William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint
795405584 2017.
[14] Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Kr- ishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sampling. 2020.
[15] Kurt Hornik, Maxwell Stinchcombe, Halbert White, et al. Multilayer feedforward networks are universal approximators. Neural networks, 255):359-366, 1989.
[16] Weihua Hu, Matthias Fey, Marinka Zitiik, Yuxiao Dong. Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs, 2020.
[17] Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over- smoothing for general Graph Convolutional Networks, 2020.

---

[18] Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in neural information processing systems, pages 4558 4567, 2018.
[19] Glen Jeh and Jennifer Widom. Simrank: measure of structural-context similarity. In Proceed- ings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 538-543, 2002.
[20] Leo Katz. A new status index derived from sociometric analysis. Psychometrika, 18(1):39-43 1953.
[21] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 1411v:1412.6980, 2014.
[22] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016.
[23] Johannes Klicpera, Stefan Weißeenberger, and Stephan Günnemann. Diffusion improves graph learning, 2019.
[24] Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International Conference on Machine Learning, pages 3734 3734-3743. PMLR, 2019.
[25] Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In Proceedings of the 12th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, KDD '06, page 63 631-63,, New York, NY, USA, 2006. Association for Computing Machinery.
[26] Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Trans. Knowl. Discov. Data, 1(1):2-es, March 2007.
[27] David A Levin and Yuval Peres. Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
[28] Guohao Li, Matthias Müller, Ali Thabet, and Bernard Ghanem. DeepGCNs: Can GCNs go as deep as CNNs? In The IEEE International Conference on Computer Vision (ICCV), 2019.
[29] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. DeeperGCN: All you need to train deeper gens, 2020.
[30] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into Graph Convolutional Networks for semi-supervised learning. arXiv preprint arXiv: 18010000,,, 2018.
[31] Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. Proceed- ings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug 2020.
[32] Yu-Chen Lo. Stefano E Rensi, Wen Torng, and Russ B Altman. Machine learning in chemoin- formatics and drug discovery. Drug discovery today, 23(8):1538-11 2018
[33] Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi-scale deep graph convolutional networks. In Advances in Neural Information Processing Systems 32, pages 10945-10955. Curran Associates, Inc., 2019.
[34] Zhewei Wei Ming Chen, Bolin Ding Zengfeng Huang, and Yaliang Li. Simple and deep graph convolutional networks. 2020.
[35] Federico Monti, Michael Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi graph neural networks. In Advances Neural Information Processing Systems, pages 3697-3707, 2017.
[36] Kenta Oono and Taiji Suzuki. Graph Neural Networks exponentially lose expressive power for node classification. In International Conference Learning Representations, 2020.
12

---

[37] Aditya Pal, Chantat Eksombatchai, Yitong Zhou, Bo Zhao, Charles Rosenberg, and Jure Leskovec. PinnerSage: Multi-modal user embedding framework for recommendations at Pinterest. Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, Aug 2020.
[38] 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, pages 596-606, 2019.
[39] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. DropEdge: Towards deep Graph Convolutional Networks on node classification. In International Conference Learning Representations, 2020.
[40] 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, pages 593-607. Springer, 2018.
[41] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfenler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[42] 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):1929-1958, 2014.
[43] Jonathan M Stokes, Kevin Yang, Kyle Swanson, Wengong Jin, Andres Cubillos-Ruiz, Nina M Donghia, Craig R MacNair, Shawn French, Lindsey A Carfrae, Zohar floom-Ackermn et al. A deep learning approach to antibiotic discovery. Cell, 180(4):688-705 2020.
[44] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference Learning Representations, 2018.
[45] Minjie Wang, Da Zheng, Zihao Ye, Quan Gan, Mufei Li, Xiang Song, Jinjing Zhou, Chao Ma, Lingfan Yu, Yu Gai, Tianjun Xiao, Tong He, George Karypis, Jinyang Li, and Zheng Zhang, Deep graph library: graph-centric highly-performant package for graph neural networks, 2020.
[46] 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 page 1243-1253, New York, NY, USA, 2020. Association for Computing Machinery.
[47] Felix Wa, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger. Simplifying graph convolutional networks. arXiv preprint arXiv: 1902.07021111 051,, 2019.
[48] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S. Yu. A comprehensive survey on graph neural networks, IEEE Transactions on Neural Networks and Learning Systems, 2020.
[49] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:
2018.
[50] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks, 2018.
[51] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. GNNExplainer: Generating explanations for graph neural networks, 2019.
[52] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 974-983, 2018
13

---

[53] Jiaxuan You. Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17009-17021. Curran Associates, Inc., 2020.
[54] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Accurate, efficient and scalable graph embedding. In 2019 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 462-471, 2019.
[55] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. GraphSAINT: Graph sampling based inductive learning method. International Conference on Learning Reprexentations, 2020.
[56] Muhan Zhang and Yixin Chen. Link prediction based graph neural networks. In Advances in Neural Information Processing Systems, pages 5165-5175, 2018.
[57] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[58] 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.
(59) Yuyu Zhang, Xinshi Chen, Yuan Yang, Arun Ramamurthy, Bo Li, Yuan Qi, and Le Song. Efficient probabilistic logic reasoning with graph neural networks, 2020.
[60] Lingxiao Zhao and Leman Akoglu. PairNorm: Tackling oversmoothing in gnns. International Conference Learning Representations, 2020.
[61] Difan Zou, Ziniu Hu, Yewen Wang. Song Jiang. Yizhou Sun, and Quanquan Gu. Layer- dependent importance sampling for training deep and large graph convolutional networks. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gamett, editors, Advances Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See appendix
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (cither in the supplemental material or as a URL)? [Yes] See the released code.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the released code. It contains all configurations.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you using existing assets (c.g., code, data, models) or curating/releasing assets...
14

---

(a) If your work uses existing assets, did you cite the creators? [Yes] See citation after each dataset.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [No]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals. if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "Yedd4z0YN8e", "reviewer": "Reviewer_k7tB", "summary": "This paper proposes a design principle to decouple the depth and scope of graph neural networks (GNN). The proposed approach first extracts a localized subgraph for each target node as a bounded-size receptive field and then applies a GNN of arbitrary depth on top of the subgraph. Such decoupling improves the expressive power of popular GNN architectures including GCN, GraphSAGE and GIN. On seven graphs and six backbone GNN architectures, the design achieves state-of-the-art accuracy with a reduction in computation cost.", "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": "Strengths\n- The performance of the proposed approach is significantly better than the baselines for various backbone GNNs.\n- The authors present theoretical analysis on the expressive power of the proposed design principle.\n- Experiments are presented for both node classification and link prediction, which are representative problems in the graph domain.\n\nWeaknesses\n- Most of the theoretical analysis is straightforward (details in the next section).\n- The idea of decoupling depth and scope of GNNs is not new, especially from the perspective of sampling neighborhoods such as in FastGCN [6].\n- There are experiments only with base GNN models. If the performance gain is because the proposed approach addresses the oversmoothing problem, a comparison should be made with recent approaches for the same purpose:\n--- PairNorm: Tackling Oversmoothing in GNNs [ICLR 2020]\n--- Scattering GCN: Overcoming Oversmoothness in Graph Convolutional Networks [NeurIPS 2020]\n--- Towards Deeper Graph Neural Networks [KDD 2020]\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I’m not sure whether Theorem 3.2 is useful. If we use a small subgraph around each node for inference, the prediction is made by the features of nodes contained in the subgraph. Then, it is straightforward that two nodes in different subgraphs make different representations, as they combine different sets of node features. The theorem is useful only if the authors provide the exact condition that makes the two representations the same or different.\n\nThe authors say in Section 3.2 that “SHADOW-SAGE can approximate \\tau with error decaying exponentially with the model depth,” but the error bound is not given. It is not clear when GraphSAGE fails at expressing the tau function, and how exactly SHADOW-SAGE performs better. The authors should rewrite Section 3.2 and provide formal theorems and proofs.\n\nI’m not sure Theorem 3.3 is a fair comparison between SHADOW-GNN and the WL test, because making the subgraph for each node makes a severe limitation on the expressiveness. For instance, consider two graphs with the same node features having the following edge sets:\n■\tE1 = {(a, c), (b, c), (c, d)}\n■\tE2 = {(e, f), (f, g)}\n\nThen, SHADOW-GNN described in the paper cannot distinguish between d and g, as it looks at only the direct neighborhood of each node. I think there is no single setting that SHADOW-GNN generalizes 1-WL in any cases, unlike the conclusion that the paper implies.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "TDsiXEWpS5g", "reviewer": "Reviewer_zi5m", "summary": "The authors propose a new approach to graph neural models that decouples layer depth and vertex receptive field: a subgraph is extracted for each vertex, and vertex representations are produced for each vertex via a multi-layer graph convolutional network. Authors theoretically prove better expressive capabilities of their approach, and reduced computational cost on very large-scale datasets. Experimental results show consistent improvement on graph classification tasks. \n\n", "questions": "", "limitations": "", "rating": 9, "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": "While other approaches to graph sampling in order to reduce computational cost on large-scale graphs have been proposed, this paper appears to be the first to frame it as a strategy to decouple GNN layer depth and vertex receptive field. Furthermore, their approach allows for more representative models with respect to graph features, since graph extraction strategies can produce non 1-WL isomorphic subgraphs.\nThe paper is clearly written, with design choices justified by theoretical proofs; experiments are rigorously conducted on well-established vertex classification tasks, showing overall improvements both regarding accuracy and computational cost with respect to common graph models (while a rigorous theoretical evaluation of cost is provided, it would have been interesting to show also empirical training/inference times).\nDue to the significant advantage in relation to computational cost and memory requirements, the proposed methodology is likely to impact significantly on large-scale (i.e. >millions vertices) graph tasks.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No negative societal impact to report.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3  hours"}, "extra_text": {}}, {"review_id": "SVK6joKSDiY", "reviewer": "Reviewer_CVVn", "summary": "This paper explores on approach of decoupling depth and scope of GNNs. To mitigate degraded expressivity due to over smoothing and expensive computation due to neighborhood explosion, their shadow-GNN approach first extracts a localized subgraph around each target entity (node or edge) and apply a GNN of arbitrary depth on top of the extracted subgraph. They do some theoretical analysis to show this combats over smoothing and increases expressivity. They also performs experiments and show state-of-the-art performance on benchmarks.", "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": "Originality: This is a simple and not completely novel approach (effectively it is running a GNN on a new altered graph) but the level of analysis and the experiments are novel and contributed original insights. I haven’t seen this detailed work around this approach and analysis before.\n\nQuality: The work is thorough and of high quality. The analysis is useful and careful. I do think a better comparison to graph-altering work could be interesting. \n\nClarity: This paper is clear but also a little bit unnecessarily complicated. For example, I suppose EXTRACT_1 and EXTRACT_2 are 1 and 2 hops respectively, but I don’t think that’s defined. But overall I think they’re doing a good job.\n\nSignificance: I believe this is significant work that analyses a core aspect of graph learning in a helpful and insightful way. It provides clear take-aways and good experiments. However, I believe it should include a little bit of discussion around the results. To some extent, being more powerful is somewhat misleading in the sense that we’re restricting (altering) the graph via EXTRACT, so we’re giving the NN more (conditional on human choices and adding additional bias) information. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not addressed. ", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a new way to perform graph sampling by using small neighborhoods of points for training and testing.  The resulting method enables very deep networks to be used on a range of graph problems.  The reviewers agree that the method is simple, and that this is a merit.  While there’s some discrepancy over the usefulness of the theory, there seems to be consensus around the point of view that the presence of theoretical results adds to the paper.


Decision: Accept (Poster)