Curvature Filtrations for Graph Generative Model Evaluation
Authors: Joshua Southern
Jeremy Wayland
Michael M. Bronstein
Bastian Rieck
Venue: NeurIPS 2023 poster (2023)
Keywords: Curvature
topology
persistent homology
graph learning
generative model
machine learning
geometric deep learning
TL;DR: We present a stable, expressive, and scalable method for graph generative model evaluation based on discrete curvature and topological data analysis.

Abstract: Graph generative model evaluation necessitates understanding differences between graphs on the distributional level. This entails being able to harness salient attributes of graphs in an efficient manner. Curvature constitutes one such property of graphs, and has recently started to prove useful in characterising graphs. Its expressive properties, stability, and practical utility in model evaluation remain largely unexplored, however. We combine graph curvature descriptors with emerging methods from topological data analysis to obtain robust, expressive descriptors for evaluating graph generative models.

Curvature Filtrations for Graph Generative Model Evaluation
Joshua Southern' Imperial College London jks170ic ac. uk
Jeremy Wayland
Helmholtz Munich & Technical University of Munich jeremy wayl wayland@tum..
Michael Bronstein!
Bastian Rieck
University of Oxford michael. bronsteinccs......m......o. ox. ac uk
Helmholtz Munich & Technical University of Munich
bastian weriiin.rieekeeee rreccktuumcco
Abstract
Graph generative model evaluation necessitates understanding differences between graphs the distributional level. This entails being able to harness salient attributes of graphs in an efficient manner. Curvature constitutes one such property that has recently proved its utility in characterising graphs. Its expressive properties, stability, and practical utility in model evaluation remain largely unexplored, however. We combine graph curvature descriptors with emerging methods from topological data analysis to obtain robust, expressive descriptors for evaluating graph generative models.
Introduction
Graph-structured data are prevalent in a number of different domains, including social networks [48], bioinformatics [38,59] 59], and transportation [33]. The ability to generate graphs from distribution a burgeoning technology with promising applications molecule or protein design [34, 35], as well as circuit design [47]. To compare graph generative models and advance research in this area, it essential to have a metric that can measure the distance between a set of generated and reference graphs, with enough expressivity critically evaluate model performance. Typically, this is done by using a set of descriptor functions, which map a graph to a high-dimensional representation in I2. An evaluator function, such the maximum mean discrepancy [27, MMD], may then be used get a distance between two distributions of graphs by comparing their vectorial representations [44, 53]. This state of the art was recently critiqued by O' O'Bray al. [54] since (i) requires numerous parameter and function choices, (ii) is limited by the expressivity of the descriptor function, and (iii) does not come equipped with stability guarantees.
We propose to overcome these issues through topological data analysis (TDA), which is capable of capturing multi-scale features of graphs while being functions. TDA is built on the existence of a function of the form : V + R. or f: E - R on graph G = (V, E). This used obtain filtration, i.e. an ordering of subgraphs, resulting in set of topological descriptors, the persistence diagrams. Motivated by their expressive power and computational efficiency, use recent notions of discrete eurvature [19, 24, 55] define filtrations and calculate persistence landscapes [10] from the persistence diagrams, thus obtaining a descriptor whose Banach space formulation permits statistical calculations. Our proposed method comes equipped with stability guarantees, can count certain substructures and measure important graph characteristics, and can used to evaluate variety of statistical tests since it permits computing distances between graph distributions.
expressive than simple descriptor
'These authors contributed equally, These authors jointly directed the work.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Our contributions are as follows:
We provide thorough theoretical analysis of the stability and expressivity of recent notions of discrete curvature, showing their fundamental utility for graph learning applications.
Using discrete eurvature and TDA, we develop new metric for graph generative model evaluation.
Our experiments reveal our metric is robust and expressive, thus improving upon current approaches that use simple graph descriptor and evaluator functions.
2
Background
The topological descriptors used in this paper are based on computational topology and discrete curvature. We give an overview of these areas and briefly comment on previous work that makes use of graph statisties in combination with MMD. In the following, we consider undirected graphs denoted by G = (V, E), with a set of vertices V and set of edges E S V x V.
2.1
MMD and Metries Based On Graph Statisties
MMD a powerful method for comparing different distributions of structured objects. It employs kemnl functions, i.e. positive definite similarity functions, and can thus be directly combined with standard graph kernels [8] for graph distribution comparison. However, there are subtle issues when calculating kernels in R Gaussian kernels geodesic metric spaces, for instance, have limited applicability when spaces have non-zero curvature [23], and certain kernels in the literature are indefinite, thus violating one of the tenets of MMD [54]. Despite these shortcomings. MMD is commonly used to evaluate graph generative models [17, 71J. This is accomplished by extracting feature vector from each graph, such as the clustering coefficient node degree, and subsequently calculating empirical MMD values between generated and reference samples. Some works [49] combine multiple structural properties of graphs into single metric through the Kolmorogov- Smirnov (KS) multidimensional distance [39]. Combining graph statistics into single measure has also led to metrics between molecular graphs, such as the quantitative estimate of drug- likeness (QED), which is common measure in drug discovery [5]. However, these simple statistics, even when considered jointly, often lack expressivity, have no stability guarantees, and their use with MMD) requires numerous parameter and function choices [54].
2.2 Computational Topology
Computational topology assigns enturiaants-chaaatteiiini properties that remain unchanged under certain transformations- topological spaces. For graphs the simplest invariants are given by the 0-dimensional (6o) and 1-dimensional (31) Betti numbers. These correspond to the number of connected components and number of cycles, respectively, and can be computed efficiently. Their limited expressivity can be substantially increased when paired with scalar-valued filtration function f: E R.3 Since can only attain finite number of values ag, a1. a2.... on the graph, this permits calculating graph filtration 0 C Go S G1.
Gk-1 C G = G, where each G3 := (V,, E.). with E, = fe E f(e) S a and V, == {u E V Ee Eş s.t. E e}. This sublevel ser filtration' permits tracking topological features, such as cycles, via persistent homology [21]. If topological feature appears for the first time in G, and disappears in Gj, we represent the feature as a tuple (a,, az), which we can collect in a persistence diagram D). Persistent homology thus tracks changes connected components and cycles over the complete filtration, measured using a filtration function f. Persistence diagrams form a metric space, with the distance between them given by the bottleneck distance, defined as d (D, D') := (inf.): n D- sup ||x Ty(2) sl.)), where ranges over all bijections between the two diagrams. A seminal stability theorem [14] states that the bottleneck distance between persistence diagrams Dy. Dy. generated from two functions f and on
the same graph, is upper- bounded by dæ D/. D2) S ilf glloo. The infinity norm of the functions, a geometrical quantity, hence limits the topological variation. In practice, we convert persistence diagrams to equivalent representation. the persistence landscape [10]. which is more amenable to statistical analyses and the integration into machine learning pipelines.
1 Onn can also consider functions over vertices, f: V > IR, when building filtrations. See Appendix B.1 for a remark on the equivalence of these viewpoints. 'Swapping 's" for "z' and max for min results in the superlevel set filtration of equal expressivity.

---

Advantageous Properties. Persistent homology satisfies expressivity and stability properties. The choice of filtration f affects expressivity; with the right filtration. persistent homology can be more expressive than the 1-WL. test 57], which is commonly used to bound the expressivity of graph neural networks [50, 52, 70]. Thus, given a suitable filtration, we can create robust and expressive metric for comparing graphs. Moreover, as we will later see, 'DA improves the expressivity of any f. meaning that even if the function on its own is not capable of distinguishing between different graphs, using it in a filtration context can overcome these deficiencies.
2.3 Discrete Curvature
While filtrations can be learnt [29, 31], in the absence of well-defined learning task for graph generative model evaluation, we opt instead to employ existing functions that exhibit suitable expressivity properties. Of particular interest are functions based on discrete curvature, which was shown to be an expressive feature for graph and molecular learning tasks [65, 68, 69]. Curvature is fundamental concept in differential geometry and topology, making it possible to distinguish between different types of manifolds. There are variety of different curvature formulations with varying properties, with Ricci curvature being one of the most prominent. Roughly speaking, Ricci curvature is based on measuring the differences in the growth of volumes in a space as compared to model Euclidean space. While originally requiring a smooth setting, recent work started exploring how to formulate theory of Ricci curvature in the discrete setting [16, 19, 24, 45, 55, 62]. Intuitively, discrete curvature measures quantify a notion of similarity between node neighbourhoods, the discrete concept corresponding to 'volume.' They tend to be larger for structures where there overlapping neighbourhoods such as cliques, smaller (or zero) for grids and lowest (or negative) for tree-like structures. Ricci curvature for graphs provides us with sophisticated tools analyse the neighbourhood of an edge and recent works have shown the benefits of using some of these curvature- based methods in combination with Graph Neural Networks (GNNs) to boost performance [65], assess differences between real-world networks [61]. or enable graph rewiring to reduce over-squashing in GNNs [64]. However, the representational power and stability properties of these measures remain largely unexplored. Subsequently, we will focus on three different types of curvature, (i) Forman- Ricci curvature [24]. (ii) Ollivier- Ricci curvature [55], and (iii) Resistance curvature [19]. We find these three notions to be prototypical of discrete curvature measures, increasing in complexity and in their ability to capture global properties of graph.
Forman-Rieci Curvature.
The Forman(-Ricci) curvature for an edge (i,j) E E is defined as Kpp(i,j) := 4- d, - d, #l
(I)
where d; is the degree of node i and |# is the number of 3-cycles (i.e. triangles) containing the adjacent nodes.
Ollivier-Rieci Curvature. Ollivier introduced a notion of curvature for metric spaces that measures the Wasserstein distance between Markov chains, i.e. random walks, defined on two nodes [55]. Let G be graph with some metric de. and the be probability measure on G for node v E V. The RilivierRRicei curvature of any² pair j E V x V with + j is then defined as
1
KOR (i,j):=11 =
Wi(ss pg),
(2)
do(1.))
where W1 refers to the first Wasserstein distance between μ4g py. Eq. (2) defines the Ollivier- Ricci (OR) curvature in a general setting outlined by Hoorn et al. [30]; this is in contrast to the majority of previous works the graph setting which specify de to be the shortest-path distance and /4, to be uniform probability measures in the 1-hop neighbourhood of the node. Extending the probability measures so that they act on larger locality scales known to be beneficial for characterising graphs [4, 26, 36]. We assume this general setting to define different notions of OR curvature on the graph, permitting us the flexibility of altering the probability measure and the metric.
Resistance Curvature. The resistance curvature for edges of a graph, as established in Devriendt and Lambiotte [19], is inspired by Ohm's Law and the concept of effective resistance, a well-studied, global metric between nodes in weighted graph that quantifies the resistance exerted by the network
In contrast to other notions of curvature, Ollivier-Raae Ricci curvature is defined for both edges and non-edges.
3

---

G-N.b
Figure An overview of our pipeline for evaluating graph generative models using discrete curvature. We depict graph's edges being coloured by KFR. as described in Eq. (1), ordering edges gives rise to a curvature filiration, followed by corresponding persistence diagram and landscape. For graph generative models, we select curvature, apply this framework element-wise and evaluate the similarity of the generated and reference distributions by comparing their average landscapes.
when current flows between nodes. For graph G = (V,E), let Ray be the resistance distance between nodes i.j V. defined in Eq. (9). The node resistance curvature of node i V is then defined as P4 == 2 Eje curvature, then defined as
jui Rji- The curvature of an edge (i, E F,, what we refer to as resistance
2(p + Pi)
AR
Raj
The resistance curvature of an edge is related to the average distance between the neighbourhoods of the nodes connected by the edge.
3 Our Method
Each notion of discrete curvature yields scalar-valued function on the edges of a graph. We use these functions define family of curvature filtrations based sublevel sets. In combination with persistent homology, this enables us to assess the structural properties of given graph at multiple scales, measured curvature. Using metrics on aggregated topological signatures- here, in the form of persistence landscapes-we may then compare two distributions of graphs. Specifically, we propose the following scheme for graph generative model evaluation:
1. Given a specific curvature filtration, we generate a set persistence diagrams that encode the persistent homology dimensions and for each graph in the distribution. Each diagram tracks the lifespan of connected components and cycles as they appear in the filtration of a given graph, resulting in multi-scale summary of the graph's 's structure.
To permit an analysis on the distributional level, we convert each diagram into more suitable rep- resentation, namely persistence landscape. functional summaries of topological information, persistence landscapes allow for easy calculation of averages and distances [10].
Finally, we conduct statistical comparisons between graph distributions, c.g. permutation using p-norms, in this latent space, providing expressive metric for evaluating generative models.
Figure illustrates our proposed pipeline using Forman-Rice curvature. For choosing notion of curvature in practice, implementation details, and computational performance we refer the reader Section 3.3, Appendix A, and Appendix G respectively. We also make framework publicly available.
3.1 Stability
We first discuss the general stability of topological calculations, proving that changes in topological dissimilarity bounded by changes in the filtration functions. Moreover, we show that filtrations based on discrete curvature satisfy stability properties the underlying graph is modified.
Topological Features. Using the persistent homology stability theorem [14], we know that if two curvature filtrations similar graph, their persistence diagrams will also be similar. However, the theorem only holds for two different functions on the same graph, whereas the distributional case has not yet been addressed by the literature. Our theorem provides (coarse) upper bound.
'Source code is available

---

Theorem 1, Given graphs F = (VF. and G = (Va, EG) with filtration functions f.g. and corresponding persistence diagrams p Dg. we have dD(Dr.DD Dg) I max max(dis(ff .), dis(g. f)}, where dis(J' g) == [max f(z) mi g(y)l and vice versa for dis(g.
This upper bound implies that changes the level of persistence diagrams bounded by changes between the input functions. The stability of our method thus hinges on the stability of the filtration functions, so need to understand the behaviour of curvature under perturbations. Following previous work [54], we aim to understand and quantify the stability of our method in response to adding and deleting edges in the graph. Our stability theorems establish bounds various discrete curvature measures for finite, unweighted, connected graphs in response to these perturbations. We restrict the outcome of a perturbation to graphs of the form G' = (V, E²) that satisfy | A |E" and do not change the number of connected components of a graph. Our theoretical results bound the new curvature k' according to the structural properties of G. For an exhaustive list of theorems and proofs, as well as experiments analysing the change in curvature for perturbed Erdós -énnyi (ER) graphs, see Appendix B and Appendix D.
Forman-Ricci Curvature. We first analyse Forman-Ricct curvature KFR, and prove that it is stable with respect adding and deleting edges.
Theorem 2. G' is the graph generated by edge addition, then the updated Forman curvature K
for pre-existing edges (i,j) F. can be bounded by kr)(i,j) 1 S kipg( S krrli,]) 2. If G' is the graph generated by edge deletion, then the updated Forman curvature kpp for pre-existing edges (1,5) E E can be bounded by Kip(i, 2 k)p((,.) S kpp((,.) +1
Ollivier-Rici Curvature. Let 9 = (G,do, (4) be a triple for specifying Ollivier-Ricei curvature calculations, with G denoting an unweighted, connected graph, de its associated graph metric, and : {ee V E V} a collection of probability measures at each node. Furthermore, let 6, denote the Dirac measure at node i and (ii == W1 (ō,, (4)) the corresponding jump probability in the graph G as defined by Ollivier [55]. Following an edge addition or deletion, we consider an updated triple g' (G', do J(), and remark that this yields updated Wasserstein distance Wi, calculated in terms of the new graph metric dg.
Theorem 3. Given perturbation (either edge addition edge deletion) producing G', the Ollivier- Ricci curvature NOR (i) of a pair (i, can be bounded via
1
J'(1) + J'(i)
do (i,5) 1W max + Wi(ps, pz)] S (on(i. S do (i,j)
(4)
where J'(v)= := (8e. p(r) refers to the new jump probabilities and W max == max Wi( M')) denotes the maximal reaction to the perturbation (measured using the updated Wasserstein distance).
Resistance Curvature. Let G be an unweighted, connected graph with a resistance distance Rij and resistance curvature (ig i) for each (i, F. Furthermore, let d. denote the degree for node I E V. We find that KR is well-behaved under these perturbations, in the sense that edge additions can only increase the curvature, and edge deletions can only decrease it. For edge additions, we obtain the following bound (see Appendix B.1.3 for the corresponding bound for edge deletions).
Theorem 4. If Gf is the graph generated by edge addition, then KiR 2 Kg. with the following bound:
(i KR( 5 Auda + dz) Raj - Aadd
(5)
where Aadd := jax (R.g 1 (6. ))
The implications of this section are that (i) the stability of our topological calculations largely hinges on the stability of the functions being used to define said filtrations, and (ii) all discrete curvature measures satisfy stability properties with respect to changes in graph connectivity, making curvature-based filtrations highly robust.
3.2 Expressivity
metric between distributions should be non-zero when the distributions differ. For this to occur, metric needs to be able to distinguish non-isomocphic graphs and be sufficiently expressive. Horn
5

---

et al. [31] showed that persistent homology with an appropriate choice of filtration is strictly more expressive than 1-WL, the 1-dimensional Weisfeiler-Le(h))) test for graph isomorphism. A similar expressivity result can be obtained for using resistance curvature node feature [65], underlining the general utility of curvature. We have the following general results concerning the expressivity or discriminative power of our topological representations.
Theorem 5. Given two graphs F = (VF, and G = (Vc. Ec) with scalar-valued filtra- tion functions f.g. and their respective persistence diagrams Dg. have d (D Dg) Z infy: Ex Su [f(x) - g(n(x))), where yi ranges over all maps from Er to Eg.
Theorem 5
implies that topologiall distances are generally more discriminative than the distances between the filtration functions. Thus, calculating topological representations of graphs based on class of functions improves discriminative power. To further understand the expressive power of curvature filtrations, we analyse strongly-regular graphs, which are often used for studying GNN expressivity as they cannot be distinguished by k-WL, the k-dimensional Weisfeiler- Le test, if l $ 3 [2, 7, 52]. Additionally, we explore how curvature filtrations can count substructures, an important tool for evaluating and comparing expressivity [56]. To the best of our knowledge, ours is the first work to explore discrete curvature and eavature-based filtrations in this context.
Distinguishing
Graphs. gtrongly-regulas graphs are often used assess the
expressive power of graph learning algorithms, constituting a class of graphs that are particularly hard to distinguish. We briefly recall some definitions. A connected graph G' with diameter D is called distance regular if there are integers b,, Ct (0 S is D) such that for any two vertices z, E V with d(x, y) i, there are C, neighbours of y in (z) and b, neighbours of y in k441 (I). For distance-regular graph, the intersection array is given by (bo. bi....,bb, bn- C12 C2, (2,...,pp) A graph is called strongly regular if is distance regular and has diameter of 2 [18]. We first state two theoretical results about curvature.
Theorem 6 (Expressivity of curvature notions). Both Bamman-Riett curvature and Resistance curvature cannot distinguish eestance-regulee graphs with the same intersection array, whereas Ollivier-Ricii curvature can distinguish the Rook and Shrikhande graphs, which are strongly-regulat graphs with the same intersection array.
The Rook and Shrikhande graph cannot be distinguished by 2-WL [9, 52]. However, OR curvature is sensitive to differences in their first-hop peripheral subgraphs [22], thus distinguishing them. This result shows the limitations of Forman-Ricel and Resistance curvature, as well as the benefits of using Ollivier-Ricci curvature. We show further experiments with curvature notions on strongly-regular graphs in the experimental section, observing improvements whenever we use them as filtrations.
Counting Substructures. Evaluating the ability of curvature to encode structural information is crucial aspect for understanding its expressivity and validating its overall utility in graph learning. It has previously been shown that incorporating structural information of graphs can extend the expressive power of message-passing [9] show how GNNs can be (i) strictly more expressive than 1-WL by counting local isomorphic substructures (e.g. cliques), and (ii) exhibit predictive performance improvements when adding such substructure counts to the node features. For instance, some strongly-regular graphs can be distinguished by counting 4-cliques. Discrete curvature measures are informed by these local substructures and have been shown to improve expressivity beyond 1-WL [65] when included as node feature. Nevertheless, there is limited work exploring what substructure information curvature carries, which would allow us to describe the expressivity of the measure. Moreover, persistent homology can track the number of cycles over the filtration of interest, allowing additional structural information to be encoded at multiple scales. Thus, we will explore the extent to which substructures can be counted for different curvatures (with and without topological component) in a subsequent experiment, providing evidence on the expressive power of curvature filtrations. See Table 4 for our experimental results, and Appendix E for a more detailed discussion on the tendencies of each curvature notion when counting substructures.
neural networks [11, 25, 42]. Additionally, Bouritsas et al.
3.3 Choosing Curvature Notion in Practice
In Section 3.1, we showed that all three of our prototypical curvature notions exhibit advantageous stability properties, thus implying that they may all be used reliably within our method to measure

---

the distance between two sets of graphs. However, which curvature should be chosen in practice? In general, we find that the answer to this question lies at the intersection of expressivity and sealability, but depends ultimately on the nature of the experiment at hand. Nevertheless, we aim to provide an intuition for all three notions, along with a general recommendation. We hope this, in conjunction with the experimental and computational complexity results in Section 4 and Appendix G will help practitioners in making an optimal choice.
Comparison. Forman-Rieci is arguably the simplest and most local notion of curvature. Though limited in expressivity when compared to Ollivier-Ricci curvature, is by far the most efficient to compute. Resistance curvature, by contrast, is the most global notion, making it sensitive to large substructures. However, computing the effective resistance metric on a graph requires inverting the Laplacian, making it far less efficient than Forman and Ollivier-Ricch especially for large graphs. Finally, we have Ollivier-Ries curvature, which we have found to be the most expressive based on its ability to (i) distinguish strongly-regula graphs, and (ii) count substructures. It is also the most versatile, given the option to adapt the underlying probability measure; this comes at the cost of lower computational performance in comparison to Forman Ricci curvature, though.
Given its high expressivity. as well as its overall experimental and computational performance, we recommend using Ollivier-Ried curvature whenever feasible.
4 Experiments
We have proven the theoretical stability of discrete curvature notions under certain graph perturba- tions. We also illustrated their ability to distinguish distance-regular and strongly-regulat graphs Subsequently, we will discuss empirical experiments to evaluate these claims and to further test the utility of our methods.
4.1 Distinguishing Strongly-Reenn Regular Graphs
In addition to the theoretical arguments outlined, we explore the ability of our method to distin- guish strongly-regular graphs in a subset of data sets, i.e. sr16622, sr261034, sr281264, and sr401224. These data sets are known to be challenging classify since they cannot be de- scribed in terms of the 1-WL test [7]. Our main goal is not to obtain the best accuracy, but to show how the discriminative power of discrete curvature can be improved by using in a filtra- tion context. Table depicts the results of our classification experiment. We perform pairwise analysis of all graphs in the data set, calculating distances based on histograms of discrete curvature measurements, or based on the bottleneck distance between persistence diagrams ( ('Filtrations') Subsequently, we count all non-zero distances (> x 10-8 8 to correct for precision errors). Our main observation is that combining TDA with curvature is always better than or equal to curvature without TDA. Similar to our theoretical predictions, both resistance curvature and Forman curvature fail to distinguish any of the graphs without TDA. We therefore show the benefits from an expressivity point of view for using discrete curvature as a filtration. Notably, we achieve the best results with OR curvature, which is particularly flexible since it permits changing the underlying probability measure. Using probability measure based on random walks (see Appendix F) takes into account higher-order neighbourhoods and improves discriminative power (on sr261034, the pairwise success rate drops to 0.0/0.2 with raw/TDA values, respectively, if the uniform probability measure is used).
Table 1: Success rate (1) of distinguishing pairs of strongly-regular graphs when using either raw curvature values curvature filtration.
Method
sr16622
sr261034
sr281264
sr401224
KER
0.00
0.00
0.00
0.00
1,00
0.78
1.00
0.00
Xi
0.00
0.00
0.00
0.00
Filtration (Mep))
1,00
0.20
0.00
0.93
Filiration (FiRR)
1.00
0.89
1.00
0.93
Filiration
1,00
0.20
0.00
0.93
4.2 Expressivity experiments with the BREC dataset
We evaluate discrete curvatures and their filtrations on the BREC data set, which was recently introduced to evaluate GNN expressiveness [66]. The data set consists of different categories of graph pairs (Basic, Regular, and Extension), which are distinguishable by 3-WL. but not by 1-WL, as well as Errongly-Regular (STR) and CFI graph pairs, which are indistinguishable using 3-WI.. We explore the ability of curvature filtrations to distinguish these graph pairs and compare them
7

---

Table Success rate (f) of distinguishing pairs of graphs in the BREC dataset when using different discrete curvatures and their filtrations.
Method
Basic (56)
Regular (50)
STR
Extension (97)
CFI
1-WL
0.00
3.WI.
1.00
1.00
0.00
1.00
0.59
Sa S4
0.86
0.96
0.00
0.05
0.00
1.00
0.98
1.00
0.84
0.00
KoR
1.00
0.96
0.06
0.93
0.00
KER
0.52
1,00
1.00
0.00
1,00
0.04
Flltration (NOR)
1.00
0.08
0.95
0.00
Filtration (Arr)
0.98
0.96
0.04
0.61
0.00
Filtration (x5g)
1.00
to substructure counting, S3 and S4, which involves enumerating all 3-node/4-node substructures around nodes in combination with the WL algorithm. These approaches, unlike discrete curvature, have limited practical applications due to their high computational complexity. Similar to our experiments on strongly-regular graphs, we calculate Wasserstein distances based histograms of OR curvature measurements between the pairs of graphs. Subsequently, we count all non-zero distances (> 1 x 10- 8 correct for precision errors). Our main observations from Table that curvature can distinguish graphs which are 3- indistinguishable. Additionally, we observe improvements in success rate using the filtration the Basic, Regular, STR and Extension graph pairs. Moreover, our peraturr-bbsed approach performs competitively and sometimes even better than S4, which has been shown to be extremely effective in graph learning tasks [9]. Despite its empirical prowess, S4 is computationally expensive, making it an infeasible measure in many applications. Discrete curvature and its filtrations, by contrast, scale significantly better.
4.3 Behaviour with Respect to Perturbations
To explore the behaviour of curvature descrip- tors under perturbations, we analyse the corre- lation of our metric when adding and remov- ing edges in the "Community Graph' data set: increase the fraction of edges added moved from 0.0 to 0.95, measuring the distance between the perturbed graphs and the original graphs for each perturbation level. Following O'Bray et al. [54], we require a suitable distance measure to be highly correlated with increasing amounts of perturbation. We compare to cur- rent approaches that use descriptor functions with MMD. As Table 3 shows, curvature filtra- tion yields a higher correlation than curvature in combination with MMD, showing the benefits of employing TDA from a stability perspective. Addi- tionally, curvature filtrations improve upon the normalized Laplacian and clustering coefficient (again, we used MMD for the comparison of these distributions). OR curvature exhibits particularly strong results when adding/removing edges, even surpassing the local degrees of a graph (which, while being well-aligned with perturbations of the graph structure, suffer terms of overall expressivity).
Table 3: Pearson correlation (1) of measures when adding/removing edges.
Measure
Adding Edges
Removing Edges
Laplacian Clust. Coeff. Degrees
0.457 0.013
0.420 0,000
0.480 0.012
0.504 0.020
0.761 0.003
0.995 + 0.000
KFR
0.420 + 0.000
0.432 + 0.003
HOR
0,903 = 0.005
0,910 + 0,002
0.420 + 0.004
0.441 # 0.005
Filtration (NpR)
0.571 + 0.006
0.996 0.001 0.006
Filtration (NOR)
0.997 = 0.000
0.970 + 0.005
Filtration (rg)) 0.730 + 0.005
+
4.4 Counting Substructures
The ability of descriptor count local substructures is important for evaluating its expressive power [3]. We follow Chen et al. [12], who assess the ability of GNNs to count substructures such triangles, chordal cycles, stars and tailed triangles. This is achieved by generating regular graphs with random edges removed, and counting the number of occurrences of each substructure in a given graph. To assess the power of curvature to capture such local structural features, we use the same experimental setup and pass the edge-based curvatures through simple 1-layer MLP to output the substructure count. Additionally, we evaluate the effect of using curvature as filtration.
8

---

Chotwing Celfaime
Move Neveauee Lipasie
0133
Iapakln
JUB
our
C/
6:1
672
14:33
Fibvakl
Fiburin
Adjusted
0.15
MOOTOM
Pring
3M
612
<
CC
oehres
6.0
My. Ma.
We. Mr. Ma.
Walli,
100
Graphons
(a) Curvature distinguishes graphon data sets
(b) Curvature distinguishes bioinformatics data sets
Figure 2: (a) Adjusted Rand Index (1) for clustering sets of four graphons. We compare our curvature filtrations (8) to kernel-based methods. (b) Permutation testing values (4) for distinguishing different
bioinformatics data sets. Position (i,j) each matrix denotes a permutation test between data set i and data set j.
Table 4: MAE (Q) for counting substructures based on raw curvature values and curvature filtrations. The 'Trivial Predictor' always outputs the mean training target.
Table 4 shows our experimental results, reported on the pre-defined test split defined by Chen et al. [12]. In comparison to Graph Convolu- tional Networks [40], find that OR curva- ture exhibits improved performance in counting small local structures such triangles and tailed triangles; this a surprising finding given the smaller computational footprint of this curvature formulation (in comparison to a GCN). More- over, we find that the OR curvature performs better than both the Forman curvature and the re- sistance curvature for the different substructures in the data. We also observe that combining cur- vature with TDA almost always improves upon using the curvature alone, the only exception being Forman curvature for counting 4-cycles. We leave more detailed investigation of these phenomena for future work.
Method
Triangle
Tailed Tri.
Star
4-Cycle
Trivial Predictor GCN
0.88
0.90
0.81
0.93
0.42
0.32
0.18
0.28
KER
0.54
0.56
0.72
0.53
NOR
0.33
0.31
0.40
0.31
MR
0.59
0.50
0.72
0.47
Filtration (Mea)
0.45
0.52
0.60
Filtration (Mog)
0.23
0.24
0.34
0.31
Filtration (Kg)
0.47
0.48
0.36
0.42
4.5 Synthetic Graph Generative Model Evaluation
To have a ground truth for a graph distribution, we tested our metric's ability to distinguish graphons. Following the approach suggested by Sabanayagam al. [60], we generate four graphons, (u(, v) = ww, W2(u, v) = exp( max(u, 0)7.76, Wa(u, v) = cxp5-0.5 (min(u, v) + 0.5 o0 and Wa (u, v) |u vil. Sampling from these graphons produces dense graphs, and we control their size to be between 9 and 37 nodes, thus ensuring that we match the sizes of molecular graphs in the ZINC data set [32], an important application for generative models.
We perform experiments by considering all combinations of three and four graphons. We generate distances between graphs with our method as well as other kernel-based approaches, and use spectral clustering to separate the distributions. We measure the performance of the algorithms using the Adjusted Rand Index (ARI) of the predicted clusters, comparing three state of the art, kernel- based approaches: (i) Wasserstein Weisfeiler-Le(h)mee
graph kernels [63], (ii) graph neural tangent kernels [20], and (iii) Tree Mover's Distance [13]. From Figure 2a, we find that a filtration based on OR curvature is better able to distinguish and cluster graphons than the previously desccribe approaches based on kernels and performs best for all sets graphons.
also observe that OR curvature performs better than other discrete curvatures, with resistance curvature achieving higher ART than Forman curvature. Notice that unlike these kernel approaches, our method can easily extended to provide proper metric between distributions of graphs.

---

4.6 Real-World Graph Generative Model Evaluation
By converting the generated persistence diagrams into a persistence landscape, we can generate an average topological descriptor for all graphs in a distribution [10]. This allows us to calculate norms between graph distributions, making it possible to perform two-sample and permutation testing, unlike a majority of kernel-based approaches, which provide a distance between all individual graphs, or would require MMD assess mean similarities. We randomly sample ten graphs from four different bioinformatics data sets, i.c. KKI, PROTEINS, Peking, and ENZYMES [51]. We measure the distance between two data sets using the L" norm between their average persistence landscapes. We then permute graphs from both samples, randomly selecting sets of equal size, measure their respective distances, and finally aggregate the fraction of distances which are higher than the original. A low fraction indicates that distances are lower for permutations than between the original sets of graphs, suggesting that the metric can distinguish between the two distributions. We compare our approach to previous methods that combine graph statistics with MMD. Using a significance threshold of p < 0.05, we see in Figure 2b that both Forman and the OR curvature are able to distinguish all but one pair of data sets, improvement over all the other approaches. In general, we find that fractions are lower using curvature filtrations than graph statistic based approaches, demonstrating the utility of our approach.
5 Conclusion
We have described the first thorough analysis of both stability and expressivity of discrete curvature notions and their filtration formulations on graphs. We believe this to be important for the community in multiple contexts, ranging from improving expressivity of GNNs to understanding the robustness of curvature on graphs. Using curvature filtrations and their topological descriptors (here: persistence landscapes), we develop new metric to measure distances between graph distributions. Our metric can be used for evaluating graph generative models, is robust and expressive, and improves upon current approaches based on graph descriptor and evaluator functions. We have also demonstrated clear advantages over state-of-the-art methods that combine graph statistics with MMD, providing instead metric with (i) well-understood parameter and function choices, (ii) stability guarantees, (iii) added expressivity, and (iv) improved computational performance. Most notably, we scale significantly better for large populations of molecular-sized graphs (see Appendix G for more details), which we consider crucial for current graph generative model applications. We hope that our pipeline will provide principled, interpretable, and scalable method for practitioners use when evaluating the performance of graph generative models.
Future work could explore other representations [1, 58), focus on different filtration constructions [15], new curvature measures, or further extend our stability and expressivity results (for instance to the setting of weighted graphs) Given the beneficial performance and flexibility of Ollivier-Rieei curvature in our experiments, we believe that changing- learning probability measure used in its calculation could lead to further improvements in terms of expressivity, for example. Another relevant direction involves incorporating node and edge features into the distance measure and applying the model to specific use cases such as evaluating molecule generation. We envision that this could be done using bi-filtrations or by considering node features for the curvature calculations.
Acknowledgments and Disclosure of Funding
The authors want to thank the anonymous reviewers for their comments, which helped us improve the paper. We are also grateful for the area chair who believed in this work. The authors are grateful to Fabrizio Frasca and Leslie O' O'Bray for valuable feedback on early versions of the manuscript. J.S. is supported by the UKRI CDT AI for Healthcare http://ii4health.io (Grant No. P/S023283/1). M.B. is supported in part by the ERC Consolidator grant No. 724228 (LEMAN) and the EPSRC Turing AI World-Leading Researcher Fellowship. B.R. is supported by the Bavarian State government with funds from the Hightech Agenda Bavaria. He wishes to dedicate this paper to his son Andrin.
10

---

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, 2017.
[2] V. Arvind, Frank Fuhlbrücc, Johannes Köbler, and Oleg Verbitsky, On Weisfeiler-Leman invariance: Subgraph counts and related graph properties, 2018. URL https://arxxx org/ abs/1811. 04801.
[3] Pablo Barceló, Floris Geerts, Juan Reutter, and Maksimilian Ryschkov. Graph neural networks with local graph parameters, 2021. URL httpt::ttt//aaa http:///aaaaaaooaaaa//////////// 06707.
[4] Sophia Benjamin, Arushi Mantri, and Quinn Perian. On the Wasserstein distance between A-step probability measures on finite graphs, 2021. URL
http://wwvvv..../....../// org/ abs Aaabs/110 21100 10363.
[5] G. Richard Bickerton, Gaia V. Paolini, Jérémy Besnard, Sorel Muresan, and Andrew L Hopkins. Quantifying the chemical beauty of drugs. Nature Chemistry, 4(2):90-98, 2012.
[6] Norman L. Biggs. Potential theory on distance-regular graphs. Combinatorics, Probability and Computing, 2(3):243-255, 1993. doi: 10. 10.1017/50963548300006666
[7] Cristian Bodnar, Fabrizio Frasca, Yuguang Wang, Nina Otter, Guido F Montufar, Pietro Lió, and Michael Bronstein. Weisfeiler and Lehman go topological: Message passing simplicial networks. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 1026-1037. PMLR, 2021.
[8] Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López, Leslie O' O'Bray, and Bastian Rieck. Graph kernels: State-of-the-an and future challenges. Foundations and Trends@ in Machine Learning, 13(5 (3:5566:33-7111 2020. doi: 10.1561/2200000076.
[9] Giorgos Bouritsas, Fabrizio Frasca, Stefanos P. Zafciriou, and Michael Bronstein. Improving graph neural network expressivity via subgraph isomorphism counting. IEEE Transactions on Pattern Analysis and Machine Intelligence, pages 1-1, 2022. doi: 10. T0.10.9..P 3154319.
[10] Peter Bubenik. Statistical topological data analysis using persistence landscapes. Journal of Machine Learning Research, 16:77-102, 2015.
[11] Ting Chen, Song Bian, and Yizhou Sun. Are powerful graph neural nets necessary? A dissection on graph classification, 2019. URL. httttttts//aaaat org/ /905 04579.
[12] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? 2020. URL https: //trxxax.vvvv///////// org/
[13] Ching-Yao Yao Chuang and Stefanie Jegelka. Tree mover's distance: Bridging graph metrics and stability of graph neural networks. In Advances in Neural Information Processing Systems, volume 35, 2022.
[14] David Cohen- Steiinr, Herbert Edelsbrunner, and John Harer. Stability persistence diagrams. Discrete & Computational Geometry, 103-220 2007, doi: 10.10077/00445--00- 1276-5.
[15] David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Extending persistence using Poincaré and Lefschetz. duality. Foundations of Computational Mathematics, 911::9--003, 2009. doi: 10.1007/s10208-000 008-9027-2.
[16] Corinna Coupette, Sebastian Dalleiger, and Bastian Rieck. Oliivier-Ricci curvature for hyper- graphs: A unified framework. In International Conference on Learning Representations (ICLR), 2023. URL
[17] Hanjun Dai, Azade Nazi, Yujia Li, Bo Dai, and Dale Schuurmans. Scalable deep generative modeling for sparse graphs, 2020. URL https: //arxiv. org/ ang/abs/2006. 15502.

---

[18] Edwin R. Van Dam, Jack H. Koolen, and Hajime Tanaka. Distance-regular graphs. The Electronic Journal of Combinatorics, 1000, apr 2016. doi: 10.37236/4925.
[19] Karel Devriendt and Renaud Lambiotte. Discrete curvature on graphs from the effective resistance. Journal of Physics: Complexiry, 3(2):025008, 2022. doi: 00.1088/2632-072X/ ac730d.
[20] Simon S. Du. Kangcheng Hou, Russ Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kemel: Fusing graph neural networks with graph kernels, In H. Wallach, Larochelle, A. Beygelzimer, F. d'Alché- Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[21] Herbert Edelsbrunner and John Harer. Computational topology: introduction. American Mathematical Society, Providence, RI, USA, 2010.
[22] Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang, How powerful are k-hop message passing graph neural networks. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and Oh, editors, Advances Neural Information Processing Systems, volume 35, pages 4776 4790. Curran Associates, Inc., 2022.
[23] Aasa Feragen, François Lauze, and Søren Hauberg. Geodesic exponential kernels: When curvature and linearity conflict. In JEEE Conference on Computer Vision and Pattern Recogni- tion (CVPR), pages 3032-3042, 2015.
[24] Robin Forman. Bochner's 's method for cell complexes and combinatorial ricci curvature. Discrete Computational Geometry, 29(3):323-377 2003. doi: 111007//00454-002-077444-
[25] Floris Geerts, Filip Mazowiecki, and Guillermo A. Pérez. Let's agree to degree: Comparing graph convolutional networks in the passage-passing framework, 2020. URL httts::///attttt org/ /b///b////// 200//////200...2///////// 02593.
[26] Adam Gosztolai and Alexis Arnaudon. Unfolding the multiscale structure of networks with dynamical Ollivier Ricci curvature. Nature Communications, 12(1))4561, 2021. ISSN 2041-
1723. doi: 10. 10.10038/44447--22244445344
[27] Arthur Gretton, Karsten M. Borgwardt, Malte J. Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. Journal of Machine Learning Research, 13(25):723-773, 2012.
[28] Ji-Ming Guo, Pan-Pan Tong, Jianxi Li, Wai Chee Shiu, and thi-Wen Wang. The effect on eigenvalues of connected graphs by adding edges. Linear Algebra and its Applications, 548: 57-65, July 2018. doi: 10.1016/j 20.18,.....211102.0000
[29] Christoph D. Hofer, Florian Graf, Bastian Rieck, Mare Niethammer, and Roland Kwitt. Graph filtration learning. In Hal Daumé and Aarti Singh, editors, Proceedings of the 37th Inter- national Conference Machine Learning (ICML), number 1 119 in Proceedings of Machine Learning Research, pages 2314-4322 PMLR, 2020.
[30] Pim van der Hoom, Gabor Lippner, Carlo Trugenberger, and Dmitri Krioukov. Ollivier curvature of random geometric graphs converges to Ricci curvature of their Riemannian manifolds. Discrete & Computational Geometry, 70(3):671-713 2023. doi: 10. 10.10077/004444022--005777777
[31] Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. In International Conference Learning Representations (ICLR), 2022. URL
[32] John J. Irwin and Brian K. Shoichet. ZINC-a free database of commercially available com- pounds for virtual screening. Journal of Chemical Information and Modeling, 45(1):177-182, 2005.
[33] Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: survey. Expert Systems with Applications, 207:1 2022. doi: 10. 10.10166..ssa.2222..19911
12

---

[34] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 2323-2332. PMLR, 2018
[35] Wengong Jin, Jeremy Wohlwend, Regina Barzilay, and Tommi S. Jaakkola. Iterative refinement graph neural network for antibody sequence-structure co-design. In International Conference on Learning Representations (ICLR), 2022. URL https: https::t/tppeneeeeeee http://ppnrriiii.neeeeeeeeeee frd LI2bhrE_22 2A.
[36] Pakawut Jiradilok and Supanat Kamtue. Transportation distance between probability measures on the infinite regular tree, 2021. URL pettps://arxiyy org/abs/ ab///////210////////// Tww.22100...9111 09876.
[37] Jürgen Jost and Shiping Liu, Ollivier's ' Ricci curvature, local clustering and curvature- -imensiomnnn inequalities on graphs. Discrete & Computational Geometry, 51()):30--322 2014. doi: 10. 1..10077.00454--3-955858
[38] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron- neberger. Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, Alex Bridgland, Clemens Meyer, Simon A. A. Kohl, Andrew J. Ballard, Andrew Cowie. Bernardino Romera-Paredes, Stanislav Nikolov, Rishub Jain, Jonas Adler, Trevor Back, Stig Petersen, David Reiman, Ellen Clancy, Michal Zielinski. Martin Steinegger, Michalina Pacholska, Tamas Berghammer, Sebastian Bodenstein, David Silver, Oriol Vinyals, Andrew W. Senior, Koray Kavukcuoglu, Pushmeet Kohli, and Demis Hassabis. Highly accurate protein structure predic- tion with AlphaFold. Nature, 596(7873):583-58) 2021. doi: 10.10388/41588-001-33331
[39] Ana Justel, Daniel Peña, and Rubén Zamar. A multivariate Kolmogorov- Smiroov test good- ness of fit. Statistics & Probability Letters, 35(3):511253 1997. doi: 10.1016680017--71522077 00020-5.
[40] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017. URL
https://openrevies: wttp://sw.....oooooooottaaaaaaaa
[41] Jack H. Koolen, Greg Markowsky, and Jongyook Park. On electric resistances for distance- regular graphs. European Journal of Combinatorics, 34(4):770-766, 2013. doi: 10.1016/j..jc. 2012.12.001.
[42] Michael Lingzhi Li, Meng Dong, Jiawei Zhou, and Alexander M. Rush. A hierarchy of graph neural networks based on learnable local features, 2019. URL hwtps::tt////stta org/ abs/ 15256....
[43] Pan Li, Yanbang Wang, Hongwei Wang, and Jure Leskovec. Distance encoding: Design provably more powerful neural networks for graph representation learning. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 4465-4478. Curran Associates, Inc., 2020.
[44] Renjie Liao, Yujia Li, Yang Song, Shenlong Wang, Charlie Nash, William L. Hamilton, David Duvenaud, Raquel Urtasun, and Richard S. Zemel. Efficient graph generation with graph recurrent attention networks, 2019. URL attps:///axxet org/ abs/1910. atb.//91..00060..
[45] Shiping Liu, Florentin Münch, and Norbert Peyerimhoff. Bakry-Emery curvature and diameter bounds on graphs. Calculus of Variations and Partial Differential Equations, 57(2), 2018. doi: 10.1007/s00526-00 1334-x.
[46] L. Lovász. Random walks graphs: A survey. In D. Miklós, T. Sós, and T. Szōnyi, editors, Combinatorics, Paul Erdös is Eighty, volume 2, pages 353-398. János Bolyai Mathematical Society, Budapest, 1996.
[47] Azalia Mirhoseini, Anna Goldie, Mustafa Yazgan, Joe Wenjie Jiang, Ebrahim Songhori, Shen Wang, Young-Joon Lee, Eric Johnson, Omkar Pathak, Azade Nazi, Jiwoo Pak, Andy Tong, Kavya Srinivasa, William Hang. Emre Tuncer, Quoe V. Le, James Laudon, Richard Ho, Roger Carpenter, and Jeff Dean. A graph placement methodology for fast chip design. Nature, 594 (7862):207-11,, 2021. doi: 11.1038//4118--022 -21-03544...
13

---

[48] Federico Monti, Fabrizio Frasca, Davide Eynard, Damon Mannion, and Michael M. Bronstein. Fake news detection on social media using geometric deep learning, 2019. URL https:
org/ abs//902. 06673.
[49] Sebastian Moreno, Jennifer Neville, and Sergey Kirshner. Tied Kronecker product graph models to capture variance in network populations. ACM Transactions on Knowledge Discovery from Data, 12(3), 2018. doi: 10.1 145/3161885.
[50] Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. Proceedings of the AAAI Conference on Artificial Intelligence, 33(1):4602-4600
2019. doi: 10. 1009/a9aaai, v33101 .33014602.
[51] Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. TUDataser: A collection of benchmark datasets for learning with graphs, 2020. URL
https://arxixn org/ awspabb... 08663.
[52] Christopher Morris, Yaron Lipman, Haggai Maron, Bastian Rieck, Nils M. Kriege, Martin Grohe, Matthias Fey, and Karsten Borgwardt. Weisfeiler and Leman go machine learning: The story so far, 2021. URL https: /ttppp:///rxiiii
09992.
[53] Chenhao NIu, Yang Song. Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling, 2020. URL https://arxiv org/ abs/2003. 00638.
[54] Leslie O' O'Bray, Max Horn, Bastian Rieck, and Karsten Borgwardt. Evaluation metries for graph generative models: Problems, pitfalls, and practical solutions. In International Conference Learning Representations (ICLR), 2022.
[55] Yann Ollivier. Ricci curvature of metric spaces. Comptes Rendus Mathematique, 345(1 1): 643-646, 2007, doi: 10. httptpp://arrii..orgaaa///////// atggabbs/20111 12884.
[56] Pál András Papp and Roger Wattenhofer. A theoretical comparison of graph neural network extensions, 2022. URL httttt/////aaat
[57] Bastian Rieck. On the expressivity of persistent homology in graph learning, 2023. URL https://arxiv.. org. abtp//2..23302..am// 09826.
[58] Bastian Rieck, Filip Sadlo, and Heike Leitte. Topological machine learning with persistence indicator functions. In Hamish Carr, Issei Fujishiro, Filip Sadlo, and Shigeo Takahashi, editors, Topological Methods in Data Analysis and Visualization V, pages 87-101. Springer, Cham, Switzerland, 2020. doi: 10. 10.1007/998--3000-440666
[59] Camilo Ruiz, Marinka Zitnik, and Jure Leskovec. Identification of disease treatment mechanisms through the multiscale interactome, Nature Communications, 12(1): 2021.
[60] Mahalakshmi Sabanayagam, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar. Graphon based clustering and testing of networks: Algorithms and theory. In International Conference on Learning Representations (ICLR), 2022. URL https: ttttps://opettt /ttp:///voe/eeeeeccomm forum?id=sTNHC+ IKDQc.
[61] Areejit Samal, R. P. Sreejith, Jiao Gu, Shiping Liu, Emil Saucan, and Jürgen Jost. Comparative analysis of two discretizations of Ricci curvature for complex networks. Scientific Reports, (1), 2018 8. doi: 10.
[62] Emil Saucan, Areejit Samal, and Jürgen Jost. A simple differential geometry for complex networks. Network Science, 110:)1063,133, 2021. doi: 10. 10.1017/nws.20200
[63] Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares- López, Bastian Rieck, and Karsten Borg- wardt. Wasserstein Weisfeiler-Lehman graph kernels. In H. Wallach, H. Larochelle, A. Beygelz- imer, F. d'Alché-Bue, E. Fox, and R. Garnett, editors, Advances in Neural Information Process- ing Systems (NeurIPS), volume 32. Curran Associates, Inc., 2019.
14

---

[64] Jake Topping, Francesco Di Giovanni. Benjamin Paul Chamberlain. Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations (ICLR), 2022. URL https:// wwwprreiwww.et/ffouundddddo/o
A.
[65] Ameya Velingker, Ali Kemal Sinop, Ira Ktena, Petar Veličković, and Sreenivas Gollapudi. Affinity-aware graph networks, 2022. URL https:///rxiyy berg/abs/2220 11941.
[66] Yanbo Wang and Muhan Zhang. Towards better evaluation of gnn expressiveness with BREC dataset, 2023. URL https: : //txxaaxvvvv/////////////////avl wwwp a0r///4b./300....//// 07702.
[67] Duncan J. Watts and Steven H. Strogatz. Collective dynamics of 'small-world" networks, Nature, 493066644)440-444,, 1998. doi: 10. 10.1038/30918.
[68] JunJie Wee and Kelin Xia. Forman persistent Ricei curvature (FPRC)-based machine learning models for protein-ligand binding affinity prediction. Briefings in Bioinformatics, 22(6):
bbab136, 2021. doi: 10. 1093/bib/bbbb13.
[69] JunJie Wee and Kelin Xia. Ollivier persistent Ricci curvature-based machine learning for the protein-ligand binding affinity prediction. Journal of Chemical Information and Modeling, 61 (4):1617-1626, 2021. doi: 1..022//acsjcim.0001141... URL https: //oii. 1//00...000 1021/ acs acs.jeim. ccs.jccim0cc0115. 0c01415.
[70] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. URL https:
[71] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages
PMLR, 2018
15

---

A Pseudocode
Here we give pseudocode for various parts of the method, highlighting the most relevant aspects of using curvature filtrations to evaluate graph generative models. First, we outline a crucial part of our evaluation framework in Algorithm I: how we compute summary topological descriptors for sets of graphs. This algorithm, taken from Bubenik [10], assumes list of precomputed persistence landscapes, one for each graph. Algorithm 2, on the other hand, outlines our procedure for generating distance between two sets of graphs using their summary topological descriptors.
Algorithm 1 Compute Average of Persistence Landscapes
Require: A is a list persistence landscapes
Ensure: A is the average persistence landscape
function
length of A
D < maximum homology degree occurring in A
< empty persistence landscape with D homology dimensions.
X* A*(k, t) 4- the piecewise-lines function encoding hom-deg & contained in A E A.
R maximal domain for each function contained in A.
< 0
while D do for & E R do
A(k; () - + (k,
end for
4 k + end while
return A end function
Recall that persistence landscapes are a collection of piecewise linear functions that encode the homological information tracked by a specified filtration. Thus, to compute the average landscape A each dimension, we simply sum the piecewise linear functions, and divide by the total number of landscapes in consideration. To understand our method for comparing sets of graphs, and thus evaluating graph generative models, based on average persistence landscapes see Algorithm
B Additional Proofs on Stability and Expressivity
B.1
Stability Proofs
Theorem 1. Given graphs F' = (Vp, Vrp.B EF) and G (Va, EG) with filtration functions f. g, and corresponding persistence diagrams Dj. Dy. have dD((D,, Dy) S max (f.isffff)))))))))))))))))) dis(g. f)), where dis(f.g) g) = Imax f(x) mingeEa g(y)l and vice versa for dis(g. f).
Proof. Considering the calculation of persistence diagrams based on scalar-valued filtrations func- tions, every point in the persistence diagram D, can be written as tuple of the form (f(er), f((r)) with e,, é'p Ey; the sample applies for Dy- The inner distance between such tuples that occur in the bottleneck distance calculation can thus be written as
(((())) - (o(ea).g(ea))))
(6)
The maximum distance that can be achieved using this expression determined by the maximum variation of the functions, expressed via dis(f, (f, g) and dis(g. f), respectively.
Edge Filtrations versus Vertex Filtrations Our results are structured to address filtrations built by function on the edges graph G EV, f: E + IR. This matches our notions of discrete curvature, which are also defined edge-wise. f gives an explicit ordering on E and thus an induced ordering on given by:
v U
Σ f(e) < Σ f(e') E
e' e'E
16

---

Algorithm 2 Computing Distance between Two Sets of Graphs
Require: Gi is a set of graphs.
Require: G2 is a set of graphs.
Require: D to be the maximum homology degree to be computed.
Require: f is function to generate filtration for persistent homology computations.
Ensure: Dist is the distance between 91.92.
function COMPUTESETDISTANCEEI
A1 + is an empty list.
A2 is empty list.
DistVec ec t- an empty D 1-dimensional vector.
for G 91 do
< Conppuceeesistencclaaaaaaaaa
AddItem((1 L.)
end for
for G G2 do
L - -CCoppppeersssccclaaalaneeeee f) AddItem(A2, L)
end for
A1
Compuue-veeageLLandseppp//a ConputeAvergeLLLndsspp////
A2 +
b By Algorithm 1.
while k < D do DistV DistVec(k] +- (supNorm((A supNorm((22k;
end while
Dist f |DDisteell2
return Dist
end function
function COMPTTERRRITTENNCLAANSSSSTEEE
P compute persistence diagram for G using f for homology degree 1: (0.... D). f transform P into persistence landscape.
> See [10] for implementation.
return L end function
where Eg is the set of edges incident to V. However, one can also define a filtration directly over vertices with scalar valued function h: V - R. By assumption, h can attain only finite number of values call the unique values b, b2,...b, by- Thus, we can also compute a filtration / C Go G1 ... C G C G+ G, where each G; (V, E,), with V; = {o E V M(o) s be) and E, = {e E max,ge h(v) I b.). Similarly, the explicit ordering on given by induces an ordering on E:
e + max h()) < max maxh(t') DEe
E'
The key idea here is that either choice gives rise to an ordering of both edges, and vertices that are used calculate persistent homology of the graph. This means that the arguments for Theorem and Theorem 5 also bound the bottle-neck distance for persistence diagrams generated using vertex filtrations.
Graph perturbations. Here we explicitly specify a common framework used in the proofs for sta- bility of curvature functions. As mentioned in the main text, we consider perturbations unweighted, connected graphs G = (V, E), with [V| n and [E| m. In the case of edge addition, let i* and j* be arbitrary vertices that we wish to connect with a new edge, forming our new graph G' = (V, E') where E' E U (i*, j+) such that EE| m - 1. For edge deletion, we similarly let (i+, E E be the edge we delete such that E' C and EE" m Moreover, we only consider edges ji*, that leave G' connected.

---

B.1.1 Forman-Roe Ricci Curvature
Theorem 2. Gf is the graph generated by edge addition, then the updated Forman curvature Kip for pre-existing edges (i,3) E E can be bounded by KFR(i,j) - S (i, S KFR(i,j) + If G' is the graph generated by edge deletion, then the updated Forman curvature for pre-existing edges (i,j) E can be bounded by Rypli. -2 (rr(i. - Kfn(i. +1.
Proof. We first handle the case of edge addition, using the graph perturbation framework specified above. By definition KFR (i,j) depends only on the degrees of the source and target (i,j) E and the number of triangles formed using (i,j), # Ary of neighbouring nodes for i, j respectively. This is a local computation- all relevant information can be computed in the subgraph surrounding the inserted edge (ix, j+*. Thus, in order to understand stability of (i, we need to understand how ((i) and N (j) change under graph perturbations. For our graph G', the only edges with potential to change their curvature lie in the set:
[N) NG)), where [(). _N( are the set
E. == [(u, v) Elu,UE ((i))
For the new edge j+* E E., we can directly compute KFR (i*, based on the original structure of the graph. However, in terms of stability we are interested in the other members of E., i.. edges in the original graph. The analysis of E_ can be split into two cases: one of the nodes is is or j* or neither is.
Case 1: WLOG assume (1,5) (i*,j) E.. Clearly, d; = d. + 1. As for | this can maximally increased by the case that j* N()), else the triangle count stays the same.
I.
Case 2: Let (i E E, where i,j E V. j*) In this case, there is no change to the degree nor the number HH'....-
Thus Case / defines the bounds which are dictated as follows: if (i+, j+) forms a new triangle, our curvature can increase by 2, and no triangle is formed the curvature can decrease by in response to the increased degree. Thus we can bound KiR (1, = 4 d' d' + 3 A'y as follows:
KFR - 1 S F (i.j) S KIR (FR(i,) (i,j) ))- +
The case of edge deletion can be handled similarly. Again, we need only consider the edges in E., defined in the proof above, and can make the same case argument.
Case 1 WLOG assume (i,5) = (i+ E E., Clearly, de = d, As for W'',, this can maximally be decreased by 1.
Case 2: Let (i,j)= E E. where i,j E V j++, Degree and number of triangles do not change in response to the perturbation.
Again, Case / gives rise to the following bounds hold for MER:
(i)(i.)) - S ( S kin(i,) +1
B.1.2 Ollivier-Ricei Curvature
The definition of KOR establishes a relationship between the graph metric dG. the Wasserstein distance W1. the probability distributions μa: Hy at nodes i.j and the curvature. Given that we are considering unweighted, and connected graphs we know that (V, dg) is a well-defined metric space and therefore W, (as defined in [55]) defines the L1 transportation distance between two probability measures ps; My with respect to the metric de: This relevant for a much larger class of graph metries than just the standard choice of the shortest path distance. We use results from [55] and the metric properties of W1 and dG on graphs to bound the potential changes in FOR following an edge perturbation.
Lemma 1. Consider the triple G (G,dG; p).. Let d, denote the Dirac measure at node i and J(i) == W1 (6c, pi) the corresponding jump probability in the graph G. The Seivier-Ricel curvature
18

---

K) satisfies the following Bonnet-Myers inspired upper bound: KOR (i.( J(i) + J(j)
dc(i.j)
Proof. Rearranging the original definition for OR curvature gives:
Wi(Hs, = do(t,))(1 - KOR (o)(),))
By definition of the Wi, we have (i,j) = (ō,, 6,), Using this and the fact that W1 satisfies the triangle inequality property, we can construct the desired upper bound on KOR:
da(i, (W, (4) + Wi (1 14)) - (1( 14))
da(i,j) <J(() + dc(i,)) FOR +
dc(1,))(1 (1 KOR (1, j))) SJ(1) SJ(1++ +J))
FOR(1,)) 5 J(i) J(1
do(i,j)
Theorem 3.
Given perturbation (either edge addition or edge deletion) producing g', the Ollivier- Ricci curvature kloR(1, () of a pair (i, can be bounded via
do (i. (W max + (Ps.)))) S (1.) J'(1) +
1
(4)
do (i.5)
where (v( (6,; pl,) refers to the new jump probabilities and W max maxzev W (Mas (la)) denotes the maximal reaction to the perturbation (measured using the updated Wasserstein distance).
Proof. We first prove the upper bound. Given that G' is still connected (by assumption). and both Wi and de still satisfy the metric axioms, this result follows directly from Lemma 1. For proving the lower bound, recall from Section 3.1 that G = (G', do',x') specifies the behaviour of the new graph metric de and the and the updated probability measure pí in response to the perturbation. Moreover, this defines new Wasserstein distance Wi and we will show that the maximum reaction (as evaluated by W/) to the perturbation W == max.ev W (1' (z)) can be used to express general lower bound for OR curvature in the event of a perturbation. As per Eq. (2), we can define our curvature following the perturbation as:
1
FOR (i,j)=1--
W (1(1l
(8)
(i,j)
Once again, make of the metric properties of Wi, to establish the lower bound as
KOR 21 1
(i, WWi (4) + Wilmy + Wi(us
2 1
(2 max + (i(,
do (i.
B.1.3 Resistance Curvature
brief clarification on inverting edge weights. The common practice when computing effective resistance is to invert the edge weights of a graph in order to get resistance. Given the spirit of resistance from circuit theory, we know that high resistance should make it difficult for current to pass between nodes. Analogously when thinking about our graph as a markov chain, this would correspond to a low transition probability. So, we think about our edge weights as coming from some kemee where higher similarity results in higher edge weight, then we should definitely invert our edge weights to get to resistance. However, in the case that our edge weights represent the cost of travelling between nodes, then this is a suitable proxy for resistance in which case inverting the nodes is unnecessary. order to achieve the theoretical properties of curvature with well known examples described in [19], we do not invert the edge weights in our experiments. Which means
19

---

that the curvature itself interprets the edge weights themselves as cost/resistance; we think it is an important point specify especially given the similarity markov chains and the borrowed terminology from circuit theory.
Definitions. The resistance distance, intuitively, measures how well connected two nodes are in graph. It is defined in [19] as:
Rig = (e; e -e,)
Here Q is the normalized laplacian (weighted degrees on the diagonal, see [19]), Q" the Moore- Penrose inverse, and e; is tth unit vector. This the main feature that will be studied to understand the stability of the curvature measure, and can be computed for any two nodes in a connected component of graph.
Recalling the equations for node resistance curvature and resistance curvature, i.c. Eq. (3), it becomes clear that the main task is to understand how the resistance distance changes in response pertur- bations. The results below from [46], are crucial for our proofs. Let C(i, j) be the commute time between nodes j E V. It is important to note that these results depend the normalized Laplacian, defined in [46] as N Då AD with eigenvalues A, ordered such that
λ2 2 .... Here, D is the diagonal matrix with inverse degrees and A the adjancecy matrix. Also, as is consistent with the rest of the paper, assume our graph has nodes and m edges, and d, is the degree node E V.
Proposition 1. For graph G, let N = D' AD be the normalized Laplacian with eigen values A 2 A2 2- ... 2 An. Then, the commute time in G between nodes i. is subject to the following bounds:
21 C(i.)) 1- 1 d, di
2m - 1
ml de di Proposition 2. Consider the unweighted graph G. where each edge represents a unit resistance, ie consider each edge in the graph to be artificially weighted with value 1. Then the following equality holds for the commute time between nodes i.
(10)
C(i,j) = 2mBus
(11)
Proposition 3. If arises from a graph G by adding a new edge, then the commute time (i, between any nodes in G' is bounded by:
s -)..)))) m
(12)
For proofs of these propositions, we refer the reader to [46]. These results create a direct connection between commute times and resistance distance, and gives insight into how commute time reacts under edge addition, and we use them directly to generate our bounds for resistance curvature. Theorem 4. If G' is the graph generated by edge addition, then K'R 2 Kg. with the following bound:
(n((i.)) - kx(2, Anda (d4 + dj)
(5)
Rij Aadd
where Andd jav (R., 1 ب ()
Proof. Let R3 be the resistance distance in G". Likewise, let C(i,j) be the commute distance in G between nodes j and (iiij) be the commute time in G'. Then Eq. (11) and Eq. (12) ensure that Ri is bounded above, by the original resistance distance in G:
1 2 Riy
2(m + 1)R2, 2mm1 + R2 Rij
m
This follows our intuition of resistance distance very well: with the addition of an edge nodes can only get more connected. Eq. (10) also gives nice lower bound:
1
(m + 1)(
s C' ('(i..)
d'
d
1
S R'y
d'
d
20

---

In the case that we are adding a single edge, it is often the case that node degrees remain constant. However, the nodes that are connected by the new edge. (i*. E' E, increase such that d', dı. +1 and d',,, = dj. + 1. Thus, the following lower bound holds in general for Rig and we can remain agnostic the precise location the new edge:
d, d S Rij S Rij
(13)
2 d. +1
And likewise, after adding p edges:
$ R S Rij
2 d. +
dj +
So the bounds of perturbed resistance distance R2 are determined by the initial network structure (Riy) and the number connections each specific vertex has. Naturally, certain node pairs will be more strongly affected by the addition of an edge. We can define the maximum reaction to perturbation across pairs as follows:
/ 1 d.
dj )
Add == max Rij jeE
(14)
2
+1
This can be used to bound node resistance curvature. In an unweighted graph, we have
p: =
Rij jui
p = 1 Σ R
For G and G' respectively. Given that resistance can only increase, pi is clearly an lower bound for pt. Certainly an upper bound occurs when when the resistance between each one of i's neighbors maximally decreases. Thus we get the following inequality:
de 2
P: S r4 S D:
Andd
(15)
Finally this gives the desired bound on káz=
Anda(d; + dz) Ríj Dadd
KR (i.j. S (i,j)) S kR().) +
Theorem 7. If G' is the graph generated by edge deletion, then K'g S Kg. bounded by:
[K)(),)) - kg(i.5)l Rij + Adel
1
2
(2Rgg + Ade)(ps + +P)) - Adei(d, + dz))
Rig
where Adel = 1-x0 min (Ris) and xa is the second largest eigenvalue of N.
Proof. Now we can beg the question of how effective resistance changes when we remove an edge. By inverting our initial argument in above proof of Theorem 4, we know that after removing an edge our resistance distance can only increase. Formally. Rı₃ S Rly. For the upper bound, we can once again make an argument using Eq. (10), this time relying on the other half of the inequality. Here we need to also mention the normalized Laplacian N' for G", with eigenvalues X Xg 2 X,-
21

---

(iii,) < 2(m - 1) 1
d3 + d
1 N/2
1
Rij 1- X/2
Again, we know that only the two unique vertices (i*, that shared an edge will have affected degrees, s.t d', de+ 1 and d' dj. Moreover, from Guo et al. [28], know that X2 X/- So can loosely bound the R as follows:
2 1 X2
Raj S Rig
(16)
In fact, this applies to any number of edge deletions, as long as G' stays connected. Again, we can define a maximum possible change in resistance distance across the graph:
2 - R2y) 1- A2
del
max -jEV
min (Ray)
(17)
A2
WeV
This leads to the following bounds on node and edge curvature, and completes the proof:
di pe Darl S p1 S Pi
Adet (d: + dj)] I (i.)) .) S kR(i,))
+ Dj (2 + Apt)((p + pp) - Ada + dj)] s (i. S (R(i,))
(1 -
>2) (1->2)
2
KR (i(
Raj Adel Rij
B.2 Expressivity Proofs
Theorem 5. Given two graphs F EV) and G (Vg, EE) with scalar-valued filtra- tion functions f.g, and their respective persistence diagrams Dy, Dy. we have inf Ep SuPzEEr lf(x) - g(n(z))), where 1j ranges over all maps from Ep to EG.
2
Proof. Considering the calculation of persistence diagrams based scalar- scalar-valued filtrations func- tions, every point in the persistence diagram D can be written as tuple of the form f((r), with ey, é' Ey; the sample applies for Dy- The inner distance between such tuples that occur in the bottleneck distance calculation can thus be written as
((((e)). - (a(ea)
(18)
which we can rewrite maxc: Ep Eo {f(x) g(C(x)) for general map C induced by the bijection of the bottleneck distance. Not every map is induced by bijection, though. Hence, if we maximise over arbitrary maps between the edge sets, we are guaranteed to never exceed the bottleneck distance.
C Additional Proofs for Distinguishing Strongly-Regular Graphs
Theorem 6 (Expressivity of curvature notions). Both Forman Ricci curvature and Resistance curvature cannot distinguish distance-regular graphs with the intersection array, whereas Ollivier-Ricci curvature can distinguish the Rook and Shrikhande graphs, which are strongly-regula graphs with the same intersection array.
Proof. We first show the part of the statement relating to the Forman-Ricct curvature. Given distance-regular graph G with N vertices and intersection array (bo. bi,... .. bn- 11:01 C2..... Cp) Let i be adjacent nodes in G. For regular graph, we have d: d, bo. where by is constant.
22

---

The number of triangles between two adjacent nodes and j in G is given by a1 = bo - b1 [18].
The Forman curvature of j.j is thus
KFR j) : 260 3/60 bj c1l-
(19)
Given two strongly-regular graphs with the same intersection array, i.e. the same values of bn. by and (1, the Forman curvature yields the same value for all pairs of adjacent nodes and cannot distinguish them. For the resistance curvature, the claim follows an immediate Corollary of Theorem A [6] and described in Koolen et al. [41]. Given the resistance between two nodes depends only on the intersection array and the number of nodes in the graph, then the resistance curvature cannot distinguish two strongly-regular graphs.
The expressivity of Selivier-RRcce curvature is strictly better, and it turns out that there are graphs with the same intersection array that we can distinguish, namely the Rook graph and the Shrikhande graph. Both graphs have the same intersection array {6, 3; 1, 2 but differ in their first hop peripheral subgraphs [22]. It is known that 2-WL cannot distinguish these graphs. Ollivier-Ricii curvature, however, is sensitive these differences in peripheral subgraphs with the edge curvatures for the Rook graph being: [0.2, 0.2, 0.33, 0.33, 0.33, 0.2, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.2, 0.2, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.2, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33, 0.33]. and for the Shrikhande graph they 0,2,,,,,,,
are 0, 0.27, 0.27, 0.1, 0.27,, 0,,,,, 0.1.0.27.0... 0.27, 0.17, 0.17, 0.17, 0.17, 0.17, 0.1,,
O, 0.1, 0.27, 0.7. 0.1, 0.17, 0.17,0017 0.17, 0.17, 0.17,
0.17, 0.17, 0.17], demonstrating that OR curvature can distinguish these graphs unlike Resistance curvature, Forman-Ro Ricci curvature and the 2- 2-WLtes test.
D Additional Stability Analysis
Given the bounds on curvature established in Section 3.1, we explore how curvature changes ex- perimentally by analysing edge perturbations Erdös-Rényí graphs. In particular, provide statistics that quantify the maximal change in curvature for random graphs with varying connectivity parameters in response edge additions and deletions. The experiment fixes the number of nodes in the ER graphs (n 100), and generates a sample of 50 graphs for the selected values of p. For each graph in the sample, we measure the curvature of all edges and calculate the standard deviation or of this distribution. We then perturb the original graph by edge addition/deletion and calculate the new curvature x'. The following tables present the worst case deviations in curvature, which we define as Ax = Ι - n/), in units of σxi in other words the maximal value of Ak/o 0, over all sample graphs and their edges.
Edge Addition: Maximal Change (4) in Curvature for ER Graphs (Ax/ar) (xx)) p=0.1
Curvature
p=0.2
p=0.3
p=0.4
p=0.5
p=0.6
p=0.7
p=0.8
p=0.9
KFR
0.582
0.419
0.334
0.296
0.253
0.246
0.232
0.25
0.315
KOR
1.545
1.157
0.613
0.465
0.396
0.366
0.368
0.399
0.512
AR
0.689
0.417
0.296
0.251
0.221
0.232
0.227
0.243
0.321
Edge Deletion:
Maximal Change
(L) in Curvature for ER Graphs (An/ow.)
Curvature
p=0.1
p=0.2
p=0.3
p=0.4
p=0.5
p=0.6
p=0.7
p=0.8
p=0.9
0.609
0.408
0.334
0.291
0.255
0.239
0.245
0.243
0.319
NOR
1.397
1.27
0.623
0.479
0.394
0.365
0.347
0.402
0.482
Kg
0.75
0.431
0.336
0.248
0.229
0.218
0.225
0.242
0.312
E Additional Commentary on Counting Substructures
We find that the difference in perspective between the selected curvature notions is underscored by their respective performance when counting substructures. Forman curvature an inherently local measure by definition, depending only on 3-cycles between adjacent nodes and their degrees. Ollivier- Ricci curvature, when used with a uniform measure, can bound the number of triangles within locally finite graph [37] through its relation with the Watts-Strogatz clustering coefficient [67]. It
23

---

can also be shown that quadrangles and pentagons influence the OR curvature, further enhancing the expressivity of this type of curvature [37].
This is the most global perspective one can achieve using FOR with uniform prohability measures, since polygons with more than five edges do not impact the curvature valuation.
However, by changing the probability measure used by KOR, we can shift the focus towards even larger substructures. For example, the rath power of the transition matrix provides information on the number of rt-atts and can therefore provide substructure information for cycles of size n [43]. Resistance curvature, by contrast, is biased towards the largest substructures. Due to the 'global' nature the resistance distance metric, Eg assigns cycles of size 2 a positive curvature. Moreover, in locally finite graph, one cannot use Kg establish non-trivial bound on the number of triangles (consider creating an infinite cycle between two nodes).
F Probability Measure for Ollivier-Ricei Curvature and Counting Substructures
The Ollivier Relivier-Ricci curvature is of particular interest because of its flexibility. While the predominant probability measure j used by the community uniform for each node, i.e. each of the node's neighbours is chosen with probability being proportional to the degree of the node. We experimented with different probability measures, one being based on expanding l to the two-hop neighbourhood of vertex, the other one being based on random walk probabilities. Specifically, for node x and positive integer m, we calculate Haw as
Poww (v)
Σ (x,
(20)
kSm
with (1, u) denoting the probability of reaching node in a k-step random walk that starts from node æ. Subsequently, we normalise Eq. (20) ensure that is a valid probability distribution. In our experiments, we set m = 2. meaning that at most 2-step random walks will be considered. As shown in the main paper, this formulation leads an increase in expressivity, and we expect that further exploration of the probability measures will be fruitful direction for the future.
We now explore what extent the ability of the curvature to count substructures can also be improved in this way. To do this, we used powers of the transition matrix as the probability measure, as it has been shown that the nihh power provides information provide substructure information for cycles of size n [43]. We find that powers of the transition matrix larger than 1 can perform better for counting the substructures, particularly for substructures larger than 3-cycles. There is also difference between Regular and Erdōs-Rény. (ER) graphs as the best transition power tends be higher for ER graphs. We hypthosise that this may have something to do with the mixing time of the graph, as large powers should converge to the stationary distribution, and regular graphs are more "expander-lide like'. The best results are obtained by taking multiple landscapes using the transition matrix powers (up to n = 5) and then averaging them. We show that combined with a single layer MIP, this method can perform better than using Graph Neural Network based approaches and OR curvature with the uniform measure.
the number of r-paths and therefore
Counting Substructures (MAE !)
Method
Trianglc
Tailed Tri.
Star
4-Cycle
GCN
0.4186
0.3248
0.1798
0.2822
NoR Filtration
0.2321
0,2395
0.3393
0.3089
Filtration with transition matrix powers
0.1956
0.2095
0.3212
0,2680
Optimal Transition Power
Method
ER
Regular
Triangle
1
Tailed Triangle
4
3
Star
4
2
Chordal Cycle
2
2
4-Cycle
8
3
24

---

Table 5: Computation time in seconds for discrete curvature on varying Erdös Erdós-Rényi graph sizes
with = 0.3.
Number of Nodes
EiR
FOR
FR
10
0.000
0.002
0.020
50
0.001
0.038
0.700
100
0.005
0.247
6.610
250
0.054
4.720
252.850
500
0,380
59.270
6414.970
1000
2.920
1040.700
74 366.070
Table 6: Computation time for different numbers of Erdös-Rééní graphs reference set (n 10
and p 0.3) with different distribution distance measures
Number of Graphs
Degree + MMD
Orbit + MMD
Curvature + MMD
Curvature Landscapes
20
3.6
mm8
217.0
ms
4.2
ms
12.5
ims
50
10.9
mss
459.0
mss
12.4
ms
20.9
In
100
34.1
ms
887.0
37.9
34.4
200
120.0
1960.0
133.0
80.4
500
678.0
ms 6740.0
ms
727.0
ms
144.0
ms
1000
2620.0
ms
19 99000.0
Iss
2680.0
ms
359.0
ms
G Computational Complexity
Persistence diagrams of 1-dimensional simplicial complexes, i.c. graphs, be computed in Om m) time where m denotes the number of edges. Empirically, when calculating differ- curvature measures for different sizes of graphs, find that Forman curvature scales well to large graphs, whereas OR and resistance curvatures can be used for smaller graphs and in cases that require more expressive measure. Note that there significantly faster ways to calculate resis- tance curvature as an approximation [65]. A majority of works on GGMs focus on small molecule generation, where any of these curvatures be used with minimal pre-computation. Table 5 depicts the computational complexity of various curvature calculations on Frdös-Rényi graphs whilst Table and Table 7 compares the complexity methods based MMD. We find that calculating persistence diagrams, turning these to persistence landscapes, averaging these and then calculating a distance takes a similar amount of time compared MMD for different sizes of graphs and for different numbers of graphs in the reference set. Interestingly, our approach scales better than MMD as both the number of graphs in the reference set increases and when the size of the graphs increases. This will be important for comparing distributions of large data sets such as the commonly used Zinc dataset or QM9, Overall, we find that our method can be easily applied in practical use cases, especially given that models for graph generation tyically generate graphs with well under 1000 nodes.
Table 7: Computation time for a fixed number of Erdös-Rény graphs in a reference set with different
sizes (p 0.3) with different distribution distance measures
Number of Graphs
Curvature + MMD
Curvature + Landscapes
10
2.3
9.0
ms8
20
4.5
ms
12.5
ms
50
15.8
ms
20.9
ms
100
93.6
ms
34.4
ms
200
556.0
80.4
500
727.0
ms
144.0
ms
1000
2800.0
364.0
25

---

H
Ethical Concerns
We have proposed general framework for comparing graph distributions focusing primarily on method and theoretical development rather than on potential applications. We currently view drug discovery as being one of the main application areas, where further experiments may be required, but we have no evidence that our method enhances biases or causes harm in any way.
26


Reviews:
[{"review_id": "CDow7lBPAM", "reviewer": "Reviewer_juxy", "summary": "This paper proposed a TDA-based graph generation model evaluation method using the discrete Ricci curvature of the graph as a filtration function. The proposed comparison between the two graphs is theoretically shown to have good properties for graph analysis, and the comparison is verified in experiments.", "questions": "Please answer the Weakness question above.", "limitations": "The authors do not explicitly address Limitation. On the other hand, the study is oriented toward reducing the social impact on the limitations of conventional methods and does not promote adverse effects.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "A new way (distance) of comparing  two graphs from a new perspective is proposed, and it is theoretically shown that the properties required for graph comparison are satisfied.", "weaknesses": "- The main concern is the consistency between the issues in the paper and the proposed methodology and validation. Although the issue of the paper is supposed to be a method for evaluating graph generation models, the proposed method is about a measure of the distance between two graphs. The two are related, of course, but there is insufficient mention of comparison methods between graph-generating models and comparison with other comparison methods. If the issue is the importance of defining good distances, the paper should be constructed as such, and if the issue is the evaluation of graph generation models, there should be a full discussion of that.\n\n- In any case, the key to the proposed method is the definition of the distance between two graphs, but most of the comparisons are in the Ricci curvature and TDA domains only, and the distance and similarity between graphs in other domains are not discussed. The following are representative of the distances and similarities between graphs. It is unnatural in light of the scope of NeurIPS that these are not mentioned.\n\t- Graph edit distance\n\t- Y. Bai et. al, SimGNN: A Neural Network Approach to Fast Graph Similarity Computation, WSDM '19\n\t\n- This is a non-essential question (with little impact on the evaluation), but why do you use Landscape for comparisons between persisntent diagrams? Many have been proposed such as Wesserstein distance, but is there a reason why Landscape is the best? Or is this an issue for future study?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking time in their review and providing valuable feedback. We have tried to address the weaknesses that you have highlighted. We believe most of the comments arise from the confusion between traditional distances between *graphs* and a distance between *distributions of graphs* (the main novelty of our work). We will better articulate this difference in the revised version of our paper. \n\n> Although the issue of the paper is supposed to be a method for evaluating graph generation models, the proposed method is about a measure of the distance between two graphs.\n\nWe apologise for this misunderstanding: in the paper, we are in fact proposing a distance between *distributions* of graphs, which enables us to evaluate graph generation models, where there is a reference set of graphs and a generated set. You are right in pointing out that there is a connection to distances between *individual* graphs. We use an example of distinguishing pairs of graphs in our work in order to show the **expressivity** of our measure (and to relate to the vaster literature on graph comparison) but we actually generate a distance between two sets of graphs (in this case, only one graph per set). This is in contrast to graph kernels and the graph edit distance which can not measure a distance between graph distributions. **We will rewrite this in a revision and clarify this point.**\n\n> There is insufficient mention of comparison methods between graph-generating models and comparison with other comparison methods\n\nCurrent comparison methods for evaluating graph generation use descriptor functions (degree, Laplacian, clustering coefficient) with MMD and we have conducted experiments to show that our approach is more stable (experiment 4.2), is better at distinguishing graph datasets and thus more expressive (experiment 4.5), and scales better (appendix F). We have also highlighted other weaknesses of previous methods such as not being robust to parameter choices, an issue alleviated by our method. **We will highlight these aspects in a revision; please let us know if there are other specific comparisons you would like us to conduct.**\n\n> [...] The key to the proposed method is the definition of the distance between two graphs, but most of the comparisons are in the Ricci curvature and TDA domains only, and the distance and similarity between graphs in other domains are not discussed.\n\nAs mentioned above, the distance we describe is not just a distance *between graphs* but a distance between two **distributions of graphs**. The choice of Ricci curvature combined with TDA is specifically done to allow this comparison between two sets of graphs and not just between two graphs (which cannot be used to evaluate graph generation). **We will discuss methods for computing distances between graphs as related work in a revision of the paper.**\n\n> This is a non-essential question (with little impact on the evaluation), but why do you use Landscape for comparisons between persistent diagrams? Many have been proposed such as Wesserstein distance, but is there a reason why Landscape is the best? Or is this an issue for future study?\n\nWe selected persistence Landscapes because of their favorable theoretical and empirical properties. Persistent Landscapes allow us to calculate distances between two *distributions* of graphs and not just between two graphs. This is due to the fact that, unlike Wasserstein distances, persistence landscapes allow us to do distributional analysis (whereas if working with persistence diagrams, their [means are non-unique and hard to calculate](https://arxiv.org/abs/1206.2790)). This means we can get average topological descriptors for all graphs in a distribution and then get a distance to the average of another distribution. There are indeed other functional summaries that could be used and we could also use a deep learning-based evaluation. **Thanks for raising this point; we will discuss these ideas in the revision and consider them for future work.**\n\nThanks for your assessment, please let us know about any other questions you might have! Should you be satisfied with our responses to your concerns, we would be grateful if you considered raising your score accordingly."}, {"review_id": "l5YksD9bi0", "reviewer": "Reviewer_4GUL", "summary": "The paper proposes a new set of graph features: first, 3 variants of graph curvature are calculated. Second, persistence landscapes are calculated over edge-based filtrations via curvature. Third, sets of graphs are compared via comparing their landscapes.\nTheoretical properties of landscapes (stability, expressivity) are studied. Experiments for both synthetic and real graph sets are provided.", "questions": "1. I am surprised that you have no experiments with a real graph generative model, instead you only compare manually prepared sets of graphs. The manuscript will benefit from such experiments. \n2. I don't understand why you don't use MMD in Section 4.5, you can calculate pairwise kernels for two sets of persistence landscapes.\n3. What is the dimension of persistence homology you calculate? How do you aggregate landscapes for different dimensions ?\n4. Is your approach is sensitive to outliers (outlier graphs in datasets) ?\n5. Why you have choosed edge-based filtration instead of node-based (like node degree)? Is it more expressive?", "limitations": "Authors adequately addressed the limitations and potential negative societal impact of their work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The research is original, afaik, since only few papers are dedicated to the developpement of new *measures* to evaluate graph generative models. However, the problem itself is an important one, having applications in molecular design.\nThe manuscript presents new theoretical results: stability w.r.t. changes in graph structure and expressivity of landscapes vs. raw filtrations (the results concern graph curvature). \nExperiments are quite diverse. \nThe paper is well written and easy to follow.", "weaknesses": "1. While the paper provides versatile approaches to comparison of graph datasets, the single end-to-end algorithm to evaluation of graph generative models and corresponding score is not formulated. I expected to find something like FID [1] for graphs. But in the end, you have a set of persistence landscapes, not one number. These landscapes should be aggregated somehow? \n2. No experiments with real graph generative models.\n\n[1] Heusel, M., Ramsauer, H., Unterthiner, T., Nessler, B., & Hochreiter, S. (2017). Gans trained by a two time-scale update rule converge to a local nash equilibrium. Advances in neural information processing systems, 30.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive assessment of our work! We are looking forward to clarifying any additional questions you might have!\n\n> While the paper provides versatile approaches to comparison of graph datasets, the single end-to-end algorithm to evaluate graph generative models and corresponding score is not formulated. I expected to find something like FID [1] for graphs. But in the end, you have a set of persistence landscapes, not one number. These landscapes should be aggregated somehow?\n\nWe aggregate the set of landscapes into an average landscape, and compare different averages via their $p$-norms (this is in fact one of the advantages of the persistence landscape formulation: it affords an easy-to-calculate mean). Similar to FID, our score is a difference between the representative landscapes for original and generated distributions of graphs, whose confidence can be evaluated by a $t$-test, for instance. **We will emphasise these aspects in a revision.**\n\n> I am surprised that you have no experiments with a real graph generative model, instead you only compare manually prepared sets of graphs. The manuscript will benefit from such experiments.\n\nThis is a great suggestion! For now, we chose not to compare outputs from real graph generative models due to the fact there is no ground truth in this case; the score between a given model’s generated and reference set doesn’t necessarily tell you how good that score is. We agree that the measure should be used to evaluate these models in the future but we first wanted to establish the new measure in a principled fashion and show how it overcomes the limitations of current approaches.\n\n> I don't understand why you don't use MMD in Section 4.5, you can calculate pairwise kernels for two sets of persistence landscapes.\n\nThanks for this suggestion! You are absolutely right to point out the existence of such kernels. However, due to the criticism of MMD outlined by [O’Bray et al.](https://openreview.net/forum?id=tBtoZYKd9n) (i.e. they find the final score is very sensitive to parameter choices and it has poor scalability), we chose to provide a method for the community which does not rely on it. Therefore, we have outlined a method that only requires defining the choice of curvature and has improved scalability. Nevertheless, our framework would potentially allow for replacing the distance calculations with a kernel. **We will emphasise this aspect in a revision.**\n\n> What is the dimension of persistence homology you calculate? How do you aggregate landscapes for different dimensions? \n\nFor now, we calculate $0$-dimensional and $1$-dimensional features (connected components and cycles) over the filtration, which can be computed efficiently using existing graph algorithms. However, our method also would permit higher-order topological features (at the expense of scalability). Our aggregation procedure then follows these steps:\n\n- We generate a landscape for each graph $G$, which can be decomposed into persistence landscape functions $\\lambda_{G,0}$ and $\\lambda_{G,1}$. These are _piecewise linear_ functions that encode the $0$- and $1$-dimensional persistent homology, respectively. \n-  We then aggregate the functions separately into average landscape functions $a_0 := \\lambda_{\\mathrm{avg}, 0}$ and $a_1 := \\lambda_{\\mathrm{avg}, 1}$ for the whole distribution. \n- Since persistence landscapes come equipped with ($p$-)norms, we use the supremum norm in our experiments. Our final summary of a distribution results in a two dimensional vector $V[\\|\\|a_0\\|\\|_\\infty, \\|\\|a_1\\|\\|_\\infty]$.\n- Finally, to compare the two distributions, we compare the Euclidean distance between these vectors.\n\n**We will highlight this calculation better in a revision.**\n\n> Is your approach is sensitive to outliers (outlier graphs in datasets) ?\n\nThanks for raising this point! We believe that, due to the properties of persistence landscapes, we can do statistical testing on a distribution of graphs to detect outliers in the distributional sense (since such outlier graphs would result in a highly different set of topological descriptors).  Moreover, our ability to detect outliers is underscored by the expressivity of the curvature filtrations. **We will highlight this aspect better in the revision of the paper, potentially also making a connection to the [stability theorem(s)](https://arxiv.org/abs/2006.16824) in persistent homology, which provides conditions under which persistence diagrams (and, subsequently, also persistence landscapes) remain stable.**\n\n> Why you have chosen edge-based filtration instead of node-based (like node degree)? Is it more expressive?\n\nWe choose to do an edge-based filtration over a node-based filtration, due to the fact that curvature is naturally defined over edges. If we were to make it node-based (e.g. mean of curvature of incoming edges) then indeed we would lose some information and be less expressive; preliminary experiments on strongly-regular graphs appear to be in support of this hypothesis. **We will add a brief discussion about this point.**\n\nAgain, thank you for your feedback on our manuscript. If you have any additional questions, please let us know! Should you be satisfied with our responses to your queries, we would be grateful if you considered reflecting this in your score."}, {"review_id": "dHBrPLBVtn", "reviewer": "Reviewer_YxdW", "summary": "In this manuscript, the authors proposed a special curvature-related graph descriptors for the evaluation of graph generative model. The key idea is to evaluate the discrete curvatures on graphs and construct a curvature-based filtration process. The corresponding persistent Landscape based metric is used for the evaluation of graphs. This metric is robust, stable, and expressive. ", "questions": "1)The construction of curvature-based TDA model is unique. However, its advantages are not clear. Once we have a graph, there are various way to define filtration parameters (or functions), what is the advantage of using curvature as the filtration parameter? Further, persistent curvature models have been developed and used in various molecular classification and property prediction. The authors are suggested to add some discussions and comparisons.\n\nJunJie Wee and Kelin Xia, \"Forman persistent Ricci curvature (FPRC) based machine learning models for protein–ligand binding affinity prediction.\" Briefings In Bioinformatics, 22 (6), bbab136 (2021)\n\nJunJie Wee and Kelin Xia, \"Ollivier persistent Ricci curvature-based machine learning for protein-ligand binding affinity prediction.\" Journal of Chemical Information and Modeling, 61 (4), 1617-1626 (2021)\n\n2) The filtration process is kind of weird. Note that positive Forman/Olivier Ricci curvatures are usually associated with certain community or cluster regions, while negative Ricci curvature are associated with the link or bridge regions. A filtration process from the largest Ricci curvature to smallest curvature will tend to reveal these cluster-type of information and seems to be more reasonable. But in this paper, the authors use the opposite way of going from the smallest to largest. Can the authors add some more discussions and explanations?\n\n3) In the sublevel set filtration, the final simplicial complex is just the original graph. In this way, all Betti_1 cycles will never been killed. That is all Betti_1 death values are infinity and no important death information will be obtained for Betti_1. However, if the authors use a general filtration process to generate simplicial complexes (with dimension 2 or above), 2-simplexes can be generated and Betti_1 bars can provide more information. Can the authors add some more discussions and explanations or comparison?\n\n4)There are many different vectorization models for TDA. Why the authors choose to use persistent landscape? What is the advantage of persistent landscape for this model?\n\n5) Forman-Ricci curvature is a combinatorial model designed for cell complexes. It is slightly “unfair” to directly compare its performance on graph with Ollivier Ricci curvature, which is designed for graphs. It may be better to add some more explanations about the background of Forman-Ricci curvature to avoid the confusion from readers not from this area!  \n", "limitations": "More discussions and explanations are needed to fully demonstrate the advantage of their model. ", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "A unique curvature-based TDA model is developed and used for the first time for the evaluation of graph generative model. The developed curvature-based metric is robust, stable, and expressive. ", "weaknesses": "The advantage to use curvature as filtration parameter is not clear. The advantage of the special filtration process and final vectorization approach is not clear. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks for the positive assessment of our work! We will include the suggested citations and are very happy to provide additional clarifications!\n\n> The advantage to use curvature as a filtration parameter is not clear. The advantage of the special filtration process and final vectorization approach is not clear.\n\nWe summarize main points; see long response below:\n\n1. We use curvature because it provides us with advantageous stability and expressivity properties (Sections 3.1 and 3.2).\n2. Moreover, curvature turns out to be a characteristic property of many geometric graphs such as molecules (we are very grateful for the additional literature you mentioned, which also serves to underscore exactly this point!)\n3. Finally, the vectorization process of persistence landscapes provides us with unique averages that are (a) easy to compute, and (b) permit us to compare distributions of graphs, while benefiting from the overall stability guarantees of TDA.\n\n> The construction of curvature-based TDA model is unique. However, its advantages are not clear. Once we have a graph, there are various ways to define filtration parameters (or functions), what is the advantage of using curvature as the filtration parameter? \n\n**Thanks for highlighting the unique aspect of our method**! We observe two advantages of curvature-based TDA:\n\n- _Stability_: Thm 1 implies that the stability of our evaluation method depends on the stability of the filtration functions we choose. We understand curvature’s stability with respect to graph perturbations and show bounds in Thms 2,3,4. This shows that our method is robust to perturbing distributions of graphs (i.e., bounded perturbations of graphs lead to bounded perturbation of curvature, which leads to bounded perturbation on landscape, which ultimately leads to a bounded perturbation on the average landscape).\n\n- _Expressivity_: Curvature itself is an expressive graph descriptor, which we motivate by analyzing its ability to distinguish strongly regular graphs and count substructures. To develop a stable/practical method for evaluating GGMs we want to use the most expressive graph descriptors that remain computationally viable.\n\n**Although other filtrations can be used in our framework, we are arguing that the combination of curvature’s expressivity, stability, and computability makes it the best choice for evaluating GGMs. We will emphasise this aspect in a revision.**\n\n>  Further, persistent curvature models have been developed and used in various molecular classification and property prediction. [...]\n\nThanks so much for these suggestions! We apologize for missing these relevant references for using curvature in the _classification_ of geometric graphs. **We will include them and discuss them as related work.**\n\n> The filtration process is kind of weird. Note that positive Forman/Olivier Ricci curvatures are usually associated with certain community or cluster regions, while negative Ricci curvature are associated with the link or bridge regions.[...] But in this paper, the authors use the opposite way of going from the smallest to largest. Can the authors add some more discussions and explanations.\n\nThat's a great point, thanks for raising it! Our framework works for both filtration directions, and we initially wanted to capture cycles 'earlier' (i.e. for smaller values of curvature). The reviewer's suggestion is great, and we will **highlight the possibility of a different filtration direction**, though our preliminary experiments do not indicate it makes a difference.\n\n> [...] In this way, all Betti_1 cycles will never been killed. That is all Betti_1 death values are infinity and no important death information will be obtained for Betti_1. However, if the authors use a general filtration process to generate simplicial complexes (with dimension 2 or above), 2-simplexes can be generated and Betti_1 bars can provide more information. [...]\n\nThanks for this suggestion! It is possible to move to higher-dimensional simplices, but we may lose the efficiency of computing PH using graph algorithms. What we could do to address this problem is consider [extended persistence](https://link.springer.com/article/10.1007/s10208-008-9027-z), which we would like to explore in a future work. When including 2-simplices and re-running the classification experiments between strongly-regular graphs, we find that the numbers in Table 1 changes as follows:\n\n| Model | sr16622 | sr261034 | sr281264 | sr401224 |\n| --- | --- | --- | --- | --- |\n| Without $2$-simplices   | 1.00     | 0.89     | 1.00    | 0.93       |\n| With $2$-simplices          | 1.0           | 0.98           | 1.0           | 0.94            |\n\nOur framework supports higher-dimensional information, but given the computational considerations, **we will add a note in a revision of the paper.** Thanks for the suggestion!\n\n> [...] What is the advantage of persistent landscape for this model?\n\nWe find that lifting the calculation to a Banach space has useful properties, such as providing us with unique averages and ways of performing statistical testing. Moreover, persistence landscapes can be calculated quickly and afford efficient distance calculations. **We will emphasize these points more in our revision.**\n\n> Forman-Ricci curvature is a combinatorial model designed for cell complexes. [...] It may be better to add some more explanations about the background of Forman-Ricci curvature to avoid confusion from readers not from this area.\n\nThanks for the suggestion! Forman-Ricci curvature seems to be rather know in ML, e.g. in the context of graph neural networks. **We will discuss more related work on [Forman--Ricci curvature](https://openreview.net/forum?id=7UmjRGzp-A) in a revision.**\n\nAgain, thank you for your feedback on our manuscript. If you have any additional questions, please let us know! Should you be satisfied with our responses to your queries, we would be grateful if you considered reflecting this in your score."}]

Author rebuttal:

Meta-review: The paper addresses a significant, albeit frequently neglected, issue regarding the quantification of dissimilarity between graph distributions. It introduces an innovative approach to assess graph generative models using discrete curvature and topological data analysis. The method's foundation in theory is robust, and I believe it has the potential to stimulate interest in other domains relevant to the conference's audience. Despite an initial dispute between a reviewer and the authors, a comprehensive conversation ultimately clarified the matter. The disagreement appeared to stem primarily from misconceptions related to certain associated concepts, and it was successfully resolved.
Decision: Accept (poster)