Research map / Graph learning / GNN architectures

On the Generalization of Equivariant Graph Neural Networks

ICML 2024 · Graph learning › GNN architectures · approach: Substructure-aware GNN expressivity

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.

Derives the first generalization bound for E(n)-equivariant GNNs (EGNNs) via Rademacher complexity, showing dependence on a weighted sum of log spectral norms and benefits of ε-normalization, and proposes a spectral-norm-log regularizer evaluated on QM9.

Problem

Generalization capability of E(n)-equivariant graph neural networks on geometric graphs was theoretically uncharacterized, despite their expressivity being studied.

Approach

Derives a PAC-style high-probability Rademacher bound for EGNNs whose dependence on weight matrices is a weighted sum of logs of stretched spectral norms (layer-dependent weights favoring bottom layers), shows ε-normalization keeps the bound polynomial in depth, and turns the bound into a regularizer.

Key results

• Theoretical bound correlates highly with empirical generalization gap: Pearson ρ mostly above 0.8 across QM9 tasks (e.g., 0.98±0.01 for εLUMO vs. width in some settings; 7 of 8 width/depth cases above 0.9).
• ε-normalization yields smaller generalization gaps as the number of EGNN layers increases (Figure 4).
• Proposed log-spectral-norm regularizer gives lower test MSE and generalization gap than SPECAVG in nearly all QM9 cases (e.g., εHOMO with 7 layers: 7.90 vs 9.25 MSE).

Measured effects reported in the paper

Surprising findings

• The bound's layer weights make bottom layers' spectral norms matter more than top layers', which is counter to naive expectations about depth.

Limitations

• Bound ignores weight matrices with norm below 1, so it cannot become arbitrarily small.
• Spectral norms depend on the training set and learning algorithm, which the analysis does not decouple.
• Bound has worse dependence on depth than MP-GNN bounds, and the impact of equivariance is left for future work.

Experimental setup

Datasets: QM9

Benchmarks: QM9

Metrics: test MSE generalization gap Pearson correlation between theoretical and empirical gaps

Baselines: SPECAVG no regularization (None) MLP bound (Bartlett et al. 2017) MLP bound (Neyshabur et al. 2018) MP-GNN bound (Garg et al. 2020)

Builds on: EGNN (Satorras et al., 2021) Bartlett et al. 2017 spectrally-normalized margin bounds Neyshabur et al. 2018 PAC-Bayes bound Garg et al. 2020 GNN Rademacher bounds Behboodi et al. 2022

Closest papers by meaning

• Are High-Degree Representations Really Unnecessary in Equivariant Graph Neural Networks? (NeurIPS 2024 · similarity 0.92)
• Universally Invariant Learning in Equivariant GNNs (NeurIPS 2025 · similarity 0.90)
• Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrum (NeurIPS 2025 · similarity 0.89)
• On Explaining Equivariant Graph Networks via Improved Relevance Propagation (ICML 2025 · similarity 0.89)
• Equivariant Machine Learning on Graphs with Nonlinear Spectral Filters (NeurIPS 2024 · similarity 0.89)
• A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.88)