On the Expressive Power of Subgraph Graph Neural Networks for Graphs with Bounded Cycles

Abstract

Standard Graph Neural Networks (GNNs) are often bottlenecked by the expressive limits of the 1-Weisfeiler-Lehman (WL) test, particularly in distinguishing complex topological structures like cycles. This paper provides a rigorous theoretical foundation for $k$-hop subgraph GNNs, proving they can perfectly distinguish graphs and approximate continuous functions provided the graphs lack cycles longer than $2k+1$. We validate this "2k+1 rule" through experiments on the ZINC molecular dataset, demonstrating that tuning the receptive field $k$ to the dataset's maximum cycle length optimizes performance and generalization.

Introduction

Message-passing GNNs (MP-GNNs) update node features by aggregating information from immediate neighbors. However, this local approach is fundamentally limited by the 1-WL test. MP-GNNs frequently fail to distinguish non-isomorphic graphs that appear locally identical, such as different configurations of regular rings.

Expand

Source, p. 2

To overcome these limitations, subgraph GNNs have been proposed, which aggregate over local $k$-hop subgraphs. While these models show empirical promise, the relationship between the aggregation distance $k$ and the specific graph topologies they can resolve remained poorly understood until now.

Theoretical Framework and Methods

The authors map the expressive power of $k$-hop subgraph GNNs to a corresponding $k$-hop subgraph WL test. They analyze two primary architectures:

1. $k$-hop subgraph GNNs: These aggregate features from $k$-hop neighbors while explicitly incorporating the internal topology (edges) of the $k$-hop subgraph.
2. $k$-hop GNNs: A more efficient variant that aggregates features based on shortest-path distance but ignores internal subgraph edges.

Using generalized Stone-Weierstrass theorems, the paper establishes the $2k+1$ Rule: a $k$-hop subgraph GNN can universally approximate any permutation-invariant continuous function on graphs, provided there are no cycles longer than $2k+1$. If internal topology is ignored ($k$-hop GNNs), this bound reduces to $2k-1$.

Expand

Source, p. 3

To test these theories, the authors implemented a $k$-hop Graphormer, modifying the standard global attention mechanism with a mask that restricts attention to the $k$-hop neighborhood, ensuring the model strictly adheres to the theoretical constraints.

Empirical Validation: The ZINC Dataset

The ZINC dataset, containing 250,000 molecular graphs, serves as the primary benchmark. Molecules in ZINC have well-defined cycle lengths, with most peaking at 6 (e.g., benzene rings) and a few reaching 10. According to the $2k+1$ rule, a receptive field of $k=3$ should be sufficient to capture the dominant structures ($2(3)+1 = 7 > 6$).

Key Results

The experimental results strongly support the theoretical predictions:

• Performance Jump: A standard 1-hop Graphormer achieves a Mean Absolute Error (MAE) of 0.459. Increasing the receptive field to $k=4$ reduces the MAE significantly to 0.054.
• Saturation Point: Performance saturates around $k=3$, confirming that $k \approx \text{cycle\_length}/2$ is the critical threshold for expressivity in bounded-cycle graphs.
• Generalization: Interestingly, the $k=4$ Graphormer slightly outperformed the full-graph ($k=\infty$) version (MAE 0.058), suggesting that bounding the receptive field to match structural limits can filter out noise and improve model focus.

Conclusion and Future Work

This work establishes a mathematically backed rule of thumb for GNN design: the receptive field $k$ should be chosen based on the maximum cycle length of the target dataset. While the proofs rely on certain mathematical assumptions like "$k$-separability," the empirical success on molecular data suggests these bounds are practically robust. Future research may focus on weakening these theoretical assumptions or developing automated tools to tune $k$ based on dataset topology.