# Higher-Order Graphon Neural Networks: Approximation and Cut Distance

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

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Mar 2025.

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

- [Any-Dimensional Invariant Universality](https://mlsanity.com/paper/2605.23156/) (2026)
- [The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysis](https://mlsanity.com/paper/2510.17515/) (2025)
- [On the Convergence and Size Transferability of Continuous-depth Graph Neural Networks](https://mlsanity.com/paper/2510.03923/) (2025)
- [From Small to Large: Generalization Bounds for Transformers on Variable-Size Inputs](https://mlsanity.com/paper/2512.12805/) (2025)
- [Neural Networks With Dense Weights Are Not Universal Approximators](https://mlsanity.com/paper/2602.07618/) (2026)
- [Zero-Shot Size Transfer for Neural ODEs on Sparse Random Graphs: Graphon Limits and Adjoint Convergence](https://mlsanity.com/paper/2606.26662/) (2026)
- [Dimension-Free Scaling Laws for Size Generalization: An Exponential Separation](https://mlsanity.com/paper/2610.19279/) (2026)

## Abstract (arXiv)

Graph limit models, like graphons for limits of dense graphs, have recently been used to study size transferability of graph neural networks (GNNs). While most literature focuses on message passing GNNs (MPNNs), in this work we attend to the more powerful higher-order GNNs. First, we extend the k-WL test for graphons (B"oker, 2023) to the graphon-signal space and introduce signal-weighted homomorphism densities as a key tool. As an exemplary focus, we generalize Invariant Graph Networks (IGNs) to graphons, proposing Invariant Graphon Networks (IWNs) defined via a subset of the IGN basis corresponding to bounded linear operators. Even with this restricted basis, we show that IWNs of order k are at least as powerful as the k-WL test, and we establish universal approximation results for graphon-signals in Lp distances. This significantly extends the prior work of Cai & Wang (2022), showing that IWNs--a subset of their IGN-small--retain effectively the same expressivity as the full IGN basis in the limit. In contrast to their approach, our blueprint of IWNs also aligns better with the geometry of graphon space, for example facilitating comparability to MPNNs. We highlight that, while typical higher-order GNNs are discontinuous w.r.t. cut distance--which causes their lack of convergence and is inherently tied to the definition of k-WL--transferability remains achievable.