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) (Ātr (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) z 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-GININ:: 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 discriminnaiveenss 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 V.--- 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 Σuev 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 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, R
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
(I)
0.9688
0.6838
(1)
0.0222
0.7905 #OU006
(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
000001
(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, SHA GNNs (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. 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é-Bue, 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": "useB1Db4Th0", "reviewer": "Reviewer_29rS", "summary": "This paper aims to tackle two challenges in GNN: oversmoothing and neighbor explosion. To this end, the authors introduce a model, SHADOW, to decouple GNN's depth (number of layers) and scope (receptive field). The proposed model enables GNNs to treat their depth and scope independently, leading to provable improved capacity for GCN, GraphSAGE, and GIN. Extensive experiments show SHADOW's clear advantage over state-of-the-art methods.", "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": "Strength:  \n* Connections to existing works are well established. Section 3 describes the connection between SHADOW and GCN/GraphSAGE/GIN, and how SHADOW can improve these GNNs. Theoretically, SHADOW can: (1) help GCN to alleviate oversmoothing, (2) extend GraphSAGE to approximate functions while GraphSAGE solely can not, and (3) enable GIN to go beyond 1-WL.\n* After decoupling, the depth and scope of GNN can be tuned independently. Notably, the authors explain why we need a larger depth than a larger scope. As an example, SHADOW-SAGE benefits from using a deep model, which may have larger depth than scope.\n* The design of subgraph extraction functions is well studied. \n* The design of experiments is reasonable, involving various datasets. The choices of baselines are fair. \nSufficient ablation studies validate the model choices (e.g., six GNNs are examined as model's backbone).\n* The paper is well written and easy to follow. Code is provided for reproducible purposes.\n\nI did not see outstanding weaknesses in this paper. Two recommendations:\n* It is better to prioritize SHADOW-GIN results to the main text instead of appendix. Because one significant contribution is that SHADOW improves GIN to exceed the power of 1-WL.\nBesides, empirical evaluation on SHADOW-GIN's ability to detect graph isomorphism can be considered. \n\n* For some graphs, distant neighbor matters, which could be a limitation for the proposed model. Though this paper claims many real-world graphs exhibit minor impacts on distant nodes, but mentioning such a limitation in the main paper is recommended.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "es0rRMtvmoa", "reviewer": "Reviewer_3DBS", "summary": "This paper proposes to control the receptive field of GNNs by extracting a small subgraph for every node, e.g. a 2-hop neighborhood. This has computational advantages since it is now easy to mini-batch nodes with their corresponding subgraphs and it allows to build deeper GNNs acting independently on each subgraph, thus avoiding oversmoothing. The paper demonstrated empirical improvements on several node classification benchmarks and a link prediction task.", "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": "- The proposed approach has computational advantages and leads to small empirical improvements, however, the main motivation is unclear. As the authors state, using $L$-hop subgraphs is equivalent to a GNN with $L$ layers. ShadowGNN allows to build models with $L' > L$ layers while keeping the receptive field to $L$ hops. I am not convinced that this is beneficial: while using more layers can be beneficial as it increases the number of parameters and overall depth, one can alternatively use a $L$-layer GNN with deeper MLPs (or ResNets, etc.) at every layer. I think it is important to conduct additional experiments to show that setting $L' > L$ in ShadowGNN is indeed beneficial as opposed to the aforementioned way of deepening GNNs. Currently, it is unclear, neither theoretically nor empirically, what is the benefit of allowing nodes to communicate with each other multiple times. In the datasets considered in experiments, since 2-hop neighborhood is sufficient to capture important information in the graph, I'd be interested to see a comparison to 2-layer GNNs with deeper feature extractors, i.e. $H^{(l)}$ can be a deeper MLP/ResNet to match the number of parameters of a $L'=5$ ShadowGNN.\n- \"a shallow neighborhood is necessary and sufficient for the GNN to learn well\" - this is a very strong claim and I do not think that it is true. I recommend revising it and adding a discussion of the limitations of the proposed method in the context of capturing long-range dependencies. While a shallow neighborhood may be sufficient for social and citation network graphs, it could be insufficient to capture important properties of molecules in chemistry applications. The problem of designing GNNs that can capture long-range dependencies and not suffer from oversmoothing was studied in \"On the bottleneck of graph neural networks and its practical implications\" (2021) by Alon and Yahav.\n- l342 says that $L' > 5$ can further improve accuracy, but the performance of $L' = 7$ in Table 14 in the appendix does not show any improvements.\n- Could you please clarify what you mean by \"a depth-3 $G_{[v]}$ differs from the 3-hop neighborhood$ in l359.\n\nMinor:\n- l63: \"the a\"\n- l91: missing square brackets in the index\n- l114: \"sufficeint\" -> sufficient\n- l245: \"we would a\" - missing a verb", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss the limitations of their approach. The main limitation in my opinion is the strong assumption that \"a shallow neighborhood is necessary and sufficient for the GNN to learn well\" - this is not true in the problems where long-range dependencies are important, and where GNNs are currently underperforming due to oversmoothing. Please see the main review for more details.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "NFVtrY2AWkD", "reviewer": "Reviewer_KB4T", "summary": "This work proposes a design principle (SHADOW) to enrich the expressive power of GNNs: it first extracts a localized subgraph as the fixed input receptive field to the GNN, and then the depth of the GNN can be selected separately. This work shows that the proposed design can be applied to various GNNs (e.g., SHADOW-GCN, SHADOW-SAGE, and SHADOW-GAT), and it provides theoretical analysis on the expressive power of three SHADOW-GNNs (the ones mentioned above) comparing to their original counterparts. It further conducts experiments on several large graph benchmark datasets and demonstrates the superior performance of SHADOW-GNNs.", "questions": "", "limitations": "", "rating": 5, "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": "This work proposes a \"decoupling\" design principle that separates the depth and scope of GNNs. The work provides some theoretical and empirical support to demonstrate the proposed design improves both the accuracy and computation efficiency. To be more specific, the work provides theoretical analysis on the expressive power of the proposed design, and hand-constructed cases where the SHADOW-GNNs are more expressive than its standard counterparts. The experimental results also show some improvements of the SHADOW-GNNs in test accuracies on ogbn benchmark datasets (6 node classification datasets and 1 link prediction dataset). The presentation of the work is very clear, and I enjoy reading it through. This work also tries to tackle two fundamental obstacles in deep GNNs: the expressive challenge and the computation, which are significant problems to be addressed in the community. \n\nWhile the work studies an important problem, my main concern lies in the EXTRACT function of the proposed principle. \n1. It seems most theorems and corollaries presented in this work are highly dependent on some appropriate EXTRACT functions (e.g., Corollary 3.2.1, Corollary 3.2.2., and Theorem 3.3). In these cases, the EXTRACT function needs to generate a localized subgraph for each of the nodes to satisfy certain properties/constraints, but it is not clear how we can obtain such an EXTRACT function without too much prior information on the given tasks. As the success of a SHADOW-GNN is greatly dependent on a good EXTRACT function, as a design principle, it is also vital to provide clear guidance on how to find/design the EXTRACT function.\n2. Although the authors slightly touch on 3 possible directions to come out with appropriate EXTRACT functions: heuristic-based, model-based, and learning-based, all of them still lack practical guidance. The model-based approaches need access to the generation process of the input graphs, which might not be available in real-world tasks. The authors also provide an example of a heuristic-based approach, which is based on a hand-engineered feature (the page rank score of other nodes to the given node), and such graph metrics are often based on human insights and expertise. The learning-based approach sounds interesting but is left to future work. \n3. How does the proposed design principle differ from neighbor-sampling (e.g. [1, 2]) and subgraph-sampling approaches (e.g. [3, 4])?\n\nMinor comment: \n- provide a more direct comparison for the reduction in computation and hardware cost with their counterparts: e.g., add new legends to Figures 6 and 7 representing the performance of the standard GNNs.\n\n[1] William L Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.\n\n[2] Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. In ICML, 2018.\n\n[3] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks.  In Proceedings of the 25th ACMSIGKDD International Conference on Knowledge Discovery & Data Mining, pages 257–266, 2019.\n\n[4] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In ICLR, 2019.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss any potential negative societal impacts of their work. Some possible perspectives to think about potential societal impacts include energy consumption, reusability of trained models, easy deployment on mobile devices and so on.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "8"}, "extra_text": {}}, {"review_id": "IjccyN-lgua", "reviewer": "Reviewer_ChBa", "summary": "The paper introduces a framework to design GNNs with decoupled depth and scope. The main motivation of the paper is to overcome the caveats arising when training GNNs on very large graphs: (i) over-smoothing and (ii) expensive computation; that rise due to the need for a deep GNN to extract meaningful information. The basic idea of the paper is to apply a GNN only on predefined subgraph neighborhoods specified by an $\\texttt{EXTRACT}$ operator for each node. The choice of the subgraph neighborhoods defines the GNN scope independently of the depth. The authors explain why this model prevents over-smoothing of the entire graph and shows greater expressivity over commonly used 1-WL GNNs.", "questions": "", "limitations": "", "rating": 4, "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": "1. **Originality**\n\n   The authors do not cite the work [1], which suggests a basically very similar idea. [1] could be thought of as a version of this work, where the $\\texttt{EXTRACT}$ operator extracts K-hop ego networks and apply GNNs of depth $K$ and not $K’>K$ as suggested in this work. The theoretical result of superior expressivity over 1-WL is also already shown in [1].\n\n   I therefore feel that the novelty of the ideas in this paper is incremental. \n\n2. **Experimental Evaluation**\n\n   It appears that the authors have done an extensive experimental evaluation of their work. \n\n   However, although achieving state-of-the-art performance on most of the datasets, the performance gain is quite small (except for link prediction), and it seems that there are many “tricks” under the hood that were needed to get these results. Furthermore, I would have wanted to see experimental evidence for the need of $L'>L$ layers for a depth-$L$ neighborhood choice. I suspect the empirical benefits do not exist as [1] is able to reach good performance without it. \n\n3. **Theory**\n\n   The authors discuss over-smoothing but then suggest applying a deep GNN on subgraphs which basically over-smooth subgraphs. I wonder whether the authors tried to apply fewer layers? \n\n   \n\n   Since I’m not convinced by the experimental evaluation, and due to the similarity to [1], I, unfortunately, think that the contribution of this work is limited.\n\n---\n\n[1] You, J., Gomes-Selman, J.M., Ying, R., & Leskovec, J. (2021). Identity-aware Graph Neural Networks. *AAAI*.\n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors do not discuss societal impacts. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an interesting idea of limiting GNNs to local neighborhoods around each node, which can be used to decouple the depth and scope dimensions of the model.  This change led to great empirical results and computational savings.

However, on the theoretical side the authors made some very strong claims without proper support.  To name a few:
* “A shallow neighborhood is necessary and sufficient for the GNN to learn well.”  This is clearly over-claiming.  Lots of problems that require global reasoning across a whole graph cannot be solved when restricting to small neighborhoods.
* “proposed a first-of-its-kind “decoupling” design principle for the general GNN architecture;” (in discussions)  This is over-claiming.  It is not unusual to see GNNs using more layers than the graph diameter.  For example [this paper](https://arxiv.org/abs/1802.03685) even used GNNs up to 1000-layers to solve certain problems.

Also after a closer inspection of the proofs of the various claims in the paper, the AC found that some proofs are questionable, or at least unclear.

For example, in the proof for shaDow-SAGE expressivity: in order to simulate a L-layer GraphSAGE, the EXTRACT function needs to return an L-hop neighborhood.  The proof notably does not cover cases where the neighborhood size is smaller than L which is the case targeted by the paper, and it is obvious that some functions that can be represented by L-layer GraphSAGE won’t be able to be represented by the proposed Shadow-SAGE with a neighborhood size < L.

Similarly, it is clear that there are some graphs distinguishable by shaDow-SAGE with a small neighborhood not distinguishable by 1-WL.  But on the other hand the provided proof does not cover cases where some graphs may be distinguished by 1-WL but potentially can not be distinguished by shaDow-SAGE with a small neighborhood size.

For these proofs it would be good to clarify when we are talking about shaDow-SAGE with a small neighborhood size (the most important and interesting case for this paper), and when we are talking about shaDow-SAGE with a full graph as the neighborhood size (not interesting and not even relevant for the main discussion of this paper).

I hope the authors can improve the writing of this paper based on the feedback and suggestions, and send the paper to the next venue.

AC
Decision: Accept (Poster)