On the Expressive Power of Subgraph Graph Neural Networks for Graphs with Bounded Cycles
This work addresses a fundamental limitation in graph learning for researchers and practitioners, but it is incremental as it builds on existing subgraph GNN frameworks.
The authors tackled the limited expressive power of graph neural networks (GNNs) by proving that k-hop subgraph GNNs can approximate any permutation-invariant/equivariant continuous function over graphs with bounded cycles, within any error tolerance, under specific assumptions.
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.