Nested Graph Neural Networks
Authors: Muhan Zhang
Pan Li
Venue: NeurIPS 2021 Poster (2021)
Keywords: graph neural network
theory
expressive power
Weisfeiler-Lehman

Abstract: Graph neural network (GNN)'s success in graph classification is closely related to the Weisfeiler-Lehman (1-WL) algorithm. By iteratively aggregating neighboring node features to a center node, both 1-WL and GNN obtain a node representation that encodes a rooted subtree around the center node. These rooted subtree representations are then pooled into a single representation to represent the whole graph. However, rooted subtrees are of limited expressiveness to represent a non-tree graph. To address it, we propose Nested Graph Neural Networks (NGNNs). NGNN represents a graph with rooted subgraphs instead of rooted subtrees, so that two graphs sharing many identical subgraphs (rather than subtrees) tend to have similar representations. The key is to make each node representation encode a subgraph around it more than a subtree. To achieve this, NGNN extracts a local subgraph around each node and applies a base GNN to each subgraph to learn a subgraph representation. The whole-graph representation is then obtained by pooling these subgraph representations. We provide a rigorous theoretical analysis showing that NGNN is strictly more powerful than 1-WL. In particular, we proved that NGNN can discriminate almost all r-regular graphs, where 1-WL always fails. Moreover, unlike other more powerful GNNs, NGNN only introduces a constant-factor higher time complexity than standard GNNs. NGNN is a plug-and-play framework that can be combined with various base GNNs. We test NGNN with different base GNNs on several benchmark datasets. NGNN uniformly improves their performance and shows highly competitive performance on all datasets.

Nested Graph Neural Networks
Muhan Zhang 1,2 Pan Li Institute for Artificial Intelligence, Peking University Beijing Institute for General Artificial Intelligence Department of Computer Science, Purdue University
Abstract
Graph neural network (GNN)'s success in graph classification is closely related to the Weisfeiler-Lehane (1- (L- algorithm. By iteratively aggregating neighboring node features to center node, both 1-WL and GNN obtain a node representation that encodes a rooted subtree around the center node. These rooted subtree rep- resentations then pooled into single representation represent the whole graph. However, rooted subtrees are of limited expressiveness to represent a non- tree graph. To address it, propose Nested Graph Neural Networks (NGNNs). NGNN represents a graph with rooted subgraphs instead of rooted subtrees, so that two graphs sharing many identical subgraphs (rather than subtrees) tend have similar representations. The key is to make each node representation encode subgraph around it more than subtree. To achieve this, NGNN extracts a local subgraph around each node and applies base GNN to each subgraph to learn a subgraph representation. The whole-graph representation then obtained by pooling these subgraph representations. We provide rigorous theoretical analysis showing that NGNN is strictly more powerful than 1-WL. In particular, we proved that NGNN can discriminate almost all r-regular graphs, where 1-WL always fails. Moreover, unlike other more powerful GNNs, NGNN only introduces a constant- factor higher time complexity than standard GNNs. NGNN is plug-and-play framework that can be combined with various base GNNs. We test NGNN with different base GNNs on several benchmark datasets. NGNN uniformly improves their performance and shows highly competitive performance on all datasets.
Introduction
Graph is an important tool to model relational data in the real world. Representation learning graphs has become a popular topic of machine learning in recent years. While network embedding methods, such as DeepWalk [1], can learn node representations well, they fail generalize to whole-graph representations, which are crucial for applications such as graph classification, molecule modeling, and drug discovery. On the contrary, although traditional graph kernels (2-7 can be used for graph classification, they define graph similarity often in heuristic way, which is not parameterized and lacks some flexibility deal with features.
In this context, graph neural networks (GNNs) have regained people's attention and become the state-of-the-art graph representation learning tool [7. GNNs use message passing propagate features between connected nodes. By iteratively aggregating neighboring node features to the center node, GNNs learn node representations encoding their local structure and feature information. These node representations can be further pooled into a graph representation, enabling graph-level tasks such graph classification. this paper, we will use message passing GNNs denote this class
"Corresponding author: Muhan Zhang (muhan@pku. edu. cn).
Pan Li contributes Sec. 3.3 that proves the Theorem I and some implementation ideas.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Original graphs
Rooted subtrees around vi and P2
Rooted subgraphs around and 2o
Height=1
Height=1
Height-2
Height-2
Height-1
Hlight-1
Height-2
Height=2
Figure 1: The two original graphs G1 and G2 are non-isomorphic. G1 is composed of two triangles, while G2 a hexagon. However, both 1-WI. and message passing GNNs cannot differentiate them, since all nodes in the two graphs share identical rooted subtrees at any height (see the rooted subtrees around in and v2 in the middle block for example). In comparison. we can discriminate the two graphs by comparing their height-1 rooted subgraphs around any nodes. For example, the height-1 I rooted subgraph around v1 is closed triangle, but the height-1 rooted subgraph around v2 an open triangle (see the red boxes in the right block).
of GNNs based on repeated neighbor aggregation [18), in order to distinguish them from some high-order GNN variants (19 where the effective message passing happens between high-order node tuples instead of nodes.
GNNs' message passing scheme mimics the 1-dimensional Weisfeiler-Lehme (1-WL) algorithm 22 which iteratively refines a node's color according to its current color and the multiset of its neighbors' colors. This procedure essentially encodes rooted subtree around each node into its final color, where the rooted subtree is constructed by recursively expanding the neighbors of the root node. One critical reason for GNN's success in graph classification is because two graphs sharing many identical or similar rooted subtrees are more likely classified into the same class, which actually aligns with the inductive bias that two graphs are similar if they have many common substructures [23
Despite this, rooted subtrees are still limited in terms of expressing all possible substructures that can appear in graph. It is likely that two graphs, despite sharing lot of identical rooted subtrees, are not similar at all because their other substructure patterns are not similar. Take the two graphs G1 and G2 in Figure as an example. If we apply 1-WL message passing GNN to them, the two graphs will always have the same representation no matter how many iterations/layers we use. This is because all nodes in the two graphs have identical rooted subtrees across all tree heights. However, the two graphs are quite different from a holistic perspective. G1 is composed of two triangles, while G2 is hexagon. The intrinsic reason for such failure is that rooted subtrees have limited expressiveness for representing general graphs, especially those with cycles.
To address this issue, we propose Nested Graph Neural Networks (NGNNs). The core idea is, instead of encoding a rooted subtree, we want the final representation of node to encode a rooted subgraph (local h-hop subgraph) around it. The subgraph is not restricted to be of any particular graph type such as tree, but serves as a general description of the local neighborhood around node. Rooted subgraphs offer much better representation power than rooted subtrees, e.g., can easily discriminate the two graphs in Figure by only comparing their height-1 rooted subgraphs.
To represent a graph with rooted subgraphs, NGNN uses two levels of GNNs: base (inner) GNNs and an outer GNN. By extracting a local rooted subgraph around each node, NGNN first applics a base GNN to each node's 's subgraph independently. Then, subgraph pooling layer is applied to each subgraph to aggregate the intermediate node representations into a subgraph representation. This subgraph representation is used the final representation of the root node. Rather than encoding rooted subtree, this final node representation encodes the local subgraph around it, which contains more information than subtree. Finally, all the final node representations outer GNN to learn a representation for the entire graph. Figure 2 shows one NGNN implementation using message passing GNNs the base GNNs and a simple graph pooling layer as the outer GNN.
further fed into an
One may wonder that the base GNN seems to still learn only rooted subtrees it is message-passing- based. Then why is NGNN more powerful than GNN? One key reason lies in the subgraph pooling
2

---

(base) GNNs
Outer GNN
Graph elaveificaiin
Perform message passing within each subgraph
Grapph regressin
Apply (subgraph pooling)
Use the outputs from inner GNNs the final node representations
Extract a rooted subgraph around each mude
Apply juaph pooling) get gruph representation
Figure 2: A particular implementation of the NGNN framework. It first extracts (copies) a rooted subgraph (height=1) around each node from the original graph, and then applies a base GNN with a subgraph pooling layer cach rooted subgraph independently to learn subgraph representation. The subgraph representation used the root node's final representation in the original graph. Then, a graph pooling layer used to summarize the final node representations into a graph representation.
layer. Take the height-1 rooted subgraphs (marked with red boxes) around U1 and 02 in Figure I as an example. Although t) and 02 's height-1 rooted subtrees are still the same, their neighbors (labeled by I and 2) have different height-1 rooted subtrees. Thus, applying one-layer message passing GNN plus subgraph pooling as the base GNN is sufficient to discriminate G1 and G2-
The NGNN framework has multiple exclusive advantages. Firstly, it allows freely choosing the base GNN, and can enhance the base GNN's representation power in a plug-and-play fashion. Theoretically, we proved that NGNN is more powerful than message passing GNNs and 1-WL by being able to discriminate almost all r-regular graphs (where 1-WL always fails). Secondly, by extracting rooted subgraphs, NGNN allows augmenting the initial features of a node with subgraph- specific structural features such as distance encoding (24] to improve the quality of the learned node representations. Thirdly, unlike other more powerful graph neural networks, especially those based on higher-order WL. tests [1 25, NGNN still has linear time and space complexity w.r.t. graph size like standard message passing GNNs, thus maintaining good scalability. We demonstrate the effectiveness of the NGNN framework in various synthetic/real-world graph classification/rgresste datasets. On synthetic datasets, NGNN demonstrates higher-than-I-W expressive power, matching very well with our theorem. On real-world datasets, NGNN consistently enhances a wide range of base GNNs' performance, achieving highly competitive results on all datasets.
2 Preliminaries
2.1 Notation and problem definition
We consider the graph classification/regression problem. Given graph G (V, where V {1, 1.2.....) n is the node set and E. C V x is the edge set, we aim to learn a function mapping G to its class target value y. The nodes and edges in G can have feature vectors associated with them, denoted by x; (for node i) and eig (for edge (i, ()), respectively.
2.2 Weisfeiler-L.chman test
The Wesfeiler-Lehmaal (1-WL) test [22] is popular algorithm for graph isomorphism checking. The classical 1-WL works follows. At first, all nodes receive color 1. Each node collects its neighbors' colors into multiset. Then, I-WL will update each node's color so that two nodes get the same new color if and only if their current colors are the same and they have identical multisets of neighbor colors. Repeat this process until the number colors does not increase between two iterations. non-isomorppic if their node colors are different at some
Then, 1-WL will return that two graphs iteration, or fail to determine whether they are non-isomorphic. See [7] 26 for more details.
1-WL essentially encodes the rooted subtrees around each node at different heights into its color representations. Figure middle shows the rooted subtrees around ii and U2. Two nodes will have the same color at iteration h if and only if their height-h rooted subtrees are the same.

---

3 Nested Graph Neural Network
In this section, we introduce our Nested Graph Neural Network (NGNN) framework and theoretically demonstrate its higher representation power than message passing GNNs.
3.1 Limitations of the message passing GNNs
Most existing GNNs follow the message passing framework [18]: given a graph G. each node's hidden state h is updated based on its previous state h and the messages m from its neighbors
h ++1 Uh m where m
Me(hin hiy evu).
(1)
(EN(v]G)
Here Mr, U2 are the message and update functions at time stamp t, Evu is the feature of edge (v, u), and (v(GG) is the set of v's neighbors in graph G. The initial hidden states h" are given by the raw node features E.. After T time stamps (iterations). the final node representations h are summarized into a whole-graph representation with a readout (pooling) function (e.g., mean or sum):
hG R( E G)).
2)
Such a message passing (or neighbor aggregation) scheme iteratively aggregates neighbor information into center node's 's hidden state, making it encode local rooted subtree around the node. The final node representations will contain both the local structure and feature information around nodes, enabling node-level tasks such node classification. After a pooling layer, these node representations can be further summarized into a graph representation, enabling graph-level tasks. When there is no edge feature and the node features are from countable space, it is shown that message passing GNNs are at most as powerful as the 1-WL test for discriminating non-isomorphic graphs 27
For an h-layer message passing GNN, it will give two nodes the same final representation if they have identical height-h rooted subtrees (i.e., both the structures and the features on the corresponding nodes/edges are the same). If two graphs have lot of identical (or similar) rooted subtrees, they will also have similar graph representations after pooling. This insight is crucial for the success of modern GNNs in graph classification, because it aligns with the inductive bias that two graphs are similar if they have many common substructures. Such insight has also been used in designing the WL subtree kernel 77, state-of-the-arr graph classification method before GNNs.
However, message passing GNNs have several limitations. Firstly, rooted subtree is only one specific substructure. It is not general enough to represent arbitrary subgraphs, especially those with cycles due to the natural restriction of tree structure. Secondly, using rooted subtree as the elementary substructure results in discriminating power bounded by the 1-WL test. For example, all n-node r-regular graphs cannot be discriminated by message passing GNNs. Thirdly, standard message passing GNNs do not allow using root-node-specifie structural features (such as the distance between a node and the root node) to improve the quality of the learned root node's ' representation. We might need to break through such limitations in order to design more powerful GNNs.
3.2 The NGNN framework
To address the above limitations, we propose the Nested Graph Neural Network (NGNN) framework. NGNN no longer aims encode a rooted subtree around each node. Instead, in NGNN, each node's final representation encodes the general local subgraph information around it more than a subtree, so that two graphs sharing lot of identical or similar rooted subgraphs will have similar representations.
Definition 1. (Rooted subgraph) Given graph G and node the height-h rooted subgraph G²; of is the subgraph induced from G by the nodes within h hops of v (including h-hop nodes).
To make node's s final representation encode a rooted subgraph, we need compute a subgraph representation. To achieve this, we resort to an arbitrary GNN, which we call the base GNN of NGNN. For example, the base GNN can be simply a message passing GNN, which performs message passing within each rooted subgraph to learn an intermediate representation for every node of the subgraph, and then uses a pooling layer to summarize a subgraph representation from the intermediate node representations. This subgraph representation is used as the final representation of the root node in

---

the original graph. Take root node w as an example. We first perform T rounds of message passing within node w's rooted subgraph G Let e be any node appearing in G We have
h e = Ui m m E, ) where m 1+1 v,Gh
Σ
Mi(h h Ku eva).
(3)
(EN())))
Here Mr, Ur are the message and update functions of the base GNN at time stamp I, N(v denotes the set of v's neighbors within w's rooted subgraph Ch., and h 1+1 and m 1+1 denote R,
v.
node u's hidden state and message specific to rooted subgraph G at time stamp t + Note that when node y attends different nodes' rooted subgraphs, its hidden states and messages will also be different. This is in contrast to standard GNNs where a node's 's hidden state and message at time f is the same regardless of which root node contributes to. For example, h1+1 and m in Eq. do not depend on any particular rooted subgraph.
After T rounds of message passing, we apply a subgraph pooling layer to summarize a subgraph representation hag from the intermediate node representations {hr e,, |V E Gw).
hw : = hag = Ro((h" |U E G
(4)
where Ro is the subgraph pooling layer. This subgraph representation hGs will be used as root node w's final representation h. in the original graph. Note that the base GNNs are simultaneously applied all nodes' rooted subgraphs
return final node representation for every node in the original graph, and all the base GNNs share the same parameters. With such node representations, NGNN uses an outer GNV to further process and aggregate them into a graph representation of the whole graph. For simplicity, we let the outer GNN be simply graph pooling layer denoted by Ry:
hg == (f ww E G)).
(5)
The Nested GNN framework can be understood as a two-level GNN, or a GNN of GNNs the inner subgraph-level GNNs (base GNNs) are used to learn node representations from their rooted subgraphs, while the outer graph-level GNN is used to return a whole-graph representation from the inner GNNs' outputs. The inner GNNs all share the same parameters which are trained end-to-end with the outer GNN. Figure depicts the implementation of the NGNN framework described above.
Compared to message passing GNNs, NGNN changes the "receptive field" of cach node from rooted subtree to a rooted subgraph, in order to capture better local substructure information. The rooted subgraph is read by base GNN to learn a subgraph representation. Finally, the outer GNN reads the subgraph representations output by the base GNNs to return a graph representation.
Note that, when we apply the base GNN to a rooted subgraph, this rooted subgraph is extracted (copied) out of the original graph and treated as completely independent graph from the other rooted subgraphs and the original graph. This allows the same node to have different representations within different rooted subgraphs. For example, in Figure 2 the same node B appears four different rooted subgraphs. Sometimes it is the root node, while other times it is a 1-hop neighbor of the root node. NGNN enables learning different representations for the same node when it appears in different rooted subgraphs, in contrast to standard GNNs where node only has one single representation at one time stamp (Eq. D. Similarly, NGNN also enables using different initial features for the same node when it appears in different rooted subgraphs. This allows to customize node's initial features based on its structural role within a rooted subgraph, as opposed to using the same initial features for node across all rooted subgraphs. For example, initial features with the distance between node B and the root-when node B is the root node, we give it an additional feature 0; and when B is k-hop neighbor of the root, we give it an additional feature k. Such feature augmentation may help better capture a node's 's structural role within a rooted subgraph. It is an exclusive advantage of NGNN and is not possible in standard GNNs.
optionally augment node B's
3.3 The representation power of NGNN
We theoretically characterize the additional expressive power of NGNN (using message passing GNNs as base GNNs) as opposed to standard message passing GNNs. We focus on the ability to discriminate regular graphs because they form an important category of graphs which standard GNNs cannot represent well. Using 1-WL or message passing GNNs, any two n-sized r-regular graphs will have the same representation, unless discriminative node features are available. In contrast, we prove that NGNN can distinguish almost all pairs of n-sized r-regular graphs regardless of node features.
5

---

Definition 2.
If the message passing (Eq. 3) and the two-level graph pooling (Eqs. 45 are all injective given input from a countable space, then the NGNN called proper.
A proper NGNN always exists due to the representation power of fully-connected neural networks used for message passing and Deep Set for graph pooling (2%]. For all pairs of graphs that 1-WL. can discriminate, there always exists proper NGNN that can also discriminate them, because two graphs discriminated by 1-WL means they must have different multisets of rooted subtrees at some height h, while rooted subtree is always included in rooted subgraph with the same height.
Now we present our main theorem.
Theorem 1. Consider all pairs of n-sized r-regular graphs, where 3 S < (2 (2logn) For any small constant e >> O. there exists a proper NGNN using at most [[ + c)
log log(r-1-e) -height rooted
subgraphs and [ (og(r---e)) -layer message passing, which distinguishes almost all (1 - o()) such pairs of graphs.
We include the proof in Appendix A. Theorem T has three implications. Firstly, since NGNN can discriminate almost all r-regular graphs where 1-WL always fails, it is strictly more powerful than 1-WL and message passing GNNs. Secondly, it implies that NGNN does not need to extract subgraphs with too large height (about 1 log
2 log (r-1) to be more powerful. Moreover, NGNN is
already powerful with very few layers, i.e., an arbitrarily small constant times log (r-1) (as few as layer). This benefit comes from the subgraph pooling (Eq, 4.. freeing us from using deep base GNNs, We further conduct simulation experiment in Appendix D to verify Theorem T testing how well NGNN discriminates r-regular graphs in practice. The results match almost perfectly with our theory.
log
Although NGNN is strictly more powerful than 1-WL. and 2-WL (1-WL and 2-W1 have the same discriminating power (2)), it unclear whether NGNN is more powerful than 3-WL.. Our early-stage analysis shows both NGNN and 3-WI. cannot discriminate strongly regular graphs with the same parameters 29
We leave the exact comparison between NGNN and 3-WL to future work.
3.4 Discussion
Base GNN. NGNN is a general plug-and-ple and-pla framework to increase the power of base GNN, For the base GNN, we are not restricted to message passing GNNs as described in Section [3.2] For example, we can also use GNNs approximating the power of higher-dimension
WL tests, such as 1-2-3-GNN 19 and PPGN/Ring- GNN 22 21). as the base GNN. In fact, one limitation of these high-order GNNs is their (n²) complexity. Using the NGNN framework we can greatly alleviate this by applying the higher-order GNN multiple small rooted subgraphs instead of the whole graph. Suppose a rooted subgraph has at most nodes, then by applying high-order GNN to all rooted subgraphs, we can reduce the time complexity from (n to Onc"))
Complexity. We compare the time complexity of NGNN (using message passing GNNs as base GNNs) with standard message passing GNN. Suppose the graph has nodes with maximum degree d, and the maximum number of nodes in a rooted subgraph is c. Each message passing iteration in a standard message passing GNN takes ((nd) operations. In NGNN, we need to perform message passing over all nodes" rooted subgraphs, which takes O(n ed). We will keep small (which can be achieved by using a small h) to improve NGNN's scalability. Additionally, small c enables the base GNN to focus on learning local subgraph patterns.
In Appendix B, we discuss some other design choices of NGNN.
4 Related work
Understanding GNN's representation power is a fundamental problem in GNN research. Xu et al. 27 and Morris et al. 19 first proved that the discriminating power of message passing GNNs is bounded by the 1-WL test, namely they cannot discriminate two non-isomorphic graphs that 1-WL fails to discriminate (such as r-regular graphs). Since then, there is increasing effort in enhancing GNN's discriminating power beyond 1-WL [19 21 20
30 24 33 25 Many GNNs have been
proposed to mimic nigher-dimensional WI. tests, such as 1-2-3-GNN 19, Ring-GNN (2 and
PPGN 200. However, these models generally require learning the representations of all node tuples

---

of certain cardinality (e.g., node pairs, node triples and so on), thus cannot leverage the sparsity of graph structure and are difficult scale to large graphs. Some works study the universality of GNNs for approximating any invariant or equivariant functions over graphs [34 21
However, tensors, which hold more theoretical value than practical applicability. Dasoulas et al. (38] propose to augment nodes of identical attributes with different colors, which requires exhausting all the coloring choices to reach universality. Similarly, Relational Pooling (RP) (30) uses the ensemble of permutation-aware functions over graphs to reach universality, which requires exhausting all n!! permutations to achieve its theoretical power. Its local version Local Relational Pooling (LRP) [9] applies RP over subgraphs around nodes, which is similar to our work yet still requires exhausting node permutations in local subgraphs and even more loses RP's theoretical power. In contrast, NGNN maintains controllable cost by only applying message passing GNN to local subgraphs, and is guaranteed to be more powerful than 1-WL..
35 37
reaching universality would require polynomial(m)-ord)
Because of the high cost of mimicking high-dimensional WL tests, several works have been proposed to increase GNN's representation power within the message passing framework. Observing that different neighbors are indistinguishable during neighbor aggregation, some works propose to add one-hot node index features or random features to GNNs [40] 41). These methods work well when nodes naturally have distinct identities irrespective of the graph structure. However, although making GNNs more discriminative, they also lose some of GNNs' generalization ability by not being able to guarantee nodes with identical neighborhoods to have the same embedding; the resulting models are also no longer permutation invariant. Repeating random initialization helps with avoiding such an issue but gets much slower convergence 42 An exception is structural message- passing (SMP) 43), which propagates one-hot node index features to learn a global n x d feature matrix for each node. The feature matrix is further pooled to learn cerrmutationiivaaiian node representation.
On the contrary, some works propose to use structural features to augment GNNs without hurting the generalization ability of GNNs. SEAL 44 45), IGMC [46] and DE 24
use distance-based
features, where a distance vector w.r.t. the target node set to predict is calculated for each node as its additional features. Our NGNN framework is naturally compatible with such distance-based features due to its independent rooted subgraph processing. GSN [1 uses the count of certain substructures to augment node/cdge features, which also surpasses 1-WL theoretically. However, GSN needs properly defined substructure set to incorporate -omaii--peccfic inductive biases, while NGNN aims to learn arbitrary substructures around nodes without the need to predefine a substructure set.
Concurrent to our work, You et al. 32 propose Identity- aware GNN (ID-GNN). ID-GNN uses different weight parameters between each root node and its context nodes during message passing. It also extracts a rooted subgraph around each node, and thus can be viewed as a special case of NGNN with: 1) the number of message passing layers equivalent to the subgraph height, 2) directly using the root node's s intermediate representation as its final representation without subgraph pooling, and 3) augmenting initial node features with 0/1 "identity"". However, the extra power of ID-GNN only comes from the "identity" feature, while the power of NGNN comes from the subgraph pooling- without using any node features, NGNN is still provably more discriminative than 1-WL. Another similar work to ours is natural graph network (NGN) (7 NGN argues that graph convolution weights need not be shared among all nodes but only (locally) isomorphic nodes. If we view distance-basee node features as refining the graph convolution weights so that nodes within a center node's neighborhood are no longer treated symmetrically, then our NGNN reduces to an NGN.
The idea of independently performing message passing within k-hop neighborhood is also explored in k-hop GNN [48] and MixHop [49. However, MixHop directly concatenates the aggregation results of neighbors at different hops as the root representation, which ignores the connections between other nodes in the rooted subgraph. k-hop GNN sequentially performs message passing for k-hop, --hop. and O-hop node (the update of (i- -)--) nodes depend on the updated states of i-hop nodes), while NGNN simultaneously performs message passing for all nodes in the subgraph thus is more parallelizable. Both MixHop and k-hop GNN directly use the root node's 's representation as its final node representation. In contrast, NGNN uses subgraph pooling to summarize all node representations within the subgraph as the final root representation, which distinguishes NGNN from other k-hop models. As Theorem shows, Ishows, the subgraph pooling enables using a much smaller number of message passing layers 1 (as small as 1) than the depth & of the subgraph, while MixHop and k-hop GNN always require 1 > k. MixHop and k-hop GNN also do not have the strong theoretical power of NGNN to discriminate r-regular graphs. Like SEAL and k-hop GNN, G-Meta (50) is another work extracting subgraphs around nodes/links. It focuses specifically on a meta- leaanle setting.
7

---

Our code is Table 1: Statistics and evaluation metrics of the QM9 and OGB datasets.
Dataset
#Graphs
Arg. #nodes
Avg. #edges
Split ratio
#Tasks
Task type
Metric
QM9
129,433
18.0
18.6
80/10/10
12
Regression
ogb1 molbiv
41,127
25.5
27.5
80/10/10
1
Classification
ROC-AU AUC
ogbl-nol poba
437,929
26.0
28.1
80/1010
128
Clussification
AP
5 Experiments
In this section, we study the effectiveness of the NGNN framework for graph classification and regression tasks. In particular, we want to answer the following questions:
Q1 Can NGNN reach its theoretical power discriminate --W--nniistinguishablle graphs?
Q2 How often and how much does NGNN improve the performance of a base GNN?
Q3 How does NGNN perform in comparison to state-of-the-arr GNN methods open benchmarks?
Q4 How much extra computation time does NGNN incur?
We implement the NGNN framework based on the PyTorch Geometric library [1]]
available at
5.1 Datasets
To answer Q1, we use simulation dataset of r-regular graphs and the EXP dataset 42 contain- ing 600 pairs of 1- WWL-indistinuuishabl but non-isomorphic graphs. To answer Q2. we use the QM9 dataset 52 5
and the TU datasets [54]. QM9 contains 130K small molecules. The task here is to perform regression on twelve targets representing energetic, electronic, geometric, and thermodynamic properties, based on the graph structure and node/edge features. TU contains five graph classification datasets including D&D [55), MUTAG (56), PROTEINS (55], PTC_MR (57). and ENZYMES [58]. We used the datasets provided by PyTorch Geometric [51]. where for QM9 we performed unit conversions to match the units used by [9]. The evaluation metric is Mean Absolute Error (MAE) for QM9 and Accuracy (%) for TU. To answer Q3, we use two Open Graph Benchmark (OGB) datasets [59], ogbg agbg-mollig molhiv and ogbg-moli molpcba.. The ogbg-moling dataset contains 41K small molecules, the task of which is to classify whether a molecule inhibits HIV virus ROC-AUC is used for evaluation. The ogbg-molpctie mol.gmmmmpcbaaaaacom dataset contains 438K molecules with 128 classification tasks. The evaluation metric is Average Precision (AP) averaged over all the tasks. We include the statistics for QM9 and OGB datasets in Table
5.2 Models
QM9. We use 1-GNN, 1-2-GNN, 1 1-3-GNN, and 1-2-3-GNN from 19 as both the baselines and the base GNNs of NGNN. Among them. 1-GNN is standard message passing GNN with 1-WL power.
1-2-GNN is GNN mimicking 2-WL, where message passing happens among 2-tuples of nodes. 1-3-GNN and 1-2-3-GNN mimic 3-WL, where message passing happens among 3-tuples nodes. 1-2-GNN and 1-3-GNN use features computed by 1 I-GNN as initial node features, and 1-2-3-GNN uses the concatenated features from 1-2-GNN and 1-3-GNN. We additionally include numbers provided by [53] and Deep LRP (39 as baselines. Note that we omit more recent methods [60|62] using advanced physical representations calculated from angles, atom coordinates, and quantum mechanics, which may obscure the comparison of models' pure graph representation power. For NGNN, we uniformly use height-3 rooted subgraphs. For a fair comparison, the base GNNs NGNN use exactly the same hyperparameters as when they are used alone, except for I-GNN where we increase the number of message passing layers from 3 to 5 to make the number of layers larger than the subgraph height, similar to (63). For subgraph pooling and graph pooling layers, we uniformly use mean pooling. All other settings follow [19].
TU. We use four widely adopted GNNs as the baselines and the base GNNs of NGNN: GCN [12] GraphSAGE (64) GIN (27) and GAT [15]. Since TU datasets suffer from inconsistent evaluation standards [65] we uniformly use the 10-fold cross validation framework provided by Py Torch
Geomtric (66) for all the models to ensure a fair comparison. For GNNs, we search the number of message passing layers in
(2.3 3, 4,53. For NGNNs, we similarly search the subgraph height h in (2,3, 3, 4, 5). so that both NGNNs and GNNs can have equal-depth local receptive fields. For NGNNs, we always use h + message passing layers instead of searching together with h, because that will
8

---

OGB. We use GNNs achieving top places on the OGB graph classification leaderboard (at the time of submission) as the baselines, including GCN [12], GIN [27], DeeperGCN [67]. Deep LRP (39] make NGNNs have more hyperparameters to tune. All models have 32 hidden dimensions, and are trained for 100 epochs with batch size of 128. For each fold, we record the test accuracy with the hyperparameters chosen based on the hest validation performance of this fold. Finally, we report the average test accuracy across all the 10 folds.
F
PNA [68], DGN [33 GINE [69] and PHC-GNN 70 Note that those high-order GNNs 2 25
are not included here, because despite being theoretically more discriminative, these GNNs are not among the GNNs with the best empirical performance on modern auree-ccal graph benchmarks, and their (n²)) complexity also raises a scalability issue. For NGNN, we use GIN as the base GNN (although GIN is not among the strongest baselines here). Some baselines additionally use the virtual node technique [8 11 71), which are marked by "** For NGNN, we search the subgraph height h in [3, 4, 5). and the number of layers in {4, 6}. We train the NGNN models for 100 and 150 epochs for ogbg- agbg-molhiv and
respectively, and report the validation and test scores at the best validation epoch. We also find that our models are subject to high performance variance across epochs, likely due to the increased expressiveness. Thus, we save a model checkpoint every 10 epochs, and additionally report the ensemble performance by averaging the predictions from all checkpoints. The final hyperparameter choices and more details about the experimental settings are included in Appendix C. All results are averaged over 10 independent runs.
In the following, we uniformly use "Nested GNN" to denote an NGNN model using "GNN" as the base GNN. For example, Nested GIN denotes an NGNN model using GIN (27 as the base GNN. For the NGNN models in QM9, TU and OGB datasets, we augment the initial features of node with Distance Encoding (DE) 24. which uses the (generalized) distance between a node and the root as its additional feature, due to DE's successful applications in link-level tasks [44 466) Note that such feature augmentation is not applicable to the baseline models as discussed in Section 3.2 An ablation study on the effects of the DE features is included in Appendix E.
5.3 Results and discussion
To answer Q1, we first run simulation to test NGNN's power for discriminating r-regular graphs. The results are presented in Appendix D. They match almost perfectly with Theorem [T] demonstrating that practical NGNN can fulfil its theoretical power for discriminating r-regular graphs.
We also test NGNN's expressive power using the EXP dataset pro- vided by 42), which contains 600 carefully constructed 1-WL in- distinguishable but non-isomorphic graph pairs. Each pair of graphs have different labels, thus standard message passing GNN cannot predict them both correctly, resulting in an expected classification accuracy of only 50%. We exactly follow the experimental settings and copy the baseline results in (42). In Table [ our Nested GIN model achieves 99.9% classification accuracy, which outperforms all the baselines and distinguishes almost all the 1-WL indistinguishable graph pairs. These results verified that NGNN's expressive power is indeed beyond 1-WL and message passing GNNs.
Table Results (%) EXP.
Method
Test Accuracy
GCN-RNI 52
98.0=11.85
PPGN 20
50.0++0.00
1-2-3-GNN
50.0.10.00
3-GCN 42
99.7=0.004
Nested GIN
99.9+10.26
To answer Q2, we adopt the QM9 and TU datasets. We show the QM9 results Table the Nested version of base GNN achieves a better result than the base GNN itself, we color that cell with light green. As we can see, NGNN brings performance gains to all base GNNs on most targets, sometimes by large margins. We also show the results on TU in Table 4 NGNNs also show improvement over their base GNNs in most cases. These results indicate that NGNN is a general framework for improving a GNN's power. We further compute the maximum reduction of MAE for QM9 and maximum improvement of accuracy for TU before and after applying NGNN. NGNN reduces the MAE by up to 7.9 times for QM9, and increases the accuracy by up to 14.3% for TU. These results answer Q2, indicating that NGNN can bring steady and significant improvement to base GNNs.
To answer Q3, we compare Nested GIN with leading methods on the OGB leaderboard. The results are shown in Table 5 Nested GIN achieves highly competitive performance with these leading GNN models, albeit using relatively weak base GNN (GIN). Compared to GIN alone, Nested GIN shows clear performance gains. It achieves test scores up to 79.86 and 30.07 on ogbg- ogbg-molhit movhiv and

---

Table 3: MAE results QM9 (smaller the better). A colored cell means NGNN better than the base GNN.
Target
Method (Ne for Nevied)
DINN
MPNN
Deep LRP
I-GNN
1-2-GNN
1.3GNN
1-2-3-GNN
NNo. I-GNN
Nr. 1-26GNN
Nr. 1-4GNN
No. I-2-1-GNN
Max, redortion
0.264
0.334
0.364
0.493
0.493
0.473
0.476
0.425
0.437
0.446
0:433
1.2x
0.95
0.89
0.298
0.78
0.27
0.46
0.27
0.29
0.278
0.261
0.265
2.7%
0.00385
0108541
0J00254
006321
0/0531
0.00228
0.00337
0.00265
0.00275
0
0,00279
1.2x
0,00512
0.00623
0.00277
000355
000350
0.00354
0.00351
0,00297
0.00271
0,00269
0,00276
1,xx
&r
0.0112
0,0056
0,00353
0.0099
0.0047
0,0046
0.0048
0.0038
0.0039
0.00.9
0,0039
1.8x
(R9))
17.0
28.5
19.3
34.1
21.5
25.8
22.9
30.5
30.4
20.2
20
1.7%
ZPVE
0.00172
0,00216
0.00055
0.01144
0.0018
0,00064
0100019
0.06120
0.00017
0.00011
0.00015
6.2%
2:43
2,05
0.413
2.32
0.0357
0.6855
0.0627
0.295
0.252
0.291
0.205
7,9
2.43
2,00
0.413
2.08
0,107
0.686
0.111
0.361
0.265
0:276
0.200
5.8%
2.43
0.413
0.070
0.79%
0.311
0.241
0.267
0.249
7.3%
2.43
0.413
0.587
0,0469
0.489
0.272
0.287
0,253
4,0%
0.27
0.129
0.158
0.174
0.0891
0.0679
0,0811
1.8%
Tahle 4: Accuracy results (5) on TU datasets.
Table Results (%) on OGB datasets (# virtual node).
D&D
MUTAG
PROTEINS
PTC MR
ENZYMES
oglg- molhii (AUC)
ogog ogpg-oolpcba(AP)
&Ciroghs
1178
188
1113
344
600
Method
Vilisiation
Validaion
Text
Aog. Anodes
284.32
17.95
29.06
14.29
32,63
CCN*
83.84100
75 75.991111
24 14441
24 24 10.54
GCN
716622
73.42105
71.76477
56.477.1
27.3255
GIN-
84, 84.7010.80
32.6711400
27.981025
27 10.03:1025
GraphSAGE
7166330
74.0=88
71.2-5.1
57.0
30,726.
Deep LRP
82.0911.16
77.1911.40
GIN
70.5339
$4.5289
70A5443
51.26992
38,326.4
DeepeeGUN*
29. 20:2::5
21
GAT
71.0144
73943161
72.0
$7.067.3
30.264.2
HIMP
18 78:80-0 87
PNA
85.19:0000
79.0521.32
Nested GCN
Nosted GraphSAGE
774444
76.3833
83.9:101
62.9.1111
73.3640
74.2-11
57.367.7
57.0559
30.786.5
31.2667
DGN
GINE
84.7025147
79, 0000
30 30.65=2.330
29 17:0.15
Nested GIN
77/8:39
57,9=82
73.9=5.1
54.123.7
29.0=8.0
PHC-CNN
82.1710099
79 79.3411.16
10:25
Nested GAT
76.054.4
61.9:1022
73.7648
56.765.
29.525.7
Nested
83.17e1.99
78.34+1
29 10.155-0.5
32-044441
Max. improvement
10.45
13.4%
4.7%
5.7%
14.3%
GIN*
M007
ogbg-molpeba, respectively, which outperform all the baselines. In partieular, for the challenging ogbg-molpcba, our Nested GIN can achieve 30.07 and 28.32 test AP with and without ensemble, respectively, outperforming the plain GIN model (with 27.03 test AP) significantly. These results demonstrate the great empirical performance and potential of NGNN even compared to heavily tuned open leaderboard models, despite using only GIN as the base GNN.
To answer Q4, we report the training time per epoch for GIN and Nested GIN on OGB datasets. On ogbg-molhiv, GIN takes 54s per epoch, while Nested GIN takes 183s. On agbg-molpcter GIN takes 10min per epoch, while Nested GIN takes 20min. This verifies that NGNN has comparable time complexity with message passing GNNs. The extra complexity comes from independently learning better node representations from rooted subgraphs, which is a trade-off for the higher expressivity.
In summary, experiments have firmly shown that NGNN is a theoretically sound method which brings consistent gains to its base GNNs in a plug-and-play way. Furthermore, NGNN still maintains a controllable time complexity compared to other more powerful GNNs.
Finally, we point out one memory limitation of the current NGNN implementation. Currently, NGNN does not scale to graph datasets with a large average node number (such as REDDIT-BINARY) or datasets with a large average node degree (such as ogbg-ppa due to copying a rooted subgraph for each node to the GPU memory. Reducing batch size or subgraph height helps, but at the same time leads to performance degradation. One may wonder why materializing all the subgraphs into GPU memory is necessary. The reason is that we want to sitch-process all the subgraphs simultaneously. Otherwise, we have to sequentially extract subgraphs on the fly, which results in a much higher latency. We leave the exploration of memory efficient NGNN to the future work.
6 Conclusions
We have proposed Nested Graph Neural Network (NGNN), a general framework for improving GNN's 'ss representation power. NGNN learns node representations encoding rooted subgraphs instead of rooted subtrees. Theoretically, we prove NGNN can discriminate almost all r-regular graphs where 1-WL. always fails. Empirically, NGNN consistently improves the performance of various base GNNs across different datasets without incurring the (n²3) complexity like other more powerful GNNs.
Acknowledge
The authors greatly thank the actionable suggestions from the reviewers to improve the manuscript. Li is partly supported by the 2021 JP Morgan Faculty Award and the National Science Foundation (NSF) award HDR-2117997
10

---

References
[1] Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference Knowledge discovery and data mining, pages 701-710. ACM, 2014.
[2] David Haussler. Convolution kernels on discrete structures. Technical report, Citeseer, 1999.
[3] Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M Borgwardt. Efficient graphlet kernels for large graph comparison. In AISTATS, volume 5, pages 488-495. 2009.
[4] Risi Kondor, Nino Shervashidze, and Karsten M Borgwardt. The graphlet spectrum. In Proceedings of the 26th Annual International Conference on Machine Learning, pages 529-536.
ACM, 2009.
[5] Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-patt kernels on graphs. In Sth IEEE International Conference on Data Mining, pages 8-pp. IEEE, 2005.
[6] Marion Neumann, Roman Gameett Christian Bauckhage, and Kristian Kersting, Propagation kernels: efficient graph kernels from propagated information. Machine Learning, 102(2): 209-245, 2016.
[7] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lemman graph kernels. Journal of Machine Learning Research, 12(Sep): 2539-2561 2011.
[8] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20( 20(1):61-80, 2009.
(9] Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint arXiv: 6203, 2013.
[10] David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In Advances in neural information processing systems, pages 2224- 2232, 2015.
[11] Yujia Li, Daniel Tarlow, Marc Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprint arXiv:1511.05499, 2015.
[12] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: /w/66/6999000.0 2016.
[13] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pages 3837-3845, 2016.
[14] Hanjun Dai, Bo Dai, and Le Song. Discriminative embeddings of latent variable models for structured data. In Proceedings of The 33rd International Conference on Machine Learning. pages 2702-2711, 2016.
[15] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 17 10903, 2017.
[16] Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In AAAI, pages 4438 4445, 2018
[17) Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Advances Neural Information Processing Systems, pages 1800-4810 10, 2018.
[18] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 1263-1272. JMLR. org, 2017.

---

[19] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602-4609, 2019.
[20] Haggai Maron, Heli Ben- Hem-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, pages 2156-2167, 2019.
[21] Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. In Advances in Neural Information Processing Systems, pages 15894-15902, 2019.
[22] Boris Weisfeiler and AA Lehman. A reduction of graph to canonical form and an algebra arising during this reduction. Nauchno-Techmichhskkyy Informatsia, 2(9):12-16, 1968.
[23] S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, [(AAr)):201-122) 2010.
[24] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding- provably more powerful gnns for structural representation learning. arXiv preprini arXivv2009.00142, 2020.
[25] Christopher Morris, Gaurav Rattan, and Petra Mutzel, Weisfeiler and leman go sparse: Towards scalable higher-order graph embeddings. 2020.
[26] Muhan Zhang and Yixin Chen. Weisfeiler-lemman neural machine for link prediction. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 575-583, ACM, 2017.
[27] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint 18X0v:1810.0000
2018
[28] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems, pages 3391-3401, 2017.
[29] Andries E Brouwer and Willem H Haemers. Strongly regular graphs. In Spectra of Graphs, pages 115-149. Springer, 2012.
[30] Ryan Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational pooling for graph representations. In International Conference on Machine Learning, pages 4663-4673, PMLR, 2019.
[31] Giorgos Bouritsas, Fabrizio Frasca, Stefanos Zafeiriou, and Michael M Bronstein. Improv- ing graph neural network expressivity via subgraph isomorphism counting. arXiv preprint arXiv:2006.09252, 2020.
[32] Jiaxuan You, Jonathan Gomes-Selman, Rex Ying, and Jure Leskovec. Identity-aware graph neural networks. arXiv preprint arXiv:2101.10320, 2021.
[33] Dominique Beaini, Saro Passaro, Vincent Létournaa, William L Hamilton, Gabriele Corso, and Pietro Liò. Directional graph networks. arXiv preprint arXiv:2010.02863, 2020.
[34] Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. arXiv preprint 1rXiv:1812.099002.2000 2018.
[35] Haggai Maron, Ethan Fetaya, Nimrod Segol, and Yaron Lipman. On the universality of invariant networks. In International conference on machine learning, pages 4363-4371. PMLL 2019.
[36] Nicolas Keriven and Gabriel Peyré. Universal invariant and equivariant graph neural networks arXiv preprint arXiv: 049.04 2019.
[37] Waiss Azizian and Mare Lelarge. Characterizing the expressive power of invariant and equivari- ant graph neural networks. arXiv preprint 15X1: 2020.
12

---

[38] George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation. arXiv preprint arXiv:1912.06058, 2019.
[39] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 2020.
[40] Andreas Loukas. What graph neural networks cannot learn: depth vs width. arXiv preprint 1900v09907.003 2019.
[41] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks. arXiv preprint arXiv:2002.03/55. 2020.
[42] Ralph Abboud, ismail Ilkan Ceylan, Martin Grohe, and Thomas Lukasiewicz. The sur- prising power of graph neural networks with random node initialization. arXiv preprint arXiv:2010.01177 179, 2020.
[43] Clément Vignac, Andreas Loukas, and Pascal Frossard. Building powerful and equivariant graph neural networks with structural message-passing. arXiv e-prints, pages arXiv-2006, 2020.
[44] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Advances in Neural Information P Processing Systems, pages 51 5165-5175, 2018.
[45] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Revisiting graph neural networks for link prediction. arXiv preprint arXiv:2010.16103, 2020.
[46] Muhan Zhang and Yixin Chen. Inductive matrix completion based on graph neural networks. In International Conference on Learning Representations, 2020. URL //opnrreiee sett/torum'iid-Byxxxee
[47] Pim de Haan, Taco Cohen, and Max Welling. Natural graph networks. arXiv preprint arXiv:2007.08349, 2020.
[48] Giannis Nikolentzos, George Dasoulas, and Michalis Vazirgiannis. k-hop graph neural networks. Neural Networks, 130:195-2000 205, 2020.
[49] 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. In international conference on machine learning, pages 21 21-29. PMLR, 2019.
[50] Kexin Huang and Marinka Zitnik. Graph meta learning via local subgraphs. Advances in Neural Information Processing Systems, 33, 2020.
[51] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. arXiv preprint arXiv: 100::0003302220 2019.
[52] Raghunathan Ramakrishnan, Pavlo O Dral, Matthias Rupp, and O Anatole Von Lilienfeld. Quantum chemistry structures and properties of 134 kilo molecules. Scientific data, 1(1):1-7, 2014.
[53] Zhenqin WU, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S Pappu, Karl Leswing, and Vijay Pande. Moleculenet: a benchmark for molecular machine learning. Chemical science, 9()):133-330 2018.
[54] Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neu- mann. Benchmark data sets for graph kernels, 2016. URL http:://rrapkernell...
tu tu-dortmund.de
[55] Paul Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771-78,, 2003.
13

---

[56] Asim Kumar Debnath, de Compadre RL Lopez, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-777, 1991.
[57] Hannu Toivonen, Ashwin Srinivasan, Ross D King, Stefan Kramer, and Christoph Helma. Statistical evaluation of the predictive toxicology challenge 2000-2001. Bioinformatics, 19(10): 1183-1193, 2003.
[58] Ida Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Dietmar Schomburg. Brenda, the enzyme database: updates and major new developments. Nucleic acids research, 32(suppL_1:D4431-D
2004.
[59] 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. arXiv preprint arXiv:2005.00687, 2020.
[60] Brandon Anderson, Truong-Son Hy, and Risi Kondor. Cormorant: Covariant molecular neural networks. arXiv preprint 1906,00000 2019.
[61] Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional message passing for molecular graphs. arXiv preprint arXiv:2003.03123 2020.
[62] Zhuoran Qiao, Matthew Welborn, Animashree Anandkumar, Frederick Manby, and Thomas F Miller III. Orbnet: Deep learning for quantum chemistry using comeetr--adateer atomic-orbital features. The Journal of Chemical Physics, 153(12):12411122 2020.
[63] Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Deep graph neural networks with shallow subgraph samplers. arXiv preprint arXiv:2012.01380 2020.
[64] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pages 1025-1035, 2017.
[65] Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. arXiv preprint 1rXiv:192..09893 2019.
[66] Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
[67] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens. arXiv preprint arXiv:2006.07739 2020.
[68] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liō, and Petar Veličkovié. Principal neighbourhood aggregation for graph nets. arXiv preprint arXiv:2004.0577 200.00500., 05718, 2020.
[69] Rémy Brossard, Oriel Frigo, and David Dehaene. Graph convolutions that can finally model local structure. arXiv preprint arXiv:201 1ttiv:20//1/50663 15069, 2020.
[70] Tuan Le, Marco Bertolini, Frank Noé, and Djork-Ari Amné Clevert. Parameterized hypercomplex graph neural networks for graph classification. arXiv preprint 2XXi:22003.1688,, 2021.
[71] Katsuhiko Ishiguro, Shin-ichi Maeda, and Masanori Koyama. Graph warp module: an auxiliary module for boosting the power of graph neural networks. arXiv preprint 190iv1992.011222 2019.
[72] Hongyang Gao and Shuiwang Ji. Graph u-nets. arXiv preprint 1eXiv:1905.05// 2019.
[73] Douglas Klein and Milan Randić. Resistance distance. Journal of Mathematical Chemistry, 12(1):81-9)) 1993.
14


Reviews:
[{"review_id": "ca6p3Rj8J0x", "reviewer": "Reviewer_6fjM", "summary": "This paper proposes a new architecture to strengthen message passing GNNs. Since the weaknesses of GNNs usually come from  the unidentifability of nodes, the authors suggest to first preprocess given graphs and add each node a new initial attribute, and then apply the outer GNN. The new node attributes come from another message passing GNN (called based GNN) applied to a subgraph of a certain depth (or height according to the paper's terminology) around each node. Then they prove that the new architecture can distinguish regular graphs with probability $1-o(1)$ (over the choice of a random regular graph), and so the new model is more expressive than MPNNs, since MPNNs can't. They finally evaluate their model in various settings.  \n\nFor me the contributions of the paper are: (1) proposing nested GNNs (NGNNs); (2) showing that NGNNs can distinguish almost all regular graphs; (3) and evaluating the new model through various experiments. ", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "\nStrengths: \n\n(1) The paper is really easy to understand. I could understand the manuscript at the first read. \n\n(2) They supported their theory with nice experiments. \n\n(3) The new theoretical result is of potential interest to the graph learning community since it provides significant contribution to the problem of learning regular graphs.\n\nWeaknesses/comments/questions:\n\n(0) A number of important previous works are missing. For example, in the context of counting substructures, people also considered strengthening GNNs with subgraph pooling [1]. In [1] the authors consider a similar setting where MPNNs are strengthened with pooling on a neighborhood around each node (similar idea), and instead of having base GNN, they consider Relational Pooling (RP). Please provide explanations why/how your paper is different from theirs, and compare the results (also see [4,5]). \nAlso, if  we have random node IDs, then GNNs can approximate any functions (e.g., see [2]). So you need to also mention those papers in your paper and explain what is your contribution. The bound you get for the complexity is also a special case of what is appeared in a preprint [3]. The referred  papers below are only examples and you can find more related papers by tracking these examples (and references therein). However, I haven't seen your theorem on distinguishing regular graphs in any previous papers, so the paper contributes on the problem of learning with regular graphs. I suggest to rewrite some parts of the paper and mention that you essentially have an original theoretical result on learning with regular graphs, and also explain/discuss/mention all the related works.  I believe the paper has good contributions, but it is still vague how it is related to the previous works, it has missing references (just I provided a few examples below), and extensive revision is required.\n\n [1] Chen, Zhengdao, et al. \"Can graph neural networks count substructures?.\" arXiv preprint arXiv:2002.04025 (2020).\n \n [2] Abboud, Ralph, et al. \"The surprising power of graph neural networks with random node initialization.\" arXiv preprint arXiv:2010.01179 (2020).\n\n[3] Tahmasebi, Behrooz, and Stefanie Jegelka. \"Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Results.\" arXiv preprint arXiv:2012.03174 (2020).\n\n[4] Lou, Zhaoyu, et al. \"Neural Subgraph Matching.\" arXiv preprint arXiv:2007.03092 (2020).\n\n[5] Ying, Rex, et al. \"Hierarchical graph representation learning with differentiable pooling.\" arXiv preprint arXiv:1806.08804 (2018).\n\n(1) The lack of detailed motivation behind the theorem: since your theorem just concerns regular graphs, there should be a reasonable motivation for why we need to  do classification/regression on regular graphs (please provide examples that regular graphs arise, like in molecules, etc.).\n\n(2) I think if the given graphs are strongly regular, then the model fails to distinguish them. Is it true? Please provide more discussion about this fact right after the main theorem because it could help the reader and it's also related to the future works.\n\n\n(3) The proposed method is a feature augmentation trick, however, I couldn't find any literature review on that topic in the related works section. Please add related papers and also discuss how your model is different from theirs. \n\n\n\n(4) While the main body of the paper is quite understandable, the appendix is not. Specially, the proof of your main theorem is not clear at all. There is a reference  to a prior work which is not clear to me unless I read the reference. Can you add a few sentences about steps 1-3 in appendix (line 637) to make the proof more readable?  There is no page restriction for the appendix.\n\n\n\n(5) In Equation 3, are the functions $U_t,M_t$ shared among nodes? Or each node has its specific function? I guess they share, but it is not so clear in the paper. \n\n\n(6) Figure 2 is great for understanding your model. Can put it earlier in the paper and give more references to it within the text?\n\n(5) Line (229): I guess $O(cn^3)$ --> $O(cn^2)$.\n\n(6) In the main theorem, can we have $\\epsilon \\to 0$, so we only need one layer message passing? How does the distinguishing error in Theorem 1 (i.e., the term $1-o(1)$) depend on $\\epsilon,n,r,...$? I believe one important question is the term $o(1)$ in your proof. Can you quantify that in your theorem?    Please quantify the dependence of the $o(1)$ bound in your result to $\\epsilon,n,r$ to allow comparison and help readers.  Also, please provide a few sentences as proof sketch right after the main result.\n\n\n(7) I cannot understand why the new algorithm increase the computational load just by a constant? Do you mean $c$ in line 229 is $O(1)$? In your setting with regular graphs, we could even have $c = r^h = O(n^{0.5})$ if we apply those $r,h$ in Theorem 1.  Is it true? Hence, your algorithm does not always increase the computational load by a constant factor. It can grow with $n$. Please clearly mention in in the paper.  \n\n --------------------------------\n\nAfter rebuttal:\n\nThe authors mostly agreed on the comments, and explained some of them, but to me some of the questions are still unanswered, or it is still not clear what exactly do they want to add to the paper after revision. I decided to keep my rating.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "10"}, "extra_text": {}}, {"review_id": "U7idf04taBa", "reviewer": "Reviewer_etFC", "summary": "This paper introduces Nested Graph Neural Networks (NGNNs), a novel kind of graph neural network that overcomes the limitations of typical message passing approaches by representing each node as a function of its nested subgraph, rather than its nested subtree. \nThe result is a model provably more expressive than 1-WL and 2-WL, at the cost of a constant increase in computational complexity (although this has practical limitations, as the authors point out).\n\nNGNN works on two levels: \n\n1. A \"base GNN\" is used to compute representations for each node, applying the GNN to the nested subgraph around the node and eventually pooling the subgraph to obtain the representation. \n\n2. An \"outer GNN\" processes the resulting graph to obtain the final node representations, and a global pooling is optionally applied to get graph-level embeddings. \n\nTherefore, NGNN can surpass 1-WL expressivity using only standard message-passing GNNs, making it very convenient and more computationally efficient than previous higher-order GNN variants. \n\nThe authors prove the expressive power of NGNN in distinguishing n-sized r-regular graphs. \n\nThe paper concludes with a thorough experimental analysis of NGNN on several benchmarks of graph classification and regression: QM9, ogb-molhiv, ogb-molpcba, and some TU datasets. \nThe method achieves state-of-the-art performance on ogb-molpcba and several QM9 subtasks. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "**Originality**: the method is novel and smartly combines existing techniques, achieving impressive results. The work is contextualized well w.r.t. previous literature and highlights the similarities and advantages of NGNN.\n\n**Quality**: the paper is technically sound. The claims are clearly stated at the beginning of the paper and methodically verified, with relevant proofs delegated to the Appendix. The goals of the experiments section are also clearly listed (which is something that one rarely sees in papers of this kind) and there is a final discussion that relates the results to the research questions. \nThe limitations of NGNN are discussed openly: \n\n1. it is unclear whether NGNN is more powerful than 3-WL;\n2. NGNN can only be used on graphs with up to 400 nodes on average, due to the memory limitations of GPUs.\n\n**Clarity**: the paper is well written and organized. I have found only one minor typo: the comma after \"because\" on line 43 should be removed. \nA few more details on how to extract subgraphs, in practice, would be needed to reproduce the results only from the paper, although this is only for the reader's convenience. All other experimental details are clearly described. \n\n**Significance**: typical message-passing GNNs have significant limitations in terms of expressivity, and much of the research in the field is dedicated to designing more expressive GNNs. Most methods, however, resort to very expensive solutions (up to $O(n^3)$ complexity) which make them poorly applicable in real scenarios. NGNN overcomes the limitations of both message-passing GNNs and higher-order approaches. I can see how this paper could have a positive impact on the GNN community. \nAlso, the method proposed achieves the state of the art on a significant benchmark (ogb-molpcba) through a novel approach, which is an important result. \nHowever, the other experimental results could be stronger and I ask the authors to comment on the points that I raise below, regarding the selection of baselines and the choice of datasets. \n\n**Comments**: I have a few comments to strengthen the paper\n\n- As a subjective observation, the description of the rationale for subgraph pooling in lines 69-76 could be more clear, as Figure 1 doesn't do a good job of showing the differences between how subtrees and subgraphs are constructed. One objection that at first comes to mind is that the base GNN is still working on subtrees, and the figure should show more clearly how this is, in fact, not the case (e.g., by coloring the nodes to make the differences more visually striking). \nSince this is the core of the method, more effort should also be spent on its explanation in the text. \n\n- How is subgraph extraction implemented in practice? The paper should describe more clearly why it is necessary to \"materialize\" the subgraphs in GPU memory, since it is the most evident shortcoming of NGNN. This would allow readers to understand the problem better and possibly come up with solutions. \n\n- For OGB, how were the baselines selected? \nThe top-4 best results on ogb-molhiv are above 0.8 ROC-AUC, while all baselines here are below 0.8, making NGNN the best method due to this selection bias. \n\n- The claimed improvements in performance on the TU datasets are often statistically insignificant (e.g., standard deviations up to 11.6 on MUTAG) and not very informative. \nSince all graphs in OGB's graph-property prediction tasks are within the limit of 400 nodes on average, why didn't the authors consider ogb-ppa and ogb-code2 instead of TU?\n\n- The code for experiments was not included in the supplementary material with the submission. It is important that the code is made available to reviewers prior to the final AC decision regarding this paper. \n\n---\n**After rebuttal**\n\nMy initial comments were minor and the authors have addressed most of them. Some issues remain about the computational complexity of the method, as also confirmed by the authors. \n\nMy rating remains unchanged. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The limitations of the work are adequately addressed.\nThe paper is unlikely to have a negative societal impact. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "TAgvmsY5QJ4", "reviewer": "Reviewer_5zao", "summary": "This paper presents a framework that applies GNN to subgraphs around each node independently to enhance node representations, followed by a global pooling layer to get graph-level embedding. The framework can be applied to any GNNs. The paper also demonstrates it's relative improvement over several real-world datasets, although the improvement seems marginal. From theoretical side, the paper proved formally that this framework can distinguish k-regular graphs where most traditional message passing based neural network cannot. ", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1. Originality: the idea of making use of subgraph to encode a better node representation is not new. In fact there some very similar papers that haven't been mentioned, and the architecture is exactly the same to their models except that the model mentioned in this paper can use any GNNs. One paper I remember is G-meta[1]. Please refer to their papers in detail and discuss the difference in terms of model architecture. The ability of using any type of GNNs seems a natural extension of their models. All in all the novelty is not enough considering the idea has been explored before. \n\n2. Quality: the architecture and the subgraph information is solid to me. Including more information from subgraph can outperform original 1-hop based message passing model. However the information provided in experiment section is not complete. The hyperparameter tuning is not very clear to me, whether the number shown in the paper follows a fair evaluation should be stated clearly and also by providing a link to their code to check. \n\n3. Clarity: the paper in general is well-written. The only part that is not clear to me is the \"outer-GNN\" mentioned in the paper. From my understanding the outer part is just a global pooling instead of a GNN model. Please explain this part clearly and if you only use a global pooling layer, please don't use the name \"outer-GNN\", instead use \"global pooling\" stage directly.  \n\n4. Significance: The result is kind of questionable from my end. \n\nFirst, the TUDataset result is very different from the result in GIN paper, where GIN model has a lot better performance than the one shown in the paper. Maybe the experiment configuration is different. However, the paper mentioned that  \"we uniformly use 4 message passing layers with 32 hidden dimensions each for all models\" and \"For NGNN, we uniformly use height-3 rooted subgraphs with mean pooling\". This part sounds to me an unfair evaluation between NGNN and GNN models. I would question whether expand the pool of hyperparameter search will increase performance of GNN and decrease the performance of NGNN, as NGNN suffers more from overfitting than GNN. I suggest the author clearly state the pool of hyperparameters and provide a link to their code to have a look. \n\nSecond, the performance on molhiv and molpcba is also questionable. Comparing GIN and Nested-GIN I do see a 1% performance improvement, however the performance of Nested-GIN is not high enough comparing with other more recent baselines. This question whether Nesting GNN is the correct way to improve expressiveness and real-world performance. The ensemble result is not attractive to me, as this is not a fair evaluation to other methods. In face the author should present other models' ensemble results. On the other perspective, the large variance of the result shows the unstable training of nested GNN. The experiment section needs a huge improvement and fair evaluation. \n\n\n[1] Graph Meta Learning via Local Subgraphs.  https://arxiv.org/pdf/2006.07889.pdf ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Not applicable. ", "review_text": "", "extra_scores": {"ethical_concerns": "Not applicable. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "RfXVvF4Fj5u", "reviewer": "Reviewer_MGt6", "summary": "This paper proposes Nested GNN, which encodes each node based on the subgraph rather than the subtree (as what GNN does) around it. The main difference between NGNN and GNN is that subgraph captures more information than the subtree, such as the interactions between a node's neighbors. The whole-graph representation can be pooled from each node representation, and can be applied in tasks such as graph classification. From theoretical perspective, this paper studies the limitations of expressive power of GNN and show that NGNN is more powerful. The proposed method shows good performance on multiple datasets. ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper studies the limitation of expressive power of GNN and proposes NGNN, which encodes each nodes representation based on the subgraph rather than the subtree around it. The point and the case study of when GNN would fail is valid, and the proposed method seems to perform well and is shown can discriminate r-regular graphs. I am a bit concerned about the novelty of the method since the first step (base GNN) seems to be just a way to learn each node representation (within the subgraph, while GNN learn it within the whole graph), and the second step is a standard graph pooling. I also have the following questions that hope the author could address:\n\n1. Do you have any guidance on choosing the subgraph height at the base GNN step? I noticed the current experiment uniformly select height = 3, I think this is a parameter that should be related with the graph size or could be tuned in a principled way. \n\n2. The main concern is about the computational cost (also mentioned in the limitation section). I noticed that the average size of graphs in the datasets are relatively small. Have you tried or implemented the base GNN step in parallel? Also, related the first question, if your graph size is small, then extracting a height-3 subgraph rooted in a node would not have too much difference with the whole graph. Would be interesting to see the performance on graph with larger size, \n\n3. The base GNN layers allow a node (v) to have different representations within difference rooted subgraphs (call the root u), which I view it as a \"contextual\" representation of node v. Currently the method uses the contextual representation of v to pool the representation of the rooted node u. Besides that, could you make use of the contextual representation of v in different rooted subgraph in other ways, for example to encode v itself when it is the root?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "My concern about the this method is the computational cost. It applies base GNN for subgraph around each node, meanwhile the classical GNN learns node representation in a one-pass fashion. The authors mentions such limitation as in their Section 5.3, that NGNN does not scale to graph datasets with average node number > 400. I am wondering could you perform the base GNN step for all nodes in parallel, since extracting subgraph and train GNN on it should be independent for each node, ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "LtKFxjvLmaz", "reviewer": "Reviewer_k3Ci", "summary": "Since GNNs based on rooted subtrees are known with limited expressive power, this paper proposes to represent nodes with their rooted subgraphs. Its expressive power with respect to graph isomorphism testing is proven beyond 2-WL. Such a method is compatible to plug into popular GNNs to enhance their representation power. Enhanced GNNs show strong performances on graph classification and regression tasks.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper proposes an interesting method to define message passing on rooted subgraph, different from rooted subtrees. It is compatible with popular base GNNs. The method proves to go beyond 2-WL w.r.t. graph isomorphism testing. Real-world graph classification and regression tasks are conducted. It also presents necessary ablation study along with a synthetic experiment. This paper is well written. \n\nPros:\n\n1. different from rooted subtrees and higher-order structures, this paper designs a more expressive gnn with easy-to-follow rooted subgraphs.\n2. the proposed method is compatible to plug into popular but weaker GNNs and results in a guaranteed boost of expressive power. Extra computation time it incurs is reasonable.\n3. distance encoding is natural in the NGNN framework as feature augmentation bringing excellent results.\n4. weaker GNNs enjoy impressive performance boosts in real-world experiments.\n5. the synthetic experiment in Appendix C confirms the theoretical result.\n\nConcerns:\n\n1. it would be better to try NGNNs on the ZINC dataset, where many popular papers proposing novel models present their results these days. It will bring more impact for this paper.\n2. where is the sentence ''our initial analysis...'' in line 220 pointing to?\n3. ablation study of distance encoding on graph classification tasks is missing. It is not sure whether the gain is from distance encoding or rooted subgraphs.\n\nI suggest an accepting score.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes a way to overcome some of the known expressivity issues of permutation invariant message-passing GNN. It does so by learning node features by applying a GNN on a subgraph around each node.

The reviewers agreed that the paper is well written and that it makes an interesting theoretical contribution. Moreover, the empirical evaluation (taking also into account the results presented during the rebuttal period) demonstrates that the proposed architecture can bring practical benefits in terms of accuracy. The main catch seems to be that the computational/memory complexity of the proposed method might be prohibitive for large graphs.

The reviewers were divided in their evaluations. The main issue expressed was that the proposed idea is not surprising given the literature and that a thorough discussion of relevant works was missing from the submitted paper. Even though these concerns are justified, it seems that the specific idea proposed has not been considered/tested before. Moreover, the authors acknowledged and explained the connections to previous works in the rebuttal period. Thus, I don't see an issue with accepting the work under the condition that the camera-ready version is updated appropriately.
Decision: Accept (Poster)