Compositional PAC-Bayes: Generalization of GNNs with persistence and beyond
Kirill Brilliantov, Amauri H. Souza, Vikas Garg
Abstract
Heterogeneity, e.g., due to different types of layers or multiple sub-models, poses key challenges in analyzing the generalization behavior of several modern architectures. For instance, descriptors based on Persistent Homology (PH) are being increasingly integrated into Graph Neural Networks (GNNs) to augment them with rich topological features; however, the generalization of such PH schemes remains unexplored. We introduce a novel compositional PAC-Bayes framework that provides a general recipe to analyze a broad spectrum of models including those with heterogeneous layers. Specifically, we provide the first data-dependent generalization bounds for a widely adopted PH vectorization scheme (that subsumes persistence landscapes, images, and silhouettes) as well as PH-augmented GNNs. Using our framework, we also obtain bounds for GNNs and neural nets with ease. Our bounds also inform the design of novel regularizers. Empirical evaluations on several standard real-world datasets demonstrate that our theoretical bounds highly correlate with empirical generalization performance, leading to improved classifier design via our regularizers. Overall, this work bridges a crucial gap in the theoretical understanding of PH methods and general heterogeneous models, paving the way for the design of better models for (graph) representation learning. Our code is available at https://github.com/Aalto-QuML/Compositional-PAC-Bayes .
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Graph Persistence goes Spectral cites Topological Graph Neural Networks
- Graph Persistence goes Spectral cites Generalization and Representational Limits of Graph Neural Networks
- Topological Graph Neural Networks cites Graph Filtration Learning
- Positional Encoding meets Persistent Homology on Graphs cites Topological Graph Neural Networks
- Positional Encoding meets Persistent Homology on Graphs cites Open Graph Benchmark: Datasets for Machine Learning on Graphs
- Positional Encoding meets Persistent Homology on Graphs cites Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning
- Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning cites Open Graph Benchmark: Datasets for Machine Learning on Graphs
Cited by top-tier papers2
Builds on13
- Open Graph Benchmark: Datasets for Machine Learning on GraphsWeihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong et al.NeurIPS 2020 · 3,935 citations
- Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation LearningPan Li, Yanbang Wang, Hongwei Wang, Jure LeskovecNeurIPS 2020 · 391 citations
- Generalization and Representational Limits of Graph Neural NetworksVikas K. Garg, Stefanie Jegelka, Tommi S. JaakkolaICML 2020 · 363 citations
- Topological Graph Neural NetworksMax Horn, Edward De Brouwer, Michael Moor, Yves Moreau et al.ICLR 2022 · 135 citations
- Graph Filtration LearningChristoph D. Hofer, Florian Graf, Bastian Rieck, Marc Niethammer et al.ICML 2020 · 124 citations
Related papers
- Contraction and Hourglass Persistence for Learning on Graphs, Simplices, and CellsMattie Ji, Indradyumna Roy, Vikas GargICLR 2026 · 1 citation
- Topological Neural Networks go Persistent, Equivariant, and ContinuousYogesh Verma, Amauri H. Souza, Vikas GargICML 2024 · 13 citations
- Topological Pooling on GraphsYuzhou Chen, Yulia R. GelAAAI 2023 · 21 citations
- ToDD: Topological Compound Fingerprinting in Computer-Aided Drug DiscoveryAndac Demir, Baris Coskunuzer, Yulia R. Gel, Ignacio Segovia-Dominguez et al.NeurIPS 2022 · 26 citations
- Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?Haitao Mao, Zhikai Chen, Wei Jin, Haoyu Han et al.NeurIPS 2023 · 58 citations
