# Decoupling the Depth and Scope of
Graph Neural Networks

Hanqing Zeng
USC
<EMAIL_ADDRESS>&Muhan Zhang
Peking University, BIGAI
<EMAIL_ADDRESS>&Yinglong Xia
Facebook AI
<EMAIL_ADDRESS>&Ajitesh Srivastava
USC
<EMAIL_ADDRESS>&Andrey Malevich
Facebook AI
<EMAIL_ADDRESS>&Rajgopal Kannan
US ARL
<EMAIL_ADDRESS>&Viktor Prasanna
USC
<EMAIL_ADDRESS>&Long Jin
Facebook AI
<EMAIL_ADDRESS>&Ren Chen
Facebook AI
<EMAIL_ADDRESS>
###### 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.
††Correspondence to: Muhan Zhang<EMAIL_ADDRESS>
##  1 Introduction

Graph Neural Networks (GNNs) have now become the state-of-the-art models for
graph mining [48, 13, 58], facilitating applications such as social
recommendation [35, 52, 37], knowledge understanding [40, 38, 59] and drug
discovery [43, 32]. With the numerous architectures proposed [22, 12, 44, 49],
it 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 [30, 36, 39, 17]): iterative
mixing of neighbor features collapses embedding vectors of different nodes
into a fixed, low-dimensional subspace.

  * •

_Scalability_ challenge (_i.e._ , neighbor explosion [7, 8, 9, 55]): recursive
expansion of multi-hop neighborhood results in exponentially growing receptive
field size (and thus computation cost).

To address the expressivity challenge, most remedies focus on neural
architecture exploration: [44, 12, 49, 29] propose more expressive aggregation
functions when propagating neighbor features. [50, 28, 18, 34, 1, 33, 31] use
residue-style design components to construct flexible and dynamic receptive
fields. Among them, [50, 28, 18] use skip-connection across multiple GNN
layers, and [34, 1, 33, 31] 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 [8, 7, 61] 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 4).

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 an input graph
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ with node set
$\IfEq{}{}{\mathcal{V}}{\mathcal{V}}$, the most straightforward way to
understand $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ is by viewing it as a single
_global_ graph. So any two nodes $u$ and $v$ belong to the same
$\IfEq{}{}{\mathcal{G}}{\mathcal{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
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$. For each node $v$, there is a _latent_
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ surrounding it which captures
the characteristics of just $v$ itself. The full
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ is _observed_ (by the data collection
process) as the union of all such
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$. Consequently,
$\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$ rather than
$\IfEq{}{}{\mathcal{V}}{\mathcal{V}}$ defines $v$’s neighborhood: if
$u\not\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$, $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 to the enlargement of the GNN’s scope (_i.e._ , receptive field). More
importantly, how we define the scope is determined by how we view
$\IfEq{}{}{\mathcal{G}}{\mathcal{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 $\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$
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 _tightly coupled_. Such coupling significantly limits the design
space exploration of GNNs with various depths [53]. Consider the example of
ogbn-products, a medium-scale graph in Open Graph Benchmark [16]. The average
number of 4-hop neighbors is around 0.6M, corresponding to $25\%$ of the full
graph size. To generate representation of a 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
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$, we propose a general design principle
to decouple the GNN depth and scope. To generate the representation of the
target node $v$, we first extract from $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ a
small subgraph $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ surrounding $v$.
On top of $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$, 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^{\prime}$ ($L^{\prime}>L$). When we use more layers ($L^{\prime}$)
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-GCN 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 linear 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 a regular graph. As a result, our
model is more powerful than the 1-dimensional Weisfeiler-Lehman test [41].

Practical implementation: shaDow-GNN. The decoupling principle leads to a
practical implementation, shaDow-GNN: Decoupled GNN on a shallow subgraph. In
shaDow-GNN, the scope is a shallow yet informative subgraph, only containing a
fraction of the 2- or 3-hop neighbors of $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$
(see Section 5). On the other hand, the model of shaDow-GNN is deeper (_e.g._
, $L^{\prime}=5$). To efficiently construct the shallow scope on commodity
hardware, we propose various subgraph extraction functions. To better utilize
the subgraph node embeddings after deep message passing, we propose neural
architecture extensions such as pooling and ensemble. Empirically, our
“decoupling” design improves both the accuracy and scalability. On seven
benchmarks (including the largest ogbn-papers100M 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 is available at
https://github.com/facebookresearch/shaDow_GNN

##  2 Preliminaries

Let
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}\left(\IfEq{}{}{\mathcal{V}}{\mathcal{V}},\IfEq{}{}{\mathcal{E}}{\mathcal{E}},\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}\right)$
be an undirected graph, with node set $\IfEq{}{}{\mathcal{V}}{\mathcal{V}}$,
edge set
$\IfEq{}{}{\mathcal{E}}{\mathcal{E}}\subseteq\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\times\IfEq{}{}{\mathcal{V}}{\mathcal{V}}$
and node feature matrix
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}\in\mathbb{R}^{|\IfEq{}{}{\mathcal{V}}{\mathcal{V}}|\times
d}$. Let $\mathcal{N}_{v}$ denote the set of $v$’s direct neighbors in
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$. The $u$th row of
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$ corresponds to the length-$d$
feature of node $u$. Let $\bm{A}$ be the adjacency matrix of
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ where $A_{u,v}=1$ if edge
$(u,v)\in\IfEq{}{}{\mathcal{E}}{\mathcal{E}}$ and $A_{u,v}=0$ otherwise. Let
$\bm{D}$ be the diagonal degree matrix of $\bm{A}$. Denote
$\IfEq{}{}{\widetilde{\bm{A}}}{\widetilde{\bm{A}}}=\bm{D}_{*}^{-\frac{1}{2}}\bm{A}_{*}\bm{D}_{*}^{-\frac{1}{2}}$
as the adjacency matrix after symmetric normalization (“$*$” means augmented
with self-edges), and
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}=\bm{D}^{-1}\bm{A}$ (or
$\bm{D}_{*}^{-1}\bm{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
$\IfEq{[u]}{}{\mathcal{G}}{\mathcal{G}}_{[u]}$. Subgraph matrices
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{[v]}$ and $\bm{A}_{[v]}$ have the
same dimension as the original $\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$ and
$\IfEq{}{}{\bm{A}}{\bm{A}}$. Yet, row vector
$\left[\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{[v]}\right]_{u}=\bm{0}$ for
$u\not\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$. Element
$\left[\bm{A}_{[v]}\right]_{u,w}=0$ if either
$u\not\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$ or
$w\not\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$. For an $L$-layer GNN,
let superscript “$(\ell)$” denote the layer-$\ell$ quantities. Let
$d^{(\ell)}$ be the number of channels for layer $\ell$;
$\IfEq{\ell-1}{}{\bm{H}}{\bm{H}}^{(\ell-1)}\in\mathbb{R}^{|\IfEq{}{}{\mathcal{V}}{\mathcal{V}}|\times
d^{(\ell-1)}}$ and
$\IfEq{\ell}{}{\bm{H}}{\bm{H}}^{(\ell)}\in\mathbb{R}^{|\IfEq{}{}{\mathcal{V}}{\mathcal{V}}|\times
d^{(\ell)}}$ be the input and output features. So
$\IfEq{0}{}{\bm{H}}{\bm{H}}^{(0)}=\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$
and $d^{(0)}=d$. Further, let $\sigma$ be the activation and
$\bm{W}^{\left(\ell\right)}$ be the learnable weight. For example, a GCN layer
performs
$\IfEq{\ell}{}{\bm{H}}{\bm{H}}^{(\ell)}=\sigma\left(\IfEq{}{}{\widetilde{\bm{A}}}{\widetilde{\bm{A}}}\IfEq{\ell-1}{}{\bm{H}}{\bm{H}}^{(\ell-1)}\bm{W}^{\left(\ell\right)}\right)$.
A GraphSAGE layer performs
$\IfEq{\ell}{}{\bm{H}}{\bm{H}}^{(\ell)}=\sigma\left(\IfEq{\ell-1}{}{\bm{H}}{\bm{H}}^{(\ell-1)}\bm{W}_{1}^{\left(\ell\right)}+\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}\IfEq{\ell-1}{}{\bm{H}}{\bm{H}}^{(\ell-1)}\bm{W}_{2}^{\left(\ell\right)}\right)$.

Our analysis in Section 3 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 5.

######  Definition 2.1.

(Depth of subgraph) Assume the subgraph
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ is connected. The depth of
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ is defined as
$\max_{u\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}}d\left(u,v\right)$,
where $d\left(u,v\right)$ denotes the shortest path distance from $u$ to $v$.

The above definition enables us to 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 a shaDow-GNN (see Section 3.6 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:  1. We use
$\text{{EXTRACT}}\left(v,\IfEq{}{}{\mathcal{G}}{\mathcal{G}}\right)$ to return
a connected $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$, where
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ is a subgraph containing $v$,
and the depth of $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ is $L$.  2. We
build an $L^{\prime}$-layer GNN on
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ by treating
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ as the _new_ full graph and by
ignoring all nodes / edges not in
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$.  So
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ is the scope of shaDow-GNN. The
key point reflecting “decoupling” is that $L^{\prime}>L$.

A normal GNN is closely related to a shaDow-GNN. Under the normal setup, an
$L$-layer GNN operates on the full $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ and
propagates the influence from all the neighbors up to $L$ hops away from $v$.
Such a GNN is equivalent to a model where EXTRACT returns the full $L$-hop
subgraph and $L^{\prime}=L$.

We theoretical demonstrate how shaDow-GNN improves expressivity from three
different angles. On shaDow-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
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ preserves richer information
than the global $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$. On shaDow-SAGE (Section
3.2), we view the GNN as a _function approximator_. 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 1D Weisfeiler-
Lehman test fails to capture.

###  3.1 Expressivity Analysis on shaDow-GCN: Graph Signal Processing
Perspective

GCNs [22] suffer from “oversmoothing” [30] – 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
$\IfEq{}{}{\mathcal{V}}{\mathcal{V}}$. “Oversmoothing” thus incurs significant
information loss by wiping out all local information.

Formally, suppose the original features
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$ reside in a high-dimensional space
$\mathbb{R}^{\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert\times
d}$. Oversmoothing pushes $\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$ towards
a low-dimensional subspace
$\mathbb{R}^{\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert\times
d^{\prime}}$, where $d^{\prime}<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
$\bm{M}=\lim_{L\rightarrow\infty}\IfEq{}{}{\widetilde{\bm{A}}}{\widetilde{\bm{A}}}^{L}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$.
It is shown that even 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 $\bm{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.

$\infty$ number of feature propagation by shaDow-GCN leads to

$\bm{m}_{[v]}=\left[e_{[v]}\right]_{v}\cdot\left(\bm{e}_{[v]}^{\mathsf{T}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{[v]}\right)$
(1)

where $\bm{e}_{[v]}$ is defined by
$\left[e_{[v]}\right]_{u}=\sqrt{\frac{\delta_{[v]}\left(u\right)}{\sum_{w\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}}\delta_{[v]}\left(w\right)}}$;
$\delta_{[v]}\left(u\right)$ returns the degree of $u$ in
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ plus 1.

Oversmoothing by normal GCN propagation. With a large enough $L$, the full
$L$-hop neighborhood becomes $\IfEq{}{}{\mathcal{V}}{\mathcal{V}}$ (assuming
connected $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$). So $\forall\;u,v$, we have
$\IfEq{[u]}{}{\mathcal{G}}{\mathcal{G}}_{[u]}=\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}=\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$,
implying $\bm{e}_{[u]}=\bm{e}_{[v]}$ and
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{[u]}=\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{[v]}=\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$.
From Proposition 3.1, the aggregation converges to a point where _no_ feature
and _little_ structural information of the target is preserved. The only
information in $\bm{m}_{[v]}$ is $v$’s degree.

Local-smoothing by shaDow-GCN propagation. With a fixed subgraph, no matter
how many times we aggregate using
$\IfEq{}{}{\widetilde{\bm{A}}}{\widetilde{\bm{A}}}_{[v]}$, the layers will not
include the faraway irrelevant nodes. From Proposition 3.1, $\bm{m}_{[v]}$ is
a linear combination of the neighbor features
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{[v]}$. Increasing the number of
layers only pushes the _coefficients_ of each neighbor features to the
stationary values. The _domain_
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{[v]}$ 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
$\bm{m}_{[v]}$, note that $\bm{e}_{[v]}$ is a normalized degree distribution
of the subgraph around $v$, and $\left[e_{[v]}\right]_{v}$ indicates the role
of the target node in the subgraph. By simply letting EXTRACT return the
$1$-hop subgraph, $\left[e_{[v]}\right]_{v}$ alone already contains all the
information preserved by a normal GCN, which is $v$’s degree in
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$. For the general EXTRACT, $\bm{e}_{[v]}$
additionally reflects $v$’s ego-net structure. Thus, a deep shaDow-GCN
preserves more structural information than a deep GCN.

######  Theorem 3.2.

Let
$\overline{\bm{m}}_{[v]}=\phi_{\IfEq{}{}{\mathcal{G}}{\mathcal{G}}}\left(v\right)\cdot\bm{m}_{[v]}$
where $\phi_{\IfEq{}{}{\mathcal{G}}{\mathcal{G}}}$ is any non-zero function
only depending on the structural property of $v$. Let
$\mathcal{M}=\\{\overline{\bm{m}}_{[v]}\;|\;v\in\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\\}$.
Given $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$, EXTRACT and some continuous
probability distribution in
$\mathbb{R}^{\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert\times
d}$ to generate $\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$, then
$\overline{\bm{m}}_{[v]}\neq\overline{\bm{m}}_{[u]}$ if
$\IfEq{[u]}{}{\mathcal{V}}{\mathcal{V}_{[u]}}\neq\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$,
almost surely.

######  Corollary 3.2.1.

Consider ${\text{{EXTRACT}}}_{1}$, where $\forall
v\in\IfEq{}{}{\mathcal{V}}{\mathcal{V}},\;\left\lvert\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}\right\rvert\leq
n$. Then
$\left\lvert\mathcal{M}\right\rvert\geq\left\lceil{\frac{\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert}{n}}\right\rceil$
a.s.

######  Corollary 3.2.2.

Consider ${\text{{EXTRACT}}}_{2}$, where
$\forall\;u,v\in\IfEq{}{}{\mathcal{V}}{\mathcal{V}},\;\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}\neq\IfEq{[u]}{}{\mathcal{V}}{\mathcal{V}_{[u]}}$.
Then
$\left\lvert\mathcal{M}\right\rvert=\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert$
a.s.

Theorem 3.2 proves shaDow-GCN does not oversmooth:  1. A normal GCN pushes the
aggregation of same-degree nodes to the same point, while shaDow-GCN with
${\text{{EXTRACT}}}_{2}$ ensures any two nodes (even with the same degree)
have different aggregation.  2. A normal GCN wipes out all information in
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$ after many times of aggregation,
while shaDow-GCN always preserves feature information.  Particularly, with
$\phi_{\IfEq{}{}{\mathcal{G}}{\mathcal{G}}}\left(v\right)=\left(\delta_{[v]}(v)\right)^{-1/2}$,
a normal GCN generates only one unique value of $\overline{\bm{m}}$ for all
$v$. By contrast, shaDow-GNN generates
$\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert$ different values
for any $\phi_{\IfEq{}{}{\mathcal{G}}{\mathcal{G}}}$ function.

###  3.2 Expressivity Analysis on shaDow-SAGE: Function Approximation
Perspective

We compare the expressivity by showing  1. shaDow-SAGEcan express all
functions GraphSAGE can, and  2. shaDow-SAGEcan express some function
GraphSAGE cannot.  Recall, a GraphSAGE layer performs the following:
$\bm{h}_{v}^{\left(\ell\right)}=\sigma\left(\left(\bm{W}_{1}^{\left(\ell\right)}\right)^{\mathsf{T}}\bm{h}_{v}^{\left(\ell-1\right)}+\left(\bm{W}_{2}^{\left(\ell\right)}\right)^{\mathsf{T}}\left(\frac{1}{\left\lvert\mathcal{N}_{v}\right\rvert}\sum_{u\in\mathcal{N}_{v}}\bm{h}_{u}^{\left(\ell-1\right)}\right)\right)$.
We can prove Point 1 by making an $L^{\prime}$-layer shaDow-SAGE identical to
an $L$-layer GraphSAGE with the following steps:  1. let EXTRACT return the
full $L$-hop neighborhood, and  2. set
$\bm{W}_{1}^{\left(\ell\right)}=\bm{I}$,
$\bm{W}_{2}^{\left(\ell\right)}=\bm{0}$ for $L+1\leq\ell\leq L^{\prime}$.  For
point 2, we consider a target function:
$\tau\left(\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}},\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}\right)=C\cdot\sum_{u\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}}\delta_{[v]}\left(u\right)\cdot\bm{x}_{u}$
for some neighborhood $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$, scaling
constant $C$ and $\delta_{[v]}\left(u\right)$ as defined in Proposition 3.1.
An expressive model should be able to learn well this simple linear function
$\tau$.

GraphSAGE cannot learn $\tau$ accurately, while shaDow-SAGE can. We first show
the GraphSAGE case. Let the depth of
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ be $L$. Firstly, we need
GraphSAGE to perform message passing for exactly $L$ times (where such a model
can be implemented by, _e.g._ , $L$ layers or $L^{\prime}$ layers with
$\bm{W}_{2}=\bm{0}$ for $L^{\prime}-L$ layers). Otherwise, the extra
$L^{\prime}-L$ message passings will propagate influence from nodes
$v^{\prime}\not\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$, violating the
condition that $\tau$ is independent of $v^{\prime}$. Next, suppose GraphSAGE
can learn a function $\zeta$ such that on some
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime}$, we have
$\zeta\left(\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime}\right)=\tau\left(\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime}\right)$.
We construct another
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime\prime}$ by adding an
extra edge $e$ connecting two depth-$L$ nodes in
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime}$. Edge $e$ changes the
degree distribution $\delta_{[v]}\left(\cdot\right)$, and thus
$\tau\left(\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime}\right)\neq\tau\left(\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime\prime}\right)$.
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 $L+1$ message
passings. So
$\zeta\left(\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime}\right)=\zeta\left(\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime\prime}\right)$
regardless of the activation function and weight parameters. Therefore,
$\zeta\neq\tau$.

For shaDow-SAGE, let EXTRACT return
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$. Then the model can output
$\zeta^{\prime}=\left[\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}^{L^{\prime}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}\right]_{v,:}$
after we  1. set $\bm{W}_{1}^{\left(\ell\right)}=\bm{0}$ and
$\bm{W}_{2}^{\left(\ell\right)}=\bm{I}$ for all layers, and  2. either remove
the non-linear activation or bypass ReLU by shifting
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$ with bias.  With known results in
Markov chain convergence theorem [27], we derive the following theorem by
analyzing the convergence of
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}^{L^{\prime}}$ when
$L^{\prime}\rightarrow\infty$.

######  Theorem 3.3.

shaDow-SAGE can approximate $\tau$ with error decaying exponentially with
depth.

We have the following conclusions from above:  1. shaDow-SAGEis more
expressive than GraphSAGE.  2. appropriate EXTRACT function improves shaDow-
GNN expressivity,  3. There exists cases where it may be desirable to set the
shaDow-GNN depth much larger than the subgraph depth.

###  3.3 Expressivity Analysis on shaDow-GIN: Topological Learning Perspective

While GCN and GraphSAGE are popular architectures in practice, they are not
the theoretically most discriminative ones. The work in [49] establishes the
relation in discriminativeness between GNNs and 1-dimensional Weisfeiler-
Lehman test (_i.e._ , 1-WL). And GIN [49] is an example architecture achieving
the same discriminativeness as 1-WL. We show that applying the decoupling
principle can further improve the discriminativeness of such GNNs, making them
more powerful than 1-WL.

$u$$v$$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$$u$$\IfEq{[u]}{}{\mathcal{G}}{\mathcal{G}}_{[u]}^{1}$$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{1}$$v$
Figure 1: Example 3-regular graph and the 1-hop subgraphs of the target nodes
$u$ and $v$.

1-WL is a graph isomorphism test aiming at distinguishing graphs of different
structures. A GNN as expressive as 1-WL 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 shaDow-GNN works, we first need to
understand why 1-WL fails. In a regular graph, all nodes have the same degree,
and thus the “regular” property describes a _global_ topological symmetry
among nodes. Unfortunately, 1-WL (and the corresponding normal GNN) also
operates _globally_ on $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$. Intuitively, on
two different regular graphs, there is no way for 1-WL (and the normal GNN) to
assign different labels by breaking such symmetry.

On the other hand, shaDow-GNN can break such symmetry by applying decoupling.
In Section 1, we have discussed how shaDow-GNN is built from the _local_
perspective on the full graph. The key property benefiting shaDow-GNN is that
_a 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 1. The graph
$\IfEq{}{}{\mathcal{G}}{\mathcal{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
1-WL runs, or how many layers the normal GNN has, they cannot distinguish $u$
and $v$. On the other hand, a shaDow-GNN with 1-hop EXTRACT and at least 2
layers can discriminate $u$ and $v$.

######  Theorem 3.4.

Consider GNNs whose layer function is defined by

$\displaystyle{\bm{h}}_{v}^{(\ell)}=f_{1}^{(\ell)}\left({\bm{h}}_{v}^{(\ell-1)},\;\sum_{u\in\mathcal{N}_{v}}f_{2}^{(\ell)}\left({\bm{h}}_{v}^{(\ell-1)},{\bm{h}}_{u}^{(\ell-1)}\right)\right),$
(2)

where $f_{1}^{(\ell)}$ and $f_{2}^{(\ell)}$ are the update and message
functions of layer-$\ell$, implemented as MLPs. Then, such shaDow-GNN is more
discriminative than the 1-dimensional Weisfeiler-Lehman test.

The theorem also implies that shaDow-GIN is more discriminative than a normal
GIN due to 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
$\IfEq{}{}{\mathcal{G}}{\mathcal{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 metrics;  2. _model based_ , where we assume a generation process on
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ 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, we present several examples on heuristic
based EXTRACT, which we also empirically evaluate in Section 5. We leave
detailed evaluation on the model based and learning based EXTRACT as future
work. See also Appendix C for details.

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
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$. Picking the random walk landing
probability as the metric, we can design a PPR-based extractor. _i.e._ , we
first run the Personalized PageRank (PPR) algorithm on
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ to derive the PPR score of other nodes
relative to the target node. Then EXTRACT define
$\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$ by picking the top-$K$ nodes
with the highest PPR scores. The subgraph
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ is the _node-induced subgraph_
111Unlike other PPR-based models [23, 6] which rewire the graph by treating
top PPR nodes as direct neighbors, our PPR neighborhood preserves the original
multi-hop topology by returning node-induced subgraph.  of
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ from
$\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$. One can easily extend this
approach by using other metrics such as Katz index [20], SimRank [19] and
feature similarity.

###  3.5 Architecture

Subgraph pooling. For a normal GNN performing node classification, the multi-
layer message passing follows a “tree structure”. The nodes at level $L$ of
the tree correspond to the $L$-hop neighborhood. 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 a shaDow-GNN, since we decouple the $L$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 to
READOUT all the subgraph node embeddings as the target node embedding.

We can understand the pooling for shaDow-GNN 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
$2L$-hop away from each other). In our design, a 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 _it establishes
the connection between the node- / link-level task and the graph-level task_.
_e.g._ , to classify a node is seen as to classify 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
shaDow-GNN. 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-GNN at the subgraph level. Consider $R$ candidates
$\left\\{{\text{{EXTRACT}}}_{i}\right\\}$, each returning
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{i}$. To generate $v$’s
embedding, we first use $R$ branches of $L^{\prime}$-layer GNN to obtain
intermediate embeddings for each
$\IfEq{v}{}{\mathcal{G}}{\mathcal{G}}_{v}^{i}$, and then aggregate the $R$
embeddings by some learnable function $g$. In practice, we design $g$ as an
attention based aggregation function (see Appendix D.2). Subgraph ensemble is
useful both when $\left\\{{\text{{EXTRACT}}}_{i}\right\\}$ consists of
different algorithms and when each ${\text{{EXTRACT}}}_{i}$ performs the same
algorithm under different parameters.

Case study Consider PPR-based ${\text{{EXTRACT}}}_{i}$ with different
threshold $\theta_{i}$ on the neighbor PPR score. A shaDow-GNN-ensemble can
approximate PPRGo [6]. PPRGo generates embedding as:
$\bm{\xi}_{v}=\sum_{u\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}}\pi_{u}\bm{h}_{v}$,
where $\pi_{u}$ is $u$’s PPR score and
$\bm{h}_{v}={\text{MLP}\left(\bm{x}_{v}\right)}$. We can partition
$\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}=\bigcup_{i=1}^{R}\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}^{i}$
s.t. nodes in $\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}^{i}$ have similar
PPR scores denoted by $\widetilde{\pi}_{i}$, and
$\widetilde{\pi}_{i}\leq\widetilde{\pi}_{i+1}$. So
$\bm{\xi}_{v}=\sum_{i=1}^{R}\rho_{i}\left(\sum_{u\in\IfEq{i}{}{\mathcal{V}}{\mathcal{V}_{i}}^{\prime}}\bm{h}_{u}\right)$,
where $\rho_{i}=\widetilde{\pi}_{i}-\sum_{j<i}\widetilde{\pi}_{j}$ and
$\IfEq{i}{}{\mathcal{V}}{\mathcal{V}_{i}}^{\prime}=\bigcup_{k=i}^{R}\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}^{k}$.
Now for each branch of shaDow-GNN-ensemble, let parameter
$\theta_{i}=\widetilde{\pi}_{i}$ so that ${\text{{EXTRACT}}}_{i}$ returns
$\IfEq{}{}{\mathcal{V}}{\mathcal{V}}_{i}^{\prime}$. The GNN on
$\IfEq{}{}{\mathcal{V}}{\mathcal{V}}_{i}^{\prime}$ can then learn
$\sum_{u\in\IfEq{}{}{\mathcal{V}}{\mathcal{V}}_{i}^{\prime}}\bm{h}_{u}$
(_e.g._ , by a simple “mean” READOUT). Finally, set the ensemble weight as
$\rho_{i}$. shaDow-GNN-ensemble learns $\bm{\xi}_{v}$. 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 – shaDow-GNN. As
the name suggests, in shaDow-GNN, the scope is a shallow subgraph (_i.e._ ,
with depth often set to $2$ or $3$).

In many realistic scenarios (_e.g._ , citation networks, social networks,
product recommendation graphs), a 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 at most 2 hops away. Formally,
by the $\gamma$-decaying theorem [56], a 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 we have defined a decoupled model as having the
model depth $L^{\prime}$ larger than the subgraph depth $L$. Strictly
speaking, a decoupled model also admits $L^{\prime}=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$-hop neighbors, and the
resulting subgraph $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ contains
only 20% nodes $L$ hops away. Then it is reasonable to consider an $L$-layer
model on such a depth-$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$ $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ propagates much less
information from nodes $L$ hops away. So the $L$ message passings are indeed
decoupled from the full $L$-hop neighborhood.

Remark on neighborhood. The “sufficiency” and “necessity” in shallow
neighborhood are 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 as 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 [1], Snowball [33], DAGNN [31] and GCNII [34] all include
some variants of residue connection, either across multiple layers or within a
single layer. In principle, such architectures can also benefit the feature
propagation of a deep shaDow-GNN, since their design does not rely on a
specific neighborhood (_e.g._ , $L$-hop). In addition to architectures,
DropEdge [39] and Bayesian-GDC [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. FastGCN [8], VR-GCN [7], AS-GCN [18],
LADIES [61] and MVS-GNN [10] 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-GNN, since the decoupling
principle is derived from a local view on
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$, our EXTRACT does not estimate any full
neighborhood quantities. Consequently, the sampling based methods only improve
the training efficiency, while shaDow-GNN addresses the computation challenge
for both training and inference.

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 [11] applies reconstruction for
customized graph operators. AM-GCN [46] 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-GNN can also work with the reconstructed graph
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}^{\prime}$ by simply applying EXTRACT on
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}^{\prime}$.

##  5 Experiments

Setup. We evaluate shaDow-GNN on seven graphs. Six of them are for the node
classification task: Flickr [55], Reddit [12], Yelp [55], ogbn-arxiv, ogbn-
products and ogbn-papers100M [16]. The remaining is for the link prediction
task: ogbl-collab [16]. The sizes of the seven graphs range from 9K nodes
(Flickr) to 110M nodes (ogbn-papers100M). Flickr, Reddit and Yelp are under
the inductive setting. ogbn-arxiv, ogbn-products and ogbn-papers100M are
transductive. Consistent with the original papers, for the graphs on node
classification, we measure “F1-micro” score for Yelp and “accuracy” for the
remaining five graphs. For the link prediction task, we use “Hits@50” as the
metric. See Appendix E.1 for details.

We construct shaDow with six backbone models: GCN [22], GraphSAGE [12], GAT
[44], JK-Net [50], GIN [49], SGC [47]. The first five are representatives of
the state-of-the-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 non-shaDow models
are trained with both full-batch and GraphSAINT-minibatch [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 our 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-
GNN, both training and inference are always executed in minibatches. One
advantage of shaDow-GNN is that the decoupling enables straightforward
minibatch construction: each target just independently extracts the small
subgraph on its own.

We implement two EXTRACT described in Section 3.4:  1. “PPR”, where we set the
node budget $K$ as $\\{200,400\\}$ for the largest ogbn-papers100M and $K\leq
200$ for all other graphs;  2. “$L$-hop”, where we set the depth as
$\\{1,2\\}$.  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^{\prime}=3$ is the standard setting in the literature
(_e.g._ , see the benchmarking in OGB [16]), we start from $L^{\prime}=3$ and
further evaluate a deeper model of $L^{\prime}=5$. All accuracy are measured
by 5 runs without fixing random seeds. Hyperparameter tuning and architecture
configurations are in Appendix E.4.

FlickrRedditYelparxivproducts$0$$0.2$$0.4$$0.6$$0.8$$1$Ratio of nodes at
different hop $\ell$4-layer GNNFlickrRedditYelparxivproductsAny layer shaDow
(PPR)$\ell=1$$\ell=2$$\ell=3$$\ell=4$
Figure 2: Neighborhood composition
$0$$5$$10$$15$$20$$25$$30$$35$$40$$45$$0.4$$0.5$$0.6$$0.7$$0.8$$0.9$$1$RedditArxivFlickrPower
on $\widetilde{\bm{A}}$ or $\widetilde{\bm{A}}_{[v]}$Test accuracys-SGC, F
s-SGC, R s-SGC, A SGC, F SGC, R SGC, A
Figure 3: SGC oversmoothing

shaDow-GNN neighborhood. For both normal and shaDow GNNs, Figure 2 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 shaDow-GNN using the Table 1
EXTRACT, most neighbors concentrate within 2 hops. A small number of nodes are
3 hops away. Almost no nodes are 4 or more hops away. Importantly, not only
does the composition of the two kinds of neighborhood differ significantly,
but also the size of shaDow-GNN scope is much smaller (see also Table 1). Such
small subgraphs are essential to high computation efficiency. Finally, we can
ignore the very few distant neighbors ($L\geq 4$), and regard the (effective)
depth of shaDow-GNN subgraph as $L=2$ (or at most $3$). Under such practical
value of $L$, a model with $L^{\prime}\geq 3$ is indeed a shaDow-GNN (see
“Remark on decoupling” in Section 3.6).

Table 1: Comparison on test accuracy / F1-micro score and inference cost
(tuned with DropEdge)

Method | Layers | Flickr | Reddit | Yelp | ogbn-arxiv | ogbn-products
---|---|---|---|---|---|---
Accuracy | Cost | Accuracy | Cost | F1-micro | Cost | Accuracy | Cost | Accuracy | Cost
GCN | 3 | 0.5159$\pm$0.0017 | 2E0 | 0.9532$\pm$0.0003 | 6E1 | 0.4028$\pm$0.0019 | 2E1 | 0.7170$\pm$0.0026 | 1E1 | 0.7567$\pm$0.0018 | 5E0
5 | 0.5217$\pm$0.0016 | 2E2 | 0.9495$\pm$0.0012 | 1E3 | OOM | 1E3 | 0.7186$\pm$0.0017 | 1E3 | OOM | 9E2
GCN-SAINT | 3 | 0.5155$\pm$0.0027 | 2E0 | 0.9523$\pm$0.0003 | 6E1 | 0.5110$\pm$0.0012 | 2E1 | 0.7093$\pm$0.0003 | 1E1 |  0.8003$\pm$0.0024 | 5E0
5 | 0.5165$\pm$0.0026 | 2E2 | 0.9523$\pm$0.0012 | 1E3 | 0.5012$\pm$0.0021 | 1E3 | 0.7039$\pm$0.0020 | 1E3 | 0.7992$\pm$0.0021 | 9E2
| 3 | 0.5234$\pm$0.0009 | (1) | 0.9576$\pm$0.0005 | (1) | 0.5291$\pm$0.0020 | (1) | 0.7180$\pm$0.0024 | (1) | 0.7742$\pm$0.0037 | (1)
shaDow-GCN (PPR) | 5 | 0.5268$\pm$0.0008 | 1E0 | 0.9564$\pm$0.0004 | 1E0 | 0.5323$\pm$0.0020 | 2E0 | 0.7206$\pm$0.0025 | 2E0 | 0.7821$\pm$0.0043 | 2E0
+Pooling | 3/5 |  0.5286$\pm$0.0013 | 1E0 |  0.9624$\pm$0.0002 | 1E0 |  0.5393$\pm$0.0036 | 2E0 |  0.7223$\pm$0.0018 | 2E0 | 0.7914$\pm$0.0044 | 2E0
GraphSAGE | 3 | 0.5140$\pm$0.0014 | 3E0 | 0.9653$\pm$0.0002 | 5E1 | 0.6178$\pm$0.0033 | 2E1 | 0.7192$\pm$0.0027 | 1E1 | 0.7858$\pm$0.0013 | 4E0
5 | 0.5154$\pm$0.0052 | 2E2 | 0.9626$\pm$0.0004 | 1E3 | OOM | 2E3 | 0.7193$\pm$0.0037 | 1E3 | OOM | 1E3
SAGE-SAINT | 3 | 0.5176$\pm$0.0032 | 3E0 | 0.9671$\pm$0.0003 | 5E1 | 0.6453$\pm$0.0011 | 2E1 | 0.7107$\pm$0.0003 | 1E1 | 0.7923$\pm$0.0023 | 4E0
5 | 0.5201$\pm$0.0032 | 2E2 | 0.9670$\pm$0.0010 | 1E3 | 0.6394$\pm$0.0003 | 2E3 | 0.7013$\pm$0.0021 | 1E3 | 0.7964$\pm$0.0022 | 1E3
| 3 | 0.5312$\pm$0.0019 | 1E0 | 0.9672$\pm$0.0003 | 1E0 | 0.6542$\pm$0.0002 | 1E0 | 0.7163$\pm$0.0028 | 1E0 | 0.7935$\pm$0.0031 | 1E0
shaDow-SAGE ($2$-hop) | 5 | 0.5335$\pm$0.0015 | 2E0 | 0.9675$\pm$0.0005 | 2E0 | 0.6525$\pm$0.0003 | 2E0 | 0.7180$\pm$0.0030 | 2E0 | 0.7995$\pm$0.0022 | 2E0
| 3 | 0.5356$\pm$0.0013 | (1) | 0.9688$\pm$0.0002 | (1) | 0.6538$\pm$0.0003 | (1) | 0.7227$\pm$0.0012 | (1) | 0.7905$\pm$0.0026 | (1)
shaDow-SAGE (PPR) | 5 |  0.5417$\pm$0.0006 | 2E0 | 0.9692$\pm$0.0007 | 2E0 | 0.6518$\pm$0.0002 | 2E0 | 0.7238$\pm$0.0007 | 2E0 | 0.8005$\pm$0.0040 | 2E0
+Pooling | 3/5 | 0.5395$\pm$0.0013 | 2E0 |  0.9703$\pm$0.0003 | 2E0 |  0.6564$\pm$0.0004 | 1E0 |  0.7258$\pm$0.0017 | 2E0 |  0.8067$\pm$0.0037 | 1E0
GAT | 3 | 0.5070$\pm$0.0032 | 2E1 | OOM | 3E2 | OOM | 2E2 | 0.7201$\pm$0.0011 | 1E2 | OOM | 3E1
5 | 0.5164$\pm$0.0033 | 2E2 | OOM | 2E3 | OOM | 2E3 | OOM | 3E3 | OOM | 2E3
GAT-SAINT | 3 | 0.5225$\pm$0.0053 | 2E1 | 0.9671$\pm$0.0003 | 3E2 | 0.6459$\pm$0.0002 | 2E2 | 0.6977$\pm$0.0003 | 1E2 | 0.8027$\pm$0.0028 | 3E1
5 | 0.5153$\pm$0.0034 | 2E2 | 0.9651$\pm$0.0024 | 2E3 | 0.6478$\pm$0.0012 | 2E3 | 0.6954$\pm$0.0013 | 3E3 | 0.7990$\pm$0.0072 | 2E3
| 3 | 0.5349$\pm$0.0023 | (1) | 0.9707$\pm$0.0004 | (1) |  0.6575$\pm$0.0004 | (1) | 0.7235$\pm$0.0020 | (1) | 0.8006$\pm$0.0014 | (1)
shaDow-GAT (PPR) | 5 | 0.5352$\pm$0.0028 | 2E0 |  0.9713$\pm$0.0004 | 2E0 | 0.6559$\pm$0.0002 | 2E0 |  0.7274$\pm$0.0022 | 2E0 | 0.8071$\pm$0.0004 | 2E0
+Pooling | 3/5 |  0.5364$\pm$0.0026 | 1E0 | 0.9710$\pm$0.0004 | 2E0 | 0.6566$\pm$0.0005 | 1E0 | 0.7265$\pm$0.0028 | 2E0 |  0.8142$\pm$0.0031 | 1E0

Comparison with baselines. Table 1 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 a 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 shaDow-GNN, we do
not include the overhead on computing EXTRACT, since it is hard to calculate
such cost analytically. Empirically, subgraph extraction is 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 baseline and shaDow models.
DropEdge helps improve the baseline accuracy by alleviating oversmoothing, and
benefits shaDow-GNN due to its regularization effects. See Appendix F.2 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 a decoupled model?  To answer Q1, we fix the
backbone architecture and remove pooling. Then we inspect “3-layer normal GNN
_vs._ 3-layer shaDow-GNN” and “5-layer normal GNN _vs._ 5-layer shaDow-GNN”.
Clearly, shaDow-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, a
depth-3 $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ differs significantly
from the 3-hop neighborhood). To answer Q1, 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 a shaDow-GNN. In conclusion, both types of
architecture tuning are effective ways of optimizing a shaDow-GNN. Finally, to
answer Q3, we compare the 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 a good EXTRACT.

Inference cost Inference cost of shaDow-GNN is orders of magnitude lower than
the normal GNNs (a 5-layer shaDow-GNN is still much cheaper than a 3-layer
normal GNN). The high cost of the baselines is due to the “neighborhood
explosion” with respect to more layers. shaDow-GNN is efficient and scalable
as the cost only grows linearly with the model depth. Note that GraphSAINT
only improves efficiency _during training_ since its inference operates on the
full $L$-hop neighborhood.

Table 2: Leaderboard comparison on papers100M

Method | Test accuracy | Val accuracy | Neigh size
---|---|---|---
GraphSAGE+incep | 0.6706$\pm$0.0017 | 0.7032$\pm$0.0011 | 4E5
SIGN-XL | 0.6606$\pm$0.0019 | 0.6984$\pm$0.0006 |  $>$ 4E5
SGC | 0.6329$\pm$0.0019 | 0.6648$\pm$0.0020 |  $>$ 4E5
shaDow-GAT200 | 0.6681$\pm$0.0016 | 0.7019$\pm$0.0011 | 2E2
shaDow-GAT400 |  0.6708$\pm$0.0017 |  0.7073$\pm$0.0011 | 3E2

Scaling to 100 million nodes. We further scale shaDow-GNN to ogbn-papers100M,
one of the largest public dataset. Even through the full graph size is at
least two orders of magnitude larger than the graphs in Table 1, the localized
scope of shaDow-GNN barely needs to increase. Since shaDow-GNN performs
minibatch computation, a low-end GPU with limited memory capacity can compute
shaDow-GNN on ogbn-papers100M efficiently. We show in Appendix F.1 that we can
train and inference our model with as little as 4GB GPU memory consumption.
This is infeasible using normal GNNs. Table 2 summarizes our comparison with
the top leaderboard methods [45, 11, 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 $5\times$
more CPU memory than shaDow-GNN (Appendix F.1).

Table 3: Leaderboard comparison on collab

Method | Test Hits@50 | Val Hits@50
---|---|---
SEAL | 0.5371$\pm$0.0047 | 0.6389$\pm$0.0049
DeeperGCN | 0.5273$\pm$0.0047 | 0.6187$\pm$0.0045
LRGA+GCN | 0.5221$\pm$0.0072 | 0.6088$\pm$0.0059
shaDow-SAGE |  0.5492$\pm$0.0022 |  0.6524$\pm$0.0017

Extending to link-level task. We further show that shaDow-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 is 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-1_ model with significant margin.

Oversmoothing. To validate Theorem 3.2, we pick SGC as 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.5 for details). While
SGC gradually collapses local information into global “white noise”, accuracy
of shaDow-SGC does not degrade. This validates our theory that extracting
local subgraphs prevents oversmoothing.

##  6 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 expressivity 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.

## 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 arXiv:1905.00067, 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. PMLR, 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 Hsieh.  Cluster-gcn: An efficient algorithm for training deep and large graph convolutional networks.  In Proceedings of the 25th ACM SIGKDD International Conference on 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 on 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 arXiv:1709.05584, 2017.
  * [14] Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna 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, 2(5):359–366, 1989.
  * [16] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec.  Open graph benchmark: Datasets for machine learning on graphs, 2020.
  * [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: a measure of structural-context similarity.  In Proceedings 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 arXiv: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ßenberger, 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–3743. PMLR, 2019.
  * [25] Jure Leskovec and Christos Faloutsos.  Sampling from large graphs.  In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’06, page 631–636, 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 gcns, 2020.
  * [30] Qimai Li, Zhichao Han, and Xiao-Ming Wu.  Deeper insights into Graph Convolutional Networks for semi-supervised learning.  arXiv preprint arXiv:1801.07606, 2018.
  * [31] Meng Liu, Hongyang Gao, and Shuiwang Ji.  Towards deeper graph neural networks.  Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, Aug 2020.
  * [32] Yu-Chen Lo, Stefano E Rensi, Wen Torng, and Russ B Altman.  Machine learning in chemoinformatics and drug discovery.  Drug discovery today, 23(8):1538–1546, 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 in 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 on Learning Representations, 2020.
  * [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 on 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.  Weisfeiler-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 Bloom-Ackerman, et al.  A deep learning approach to antibiotic discovery.  Cell, 180(4):688–702, 2020.
  * [44] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio.  Graph Attention Networks.  In International Conference on 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: A 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 Wu, Tianyi Zhang, Amauri Holanda de Souza Jr, Christopher Fifty, Tao Yu, and Kilian Q Weinberger.  Simplifying graph convolutional networks.  arXiv preprint arXiv:1902.07153, 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:1810.00826, 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.
  * [53] Jiaxuan You, Zhitao Ying, and Jure Leskovec.  Design space for graph neural networks.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. 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.  In International Conference on Learning Representations, 2020.
  * [56] Muhan Zhang and Yixin Chen.  Link prediction based on 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.  In International Conference on 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. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.

##  Appendix A Proofs

###  A.1 Proof on shaDow-GCN Expressivity

###### Proof of Proposition 3.1.

The GCN model performs symmetric normalization on the adjacency matrix.
shaDow-GCN follows the same way to normalize the subgraph adjacency matrix as:

$\displaystyle\IfEq{}{}{\widetilde{\bm{A}}}{\widetilde{\bm{A}}}_{[v]}=\left(\bm{D}_{[v]}+\bm{I}_{[v]}\right)^{-\frac{1}{2}}\cdot\left(\bm{A}_{[v]}+\bm{I}_{[v]}\right)\cdot\left(\bm{D}_{[v]}+\bm{I}_{[v]}\right)^{-\frac{1}{2}}$
(3)

where $\bm{A}_{[v]}\in\mathbb{R}^{N\times N}$ is the binary adjacency matrix
for $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$.

$\IfEq{}{}{\widetilde{\bm{A}}}{\widetilde{\bm{A}}}_{[v]}$ is a real symmetric
matrix and has the largest eigenvalue of $1$. Since EXTRACT ensures the
subgraph $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ is connected, so the
multiplicity of the largest eigenvalue is 1. By Theorem 1 of [17], we can
bound the eigenvalues $\lambda_{i}$ by
$1=\lambda_{1}>\lambda_{2}\geq\ldots\geq\lambda_{N}>-1$.

Performing eigen-decomposition on
$\IfEq{}{}{\widetilde{\bm{A}}}{\widetilde{\bm{A}}}_{[v]}$, we have

$\displaystyle\IfEq{}{}{\widetilde{\bm{A}}}{\widetilde{\bm{A}}}_{[v]}=\bm{E}_{[v]}\bm{\Lambda}\bm{E}_{[v]}^{-1}=\bm{E}_{[v]}\bm{\Lambda}\bm{E}_{[v]}^{\mathsf{T}}$
(4)

where $\bm{\Lambda}$ is a diagonal matrix $\Lambda_{i,i}=\lambda_{i}$ and
matrix $\bm{E}_{[v]}$ consists of all the normalized eigenvectors.

We have:

$\displaystyle\IfEq{}{}{\widetilde{\bm{A}}}{\widetilde{\bm{A}}}_{[v]}^{L}=\bm{E}_{[v]}\bm{\Lambda}^{L}\bm{E}_{[v]}^{\mathsf{T}}$
(5)

Since $\left\lvert\lambda_{i}\right\rvert<1$ when $i\neq 1$, we have
$\lim_{L\rightarrow\infty}\IfEq{}{}{\widetilde{\bm{A}}}{\widetilde{\bm{A}}}_{[v]}^{L}=\bm{e}_{[v]}\bm{e}_{[v]}^{\mathsf{T}}$,
where $\bm{e}_{v}$ is the eigenvector corresponding to $\lambda_{1}$. It is
easy to see that $\left[\bm{e}_{[v]}\right]_{u}\propto\sqrt{\delta_{[v]}(u)}$
[17]. After normalization,
$\left[\bm{e}_{[v]}\right]_{u}=\sqrt{\frac{\delta_{[v]}(u)}{\sum_{w\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}}\delta_{[v]}(w)}}$.

It directly follows that
$\bm{m}_{[v]}=\left[e_{[v]}\right]_{v}\cdot\left(\bm{e}_{[v]}^{\mathsf{T}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{[v]}\right)$,
with value of $\bm{e}_{[v]}$ defined above. ∎

###### Proof of Theorem 3.2.

We first prove the case of $\overline{\bm{m}}_{[v]}=\bm{m}_{[v]}$. _i.e._ ,
$\phi_{\IfEq{}{}{\mathcal{G}}{\mathcal{G}}}(v)=1$.

According to Proposition 3.1, the aggregation for each target node equals
$\bm{m}_{[v]}=\left[e_{[v]}\right]_{v}\bm{e}_{[v]}^{\mathsf{T}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{[v]}$.
Let $N=\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert$. Let
$\bar{\bar{\bm{e}}}_{[v]}\in\mathbb{R}^{N\times 1}$ be a “padded” vector from
$\bm{e}_{[v]}$, such that the $u^{\text{th}}$ element is
$\left[e_{[v]}\right]_{u}$ if
$u\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$, and 0, otherwise.
Therefore,
$\bm{m}_{[v]}=\left[e_{[v]}\right]_{v}\bar{\bar{\bm{e}}}_{[v]}^{\mathsf{T}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$.
Then, the difference in aggregation of two nodes $u$ and $v$ is given by

$\displaystyle\bm{m}_{[v]}-\bm{m}_{[u]}$
$\displaystyle=\left[e_{[v]}\right]_{v}\bar{\bar{\bm{e}}}_{[v]}^{\mathsf{T}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}-\left[e_{[u]}\right]_{u}\bar{\bar{\bm{e}}}_{[u]}^{\mathsf{T}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$
(6)
$\displaystyle=\bm{\epsilon}^{\mathsf{T}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}},$
(7)

where
$\bm{\epsilon}=\left[e_{[v]}\right]_{v}\cdot\bar{\bar{\bm{e}}}_{[v]}^{\mathsf{T}}-\left[e_{[u]}\right]_{u}\cdot\bar{\bar{\bm{e}}}_{[u]}^{\mathsf{T}}$.

When two nodes $u$ and $v$ have identical neighborhood as
$\IfEq{[u]}{}{\mathcal{V}}{\mathcal{V}_{[u]}}=\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$,
then the aggregation vectors are identical as $\bm{\epsilon}=\bm{0}$. However,
when two nodes have different neighborhoods, we claim that they almost surely
have different aggregations. Let us assume the contrary, _i.e._ , for some $v$
and $u$ with
$\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}\neq\IfEq{[u]}{}{\mathcal{V}}{\mathcal{V}_{[u]}}$,
their aggregations are the same: $\bm{m}_{[v]}=\bm{m}_{[u]}$. Then we must
have
$\bm{\epsilon}^{\mathsf{T}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}=\bm{0}$.

Note that, given $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$, EXTRACT and some
continuous distribution to generate
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$, there are only _finite_ values
for $\bm{\epsilon}$. The reasons are that  1.
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$is finite due to which there are only
finite possible subgraphs and,  2. even though
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$ can take infinitely many values,
$\bm{\epsilon}$ does not depend on
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$.  Each of such
$\bm{\epsilon}\neq\bm{0}$ defines a hyperplane in $\mathbb{R}^{N}$ by
$\bm{\epsilon}\cdot\bm{x}=\bm{0}$ (where $\bm{x}\in\mathbb{R}^{N}$). Let
$\mathcal{H}$ be the finite set of all such hyperplanes.

In other words, $\forall i,\;\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{:,i}$
must fall on one of the hyperplanes in $\mathcal{H}$. However, since
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$ is generated from a continuous
distribution in $\mathbb{R}^{N\times f}$,
$\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{:,i}$ almost surely does not fall
on any of the hyperplanes in $\mathcal{H}$. Therefore, for any $v$ and $u$
such that
$\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}\neq\IfEq{[u]}{}{\mathcal{V}}{\mathcal{V}_{[u]}}$,
we have $\bm{m}_{[v]}\neq\bm{m}_{[u]}$ almost surely.

For a more general $\phi_{\IfEq{}{}{\mathcal{G}}{\mathcal{G}}}(v)$ applied on
$\bm{m}_{[v]}$, since $\phi_{\IfEq{}{}{\mathcal{G}}{\mathcal{G}}}$ does not
depend on $\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$, the proof follows
exactly the same steps as above.

∎

###### Proof of Corollary 3.2.1.

Note that any subgraph contains the target node itself. _i.e._ , $\forall
u\in\IfEq{}{}{\mathcal{V}}{\mathcal{V}},\;u\in\IfEq{[u]}{}{\mathcal{V}}{\mathcal{V}_{[u]}}$.
Therefore, for any node $v$, there are at most $n-1$ other nodes in
$\IfEq{}{}{\mathcal{V}}{\mathcal{V}}$ with the same neighborhood as
$\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$. Such $n-1$ possible nodes are
exactly those in $\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$.

By Theorem 3.2, $\forall v\in\IfEq{}{}{\mathcal{V}}{\mathcal{V}}$, there are
at most $n-1$ other nodes in $\IfEq{}{}{\mathcal{V}}{\mathcal{V}}$ having the
same aggregation as $\bm{m}_{[v]}$. Equivalently, total number of possible
aggregations is at least
$\lceil\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert/n\rceil$. ∎

###### Proof of Corollary 3.2.2.

By definition of ${\text{{EXTRACT}}}_{2}$, any pair of nodes has non-identical
neighborhood. By Theorem 3.2, any pair of nodes have non-identical
aggregation. Equivalently, all nodes have different aggregation and
$\left\lvert\mathcal{M}\right\rvert=\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert$.
∎

###  A.2 Proof on shaDow-SAGE Expressivity

In Section 3.2, we have already shown why the normal GraphSAGE model cannot
learn the $\tau$ function. Here we illustrate the idea with an example in
Figure 4. The neighborhood
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime}$ (or,
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime\prime}$) is denoted by
the solid lines as the edge set
$\IfEq{[v]}{}{\mathcal{E}}{\mathcal{E}_{[v]}}^{\prime}$ (or,
$\IfEq{[v]}{}{\mathcal{E}}{\mathcal{E}_{[v]}}^{\prime\prime}$) and solid nodes
as the node set $\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}^{\prime}$ (or,
$\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}^{\prime\prime}$). The red dashed
edge and the red node $v^{\prime}$ is in the full graph
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ but outside
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime}$ or
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime\prime}$. Due to such
$v^{\prime}$, candidate GraphSAGE models approximating $\tau$ cannot have
message passing for more than 2 times. Further,
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime\prime}$ differs from
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime}$ by the green edge $e$
connecting two 2-hop neighbors of the target $v$. The influence of $e$ cannot
be propagated to target $v$ by only two message passings. Thus, as discussed
in Section 3.2, there is no way for GraphSAGE to learn the $\tau$ function.

$v$$v^{\prime}$$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime}$$v$$e$$v^{\prime}$$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime\prime}$
Figure 4: Example $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime}$ and
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{\prime\prime}$ as described in
Section 3.2

###### Proof of Theorem 3.3.

shaDow-SAGE follows the GraphSAGE way of normalization on the adjacency
matrix. Thus, each row of
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$ sums up to 1. Such
normalization enables us to view
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$ as the transition matrix
of a Markov chain. The coefficients of the linear function $\tau$ (_i.e._ ,
$\delta_{[v]}\left(\cdot\right)$) equal the limiting distribution of such a
Markov chain. Therefore, we can use the convergence theorem of Markov chain to
characterize the convergence of
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}^{L^{\prime}}$ towards
$\tau$’s coefficients. We can also use the mixing time of the Markov chain to
derive the error bound of shaDow-SAGE. Our proof is built on the existing
theoretical results in [27].

We rewrite $\tau$ as $\tau=C\cdot\bm{\delta}\bm{X}$, where $\bm{\delta}$ is a
length-$\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert$ vector
with $\left\lvert\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}\right\rvert$
non-zero elements – each non-zero corresponds to $\delta_{[v]}\left(u\right)$
of the neighborhood $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$. Further,
denote $\widehat{\bm{\delta}}$ as the normalized $\bm{\delta}$ vector. _i.e._
, each non-zero element of $\widehat{\bm{\delta}}$ equals
$\frac{\delta_{[v]}\left(u\right)}{\sum_{w\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}}\delta_{[v]}\left(w\right)}$.
So
$\tau=C^{\prime}\cdot\widehat{\bm{\delta}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$
with some scaling factor $C^{\prime}$. For ease of discussion, we ignore
$C^{\prime}$, as any scaling factor can be easily expressed by the model
weight parameters.

By Section 3.2, shaDow-SAGE can express
$\left[\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}^{L^{\prime}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}\right]_{v,:}=\left[\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}^{L^{\prime}}\right]_{v,:}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}$.
So now we need to show how
$\left[\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}^{L^{\prime}}\right]_{v,:}$
converges to $\widehat{\bm{\delta}}$ when $L^{\prime}\rightarrow\infty$. We
establish the following correspondence:

$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$ as the Markov transition
matrix. This can be easily seen since each row of
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$ sums up to 1. Further,
if we add self-loop in $\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$ and we
consider $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ as undirected and
connected (as can be guaranteed by EXTRACT), then
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$ is _irreducible_ ,
_aperiodic_ and _reversible_. Irreducibility is guaranteed by
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$ being connected. Aperiodicity
is guaranteed by self-loops. For reversibility, we can prove it by the
stationary distribution of
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$. As shown by the next
paragraph, $\widehat{\bm{\delta}}$ is the stationary distribution of
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$. So we need to show that

$\left[\widehat{\bm{\delta}}\right]_{u}\left[\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}\right]_{u,w}=\left[\widehat{\bm{\delta}}\right]_{w}\left[\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}\right]_{w,u}$
(8)

Consider two cases. If
$\left(u,w\right)\not\in\IfEq{[v]}{}{\mathcal{E}}{\mathcal{E}_{[v]}}$, then
$(w,u)\not\in\IfEq{[v]}{}{\mathcal{E}}{\mathcal{E}_{[v]}}$ and both sides of
Equation 8 equal 0. If
$\left(u,w\right)\in\IfEq{[v]}{}{\mathcal{E}}{\mathcal{E}_{[v]}}$, then
$\left[\widehat{\bm{\delta}}\right]_{u}=\frac{\delta_{[v]}\left(u\right)}{\sum_{x\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}}\delta_{[v]}\left(x\right)}$
and
$\left[\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}\right]_{u,w}=\frac{1}{\delta_{[v]}\left(u\right)}$.
So both sides of Equation 8 equal
$\frac{1}{\sum_{x\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}}\delta_{[v]}\left(x\right)}$.
Thus, Equation 8 holds and
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$ is reversible.

$\widehat{\bm{\delta}}$ as the limiting distribution. By definition, the
stationary distribution $\bm{\pi}$ satisfies

$\bm{\pi}=\bm{\pi}\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$ (9)

It is easy to see that setting $\bm{\pi}=\widehat{\bm{\delta}}^{\mathsf{T}}$
can satisfy Equation 9. So $\widehat{\bm{\delta}}$ is the stationary
distribution. For irreducible and aperiodic Markov chain, the stationary
distribution is also the _limiting distribution_ , and thus

$\lim_{L^{\prime}\rightarrow\infty}\left[\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}^{L^{\prime}}\right]_{v,:}=\widehat{\bm{\delta}}$
(10)

So far, we can already show that when the shaDow-SAGE model is deep enough
(_i.e._ , with large $L^{\prime}$), the model output approximates $\tau$:

$\lim_{L^{\prime}\rightarrow\infty}\left[\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}^{L^{\prime}}\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}\right]_{v,:}=\tau$
(11)

Desired model depth as the mixing time. Next, we want to see if we want the
shaDow-SAGE model to reach a given error bound, how many layers $L^{\prime}$
are required. Firstly, directly applying Theorem 4.9 of [27], we know that the
error of shaDow-SAGE approximating $\tau$ reduces _exponentially_ with the
model depth $L^{\prime}$. Then From Equation 4.36 of [27], we can directly
relate the mixing time of Markov chain with the required shaDow-SAGE depth to
reach any $\epsilon$ error. Finally, by Theorem 12.3 of [27], the mixing time
can be bounded by the “absolute spectral gap” of the transition matrix
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$. Note that Theorem 12.3
applies when the Markov chain is reversible – a condition satisfied by
$\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$ as we have already
discussed. The absolute spectral gap is calculated from the eigenvalues of the
transition matrix $\IfEq{}{}{\widehat{\bm{A}}}{\widehat{\bm{A}}}_{[v]}$.

In summary, shaDow-SAGE can approximate $\tau$ with error decaying
exponentially with depth $L^{\prime}$. ∎

###  A.3 Proof on shaDow-GIN Expressivity

###### Proof of Theorem 3.4.

We consider GNNs whose layer function is defined by Equation 2. Define
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{L}$ as the subgraph _induced_
from all of $v$’s $\ell$-hop neighbors in
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$, where $1\leq\ell\leq L$.

First, we show that a shaDow-GNN following Equation 2 is at least as
discriminative as the 1-dimensional Weisfeiler-Lehman test (1-WL). We first
prove that given any $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{L}$, an
$L^{\prime}$-layer GNN can have exactly the same output as an $L$-layer GNN,
where $L^{\prime}>L$. We note that for the target node $v$, the only
difference between these two architectures is that an $L$-layer GNN exactly
performs $L$ message passing iterations to propagate node information from at
most $L$ hops away, while an $L^{\prime}$-layer GNN has $L^{\prime}-L$ more
message passing iterations before performing the rest of $L$ message passings.
Thanks to the universal approximation theorem [15], we can let the MLPs
implementing $f_{1}$ and $f_{2}$ learn the following GNN layer function:

$\displaystyle{\bm{h}}_{v}^{(\ell)}=$ $\displaystyle
f_{1}^{(\ell)}\left({\bm{h}}_{v}^{(\ell-1)},\sum_{u\in\mathcal{N}_{v}}f_{2}^{(\ell)}\left({\bm{h}}_{v}^{(\ell-1)},{\bm{h}}_{u}^{(\ell-1)}\right)\right)$
$\displaystyle=$ $\displaystyle{\bm{h}}_{v}^{(\ell-1)},\qquad\qquad\forall
1\leq\ell\leq L^{\prime}-L$

This means ${\bm{h}}_{v}^{(0)}={\bm{h}}_{v}^{(L^{\prime}-L)}$. Then the
$L^{\prime}$-layer GNN will have the same output as the $L$-layer GNN.
According to [49], the normal GNN (_i.e._ , $L$-layer on
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{L}$) following Equation 2 is as
discriminative as 1-WL. Thus, shaDow-GNN (_i.e._ , $L^{\prime}$-layer on
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{L}$) following Equation 2 is at
least as discriminative as 1-WL.

$u$$v$$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$$u$$\IfEq{[u]}{}{\mathcal{G}}{\mathcal{G}}_{[u]}^{1}$$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{1}$$v$
Figure 5: Example 3-regular graph and the 1-hop subgraph of the target nodes
$u$$v$CC2CC1 Figure 6: Example 2-regular graph with two connected components
(CC)

Next, we show that there exists a graph where shaDow-GNN can discriminate
topologically different nodes, while 1-WL cannot. The example graph mentioned
in Section 3.3 is one such graph. We duplicate the graph here in Figure 5.
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ is connected and is 3-regular. The nodes
$u$ and $v$ marked in red and blue have different topological roles, and thus
an ideal model / algorithm should assign different labels to them. Suppose all
nodes in $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ have identical features. For
1-WL, it will assign the same label to all nodes (including $u$ and $v$) no
matter how many iterations it runs. For shaDow-GNN, if we let EXTRACT return
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{1}$ and
$\IfEq{[u]}{}{\mathcal{G}}{\mathcal{G}}_{[u]}^{1}$ (_i.e._ , $1$-hop based
EXTRACT), and set $L^{\prime}>1$, then our model can assign different labels
to $u$ and $v$. To see why, note that
$\IfEq{[u]}{}{\mathcal{G}}{\mathcal{G}}_{[u]}^{1}$ and
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{1}$ are non-isomorphic, and
more importantly, _non-regular_. So if we run the “shaDow” version of 1-WL
(_i.e._ , 1-WL on $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{1}$ and
$\IfEq{[u]}{}{\mathcal{G}}{\mathcal{G}}_{[u]}^{1}$ rather than on
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$), the nodes $u$ and $v$ will be assigned
to different labels after two iterations. Equivalently, shaDow-GNN can
discriminate $u$ and $v$ with at least 2 layers.

We can further generalize to construct more such example graphs (although such
generalization is not required by the proof). The guideline we follow is that,
the full graph $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ should be regular. Yet
the subgraphs around topologically different nodes (_e.g._ ,
$\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}^{k}$) should be non-isomorphic
and non-regular.

The graph in Figure 6 is another example 2-regular graph, where nodes $u$ and
$v$ can only be differentiated by decoupling the GIN.

Finally, combining the above two parts, shaDow-GNN following Equation 2 is
more discriminative than the 1-dimensional Weisfeiler-Lehman test.

∎

##  Appendix B Inference Complexity Calculation

Here we describe the equations to compute the “inference cost” of Table 1.
Recall that inference cost is a measure of computation complexity to generate
node embeddings for a given GNN architecture.

The numbers in Table 1 shows on average, how many arithmetic operations is
required to generate the embedding for each node. For a GNN layer $\ell$,
denote the number of input nodes as $n^{(\ell-1)}$ and the number of output
nodes as $n^{(\ell)}$. Denote the number of edges connecting the input and
output nodes as $m^{(\ell)}$. Recall that we use $d^{(\ell)}$ to denote the
number of channels, or, the hidden dimension.

In the following, we ignore the computation cost of non-linear activation,
batch-normalization and applying bias, since their complexity is negligible
compared with the other operations.

For the _GCN_ architecture, each layer mainly performs two operations:
aggregation of the neighbor features and linear transformation by the layer
weights. So the number of multiplication-addition (MAC) operations of a
layer-$\ell$ equals:

$\displaystyle
P_{\text{GCN}}^{(\ell)}=m^{(\ell)}d^{(\ell-1)}+n^{(\ell)}d^{(\ell-1)}d^{(\ell)}$
(12)

Similarly, for the _GraphSAGE_ architecture, the number of MAC operations
equals:

$\displaystyle P_{\text{SAGE}}^{(\ell)}=m^{(\ell)}d^{(\ell-1)}+2\cdot
n^{(\ell)}d^{(\ell-1)}d^{(\ell)}$ (13)

where the $2$ factor is due to the weight transformation on the self-features.

For _GAT_ , suppose the number of attention heads is $t$. Then the layer
contains $t$ weight matrices $\bm{W}^{i}$, each of shape
$d^{(\ell-1)}\times\frac{d^{(\ell)}}{t}$. We first transform each of the
$n^{(\ell-1)}$ nodes by $\bm{W}^{i}$. Then for each edge $(u,v)$ connecting
the layer input $u$ to the layer output $v$, we obtain its edge weight (i.e.,
a scalar) by computing the dot product between $u$’s, $v$’s transformed
feature vectors and the model attention weight vector. After obtaining the
edge weight, the remaining computation is to aggregate the $n^{(\ell-1)}$
features into the $n^{(\ell)}$ nodes. The final output is obtained by
concatenating the features of different heads. The number of MAC operations
equals:

$\displaystyle P_{\text{GAT}}^{(\ell)}=$ $\displaystyle t\cdot
n^{(\ell-1)}d^{(\ell-1)}\frac{d^{(\ell)}}{t}+2t\cdot
m^{(\ell)}\frac{d^{(\ell)}}{t}+m^{(\ell)}d^{(\ell)}$ $\displaystyle=$
$\displaystyle 3m^{(\ell)}d^{(\ell)}+n^{(\ell-1)}d^{(\ell-1)}d^{(\ell)}$ (14)

On the same graph, GCN is less expensive than GraphSAGE. GraphSAGE is in
general less expensive than GAT, due to $n^{(\ell-1)}>n^{(\ell)}$ (on the
other hand, note that $n^{(\ell-1)}=n^{(\ell)}$ for any shaDow-GNN). In
addition, for all architectures, $P_{*}^{(\ell)}$ grows proportionally with
$n^{(\ell)}$ and $m^{(\ell)}$. For the normal GNN architecture, since we are
using the full $\ell$-hop neighborhood for each node, the value of
$n^{(\ell)}$ and $m^{(\ell)}$ may grow exponentially with $\ell$. This is the
“neighbor explosion” phenonemon and is the root cause of the high inference
cost of the baseline in Table 1.

For shaDow-GNN, suppose the subgraph contains $n$ nodes and $m$ edges. Then
$n^{(\ell)}=n$ and $m^{(\ell)}=m$. The inference cost of any shaDow-GNN is
ensured to only grow linearly with the depth of the GNN.

Remark The above calculation on normal GNNs is under the realistic setting of
minibatch inference. By “realistic setting”, we mean  1. the graph size is
often gigantic (of similar scale as ogbn-papers100M);  2. the total number of
target nodes can be much, much smaller than the full graph size (_e.g._ ,
$<1\%$ of all nodes are target nodes, as in ogbn-papers100M), and  3. we may
only want to generate embedding for a small subset of the target nodes at a
time.  As a result, the above calculated computation complexity reflects what
we can achieve in practice, under minibatch computation.

On the other hand, most of the benchmark graphs evaluated in the paper may not
reflect the realistic setting. For example, ogbn-arxiv is downscaled
$657\times$ from ogbn-papers100M. Consequently, the full graph size is small
and the number of target nodes is comparable to the full graph size. Such a
“benchmark setting” enables full-batch inference: _e.g._ , for GCN, one
multiplication on the full graph adjacency matrix (_i.e._ ,
$\IfEq{}{}{\widetilde{\bm{A}}}{\widetilde{\bm{A}}}\cdot\bm{H}\cdot\bm{W}$)
generates the next layer hidden features for all nodes at once.

While full-batch computation leads to significantly lower computation
complexity than Equations 12, 13 and B, it has strict constraints on the GPU
memory size and the graph size – the full adjacency matrix and the various
feature data of _all_ nodes need to completely fit into the GPU memory. For
example, according to the official OGB guideline [16], full-batch training of
ogbn-products on a 3-layer GNN requires 48GB of GPU memory. On one hand, only
the most powerful NVIDIA GPUs (_e.g._ , RTX A6000) have memory as large as
48GB. On the other hand, ogbn-products is still $45\times$ smaller than ogbn-
papers100M. Therefore, full batch computation is not feasible in practice.

In summary, the inference complexity shown in Table 1 based on Equations 12,
13 and B reflects the feasibility of deploying the GNN models in _real-life
applications_.

##  Appendix C Designing Subgraph Extraction Algorithms

We illustrate how we can follow the three main approaches (_i.e._ , heuristic
based, model based and learning based. See Section 3.4) to design various
subgraph extraction functions. Note that the $L$-hop and PPR based EXTRACT are
only example algorithms to implement the principle of “decoupling the depth
and scope”.

Heuristic based. As discussed in Section 3.4, we can design EXTRACT by
selecting appropriate graph metrics. We have shown some examples in Section
3.4. Here we provide detailed description on the two EXTRACT used in our
experiments.

$L$-hop EXTRACT. Starting from the target node $v$, the algorithm traverses up
to $L$ hops. At a hop-$\ell$ node $u$, the sampler will add to its
hop-($\ell+1$) node set either all neighbors of $u$, or $b$ randomly selected
neighbors of $u$. The subgraph $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$
is induced from all the nodes selected by the EXTRACT. Here depth $L$ and
budget $b$ are the hyperparameters.

PPR EXTRACT. Given a target $v$, our PPR EXTRACT proceeds as follows:  1.
Compute the approximate PPR vector
$\bm{\pi}_{v}\in\mathbb{R}^{\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert}$
for $v$.  2. Select the neighborhood
$\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$ such that for
$u\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$, the PPR score
$\left[\bm{\pi}_{v}\right]_{u}$ is large.  3. Construct the induced subgraph
from $\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$.  For step 1, even though
vector $\bm{\pi}_{v}$ is of
length-$\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert$, most of
the PPR values are close to zero. So we can use a fast algorithm [3] to
compute the approximate PPR score by traversing only the local region around
$v$. Throughout the $\bm{\pi}_{v}$ computation, most of its entries remain as
the initial value of 0. Therefore, the PPR EXTRACT is scalable and efficient
w.r.t. both time and space complexity. For step 2, we can either select
$\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$ based on top-$p$ values in
$\bm{\pi}_{v}$, or based on some threshold $\left[\bm{\pi}_{v}\right]>\theta$.
Then $p$, $\theta$ are hyperparameters. For step 3, notice that our PPR
sampler only uses PPR scores as a node filtering condition. The original graph
structure is still preserved among
$\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}$, due to the induced subgraph
step. In comparison, other related works [23, 6] do not preserve the original
graph structure.

We also empirically highlight that the approximate PPR is both scalable and
efficient. The number of nodes we need to visit to obtain the approximate
$\bm{\pi}_{v}$ is much smaller than the graph size
$\left\lvert\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\right\rvert$. In addition,
each visit only involves a scalar update, which is orders of magnitude cheaper
than the cost of neighbor propagation in a GNN. We profile the three datasets,
Reddit, Yelp and ogbn-products. As shown in Table 4, for each target node on
average, the number of nodes touched by the PPR computation is comparable to
the full 2-hop neighborhood size. This also indicates that faraway neighbors
do not have much topological significance. We further show the empirical
execution time measurement on multi-core CPU machines in Figure 8.

Table 4: Average number of nodes touched by the approximate PPR computation Dataset | Avg. 2-hop size | Avg. # nodes touched by PPR
---|---|---
Reddit | 11093 | 27751
Yelp | 2472 | 5575
ogbn-products | 3961 | 5405

Model based. From Section 1, treating $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$ as
the union of $\IfEq{[v]}{}{\mathcal{G}}{\mathcal{G}}_{[v]}$’s describes a
generation process on $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$. EXTRACT then
describes the _reverse_ of such a process. This links to the graph generation
literature [26]. _e.g._ , forest-fire generation model would correspond to
EXTRACT being forest-fire sampler [25]. More specifically, to extract the
subgraph around a node $v$, we can imagine a process of adding $v$ into the
partial graph $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}^{\prime}$ consisting of
$\IfEq{}{}{\mathcal{V}}{\mathcal{V}}\setminus\\{v\\}$. Then the nodes selected
by EXTRACT would correspond to the nodes touched by such an imaginary process
of adding $v$.

Learning based. We may treat the design of EXTRACT as part of GNN training.
However, due to the combinatorial nature of subgraph extraction,
simultaneously learning EXTRACT and the shaDow-GNN layer parameters is
challenging. The learning of EXTRACT can be made possible with appropriate
approximation and relaxations. _e.g._ , we may use the techniques proposed in
[51] to design a two-phased learning process. In Phase 1, we train a normal
$L$-layer GNN, and then use [51] to identify the important neighbors among the
full $L$-hop neighborhood. In Phase 2, we use the neighborhood identified in
Phase 1 as the subgraph returned by EXTRACT. Then we train an
$L^{\prime}$-layer shaDow-GNN on top of such neighborhood.

Detailed design and evaluation on the model and learning based approaches are
left as future work.

##  Appendix D The Complete shaDow-GNN Framework

Algorithm 1 Inference algorithm for the general shaDow-GNN model

Input:
$\IfEq{}{}{\mathcal{G}}{\mathcal{G}}\left(\IfEq{}{}{\mathcal{V}}{\mathcal{V}},\IfEq{}{}{\mathcal{E}}{\mathcal{E}},\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}\right)$;
Target nodes $\IfEq{t}{}{\mathcal{V}}{\mathcal{V}_{t}}$; GNN model; $C$ number
of samplers $\\{{\text{{EXTRACT}}}_{i}\\}$;

Output: Node embedding matrix $\bm{Y}_{t}$ for
$\IfEq{t}{}{\mathcal{V}}{\mathcal{V}_{t}}$;

for $v\in\IfEq{t}{}{\mathcal{V}}{\mathcal{V}_{t}}$ do

for $i=1$ to $C$ do

Get $\IfEq{[v],i}{}{\mathcal{G}}{\mathcal{G}}_{[v],i}$ by
$\text{{EXTRACT}}_{i}$ on $\IfEq{}{}{\mathcal{G}}{\mathcal{G}}$

Propagate $\IfEq{[v],i}{}{\mathcal{G}}{\mathcal{G}}_{[v],i}$ in the $i$th
branch of $L$-layer GNN

$\bm{H}_{[v],i}\leftarrow
f_{i}^{L}\left(\IfEq{}{}{\bm{X}}{\bm{X}^{\left(\right)}}_{[v],i},{\bm{A}}_{[v],i}\right)$

$\bm{y}_{v,i}\leftarrow{\text{MLP}\left({\text{READOUT}\left(\bm{H}_{[v],i}\right)}\big{\|}\left[\bm{H}_{[v],i}\right]_{v,:}\right)}$

end for

$\bm{y}_{v}\leftarrow{\text{ENSEMBLE}\left(\\{\bm{y}_{v,i}\\}\right)}$

end for

Algorithm 1 shows the inference algorithm of shaDow-GNN after integrating the
various architecture extensions discussed in Section 3.5. The $f_{i}$ function
specifies the layer propagation of a given GNN architecture (_e.g._ , GCN,
GraphSAGE, _etc._), and $f_{i}^{L}$ is a shorthand for $L$ times iterative
layer propagation of the $L$-layer model. The
${\text{READOUT}\left(\cdot\right)}$ function performs subgraph pooling and
${\text{ENSEMBLE}\left(\cdot\right)}$ performs subgraph ensemble. The
implementation of such functions are described in the following subsections.

After the pooling by ${\text{READOUT}\left(\cdot\right)}$, we further feed
into an MLP the vector summarized from the subgraph and the vector for the
target. This way, even if two target nodes $u$ and $v$ have the same
neighborhood, we can still differentiate their embeddings based on the vectors
$\left[\bm{H}_{[v]}\right]_{v,:}$ and $\left[\bm{H}_{[u]}\right]_{u,:}$.

###  D.1 Architecture for Subgraph Pooling

The ${\text{READOUT}\left(\cdot\right)}$ function in Algorithm 1 can perform
subgraph-level operation such as sum pooling, max pooling, mean pooling, sort
pooling [57], _etc._ Table 5 summarizes all the pooling operations that we
have integrated into the shaDow-GNN framework, where $\bm{H}_{[v]}$ is the
subgraph embedding matrix as shown in Algorithm 1.

Table 5: ${\text{READOUT}\left(\cdot\right)}$ function for different pooling operations. Name | ${\text{READOUT}\left(\cdot\right)}$
---|---
Center | $\left[\bm{H}_{[v]}\right]_{v,:}$
Sum | $\sum_{u\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}}\left[\bm{H}_{[v]}\right]_{u,:}$
Mean | $\frac{1}{\left\lvert\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}\right\rvert}\sum_{u\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}}\left[\bm{H}_{[v]}\right]_{u,:}$
Max | $\max_{u\in\IfEq{[v]}{}{\mathcal{V}}{\mathcal{V}_{[v]}}}\left[\bm{H}_{[v]}\right]_{u,:}$
Sort | ${\text{MLP}\left(\left[\bm{H}_{[v]}\right]_{\left[\arg\text{sort}\left[\bm{H}_{[v]}\right]_{:,-1}\right]_{:s}}\right)}$

In particular, sort pooling  1. sorts the last column of the feature matrix,
2. takes the indices of the top $s$ values after sorting ($s$ is a
hyperparameter of the sort pooling function), and  3. slice a submatrix of
$\bm{H}_{[v]}$ based on the top-$s$ indices.  The input to the
${\text{MLP}\left(\cdot\right)}$ (last row of Table 5) is a submatrix of
$\bm{H}_{[v]}$ consisting of $s$ rows, and the output of the
${\text{MLP}\left(\cdot\right)}$ is a single vector.

###  D.2 Architecture for Subgraph Ensemble

For the ensemble function, we implement the following after applying attention
on the outputs of the different model branches:

$\displaystyle w_{i}=$
$\displaystyle{\text{MLP}\left(\bm{y}_{v,i}\right)}\cdot\bm{q}$ (15)
$\displaystyle\bm{y}_{v}=$
$\displaystyle\sum_{i=1}^{C}\widetilde{w}_{i}\cdot\bm{y}_{v,i}$ (16)

where $\bm{q}$ is a learnable vector; $\widetilde{\bm{w}}$ is normalized from
$\bm{w}$ by softmax; $\bm{y}_{v}$ is the final embedding.

##  Appendix E Detailed Experimental Setup

We used the tool “Weight & Biases” [5] for experiment tracking and
visualization to develop insights for this paper.

###  E.1 Additional Dataset Details

The statistics for the seven benchmark graphs is listed in Table 6. Note that
for Yelp, each node may have multiple labels, and thus we follow the original
paper [55] to report its F1-micro score. For all the other node classification
graphs, a node is only associated with a single label, and so we report
accuracy. Note that for Reddit and Flickr, other papers [12, 55] also report
F1-micro score. However, since each node only has one label, “F1-micro score”
is exactly the same as “accuracy”. For the link prediction graph ogbl-collab,
we use “Hits@50” as the metric.

For ogbn-papers100M, only around $1\%$ of the nodes are associated with ground
truth labels. The training / validation / test sets are split only among those
labelled nodes.

Table 6: Dataset statistics

Dataset | Setting | Nodes | Edges | Degree | Feature | Classes | Train / Val / Test
---|---|---|---|---|---|---|---
Flickr | Inductive | 89,250 | 899,756 | 10 | 500 | 7 | 0.50 / 0.25 / 0.25
Reddit | Inductive | 232,965 | 11,606,919 | 50 | 602 | 41 | 0.66 / 0.10 / 0.24
Yelp | Inductive | 716,847 | 6,977,410 | 10 | 300 | 100 | 0.75 / 0.10 / 0.15
ogbn-arxiv | Transductive | 169,343 | 1,166,243 | 7 | 128 | 40 | 0.54 / 0.18 / 0.29
ogbn-products | Transductive | 2,449,029 | 61,859,140 | 25 | 100 | 47 | 0.10 / 0.02 / 0.88
ogbn-papers100M | Transductive | 111,059,956 | 1,615,685,872 | 29 | 128 | 172 | 0.78 / 0.08 / 0.14
ogbl-collab | – | 235,868 | 1,285,465 | 8 | 128 | – | 0.92/0.04/0.04

Note that Reddit is a pre-exisiting dataset collected by Stanford, available
at http://snap.stanford.edu/graphsage. Facebook did not directly collect any
data from Reddit. None Reddit content is reproduced in this paper.

###  E.2 Hardware

We have tested shaDow-GNN under various hardware configurations, ranging from
low-end desktops to high-end servers. We observe that the training and
inference of shaDow-GNN can be easily adapted to the amount of available
hardware resources by adjusting the batch size.

In summary, we have used the following three machines to compute shaDow-GNN.

  * •

Machine 1: This is a low-end desktop machine with 4-core Intel Core i7-6700
CPU @3.4GHz, 16GB RAM and one NVIDIA GeForce GTX 1650 GPU of 4GB memory.

  * •

Machine 2: This is a low-end server with 28-core Intel Xeon Gold 5120 CPU
@2.2GHz, 128GB RAM and one NVIDIA Titan Xp GPU of 12GB memory.

  * •

Machine 3: This is another server with 64-core AMD Ryzen Threadripper 3990x
CPU @2.9GHz, 256GB RAM and three NVIDIA GeForce RTX3090 GPUs of 24GB memory.

From the GPU perspective, the low-end GTX 1650 GPU can support the shaDow-GNN
computation on all the graphs (including ogbn-papers100M). However, the
limited RAM size of Machine 1 limits its usage to only Flickr, Reddit, ogbn-
arxiv and ogbl-collab. The other two servers, Machine 2 and Machine 3, are
used to train all of the seven graphs.

Table 7 summarizes our recommended minimum hardware resources to run shaDow-
GNN. Note that regardless of the model, larger graphs _inevitibly requires
larger RAM_ due to the growth of the raw features (the raw data files of ogbn-
papers100M already takes 70GB). However, larger graphs _do not correspond to
higher GPU requirement_ for shaDow-GNN, since the GPU memory consumption is
controlled by the batch size parameter.

See Appendix F.1 for how to control the GPU memory-speed tradeoff by batch
size.

Table 7: Recommended minimum hardware resources for shaDow-GNN Dataset | Num. nodes | CPU cores | RAM | GPU memory
---|---|---|---|---
ogbn-arxiv | 0.2M | 4 | 8GB | 4GB
ogbn-products | 2.4M | 4 | 32GB | 4GB
ogbn-papers100M | 111.1M | 4 | 128GB | 4GB

###  E.3 Software

The code is written in `Python 3.8.5` (where the sampling part is written with
`C++` parallelized by `OpenMP`, and the interface between `C++` and `Python`
is via `PyBind11`). We use `PyTorch 1.7.1` on `CUDA 11.1` to train the model
on GPU.

###  E.4 Hyperparameter Tuning

For all models in Table 1, we set the hidden dimension to be $d^{(\ell)}=256$.
In addition, for GAT and shaDow-GAT, we set the number of attention heads to
be $t=4$. For all the GIN and shaDow-GIN experiments, we use a 2-layer MLP
(with hidden dimension $256$) to perform the injective mapping in each GIN
layer. For all the JK-Net and shaDow-JK experiments, we use the concatenation
operation to aggregate the hidden features of each layer in the JK layer.
Additional comparison on GIN, JK-Net and their shaDow versions is shown in
Table 12.

All experiments are repeated five times without fixing random seeds.

For all the baseline and shaDow-GNN experiments, we use Adam optimizer [21].
We perform grid search on the hyperparameter space defined by:

  * •

Activation: $\left\\{\text{ReLU},\text{ELU},\text{PRELU}\right\\}$

  * •

Dropout: 0 to 0.5 with stride of 0.05

  * •

DropEdge: 0 to 0.5 with stride of 0.05

  * •

Learning rate: $\\{$110-2$,$210-3$,$110-3$,$210-4$,$110-4$,$210-5$\\}$

  * •

Batch size: $\\{16,32,64,128\\}$

The EXTRACT hyperparameters are tuned as follows.

For the PPR EXTRACT, we consider two versions: one based on fixed sampling
budget $p$ and the other based on PPR score thresholding $\theta$.

  * •

If with fixed budget, then we disable the $\theta$ thresholding. We tune the
budget by $p\in\left\\{150,175,200\right\\}$.

  * •

If with thresholding, we set $\theta\in\left\\{0.01,0.05\right\\}$. We still
have an upper bound $p$ on the subgraph size. So if there are $q$ nodes in the
neighborhood with PPR score larger than $\theta$, the final subgraph size
would be $\max\\{p,q\\}$. Such an upper bound eliminates the corner cases
which may cause hardware inefficiency due to very large $q$. In this case, we
set the upper bound $p$ to be either 200 or 500.

For $L$-hop EXTRACT, we define the hyperparameter space as:

  * •

Depth $L=2$

  * •

Budget $b\in\left\\{5,10,15,20\right\\}$

The hyperparameters to reproduce the Table 1 shaDow-GNN results are listed in
Tables 8 and 9. The hyperparameters to reproduce the Table 2 and 3 shaDow-GNN
results are listed in Table 10.

Table 8: Training configuration of shaDow-GNN for Table 1 (PPR EXTRACT)

Arch. | Dataset | Layers | Dim. | Pooling | Learning Rate | Batch Size | Dropout | DropEdge | Budget $p$
---|---|---|---|---|---|---|---|---|---
shaDow-GCN | Flickr | 3 | 256 | – | 0.001 | 256 | 0.40 | 0.10 | 200
5 | 256 | – | 0.001 | 256 | 0.40 | 0.10 | 200
5 | 256 | mean | 0.001 | 256 | 0.40 | 0.10 | 200
Reddit | 3 | 256 | – | 0.0001 | 128 | 0.20 | 0.15 | 200
5 | 256 | – | 0.0001 | 128 | 0.20 | 0.15 | 200
3 | 256 | max | 0.0001 | 128 | 0.20 | 0.15 | 200
Yelp | 3 | 256 | – | 0.001 | 32 | 0.10 | 0.00 | 100
5 | 256 | – | 0.001 | 32 | 0.10 | 0.00 | 100
5 | 256 | max | 0.001 | 32 | 0.10 | 0.00 | 100
ogbn-arxiv | 3 | 256 | – | 0.00005 | 32 | 0.20 | 0.10 | 200
5 | 256 | – | 0.00005 | 32 | 0.20 | 0.10 | 200
5 | 256 | max | 0.00002 | 16 | 0.25 | 0.10 | 200
ogbn-products | 3 | 256 | – | 0.002 | 128 | 0.40 | 0.05 | 150
5 | 256 | – | 0.002 | 128 | 0.40 | 0.05 | 150
5 | 256 | max | 0.002 | 128 | 0.40 | 0.05 | 150
shaDow-SAGE | Flickr | 3 | 256 | – | 0.0005 | 64 | 0.45 | 0.05 | 200
5 | 256 | – | 0.001 | 128 | 0.45 | 0.00 | 200
5 | 256 | max | 0.001 | 128 | 0.45 | 0.00 | 200
Reddit | 3 | 256 | – | 0.0001 | 128 | 0.20 | 0.15 | 200
5 | 256 | – | 0.0001 | 128 | 0.20 | 0.15 | 200
5 | 256 | max | 0.0001 | 128 | 0.20 | 0.15 | 200
Yelp | 3 | 256 | – | 0.0005 | 16 | 0.10 | 0.00 | 100
5 | 256 | – | 0.0005 | 16 | 0.10 | 0.00 | 100
3 | 256 | max | 0.0005 | 16 | 0.10 | 0.00 | 100
ogbn-arxiv | 3 | 256 | – | 0.00002 | 16 | 0.25 | 0.15 | 200
5 | 256 | – | 0.00002 | 16 | 0.25 | 0.15 | 200
5 | 256 | max | 0.00002 | 16 | 0.25 | 0.15 | 200
ogbn-products | 3 | 256 | – | 0.002 | 128 | 0.40 | 0.05 | 150
5 | 256 | – | 0.002 | 128 | 0.40 | 0.05 | 150
3 | 256 | max | 0.002 | 128 | 0.40 | 0.15 | 150
shaDow-GAT | Flickr | 3 | 256 | – | 0.0005 | 64 | 0.45 | 0.00 | 200
5 | 256 | – | 0.0005 | 64 | 0.45 | 0.00 | 200
3 | 256 | mean | 0.001 | 128 | 0.40 | 0.00 | 200
Reddit | 3 | 256 | – | 0.0001 | 128 | 0.20 | 0.00 | 200
5 | 256 | – | 0.0001 | 128 | 0.20 | 0.00 | 200
5 | 256 | max | 0.0001 | 128 | 0.20 | 0.00 | 200
Yelp | 3 | 256 | – | 0.0005 | 16 | 0.10 | 0.00 | 100
5 | 256 | – | 0.0005 | 16 | 0.10 | 0.00 | 100
3 | 256 | max | 0.0005 | 16 | 0.10 | 0.00 | 100
ogbn-arxiv | 3 | 256 | – | 0.0001 | 64 | 0.20 | 0.00 | 200
5 | 256 | – | 0.0001 | 64 | 0.20 | 0.00 | 200
5 | 256 | max | 0.0001 | 64 | 0.20 | 0.00 | 200
ogbn-products | 3 | 256 | – | 0.001 | 128 | 0.35 | 0.10 | 150
5 | 256 | – | 0.001 | 128 | 0.35 | 0.10 | 150
3 | 256 | max | 0.001 | 128 | 0.35 | 0.10 | 150

Table 9: Training configuration of shaDow-GNN for Table 1 ($2$-hop EXTRACT)

Arch. | Dataset | Layers | Dim. | Pooling | Learning Rate | Batch Size | Dropout | DropEdge | Budget $b$
---|---|---|---|---|---|---|---|---|---
shaDow-SAGE | Flickr | 3 | 256 | – | 0.0005 | 64 | 0.45 | 0.05 | 20
5 | 256 | – | 0.0005 | 64 | 0.45 | 0.05 | 20
Reddit | 3 | 256 | – | 0.0001 | 128 | 0.20 | 0.15 | 20
5 | 256 | – | 0.0001 | 128 | 0.20 | 0.15 | 20
Yelp | 3 | 256 | – | 0.0005 | 16 | 0.10 | 0.00 | 20
5 | 256 | – | 0.0005 | 16 | 0.10 | 0.00 | 20
ogbn-arxiv | 3 | 256 | – | 0.00005 | 16 | 0.25 | 0.15 | 20
5 | 256 | – | 0.00005 | 16 | 0.25 | 0.15 | 20
ogbn-products | 3 | 256 | – | 0.002 | 128 | 0.40 | 0.05 | 20
5 | 256 | – | 0.002 | 128 | 0.40 | 0.05 | 20

Table 10: Training configuration of shaDow-GNN for Table 2 and 3 (PPR EXTRACT)

Dataset | Arch. | Layers | Dim. | Pooling | Learning Rate | Dropout | DropEdge | Budget $p$ | Threshold $\theta$
---|---|---|---|---|---|---|---|---|---
ogbn-papers100M | shaDow-GAT200 | 5 | 800 | max | 0.0002 | 0.30 | 0.10 | 200 | 0.002
shaDow-GAT400 | 3 | 800 | max | 0.0002 | 0.35 | 0.10 | 400 | 0.002
ogbl-collab | shaDow-SAGE | 5 | 256 | sort | 0.00002 | 0.25 | 0.10 | 200 | 0.002

###  E.5 Setup of the SGC Experiments

Following [47], we compute the SGC model as
$\bm{Y}={\text{softmax}\left(\widetilde{\bm{A}}^{K}\bm{X}\bm{W}\right)}$ where
$\widetilde{\bm{A}}=\widetilde{\bm{D}}^{-\frac{1}{2}}\widetilde{\bm{A}}\widetilde{\bm{D}}^{-\frac{1}{2}}$
and $\widetilde{\bm{A}}=\bm{I}+\bm{A}$. Matrix $\bm{W}$ is the only learnable
parameter. $K$ is the power on the adjacency matrix and we vary it as
$K\in\\{1,3,5,10,20,30,40\\}$ in the Figure 3 experiments. For shaDow-SGC, we
compute the embedding for target $v$ as
$\bm{y}_{v}=\left[{\text{softmax}\left(\widetilde{\bm{A}}_{[v]}^{K}\bm{X}_{[v]}\bm{W}\right)}\right]_{v,:}$.

SGC and shaDow-SGC are trained with the same hyperparameters (i.e., learning
rate equals 0.001 and dropout equals 0.1, across all datasets). shaDow-SGC
uses the same EXTRACT as the shaDow-GCN model in Table 1. In the legend of
Figure 3, due to lack of space, we use s-SGC to denote shaDow-SGC. We use “F”,
“R” and “A” to denote the datasets of Flickr, Reddit and ogbn-arxiv
respectively.

##  Appendix F Additional Experimental Results

###  F.1 Understanding the Low Memory Overhead of shaDow-GNN

shaDow-GNN in general consumes much less memory than the other GNN-based
methods. We can understand the low memory overhead of shaDow-GNN from two
perspectives.

Comparing with the normal GNN model, shaDow-GNN requires much less GPU memory
since both the training and inference of shaDow-GNN proceeds in minibatches.
While other minibatching training algorithms exist for the normal GNNs (_e.g._
, layer sampling [7] and graph sampling [55]), such algorithms either result
in accuracy degradation or limited scalability. Therefore, most of the OGB
leaderboard methods are tuned with _full-batch_ training.

Comparing with the simplified GNN models (_e.g._ , SIGN [11] and SGC [47]),
shaDow-GNN requires much less RAM size. The reason is that both SIGN and SGC
rely on preprocessing of node features over the full graph. Specifically, for
SIGN, its preprocessing step concatenates the original node features with the
smoothened values. For the $(p,s,t)$ architecture of SIGN (see the SIGN paper
for definition of $p$, $s$ and $t$), the memory required to store the
preprocessed features equals:

$M=N\cdot
f\cdot\left(\left(p+1\right)+\left(s+1\right)+\left(t+1\right)\right)$ (17)

where $N$ is the number of nodes in the full graph and $f$ is the original
node feature size. For the $(3,3,3)$ SIGN / SIGN-XL architecture on the ogbn-
papers100M leaderboard (see Table 2), the required RAM size equals $M=682$GB.
This number does not even consider the RAM consumptions due to temporary
variables or other buffers for the trainig operations.

For SGC, even though it does not perform concatenation of the smoothened
features, it still requires double the original feature size to store the
temporary values of ${\bm{A}}^{K}\cdot\bm{X}$. The original features of ogbn-
papers100M takes around 56GB, and the full graph adjacency matrix consumes
around 25GB. In sum, SGC requires at least $2\cdot 56+25=137$GB of RAM.

Table 11 summarizes the RAM / GPU memory consumption for the leaderboard
methods listed in Table 2. Note that our machines do not support the training
of SIGN (due to the RAM size constraint), and thus we only show the lower
bound of SIGN’s RAM consumption in Table 11.

Table 11: Memory consumption of the ogbn-papers100M leaderboard methods Method | CPU RAM | GPU memory
---|---|---
GraphSAGE+incep | 80GB | 16GB
SIGN-XL |  $>$682GB | 4GB
SGC |  $>$137GB | 4GB
shaDow-GAT | 80GB | 4GB

On the other hand, shaDow-GNN can flexibly adjust its batch size based on the
available memory. Even for ogbn-papers100M, a typical low-end server with 4GB
of GPU memory and 128GB of RAM is sufficient to train the 5-layer shaDow-GAT.
Increasing the batch size of shaDow-GNN may further lead to higher GPU
utilization for more powerful machines. Figure 7 shows the computation time
speedup (compared with batch size 32) and GPU memory consumption for shaDow-
GAT under batch size of 32, 64 and 128. A 5-layer shaDow-GAT only requires
around 5GB of GPU memory to saturate the computation resources of the powerful
GPU cards such as NVIDIA RTX 3090.

$0$$2$$4$$6$$8$$10$$12$$0$$1$$2$GPU (RTX 3090) memory consumption
(GB)Execution speedup ($\times$)ogbn-productsogbn-papers100M Figure 7:
Controlling the GPU memory-speed tradeoff by shaDow-GAT batch size (32, 64,
128)

###  F.2 shaDow-GNN on Other Architectures

In addition to the GCN, GraphSAGE and GAT models in Table 1, we further
compare JK-Net and GIN with their shaDow versions in Table 12. For all the
results in Tabel 1, we do not apply pooling or ensemble on shaDow-GNN. Similar
to DropEdge, the skip connection (or “jumping knowledge”) of JK-Net helps
accuracy improvement on deeper models. Compared with the normal JK-Net,
increasing the depth benefits shaDow-JK more. The GIN architecture
theoretically does not oversmooth. However, we observe that the GIN training
is very sensitive to hyperparameter settings. We hypothesize that such a
challenge is due to the sensitivity of the sum aggregator on noisy neighbors
(e.g., for GraphSAGE, a single noisy node can hardly cause a significant
perturbation on the aggregation, due to the averaging over the entire
neighborhood). The accuracy improvement of shaDow-GIN compared with the normal
GIN may thus be due to noise filtering by the EXTRACT. The impact of noises /
irrelevant neighbors can be critical, as reflected by the 5-layer GIN accuracy
on Reddit.

Table 12: Test accuracy on other architectures (PPR EXTRACT)

| Flickr | Reddit | ogbn-arxiv
---|---|---|---
| Normal | shaDow | Normal | shaDow | Normal | shaDow
JK (3) | 0.4945$\pm$0.0070 |  0.5317$\pm$0.0027 | 0.9649$\pm$0.0010 |  0.9682$\pm$0.0003 | 0.7130$\pm$0.0026 |  0.7201$\pm$0.0017
JK (5) | 0.4940$\pm$0.0083 |  0.5328$\pm$0.0026 | 0.9640$\pm$0.0013 |  0.9685$\pm$0.0006 | 0.7166$\pm$0.0053 |  0.7226$\pm$0.0024
GIN (3) | 0.5132$\pm$0.0031 |  0.5228$\pm$0.0028 | 0.9345$\pm$0.0034 |  0.9578$\pm$0.0006 | 0.7087$\pm$0.0016 |  0.7173$\pm$0.0029
GIN (5) | 0.5004$\pm$0.0067 |  0.5255$\pm$0.0023 | 0.7550$\pm$0.0039 |  0.9552$\pm$0.0007 | 0.6937$\pm$0.0062 |  0.7140$\pm$0.0027

###  F.3 Benefits of Pooling

In Table 13, we summarize the average accuracy of 5-layer shaDow-SAGE obtained
from different pooling functions (see Table 5 for the equations for pooling).
For both graphs, adding a pooling layer helps improve accuracy. On the other
hand, the best pooling function may depend on the graph characteristics. We
leave the in-depth analysis on the effect of pooling as future work.

Table 13: Effect of subgraph pooling on 5-layer shaDow-SAGE Dataset | None | Mean | Max | Sort
---|---|---|---|---
Flickr | 0.5351$\pm$0.0026 | 0.5361$\pm$0.0015 | 0.5354$\pm$0.0021 |  0.5367$\pm$0.0026
ogbn-arxiv | 0.7302$\pm$0.0014 | 0.7304$\pm$0.0015 |  0.7342$\pm$0.0017 | 0.7295$\pm$0.0018

###  F.4 Cost of Subgrpah Extraction

FlickrRedditYelparxivproductspapers100M$0$$1$$2$$3$Inference time per node
(ms)PPRshaDow-SAGEshaDow-GAT Figure 8: Measured execution time for PPR EXTRACT
and the GNN model computation

We evaluate the PPR EXTRACT in terms of its execution time overhead and
accuracy-time tradeoff. In Figure 8, we parallelize EXTRACT using half of the
available CPU cores of Machine 3 (_i.e._ , 32 cores) and execute the GNN
computation on the RTX 3090 GPU. Clearly, the PPR EXTRACT is lightweight: the
sampling time is lower than the GNN computation time in most cases. In
addition, the sampling time per node does not grow with the full graph size.
This shows that shaDow-GNN is scalable to massive scale graphs. By the
discussion in Appendix C, the approximate PPR computation achieves efficiency
and scalability by only traversing a local region around each target node.

###  F.5 Tradeoff Between Inference Time and Accuracy

$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$0.4$$0.6$$0.8$$1$Inference time per
node (ms)Test accuracyTradeoff analysis
(5-layer)shaDowSAGEshaDowGATNormalSAGENormalGATFlickrRedditarxivproducts
Figure 9: Inference performance tradeoff. We test pre-trained models by
subgraphs of various sizes.

To evaluate the accuracy-time tradeoff, we take the $5$-layer models of Table
1 as the pretrained models. Then for shaDow-GNN, we vary the PPR budget $p$
from 50 to 200 with stride 50. In Figure 9, the inference time of shaDow-GNN
has already included the PPR sampling time. Firstly, consistent with Table 1,
inference of shaDow-GNN achieves higher accuracy than the normal GNNs, with
orders of magnitude speedup as well. In addition, based on the application
requirements (e.g., latency constraint), shaDow-GNNs have the flexibility of
adjusting the sampling size without the need of retraining. For example, on
Reddit and ogbn-arxiv, directly reducing the subgraph size from 200 to 50
reduces the inference latency by $2\times$ to $4\times$ at the cost of less
than $1\%$ accuracy drop.

Table 14: shaDow-GCN test accuracy $L^{\prime}$ | EXTRACT | Flickr | ogbn-products
---|---|---|---
3 | PPR | 0.5257$\pm$0.0021 | 0.7773$\pm$0.0032
5 |  $2$-hop | 0.5210$\pm$0.0023 | 0.7794$\pm$0.0039
PPR | 0.5273$\pm$0.0020 | 0.7836$\pm$0.0034
Ensemble |  0.5304$\pm$0.0017 |  0.7858$\pm$0.0021
7 | PPR | 0.5225$\pm$0.0023 |  0.7850$\pm$0.0044

###  F.6 Ensemble and Deeper Models

Table 14 shows additional results on subgraph ensemble and deeper shaDow-GCN
models. The PPR and $2$-hop EXTRACT follow the same configuration as Table 8
and 9. When varying the model depth, we keep all the other hyperparameters
unchanged. From both the Flickr and ogbn-products results, we observe that
ensemble of the PPR EXTRACT and the $2$-hop EXTRACT helps improve the shaDow-
GCN accuracy. From the ogbn-products results, we additionally observe that
increasing shaDow-GCN to deeper than 5 layers may still be beneficial. As
analyzed by Figure 2, the model depth of 5 is already much larger than the
hops of the subgraph. The 7-layer results in Table 14 indicate future research
opportunities to improve the shaDow-GNN accuracy by going even deeper.