Abstract
While message passing Graph Neural Networks (GNNs) have become increasingly popular architectures for learning with graphs, recent works have revealed important shortcomings in their expressive power. In response, several higher-order GNNs have been proposed that substantially increase the expressive power, albeit at a large computational cost. Motivated by this gap, we explore alternative strategies and lower bounds. In particular, we analyze a new recursive pooling technique of local neighborhoods that allows different tradeoffs of computational cost and expressive power. First, we prove that this model can count subgraphs of size $k$, and thereby overcomes a known limitation of low-order GNNs. Second, we show how recursive pooling can exploit sparsity to reduce the computational complexity compared to the existing higher-order GNNs. More generally, we provide a (near) matching information-theoretic lower bound for counting subgraphs with graph representations that pool over representations of derived (sub-)graphs. We also discuss lower bounds on time complexity.
Introduction: The Expressivity Gap
Standard Message Passing GNNs (MPNNs) are the workhorses of graph machine learning, but they suffer from a fundamental "blind spot": their expressive power is limited by the 1-dimensional Weisfeiler-Leman (1-WL) graph isomorphism test. This limitation means they cannot distinguish between certain non-isomorphic graphs and, crucially, they cannot count subgraphs with more than two nodes. For instance, a standard MPNN cannot determine the number of triangles in a graph.
In fields such as drug discovery or social network analysis, these subgraphs (motifs) are vital features. While "higher-order" GNNs ($k$-GNNs) can count these structures, they are computationally expensive, often requiring $O(n^k)$ operations. This research introduces a middle ground: an architecture that is expressive enough to count motifs but efficient enough for real-world sparse graphs.
Recursive Neighborhood Pooling (RNP)
The core contribution of this work is Recursive Neighborhood Pooling (RNP). Instead of simple message passing, RNP operates through a recursive decomposition of the graph:
- Local Subgraph Selection: Identifying a local neighborhood around a node.
- Node Deletion & Marking: Removing the central node and "marking" its neighbors to retain structural context.
- Recursion: Repeating this process on the resulting smaller subgraphs.
To guide this recursion, the authors introduce Covering Sequences—a set of radii and node-removal steps that guarantee the network can identify a specific motif of size $k$. By recursively "peeling" the graph and marking intersections of neighborhoods, RNP effectively remembers structural relationships without needing unique node IDs.
Theoretical Foundations and Complexity
The paper establishes rigorous theoretical bounds for this approach. A key insight is that RNP can exploit sparsity for significant speedups. While higher-order GNNs are always expensive, RNP’s complexity is graph-dependent. On "strongly sparse" graphs (where the maximum degree is constant), RNP can count motifs in nearly linear time—an exponential improvement over traditional $O(n^k)$ models.
Furthermore, the authors provide Information-Theoretic Lower Bounds. Using the Exponential Time Hypothesis (ETH), they prove that if a GNN can count a $k$-clique, it must take at least $n^{\Omega(k)}$ time in the worst case. This establishes a fundamental speed limit for any expressive GNN, showing that RNP is near-optimal in its efficiency.
Experimental Results
The RNP framework was evaluated on synthetic motif counting tasks and the EXP Dataset, which contains graph pairs designed to be indistinguishable by 1-WL tests.
- Motif Counting: RNP-GNN consistently ranked among the top models for counting triangles and 3-stars, outperforming standard MPNNs (GCN, GIN) and matching specialized higher-order models like PPGN.
- Logic & Isomorphism: On the EXP dataset, RNP-GNN achieved 99.8% accuracy. In contrast, standard GNNs and some higher-order variants (like 1-2-3-GCN) performed no better than random guessing (50%) due to their lack of necessary WL-expressiveness.
Conclusion
Recursive Neighborhood Pooling bridges the gap between simple MPNNs and expensive higher-order GNNs. By leveraging recursion and sparsity, it provides a provably expressive framework for counting complex subgraphs while maintaining computational feasibility on sparse, real-world data. Future work may focus on approximating these recursive steps to further enhance scalability for massive datasets and larger motifs.
Summary updated