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

arXiv: https://arxiv.org/abs/2502.03703 · HTML: https://mlsanity.com/paper/2502.03703/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Feb 2025.

## Built on by (most cited first, 1 of 1)

- [Unifying approach to uniform expressivity of graph neural networks](https://mlsanity.com/paper/2602.18409/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) have been widely used in graph-related contexts. It is known that the separation power of GNNs is equivalent to that of the Weisfeiler-Lehman (WL) test; hence, GNNs are imperfect at identifying all non-isomorphic graphs, which severely limits their expressive power. This work investigates k-hop subgraph GNNs that aggregate information from neighbors with distances up to k and incorporate the subgraph structure. We prove that under appropriate assumptions, the k-hop subgraph GNNs can approximate any permutation-invariant/equivariant continuous function over graphs without cycles of length greater than 2k+1 within any error tolerance. We also provide an extension to k-hop GNNs without incorporating the subgraph structure. Our numerical experiments on established benchmarks and novel architectures validate our theory on the relationship between the information aggregation distance and the cycle size.