Research map / Graph learning / GNN architectures

Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs

ICLR 2025 · Graph learning › GNN architectures · approach: Weisfeiler-Leman expressivity hierarchies · 0 citations (OpenAlex)

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.

Proposes a pseudometric (DIDM mover's distance based on hierarchical optimal transport over computation trees/iterated degree measures) for attributed graphs/graphons under which the space is compact, MPNNs are Lipschitz and separate points, yielding universal approximation and graph-agnostic generalization bounds.

Problem

Existing pseudometrics for graphs do not simultaneously give MPNN continuity, point separation, and compactness of the space of attributed graphs, which blocks universal approximation and generalization analysis for GNNs on attributed graphs.

Approach

Extend iterated degree measures to graphon-signals by using node attribute space as the base level, and define the DIDM mover's distance as hierarchical optimal transport between computation IDMs; this metric makes MPNNs Lipschitz and separating while the attributed graphon space is compact.

Key results

• Empirically, the DIDM mover's distance (order 2) on SBM graph sequences shows strong correlation with output distances of randomly initialized MPNNs, for both constant and community-valued signals.
• Proves the space of attributed graphons with the DIDM mover's distance is compact, enabling universal approximation over attributed graphons (MPNNs dense in continuous functions).
• Proves a uniform generalization bound for MPNNs on attributed graphs/graphons that makes no distributional assumption and no dependence on parameter count, only Lipschitz constraints.

Surprising findings

• Sparse graphs are always close to the empty graph under the proposed metrics, so the theory is only meaningful for dense graphs.

Limitations

• Theory applies only to dense graphs; sparse graphs collapse to the empty graph under the metric.
• Proofs are specific to MPNNs with normalized sum aggregation; other aggregations are not covered.
• Empirical evaluation is a small proof-of-concept on synthetic SBM graphs with randomly initialized MPNNs.

Experimental setup

Datasets: stochastic block model graphs (50 graphs of 30 nodes, generated synthetically)

Metrics: correlation between DIDM mover's distance and MPNN output di

Baselines: Tree Mover's Distance cut distance for graphon-signals WL distance over hierarchies of probability measures

Builds on: 1-WL test for graphons (iterated degree measures) tree mover's distance cut distance Stone-Weierstrass theorem MPNN GIN

Closest papers by meaning

• Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.91)
• On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.91)
• Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.90)
• Covered Forest: Fine-grained generalization analysis of graph neural networks (ICML 2025 · similarity 0.90)
• On the Expressivity and Sample Complexity of Node-Individualized Graph Neural Networks (NeurIPS 2024 · similarity 0.89)
• Almost Surely Asymptotically Constant Graph Neural Networks (NeurIPS 2024 · similarity 0.88)