TL;DR
Standard message passing Graph Neural Networks (MPNNs) are fundamentally incapable of counting simple subgraphs like triangles and cliques, while higher-order GNNs that can are computationally prohibitive ($\Omega(n^k)$ complexity). This paper introduces Recursive Neighborhood Pooling (RNP-GNN), a framework that recursively pools over localized sub-neighborhoods annotated with simple connectivity markers to provably count subgraphs of size $k$. By exploiting graph sparsity, RNP-GNN achieves near-linear runtime on sparse graphs, bridging the gap between computational efficiency and expressive power.
What Problem Does This Paper Address?
Graph Neural Networks are widely used to model molecules, social networks, and physical systems. However, most popular architectures rely on local message passing bounded by the 1-Weisfeiler-Leman (1-WL) graph isomorphism test. As a result, standard MPNNs cannot distinguish strongly regular graphs, nor can they count induced subgraphs with three or more vertices (such as triangles, cycles, or cliques)—features critical for tasks like identifying chemical functional groups.
Existing solutions fall into two extremes:
- Adding unique node identifiers or random node features, which breaks permutation invariance or requires extensive sampling.
- Higher-order GNNs (such as $k$-WL networks or equivariant tensor networks), which operate on $k$-tuples of nodes. While expressive enough to count $k$-node subgraphs, they require $\Omega(n^k)$ operations—making them unusable for large real-world graphs.
The authors ask: Can we design a GNN architecture that can provably count substructures while avoiding the prohibitive $\Omega(n^k)$ cost on sparse graphs, and what are the fundamental lower bounds for this task?
Methods
The authors propose Recursive Neighborhood Pooling (RNP-GNN), guided by the following principles:
- Recursive Subgraph Extraction and Marking: To represent an $r_1$-neighborhood around node $v$, RNP removes $v$ and marks each neighbor $u \in \mathcal{N}_{r_1}(v)$ with an indicator showing whether it was adjacent to $v$. It then recursively applies the pooling operation on smaller sub-neighborhoods within this screened subgraph down to base cases ($\tau = 1$).
- Covering Sequences: To determine the neighborhood radii $(r_1, r_2, \dots, r_\tau)$ needed to count a target pattern $H$ on $k = \tau + 1$ vertices, the authors introduce covering sequences. These are computed by taking a spanning tree of $H$ and iteratively peeling away leaf nodes, tracking the maximum shortest-path distance to the remainder of the graph.
- Injective Aggregation: At each level, node and neighborhood representations are aggregated via injective multiset functions (parameterized by Multi-Layer Perceptrons, following the GIN formalism).
- Theoretical Lower Bounds:
- Information-theoretic bound: For any architecture encoding a graph into $t$ subgraphs with $s$ possible encoding states, counting $k$-vertex motifs requires $t = \tilde{\Omega}(n^{\frac{k}{s-1}})$. For binary encodings ($s=2$), one fundamentally needs $\tilde{\Omega}(n^k)$ subgraphs.
- Computational bound: Assuming the Exponential Time Hypothesis (ETH), counting general $k$-vertex subgraphs requires $n^{\Omega(k)}$ time in the worst case, and no algorithm can run in linear time on weakly sparse graphs (bounded average degree).
Datasets
- Synthetic Subgraph Counting Benchmark: Following Chen et al. (2020), evaluated on:
- Erdős-Rényi graphs: 5,000 graphs of 10 nodes each.
- Perturbed Random Regular graphs: 5,000 graphs varying between 10, 15, 20, and 30 nodes, where $n$ random edges are deleted.
- Tasks: Predicting counts of induced triangles and non-induced 3-stars.
- EXP Dataset: Introduced by Abboud et al. (2021), consisting of 600 pairs of graphs (1,200 graphs total; averaging ~44 nodes and 110 edges). The graphs encode satisfiable vs. unsatisfiable propositional formulas that are indistinguishable by 1-WL but separable by 3-WL.
Key Insights and Ideas
- Pooling alone is surprisingly powerful: Prior methods like Local Relational Pooling (LRP) required averaging over all $k!$ node permutations within a local patch. RNP proves that simple recursive multiset pooling paired with single-bit neighbor markings is sufficient to achieve subgraph counting without factorial permutations or node IDs.
- Exploiting sparsity reduces worst-case barriers: Although worst-case graphs require $O(n^k)$ updates, on strongly sparse graphs (maximum degree $\Delta = O(1)$), the number of node updates drops to $O(n c^\tau) = O(n)$ for constant motif sizes.
- Minimizing the outer radius $r_1$: The overall complexity is dominated by the initial neighborhood radius $r_1$. The authors provide a polynomial-time algorithm using All-Pairs Shortest Paths (APSP) and Minimum Spanning Trees (MST) to find covering sequences that minimize $r_1$.
Key Results
- Substructure Counting: RNP-GNN dramatically outperforms standard MPNNs (GCN, GIN, GraphSAGE) and spectral/tensor baselines (2-IGN). On normalized Mean Squared Error (MSE / variance):
- Erdős-Rényi Triangles: RNP-GNN achieves $1.39 \times 10^{-5}$, outperforming GIN ($1.23 \times 10^{-1}$), PPGN ($5.08 \times 10^{-8}$ performs best, but RNP beats LRP-1-3's $1.56 \times 10^{-4}$ and Deep LRP-1-3's $2.81 \times 10^{-5}$).
- Random Regular Triangles: RNP-GNN achieves $2.38 \times 10^{-6}$, competitive with Deep LRP-1-3 ($1.30 \times 10^{-6}$) and beating PPGN ($1.40 \times 10^{-6}$).
- Isomorphism Separation (EXP Dataset):
- RNP-GNN with $r_1 = 1$ fails (50.0% accuracy, matching 1-WL limits).
- With $r = (2, 1)$, RNP-GNN jumps to $99.8 \pm 0.005\%$ accuracy, surpassing 3-GCN ($99.7\%$), GCN with Random Node Initialization ($98.0\%$), and 1-2-3-GCN-L (50.0%).
Limitations and Future Work
- Dense Graph Bottleneck: On dense graphs, neighborhood sizes do not shrink quickly, causing the worst-case runtime to degrade back to $O(n^k)$.
- Empirical Latency vs. 1-WL: While asymptotically faster than higher-order tensor networks, RNP-GNN is still substantially slower to train than standard GIN (e.g., ~153–835 seconds per 10 epochs vs. ~0.88 seconds for GIN on synthetic graphs).
- Heuristic Approximations: Just as LRP inspired practical variants (Deep LRP), developing relaxed, learned, or sampled approximations of recursive neighborhood pooling is left as an important direction for scaling to massive real-world graphs.
Summary updated