Research map / Graph learning / GNN architectures

Covered Forest: Fine-grained generalization analysis of graph neural networks

ICML 2025 · Graph learning › GNN architectures · approach: Subgraph and distance-aware GNNs · 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.

Uses covering-number robustness theory with refined graph pseudo-metrics (Tree distance, Forest distance/TMD, mean-Forest distance) to derive tighter generalization bounds for MPNNs under various aggregations and losses.

Problem

Existing generalization bounds for MPNNs ignore graph structure, cover only specific aggregations, and assume the impractical 0-1 loss, leading to vacuous bounds that rely on a naive discrete notion of graph similarity tied to 1-WL.

Approach

Combine data-dependent covering-number robustness bounds with pseudo-metrics on graphs that are at least as expressive as 1-WL (Tree distance, Forest distance equivalent to TMD, mean-Forest distance for mean aggregation), so that MPNNs are Lipschitz with respect to them and covers become smaller, giving tighter generalization bounds for general losses such as cross-entropy and MAE.

Key results

• Shows that using the Tree distance yields a strictly tighter generalization bound than the 1-WL discrete-metric VC bound of prior work, and extends it to cross-entropy and MAE losses.
• Establishes that the Forest distance equals the Tree Mover's distance and defines a mean-Forest distance (1-MWL equivalent) that is Lipschitz for mean-aggregation MPNNs.
• Empirical study supports the theory, showing how graph structure and aggregation affect generalization.

Limitations

• Bounds for the discrete 1-WL metric are vacuous for large graphs since the logarithm term must be positive.
• Pseudo-metrics such as the Tree distance are hard to compute exactly (graph isomorphism-hard for metrics).

Experimental setup

Metrics: generalization error bound

Baselines: VC-dimension bound of Morris et al. 2023 1-WL discrete pseudo-metric bound

Builds on: Tree distance Tree Mover's distance robustness-based generalization (Xu & Mannor) data-dependent covering number bounds (Cheng et al.) VC dimension of MPNNs (Morris et al. 2023)

Closest papers by meaning

• Generalization Analysis of Message Passing Neural Networks on Large Random Graphs (NeurIPS 2022 · similarity 0.93)
• Towards Bridging Generalization and Expressivity of Graph Neural Networks (ICLR 2025 · similarity 0.92)
• Generalization, Expressivity, and Universality of Graph Neural Networks on Attributed Graphs (ICLR 2025 · similarity 0.90)
• On the Rademacher Complexity of Graph Neural Networks: Unifying Expressivity and Geometry (NeurIPS 2026 · similarity 0.90)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.90)
• Generalization of Graph Neural Networks Is Robust to Model Mismatch (AAAI 2025 · similarity 0.89)