Research map / Graph learning / GNN architectures

Higher-Order Graphon Neural Networks: Approximation and Cut Distance

ICLR 2025 · Graph learning › GNN architectures · approach: Subgraph and distance-aware GNNs

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Extends k-WL and homomorphism densities to graphon-signals, defines Invariant Graphon Networks (IWNs) with bounded linear equivariant layers, proves k-WL expressivity and universal approximation in L_p distances, and shows higher-order graphon models are cut-distance discontinuous yet transferable.

Problem

Higher-order GNNs (IGNs/k-WL) lack a graphon-limit framework, so their expressivity, continuity, and size transferability are not systematically understood compared to MPNNs on graphons.

Approach

Introduce signal-weighted homomorphism densities for graphon-signals, and define IWNs by restricting IGN linear equivariant layers to bounded operators on L2 over [0,1]; this basis (no diagonal selection) suffices for k-WL expressivity and universality, and transferability holds despite cut-distance discontinuity.

Key results

• IWNs of order k are at least as expressive as k-WL on graphon-signals and are universal approximators in L_p distances on compact subsets.
• All nontrivial IWNs (pointwise nonlinearity) are discontinuous w.r.t. cut distance, yet transferability holds: E|N(G_n)-N(G_m)| -> 0 for functions in the closure of signal-weighted homomorphism density spans.
• Toy experiment: IWN errors on sampled graphs stabilize rather than vanish, while MPNN errors decrease with graph size; prediction interval widths contract for both.

Measured effects reported in the paper

Surprising findings

• Higher-order graphon networks are discontinuous w.r.t. cut distance, so sampled graphs do not converge to the graphon-limit output, although transferability still holds.
• The bounded-operator IWN basis (dimension at most bell(k+l)) keeps the full IGN expressivity in the limit.

Limitations

• Transferability proof gives convergence without a rate in general; quantitative rate only for a 2-layer real-analytic subclass.
• Experiments are only a small proof-of-concept on a few graphons.
• Compactness and universality hold only on compact subsets for L_p distances.

Experimental setup

Datasets: graphons from the paper's toy experiment

Metrics: absolute output error 90% prediction interval width

Baselines: IGN-small MPNN

Builds on: Invariant Graph Networks k-WL graphon homomorphism densities IGN-small

Closest papers by meaning

• A graphon-signal analysis of graph neural networks (NeurIPS 2023 · similarity 0.92)
• Convergence of Invariant Graph Networks (ICML 2022 · similarity 0.91)
• Minimax Sample Complexity of Graph Neural Networks: Lower Bounds and Structural Effects (ICLR 2026 · similarity 0.90)
• Graph neural networks and non-commuting operators (NeurIPS 2024 · similarity 0.89)
• Homomorphism Expressivity of Spectral Invariant Graph Neural Networks (ICLR 2025 · similarity 0.88)
• The Graphon Limit Hypothesis: Understanding Neural Network Pruning via Infinite Width Analysis (NeurIPS 2025 · similarity 0.88)