The Power of Recursion in Graph Neural Networks for Counting Substructures

Behrooz Tahmasebi, Derek Lim, Stefanie JegelkaAISTATS 2023 · OpenReview

Abstract

To achieve a graph representation, most Graph Neural Networks (GNNs) follow two steps: first, each graph is decomposed into a number of subgraphs (the recursion step), and then the collection of subgraphs is encoded by several iterative pooling steps. While recently proposed higher-order networks show a remarkable increase in expressive power through a single recursion on larger neighborhoods followed by iterative pooling, the power of deeper recursion in GNNs without any iterative pooling is still not fully understood. We introduce the Recursive Neighborhood Pooling GNN (RNP-GNN), a pure recursion-based architecture. We quantify its expressive power through the task of counting substructures—a known limitation of standard Message Passing GNNs (MPNNs). Our results show that RNP-GNN exploits graph sparsity to achieve powerful representations with low computational cost, reaching near-optimal time complexity.

Introduction: The Counting Problem in GNNs

Standard Message Passing Neural Networks (MPNNs) are fundamentally limited in their ability to recognize graph topology. Their expressive power is upper-bounded by the 1-dimensional Weisfeiler-Lehman (1-WL) graph isomorphism test. This theoretical constraint manifests as a "blind spot" for local substructures: standard GNNs cannot count basic motifs like triangles, cliques, or cycles if they involve more than two nodes.

Examples of graph substructures that pose challenges for standard 1-WL limited GNNs.

This limitation is critical in domains like drug discovery, where the presence of specific functional groups (substructures) determines biological activity. While higher-order $k$-GNNs can address this, they often suffer from prohibitive $O(n^k)$ computational complexity, making them impractical for large-scale real-world graphs.

Methodology: Recursive Neighborhood Pooling

The RNP-GNN architecture departs from the traditional "aggregate-and-iterate" paradigm. Instead, it employs a "decompose-and-recurse" strategy. The core idea is to recursively break down a graph into smaller, overlapping neighborhoods until the structural information is explicitly captured.

The Recursion Mechanism

For any given node $v$, the model identifies its $r$-hop neighborhood $\mathcal{N}_r(v)$. It then removes the center node $v$ and "marks" the remaining neighbors to preserve the relative structural context. This process is applied recursively to the resulting subgraphs.

The recursive decomposition process in RNP-GNN, showing how neighborhoods are iteratively refined to capture deep structural features.

The depth of this recursion, $\tau$, determines the complexity of the substructures the model can identify. To ensure that all relevant motifs are captured, the authors introduce covering sequences—specific ordered sets of node removals and neighborhood radii that guarantee the identification of any substructure of a given size. Unlike previous methods like Local Relational Pooling (LRP), RNP-GNN uses injective multi-set pooling, which avoids the $O(k!)$ cost of isomorphic encodings.

Experimental Evaluation

The RNP-GNN was evaluated on synthetic and benchmark datasets designed to test structural expressivity:

  1. Substructure Counting: On Erdős-Rényi and Random Regular graphs, RNP-GNN successfully counted induced triangles and non-induced 3-stars, significantly outperforming GCN and GIN.
  2. EXP Dataset: This dataset contains pairs of 1-WL equivalent graphs that represent different propositional formulas. RNP-GNN achieved 99.8% accuracy, whereas standard powerful models like PPGN often fail, performing no better than random chance.

Complexity and Sparsity

A key advantage of RNP-GNN is its efficiency on sparse graphs. While dense graphs can lead to high computational costs due to neighborhood overlaps, the model achieves near-linear complexity ($O(nc^\tau)$) on graphs with a constant maximum degree. This makes RNP-GNN a practical alternative to $k$-GNNs for real-world networks which are typically sparse.

Conclusion

RNP-GNN demonstrates that deep recursion is a powerful alternative to iterative message passing for graph representation. By explicitly decomposing the graph, the model bypasses the limitations of the 1-WL test and enables efficient, provable substructure counting. Future work will focus on learning the recursion parameters end-to-end to further optimize the decomposition strategy for specific tasks.

Summary updated

Abstract

To achieve a graph representation, most Graph Neural Networks (GNNs) follow two steps: first, each graph is decomposed into a number of subgraphs (which we call the recursion step), and then the collection of subgraphs is encoded by several iterative pooling steps. While recently proposed higher-order networks show a remarkable increase in the expressive power through a single recursion on larger neighborhoods followed by iterative pooling, the power of deeper recursion in GNNs without any iterative pooling is still not fully understood. To make it concrete, we consider a pure recursion-based GNN which we call Recursive Neighborhood Pooling GNN (RNP-GNN). The expressive power of an RNP-GNN and its computational cost quantifies the power of (pure) recursion for a graph representation network. We quantify the power by means of counting substructures, which is one main limitation of the Message Passing graph Neural Networks (MPNNs), and show how RNP-GNN can exploit the sparsity of the underlying graph to achieve low-cost powerful representations. We also compare the recent lower bounds on the time complexity and show how recursion-based networks are near optimal.
BibTeX
@inproceedings{tahmasebi2023power,
  author = {Behrooz Tahmasebi and Derek Lim and Stefanie Jegelka},
  title = {{The Power of Recursion in Graph Neural Networks for Counting Substructures}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2023},
  url = {https://openreview.net/forum?id=xfFQGTmGug},
}
Figure