Nested Graph Neural Networks

Muhan Zhang, Pan Li

TL;DR

Nested Graph Neural Networks (NGNNs) significantly boost the expressive power of standard Graph Neural Networks by shifting the focus from "rooted subtrees" to "rooted subgraphs." This simple yet powerful architectural change allows NGNNs to distinguish complex graph structures that traditional GNNs find identical, all while maintaining scalable, linear time complexity.

What Problem Does This Paper Address?

Most modern Graph Neural Networks (GNNs) rely on a message-passing scheme that is theoretically bounded by the 1-dimensional Weisfeiler-Lehman (1-WL) test. In simple terms, when a GNN aggregates information from neighbors, it essentially "sees" the local neighborhood as a tree structure (a rooted subtree).

The problem? Many real-world graphs aren't trees—they have cycles and complex local clusters. Two graphs can look identical to a 1-WL test (and thus a standard GNN) even if they are structurally very different. For example, a standard GNN cannot distinguish between two triangles and one hexagon (both are 2-regular graphs where every node has two neighbors). This limitation hinders performance in critical tasks like molecule modeling and social network analysis where cycles and motifs are essential.

Comparison of rooted subtrees (1-WL) and rooted subgraphs (NGNN) for two 2-regular graphs.

As illustrated above, while the rooted subtrees (middle) for the two distinct graphs look identical to a standard GNN, extracting rooted subgraphs (right) preserves the actual connectivity, allowing the model to easily distinguish the triangle from the hexagon.

Methods

The authors propose Nested Graph Neural Networks (NGNNs), a "plug-and-play" framework designed to capture more than just tree-like structures.

The Nested Graph Neural Network (NGNN) architecture.

The process works in three main steps:

  1. Subgraph Extraction: For every node in the graph, the model extracts a local $h$-hop "rooted subgraph" (the actual nodes and edges within a certain distance).
  2. Base GNN (Inner): A "base" GNN (like GCN or GIN) is applied to each of these subgraphs independently. Because the subgraph is treated as its own entity, the model can learn representations that reflect the actual internal connectivity (like cycles) of that neighborhood.
  3. Pooling and Outer GNN: The representations of all nodes within a subgraph are pooled into a single vector, which becomes the final representation for the "root" node. These root representations are then fed into an "outer" GNN or a global pooling layer to represent the entire graph.

Crucially, NGNNs allow for Distance Encoding: augmenting node features with their distance to the root node of the subgraph. This helps the model understand the "role" a node plays within its local neighborhood.

Datasets

The authors evaluated NGNN across a diverse set of benchmarks:

  • Synthetic: The EXP dataset, specifically designed with pairs of non-isomorphic graphs that 1-WL cannot distinguish, and a simulation dataset of $r$-regular graphs.
  • Chemistry/Regression: QM9, containing 130k small molecules with 12 regression targets.
  • Bioinformatics/Classification: TU datasets (D&D, MUTAG, PROTEINS, PTC_MR, ENZYMES).
  • Large-scale Benchmarks: Open Graph Benchmark (OGB) datasets, specifically ogbg-molhiv and ogbg-molpcba.

Key Insights and Ideas

  • Subgraphs > Subtrees: By extracting subgraphs and processing them independently, the model can "see" edges between neighbors that standard message passing ignores. This makes NGNN strictly more powerful than the 1-WL test.
  • The Power of $r$-regular Graphs: The authors provide a rigorous proof that NGNN can discriminate almost all $r$-regular graphs—a category where standard GNNs fail 100% of the time.
  • Efficiency via Locality: While "higher-order" GNNs (like 3-WL) exist, they are often computationally explosive ($O(n^3)$ or worse). NGNN maintains a near-linear complexity relative to the number of nodes because it only looks at small, local subgraphs.
  • Plug-and-Play: NGNN isn't a new "layer" but a way to wrap existing GNNs. You can take a standard GIN or GCN and "nest" it to immediately improve its structural awareness.

Key Results

  • Expressive Power: On the EXP dataset, where standard GNNs achieve only 50% accuracy (random guessing), Nested GIN achieved 99.9% accuracy.
  • Consistent Gains: NGNN improved the performance of every base GNN it was tested with. On the QM9 dataset, it reduced Mean Absolute Error (MAE) by up to 7.9x.
  • TU Datasets: It showed accuracy improvements of up to 14.3% compared to the base models.
  • State-of-the-Art: On the OGB ogbg-molpcba leaderboard, Nested GIN outperformed the plain GIN model significantly, showing that the framework scales to challenging, real-world molecular datasets.

Limitations and Future Work

The primary limitation is memory overhead. Because NGNN "copies" subgraphs for every node, it can consume significant GPU memory if the graph has a very high average degree or if the chosen subgraph height ($h$) is too large.

The authors suggest that future work should focus on more memory-efficient implementations, perhaps by extracting subgraphs "on the fly" or using more sophisticated sampling techniques to handle massive graphs like social networks or citation webs. Additionally, exploring the theoretical relationship between NGNN and 3-WL remains an open question.

Summary updated

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.
BibTeX
@inproceedings{zhang2021nested,
  author = {Muhan Zhang and Pan Li},
  title = {{Nested Graph Neural Networks}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=GP3-fXQ_1Pj},
}
Figure