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.
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 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:
- 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.
- 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