Compositional PAC-Bayes: Generalization of GNNs with persistence and beyond

Kirill Brilliantov, Amauri H Souza, Vikas Garg

TL;DR

Researchers have developed a new "compositional" PAC-Bayes framework that provides a general recipe for analyzing how complex, multi-part AI models generalize to new data. They used this framework to establish the first-ever data-dependent generalization bounds for Graph Neural Networks (GNNs) augmented with topological features, leading to new regularization techniques that significantly improve model performance.

What Problem Does This Paper Address?

In the quest to make Graph Neural Networks (GNNs) more powerful, researchers have started looking at Topological Data Analysis (TDA). Specifically, they use Persistent Homology (PH) to capture global structural features—like loops and connected components—that standard GNNs often miss because they focus strictly on local neighborhoods.

Architecture of a heterogeneous GNN augmented with Persistent Homology (PH) features.

However, there’s a catch: these hybrid models are "heterogeneous." They mix traditional neural layers with specialized topological vectorization layers (like PersLay). Standard theoretical tools for predicting generalization—how well a model performs on unseen data versus its training data—usually assume the model is made of uniform layers. Because of this, we haven't had a clear mathematical understanding of why these PH-augmented GNNs work or how to optimize them. This paper fills that gap by providing a way to analyze models built from diverse, "composed" parts.

Methods

The authors leverage PAC-Bayes analysis, a framework that views learning through a Bayesian lens to provide "Probably Approximately Correct" guarantees. The core of their approach is a "compositional" strategy:

  1. The General Recipe: They identify a set of general conditions (related to output bounds and sensitivity to weight perturbations) that any model layer must satisfy to be "analyzable."
  2. Compositional Lemmas: They prove that if individual sub-models satisfy these conditions, their combinations—whether stacked in a sequence (serial) or running side-by-side (parallel)—also satisfy them.
  3. Application to PersLay: They apply this recipe to PersLay, a popular framework for turning topological diagrams into vectors. This allows them to derive the first data-dependent bounds for TDA-based classifiers.
  4. New Regularizers: Theoretical bounds aren't just for show; the authors turn their math into a practical tool. By identifying which terms in the bound drive generalization error (specifically the spectral norm of the weights), they design a new spectral norm regularizer to keep the model from overfitting.

Datasets

The authors evaluated their framework on several standard real-world graph classification benchmarks:

  • Small/Medium-scale: DHFR, MUTAG, PROTEINS, NCI1, and IMDB-BINARY.
  • Large-scale: MOLHIV and NCI109.

These datasets cover a range of domains, from predicting chemical properties of molecules to analyzing social networks.

Key Insights and Ideas

  • Heterogeneity is no longer a barrier: The "aha moment" here is that you don't need a bespoke proof for every new architecture. By breaking a model into its constituent "heterogeneous" layers and showing each piece is well-behaved, you can mathematically "glue" the bounds together.
  • Theory matches Reality: One of the most striking findings is the high correlation (often > 0.9) between their theoretical bounds and the actual empirical generalization gap observed during training. This suggests the math is capturing the true underlying mechanics of the model.
Correlation between the empirical generalization gap and the proposed theoretical bound across multiple datasets.
  • Topology needs constraints: The analysis shows that the width of the topological representation (the "h" dimension) and the choice of aggregation function (like "sum" vs "mean") significantly impact generalization. For instance, using "mean" or "k-max" aggregation often leads to better theoretical guarantees than a simple "sum."

Key Results

  • Improved Accuracy: Models using the new spectral norm regularizer (SpecNorm) outperformed standard Empirical Risk Minimization (ERM) in 5 out of 6 test cases for the PersLay classifier.
  • Tighter Generalization: In experiments with PH-augmented GNNs (using GCN, GraphSage, and GIN architectures), the regularized versions showed a massive drop in the generalization gap. For example, on the NCI dataset with a GCN, the gap dropped from 0.19 to nearly 0.01.
  • Versatility: The framework easily reproduced (and in some cases improved upon) existing bounds for standard MLPs and GCNs, proving its utility as a general-purpose tool.

Limitations and Future Work

The authors acknowledge a few key areas for growth:

  • The "Tightness" Gap: While the theoretical bounds correlate perfectly with the trend of the empirical gap, there is still a numerical distance between the absolute values of the theory and the practice.
  • Fixed vs. Learnable Filtrations: This study focused on "fixed" filtration functions (the rules that generate the topological diagrams). In the future, the authors want to extend this to "learnable" filtrations, which are more flexible but much harder to analyze mathematically.
  • Computational Cost: While the regularizers are effective, TDA-based methods are still computationally heavier than standard GNNs, a hurdle that needs addressing for massive-scale applications.

Summary updated

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.
BibTeX
@inproceedings{brilliantov2024compositional,
  author = {Kirill Brilliantov and Amauri H Souza and Vikas Garg},
  title = {{Compositional PAC-Bayes: Generalization of GNNs with persistence and beyond}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2024},
  url = {https://openreview.net/forum?id=ZNcJtNN3e8},
}
Figure