Nested Graph Neural Networks

Muhan Zhang, Pan Li

TL;DR

Nested Graph Neural Networks (NGNNs) break the "subtree" limitation of standard Graph Neural Networks by representing nodes through rooted subgraphs instead. This architectural shift makes them strictly more powerful than the standard Weisfeiler-Lehman (1-WL) test, allowing them to distinguish complex structures like $r$-regular graphs while maintaining the linear scalability required for real-world applications.

What Problem Does This Paper Address?

Most modern Graph Neural Networks (GNNs) are built on a message-passing scheme that mimics the 1-dimensional Weisfeiler-Lehman (1-WL) algorithm. While effective, this approach has a fundamental "blind spot": it represents the neighborhood of a node as a rooted subtree.

The problem is that subtrees are poor at capturing cycles and complex local connectivity. For example, a standard GNN cannot distinguish between two different $r$-regular graphs (where every node has the same number of neighbors) because their local "trees" look identical, even if their global structures are completely different.

Comparison of rooted subtrees vs. rooted subgraphs. Standard GNNs use subtrees (middle), which fail to capture cycles present in the original graphs. NGNNs use subgraphs (right), preserving local structural information.

While "higher-order" GNNs exist to solve this, they usually suffer from $O(n^3)$ or higher computational complexity, making them impractical for large datasets. NGNN aims to bridge this gap—providing higher expressive power without the massive computational overhead.

Methods

The authors propose a "GNN of GNNs" approach. Instead of running one global message-passing operation, NGNN operates in two nested levels:

  1. Subgraph Extraction: For every node in the graph, NGNN extracts a local $h$-hop rooted subgraph (a "neighborhood" that includes the edges between neighbors, not just the tree-like paths).
  2. Inner (Base) GNN: A base GNN (like GIN or GCN) is applied to each of these subgraphs independently. Because these subgraphs are treated as separate entities, the model can use Distance Encoding—tagging nodes based on how far they are from the "root" node of that specific subgraph.
  3. Subgraph Pooling: The representations of all nodes within a subgraph are pooled to create a single, highly informative representation for the root node.
  4. Outer GNN: These enhanced node representations are then fed into an outer GNN or a global pooling layer to produce the final graph-level representation.
The NGNN architecture: Inner GNNs process extracted subgraphs, followed by subgraph pooling and an outer GNN for final graph representation.

This "nested" design allows the model to "see" cycles and local clusters that standard message-passing would flatten into a tree.

Datasets

The authors evaluated NGNN across a diverse range of benchmarks:

  • Synthetic: The EXP dataset, specifically designed to contain pairs of graphs that 1-WL (and standard GNNs) cannot distinguish.
  • Molecules (Regression): QM9, a dataset of 130k small molecules where the goal is to predict chemical properties.
  • Bioinformatics/Social (Classification): Several TU datasets including D&D, MUTAG, PROTEINS, and ENZYMES.
  • Large-Scale Benchmarks: ogbg-molhiv and ogbg-molpcba from the Open Graph Benchmark (OGB).

Key Insights and Ideas

  • Subgraphs > Subtrees: The core "aha moment" is that by simply "copying" a local neighborhood and treating it as its own graph, you unlock the ability to see internal edges (cycles) that are invisible to standard message passing.
  • The Power of Distance: Because each subgraph has a clear "center" (the root node), the model can use the distance from the center as a feature. This breaks the symmetry that usually confuses GNNs in regular graphs.
  • Plug-and-Play Power: NGNN isn't a specific model like GCN; it’s a framework. You can take any existing GNN and "nest" it to immediately boost its theoretical and practical performance.
  • Efficiency via Locality: While it sounds expensive to run a GNN for every node, the subgraphs are small. This keeps the complexity linear $O(n)$ with respect to the number of nodes, rather than the $O(n^3)$ seen in other powerful GNN variants.

Key Results

  • Theoretical Superiority: The authors proved that NGNN can distinguish almost all $r$-regular graphs, a task where standard GNNs fail 100% of the time.
  • Synthetic Breakthrough: On the EXP dataset, standard GNNs achieved only 50% accuracy (random guessing), while Nested GIN achieved 99.9%.
  • Massive Gains in Chemistry: On the QM9 dataset, NGNN reduced the Mean Absolute Error (MAE) by up to 7.9x compared to the base models.
  • State-of-the-Art Performance: On OGB benchmarks, Nested GIN outperformed much more complex and heavily tuned models, showing that structural expressiveness is often more important than model depth or parameter count.

Limitations and Future Work

  • Memory Overhead: The current implementation involves "materializing" or copying subgraphs into memory. For very dense graphs or graphs with a high average degree, this can lead to high GPU memory consumption.
  • Scalability to Giant Graphs: While linear in time, the constant factor (the size of the $h$-hop subgraph) can become a bottleneck on massive social networks or web graphs.
  • Theoretical Bounds: While NGNN is strictly better than 1-WL, its exact relationship to the 3-WL test (a higher-order logic test) remains an open question for future research.
  • Automated Subgraph Selection: The paper uses a fixed $h$-hop radius; future work could explore learning which subgraphs are most relevant for a specific task.

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