Research map / Graph learning / GNN architectures
Compositional PAC-Bayes: Generalization of GNNs with persistence and beyond
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.
Introduces a compositional PAC-Bayes framework that yields the first data-dependent generalization bounds for persistence-vectorization (PersLay) classifiers and PH-augmented GNNs, and uses the bound to derive a spectral-norm regularizer.
Problem
Generalization of heterogeneous models, especially persistent homology (PH) vectorizations (PersLay) and GNNs augmented with PH descriptors, has no data-dependent bounds.
Approach
A general perturbation-based PAC-Bayes lemma with four conditions (output bound, perturbation bound, a mean-of-inverse-norms condition, and an eta condition) that is closed under MLP composition and parallel combination, so heterogeneous models (PersLay + GNN) inherit bounds compositionally.
Key results
- Bound on weight spectral norm correlates with generalization gap with mean correlation above 0.7 in 7 of 9 PersLay/GNN experiments (e.g., 0.95 on MUTAG PersLay).
- PersLay with spectral-norm regularization achieves better test accuracy on 5 of 6 datasets (e.g., MUTAG 0.94 vs 0.88 ERM).
- Spectral regularizer reduces generalization gap for PH-augmented GCN/SAGE/GIN on NCI, NCI109, PROTEINS in nearly all cases.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add spectral norm regularization | PersLay · DRFH, MUTAG, PROTEINS, IMDB-B, NCI1, MOLHIV | accuracy / AUROC: DRFH: 0.71 ± 0.04 -> 0.72 ± 0.02; MUTAG: 0.88 ± 0.02 -> 0.94 ± 0.01; PROTEINS: 0.65 ± 0.03 -> 0.72 ± 0.01; IMDB-B: 0.65 | Helped |
| add spectral norm regularization | PH-augmented GCN, GraphSage, and GIN · NCI, NCI109, PROTEINS | test error: GCN NCI: 0.22 ± 0.01 -> 0.21 ± 0.02; GCN NCI109: 0.28 ± 0.00 -> 0.28 ± 0.02; GCN PROTEINS: 0.31 ± 0.01 -> 0.27 ± 0.02; S | Mixed |
| add spectral norm regularization | PH-augmented GCN, GraphSage, and GIN · NCI, NCI109, PROTEINS | generalization gap: GCN NCI: 0.19 ± 0.01 -> 0.01 ± 0.06; GCN NCI109: 0.25 ± 0.00 -> 0.12 ± 0.03; GCN PROTEINS: 0.25 ± 0.02 -> -0.02 ± 0.11; | Helped |
Surprising findings
- Regularized PH-augmented GNNs sometimes show negative generalization gaps (e.g., SAGE on PROTEINS -0.15 ± 0.30).
Limitations
- Gap between bounds and empirical results remains considerable, so bounds are not tight.
- Analysis restricted to fixed (non-learnable) filtration functions.
- PersLay with sum aggregation introduces a max cardinality term that can be large.
Experimental setup
Datasets: DHFR MUTAG PROTEINS NCI1 NCI109 IMDB-BINARY MOLHIV
Benchmarks: DHFR MUTAG PROTEINS NCI1 NCI109 IMDB-BINARY MOLHIV
Metrics: accuracy AUROC 0-1 test error generalization gap Pearson correlation between bound and generalization gap
Baselines: ERM
Builds on: Neyshabur et al. PAC-Bayes spectral norm bound Liao et al. PAC-Bayes GNN bound PersLay Sun and Lin GCN PAC-Bayes
Closest papers by meaning
- Positional Encoding meets Persistent Homology on Graphs (ICML 2025 · similarity 0.88)
- Towards Scalable Topological Regularizers (ICLR 2025 · similarity 0.87)
- Boosting Graph Pooling with Persistent Homology (NeurIPS 2024 · similarity 0.87)
- On the Limitations of Fractal Dimension as a Measure of Generalization (NeurIPS 2024 · similarity 0.86)
- Topological Generalization Bounds for Discrete-Time Stochastic Optimization Algorithms (NeurIPS 2024 · similarity 0.86)
- A Manifold Perspective on the Statistical Generalization of Graph Neural Networks (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.