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

Levi Rauchwerger, Stefanie Jegelka, Ron Levie

TL;DR

This paper provides a unified theoretical framework for Graph Neural Networks (GNNs) on attributed graphs by introducing a novel metric based on hierarchical optimal transport. The authors prove that under this metric, GNNs are universal approximators and satisfy rigorous generalization bounds, effectively bridging the gap between expressivity, stability, and learnability.

What Problem Does This Paper Address?

While Graph Neural Networks (GNNs) are incredibly successful in practice—from drug discovery to social network analysis—our theoretical understanding of them has remained fragmented. Specifically, researchers have struggled to create a mathematical "space" for graphs with node attributes that satisfies three critical criteria simultaneously:

  1. Separation Power: The ability for GNNs to distinguish between different graphs (expressivity).
  2. Stability: Ensuring that small changes in the graph lead to small changes in GNN output (Lipschitz continuity).
  3. Compactness: A topological property required to prove that GNNs can approximate any function (universality) and to derive bounds on how well they perform on unseen data (generalization).

Previous works often sacrificed one of these. For instance, some metrics worked only for graphs without attributes, while others were not "compact," making it impossible to guarantee that a model trained on a finite dataset would work reliably on the entire distribution of possible graphs.

Methods

The authors bridge these gaps using a combination of Graphon Theory and Optimal Transport.

  • Graphon-Signals: They treat finite graphs as samples of "graphons"—continuous limits of dense graphs. They extend this to "graphon-signals" to incorporate node attributes.
  • Iterated Degree Measures (IDMs): To capture the recursive nature of GNN message passing, they use IDMs. An IDM represents a "computation tree" rooted at a node, encoding both the node's own attributes and the distribution of attributes in its neighborhood across multiple hops.
  • DIDM Mover’s Distance: The core innovation is a new pseudometric ($\delta_{DIDM}$). It uses Unbalanced Optimal Transport to compare the distributions of these computation trees between two graphs.
Figure 1: Measuring similarity between graph-signals on the left is translated into mea- suring similarity between graphon-signals and, lastly, to computing optimal transport between two IDMs, which comprise in the figure of a signal value and a distribution over signal values induced by the graphon’s adjacency. Edges colors depict edge weights and node colors depict signal values.

The paper focuses on Message Passing Neural Networks (MPNNs) using normalized sum aggregation, which aligns naturally with the continuous integration used in their graphon-based proofs.

Datasets

The authors validated their theory using both synthetic and real-world benchmarks:

  • Synthetic: Graphs generated via Stochastic Block Models (SBMs) were used to test the correlation between the proposed metric and actual GNN output perturbations.
  • Real-world: The MUTAG (mutagenic aromatic and heteroaromatic nitro compounds) and PROTEINS datasets were used for 1-Nearest-Neighbor classification tasks and to demonstrate that the metric captures task-relevant similarities.

Key Insights and Ideas

  • Compactness is the "Aha!" Moment: By proving the space of attributed graphs is compact under their new metric, the authors could invoke the Stone-Weierstrass theorem. This allowed them to prove that GNNs are universal approximators for any continuous function on attributed graphs.
  • Equivalence of Geometry: A major finding is that the "geometry" of graphs under the $\delta_{DIDM}$ metric is essentially equivalent to the geometry of GNN representations. If two graphs are close in the metric, all GNNs will produce similar outputs for them.
  • Computability: Despite the heavy measure-theoretic machinery, the authors show that the distance between two graphs with $N$ nodes can be computed in polynomial time ($O(L \cdot N^5 \log N)$), making it a practical tool for analysis.

Key Results

  • Universal Approximation: The paper provides a formal proof (Theorem 6) that MPNNs can approximate any continuous function over the space of attributed graphs.
  • Generalization Bounds: They derive a new generalization bound (Theorem 8) that does not depend on the number of parameters in the GNN, but rather on the Lipschitz constants of the layers and the complexity of the graph space itself.
  • Empirical Correlation: Experiments showed a very strong correlation between the $\delta_{DIDM}$ distance and the output distance of randomly initialized GNNs, supporting the theory that the metric accurately reflects how GNNs "see" graphs.
  • Classification: Using the metric directly in a 1-Nearest-Neighbor classifier on MUTAG yielded an accuracy of 89.47%, performing comparably to other state-of-the-art graph metrics while providing much stronger theoretical guarantees.

Limitations and Future Work

  • Dense Graph Bias: The current theory is primarily meaningful for dense graphs. In sparse graph sequences (where the number of edges is much smaller than $N^2$), the graphs tend to collapse toward a "zero" graphon in this metric. The authors suggest that future work should focus on fine-grained analysis for sparse attributed graphs.
  • Aggregation Schemes: The proofs specifically target normalized sum aggregation. While this is common, extending the theory to other popular schemes like max or mean aggregation remains an open challenge.
  • Node-Level Tasks: The current framework is designed for graph-level tasks (e.g., "is this molecule toxic?"). Extending IDMs to analyze node-level stability and generalization is a promising next step.

Summary updated

Abstract

We analyze the universality and generalization of graph neural networks (GNNs) on attributed graphs, i.e., with node attributes. To this end, we propose pseudometrics over the space of all attributed graphs that describe the fine-grained expressivity of GNNs. Namely, GNNs are both Lipschitz continuous with respect to our pseudometrics and can separate attributed graphs that are distant in the metric. Moreover, we prove that the space of all attributed graphs is relatively compact with respect to our metrics. Based on these properties, we prove a universal approximation theorem for GNNs and generalization bounds for GNNs on any data distribution of attributed graphs. The proposed metrics compute the similarity between the structures of attributed graphs via a hierarchical optimal transport between computation trees. Our work extends and unites previous approaches which either derived theory only for graphs with no attributes, derived compact metrics under which GNNs are continuous but without separation power, or derived metrics under which GNNs are continuous and separate points but the space of graphs is not relatively compact, which prevents universal approximation and generalization analysis.
BibTeX
@inproceedings{rauchwerger2025generalization,
  author = {Levi Rauchwerger and Stefanie Jegelka and Ron Levie},
  title = {{Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=qKgd7RaAem},
}
Figure