  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.
