Compositional PAC-Bayes: Generalization of GNNs with persistence and beyond
Authors: Kirill Brilliantov
Amauri H Souza
Vikas Garg
Venue: NeurIPS 2024 poster (2024)
Keywords: generalization
tda
GNN
PAC-Bayes
Primary area: learning_theory
TL;DR: This paper introduces data-dependent generalization bounds for integrating persistent homology vectorizations with graph neural networks using a compositional PAC-Bayes framework.

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.

Compositional PAC-Bayes:
Generalization of GNNs with persistence and beyond
Kirill Brilliantov
Amauri H. Souza Federal Institute of Ceará amaur nourrhhllee wawlaaanddiffee edu. br
Vikas Garg
ETH Zürich
Yai Ltd & Aalto University vgargOcsail .ii. edu
Abrilliantov@ethh.cd
Abstract
Heterogeneity, e.g., due to different types of layers multiple sub-models, poses key challenges in analyzing the generalization behavior of several modern archi- tectures. For instance, descriptors based on Persistent Homology (PH) are being increasingly integrated into Graph Neural Networks (GNNs) augment them with rich topological features; however, the generalization of such PH schemes remains unexplored. We introduce a novel compositional PAC-Bayes framework that pro- vides general recipe to analyze a broad spectrum of models including those with heterogeneous layers. Specifically, we provide the first data-dependent generaliza- tion bounds for widely adopted PH vectorization scheme (that subsumes persis- tence landscapes, images, and silhouettes) as well as PH-augmented GNNs. Using framework, also obtain bounds for GNNs and neural nets with ease. Our bounds also inform the design of novel regularizers. Empirical evaluations on sev- eral standard real-world datasets demonstrate that our theoretical bounds highly cor- relate with empirical generalization performance, leading to improved classifier de- sign via our regularizers, Overall, this work bridges 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 avail- able at https: / thub. com/ Aalto- http//Commostiiioo PPCC Bayes.
Introduction
Topological data analysis (TDA) harnesses tools from algebraic topology to unveil the underlying shape and structure of data. TDA has recently gained significant traction within machine learning mainly due to its flagship method: persistent homology (PH) [11], which allows for capturing topolog- ical invariants (like connected components and loops) of the input domain multiple scales. par- ticular, PH has recently been leveraged as tool to augment the representational capabilities of graph neural networks (GNNs) [20, 53, 58], with expressivity gains formally established [22, 44]. Intuitively, PH furnishes global structural signatures that complement the local nature of GNNs [5, 18, 20, 57].
Understanding the generalization behavior of these models is crucial ensuring their reliability and applicability [41]. In this context, there are two fundamental approaches achieving generalization bounds: data-independent and data-dependent [47], each offering unique insights into the generalization problem. Both these approaches have been investigated to analyze the generalization ability of GNNs [12, 14, 25, 33, 36, 46, 48, 52, 59]. Data-dependent generalization bounds evoke particular interest since they are typically much tighter than the agnostic bounds afforded by, e.g.. VC dimension. However, no such bounds have been unearthed for PH methods (i.e.. leamable vectorization schemes) and, consequently, for GNNs enhanced with PH-based descriptors.
plays pivotal role in
We bridge this gap with the first data-dependent generalization bound for classifiers based versatile and widely used vectorization framework for persistence diagrams, namely, Perslay [5].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

PersLay leverages extended persistence to effectively represent detailed topological features, and subsumes commonly used methods such persistence landscapes [4], images [1], and silhouettes [6].
Central to our analysis is novel PAC-Bayes framework (Lemma 2) that provides general recipe to analyze the generalization of broad spectrum of models, including those with heterogeneous layers and those comprising multiple sub-models. To achieve this, we introduce general conditions (Equations 6-9) that are satisfied by commonly used learning architectures and, surprisingly, their com- positions (Section 4). Leveraging Lemma 2, we show how to obtain bounds for heterogeneous MLPs and GNNs in a straightforward manner (Table 2). Notably, we also establish the first generalization bounds for GNNs augmented with persistence layers (PersLay).
graphs; however, i) our Lemma 2 can be used in any domain and ii) our bound for
Our exposition focuses
Table I: Main thcoretical contributions of this work.
Section 3: Generalized PAC-Bayes
PersLay considers persistence diagrams obtained from any non-learnable fil- tration function, and therefore extends more generally input domains beyond graphs. From a technical perspective, our approach hinges on contrasting previous analyses within the PAC-Bayes framework [9, 37, 38] extract the common structure encoded in the general conditions of Lemma This allows us to overcome challenges arising from the heterogeneity of the models we consider.
General recipe for heterogeneous models
Lm. 2
Applying the recipe to GNNs and MLPs
Tab.
New bound for PersLay
Cor.
Section 4: Compositional PAC-Bayes
Bound for the composition with MLP
Lm. 3
Bound for two models in parallel
Lm. 4
New bound for GNNs with persistence
Cor. 2
Our experiments on several standard real-world datasets confirm strong correlation between the empirical performance and our theoretical bounds. We reinforce the merits of our analysis via regularized PH-based models informed by our bounds with demonstrable empirical benefits.
Our main contributions are:
(Theoretical, see Table 1) We develop a general recipe for obtaining PAC-Bayes bounds for broad class of (possibly heterogeneous) models and their compositions. We also provide the first data-dependent bounds for PH-based classifiers and combinations of GNNs and PersLay;
(Empirical) We show that the dependence parameters depicted in our bounds strongly correlates with the observed performance. We also show that novel regularization schemes based on our bounds can reduce the generalization gap of PH-augmented GNNs on multiple datasets.
2 Preliminaries
This section overviews GNNs, persistent homology on graphs, and their combination. We also provide basic notions and results PAC-Bayes learning, which serve as background for this work.
Notation. We consider attributed graphs denoted as a tuple G = (V, E, 2), where V V= {1, n} the vertex set, C V x V the edge set, and : V Rd: assigns to each vertex E V an attribute (or color) 2(v). For convenience, hercafter, we denote the feature vector of v by 2.. We consider classification tasks with input and label spaces X and y = = (I,...,,K, (K is the number of classes) and the m-margin loss L, 3 R + {0, where (v 9) 100 I 7 max Ú;) and y 2 0 is the margin parameter. Let S {(x, ) C X x y denote a collection of m input/label pairs sampled i..dd from some unknown distribution D. Then, the empirical error of hypothesis (1; Sw (xx)). Accordingly, we can define the generalization error as [DD,( = B< (L, (U, Iw (x))]. We use || ||2 to refer the lg norm (vectors) and the spectral norm (matrices). and ||. || p to refer to the Frobenius norm. Also, we denote the set {1...., n by [n). We provide notation table in the Appendix (Table 5).
Iw X' - R with parameters is defined i.s. (gw) 11mm E
Graph neural networks (GNNs). Message-passing GNNs [15, 55] employ sequence of message- passing steps: each node aggregates messages from its neighbors Nwv) (u (v, u) E E), using the resulting vector to update its own embedding. Starting from (0)) 2,. GNNs recursively apply
z
(I+1) Upd, (z(²) Agg, (f =!= :uc E(()B))
VU V,
(1)

---

where B denotes a multiset, Agg, is an invariint function and Upd, is an arbitrary update function often a multilayer perceptron (MLP).
Persistence homology (PH) on graphs aims to extract detailed (multiscale) topological features from graphs. A filtration of a graph G is a finite nested sequence of subgraphs of G, i.e., 0 = Go C Gj C... C G - alternatively, clique complexes can also be built at each step (see [2]). While filtrations can be obtained in different ways [2. 18], typical choice consists of leveraging a real-valued filtering function f on the vertices of G (or their features) to compute the vertex level set Va {v: : f(v) S a} at scale a E RR. Let Ga be the subgraph of G' induced by Va. By increasing a from -oo to oo, we obtain nested sequence of subgraphs called the sub-level filraation of G induced by f. The idea of PH is to keep track of the appearance and disappearance of topoloiiall features (e.g., connected components, loops) in a filtration. If topological feature first appears in Go, and disappears in Ga.. then we encode its persistence as pair (ob; Oa): a feature does not disappear, then its persistence is (as, oo). The collection of all pairs forms a multiset that we call persistence diagram. We use Dg, (G) to denote the persistence diagram for i-dim topological features of graph G. For details on PH, we refer to Edelsbrunner and Harer [10], Hensel et al. [17], and Hofer et al. [19].
Persistence layers (PersLay). Carrière et al. [5] introduced a general way to vectorize persistence diagrams. Given a persistence diagram Dg(G) for an arbitrary dimension, PERSLAY computes
PERSLAY(Dg(G)) Agg (((())(()) pp E Dg)
where Agg is any permutation invariant operation (e.g., minimum, maximum, sum, kth largest value), w IR? + R is a weight function for the elements in Dg(G), and & I²² + IR is the so-called point transformation. More specifically, given a persistence pair p = [p1.22] T R? PersLay introduces the triangle point transformation (A):
(p) = (Ap(ta)....AAAt Ap(tA)]
with Ap(ti) max P2 |t, - p1ll, 1.ll,,.E E
(3)
the Gaussian point transformation (T';
(p) = (t). (......,,tttt)))t.. [ta]] with rp(t.) exp (- || (-1ll; pll -pll)
272 ,t, E R
(4)
and the line point transformation (V²):
1o (p) (V, (p(ta)] with vp(l.) = t1,1P1 + ti,2P2 + 44,,,,4 14 E R23
(5)
In all of these transformations t tn are learnable parameters. Notably, the architectural design of PERSLAY is quite versatile and accommodates wide range of traditional persistence diagram vec- torizations, extending DeepSets [56] and including persistence landscapes [4], persistence silhouette
[6], persistence images [1], and other Gaussian basad kernel approaches [23, 29, 31].
To obtain class predictions, the output of PersLay is typically fed to an MLP with Lipschitz activations. We refer to this joint model (PersLay followed by MLP) as Perslay Classifier (PC).
GNNs with persistence. Recently, PH has been used to boost the expressive power of GNNs. For instance, Horn et al. [20] and Immonen et al. [22] leverage node embeddings at each layer of a GNN to obtain persistence descriptors. This topological
G
GNN
ReadOut
MLP
information can be added to GNN's node embeddings (as in [20]) or concatenated with GNN's graph-level representation (as in [22]) - which we refer to the parallel mode of integrating PH into GNNs. Figure illustrates the latter (parallel mode) with persistence diagrams vectorized using PersLay.
PH
PersLay
ra
DgtG
Figure I: GNNs with persistence (parallel mode).
PAC-Bayesian analysis adopts a Bayesian approach the PAC learning framework [30, 37, 38, 50]. The idea consists of placing a prior distribution P over our hypothesis class and then use the training data to obtain a posterior 2, i.c., the learning process induces posterior distribution over the hypothesis class. Importantly, we can leverage the Kullback-Leibler (KL) divergence between Q and P to bound the difference between the generalization and empirical errors [37]. To compute PAC- Bayes bounds for models like neural networks, we can i) choose a prior, ii) apply a learning algorithm; and iii) add random perturbations (from some known distribution) to the learned parameters such that we ensure tractability of the KL divergence. Following this recipe, Neyshabur et al. [40] established the following generalization bound (Lemma) 1) when the change in the output of the model due to perturbations over the learned parameters is small with high probability.
3

---

Lemma 1 (Neyshabur et al. [40]). Let 9w(z) X + R be any model with parameters w, and let P be any distribution on the parameters that independent of the training data. For any w, we construct posterior Q(w + u) by adding any random perturbation u to w, s.l., Pu Pu(maxxex tw (x) 9w Ow(x))ls < 3) 2 Then, for any 71 > with probability at least 1 - 8 over an t.d. size-m training set S drawn according to D. for any we have:
DKL(Q(W -n)lPP) log
LD.u(ow) & (ow)(ow) + +
m
3 Generalized PAC-Bayes
This section first presents general procedure for obtaining generalization bounds for heterogeneous models, i.e., going beyond
layers and architecture-specifi models (as in [33, 40).. Then, we show how to leverage such a procedure to extend existing bounds the literature and to obtain the first generalization bound for PersLay.
Our next result (Lemma 2) applied perturbation- based PAC-Bayes bounds arbitrary models with (possibly) non-homee oo-hhomggeneous layers. To achieve this generality, we carefully contrasted results in [33, 40, 48] to identify the conditions (Equations 6, 7, and 9) that are sufficient to subsume the considered models as well as to extend to a broader class of models. In Section 4, we will also exploit Lemma 2 in the analysis of different combinations of neural models (e.g., GNNs and PersLay).
General recipe for PAC- BAC-Bayesian bounds for heterogeneous models
Lemma 2. Let fw X R be model with parameters w vec[Wi, Wn). If there exists E TR+ and a sequence (Si)ie(m) with S; E TK+ both of which may depend on w, and purameter-independee C₁, C2 E IR and sequence (Ni)atj) with v E (0, 1] such that: the output is bounded by C,T:
(2)ll S C,T. #eX
sup
(6)
the oulput change be bounded under small perturbation of the parameters, i.e. for all u = (ec(UU....,u,) with ||U:ll2 S npS::
|
sup (l) Sw (x))l2 S C2T xEX
(7)
S
the following auxiliary conditions hold:
(8)
71
T1/n
C1
min
1/ <
(9)
Isi5
2C2
Then, for any 7, > with probability at least 1- over the choice of training sets S with ii.dd samples drawn according distribution DD have:
LD.O(Sw) (sw)(sw)+
max(1, || 12)22
Σ S;
hn (nh) Cin + log max
m
m
8 801
(10)
+ 0
where h is the maximum dimension across the matrices (W

---

Proof sketch. We build on the main result in [40] by extending it to a broader context. The general idea involves employing Lemma I. Following [40], we define the prior distribution P as an isotropic Gaussian with variance o² and the posterior distribution Q as a shifted isotropic Gaussian with the same variance. To achieve a tighter bound, is essential to maximize a (since the Kl--divergence scales as ())/²))); consequently, should be determined based on the parameter B3. However, since P must remain independent of the learned weights, we set a according to an approximation of the learned weights. Specifically, we define 3 = ' T 1/s, and at first consider only w such that / fall within the range |3 3] < 1/28 for some arbitrary B. an approximation. We then select a based on this approximation, 3. At this point we can apply Lemma for all w such that | falls into the defined earlier interval. To account for other values of 8, we establish finite grid across the relevant /3 values and choose an appropriate 3 for each interval on the grid. Finally, a union-bound argument across all 33 values provides the final result. Although Equation 7 and Lemma I have their own constraints on the random perturbation, the above steps outline a method to set the variance a that satisfies these constraints and maintains independence from the learned weights.
Table 2: Application of Lemma 2 to MLPs and GNNs. The detailed proof of the lemma applicability can be found in the Appendix E and the detailed description of the models in Appendix B. Here provide brief description. We consider n-layer multilayer perceptron (MLP) with weights Wi,... W,, After layer i apply Lip.-Lipschhtz activation function for i E [n 1]. Every input is contained in fz-ball of radius B. We consider n-layer GCN with weights Wi..., W.. After layer i we apply Lip.-Lipschitz activation function. Every node feature of the graph is contained in ba-ball of radius B and the maximum degree of the node is d 1. We denote Lip = Lip,
Lip We consider n-layer (n > 2) MPGNN with weights W1, W2. W3 with activation functions g, o, P with corresponding Lipschitz constants. We denote C = Lip,
Il. A = || WaallalWalb Wall and
Comparing to [33] do not add Lip, to and instead of Wi we have W3.
Model (reference)
T
S
C1
C2
MLP (Neyshabur et al. [40])
||Wl12
B Lip
eB Lip
on
1=1
GCN (Liao et al. [33])
II
|Will
|
a B Lip
ed - B Lip
6n
GCN (Sun and Lin [48])
Walll
||ill
B Lip
eB Lip
MPGNN, dC f 1 (Liao et al. [33])
X
[Wlll*
B Lips
eBn Lips
6n
MPGNN. dC (Liao et al. [33])
A
|Will
Bn Lip
eBn² Lip
6n
*S²- -min(dC, (
Discussion. We note that Lemma 2 requires choosing values for the variables (S)) and T. In this regard, one might set St as the spectral norm of the weight matrix W., i.e., S = || Wall.. and make T' equal to II, St. In this case, the condition in Equation 8 is satisfied - the geometric mean is always smaller than or equal to the arithmetic mean. Regarding the variables (m:).. typical choice is to set 1 = (1/x). By doing so, our bound implicitly depends on n also through 1):-
The role of Equation is to constraint w to non-trivial parameter spaces. In particular, if T is too small, the magnitude of the model output might not be sufficient to distinguish different inputs up to a margin y. In this case, the model would have large empirical loss. In turn, Equation 7 is directly associated with the condition in Lemma 1, enabling us to use it.
As discussed, Neyshabur et al. [40] assume pectrally-normallinn assumption, introduce the conditions in Equation 8 and Equation 9, which allow to pick perturbations that meet the condition in Equation 7, again justifying the application of Lemma 1.
weight matrices. To avoid this
The bound also includes somewhat unconventional term, max (1, |w [w]]]] While this technical term allows for a more concise proof, we note that it does not impose suboptimality. More specifically, in most real-world cases, the squared norm of w is greater than 1. See Appendix I for discussion.
5

---

Applying Lemma 2 to MLPs and GNNs. As previously mentioned, using Lemma 2 involves defining the variables T. (S,) (1t);, C₁ C2 to meet all conditions in Lemma 2's statement. Typically, this definition comes naturally from the perturbation analysis of the model. To illustrate the power of Lemma 2. Table shows how we can apply it using the perturbation analysis for MLPs and GNNs provided in [33, 40, 48). Detailed proofs are given in Appendix E. Importantly, we note that we do not make any additional assumption beyond those in the original papers we state all assumptions before each proof in the Appendix for clarity.
Notably, our approach generalizes results by Neyshabur al. [40] and Liao et al. [33] to MLPs/GCNs with different activation functions note that the original works only consider ReLU activations. For inherently non oon-homogeneous models like MPGNNs, our method leads to tighter bounds in several settings. We provide comparison between our bounds and previous ones in Appendices F and G.
Applying Lemma 2 to PersLay. Next, Corollary provides PAC-Bayes bound for PersLay under fixed filtration functions - see Appendix H for a discussion about filtration functions. To the best of our knowledge, this is the first generalization result for vectorization schemes of persistence diagrams. Again, the proof consists of verifying if the requirements of Lemma 2 are met. For readability, we omit the proof and provide only the constant weighting function case in the main text, proof as well as the arbitrary weighting function case can be found in Appendix E. The perturbation analysis of PersLay is also given in the supplementary material (Lemma 10).
Corollary 1 LPersLay with constant weighting function). Let fw G G with = vee[W(s) be a PersLay where W()) denotes the parameters of the goint-tranffrrmation function, 4p Let Dg be a mapping from graphs to (extended) persistence diagrams with a fixed filtration function and B such that max max |lpl|2 S B, then fw satisfies the requirements of Lemma 2 with:
GEG pEDg(G)
T = TT1)) and
== 1| and " 1=
C = 202 and C2 2A2 max (eax(lipp() (Lip(p) c(+))
where
A A max card GEg
if Agg = "sum"
A1 1, 1, = 3
if Agg "k-max" or "mean"
and
N max(1, || max [|](())
O Bvh
Lip
if Φ = A
1
if r
VT
TVC
if + Y
||
v3 ma, B}
max B}
PersLay's 's special cases. Carrière et al. [5] designed PersLay with flexibility in mind to subsume commonly used persistence vectorization schemes in the literature. Consequently, we can obtain bounds for these schemes - we provide the values of C2 (divided by 2) which is enough to compare the schemes since everything else is the same in the constant weighting function case:
Persistence k-landscapes [4] Persistence Images [1] Persistence Silhouettes [6]
3 3axx(BVh.1)
card- max{ Vh, + card max(BVh,) 13
where card is the maxged Dg(G). If "images" and "silhouettes" use "sum" an aggregating func- tion, then our generalization analysis suggests that "k-landscapes" would have stronger guarantees. If these schemes use "mean" an aggregating function, then C2 for "k-landscapes" would be at most C2 for "silhouettes", and the result of comparison of "k-landscapes" and "images" could be in favor of both "landscapes" and "images" depending on chosen parameters and B.
4 Compositional PAC-Bayes
In this section, we present two lemmas (Lemmas 3 & 4) that allow us to compose models satisfying Lemma 2 requirements. At the end of the section (Corollary 2), we showcase our framework by

---

getting generalization bounds for combinations of GNNs and PersLay. For readability, here we provide informal statements and defer the formal ones to the Appendix (Lemma 5, Lemma 6).
In particular, Lemma 3 establishes that the composition of MLPs with models that satisfy Lemma also satisfy it. As result, we can derive PAC-Bayes bounds for heterogeneous models that leverage MLPs using our framework in a straightforward way. This is particularly relevant since deep learning models often employ learnable feature extractors followed by MLPs as classification heads.
Lemma 3 (Informal; Composition with MLP). Let f be an MLP and g be a model satisfying Lemma requirements, then f o g also satisfies Lemma 2 requirements.
In addition, we show in Lemma 5 (Appendix) that this result also extends to an arbitrary number of models beyond MLPs. In particular, the result holds whenever we can upper bound output deviations due to perturbations on parameters and inputs, i.e., SUPzEx IIf Ar) fw (2r)lla is bounded.
Our next lemma suggests that models satisfying Lemma 2 requirements are closed under parallel concatenation. We note that combining two (or more) models in parallel is also a common design choice in deep learning. For instance, this encompasses ensemble methods [13].
GNNs [22] and
Lemma (Informal; Models in parallel). Let Jt. f2 be two models satisfying Lemma requirements and g be aggregating Apsschtiz,fucttin Then, ((f(()), (2(-)) also satisfies Lemma 2 requirements.
We also provide generalization of this lemma in the Appendix (Lemma 6) for 2 models in parallel. It leads to tighter bounds than a naive 2- sequential application of Lemma 4.
Corollary 2 (Informal). By combining the results for MLPs, GCNs, MPGNNs (Table 2) and that for PersLay (Corollary 1) with Lemma 3 and Lemma 4, we can get generalization bounds on various compositions of these models. In particular, for GNNs with persistence (see Figure 1), we huve
* T for the overall model scales with the product of PersLay's 's and GNN's T variables;
. C and C2 of the overall model scale linearty with C1, C2 of PersLay and GNN.
Despite the generality of our results, Corollary 2 demonstrates the benefits of our framework in the domain of graph representational learning. To the best of our knowledge, this the first result providing generalization guarantees for graph neural networks combined with persistence vectorization schemes. Furthermore, our findings can aid practitioners in making informed architectural decisions to enhance the generalizability of their models. Specifically, in the case of combining PersLay with GNNs, a tighter bound can be achieved by selecting a PersLay dimension that is considerably smaller than the GNN dimension. Failing to do so may result in a bound dependency on the width of the form Ohv/In h) rather than O(v In h). Additionally, we recommend using aggregation functions such as "mean" or "k-max" instead of "sum" as the latter introduces a term maXGeg card(G) (G) to the bound, which may be large in practical scenarios.
5 Related Works
Expressivity and generalization of GNNs GNNs have achieved state-of-the-ar performance across various applications [16, 28, 45, 51, 54], and have garnered significant attention. Maron et al. [35], Xu et al. [55] analyzed the representational power of GNNs in terms of the 1-WL test, revealing theoretical limits on their expressivity. This has motivated a surge of works aiming to go beyond 1-WL with GNNs [e.g.. 32). Regarding generalization, Scarselli et al. [46] provided upper bounds on
the order of growth of VC-dimension for GNNs. Garg et al. [14] presented the first data-dependent generalization bounds for GNNs via Rademacher complexity. Recently, Morris et al. [39] employed the WL test alongside VC-dimension to gain insights about the generalization performance of GNNs. For details about the expressivity and learning of GNNs, we refer to Jegelka [24].
Learning theory and PH. Birdal et al. [3], Dupuis et al. [8] and Chen et al. [7] investigate connections between learning theory and topological data analysis. In particular, Birdal et al. [3], Dupuis et al. [8] explored the concept of PH dimension as a complexity measure to analyze generalization. Chen et al.
[7] proposed topological regularizer to simplify decision boundaries by penalizing non-essential topological features. In contrast, we apply learning theory to derive data-dependent generalization bounds for arbitrary heterogeneous layers, specifically targetting persistence-aware GNNs, and intro-
duce a regularizer informed by these bounds to guide the design of robust and generalizable models.
7

---

METTAG
PROTRINS
NET1
PVDR IMDD-RINAAS RINARY
1.0
1.3
2.
01.5
03
1-0 110000
(r
-03
(r (11000000)))
( 1140-0000
(2 1000000000
2000
300
2000
3X0
300
Figure 2: PersLay classifier: spectral norm vs. generalization gap. Overall, our bound on the spectral norm of the weights is highly correlated with the generalization gap.
DHFR
MUTAG
PROTEINS
NCI
IMDB HINARY
1.00
100
Ir 64)
0.
Orchard
11.20
0.5
W
Figure 3: PersLay classifier: width vs. generalization gap. The dependence of the empirical gap on the model width is captured by our bound. We obtain high average correlation for all datasets.
PAC-Bayes. The PAC-Bayes framework [37, 38] allows us to leverage knowledge about learn- ing algorithms and distributions over the hypothesis set to achieve tighter generalization bounds. Remarkably, Neyshabur et al. [40] presented a generalization bound for feedforward networks in terms of the product of the spectral norm of weights using a PAC-Bayes analysis. Liao et al. [33] provided PAC-Bayes bounds for GNNs, and Sun and Lin [48] enhanced their analysis considering the adversarial case as well. In a seminal work, Dziugaite and Roy [9] optimized PAC-Bayes bounds
directly to obtain non-vacuous generalization bounds for deep stochastic neural networks.
6 Experiments
To illustrate the practical relevance of our analysis, we now consider the generalization of persistence- aware models on real-world datasets, and report results for regularized models based on our bounds. In particular, we conduct two main experiments. The first one aims to analyze how well our bounds capture generalization gaps as a function of model variables. The second assesses to which extent structural risk minimization algorithm that uses our bound on the weights spectral norm improve generalization compared to empirical risk minimizers. We implemented all experiments using PyTorch [42], and implementation details are given in the Appendix J. Our code is available at https: /tgps://gitor thub. com/Aalto- Aalto Maltoo-uMM//CA Baaal//Compsiiional---11. -wc-oonaa--A--aeeeeee
Datasets and evaluation setup. We six popular benchmarks for graph classification: DHFR, MUTAG, PROTEINS, NCTI, IMDB-BING BINARY, MOLHIV, which are available as part of TUDatasets [26] and OGB [21]. We model selection. Here, we consider both PersLay Classifiers and GNNs with persistence models with constant weight functions and Gaussian point transformations. For the experiments with GNNs, we kept only the larger datasets (and added results for the NCI109 dataset). Regarding filtration functions, we closely follow [5] and use Heat kernels with parameter values equal to 0.1 and 10.
80/10/10% (train/val/test) split for all datasets when we perform
Dependence on model components. Figure 2 and Figure 4 show the generalization gap (measured as I.D,0 I.s,)=)) and the bound on the weights spectral norm (7 from Lemma 2) over the training epochs for PersLay Classifier and GNNs with persistence, respectively. To evaluate how well our bound captures the trend observed in the empirical gap, compute correlation coefficients between the two sequences across different seeds and report their mean and standard deviation for each dataset. Overall, the coefficients are greater than 0.7 in out of 9 experiments, indicating good correlation.
Figure shows the empirical gap and our estimated bound as a function of the model's width for the PersLay classifier. Again, we compute correlation coefficients between the two curves and find they are highly correlated (with an average correlation above 0.91 on 4 out of 5 datasets). Also, we note that these curves are obtained at the final training epoch. We report additional results across different epochs and parer-parameters in the supplementary material, Again, these results validate that our theoretical bounds can capture the trend observed in the empirical generalization gap.
8

---

NCII
NCT109
PROTEINS
IMDB-BINARY
1.5
1.0
Generalization
1.0
Grmemiizzikn
Our bourd
1.01
0.5
0.5
0.5
0.0
6.0
0.77
-0.5
0,68
-0.5
0,9020013
-0.5
0.7200100
1000
2000
1000
2000
1000
2000
1000
2000
Ejpoch
Epoch
Ejech
Epoch
Figure 4: GNNs with persistence: empirical gap vs. PAC-Bayes bound. Again, there is positive and high correlation between our bound and the observed generalization gap.
Regularizing PersLay. We compare variants of Perslay trained via ERM (empirical risk minimiza- tion) and a regularized version with loss given by Ls. ta /n2 In 123²; a, is a hyper-parameter proof sketch of Lemma 2
that balances the influence of the two terms and 3 T TE, 1/s. in Section 3. This is similar to a weight-decay regularization approach, with the spectral norm of 2, selected via hold-out validation. We note that PersLay classifier does not use node features, it only exploits graph structures.
weights appearing in B. Here, consider models with
Table Comparison of PersLay with and without spectral norm regularization. We report accuracy statistics (except for MOLHIV, which uses AUROC) computed over five independent runs In 5 out of 6 cases, the models using SpecNorm achieve better test results.
Method
DRFH
MUTAG
PROTEINS
IMDB-B
NCI1
MOLHIV
PersLay (ERM)
0.71 = 0.04
0.88
0.02
0.65 = 0.03
0.65 + 0.01
0.68
0.01
0.7005
0.0177 0.7185 0.0106
PersLay SpecNorm)
0.72 0.02
0.94 0.01
0.72 0.01
0.70 = 0.01
0.68
0.01
Table 3 reports accuracy results (mean and standard deviations) computed over five runs. Overall, the regularized approach significantly outperforms the ERM variant despite the use of small-sized networks. On 5/6 datasets, PersLay with spectral norm regularization the best-performing model.
Regularizing GNNs with persistence. We now evaluate the impact of using our bound to regularize different GNNs combined with persistent homology (PersLay) in parallel mode. We consider GCN [28], GraphSage [16], and GIN [55] architectures. Table reports the test classification error and the generalization gap the NCI, NCI109, and PROTEINS datasets obtained over five independent runs. For our regularizer, we select the optimal penalization factor a, E {le-5, le-6, 1c-7, 1c-8} using the validation set. Overall, the results show that the regularized methods achieve smaller generalization gaps and slightly lower classification errors. In particular, our spectral regularizer leads significant drop in generalization gap in all experiments.
mean and standard deviation
Table Test classification error (0-1 loss) and generalization gap (LD,0- Ls.,) for PH-augmented GNNs. ERM means empirical risk minimizer (no regularization) We denote the best-perfont rest-performing methods in bold. In almost all cases, employing the method derived from our theoretical analysis leads to the smallest test errors and generalization gaps.
Test error
Generalization gap
GNN
Dataset
ERM
SPECNORM
ERM
SPECNORM
NCI
0.22 1 0.01
0.21 + 0.02
0.19 0.01
0.01 +:2 0.06
GCN
NC1109
0.28 + 0.00
0.28 + 0.02
0.25 = 0.00
0.12 + 0.03
PROTEINS
0.31 131+0.00 0.01
0.27 + 0.02
0.25 0.02
-0.02 + 0.11
NCI
0.01
0.21 0.02
0.18 0.04
-0.08 0.05
SAGE
NCT109
0.24 0.01
0.23 + 0.01
0.05 + 0.06
PROTEINS
0.27 0.02
0.26 0.02
0.25 - 0.01
-0.15 0.30
NCI
0,25 0.01
0.22 + 0.00
0.23 0.01
0.01 1 0.06
GIN
NC1109
0.24 0.01
0.24
0.22 0.01
0.00 - 0.08
PROTEINS
0.29 + 0.02
0,30 0.03
0.26 0.03
0.07 + 0.18

---

7 Conclusion, Broader Implications, and Limitations
We derive the first generalization bounds for neural networks that appeal persistent homology for graph learning. Notably, the analyzed framework (PersLay) offers a flexible and general way to extract vector representations from persistence diagrams. Due this generality, our analysis covers several methods available in the literature. The developed framework also allows to analyze composite models like, GNNs combined with PersLay. Our constructions involve a perturbation and generalization behavior analysis of ton-homogeneous networks in rather general setting, which poses specific technical challenges.
While we provide valuable insights and methodologies, we would like to underscore the need for future investigations to delve into PH schemes that encompass parametrized filtration functions. Nonetheless, while some works showed gains using learnable filtrations [20], others have reported no benefits and advocated fixed functions instead [5, 34]. Moreover, the tightness of our bounds can further be improved since there is still considerable gap between empirical results and the theoretical one. By shedding new light on the generalization of machine learning models based on persistent homology, we hope to contribute to the community by providing key insights about the limits and power of these methods, paving the path to further theoretical developments on PH-based neural networks for graph representation learning.
Acknowledgments
VG acknowledges support from the Research Council of Finland (grant decision 342077) for the project "Human-steered next-generation machine learning for reviving drug design", and the Jane and Aatos Erkko Foundation (grant (03) for "Biodesign: Use of artificial intelligence in enzyme design for synthetic biology". VG also thanks the Finnish Ministry for Education and Culture for their support via the "MEC Global Programme pilot USA" initiative. AS acknowledges the support from the Conselho Nacional de Desenvolvimento Científico Tecnológico CNPq (404336/2023-0) and the Silicon Valley Community Foundation through the University Blockchain Research Initiative (Grant #2022-1996111 KB thanks Aalto University for the support during the internship.
References
[1] Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier. Persistence Images: A Stable Vector Representation of Persistent Homology. Journal of Machine Learning Research, 18(8):1-35, 2016.
[2] M.E. Aktas, E. Akbas, and A.E Fatmaoui. Persistence homology of networks: methods and applications. Applied Network Science, 2019.
[3] Tolga Birdal, Aaron Lou, Leonidas Guibas, and Umut Şimşekli. Intrinsic Dimension, Persis tent Homology and Generalization in Neural Networks. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[4] Bubenik. Statistical topological data analysis using persistence landscapes. Journal of Machine Learning Research, 16:77-102, 2015.
[5] Mathieu Carrière, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda. PersLay: A Neural Network Layer for Persistence Diagrams and New Graph Topological Signatures. In Artificial Intelligence and Statistics (AISTATS), 2020.
[6] Frédéric Chazal, Brittany Terese Fasy, Fabrizio Lecci, Alessandro Rinaldo, and Larry Wasser- man. Stochastic Convergence of Persistence Landscapes and Silhouettes. Proceedings of the Thirtieth Annual Symposiun on Computational Geometry, 2014.
[7] Chao Chen, Xiuyan Ni, Qinxun Bai, and Yusu Wang. A Topological Regularizer for Classifiers via Persistent Homology, October 2018
[8] Benjamin Dupuis, George Deligiannidis, and Umut Şimşekli. Generalization Bounds with Data-dependent Fractal Dimensions. arXiv e-prints, 2023.
10

---

[9] Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Conference Uncertainty in Artificial Intelligence (UAI), 2017.
[10] H. Edelsbrunner and J. Harer. Computational Topology- an Introduction. American Mathemat- ical Society, 2010.
[11] Herbert Edelsbrunner and John Harer. Persistent homology-asurree In Jacob E. Goodman, János Pach, and Richard Pollack, editors, Contemporary Mathematics, volume 453, pages 257-2822 American Mathematical Society, 2008.
[12] Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar, Learning theory can (sometimes) explain generalisation in graph neural networks. In Advances in Neural Information Processing Systems (NeurIPS), 2021.
[13] M.A. Ganaie, Minghui Hu, A.K. Malik, M. Tanveer, and P.N. Suganthan. Ensemble deep learning: A review. Engineering Applications of Artificial Intelligence, 115, 2022.
[14] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and Representational Limits of Graph Neural Networks. In International Conference on Machine Learning (ICML). 2020.
[15] Gilmer, S. S. Schoenholz, F. Riley, O. Vinyals, and E. Dahl. Neural message passing for quantum chemistry. In International Conference on Machine Learning (ICML), 2017.
[16] William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large
graphs. In Conference on Neural Information Processing Systems (NeurIPS), 2017.
[17] Felix Hensel, Michael Moor, and Bastian Rieck. A Survey of Topological Machine Learning Methods. Frontiers in Artificial Intelligence, 4, 2021. ISSN 2624-8212.
[18) Christoph Hofer, Roland Kwitt, Mare Niethammer, and Andreas Uhl. Deep Learning with Topological Signatures. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
[19] Christoph Hofer, Florian Graf, Bastian Rieck, Mare Niethammer, and Roland Kwitt. Graph filtration learning. In International Conference on Machine Learning (ICMI.), 2020.
[20] M. Horn, E. De Brouwer, M. Moor, Y. Moreau, Rieck, and K. Borgwardt. Topological graph neural networks. In International Conference Learning Representations (ICLR), 2022.
[21] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benehmark: Datasets for machine learning on graphs. arXiv preprint arXiv:2005.00681 2020.
[22] Johanna Emilia Immonen, Amauri H. Souza, and Vikas Garg. Going beyond persistent ho- mology using persistent homology. In Advances in Neural Information Processing Systems (NeurlPS), 2023.
[23] Jan Reininghaus, Stefan Huber, Ulrich Bauer, and Roland Kwitt. A stable multi-scale kernel for topological machine learning. 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2015.
[24] Stefanie Jegelka. Theory of graph neural networks: Representation and learning. ArXiv, abs/2204.00697,, 2022.
[25] Haotian Ju, Dongyue Li, Aneesh Sharma, and Hongyang R. Zhang. Generalization in graph neural networks: Improved pac-bayesian bounds graph diffusionn. In International Conference on Artificial Intelligence and Statistics, 2023.
[26] Kristian Kersting, Nils M. Kriege, Christopher Morris, Petra Mutzel, and Marion Neu- mann. Benchmark data sets for graph kernels, 2016. URL http:://graphternels.ccm uu-dortmund.ccm de.
[27] D. Kingma J. Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations (ICLR), 2015.

---

[28] Thomas N. Kipf and Max Welling. Semi- Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
[29] Genki Kusano, Yasuaki Hiraoka, and Kenji Fukumizu. Persistence weighted Gaussian kernel for topological data analysis. In International Conference on Machine Learning (ICML), pages 1004-2013 2016.
[30] John Langford and John Shawe-Taylor. PAC-Bayes & Margins. In Advances in Neural Information Processing Systems (NeurIPS), volume 15. MIT Press, 2002.
[31] Tam Le and Makoto Yamada. Persistence Fisher Kernl:: A Riemannian Manifold Kernel for Persistence Diagrams. In Advances in Neural Information Processing Systems (NeurIPS), 2018.
[32] P. Li, Y. Wang. H. Wang, and J. Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
[33] Renjie Liao, Raquel Urtasun, and Richard Zemel. A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks. In International Conference on Learning Representations (ICLR), 2020.
[34] Yuankai Luo, Lei Shi, and Veronika Thost. Improving self self-supervised molecular representation learning using persistent homology. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[35] H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[36] Sohir Maskey, Ron Levie, Yunseok Lee, and Gitta Kutyniok. Generalization analysis of message passing neural networks on large random graphs. In Advances in Neural Information Processing Systems (NeurIPS). 2022.
[37] David McAllester. Simplified PAC-Bayesian Margin Bounds. In Bernhard Schölkopf and Man- fred K. Warmuth, editors, Learning Theory and Kernel Machines, Lecture Notes in Computer Science, pages 203-215, Berlin, Heidelberg, 2003. Springer.
[38] David A. McAllester. PAC- BaC-Bayeiian model averaging. In Proceedings of the Twelfth Annual Conference on Computational Learning Theory, COLT '99, pages 164-170. Association for Computing Machinery, July 1999.
[39] Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe WL meet VC. In Interna- tional Conference on Machine Learning (ICML), 2023.
[40] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-Bayesian Approach to Spectrally-Normaaizze Margin Bounds for Neural Networks. In International Conference on Representation Learning (ICLR), 2018.
[41] Vahid Partovi Nia, Guojun Zhang, Ivan Kobyzev, Michael R. Metel, Xinlin Li, Ke Sun, Sobhan Hemati, Masoud Asgharian, Linglong Kong, Wulong Liu, and Boxing Chen. Mathematical Challenges in Deep Learning. ArXiv e-prints: 1546,, 2023.
[42] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. Viiooo, Z. Lin, A. Desmaison,
L. Antiga, and A. Lerer. Automatic differentiation in pytorch. In Advances in Neural Information Processing Systems (NeurIPS- - Workshop), 2017.
[43] Giovanni Petri, Martina Scolamiero, Irene Donato, Francesco Vaccarino, Thomas Gilbert, Markus Kirkilionis, and Gregoire Nicolis. Nenworks and Cycles: A Persistent Homology Approach to Complex Networks. Proceedings of the European Conference on Complex Systems 2012. Springer International Publishing, 2013. ISBN 978-3-319-0039443.
[44] Bastian Rieck. On the Expressivity of Persistent Homology in Graph Learning, arXiv e-prints. (arXiv:2302.0988) 0098220 2023.
[45] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2009.
12

---

[46] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The aapnik-chervonenkee dimension of graph and recursive neural networks. Neural Networks, 108:248 2598, 2018.
[47] Milad Sefidgaran and Abdellatif Zaidi. Data-dependent Generalization Bounds via Variable-Size Compressibility. arXiv e-prints, 2023.
[48] Tan Sun and Junhong Lin. Pac-bayesian adversarially robust generalization bounds for graph neural network. arXiv e-prints, 2024.
[49] Joel A. Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Compu- tational Mathematics, 12(4):389-434, August 2012. ISSN 1615-3375, 1615-3383.
[50] L. G. Valiant. theory of the learnable. Communications of the ACM, 27(11):1134-114; November 1984. ISSN 0001-0782. doi: 10.1145/1968 1972.
[51] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations (ICLR), 2018.
[52] S. Verma and Z.-L. Zhang. Stability and generalization of graph convolutional neural networks. In International Conference on Knowledge Discovery Data Mining (KDD), 2019.
[53] Yogesh Verma, Amauri H Souza, and Vikas Garg. Topological neural networks go persistent, equivariant, and continuous. In International Conference Machine Learning (ICML), volume 235, 2024.
[54) Feng Xia, Ke Sun, Shuo Yu, Abdul Aziz, Liangtian Wan, Shirui Pan, and Huan Liu. Graph Learning: Survey. IEEE Transactions on Artificial Intelligence, 2(2):109-127, April 2021. ISSN 2691-4581. doi: 11100/9A1.221.307600
[55] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations (ICLR), 2019.
[56] Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan Salakhutdinov, and Alexander Smola. Deep sets, 2018
[57] Qi Zhao and Yusu Wang. Learning metries for persistence-based summaries and applications for graph classification. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
[58] Qi Zhao, Ze Ye, Chao Chen, and Yusu Wang. Persistence Enhanced Graph Neural Network. In International Conference on Artificial Intelligence and Statistics (AISTATS), 2020.
[59] Yangze Zhou, Gitta Kutyniok, and Bruno Ribeiro. OOD link prediction generalization capa- bilities of message-passing GNNs in larger test graphs. In Advances Neural Information Processing Systems (NeurIPS), 2022.
13

---

A
Notation
Table 5 summarizes the main mathematical symbols and abbreviations used in this work.
Table 5: Summary of notation and abbreviations.
Notation
Description
G = (V, F)
arbitrary graph with vertices V and edges F
(g)
persistence diagram of cardinality card(Dg(())
(-))
arbitrary weight function in the PersLay ay architecture, R² + IR
W
parameter vector (matrix) of the (weight) function
h
maximum dimensionality of the parameter vectors (matrices)
+P()
arbitrary point transformation, in the PersLay architecture RR² + Rd
(a,, (pr,
TriangleGGaussian/Ling point transformation ith parameter value(s) of a point transformation - following Carrière et al. [5]
fa
W(v)
vector comprising parameters of the point transformation yo, i.e. W veo((ti)
Agg
arbitrary aggregation function (typically sum, mean k--max)
PERSLAY
mapping from persistence diagrams R² (Equation 2)
K
number of classes
Lip;
Lipschitz constant of activation function ith layer
V
non- linear Lip,- Lipschitz activation function before ith layer
ML.
multi-layer perceptron with non-linear Lips-hip activation functions
vec(.)
function that converts its input to single vector
D
data distribution
S, m
S is a training set consisting of m input pairs (x.
margin scalar used in the margin- baaeed loss
(.s,((w)
empirical error (y-margin loss) of hypothesis (with parameters w) on S generalization error (7-margin loss) of a hypothesis g (with parameters w) on 2>
(9w)(9w)
82
L-2 norm
B
the maximum norm of the input to the with respect to & norm.
DKL
KL-divergence between two distributions
|-|
absolute value
||
|2. |l
F
matrix (or vector) norm induced by vector 2-norm Frobenius norm a matrix
U
perturbation of the model parameter
ro, 11,, vig
number of parameter matrices (vectors)
k
typically the number of models compose
T
quantity of weights bounding max nom=m and max perturbation of a model in Lemma 2
S
correcting quantity appearing in max perturbation bound of a model in Lemma 2
C1
constant appearing in max norm upper-bound of the model output in Lemma 2
C2
constant appearing in max perturbation of a model upper-hound in Lemma 2
M): 1
maximum allowed ratio of ||2 to ||S.]| min of f); in Lemma 2
8,9
T Σ
arbitrary approximation of 3 appearing in Lemma 2
1
14

---

B
Model descriptions
MLP.
H₂ = 2/ (W
(k-th layer),
(11) where H₂ E IR are the vectors computed after layer k, and W E IR 1xh* & E [m] are the parameters in the k-th layer, and we let Hu =. th,, k [n 1] are some dlement-wise non-linear Lip,, Lipschitz functions. Note that we change (number of layers Neyshabur et al. [40] notation) to to be consistent with the number of parameters notation.
H, Wn, H,,,,
(Final layer);
GCN.
H₂ (n(PoHH--WW)
(k-th Graph Convolution Layer),
H [V] 11
(Readout layer),
(12)
where H3 E RIVixbe kE [n 1] are the node representations in each layer, H,, E RIxK is the readout, and W& Rh 1xk,, [n]] are the parameters in the k-th layer. And we let Ho Z, where Z is the matrix constructed from node features, 2u for v E V. The matrix Pa E R/V | is related to the graph structure and (*),,,, k E [n- 1 1] are some element wise non-linear L -Lipschit mappings. Practically, for GCN, we take Pg as the Laplacian of the graph, defined as Đ-1/2 Á 11/2
where the adjacency matrix with +1 on the diagonal and か = diag [Σ A.j, i E (IV1) is
the degree matrix of Á. Note that we sightly changed (comparing to Liao et al. [33], Sun and Lin [48]) the notation be consistent: instead of l, number of layers, we have n. instead of n, number of nodes, we have [V] and instead of we have yh; as activation functions.
MPGNN.
M₁- = ([CoeHHk-))
(k-th step Message Computation)
M₁ MR
(k-th step Message Aggregation) (k-thh step Node State Update) (Readout Layer),
H₂ Φ (XW1 + p (Mr) W2)
H. [V 111
(13)
where k E [n - 1]. H2 E VIX are node representatiions/saaess and Hn FI*K is the output representation. Here we initialize Ho O. WLOG, we assume Vk [n 1]. Hs E xV and Mr e IV|x since h the maximum hidden dimension. Cin E [V and Cout E R V|x[ are the incidence matrices corresponding to incoming and outgoing nodes' respectively. Specifically, rows and columns of On and Cout correspond nodes and edges respectively. C₁ [i indicates that the incoming node of the j-th edge is the i-th node. Similarly, Coulli.) = indicates that the outgoing node of the j-th edge the i-th node, 9. Ø, P are nonlinear mappings, e.g., ReL.U and Tanh. Technically speaking, individual node/edge. However, since we share these functions across nodes/edges, we can naturally ((( :)). By
T + h Ø Ie + RR and p R + I operate on vector-states of
generalize them to matrix-states, e.g., RRV XΛ - RVVxx where (( doing so, the same function could be applied to matrices with varying size of the first dimension. For simplicity, we use g, d. P to denote such generalization to matrices. We denote the Lipschitz constants of g, ó, o under the vector 2-norm Cg., Co, Cp respectively. We also assume ( 0. (0) = O, and p(0)= = 0 and define the percolation complexity as = C, Cl following Garg et al. [14]. Note that sightly changed (comparing to Liao et al. [33], Sun and Lin [48]) the notation to be consistent: instead of number of layers, we have n, instead of n, number of nodes, we have [V| and instead of Wi, parameter matrix, we have W3.
For undirected graphs, convert each edge into two directed edges.
15

---

C Proofs of main lemma and composition lemmas
Lemma 2. Let fw : X + R be a model with parameters w veo[W], Wi.... l.... Wr). If there exists
T E IR and S; E IR for i E [m]] depending on Wi,..., Wni C1: C2 > 0; E (0, 1J E [n] such that:
maximum norm of the output is bounded by T and C1:
max
|| (2))l2 CiT,
(14)
=EX
maximum change of the output with perturbed weights, vee(U1, Un], is bounded if the perturbation is small, ||U,1l2 S S,S.
U
max xEX
[1 [w(x))l2 S C2T
(15)
S
arithmetic mean of S; inverses is at least the nith root of inverse:
1
2 1
(16)
S
T1/n²
minimum i7 is at most the ratio of C₁ and 2C2:
min S C1 I8iS
(17)
202
then for any Y, > with probability least 1 8 over the choice of training set S of size sampled accordingly to some data distribution we have the bound on the generalization gap:
LD.O(Sw) (Sw)
max(1, /|/2]22
Σ
(h nn)) C77-2 + log m max { 11 8
S.
(18)
+ +0
where & is the upper bound for dimensions of W..
Proof. First, we note that if such that C,T < 3/2 then this imply for any e [K]
max w (x); max XEX
[w S CTT 2
xEX
where we used Equation 6 and the fact that every coordinate of the vector is at most fg-norm of the vector. In this case the empirical loss would be equal to one, since index can satisfy fw (x); 2 y + max fw (x) and the inequality in Equation 10 becomes trivial since generalization
*$1
not be greater than 1.
So from now on we consider such that C,T 2 7. Moreover we note that:
2 ? 7
7
CT
(19)
2
201
We denote
T
(20)
S
Following Neyshabur et al. [40] and Liao et al. [33], we consider the prior A'00, 1) and random perturbation ~ ~/(0, o² IT). Note that the a of the prior and the perturbation are the same
16

---

and will be set according to 3. More precisely, we will set the based on some approximation 3 of 3 since the prior cannot depend on any learned weights directly. The approximation 33 is chosen to be a cover set which covers the meaningful range of B. For now, let us assume that we have fixed [ and consider 3 which satisfies | B1 S sB for some & > 0. Note that this also implies:
|8 - 68 -
85 1
(21)
B 5B 3 < + +38
(22)
This setup is very like the setup in Neyshabur et al. [40] and Liao et al. [33]
Choosing From Tropp [49] we know that if U E Rixh Uij NOO, o²), then
PP ( 2 t) S expxp
2hio
So applying it to U1,... Un (all of them are smaller than h x h)) and = ov2h In 4nh we have:
P ([]Ui|] S oC, &... & 11unl2 S o0)
Σ
Pl 2 o00)
(23)
o²Coz
2 1 - 2nhexp
2nhexp
In 4nh
2h
For simplicity of notation we denote C, = 22h In 4nh.
Using defined perturbation vec(U1..... Un} and Equation 23 combined with Equation 7 we get with probability at least 5:
max [fw+u(z) - fw(x))loc S max EX
(fw+u(x) - (x)ll2
zEX
1 UUel2
C.T
S
(24)
C20oCs 1
oß
< C2C T-6
If
- 7(1 8)
4C,C,3"
then the perturbation is bounded by 7 However, we need to satisfy the condition of Equation 7, i.e. vi E [n] ||U I S,. Let us find C2 2 such that:
7(1 6) 8) 4C,C,0, 3 4C,C,8
< 7(1 (1-6) 8)
(25)
and that
vi [n] oC, < n.S.
17

---

1(1 8)
(
7
(6)
oc
C.
BB8
(181)
7 n/::
17::0
4C2Com1
1+
St
(26)
(10)
4C2C.mi
201
C1
S 2C2Cs 1
(i) comes from Equation 21. (ii) we just multiplied and divided on 77S, (ii) we plugged in the
expression for B, Equation 20. (iv)
2 (v) comes from Equation
Sk
kf1
We choose
C1
C1 202 f
C. = 2C2
(27)
min 1B 15
In this case C. 2 because of Equation 9 and continuing Equation 26:
(1) where (i) comes from the fact that ij the minimum among n,8, gives us that Vi E [n] ||Ubl22 s n:S. Plugging this into expression for a, Equation 25, we get:
C.
oC, S n;S; 20,Com: 77
S
o 1(1 c) c) E)
(28)
4C2C,B 2C
At this point, we selected prior, P NO I)),, and perturbation distribution, Q NN such that the conditions of Lemma can be satisfied.
Getting the bound for weights |3 3 < e, Now, we can compute the KI--divegeence and get the bound using Lemma for case when is around B, i.e such that |B
| eB.
4C70332
(6)
OxI(O(w+ur) u)llP)
S
20
2
72
- 27
(29)
CHC
Lit
g2
(8)
I-e
w
where (i) comes from a definition, Equation 28, (ii) comes from the upper-bound on 3, Equation 22. We are ready to put this into Lemma 1:
DKI(Q(w + [P) + log 6m
Lo.ol/w) (ss,(ww)) + +4/
m
(30)
max(1, [wl]],
I+e n-
In
= (fs)
22m
where we upper-bounded || max(1, [[]][]) to simplify further derivations.
18

---

Union bound. Finally, we need to consider multiple choices of 3 so that for any 8, we can bound the generalization error like Equation 30. In order this we (i) find interval of reasonable As. (ii) define covering and upper-bound the number of balls in the covering, (iti) combine bounds for every 3 together and get the final result.
If is too large, the KL-divergence would be too large and generalization gap would be greater than 1 which thereby trivialize the bound since the generalization error cannot be greater than 1.
max
(1, [w(l]
1tt 1-t
1j2 2 +
In m
(
7Pm
(31)
(1)
(i)
CBB
2
227
mmm
where (i) holds since we remove multipliers that are greater than and In m
8 which is 2 0 and appears
sum, (ii) comes from the fact that fj S 1.
So, B 2 Ci then the bound becomes trivial.
On the other hand, if the 3 is too small, then the empirical loss would be too large since the model would not be able to classify with margin, as it was shown in Equation 19. Using this equation and Arithmetic versus Geometric mean we get the following inequality:
(8) nf
3= T
(32)
2C
1=1
where (i) comes from Equation 8 and (ii) comes from Equation 19,
Combining lower (Equation 32) and upper (Equation 31) bound on 3 we get:
Tvm m S
<
(33)
20
Ci
To satisfy the condition |3 - -3 S eB we can take en
as the radius of the covering, C. In
20
this case let us derive the upper bound for the size of the covering, |C|:
1/m
m
7
1
IC|
22mm-
(34)
20
C1
Let us consider cases:
1/n
1/a
1
1 a21
First inequality holds because function we can combine:
is monotonously decreasing on the interval (0, +oo). So.
CC < 2 max {1 c
1
(35)
It is left to apply the union bound argument for the events of Equation 30 happening with 3 taking value from äth ball. Let us denote such event E;:
C
P PEE ... & E c))= = - P(3:: not E,) 2
P(not E,) > 1 CC
(36)
19

---

Hence, if we set 8' 5 cc then with probability at least 1 - for all w we have:
IDpo(fw) I (J)+
2
max{1 1, ||
CG + log m max 1, 05
S.
+ 0
32m
Note that we substituted & with 2 and now max G appearing under logarithm comparing to Equation 30.
Lemma 5 (Generalization of Lemma 3). Let swi : + Rh,,..., Sw... Xx Rh for k E N
(1))
with w, = ve ,., Whil) } and hy K be some models that we can compose, i.e. =
(...
If there exists for j E [k] TT() depending W(i)
.... Wlf) for j E
b 561 s(1) E R depending on W .... Why); 4/1 ..... Ta 71 Thkk E (0. 1] and
(1) (k)
dt cth) E RR Chu ...., C2iy such that:
maximum output for every model is bounded as follows:
Vj (X) 1x2)()))
(37)
for j = k we can have weaker condition the same as in Lemma 2,
maximum perturbation of the oulput during small perturbation of weights, |0:100 112 S (1 (())s()) for
every model is bounded as follows:
Vj E [K], Vx, Ax E
I1f (x + Ax)
sw: (x)112 5
S cHig((
|
|x|12
n5 | l|2
(38)
s(5)) 1|2
and j = k we can have weaker condition - the same as in Lemma 2,
arithmetic mean of inverses of 5!5) is greater than noot of T());
n nl
1/ng
Vj E
[k]
(39)
T
and 17() min 1hi is upper- upper-bounded bounded by the ration c(u) and ( :E(n,]
(3)
c
Vjj
[k]
17())
(40)
2C ())
we denote n Σ nj then f meets requirements of Lemma 2 with
20

---

T=
T
and
S1:n =1
1. S/1 S(1))
(1)
(K)
(8)
Mmm
" .... Mii
..... 1/
mix
k
(find)
C = max xEdr
|||||2 max
II
C
(ind)
2
C2 = max xEd%
|x||2C,
where ind = arg min 77 and C = max jelk]
(l
I 1=+1
c
je[k]
Proof. We denote as f composition of models from jo
First we test Equation 6 by plugging in Equation 37 for every model:
f1 (x)ll2 S max ( XEA:
max xE
(41)
max
||x||
II T SCT
xEX
j=1
Next, we test Equation 7 by plugging in Equation 38 and Equation 37 for every model:
max xEX,
(u - for (x))22 S
10 10 12
))
max ch (1)((1))) XEd
[1
f 1|2 + 1| (x)ll2
Σ
sp
EII
(1)) II
nly
| 1l2
(42)
max X
||x||2
II TT))
(=+1
& my
11 ll2
S C.
ΣΣ
s(D)
To test Equation 8 we use arithmetic versus geometric mean inequality:
Ry-1
(
(+)))
ny
j=1
b
1/n2
(43)
2
(T(i)
(1)
nf
is left to verify Equation As one can notice
20
C1_
(ind)
C Ind]
17.
Lemma 6 (Generalization of Lemma 4). Let [ X' + R ..... (k) X + Rhe with W
(((( W(()), }, ..., WA vec(W((6) ?-.... wi(k)
} be some models satisfying Lemma conditions.
Agg Rh Rhe + IR such that:
VXI, E hi ... Xk, Yk E hR ||Agg(xI...., xx) Aggly Aggly......a) yx)l22 S
|x, 13y-1112 81112 Σ j=1
21

---

k
for some A >> and Og., 0) = 0. Also we denote n = satisfies Lemma conditions with either:
Σ
ng then Agg(f (),..)).....) fW2 ())
]=1
T max T()) ((k)
T
and
Sin S
S(2)
5ax
(1)
(1)
(R)
111m
77
pars Dry
M11
:
....
(ind)
G
C1 Aaxx
max
JElK]
2
(ind)
max C((i)
C2
SE(R]
or with
k
T = max
Σ
T
T())
and
Sin = -(1) ...., s(1)) S(.
...., s(h) ,..., ,...,st!! ((K)
mi
j=1
(1)
(k)
Mm
7i
Tmi
7h
mik
C (ind)
C A Amax
max kE(K]
(
max
(
JE(N]
(ind)
C2 = A max
2
(1)
jE(R]
where ind arg min ( jE[k]
Proof. First, we test Equation 6 for composite model by applying assumption about Agg and its Equation 6 for every r():
Σ TUI
max c(
max xEX
[Aggg[(( (1) (x))l S
Σ j=1
(x)l2s
j=l
jElk]
(44)
T Σ c
A Amxx jE
To test Equation 7 for composite model we again apply assumption about aggregation function and its Equation 7 version for every f());
max || Agg(( (.
wituu (x), ..., wetue (x)) Agg(s()) (()(((())))))))) (x), .... ((0) (w))
(k)
5
112
< A
Wwjuuy (x) - (x)(1) S A
000
s(o)
(45)
j=1
j=1
AT max jE(k]
C.
To test Equation 8 for composite model we employ arithmetic vs geometric mean together with Equation for every model:
T
n2
T()
& nj
T
T
2n n
2
n7
2=1
S
(T6))
1/n
(46)
j=1
TU)
1=1
22

---

k
where the last inequality comes from the fact that
II
T()
ST
j=1
C (nld 20 2 1
is left test Equation As one can notice in either case
202
D Perturbation analysis
Lemma 7. Let w = vee 3n) be vector of weight matrices of an n-layer MLP, fw : X + RKK Let vi be -iisschitz activation function after layer for [n 1]. Then for any input and input perturbation, x, Ax E X, weight perturbation, = vec(U1..... Unh. and constants, n.... yn such that for E [n]: ||U,112 & vps W:lla we have two inequalities:
n II
[x -
Lip Lip. (IWall
|x/2
(47)
[ |x|2
UU
[[ + Ax) - fww (x) S
II +
II Lip [Wlll
>
(48)
[W
where we denote Lip,. = 1.
Proof. The proof follows the Neyshabur et al. [40] with some modifications concerning the Ax and Lip, and 7/--
We denote truncated I after i + Ith layer as ((+1), First, we provide the bound on the norm of the output after 1th layer:
(ai
(ai) (49)
1
(x) (Wba (x))
(x)))l S i+ W (x))
[ Lapp, (x)ll2.
where is the definition of MLP, (ii) comes from the definition of operator norm, (iii) comes from Lipschitzness. Unrolling the recursion of Equation 49 will get us (we denote fwr (x) to be x):
(II
(1t (x) (x) 12 s
II [IWlll
Lipz k=1
|x/2
(50)
Now let us provide the bound for the perturbation after i 1th layer. We denote this perturbation as Ait1
A H+
((ttt) (x Ax) x((+1)(xx)
(4x)
(WW++1 + 11+1) (f) (x + Ax)) - W W411 (()))
(18)
[[W1+ + U1+1)
Ax)) (2 (x))) U 1 (x)) (1v)
(6v)
w. (x) + |1 (x)) m
[[i+1 + 1
(1 ( [ + 11ll
II
Lip
Wall2 (1))
k=1
A=1
[p))
(1 + M W [x/2
i+1 II
[Wallll)
Lipp k=1
|1ttall
|
(51)
23

---

where (i) comes from the definition of A++1, (ii) comes from the defintion of an MLP, (iii) add and substract U (0) (x)), (iv) comes from triangle inequality combined with operator norm definition, (v) comes from the definition of 7,+1, Lipschitzness and Equation 50, (vi) comes from multiplying and dividing by [[ the second term. Now we unroll the recursion of Equation 51
A++1 S (1 M
(1)
[ A, |||||
II
i+1
Walll
Lips
II Lip&
U ll
(8))
S
(
1+1
++1
x+11
i+1
1
(111)
1 + Tk
II Lipk
|| + ||x||2
II
II Lipx
S
Wael2
A=1
k=1
(Ri1)
(1axI1=
1 +
me
II k=1
[W&lla
II
Lips
|1xx|
|||||
[W&ll2
(52)
where (i) comes from Equation 51, (ii) comes from unrolling the recursion A., (iii) comes from the fact that + 2 1.
Lemma (GCN perturbation analysis). Let fw x R-K with w ( 1,,.., wn} be a n-layer GCN model. Let s/s be Lip, activation fanctions after layer E in 1.. If f B E R are such that: Vi E [n] ||U:|| S Will2 and VG E X, Vu E G 120/2 S B, and VG X,
Un).
G is simple and have maximum degree of d, then for any G (V, E, 2) E
1 VV
U1ll2
fww fw (G)22 -
1
Pa
II Lip |W
Σ
W:l12
U1ll12
$ eB
II i=1
Lip, |Wlll2
(53)
|Will
|ull
$ eea(n-11/2 1)/2
II Lip,
Wall2
where Z RlVixd, is the matrix consisting of 2u for u E V, and Pa is Laplacian of the graph G which is equal to D-1/2 AD-1/2 where A is adjacency matrix with +1 the diagonal and
ò- diag Σ Ag E [[V]) and is maximum degree of a graph in X.
Proof. The proof follows [48] except for the fact that add Lip, to the bound. This change is straightforward, however, for the completeness of the picture we provide this proof here. The detailed description of the architectures can be found in Appendix B.
First we prove two helpful propositions
Proposition 1. For any matrix A E paxm B E IRP we have,
|AB|| & ||
Proof. Let x.. a. be ith row of AB and A respectively, then we have:
|ABIE S
a
a
B
la | = ||
Proposition For any undirected graph G= (V, F), les A E [ be the adjacency matrix, D diag(D,..... Di....,Dyv Dvv be the degree matrix, and d ( be the maximun degree,
24

---

where Di - Ej Aej, E [V]]. Then we have,
(i) ||Al|2 S d;
Σ Ag i E (vi)
(ii) [ à Ań- 1 $11 11, where À == A T and Î diaggD Di...., D(v diag
Proof. For (i), by the definition of spectral norm, we have
2
+ x
||A||2 max x 1 2=1
Az
Σ (J))
max
d
1 d.
||
|
2
2
(ME)
i
For (ii), let E E ii e v} be the edge associated with the adjacency matrix A. By the definition of spectral norm, we have
D ÄD
|| = max 1
T
(D-1AD-
x= max ||
Σ
(iS)) v VD.Ds
x
< max ||
Σ
x
+
S
max
Σ x =1=1.
2D:
2Dg
||l|a
(K
iEV
Before proving the first inequality we note that v 1X I B and |Pol2 1- S 1, so the second
inequality is rather straightforward. The last inequality comes from the fact that d 2 1.
We denote the node representation in the j-th (j () layer as
(G) H, = 15 (Po (Pa
E 1).
[ (G) H, 1
[V] 1 Hn-1Wn.
Adding perturbation the parameter w, that is, for the j-th (j n)) layer, the perturbed parameters W, U, and denote H' ( [n].
Upper Bound on the Node Representation.
For any n
||1 = I1o z
s Lip 5
s [L
where the first inequality holds since v is Lipschitz and tb, (0) 0. and the second and the last ones hold by Proposition Then, unrolling the recursion and setting Ho X, we have
|| s Poll Hollr
Lip, WW S
(54)
2
Pall
Lip, W
Upper Bound on the Change of Node Representation. For any j [V]
H H,llr (P U,)) W
(55)
Lip, Lip,llPo +U,) Poll
25

---

Using the triangle inequality. we have
| Hylls = Lip, + - PPPHHH-UUlll The first term can bounded as
P H, H + U,) = || H1--111l 11, + U212, and the second term can be bounded
||P=G,,-UU]|==== [|P_]]]====|[|]]]]__]]=====1=1
Therefore,
| - Hylle &
W, + U2l2 + Lip, Pallz | (56)
Unrolling the recursion while simplifying notation as: ||H Hj |E م Hy - by-1 we get:
H3J Hylle
bk
II
k==0
v+=++
1
j-1 II 1=b+1
Li + Unaale)=
Lip Pa
||| H& H& 1Uk-
j-1
5-1 II
||Pell5~1|HHlll
|U++illa Lip
[| + U4ail2..
Plugging in Equation 54, we have:
|| H - H,llo S Lip,
PPll2
||P||| Z11e II [alll
111++1|2
II w + Uill
1=1
km
< ||Z
Lip;
PPll2
Uu+ 112
k+1
I ll2
5-1
II
(1+ +1
1
|1
W ll2
i=1
imk+1
j-k
1
1 PPll
Wall2
Lip, km
1
W
m
[=1
(57)
Final Bound on the Readout Layer.
1
H H,
l HY (W, Un)
[V] l Hn.
[v] Hn 1 + +U,)
+
1 1 H H
Un
5
|v
2
<
[ - + Unm)
+
1 1 1n- Hn Un
5
[
1
1 [1(1/-1 - (W_ + +UW)l2 +
[ 1 1|v
|
H H Hn-1 - Un|12 +
Hn Un.l2
where in last inequality we first apply that ||A||2 ||||| for any matrix A and then use Proposi- tion Using Equation 54 and Equation 57, we have:
26

---

X sorted by f:
m(k)
r2(k))
n(ii)
X sorted by gi
n(i)
(k)
Figure 5: Case g(n(k))
((m(k)), ((((k) (mm(())
X sorted by f:
m(k)
nkk)
X sorted by g:
nz(k)
m(k)
Figure 6: Case g(((k)) > g(m(()), f((kk) - f(m(k))
1k
1 n
[Ha -Hal2 S
W. + 1
Lip, W
1
V
W
||||||1 Pa
Lip, W
12
IMP
1
1 1
n-
Poll n- |2
IW, + Un
Lip, Lip,IIWll
+ +|lUnll2
Lip, Walla
Viv
[W&ll
|| + Un
| 2|
nーh-1
||U l2
Pall" |/
n-
Lip, Will2
1 +
+
VIVI
1 12
W
| l|
1=1
1
(1+ 1
Uull
(1 (1+
n
|1,,112
|2
Pall
Lip, W
<
V
W,, ||
1=1 Lip, W
||U1l2
12
1=1
where we set Lip, 1 for simplicity of notation and last inequality holds since 1 < (1 + 4 < e.
Our next lemma helps us to upper bound the PERSLAY's perturbation, when Agg = k- max.
Lemma 9, Let X be an arbitrary finite set and f.g X + R. Then we can say that:
kk- max fxx) - k- max ((x) < 3 max [f(x) g(x)
xeX
zEX
Proof. Denote n N X by function that maps natural number & to element of X that would be on kcth position in order sorted by f. Denote m as an analogous function but for g. Then, we are interested in the following expression: (f(n()) ((m(k))] Let rewrite it:
(f((k)) g(m(k)) If(n(k)) - g(n(k)) + g(((k)) - g(m(k))) < (f(n()))
+((n))))))+((())))) g(m(k)) 1
S max 1f(x) 9(x) + +l((n(k)) - 9(m(k))
xex
Now, the task is to prove that (0(n())) - g(m S max (f(z) - g(x)
Let us consider four cases:
g(n(k)) > g(m(k)) and [(n(k) 2 mmm(k) (Fig. 5). In this case Fi N such that f(n(i)) > f(n(k)) and g(n(i)) < g(m(k)). Indeed, if none of the elements "to the right"
27

---

of (k) moved "to the left" of m(),, then "to the right" of m(k), there are at least n - 1: + 1
elements; however, there are must be exactly n k elements.
[g(n(k)) s(m(())) g(n(k)) - s(m(k)) - g(((k))))))))))))))))(())))))( g(((i)) S
S f(((k)) (max [[() g(x)l) g(n(1)) <
< <(n(i)) + (max [f(x) g(x)l) g(n(i)) < 2(max [f(z) - g(x)))
=
#EX
. g(((k)) > g(m())) and f(((k)) - fmm(k)) (Fig. 6)
19(n(k)) - g(m(k))) g(n(k)) gmm(k)) 1
S [(n(k)) + zex [f g(x)) ((m(k)))
S f(m(k)) +
max (f g(xx)) g(m(()))
nEX
2 max [f(x) s(x)]
The rest of the cases can be handled analogously.
Lemma 10 (Perturbation analysis of PersLay). Let fw G + Rh with w = (W(w), W } be PersLay where W() is a parameter vector (matrix) of weight function, w. and W(v) is parameter vector (matrix) of toanttranfforatiion function, s. Let Dg be mapping from graphs to (extended) persistence diagrams with a fixed filtration function and such that max max ||pl|2 S B, then: GE9 pEDR(G)
max [G)l2 S ((
(58)
GEG
and nfw) and u = (W(w), ((P)] such that | 1|2 S ((w)) we have:
max [w+uu() Jw (G)22 GEG
[1U(00)22 T(x)
||
(59)
Ag ma Liph ( ((TWW(T)
T(w)
where A max card(Dg((G) if Agg is sum and A if Agg is k-max or mean; A2 GEg
max card (g(())(()))))) if Agg is sum or Ag = if Agg is k-max or mean; GES
(T(P), g(e), Lipl+)) = (max(1, || 12), VTB,1)
A
(T(P), c(e), Liplt)) (max(1, (W [2], Th, 1/2)
8 r
= L. (T(P), g(e) lipl()) = (1WW1)))2 v3 m1 B), max (1, B})
T(w) - max(1, || and C(w), Lip are such that:
max max (ww ((w) and max (ww+u(p) ww ww)()) (i) | GEg (EDg(G)
GE9 Pc (gDg
for any w and u
Proof. First prove the inequaliry about maximum output norm.
28

---

Maximum output norm.
max (l & A max max GEG
|w (p) (p)ll2 s
GE9 pEDg(G)
I A max max ww (p) Pw (p)ll2 = GEg pEDR(G)
(60)
S A
max ww (p) Dg())
max
l (p)ll2,
G G
where A₁ is max card(Dg(G)) if Agg is sum and A = if Agg is k-max or mean. Geg
From the Lemma statement we can upper bound ww (p):
Ww (p) - ((w))(()
max pEg(P)
Maximum norm of yp:
P = A.
max
(Pw(()))
max GEG.PEDg(C)
max P2 - 1t; - -P11 S p2 S B
Dg(C)
Hence:
1/2
1/2
max GEG.PEDR(C)
119w(p)122=
Σ
P P (p)
6²
Bvh
1=1
==10 r.
Ip1
t 1 + lp2 - ts,2
max
(pw())))
max Dg(
exp
1
GEO.pEDg(C)
27
Hence:
1/2
h
(1))(2)
Σ
le (p)x
Σ
Vh.
GEG.PEDg(G)
6 V.
I (p)el GEg.pEDg(C)
max
=
max
[1t4[1] + +ptt.(2] + t,[3] I
Geg.reDg(G)
I ma (B, 1344 + 4.2 + [3]3]
Hence:
h
1/2
h
1/2
Σ
Σ
max B, B, 1/ + +,22 + t,133
max Geg.pEDg(G)
h
ma 1}
Σ
3(12, 1 + 12,2 + (3)3))
$ / max ( BB 1 ([))
Combining all together we get the Equation 58.
Maximum perturbation of the PersLay output.
max
(fg()()g(G)) - fw (Dg(G))) S A2 GEg
GEgGLEDE(G)) [kw+u()))w=u(p)) - ww ww (p))pw())l2
max
$ A2 (g(G)
max
- (p + aw (p()( -w S
< A2 max Dg(G))
(ww.Hu(P)ll Pw (p) + ll (lwp - (w)))
29

---

where Ag is max card(Dg(G)) if Agg is sum, A is 3 if Agg is k-max by Lemma 9 and Ag is if Geg
Agg is mean.
By the Lemma statement have:
||u S (1 (1 + s/(l)
max (g(G)
and
GgG.pEDg(G) (w++up) ww [p)] I Lip |
max
Moreover, from Paragraph about max norm of yp:
max GEG.PEDg(G) (p S ((9)T(P))
Maximum perturbation of yp:
p = A. Since g(z) = |x| is 1-Lipschitz we have that:
I1(pw+u(p)) - 9w (p))sll s U.!0) GE9.pEDg(C)
max
Hence,
h
1/2
max GEG.pEDg(G)
(1 - -w 2
Σ ((e - 4 (p))s1?
1/2
Σ (1(1))
=110000112
r. Suppose g(z, v) = exp -2
Then
11 y) - g(x + Ar. y + Av)ll2 = V3(4', y/ 12 Ar + Ay² z
S max Vg [ ( Ar Av² 2 yg'
by mean-value theorem for some x', y between and + Ar and y and y Ay.
Let find maximum of the gradient by every coordinate. Since the function is symmetric we need to do it only for one of the coordinates.
The maximum of the norm of the first coordinate of the gradient is achieving at the point t,,1 = P1 + т, and the gradient value at these points at most 7e7 So we have:
1/2
(P)
12
|[ee(UU))))
(19 - (p)ll2 -
max GEG.)EDg(G)
c2e
7e//2
< V. In this case g( 2) Di + p2y is max (B 1)-Lipschitz,
1/2
(
max ( [B, 1)
max B, 1 (B.1c))ee(((()))
max GEG.pEDg(G)
Combining all together we have:
max [l.f+uu( (G) - fw < As (1 + www GEG
((P) ((e) (w) |
[2]
|
U ( 112
< A (1 +1+1) (1)) max (z) ((w) Lip ((p))
|
[ 12
30

---

E Proofs of corollaries
Corollary 3. Let fw X' EK with [W Wn3 be an n-layer MLP with Lip--Lipschitz activation functions 4h for E [n mn-1 -11. Let B E I. be such that Vr E X | S B. Then fw satisfy requirements of Lemma with:
Willa and E [n] S = [Wil2
=
6n
1=1
n-1
n-1
C = B II
Lip. and C2 = eB
Lip;
==1
==1
Proof. To test Equation and Equation we use Lemma 7. To check Equation 8 we apply arithmetic-geometric mean inequality:
n
ll
Σ
EI
Wyll2
W
12
jy
(61)
112
II T
nT
is left show that Equation 9 holds:
C1
3n 1
(62)
2C
Corollary 4. Let fw : X' R with w (W.,... Wr} I be n-layer GCN network with readout
layer. Let wh for i [n [1] be -Lipschit activation function. Let node feature of any graph be contained Ez-ball of radius B, i.e. VG E X: || S for every node v and VG X, G simple and has maximum degree most d - 1. Then fw satisfy requirements of Lemma 2 with:
1
Willa and wen: S, ||1l22, 7 6n T=
if using perturbation analysis from Liao et al. [33]
C C=
II
Lip, and C2 = eBd
Lip:
or if using perturbation analysis from Sun and Lin [48]
C =
II Lip. and C2 = cB Lip 2m1
Proof. To test Equation 6, Equation 7 we use Lemma 8. We can apply Lemma 8 because To test Equation 8 use arithmetic geometric mean inequality:
1
<
2
W,ll2
>
W. 12
R-1
2
112
n
T
nl
t=1
It is left test Equation 9
31

---

C1 202 Gn
_ 2
Corollary 5. Let fw + R with w [W1, 22. W3} be n-layer MPGNN (n 2). Let O. be activations functions with Lipschitz constants: Lip.. Lip a. Lipp We denote Lip Lip, W2 with C. Let node feature of any graph be contained in 2z-ball of radius B, ie. YG = (V, E, 2) E X, &.Ve E V || S B and vG X. G is simple and has maximum degree at most d - 1. Then fw satisfy Lemma requirements with
if dC + 1:
(dC)--1-1
T - 12 Walp dc -
S = [Wil, S2 = min
||2 |2], S3 = =|Wall2,
111 = 1/2 133 6n
C BC and C2 eBC
dC 1:
T
S Will, S₂ min [2l12)) S3 [Wall2
1/2 = n/3
6(n 1)
C1 = BC + 1) and C2 eBC
Proof. From [33] (Lemma 3.3) we know that:
eB(n + 1)2 W dC =1
max [lf - fw (G)ll2 S GEX
e eBan Willa ||2 2 (do)==1- d dC + 1,
(63)
where = max
Calla [Walla
I
1. In our case ñ - n
6n so we can apply these
1
[ inequalities. Note that in our notation we have n-layer MPGNN and instead of Wi we have W3 (and instead of U/ we have Uz).
|Wall
And
B(n - 1)Co dc =
max fl (G)ll2 <
GEX
BC lallWl
[de--i)-1 dc
dc +
(64)
Eq. (76) and Eq. (68) respectively. Equation 6 follows from Equation 64. To test Equation 7 note that:
|11112 12212 W1ll2
UUB [W&
|1112
1121l
l3ll2
S
(65)
[Wll
[
min (dC, [W2ll
W l2
Now Equation follows from Equation 63 and Equation 65.
To test Equation 8 employ arithmetic geometric mean inequality:
3
W. W 2 2/
dc =
1
3T (S
( W. 147
T
W. Walla W (dcyn-1_
S2
Sz
S2
3
372/3 dC + (dc)
(1 dc
where in case dC 1, S2 < 1 and in case dC + 1, S2 dC and
> dC for n > 2.
dc
32

---

To test Equation 9 we provide the following derivation:
C1
1+1 B(++ij
dC =
2 112
2C²
6n dC +1
Corollary 1. Let fw - R with (W(w), W be PersLay where W() is parameter vector (matrix) of weight function, w. and ( is parameter vector (matrix) of function, g. Let Dg be a mapping from graphs to (extended) persistence diagrams with a fixed filtration function and B such that max max l|pl|2 B, then fw satisfy requirements of Lemma
GE9 PEDg(G)
with:
T T= T and (S( s(w)) (1] 12, [I and (111)) (1.1)
C 2ma A1 C(w) c(P) 2A₂ max ((w) Lip ((ellip
C2 = 2A2 max (C(,) Lip (9), c(+) Lip 3.
max card(Dg(GG) if Agg is sum and A = 1 if Agg is k-max or mean; A GEG max card (Dg(G) if Agg is A₂ if Agg is k-max mean; GEG
where A
(T(e), c(+), Lip (max || 12), Bvh,1)
8 A
(Tle), c(+), Lip( = (max(1, W [2), Vh, Te- 1/2)
4 =
(T(9), ((+), Lip(()) - (l/W<e0)22 v3 max B}, m1
W
T(w) m1 [W()) |2): and c(w), Lip(w) such that:
Www (p)l2 - ((+) and max max (w++u(p) - ww(p)) Lip(w) | GEG pEDg(G)
max max GEG pEDg(G)
for any w and u.
Proof. To test Equation 6 and Equation 7 we apply Lemma 10. mf(w) in Lemma 10 is arbitrary, we can use this lemma with 17(w) = 1 and in this case 1 + n7(w) = 2, so our choice of C2 works.
To test Equation 8 arithmetic geometric mean inequality:
T(p)((>)
((p)
T(p)(())
2
2
(T())T()))13 27
S(F)
S(wi
It is left test Equation 9
2A ((w) max {1, 24g max (ip))) Lip)))))))
G
>
21
20²
2A₂ max ( Lip( (+), Lip(
F
Comparing bounds with prior works
MLP & GCN
The result is not as tight as in [40] because of the homogenity assumption that they do. Specificaly, matching our result to theirs, we have (2 In nh) the same as B²n (h In nh) (instead of n they have in their notation). We have log (m max(1, 1 }) which in most cases better than log min 5=
However, the suboptimality of our bound comes from:
2
max 1,
W
Σ
W l
33

---

by Cauchy-Schwarz inequality. The most left expression is the term that is in Neyshabur et al. [40] and the most right expression is the one we have in our bound.
However, the advantage of our result is that it does not depend on the assumption of all activation functions being equal to ReLU and that we can compose with results for other networks to get bounds for compositions of networks.
MPGNNs As discussed in the main text the difference between our bound and the one in Liao et al. [33] comes from the dependency on the weights.
Their dependency: max { --1t+1), (dc)'=1-1 |e/lle/WWlll. =Ca dc-1
}. where Ç min || [W]ll2), A (1+1), (AE) +
Let us show, how our bound depends on X, Ç and g:
5- = max 1|
3 W1lle +
12ll2' WWll
W| [Wille
min dL,,, Lip, Lipp)
Wall2 +
3
min 222l
[[ill2
and
1
5- = max [Wall2'
S
122ll2'
||ill Will2
||ill 1|2ll2
[Will2 min(de, [22ll2] |Willa*
Note that
Ag T. Now let analyze cases:
(1E) 2 (c)-(++), this case Ç-1 s (Ag)a/1 and Ç- S (AE)
2. (C) (C) (1+1) 2 (AE) t In this case 5-1 2 xg and Ç 1 S 5 g-(11) (14()- (+
=
So, in the case when dLip, Lip, Lip, is lower bounded by some constant we can conclude that asymptotically our bound is not inferior, than the one in Liao et al. [33].
G Dependency on Model Parameters and Hyperparameters
In the Table we present the dependency of existing results and our result on the model parameters and hyperparameters.
H Learnable Filtration Functions
Fixed filtration functions dominate the PH/ML literature. The widespread use of learnable functions relatively recent phenomenon in PH-based MI, and usually runs orders of magnitude slower compared to non-learnable ones. Arguably, applying non-learnable functions still represents the mainstream approach in TDA.
Some works have explicitly advocated for fixed filtration functions (with learnable vectorizations) over learnable filtrations. Filtration functions can come in different flavors: for instance, they can rely on node degree [18], cliques [43], or node attributes [22]. Some of the popular options are parameter-free. Also, while some works showed gains using learnable filtrations [20], others have reported no benefits and adopted fixed functions instead [5, 34]. There is still no consensus about the significance of the gains associated with learnable filtration in many applications.
Perslay [5] uses fixed filtration functions. Despite the generality of our results, we provide specific bounds for PersLay, which employs fixed filtration functions.
Our work lays strong foundation for analyzing learnable filtrations. One way to analyze PH with learnable filtration schemes could be to get upper bounds perturbation of outputs in terms of the
34

---

Table 6: The dependency of the bound on the model parameters. All models have maximum width of weight matrices h. We consider n-layer multlaayer perceptron (MLP) with weights
W Wi..... W.. We consider n-layer GCN with weights Wi,..,, Wn. We consider n-layer (n > 2) MPGNN with weights W1, W2, W3. We consider simple graphs with maximum degree d. We denote c= L L Lipp,//Wlll = [[ ||2 3al2 and ((dC)) (dC and |w|2 is the norm of all parameters the model. Comparing [33] do not add Lip, & and instead of W we have W3- We consider PersLay with one of the classical point-trane transformmaiin (described in [5]) and weight function with weights W(+), ((w) and ||w/22 2 is the norm of all parameters in the model. We consider abstract model that satisfy Lemma requirements with w, T, 17, Cnorm and S
Name (Reference)
Model Parameters
Model Hyperparameters
MLP, [40]
11 1=1
2
/
h hn(nh)
GCN, [33]
II
WWlll2
[w.ll
d d In(h)
1=1
MPGNN, [33]
|w|2 max (m+1)
(Ag)
"V hVhln(n))
PersLay
||
| ( || (W
V/2a In
Lemma
| 2 Σ 1/s:
Cnorm
V In (nh)
filtration function parameters. This would additionally require analysis of Wasserstein distances between persistence diagrams obtained with different parameters. We believe that for a specific class of graphs can get modified upper bounds for perturbation with respect filtration function parameters that would depend on Wasserstein distance of the same order. This additional analysis could be readily integrated into our framework get generalization bounds for learnable filtrations.
I Discussion on the max over and parameters norm.
From the first glance it may seem that introducing max || } is suboptimal; however, || is
greater than in many real-world scenarios. For instance, suppose have parameters within the range of (E)) then the squared norm would be greater than 1 if the number of parameters exceeds 1. Considering a typical choice in the Deep Learning literature, E 0.01, we need more than 10, 000 parameters. For example, a two-layer MLP with a hidden dimension of 64 (also a typical choice) has more than 8, 000 parameters, so practice, ||w]] | 2 usually true.
J Implementation details
J.1 Datasets
Table 7 reports summary statistics of the datasets used in this paper.
Table 7: Statistics of the datasets.
Datasct
#graphs
#classes
Avg #nodes
Avg #edges
NCI1
4110
29.87
32.30
IMDB-B
1000
19.77
96.53
PROTEINS (full)
1113
2
39.06
72.82
MUTAG
188
2
17.93
19.79
DHRF
756
42.43
44.54
MOLHIV
41127
25.5
27.5
NCT109
4127
29.68
32.13
35

---

J.2 Models
For the experiments with PersLay Classifier, we closely follow the filtration functions used in [5]. In particular, we use Kernel heat functions with parameters t = 0.1 and t = 10 for the remaining datasets. Instead processing each diagram type using separate models, we combine ordinary and extended diagrams for O- and 1-dimensional features and apply single model. We use mean aggregation function in all experiments, and Gaussian point transformations. For the feedforward part of PersLay, we apply ReLU activation functions. All models are trained with Adam [27] and learning rate of 10-3 for 3000 epochs.
For the experiments with GNNs with persistence, we use graph isomorphism networks (GINs) with 2 layers and 64 hidden units. The models were trained for 2000 epochs using the Adam optimizer.
Dependence on model paramaters. Regarding the dependence on the spectral norm of weights, we reported results for a model with final MLP (multilayer perceptron) of 2 hidden layers (3 layers in total) and width of 128 for all layers. The number parameters of the point transformation was h 100. For the experiments on width vs. generalization gap, we used h 100, and 1 hidden layer with a varying width in (32, 64, 128, 256, 512).
Regularizing PersLay. For the experiments regarding ERM and spectral norm regularizers, perform model selection for (number of layers) / E {2, 3), and a, E {10- 10 1015s 100-).. Again, we use Gaussian point transformation, h = 100, and width equals to 128. Our goal was to see we could observe gains from the regularized version even for shallow neural networks.
Regularizing GNNs with persistence. Here, we consider GNNs with 64 hidden units of 64 (width) and 2 layers. We set the dimensionality of PersLay parameters equal to 100, Gaussian point transformation, and mean aggregation function. We apply hold-out model selection with penalty term Or E (10-5, 10-6, 10-7, 10-$) using the validation set.
Hardware. For all experiments, we use Tesla V100 GPU cards and consider a memory budget of 32GB of RAM.
PROTEINS
NCI
IMDR-BINARY
1.0
p: 0.911:0004
1.0
#:
0.9550004
1.0
j: 0.72180066
0.5
0.5
0.5
0.9
0.0
Trepirca gtp
Out bouu
0.0
Wiah,
Figure 7: Width vs. generalization gap for the triangle point transformation.
PROTEINS
NCLI
BIDB-BINARY
1.5
1.5
Generiisation Dap
Spectral norn
1.0
0.5
0.5
0.5
0.0
-0.5
0)
72
-0.5
1 0.84+
-0.3
1r 0.00:0.04
1000
1000
2000
Epoch
Epoch
Egoch
Figure 8: Spectral norm vs. generalization gap for the triangle point transformation.
K Additional visualizations
Figure 7 and Figure 8 report additional results for the triangle point transformation on the three largest datasets: PROTEINS, NCII, and IMDB-BINARY. In particular, Figure 7 shows the dependence of the generalization on width, while Figure 8 shows the dependence on the spectral norm. Overall, our bound can capture the trend in the empirical gap and produces high correlation values for all datasets.
36

---

NeurIPS Paper Checklist
You should answer [Yes], [No], or [NA]
[NA] means either that the question Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatiio right after your answer (even for NA).
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Table 1 maps the results supporting our claims.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
be expected to generalize other settings.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The discussion about the Table 2 in the Section 3 contains comparison with prior works. The discussion after Corollary contains description of the limitation of our PersLay analysis. Moreover, the conclusion summarizes some of the important limitations.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-texx system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
37

---

3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: Assumptions clearly stated in the statements, and in the Appendix E and Appendix C.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems. The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Details are provided in the Experiment Section as well as in the Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
38

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [Yes]
Justification:
We provide a link to our code Section 6,
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (uttps://nips..
cwtemmissssooooliiiooooo onPolicyl for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: / //nips.
for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details are provided the Experiment Section as well as in the Appendix J Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Plots count on error bars and tables count on standard deviation.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
39

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Appendix J.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https htap:::://eeeee http///eeurspp.eee cwtrriiss.cppppbaae wwtpppcic/tttcciiicccce wtw.ehhhhiiieeeeeeseee
Answer: [Yes]
Justification:
Our submission follow the NeurIPS ethical guidelines.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We provide a perspective on broader impacts Section 7, but do not foresee any direct negative societal impact.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
40

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not foresee any direct risk stemming from our work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: All code was made by the authors
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswi wwwode.hcoe...c. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
41

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
No new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: No experiments with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No experiments with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
42


Reviews:
[{"review_id": "o5OmrqwdBX", "reviewer": "Reviewer_zp7n", "summary": "This paper presents a compositional PAC learning framework for bounding the generalization gap in deep graph networks that are augmented by PersLay-vectorization of persistent homology features. Topological features can be complementary to deep features. Empirically, this combination can boost the empirical test performance. This paper investigates whether this observation reflects to the theory, and concludes that it does, up to some assumptions, for example in filtrations.", "questions": "I have appended my questions after each relevant weakness. I would be happy if the authors could address them. In addition: \n- Why would the bounds worsen with the increase number of epochs (where I believe training gets better)?\n- There is also growth in the width disproportionately to the empirical gap. Why would this happen?\n\nIn general, some more light on the empirical findings would be useful.", "limitations": "The paper appropriately discusses the limitations and remains to be largely theoretical in a very niche domain of machine learning. As such, I don't see any issues with broader impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- To the best of my knowledge, this is the first generalization bound of its kind, presenting bounds for a heterogeneous network composed of PH vectorization and GNNs.\n- I really like the presentation and exposition in this paper, that makes it informative and easy to follow.\n- The idea of using a compositional pac-bayes framework for bounding generalization in PH-augmented GNNs really makes sense to me.\n- Although I have not been able to thoroughly check all the proofs, the theoretical parts I investigated made sense.\n- Given the nicheness of the topic, the models (GNN + PersLay) are intuitive for integrating topological features in deep graph learning. I have seen such architectures a few times.", "weaknesses": "- One obvious drawback is that the architectures of concern in this paper are rather limited and not the ones used in practice. While this limits the applicability, the paper's theoretical contributions make it less of a concern. According to me, speaking of generalization for PH-augmented GNNs through the lens of compositional pac-bayes is interesting in its own right.\n\n- Most importantly, does the proposed bound, similar to the KL-terms in Neyshabur's bound, depend on the number of parameters in the network? (I was suspecting this due to the use of the norm.) If so, it is definitely worth discussing, as the recent theory of deep learning states that the intrinsic dimension matters rather than the ambient dimension. And if not, please clarify.\n\n- I'm curious about the limitations of the compositional framework. Can we leverage the nature of PH and the integration to do something more specific to tighten the bound? The compositional framework seems to adapt a rather late fusion. \n\n-  Ln. 81: The generalization error is defined to be the population risk and not as the difference between them. I believe some sort of a difference between test/train would be more appropriate. Why is this chosen? Is this common convention? \n\n- I see PH as a hand-crafted way of extracting topological features, which goes a bit orthogonal to the current trends. Can the same analysis be extended to hybrid classical & topological deep learning (like the ones presented in [*,**]) which also operates on complexes? If so, do the authors see a straightforward way? \n\n- There are multiple ways to combine PH(-vectorization) and GNNs. A two-branch architecture + PersLay is definitely a good way. Yet, I would expect that the paper investigates other forms of combination. For example, what about learning a filtration?\n\n- I'm noticing that only a single family of GNNs is used in the paper. Is it possible to show results with more modern architectures at least like GraphSage?\n\n- There is also a rather recent literature of leveraging PH to bound generalization [***] (other way around), which this paper does not seem to discuss. It would be good to have both sides of this picture to stress on the impact of PH in the generalization theory.\n\n[*] Hajij, Mustafa et al. \"Topological deep learning: Going beyond graph data.\" arXiv preprint arXiv:2206.00606 (2022).\n\n[**] Papamarkou, Theodore, Tolga Birdal, Michael M. Bronstein, Gunnar E. Carlsson, Justin Curry, Yue Gao, Mustafa Hajij et al. \"Position: Topological Deep Learning is the New Frontier for Relational Learning.\" In Forty-first International Conference on Machine Learning. 2024.\n\n[***] Birdal, Tolga, Aaron Lou, Leonidas J. Guibas, and Umut Simsekli. \"Intrinsic dimension, persistent homology and generalization in neural networks.\" Advances in Neural Information Processing Systems 34 (2021): 6776-6789.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your thoughtful, constructive, and insightful review. We hope that the answers below sufficiently address your concerns. \n\n> the architectures of concern in this paper are rather limited and not the ones used in practice.\n\nDespite the generality of our framework, we focused on PH and PH-augmented GNNs due to the lack of generalization bounds for these classes of models and their increasing popularity in the graph learning community. In this regard, a prominent way to combine persistence diagrams (PDs) with GNNs consists of leveraging PDs as global topological descriptors, which are then concatenated (in parallel) with graph-level GNN embeddings (see [1]). We followed this approach in our work. \n\nImportantly, our work paves the way for the generalization analysis of different classes of topological neural networks and their integration with PH [2,3]. For instance, compositional PAC-Bayes may be an asset in analyzing models that exploit 0-dim PD as node-level information that can be combined with node embeddings at each GNN layer (see [4]). \n\n> does the proposed bound [...] depend on the number of parameters in the network?\n\nLike Neyshabur’s bound, our results implicitly depend on the number of model parameters via model hyper-parameters (e.g., number of layers) and parameter values (e.g., spectral norms). We show in Table 1 of the rebuttal PDF the dependence of our bounds on model parameters and hyperparameters separately.\n\nWhile we initially found PAC-Bayes particularly suitable to develop a general recipe for composing bounds for heterogeneous layers, we agree that applying our ideas to other generalization frameworks (e.g., in terms of intrinsic dimension) can provide further insights into generalization in DL. We believe this is a fascinating research direction for future work.\n\n> Can we leverage the nature of PH and the integration to do something more specific to tighten the bound?\n\nIn this work, we focused more on deriving a flexible recipe that can accommodate a broad class of models and less on tightening bounds. However, extending our ideas regarding the compositionality of heterogeneous layers to other generalization paradigms (e.g., PH-dim [6]) is a very interesting direction, and it seems a promising approach to get tighter bounds.\n\n> The generalization error is defined to be the population risk and not as the difference between them. \n\nIndeed, it is possible to define it as a difference, but we wanted to be consistent with some reference works in the PAC-Bayesian literature, such as [7,8,9].\n\n> Can the same analysis be extended to hybrid classical & topological DL … which also operates on complexes?\n\nIndeed, we believe that Lemma 2 can be used to derive bounds for higher-order TNNs [2, 5] and their combination with the classical PH approach. Intuitively, we would expect T (a relevant component in Lemma 2) to depend on the norms of the weights associated with the different neighborhood structures. We note that the technical details to ensure that the conditions in Lemma 2 are satisfied need to be figured out. We believe this is an interesting future work.\n\n> What about learning a filtration?\n\nFor a discussion about learnable filtration functions, please see the global response.\n\n> Is it possible to show results with more modern architectures at least like GraphSage?\n\nWe have run additional experiments using GraphSage (see Tab 2 in the rebuttal PDF). Although our bound is not particularly tailored to GraphSAGE, due to its similarity to GCNs (GraphSAGE samples neighbors at every iteration instead of counting on all neighbors), our regularization scheme also benefits GraphSAGE. Table 2 also contains additional results regarding regularized versions of GCN and GIN combined with PersLay. Overall, the regularized methods achieve smaller generalization gaps and lower errors in most experiments.\n\nFrom a theoretical perspective, we can upper-bound GraphSAGE by leveraging full neighborhoods — obtaining GCNs. In some sense, our analysis already subsumes GraphSAGE. In fact, our additional experiments using GraphSAGE show that the empirical generalization gap strongly correlates with our bound (see Fig 2 in the rebuttal PDF). However, achieving tighter bounds would require deriving a specific perturbation analysis for GraphSAGE.\n\n> There is also a rather recent literature of leveraging PH to bound generalization [..] which this paper does not seem to discuss.\n\nWe agree that using PH to bound generalization is an important line of work. Indeed, Appendix G of our paper discusses it. We will also appropriately position these influential works in the main text in the revised manuscript.\n\n> Why would the bounds worsen with the increase number of epochs?\n\nThe bounds worsen because the spectral norms increase during training to fit the training data. To validate this, we now report the average spectral norms for GNN and MLP layers in Fig 1 of rebuttal PDF.\n\n> There is also growth in the width disproportionately to the empirical gap. Why would this happen?\n\nWe suspect that some dependencies in our bounds could be improved, which may explain the discrepancy you noted. \n\n[1] Going beyond persistent homology using persistent homology. NeurIPS 2023.\n\n[2] Topological deep learning: Going beyond graph data. Arxiv, 2022.\n\n[3] Topological neural networks go persistent, equivariant, and continuous. ICML, 2024.\n\n[4] Topological graph neural networks. ICLR 2022.\n\n[5] Weisfeiler and Lehman Go Cellular: CW Networks. NeurIPS 2021.\n\n[6] Intrinsic Dimension, Persistent Homology and Generalization in Neural Networks, NeurIPS 2021.\n\n[7] A PAC-Bayesian Approach To Spectrally-Normalized Margin Bounds for Neural Networks. ICLR 2018\n\n[8] Simplified PAC-Bayesian Margin Bounds. Learning Theory and Kernel Machines, Lecture Notes in Computer Science, 2003\n\n[9] A PAC-Bayesian Approach to Generalization Bounds for Graph Neural Networks. ICLR 2021\n\nWe're grateful for your constructive feedback. Many thanks!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "q2viyEti32", "reviewer": "Reviewer_toK8", "summary": "This paper introduces a novel compositional PAC-Bayes framework for analyzing the generalization of heterogeneous machine learning models, with a particular focus on graph neural networks (GNNs) augmented with persistent homology (PH) features. The work develops a general PAC-Bayes lemma for heterogeneous models that not only recovers existing bounds for neural networks and GNNs but also extends them to more complex architectures. Notably, it provides the first data-dependent generalization bounds for PH-based models.\nThe key innovation lies in the compositional approach, presenting lemmas that allow for combining bounds from different model components. This enables the analysis of complex architectures like GNNs augmented with PH features, bridging an important gap in the theoretical understanding of topology-based graph representation learning methods. The framework's versatility is demonstrated by recovering existing bounds for various models and deriving new bounds for PersLay and its variants. The empirical evaluations across multiple datasets validate the theoretical results, showing correlation between the derived bounds and observed generalization performance.", "questions": "- The theoretical analysis assumes fixed filtration functions for PH. How limiting is this in practice, and could the framework be extended to learnable filtrations?", "limitations": "- While the experiments cover several datasets, they focus primarily on graph classification tasks. The paper could benefit from a broader range of experiments, including node classification or link prediction tasks, to demonstrate the generality of the approach.\n- While the paper derives a regularization scheme from the bounds, it doesn't fully explore how the theoretical results could guide the design of better GNN+PH architectures in general. Some discussion on how the bounds suggest optimal ways to combine GNNs and PersLay could enhance the practical impact of the work. \n\nThese points did not diminish the overall contribution of the paper but addressing them could significantly strengthen its impact and applicability.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- Novel theoretical contributions that advance the state-of-the-art in generalization analysis for GNNs and PH-based methods.\n- Flexible framework that recovers existing bounds and enables analysis of new model compositions", "weaknesses": "- Empirical evaluation focuses mostly on graph classification tasks; additional experiments on node classification or link prediction could strengthen the results", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback and for appreciating our work. We hope that the answers below sufficiently address your concerns. Otherwise, we would be happy to engage further. \n\n> Empirical evaluation focuses mostly on graph classification tasks; additional experiments on node classification or link prediction could strengthen the results\n\nThanks for your comment. While we agree that developing bounds (and  running experiments) for different tasks would be valuable, our work focuses on graph-level prediction tasks. Extending it to node-level tasks, for instance, would require adapting the theoretical framework — the i.i.d. assumption (basic assumption in PAC-Bayes) may not hold. Since our experiments aim to validate and demonstrate the practical relevance of our analysis, we abide by the settings we consider in Sections 3 and 4. We also note that PH-augmented GNNs for node classification tasks often apply local topological descriptors [e.g., 1], which fundamentally differ from what we discuss elsewhere in the paper. \n\n> The theoretical analysis assumes fixed filtration functions for PH. How limiting is this in practice, and could the framework be extended to learnable filtrations?\n\nThanks for your question. For an in-depth discussion about learnable filtrations, we kindly refer to the global response.\n\n> While the paper derives a regularization scheme from the bounds, it doesn't fully explore how the theoretical results could guide the design of better GNN+PH architectures in general. Some discussion on how the bounds suggest optimal ways to combine GNNs and PersLay could enhance the practical impact of the work.\n\nIndeed, this would strengthen our work; thank you for pointing this out! From our theoretical findings, we can say: \n- since the $C_{pert}$ constant for PersLay depends on the square root of its dimension, one should choose it significantly smaller than the dimension of the GNN to avoid an $O(h\\sqrt{\\ln h})$ dependency of the total generalization bound on $h$ instead of $O(\\sqrt{h \\ln h})$;\n- compared to the “k-Max” and “Mean” functions, the “Sum” aggregation function introduces a $\\max\\limits_{G\\in\\mathcal{G}} card(G)$ term to the bound, which in practice can be rather large. So, we recommend using “Mean” instead of “Sum”.\n\nMoreover, using our analysis, we can compare different PersLay variants (see Table 3 in the paper). Let us consider the constant weighting function for simplicity. Then, $C_{pert} = 2C_{norm}$, and as a result, we can rank different PersLay variants (e.g., k-landscapes, images, and silhouettes) by simply comparing their associated constants $C_{pert}$. For landscapes, $C_{pert} = 2\\cdot 3\\cdot B\\sqrt{h}$; for images, we have $2 \\cdot card \\cdot \\max \\\\{\\sqrt{h}, \\frac{1}{\\tau e^{1/2}}\\\\}$; for silhouettes we have $2 \\cdot card \\max \\\\{B \\sqrt{h}, \\frac{1}{\\tau e^{1/2}} \\\\}$. If the last two options use ‘sum’ as an aggregating function, then our generalization analysis suggests that k-landscapes would have stronger guarantees. If the last two options use ‘mean’ as an aggregating function, then $C_{pert}$ for k-landscapes would be at most $C_{pert}$ for silhouettes, and the result of comparison of k-landscapes and images could be in favor of both landscapes and images depending on chosen parameters $\\tau$ and $B$.\n\nWe will add this discussion to the revised manuscript.\n\n[1] Persistence Enhanced Graph Neural Network. AISTATS, 2020.\n\nWe are grateful for your constructive feedback. Many thanks!", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TuOarzAc0x", "reviewer": "Reviewer_Hv3h", "summary": "The paper introduces a novel Compositional PAC-Bayes framework that addresses challenges related to the heterogeneity of Graph Neural Network (GNN) layers and persistent vectorization components. It provides data-dependent generalization bounds for PH vectorization schemes and persistence-augmented GNNs, offering insights into improved classifier design and generalization performance predictions.", "questions": "1. This paper mentioned the expressivity of PH and GNNs for many times. Does the expressivity have anything to do with the generalization?\n2. What is the influence of using different filtration functions in the proposed framework?\n3. Does the proposed framework have any concrete applications? Can you provide a case study?", "limitations": "yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The introduction of the Compositional PAC-Bayes framework is a significant contribution to the field, especially in handling heterogeneous GNN layers.\n2.  The provision of data-dependent generalization bounds adds a valuable dimension to the analysis of GNNs and persistence-augmented models.\n3.  The empirical evaluations on real-world datasets demonstrate the practical applicability and effectiveness of the proposed framework.", "weaknesses": "Clarity: Some sections of the paper may require further clarification to enhance readability and understanding for a broader audience. From experiments, we can observe that there exists a considerable gap between the theoretical results and empirical results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your feedback. We hope our answers below satisfactorily address your concerns. Otherwise, we will be happy to engage further.\n\n> Clarity: Some sections of the paper may require further clarification to enhance readability and understanding for a broader audience. \n\nThanks for your comment. To further improve the clarity of our manuscript, we will:\n- include a list with the assumptions related to PAC-Bayes and the perturbation analysis adopted in the paper;\n- add a discussion about the main takeaways of our analysis, especially regarding how we can use it to choose better hyperparameters (see last answer to reviewer toK8).\n\nShould the reviewer provide additional suggestions for improvements, we would be happy to incorporate them.\n\n> From experiments, we can observe that there exists a considerable gap between the theoretical results and empirical results.\n\nThanks for your comment. Overall, we note that our theoretical bounds strongly correlate with empirical generalization gaps for most datasets and models. This is what one would expect, given that theoretical generalization bounds are often loose.\nTo complement our analysis, we have included additional experiments with different PH-augmented GNNs (GCN, GraphSAGE, and GIN) in Table 2 of the rebuttal PDF. The results reinforce that the regularized variants achieve smaller generalization gaps. We also report empirical vs. theoretical generalization plots for GraphSAGE — the results again confirm the practical relevance of our work.\n\n> This paper mentioned the expressivity of PH and GNNs for many times. Does the expressivity have anything to do with the generalization?\n\nThank you for the opportunity to clarify this.\n\nIn fact, expressivity and generalization can be at odds with each other, and finding a good tradeoff holds the key to success of machine learning models [1]. Indeed, enhancing expressivity typically comes at the expense of generalization. [2] established such a result for Graph Neural Networks, showing that the VC-dimension of GNNs with $L$ layers is lower bounded by the maximal number of graphs that can be distinguished by 1-WL (Weisfeiler-Leman test for isomorphism). High VC-dimension directly translates to poor generalization, whereas by definition greater the number of graphs that can be distinguished greater the expressivity. Thus, [2] showed the tension between expressivity and generalization in the context of message passing GNNs that are at most as expressive as the 1-WL test.\n\nExpressivity of machine learning models is certainly important [3]; however, it does not guarantee that powerful models that do well on training data would generalize, i.e., predict well on unseen data as well. \n\nMoreover, most of the generalization bounds in the literature share a common structure: population risk is bounded by empirical risk + complexity of the model class ($\\approx$ expressivity). This fact also suggests the intricate connection between generalization and expressivity.\n\n> What is the influence of using different filtration functions in the proposed framework?\n\nOur work considers fixed filtration functions, and the exact choice of filtration function does not affect the bound. This happens because the considered filtration functions are parameter-free --- this part of the model does not impact the output change due to parameter perturbations. However, the choice of the filtration function affects the risk, not the bound on the difference.\n\nAlso please see the global response for the discussion about learnable filtration functions.\n\n> Does the proposed framework have any concrete applications? Can you provide a case study?\n\nAs a general result, Lemma 2 and the Corollaries about model compositionality of heterogeneous layers apply to a broad class of models. Indeed, in the paper, we show specific case studies where we can recover existing bounds (for MLPs, GCNs, and MPNNs) from our framework. In addition, we use our framework to derive new bounds for PH-augmented GNNs and PersLay --- as case studies. \n\nFrom an empirical standpoint, we leverage our results to derive integrated regularization procedures for different methods, including PersLay and PH-augmented GNNs. Our results show that the regularized variants can achieve better (test) classification performance and smaller empirical generalization gaps. In the rebuttal PDF (see Table 2), we provide additional results for different GNN architectures to further support our claims.\n\n[1] Generalization and Representational Limits of Graph Neural Networks. ICML, 2020\n\n[2] WL meet VC. arXiv, 2023\n\n[3] A Survey on The Expressive Power of Graph Neural Networks. arXiv , 2020\n\nMany thanks again for your thoughtful comments, which have helped us reinforce the strengths of this work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hUCv8sktpm", "reviewer": "Reviewer_ynbU", "summary": "This paper derives novel generalization bounds for a special class of GNNs augmented with persistent homology descriptors, specifically PersLay. They empirically test the bound and use the bound to propose a regularization, which works well in practice.", "questions": "How does the bound for GNNs with PH compare with their counterparts without PH? Does the result provide any insights into why PH is beneficial for enhancing GNN performance?", "limitations": "Please refer to the weaknesses section.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The paper provides a clear background introduction to persistence homology and its integration with GNNs.\n2. The derived bound has positive correlation with the empirical generalization gap of GNNs.\n3. The paper is well positioned within related works on perturbation based generalization bounds of MLPs and GNNs.", "weaknesses": "1. It is hard to parse the significance of this work as the bound applies only to a restricted family of models augmented with PersLay. This issue could be mitigated by demonstrating that a model derived from this analysis is comparable with more advanced GNN models (not necessarily with PH), which the paper fails to do.\n2. The paper would benefit from listing all assumptions used in the derivation.\n3. The experiments could be strengthened by considering different GNN models augmented by different PersLay variants.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for your feedback. We reply to your comments/questions below.\n\n> It is hard to parse the significance of this work as the bound applies only to a restricted family of models augmented with PersLay. This issue could be mitigated by demonstrating that a model derived from this analysis is comparable with more advanced GNN models (not necessarily with PH), which the paper fails to do.\n\nThank you for the opportunity to clarify important aspects of our work. \n\nThe main result (Lemma 2) and the Corollaries about model compositionality apply to a broad class of models and are not restricted to models augmented with PersLay. We used GNNs combined with PersLay to showcase our developed recipe since, despite their increasing popularity [1,2,3,4], their generalization behavior is heavily underexplored.\n\nMoreover, our analysis can be extended to other GNN architectures, such as GraphSAGE. Indeed, given the similarity between GraphSAGE and GCN, our analysis already subsumes GraphSAGE, as we can upper-bound GraphSAGE by leveraging full neighborhoods. \n\nWe have included additional experiments with different PH-augmented GNNs (GCN, GraphSAGE, and GIN) in Table 2 of the rebuttal PDF. The results show the benefits of our bound used as a regularizer — the regularized variants achieve smaller generalization gaps and lower errors in most experiments.\n\n> The paper would benefit from listing all assumptions used in the derivation.\n\nThank you for this comment. While our main result (Lemma 2) does not make any assumptions beyond data being iid, we agree that the perturbation analysis requires certain assumptions. We will gladly include all assumptions in the Appendix and overview them in the main text.\n\nThe following list provides the assumptions:\n- Data (i.e. tuples) are i.i.d samples from some unknown distribution $\\mathcal{D}$.\n- the width of all layers is bounded by $h$ (stated in Lemma 2).\n- For MLP: all inputs are contained in the $\\ell_2$-ball of radius $B$.\n- For GCNs and MPGNNs: graphs are simple with maximum degree of $d$ and node features are contained in $\\ell_2$-ball of radius $B$. (listed in the caption for Table 2 in the main paper)\n- For PersLay: the norm of the elements of persistence diagrams are contained in a $\\ell_2$-ball with a radius $B$ and all of the considered point transformations and weight functions are Lipschitz continuous with respect to the parameters.\n\n> The experiments could be strengthened by considering different GNN models augmented by different PersLay variants.\n\nThanks for your suggestion. We have run additional experiments using regularized versions of GraphSAGE, GIN, and GCN combined with PersLay (see Table 2 in the rebuttal PDF). Overall, our results show that the regularized methods achieve smaller generalization gaps and slightly lower classification errors. We will add these experiments to the revised manuscript.\n\n> How does the bound for GNNs with PH compare with their counterparts without PH? Does the result provide any insights into why PH is beneficial for enhancing GNN performance?\n\nFrom Informal Lemma 4 (two models in parallel), $C_{norm}$ and $C_{pert}$ (as well as $T$) of the combined bound scale as the maximum of the corresponding parameters of the GNN and PersLay bounds. Since GNNs usually have more parameters than PH in practice, the bound for the combined network would scale with the GNN bound, so PH does not introduce a lot of overhead in the generalization performance. \n\nWe also note that combining PH with GNNs indeed improves the latter's expressivity [3,5] --- for instance, persistence diagrams contain information about the number of components and cycles that 1-WL (Weisfeiler-Leman) GNNs can not decide. However, while the expressivity of PH-augmented GNNs has been explored [5,6], their generalization capabilities remain largely uncharted, which is the motivation for our work.\n\n[1] PersLay. AISTATS 2020.\n\n[2] Topological neural networks go persistent, equivariant, and continuous. ICML, 2024.\n\n[3] Topological graph neural networks. ICLR 2022.\n\n[4] Position: Topological Deep Learning is the New Frontier for Relational Learning. ICML, 2024.\n\n[5] Going beyond persistent homology using persistent homology. NeurIPS 2023.\n\n[6] On the Expressivity of Persistent Homology in Graph Learning. arXiv, 2023\n\n---\nWe're grateful for your feedback. We hope our answers have addressed your concerns and improved your assessment of this work.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We are grateful to all the reviewers for their time and insightful comments, as well as to the (senior) area, program, and general chairs for their service to the community. 

We are pleased to note that reviewers appreciate the **novelty** (zp7n, toK8, Hv3h, ynbU) and the **presentation** (zp7n, toK8) of our work. Also reviewers found that our work provides a **flexible framework** (toK8) and **empirical evaluations on real-world datasets that demonstrate the practical applicability and effectiveness** (Hv3h).

To the best of our efforts, we have tried to address all the specific comments that have been raised by each reviewer.

Below, we provide some of the main revisions:

1. Reviewer zp7n asked about the dependency of our bounds on the number of model parameters. We used this opportunity to **clarify how PAC-Bayesian bounds depend on parameter values and hyper-parameters**. **Table 1** in the rebuttal PDF outlines these dependencies.

2. Reviewers zp7n and ynbU asked about other GNN architectures, such as GraphSAGE (zp7n). **We have run additional experiments considering GCN, GraphSAGE, and GIN combined with PersLay to assess the effectiveness of our theoretical bounds as a regularization scheme** (see **Table 2** of the rebuttal PDF). We considered 3 datasets (NCI1, NCI109, and PROTEINS) and reported test classification errors and empirical generalization gaps. Our results show that the regularized versions achieve competitive classification errors and significantly smaller generalization gaps. In addition, in Figure 2 (attached PDF), we show that our theoretical bound strongly correlates with the empirical gap for GraphSAGE.

3. Reviewer zp7n asked why the generalization bound increases with the number of epochs. To explain that, we report in **Figure 1 (attached PDF) the average spectral norms over training**. Interestingly, we observe that MLP layers dominate GNN ones — i.e., the average norm of MLPs is higher than that of GNNs.

4. Reviewer ynbU asked for clarification regarding the assumptions of our analysis. To summarize, **our main results (Lemma 2 and corollaries about compositionality) assume i.i.d data, while the remaining (model specific) results make typical assumptions related to perturbation analysis** (e.g., inputs lie in a $\ell_2$-norm ball, graphs have bounded degree). In the revised manuscript, we will list the assumptions for every result in the Appendix and overview them in the main text.

5. Reviewer toK8 suggested providing a discussion on takeaways from our theoretical analysis. **We will add the discussion about the choices of PersLay hyperparameters one can make informed by our theoretical bound**.

6.  Reviewers asked about analyzing learnable filtration functions. Below, we summarize the reasons behind our modeling choice as well as insights into how to extend results for the learnable filtration case:

    - **Fixed filtration functions dominate the PH/ML literature**. The widespread use of learnable functions is a relatively recent phenomenon in PH-based ML, and usually runs orders of magnitude slower compared to non-learnable ones. Arguably, applying non-learnable functions still represents the mainstream approach in TDA.

    - **Some works have explicitly advocated for fixed filtration functions (with learnable vectorizations) over learnable filtrations**. Filtration functions can come in different flavors; for instance, they can rely on node degree [1], cliques [2], or node attributes [3]. Some of the popular options are parameter-free. Also, while some works showed gains using learnable filtrations [4], others have reported no benefits and adopted fixed functions instead [5,6]. There is still no consensus about the significance of the gains associated with learnable filtration in many applications.

    - **Perslay [5] uses fixed filtration functions**. Despite the generality of our results, we provide specific bounds for PersLay, which employs fixed filtration functions.

    - **Our work lays a strong foundation for analyzing learnable filtrations**. One way to analyze PH with learnable filtration schemes could be to get upper bounds on perturbation of outputs in terms of the filtration function parameters. This would additionally require an analysis of Wasserstein distances between persistence diagrams obtained with different parameters. We believe that for a specific class of graphs we can get modified upper bounds for perturbation with respect to filtration function parameters that would depend on Wasserstein distance of the same order. This additional analysis could be readily integrated into our framework to get generalization bounds for learnable filtrations.

[1] Deep learning with topological signatures. NeurIPS 2017.

[2] Networks and cycles: A persistent homology approach to complex networks. ECCS 2013.

[3] Going beyond persistent homology using persistent homology. NeurIPS 2023.

[4] Topological GNNs. ICLR 2022.

[5] PersLay. AISTATS 2020.

[6] Improving Self-supervised Molecular Representation Learning using Persistent Homology. NeurIPS 2023.

---

We thank reviewers again for their very constructive comments.

Meta-review: This paper uses a PAC-Bayes framework to recover known generalization bounds for MLPs and GNNs, and derive new generalization bounds for GNNs with additional topological features. Experiments show that these bounds correlate well with empirical generalisation performance, and a regularization technique based on the analysis in this paper was shown to yield good results.

The reviewers have voiced some concerns regarding the nichenss of the particular topological GNNs used. Nonetheless, most reviewers found the technical contribution of generalization using PAC-Bayes important, and recommended acceptance.
Decision: Accept (poster)