EMP: Effective Multidimensional Persistence for Graph Representation Learning
Authors: Ignacio Segovia-Dominguez
Baris Coskunuzer
Cuneyt Gurcan Akcora
Yuzhou Chen
Zhiwei Zhen
Murat Kantarcioglu
Yulia Gel
Venue: Submitted to ICLR 2023 (2023)
Keywords: multiparameter persistence
topological data analysis
machine learning

Abstract: Topological data analysis (TDA) has become increasingly popular in a broad range of machine learning tasks, ranging from anomaly detection and manifold learning to graph classification.
Persistent homology being the key approach in TDA provides a unique topological fingerprint of the data by assessing the evolution of various hidden patterns in the data as we vary a scale parameter. Current PH tools are limited to analyze the data by filtering with single parameter while in many applications, several relevant parameters are equally important to get a much finer information on the data. In this paper, we overcome this problem by introducing Effective Multidimensional Persistence (EMP) framework which enables to investigate the data by varying multiple scale parameters simultaneously. EMP framework provides a highly expressive summary of the data by integrating the multiple descriptor functions to the process successfully. EMP naturally adapts to many known single PH summaries and convert them into multidimensional summaries, for example, EMP Landscapes, EMP Silhouettes, EMP Images, and EMP Surfaces. These summaries deliver a multidimensional fingerprint of the data as matrices and arrays which are suitable for various machine learning models. 
We apply EMP framework in graph classification tasks and observe that EMP boosts the performances of various single PH descriptors, and outperforms the most state-of-the-art methods on benchmark datasets. We further derive theoretical guarantees of the proposed EMP summary and prove the stability properties.

Under review as a conference paper at ICLR 2023
EMP: EFFECTIVE MULTIDIMENSIONAL PERSISTENCE FOR GRAPH REPRESENTATION LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Topological data analysis (TDA) has become increasingly popular in broad range of machine learning tasks, ranging from anomaly detection and manifold learning to graph classification. Persistent homology being the key approach in TDA provides a unique topological fingerprint of the data by assessing the evolution of various hidden patterns in the data as we vary a scale parameter. Current PH tools are limited to analyze the data by filtering with single parameter while in many applications, several relevant parameters are equally important to get much finer information on the data. In this paper, we overcome this problem by introducing Effective Multidimensional Persistence (EMP) framework which enables investigate the data by varying multiple scale parameters simultaneously. EMP framework provides a highly expressive summary of the data by integrating the multiple descriptor functions the process successfully. EMP naturally adapts to many known single PH summaries and converts them into multidimensional summaries, for example, EMP Landscapes, EMP Silhouettes, EMP Images, and EMP Surfaces. These summaries deliver a multidimensional fingerprint of the data as matrices and arrays which are suitable for various machine learning models. We apply EMP framework in graph classification tasks and observe that EMP boosts the performances of various single PH descriptors, and outperforms the most mate-of--hhe-ar methods on benchmark datasets. We further derive theoretical guarantees of the proposed EMP summary and prove the stability properties.
INTRODUCTION
In the past decade, topological data analysis (TDA) proved to be powerful machinery to discover many hidden patterns various forms of data which are otherwise inaccessible with more traditional methods. In particular, for graph machine learning tasks, while many traditional methods fail, TDA and. specifically, tools of persistent homology (PH), have demonstrated high potential to detect local and global patterns and to produce unique topological fingerprint to be used in various machine learning tasks. This makes PH particularly attractive for capturing various characteristies of the complex data which may play the key role behind the learning task performance.
In turn, multiparameter persistence, or multipersistence (MP) is novel idea to further advance the PH machinery by analysing the data in much finer way simultancously along multiple dimensions. However, because of the technical problems related to commutative algebra because of its multidi- mensional structure, it has not been defined for general settings yet (See Section 2.1.. In this paper, we develop an alternative approach to utilize multipersistence idea very efficiently for various types of data, with main focus graph representation. In particular, MP by obtaining very practical summaries by utilizing slicing idea in structured way. In turn, we obtain suitable multidimensional topological fingerprints of the data matrices and arrays where ML models can easily detect the hidden patterns developed in the complex data.
bypass technical issues with the
Our contributions can be summarized as follows:
We develop new computationally efficient and highly expressive EMP framework which provides multidimensional topological fingerprints of the data. EMP expands many pop- ular summaries of single persistence multidimensions by adapting an effective slicing

---

Under review as a conference paper at ICLR 2023
direction. As such, our EMP framework provides a practical way to utilize the promising multipersistence approach in real-life applications.
We illustrate the utility of EMP summarics in various settings and compare results to state-of-the-an methods. Our numerical experiments demonstrate that EMP summaries outperforms SOTA in several benchmark datasets for graph classification tasks.
We derive theoretical stability guarantees of the new topological summaries.
RELATED WORK
2.1
MULTIPARAMETER PERSISTENCE
Persistent homology (PH), being a key tool in topological data analysis (TDA), delivers invaluable and complementary information the intrinsic properties of data that are inaccessible with conventional methods (Chazal & Michel 202I Hensel et al., (021). In the past decade, PH has become quite popular in various ML tasks, ranging from manifold learning to medical image analysis, material science to finance (TDA applications library (Giunti] 2022)). One of the key benefits of PH is that allows us extract the evolution of subtler patterns in the data shape dynamics multiple resolution scales which are not accessible with more conventional, non-topological methods [Wasserman 2018).
Multipersistence (MP) is a highly promising approach to significantly improve the success of single parameter persistence (SP) in applied topological data analysis, but there are some issues to convert this novel idea into an effective feature extraction method as desired (See Appendix (D3)). Except for some special cases, MP theory suffers from the problem of the nonexistence of barcode decomposition because of the partially ordered structure of the index set {(a;, 3,)) (Botnan & Lesnick (022). Lesnick & Wright (2015) suggested to bypass this issue via slicing technique by studying one- dimensional fibers of the multiparameter domain where one restricts the multidimensional persistence module to single direction (slice) and to single persistence on this one dimensional slice. Later, by using this novel idea, Carrière & Blumberg (2020) combined several slicing directions (vineyards) and obtained vectorization by summarizing the persistence diagrams (PDs) in these directions. There are several promising recent studies in this direction (Botnan et al. 2021 Vipond 2020), but these approaches are not computationally feasible, and cannot provide the expected effectiveness of MP approach in real life applications. Here we develop a highly efficient way to use MP approach for various forms of data, and provide a multidimensional topological vectorization with EMP summaries.
2.2 GRAPH REPRESENTATION LEARNING
After the success of convolutional neural networks (CNN) image-based tasks, graph neural networks (GNNs) have emerged as a powerful tool for graph-level classification and representation learning. A wide variety of models developed based on numerous theories (see Appendix A for further details). However, to our best knowledge, most of existing approaches do not account for the important topological information on the shapes of the node neighborhoods. While GNNs produce great performances in many graph learning tasks, they tend to suffer from over-smoothing problems and are vulnerable to graph perturbations. To address these challenges, TDA provides computationally efficient alternative to GNNs, and can be used as an effective feature extractor to be combined with the deep learning methods Hoter et al. (2220); [Bodnar al. (2022): Horn al. (2021). Recently, this direction has been explored in many works, and single persistent homology give highly competitive results with kernel-based methods Togninalli et al.) (2019): RReck
(Ricck et al. (2019);
Le & Yamada (2018), 8); Zhao & Wang (2019): Kyriakis et al. (202l) and neural networks Hofer et al. (2019); Carrière al. (2020) graph classification tasks. In this work, we apply MP approach for the first time in this setting, and our EMP model outperforms most deep learning models in benchmark datasets.
BACKGROUND
We start from providing the basic background for our framework. Since we mainly focus on graph representation learning in this paper, explain construction graph setting. Note that
2

---

Under review as a conference paper at ICLR 2023
our techniques can easily be adapted to other types of data, e.g., point clouds and images (See Appendix D.I.
3.1 PERSISTENT HOMOLOGY
Persistent Homology (PH) is a mathematical machinery to capture the hidden shape patterns in the data by using algebraic topology tools. PH extracts this information by keeping track of evolution of the topological features (components, loops, cavities) created in the data while looking at it in different resolutions Dey & Wang (2022). Appendix B provides additional background on classic PH for the avid reader.
For given graph 9, consider nested sequence of subgraphs 91 ....
S...9. GN G. For each
gs define an abstract simplicial complex G. 1 S i S N. yielding a filtration of complexes G. S
S CỘv. Here, clique complexes are among the most common ones, i.c., a clique complex ç is obtained by assigning (filling with) a k-simplex to each complete (k + 1)-complete subgraph in G. e.g., 3-clique, a complete 3-subgraph, in 9 will be filled with a 2-simplex (triangle). Then, in this sequence of simplicial complexes, one can systematically keep track of the evolution of topological patterns mentioned above. A k-dimensional topological feature (or k-hole) may represent connected components (0-hole), loops (I-hole) and cavities (2-hole). For each k-hole o, PH records its first appeareance in the filtration sequence, say gr., and first disappearence in later complexes, Ga, with a unique pair (b,, do), where 1 S by < do S N. We call b, the hirth time of a and dz the death time of a. We call dg by the life span of a. PH records all these birth and death times of the topological features in persistence diagrams (PD). Let 0 S k S D where D is the highest dimension in the simplicial complex GN. Then the kth persistence diagram PDx( {(b,, E H (G.) for by S < do}. Here, (9,)) represents the 1thh homology group of G, which keeps the information of the k-holes in the simplicial complex G. For sake of notation, we skip the dimension (subscript k). With the intuition that the topological features with long life span (persistent features) describe the hidden shape patterns in the data, these PDs provide a unique topological fingerprint of G.
As one can easily notice, the most important step in the PH machinery is the construction of the nested sequence of subgraphs G1 S ... S GN G. For given unweighted graph g = (V, E) with V- = {ui..... u.r } the set of nodes and & c {(r, e E V x V, # j} the set of edges, the most common technique is to use a filtration function f V - with a choice of thresholds
I {a;} where
min f(v) < 022 < < ON = max.ev f(v). For Og E I. let V. = {Ur E VVI f(x, S a.). Let G. be the induced subgraph of G by V,, i.e., G, = (V,, E.) where E, {ers E Ur, U. V.j. This process yields nested sequence of subgraphs GI G2 C... C
GN = G. called the sublevel filtration induced by the filtration function f. We denote PDs obtained via sublevel filtration for filtration function f as PD(G, f). The choice of f is crucial here, and in most cases, f is either an important function from the domain of the data, e.g., atomic number in protein or a function defined from intrinsic properties of the graph, e.g., degree and betweenness. Similarly, for a weighted graph, one can use sublevel filtration on the weights of the edges and obtain suitable filtration reflecting the domain information stored in the edge weights. (For further details on different filtrations see Aktas et al. (2019); Hofer et al. (2020).)
3.2 SINGLE PERSISTENCE VECTORIZATIONS
While PH extracts hidden shape patterns from data as persistence diagrams (PD), PDs being col- lection of points in 2 by itself are not very practical for statistical and machine learning purposes. Instead, the common techniques are by faithfully representing PDs as kernels Kriege et al. (2020) or vectorizations Hensel et al. (202T). This provides a practical way to use the outputs of PH in real life applications. Single Persistence Vectorizations transform obtained PH information (PDs) into a function or a feature vector form which are much more suitable for machine learning tools than PDs. Common single persistence (SP) vectorization methods are Persistence Images Adams al. 2017). Persistence Landscapes Bubenik (015), Silhouettes Chazal et al. (0014). and various Persistence Curves Chung & Lawson| (2019). These vectorizations defines single variable or multivariable functions out of PDs, which can be used as fixed size 1D or 2D vectors in applications, i. x n vectors m x n vectors. For example, Betti curve for PD with n thresholds can also be expressed
3

---

Under review as a conference paper at ICLR 2023
as 1 X size vectors. Similarly, Persistence Images is an example of 2D vectors with the chosen resolution (grid) size. See the examples given in Section 4.2 for further details.
3.3 MULTIDIMENSIONAL PERSISTENCE
MultiPersistence (MP) is novel idea to significantly boost the performance of the single parameter persistence technique described above. The reason for the term "single" is that we are filtering the data in only one direction G1 fine analysis of the data to find the hidden patterns. If one uses one function ʃ V + IR which has very valuable domain information (c.g.. amount for blockchain networks, atomic number for protein networks), then this induces a single parameter filtration as above. However, various data have more than one very natural domain functions to analyze the data, and using them simultaneously would give much better understanding of the hidden patterns. With this intuition, multiparameter persistence (MP) theory is suggested as natural generalization of single persistence (SP).
GN G. The construction of the filtration is the key get
In simple terms, if one uses only one filtration function, sublevel sets induces a single parameter filtration G1 C... C GN- G. Instead, if one uses two more functions, then it would give way to study the data in much finer resolution. For example, if we have two functions f -- R and g: - IR with very valuable complementary information of the network, MP idea is presumed to produce a unique topological fingerprint combining the information from both functions. These pair of functions f.g induces multivariate filtration function F V R22 with F(u) = (f(v), g(v)). Again, one can define a set of nondecreasing thresholds {a:] and 13 for f and g respectively. Then, Vij = for E V f(r,)= S 0s, ((v)) S 831, i.e., ViJ = F--((((-)) ((-00, o:s] x (-o0, (3)) Then, let Giy be the induced subgraph of G by Vaj. i.e., the smallest subgraph of g generated by Vij- Then, instead of a single filtration of complexes, we get a bifiltration complexes {θ., 1isis
m, 1 S j S n.. One can imagine {
rectangular grid of size 1 1 i0 S m, }/= gives a nested (horizontal) sequence of simplicial complexes. Similarly, for each 1 S jo S {9roo )m gives nested (vertical) sequence of simplicial complexes (See Figure in the Appendix).
such that for each
By computing the homology groups of these complexes, {Hs (Gg)). we obtain the induced bigraded persistence module rectangular grid of size m n)). Again, the idea to keep track of the k-dimensional topological features via the homology groups { (Ha)) in this grid. As explained in Appendix D.3] because of the technical issues related to commutative algebra, there are still issues to define a mathematical output like "Multipersistence Diagram", and hence, to obtain an effective vectorization of the MP module (Section B). These technical issues prevent this promising approach to reach its full potential in real life applications.
In this paper, we overeome this problem by producing very practical vectorizations by utilizing slicing idea in the multipersistence grid in a structured way. The key point in our approach that we produce multidimensional vectors (matrices and arrays) unique topological multidimensional fingerprints of the data. In other words, by using MP approach, we extract multidimensional features of the data same size matrices and arrays which are quite suitable for various machine learning models, and we can facilitate the appropriate ML method to analyze these unique fingerprints and detect the patterns developing in these multi-resolution view of the data.
4 EFFECTIVE MULTIDIMENSIONAL PERSISTENCE SUMMARIES
We now introduce our Effective MultiPersistence (EMP) framework which describes way to expand most single persistence vectorizations (Section 3.2) as multidimensional vectorizations by utilizing MP approach. In particular, by using the existing single parameter persistence vectorizations, we produce multidimennional vectorization by effectively using the one of the filtering direction as "slicing direction" in the multipersistence module.
4.1 EMP FRAMEWORK
In simple terms, for d = 2, for a given two filtration functions f.g. the main idea is to use first filtration function get single parameter filtering of the data, i.e., 91 C ... 9m = g. Then,
4

---

Under review as a conference paper at ICLR 2023
use the second function in each subgraph obtain persistence diagram PD 9) for 1 i m.
In particular, we obtain m persistence diagrams {PD(G,, 9)}; Then, by applying the chosen SP vectorization yp to each PD, obtain different same length vector ş (PD g)), say 1 x k vector. Then, by combining all m 1 1D-vectors, we obtain EMP vectorization Ms such that M = ((PD(G; g)) where M represents the jth row of Mp which is 2Dvvector (matrix) of size x k (See Figure 3 in Appendix). For > 2, the construction is similar and given below.
Here, we give the details for sublevel filtration for two filtration functions. In Appendix D.2 we explain how to modify the construction for weight filtrations or power filtrations. Let G = (V. be graph, and let f.g V + R be two filtration functions with threshold sets {a, Ji=1 and {3,}
respectively. Let Vi fu, E V f(u,) S az). Let GJ be the induced subgraph of g by V4. This gives a filtering of the graph (nested subgraphs) as 91 S ... S 9m = G. Recall that g - R is another filtration function for G. Now, we fix in m, and consider Gin- By restricting g on Gig, we get persistence diagram (D 9) as follows. Let Vioj ( E V., [(vr) S <33), and let Gind be the induced subgraph of Gio by Ving- This defines finer filtering of the graph Gip as 9 C 9 .... C
gign = Gip- Corresponding clique complexes defines a filtration g001 S 92.2... C 9in = P.o.
This filtration gives the persistence diagram P PD 9). Hence, for each 1 S i m, we obtain persistence diagram P PD(G,, 9).
The next step is to use the vectorization on these m persistence diagrams. Let y be a single persistence vectorization, e.g., Persistence Landscape, Silhouette, Entropy, Betti, Persistence Image. By applying the chosen SP vectorization y each PD, we obtain a function yo, = (p(PD(), g)) where in most cases it is a single variable function on the threshold domain [31, _.]. i.e. y : [31, 3m]] - R. For the multivariable case (e.g.. Persistence Image). we give explicit description in the examples section below. Most such vectorizations being induced from a discrete set of points PD(G). they naturally can be expressed as a 1 /) vector of length k: In the examples below, we explain this conversion in detail. Then, let 7 be the corresponding 1 x k vector for the function yi:. Now, we are ready to define our EMP summary M. which is a 2D-vcctor (a matrix)
M = 5 for 1 Isism.
where M is the 5th-row of Mp. Hence, Mp is 2D-vector of size m x k. Each row M is the vectorization of the persistence diagram PD(G,, g) via the SP vectorization method ip. We use the first filtration function f to get a finer look at the graph as G1 C... C 9m = G. Then, we use the second filtration function g to obtain the persistence diagrams PD(G,,g) g) of these finer pieces. In a way, we look at G with a two dimensional resolution {Gy and we keep track of the evolution of topological features in the induced bifiltration (G The main advantage of this technique that the outputs are fixed size matrices (or arrays) for each dataset which is highly suitable for various machine learning models.
Order of the Filtration Functions. We need note that for given two filtration functions g, the order is quite important for our algorithm. In particular, let (f. represent the above construction where we first apply f to get filtering {= and then we obtain m different PD g). Hence, (f. would be m x l matrix. On the other hand, if we apply first, we would get filtering {G' yiz Then, by using sublevel filtration with for each GO, we would get n persistence diagrams PD(G", f). Assuming the produced vectors و5 for [a1, am] domain has length k', then M. f) would give us n x k size matrices. In particular, in the first one M. g) we use "horizontal" slicing in the bipersistence module, while in the latter Mp f), we use "vertical" slicing.
For the question "Which function should be used first", the answer is that the function with more important domain information should be used second function (g in the original construction), as we get much finer information via persistence diagram P PD g) for the second function.
Higher Dimensional Multipersistence. Similarly, for d = 3, let f. f.g. h be filtration functions and let { be the bifiltering of the data, e.g., sublevel filtration for two functions f.g. Then, again by using the third function h, we find m n persistence diagrams (PD(G h) mi. 1 Similarly, for a given SP vectorization yp one obtains a D-vector ((PD(Gs,,g)) of size 1 x k for each i, This produces a 3D-vector (array) M. of size m X n x k where M = (DDD( g)). .. For > 3, one could follow similar route.
5

---

Under review as a conference paper at ICLR 2023
14
35
30
12 10
Brraton
15
10
60
62
03
23
28
20
Ritrston
FRrutie-2
Harator
Figure I: For the same network and the same filtration functions, EMP Betti Summary (left), EMP Silhouette (center), and EMP Entropy Summary (right) can produce highly different topological summaries emphasizing different information persistence diagrams.
4.2 EXAMPLES OF EMP SUMMARIES
Here, we discuss explicit constructions of EMP summaries for most common vectorizations. As noted above, the framework is very general and it can be applied to most SP vectorization methods. In all examples below, we use following setup: Let G = (V, E) graph, and let f.g be two filtration functions with threshold sets {a, = and (3, }ー= respectively. As explained above, we first apply sublevel filtering with ff to get a sequence Then, for each Gi apply sublevel filtration with g to get persistence diagram PD(G,, g). Therefore, we will have m PDs. In the examples below, for given SP vectorization we explain how to obtain vector ( g)). and define the corresponding EMP M.- Note that skip the homology dimension (subscript k for (G) in the discussion. In particular, for each dimension 0, l,... will have one EMP M ( matrix array) corresponding (#(PDD(G,, g))} The most common dimensions are k = and = in applications.
IR
nested subgraphs. G1 C... C 9m G.
EMP Landscapes. Persistence Landscapes À one of the most common SP vectorizations introduced by [Bubenik (0155). For given persistence diagram PD(G) = {(b,, d ). À produces a function X()) by using generating functions A, for each (b,, d.) PD(g), ie., A, : [b, d,] + R is piecewise linear function obtained by two line segments starting from (b,, 0) and (d,, 0) connecting to the same point ( b. thitd: b, bidd) Then, the Persistence Landscape function X(g) [e1, Cgl - IR for
t [c1, Cg] is defined
X()(()) max; A²(().
where { are thresholds for the filtration used.
Considering the piecewise linear structure of the function, X(G) is completely determined by its values at 2q- points, i.e., b.id, E {(i, 61., c2, c2.5..... (g} where = (c+ + cx+1//2. Hence, a vector size x (2g 1) whose entries the values of this function would suffice capture all information needed, i.c. À [A(e1) A(E1.5) A(E2) A(e2.5) A(ea) X(E,)]
Considering we have threshold set (,3 1 for the second filtration function g. X, X(PD(G,, 9)) will be vector of size x 2n 1. Then, as M X; for each < S m, EMP Landscape MX(G) would be 2D-vector (matrix) of size x (2n 1).
Silhouette Chazzll et al. (2014) is another very popular SP vectorizations method machine learning applications. The idea is similar Persistence Landscapes, but this vectorization uses the life span of the topological features more effectively. For PD(G) = {(b,, d let A; be the generating function for (bs, d,) as defined Landscapes above. Then, Silhouette function & defined as
EMP Silhouettes.
N (,
(G)
Em EE [E11
where the weight w, is mostly chosen the life span d; b, and (a))== represents the thresholds for the filtration used. Again such a Silhouette function (G) produces a 1D-vector (GG) of size 1 (2q (oq-1) 1) in Persistence Landscapes case. Similar the EMP Landscapes, with the threshold set

---

Under review as a conference paper at ICLR 2023
{3 for the second filtration function 9, 8/. (PD(( 9) will be vector of size x 2n 1. Then, as M = vi for each 1 S i S m, EMP Landscape Mg) would be again a 2D-vector (matrix) of size x (2n 1) (Figure I.
EMP Persistence Images. Next SP vectorization in our list is Persistence Images Adams et al. (2017). Different than the most SP vectorizations, Persistence Images produces 2D-vecoors. The idea is to capture the location of the points in the persistence diagrams with a multivariable function by using the 2D Gaussian functions centered these points. For PD(G) = { d.) J. let o; represent a 2D-Gaussian centered at the point (bi, d,) E IR2 Then, one defines a multivariable function, Persistence Surface, J4 = E w,o; where w, is the weight, mostly a function of the life span d, b;- To represent this multivariable function as Deveco,,, one defines a k x grid (resolution size) on the domain of pr. i.e., threshold domain of (g) Then, one obtains the Persistence Image, a -veecr (matrix) 17 = [Mrs] of size k x where Prs JA.. p(x,, y) dxdy and Ars is the corresponding pixel (rectangle) in the k x 1 grid.
This time, the resolution size k | is independent the number thresholds used in the filtering, the choice of k and / is completely up to the user. Recall that by applying the first function f. we have the nested subgraphs {- For each Gs, the persistence diagram PD 9) obtained by sublevel filtration with induces 2D vector fI, Tū( =T(PP(G...) g)) of size k x I. Then, define EMP Persistence Image as Mr = fi, where M is the 2thh -flor of the array M,. Hence, M2 would be 3Dveccoor (array) of size k x I where m is the number of thresholds for the first function and l: x 7 is the chosen resolution size for the Persistence Image J7.
EMP Surfaces and EMP Betti Summaries. Next, we give an important family of SP vectoriza- tions, Persistence Curves Chung & Lawson (2019). This is umbrella term for several different SP vectorizations, i.e Betti Curves, Life Entropy, Landscapes, et al. Our EMP framework naturally adapts to all Persistence Curves to produce multidimensional vectorizations. As Persistence Curves produce a single variable function in general. they all can be represented as 1D-vectors by choosing suitable mesh size depending the number of thresholds used. Here, we describe one of the most common Persistence Curves in detail, i.e., Betti Curves. It is straightforward to generalize the construction other Persistence Curves.
Betti curves are one of the simplest SP vectorization as it gives the count of topological feature given threshold interval. In particular, Bx (A) is the total count of k-dimensional topological feature in the simplicial complex A, i.e., 3x (A) = rank Ha (A)) (See Figure 2 in the Appendix). In particular, (9): [c1, Eq+1] + E is a step function defined as
(g) = rank H (G.))
for E [cs; 441), where { represents the thresholds for the filtration used. Considering this is step function where the function is constant for each interval [ei, 6++1) 1), it can be perfectly represented by vector of size g as B(G) [1) ((2) 8(3) ... B(g)].
Then, with the threshold set (3,) } for the second filtration function g. 3 100 ((PD( g)) will be
a vector of size x n. Then, as M 3 = B3 for each 1 < i S m. EMP Betti Summary Ma would be a 2D-vector (matrix) of size X (Figure [ In particular, each entry Mg- = |m,y] is just the Betti number of the corresponding clique complex in the bifiltration (G. ). i.e., mij = 3(,)) This
matrix M3 is also called bigraded Betti numbers in the literature, and computationally much faster
than other vectorizations Lesnick & Wright (202)).
4.3 STABILITY OF EMP SUMMARIES
We now show that when the source single parameter vectorization o is stable, then so is its induced EMP vectorization M9. (We give the details of stability notion in persistence theory and examples of stable SP vectorizations in Appendix C.I
Let g+ (0+ and g (V- E-) be two graphs. Let to be stable SP vectorization with the stability equation
((p( s C.. (PD(St)
7

---

Under review as a conference paper at ICLR 2023
for some S P3 cc. Here, (( represent the corresponding vectorizations for PD(G*) and Wp represents Wasserstein-p distance as defined in Appendix
Now, by taking d 2 for EMP construction, let f.g. V + R be two filtration functions with threshold sets {ar [m and {33]} respectively. Then, by defining V {u, V# f((,) S aa). their induced subgraphs {g,}} give the filtration G C G .... 9m as before. For each I i S m, we will have persistence diagram PD(G..)) g) as detailed in Section 4.1 We define the induced
matching distance between the multiple persistence diagrams as
Dy((PD(G)) ), (PD(C) )H
Σ WM(PD(G .9), PD(G,
(2)
Now, we define the distance between induced EMP Summaries as
D (MM,(C+).
Σ d(((())).
Theorem 4.1. Let up be stable SP vectorization. Then, the induced EMP Vectorization M. is also stable, i.e,, with the notation above, there exists C.p such that for any pair of graphs G+ and g we have the following inequality.
(. C.p Dp, (IPD(T))), (PD(G)))
The proof is given in Appendix C.2
EXPERIMENTS
5.1
DATASETS
To verify our EMP summaries on graph representation learning, we evaluate EMP summaries with random forest on nine widely used benchmark datasets, i.e., (i) three molecule graphs (Sutherland
et al. y003) BZR MD, COX2 MD, and DHFR MD: (ii) two biological graphs (Kriege & Mutzel 2012 Borgwardt et al. 2005): MUTAG and PROTEINS; and (iii) four social graphs: IMDB- LMMB--M), BEDDIT-Binary (REDDIT-B), and REDDIT-Multi-55 (REDDIT-M-5K). We also calculate (i) average node-level centrality measures: average degree centrality, average betweenness centrality, average closeness centrality, average clustering centrality, average eigenvector centrality, and average Katz centrality; and (ii) average edge-level centrality measures: average betweenness centrality, average Ricci curvature, and average Ricci positive curvature, and feed these node-/edge-leys
Binary (IMDB-B), B),
measures into random forest model. Furthermore, it is worth noting that COX2 MD and DHFR MD all have three node features, whereas PROTEINS has one node feature. We use all these available features as input to random forest model. Further details on the datasets and experimental setup are provided in Appendix E.
5.2 EXPERIMENTAL SETUP
We vectorize our proposed EMP representations and use random forest (RF) for the graph classifica- tion task. For RF, we set the number of trees in the forest as 1000, the minimum number of samples as 2. and the function to measure the split quality as Gini impurity. We apply filtrations based on the available information of each dataset, either using their graph structure or their provided node/edge features. Our pool of filtration functions include, but is not limited to: type of atom, closeness, edge-betweenness, weighted degree, katz centrality, ricci curvature, and distance between atoms. In this experiments, first we apply a sublevel filtration on nodes, and secondly a power filtration over edges. To test EMP framework and entropy summary functions, thus producing EMP matrix representations which can be embedded in classic and modern machine learning algorithms.
three vectorizations: Betti curves, silhouette functions,
We compare EMP summary with two types of state-of-the-ard baselines, covering six graph kernels, one graph neural networks, and one topological method. Graph kernels: (i) comprised of the
8

---

Under review as a conference paper at ICLR 2023
Table I: Classification accuracy % standard deviation) of EMP summary on nine benchmark datasets.
The best results are in bold font and the second best results are marked underlined.
Model
BZR_MD
COX2_MD
DHFR_MD
MUTAG
PROTEINS
IMDB-B
IMDB-M
REDDIT-B REDDIT-SK
CSM
77.63++1.29
OOT
OOT
87.29-1.25
O0T
OCT
O0T
OOT
OCT
HGK-SP
60.08+0.88
59.92=0.66
67.95=0.00
80.90=048
74.5340.35
73.34=0.47
51.58=0,42
OOM
OOM
HGK-WI
WI.
52.64++1.20
57.15+1.20
66.08+1.02
15.51-1.34
74.53+0.35
72.75+1.02
50.73-0063
0OM
OOM
MLG
51,46+0.61
51.15+0.00
67.95+0.00
78.53-2.25
75.55=40.7
52.56+0.42
34.27=0.33
0OM
OOM
WL
67.45+1.40 60.07=2.22
62.5621.51
85.75=1.96
73.06:0.47
71.15=0.47
50.25=0.72
77.95=0.60
51.63=0,37
WLOA
68.19:11.09
62.37:22.11
64.1011..7
86.10=1.95
73.50:10.87
74.0110.66
49.95:10.46
87.6011.33
OOM
GNNs
69.87-4-1229
66.05+3.16
73.1141.599
80.42-2.07
70.314-193
66.5342.33
48.93-0088
89.90+1990
=6.10-166
FC-V
75.61+1113
73.41=00779
76.78:+0.69
87.31=0.66
74,5440.48
73.84=0.36
06.30-0.37
89.41:0.24
52.36+0.37
EMP
77.77:00.5 70.48=1.38
80.50:1107
8..79=0.63
72.7840.54
75.34=0.29
48.75=0.22
91.03:10.22
54.4110.32
subgraph matching kernel (CSM) Kriege & Mutzel (0012). (ii) Shortest Path Hash Graph Kernel (HGK-SP) Morris et al. (2016). (iii) Weisfeiler-Lehman Hash Graph Kernel (HGK-WL) Morris
ct al. (006)). (iv) Multiscale Laplacian Graph Kernel (MLG) Kondor Pan (2016), (v) Weisfeiler-
Lehman (WL) Shervashidze et al. ( and (vi) Weisfeiler-Lehmant Optimal Assignment (WL-
OA) Kriege et al. (2016); graph neural networks: graph neural networks (GNN) Kipf & Welling (2017); topological method: filtration curves (FC-V) Bray et al. (202T). For all methods, report
the average accuracy of 10 runs of 10-fold CV along with standard deviation, and running time for computation of each EMP representation. The source code is freely available
5.3 EXPERIMENTAL RESULTS
Table shows the results of different methods on nine graph datasets. Out-of-time (OOT) results indicate that a method could not complete the classification task within 12 hours, and OOM means "out-of-memory (from an allocation of 128 GB RAM). We observe the following phenomena:
Compared with all baselines, out of 9 benchmark datasets, the proposed EMP summaries achieve the best performance on 5 datasets (BZR_MD DFHR __D, MUTAG, IMDB-B, REDDIT-B), and second best in datasets (COX2_M)) MD, REDDIT-5K).
EMP summary consistently outperforms Filtration Curves all datasets except COX2_ML and PROTEINS, indicating that multiparameter structure of the EMP summaries can better capture the complex structural properties and local topological information in heterogeneous graphs.
Moreover, EMP Summaries consistently delivers the competitive results with GNNs in all benchmark datasets. This indicates that EMP summary introduces powerful topological and geometric schemes for node features and graph representation learning.
To further investigate the effectiveness of the EMP vectorization function in graph representation learning, we have conducted ablation studies of various EMP summaries on the benchmark datasets, see Appendix G Furthermore, Appendix Fiinclues an analysis of computational complexity.
6 DISCUSSION
We have proposed a computationally efficient summary for multidimennional persistence for various forms of data, and include focus-cases on graph machine learning. The new Effective Multidimensional Persistence (EMP) framework provides a practical way to employ the promising multidimensional persistence idea in real-life applications. As such, EMP summaries are highly compatible with machine learning models and can boost the performances of popular single persistent summaries in unified manner. In graph classification task, EMP summaries outperform state-of-the art methods in several benchmark datasets. Furthermore, we have shown that EMP maintain important stability guarantees. Therefore, EMP makes important step toward bringing the theoretical concepts of multipersistence to the machine learning community and advances the use persistent homology
ht http://h///////ooooooocoooooo/on

---

Under review as a conference paper at ICLR 2023
in various settings. In future work, we aim enhance the EMP framework by using more than one slicing direction in the multipersistence grid and, thus, effectively combining the outputs multiple slicing directions with deep learning approaches.
10

---

Under review as a conference paper at ICLR 2023
REFERENCES
Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard. Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional ar- chitectures via sparsified neighborhood mixing. In International Conference on Machine Learning. 2019.
Sami Abu-El-Haija, Amol Kapoor, Bryan Perozzi, and Joonseok Lee. N-GCN; Multi-scale graph convolution for semi-supervised node classification. In Uncertainty Artificial Intelligence, pp. 841-851, 2020.
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, 2017.
Mehmet E Aktas, Esra Akbas, and Ahmed El Fatmaoui. Persistence homology of networks: methods and applications. Applied Network Science, 4(1):1-28, 2019.
Nieves Atienza, Rocío González-Díaz and Manuel entropy and new summary functions for topological data analysis. Pattern Recognition, 107: 107509, 2020.
On the stability of persistent
Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pietro Liò, and Michael M Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in gnns. arXiv preprint arXiv:2202.0457 2022.
Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-PPter Kriegel. Protein funetion prediction via graph kernels. Bioinformatics, 21(suppl_I) 1): i47-i56, 2005.
Magnus Bakke Botnan and Michael Lesnick. An introduction multiparameter persistence, arXiv preprint arXiv:2203. 11022223..4290 14289, 2022.
Magnus Bakke Botnan, Steffen Oppermann, and Steve Oudot. Signed barcodes for nulti-parameter persistence via rank decompositions and rank-exact resolutions. arXiv preprint 1xXiv2210700600 2021.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In ICLR, 2014.
Bubenik. Statistical topological data analysis using persistence landscapes. JMLR, 16(1):77-102, 2015.
Mathieu Carrière and Andrew Blumberg. Multiparameter persistence image for topological machine learning. Advances in Neural Information Processing Systems, 33, 2020.
Mathieu Carrèère, Frédéric Chazal, Yuichi Ike, Théo Lacombe, Martin Royer, and Yuhei Umeda. Perslay: A neural network layer for persistence diagrams and new graph topological signatures. In AISTATS, pp. 2786-2796, 2020.
Frédéric Chazal and Bertrand Michel. An introduction to topological data analysis: fundamental and practical aspects for data scientists. Frontiers in Artificial Intelligence, 4, 2021.
Frédéric Chazal, Brittany Terese Fasy, Fabrizio Lecci, Alessandro Rinaldo, and Larry Wasserman. Stochastic convergence of persistence landscapes and silhouettes. In Proceedings of the thirtieth annual symposium on Computational geometry, pp. 474 483, 2014.
Y. Chen, Y.R. Gel, and K. Avrachenkov. LFGCN; Levitating over graphs with levy flights. In IEEE ICDM, 2020.
Yu-Min Chung and Austin Lawson. Persistence curves: A canonical framework for summarizing persistence diagrams. arXiv preprint arXiv: 190.00094 2019.

---

Under review as a conference paper at ICLR 2023
M. Defferrard, X. Bresson, and P. Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. Advances in Neural Information Processing Systems, pp. 3844 -852, 2016.
Tamal Krishna Dey and Yusu Wang. University Press, 2022.
Computational Topology for Data Analysis.
Cambridge
Herbert Edelsbrunner and John Harer. Computational topology: an introduction. American Mathe- matical Soc., 2010.
Herbert Edelsbrunner and Salman Parsa. On the computational complexity of Betti numbers: reductions from matrix rank. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, pp. 152-160. SIAM, 2014.
geometry, David Eisenbud. Commutativv algebra: with a view toward geomerty, volume 150. Springer
Science & Business Media, 2013.
Barbara Giunti. Tda applications library, 2022.
httes://ww.ecteer..or///gggggg
2425412/tda- app-aappppppee http://taaappplaaataaaaaa SaapplicaaiinssII1111
Felix Hensel, Michael Moor, and Bastian Rieck. survey of topological machine learning methods. Frontiers in Artificial Intelligence, 4:52, 2021.
Christoph Hofer, Florian Graf, Bastian Rieck, Mare Niethammer, and Roland Kwitt. Graph filtration learning. In International Conference Machine Learning, pp. 4314 4323. PMLR, 2020.
Christoph D Hofer, Roland Kwitt, and Mare Niethammer. Learning representations of persistence barcodes. Journal of Machine Learning Research, 20( 20(126):1-45, 2019.
Max Horn, Edward De Brouwer, Michael Moor, Yves Moreau, Bastian Rieck, and Karsten Borgwardt. Topological graph neural networks. In International Conference on Learning Representations, 2021.
Megan Johnson and Jae-Hun Jung. Instability of the Betti sequence for persistent homology and stabilized version the Betti sequence. arXiv preprint woXiv:2109009/11 2021.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. ICLR, 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günneemnnn Predict then propagate: Graph neural networks meet personalized pagerank. In ICLR, 2019.
Risi Kondor and Horace Pan. The multiscale laplacian graph kernel. Advances in neural information processing systems, 29, 2016.
Nils Kriege and Petra Mutzel. Subgraph matching kernels for attributed graphs. In Proceedings of the 29th International Coference International Conference Machine Learning, pp. 291-298. 2012.
Nils M Kriege, Pierre-Louis Giscard, and Richard Wilson. On valid optimal assignment kernels and applications to graph classification. Advances in neural information processing systems, 29, 2016.
Nils M Kriege, Fredrik D Johansson, and Christopher Morris. A survey on graph kernlss. Applied Network Science, 5(1):1-42, 2020.
Panagiotis Kyriakis, Iordanis Fostiropoulos, and Paul Bogdan. Learning hyperbolic representations of topological features. In International Conference on Learning Representations, 2021.
Langley. Crafting papers on machine learning. In Pat Langley (ed.), International Conference on Machine Learning, pp. 1207-1216. Stanford, CA. 2000. Morgan Kaufmann.
Tam Le and Makoto Yamada. Persistence fisher kemnl: Riemannian manifold kernel for persistence diagrams. In Advances in Neural Information Processing Systems, pp. 10007-10018, 2018.
12

---

Under review as a conference paper at ICLR 2023
Michael Lesnick. The theory of the interleaving distance multidimensional persistence modules. Foundations of Computational Mathematics, 15(3):613-6) 650, 2015.
Michael Lesnick and Matthew Wright. Interactive visualization of 2-D persistence modules, arXiv preprint
2015.
Michael Lesnick and Matthew Wright. Computing minimal presentations and bigraded Betti numbers of 2-parameter persistent homology. SIAM Journal on Applied Algebra and Geometry, 6(2): 267-298, 2022.
Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. Proceedings of the 26th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, KDD '20, pp. 238-348, New York, NY, USA, 2020. Association for Computing Machinery. ISBN 9781450379984, doi: 10.11447/3394988333377. 3394 3403076
Federico Monti, Karl Otness, and Michael M Bronstein. MotifNet: a motif-based graph convolutional network for directed graphs. IEEE DSW, pp. 225-228, 2018.
Christopher Morris, Nils M Kriege, Kristian Kersting, and Petra Mutzel. Faster kernels for graphs with continuous attributes via hashing, In 2016 IEEE 16th International Conference on Data Mining (ICDM), pp. 1095-1100. IEEE, 2016.
Leslie O' O'Bray, Bastian Rieck, and Karsten Borgwardt. Filtration curves for graph representation. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pp- 1267-1275, 2021.
Nina Otter, Mason A Porter, Ulrike Tillmann, Peter Grindrod, and Heather A Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, 6:1-38, 2017.
Meng Qu, Yoshua Bengio, and Jian Tang. GMNN: Graph Markov Neural Networks.
arXiv:1905.06214. 2019.
Bastian Rieck, Christian Bock, and Karsten Borgwardt. A persistent weisfeiler-lehman procedure for graph classification. In International Conference on Machine Learning, pp. 5448-5458, 2019.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mchlhorn, and Karsten M Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9). 2011.
Jeffrey Sutherland, Lee O'brien, and Donald F Weaver. Spline-fitting with genetic algorithm: A method for developing classification structure-activity relationships. Journal of chemical information and computer sciences, 4306):19661115 2003.
Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borgwardt. Wasserstein weisfeiler-lehman graph kernels. In Advances in Neural Information Processing Systems, pp. 6439-6449, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. ICLR, 2018.
Oliver Vipond. Multiparameter persistence landscapes. Mach. Learn. Res., 21:61-1, 2020.
Larry Wasserman. Topological data analysis. Annual Review of Statistics and Its Application, 5: 501-532, 2018.
Yiding Yang. Xinchao Wang, Mingli Song, Junsong Yuan, and Dacheng Tao. Spagan: shortest path graph attention network. In International Joint Conference on Artificial Intelligence, pp. 4099-4105, 2019.
Qi Zhao and Yusu Wang. Learning metries for persistence-based summaries and applications for graph classification. In NeurlPS, pp. 0855-9866. 2019.
13

---

Under review as a conference paper at ICLR 2023
Appendix
A ADDITIONAL LITERATURE ON GRAPH REPRESENTATION LEARNING
After the success of convolutional neural networks (CNN) on image-based tasks, graph neural networks (GNNs) have emerged as a powerful tool for graph classification and representation learning. Based on the spectral graph theory, [Bruna et al. (2014) introduced graph-based convolution in Fourier domain. However, complexity of this model is very high since all Laplacian eigenvectors are needed. To tackle this problem, MeeeNNe(DDefeereee with Chebyshev polynomials. Then, Graph Convolutional Networks (GCNs) of Kiip' & Welling (2017) simplified the graph convolution with localized first-order approximation. More recently, there have been proposed various approaches based on accumulation of the graph information from wider neighborhood, using diffusion aggregation and random walks. Such higher-order methods include approximate personalized propagation of neural predictions (APPNP) Klicppra et al. (2019). higher-order graph convolutional architectures (MixHop) AAbu-El-Hajaa et al. (2019). multi-scal graph convolution (N-GCN) Abu-El-Haija et al. (2020), and Lévy Flights Graph Convolutional Networks (LFGCN) Chen et al. (2020). addition to random walks, other recent approaches include GNNs on directed graphs (MotifNet) Monti et al. (2018), graph convolutional networks with attention mechanism (GAT, SPAGAN) Veličković et al. (2018); Yang et al. (2019), and graph Markov neural network (GMNN) Qu et al. (2019). Most recently, Liu al. Liu et al. (2020) consider utilizing information on the node neighbors' features in GNN, proposing Deep Adaptive Graph Neural Network (DAGNN). However, DAGNN, and other state-of-the-an approaches, does not account for the important information on the shapes of the node neighborhoods.
et al. (2066) integrated spectral graph convolution
B FURTHER BACKGROUND ON SINGLE PERSISTENT HOMOLOGY
Here, we give further details single parameter persistent homology. To sum up. PH machinery is 3-step process. The first step is the filtration step, where one can integrate the domain information into the process. The second step is the persistence diagrams, where the machinery records the evolution of topological features (birth/death times) in the filtration sequence of the simplicial complexes. The final step is the vectorization (fingerprinting), where one can convert these records function or vector to be used in suitable ML models.
Constructing Filtrations: As PH is the machinery to keep track of the evolution of topological features in sequence, the most important step is inducing this nested sequence of simplicial complexes, Do C A C... C Am. This is the key step where one can inject valuable domain information into the PH process by using important domain functions. Two most common methods are Sublevel/superlevel filtration and Vietoris-Rips (VR) filtration We already described sublevel filtration in Section
VR filtration is another common method especially used for point clouds, where coarse geometry of the data set X play key role (Chazal & Michel 2021). Let X' = { .2,,..,, ..., IN be the given data set. For a given threshold 6, one forms a Vietoris-Rips complex A by adding a k-simplex to X for any subset {Zngs Ing ..., Tne where the pairwise distances are all d( Xn.) < c In particular, if a pair of points Ing Iny has distance < 6, then in the induced simplicial complex A, we add an edge enony between the corresponding vertices Wigg and Tny- If three such points Ing Tn,, Tn, have pairwise distances < e,, then we fill the triangle enon, U Engna U Engno with 2-simplex, and so on. For each e,, one obtains simplicial complex A; by using this procedure. Changing threshold values E < E2 <.... < em results in a hierarchical nested sequence of simplicial complexes A C A2 C... C Am that termed the Vietoris Rips filtration of the data set X. Note that VR filtration can also be considered as a sublevel filtration for the distance function to X' from the ambient space Idd, i.e., : Rd + R with f() = d(y, X) where X C Rdd
ii Persistence Diagrams: The second step in PH process is to obtain persistence diagrams (PD) for the filtration As C A₁ C .... C Am- As explained in Section 3.1 PDs are collection of 2-tuples, marking the birth and death times of the topological features appearing in the filtration, i.c. (D) = {bb, dz) a E (A,) for b, < < d Current algorithmic advancements make possible to efficiently compute persistence diagrams via modern software libraries (Otter et al.) 2017).
14

---

Under review as a conference paper at ICLR 2023
iii. Vectorizations: While PH extracts hidden shape patterns from data persistence diagrams (PD), PDs, a collection of points in I2 by itself, are not very practical for statistical and ML purposes. Instead, the common techniques are faithfully representing PDs as kernels (Kriege et al. 2020) or vectorizations (Hensel et al. 202T). One can consider this step as converting PDs into a useful format to be used in the MI. process fingerprints of the dataset. This provides a practical way the outputs of PH in real-life applications. Single Persistence Vectorizations transform obtained PH information (PDs) into a function or a feature vector form which is much more suitable for ML tools than PDs. Common single persistence (SP) vectorization methods are Persistence Images (Adams al., 2017), Persistence Landscapes (Bubenik) (201)), Silhouettes (Chazal et al. 2014), Betti Curves and various Persistence Curves (Chung & Lawson 2019). These vectorizations define a single variable or multivariable function out of PDs, which can be used as fixed-size 1D or 2D vectors in applications, i.e., 1 x π. vectors or x vectors. For example, Betti curve for a PD with thresholds can also be expressed as X n2 size vectors. Similarly, Persistence Images is an example of 2D vectors with the chosen resolution (grid) size. See the examples given in Section 4.2 for further details.
C STABILITY
C.I STABILITY OF SINGLE PERSISTENCE SUMMARIES
For a given PD vectorization, the stability is one of the most important properties for statistical purposes. Intuitively, stability question is whether a small perturbation in PD cause a big change in the vectorization or not. To make this question meaningful, one needs to define what "small" and "big" means in this context. Therefore, we need to define distance notion, i.c., metric in the space of persistence diagrams. The most common such metric called Wasserstein distance (or matching distance) which is defined as follows. Let PD(X+) and PD(X-) be persistence diagrams two datasets X and X' (We omit the dimensions in PDs). Let PD(X+) = {q } U A and P {प U A where A = represents the diagonal (representing trivial cycles) with infinite multiplicity. Here, 93 (63 .d)) E PD(X') represents the birth and death times of a hole oj in x Let Φ PD(x*) + PD(X represent bijection (matching). With the existence of the diagonal A in both sides, we make sure the existence of these bijections even if the cardinalities Hg H and H9; H are different. Then, the pth Wasserstein distance Wp defined as
-min Σ 11 (( E
W,((D(()),P((*>>)
P DEZ-
Then, vectorization (function) 4 (PD(2) is called stable if d(ppt, --) W,,(D(()))PP(()) ()) where g= (PD((x)))) and d(.,.) is a suitable metric on the space of vectorizations used. Here, the constant C > 0 is independent of = This stability inequality interprets as the changes in the vectorizations are bounded by the changes in PDs. Two nearby persistence diagrams are represented by nearby vectorizations. If given vectorization yo satisfies such a stability inequality for some d and Wp. we call y a stable vectorization Atienza et al. (2020). Persistence Landscapes Bubenik (2015), Persistence Images Adams et al. (2017). Stabilized Betti Curves Johnson & Jung (2021) and several Persistence curves Chung & Lawson (0019) are among well-known examples of stable vectorizations.
C.
C.2 PROOF OF THEBREM 4.1: STABILITY OF EMP SUMMARIES
Proof. As vp is stable SP vectorization, for any < i m. we have C₁ W,, (PD(Gt). PD(GT) for some C2p > by Equation [1. where Wp, is Wasserstein-p
s
15

---

Under review as a conference paper at ICLR 2023
distance. Notice that the constant Cp 0 independent of i. Hence,
(,
d(p(07).
S
Σ
Co Wp, (DCC)
i=1
Cp
Σ W (PD(S)) 1=1
=
where the first and last equalities are due to Equation (2) and Equation (3) while the inequality follows from Equation which true for any i. This concludes the proof of the theorem.
D EMP FRAMEWORK
D.1 EMP FOR OTHER TYPES OF DATA
So far, to keep the exposition simple, we described our construction in the graph setup. However, our framework suitable for various types of data. Let X be an image data or a point cloud. Let f X + IR and X - I be two filtration functions on X' For example, it can be grayscale function for image data, density function on point cloud data.
Let f X + I be the filtration function with threshold set far Let X4 = f- asl). Then, we get a filtering of X' as nested subspaces X1 C X₂ C ... C X'm = X. By using the second filtration function, we obtain finer filtrations for each subspace X; where 1 < i < m. In particular, fix S ig S m and let {3,) be the threshold set for the second filtration function Then, by restricting to Xig, we get filtration function Xio, i.e., Xi - R which produces filtering Xi,1 X202 ... Mign Xig. By inducing simplicial complex & for each Xasi. we get a filtration Ri,1 C Ri C... Rinm = & This filtration results a persistence diagram (PD) PD(X,, g). For each 1 15 siS m, obtain PD(X;, g). Note that after getting { via f. instead of using second filtration function g, one can apply power filtration or Vietoris-Rips construction based on distance for each X in order to get different filtration
Rio1 Ri C .... C Rig = X
By using PDs. we follow similar route to define our EMP summaries. Let be single persistence vectorization. By applying the chosen SP vectorization y to each PD, we obtain a function ;0, (((,,,,,))) g)) on the threshold domain Bx), which can be expresses 2D) vector most cases (Section 4.2p. Let G be the corresponding x l vector for the function po, Define the corresponding EMP M, e M f where M. is the th row of M2 In particular, M. is a 2evectr (a matrix) of size m x & where m is the number of thresholds for the first filtration function f, and & is the length of the vector
1D (or
D.2 EMP WITH OTHER FILTRATIONS
Weight filtration For given weighted graph G (V,E, W), common use edge weights W {wrs E R+ Crs E }} to describe filtration. By choosing the threshold set similarly = {a um with a1 = min (uys E W} < 022 < <... < am = max(w,, E W). For a; E I, let ε, (ers E V Wrs S a.). Let G be subgraph of G induced by V. This induces nested
sequence subgraphs G1 C G2 C ... C Gm = (See top row in Figure 2).
In the case of weighted graphs, (via f' with weight filtering. In particular, let g V + R be a filtration function with threshold set ) Then, apply to each G. to get bilfiltration {Gig) (m x resolution). One gets PDs as PD(G,, g) and induce the corresponding M.. Alternatively, one can change the order by applying first, and get different filtering 91 C G2 C Gn G induced by g. Then, apply to edge weight filtration
apply the EMP framework just by replacing the first filtering
first apply weight filtering get G1 C C G. G above, and then
16

---

Under review as a conference paper at ICLR 2023
degree
2
55,
30
-00
weight
Figure 2: Multidinensional persistence on a graph network (original graph: left). Black numbers denote the degree values of each node whilst red numbers show the edge weights of the network. Hence, shape properties are computed on two filtration functions (i.e., degree and edge weight). While each row filters by degree, each column filters the corresponding subgraph using its edge weights. For each cell, lower left corners represent the corresponding threshold values. For each cell, Bu and B, represent the corresponding Betti numbers.
to any Gj. one gets bifiltration ( (n m resolution) this time. As result, one gets n PDs as PD w) and induce the corresponding M.. The difference is that in the first case (first apply weights, then g), the filtration function plays more important role M. uses PD 9) while in the second case (first apply g. then apply weights) weights have more important role as M. is induced by w)) Note also that there a very different filtration method for weighted graphs by applying the following the following VR-complexes method.
Power (Vietoris-Rips) Filtration There is highly different filtration technique using distances between the data points the dataset. The technique is called power filtration for unweighted graphs/Aktas et al. (2019), while it is called Vietoris-Rips filtration for other types of dataaFdelssbunnn Harer 2010). The idea is for point cloud = {#1, Z2...., , .IN }. one uses the pairwise distances d(Tr F2a) to construct the simplicial complexes in the filtration. In particular, for a threshold set 61 < C2 < ... < 6n = diam(X),, one forms a Vietoris-Rip complex Aj by adding a k-simplex to X' for any subset {2rg TT, :.:..... ...., 2r }, where the pairwise distances are all < cj. If pair of points Tri Xra has distance < ej. then in the induced simplicial complex Aj. we add an edge between the corresponding vertices xy and xg. If three such points Ir, : Fr Try have pairwise distances < fj- then we fill the triangle eriz U errra Uran with a 2-simplex, and so on. This procedure induces in hicrarchical nested sequence of simplicial complexes A C Ag C ... C Am that is termed Vietoris-Rin Rips filtration induced by the point cloud X. For unweighted graphs, one takes the vertex set as the point cloud, and defines the distances d(v), U2) as the shortest distance in the graph where each edge has length 1. For weighted graphs, one can do the same by defining edge lengths induced by the weights.
One can adapt Vietoris-Rips filtrations to our EMP setting as follows. Start with filtration function f:X
X + with threshold set (a; ) and obtain X; C X2 C... C Xm = X' where X; = ((-oo, a:)). Then, apply Vietoris-Rin Rips filtration to each X. for threshold set {e,} which produces a filtration Ro C L2 C... .... C Prg where Roo5 is the Vietoris-Rips complex of X; for threshold Ej. Construct PD(X,, VR) of these filtrations for each 1 S S m. The following steps are same Section 4.2 For a given SP vectorization let 5i be the corresponding 1 x &o vector induced by yp (X,, VR) with domain [C1, G.). Then, define EMP M. as M', = 3 where M the th row of M, Again, M, is a vector (a matrix) of size m x l where m is the number of thresholds for the filtration function and l: is the length of the vector 5.
17

---

Under review as a conference paper at ICLR 2023
D.3 MULTIPARAMETER PERSISTENCE THEORY
Multipersistence theory is under intense research because of its promise to significantly improve the performance and robustness properties of single persistence theory. While single persistence theory obtains the topological fingerprint of single filtration, multidimensional filtration with more than one parameter should deliver a much finer summary of the data to be used with ML models. However, because of the technical issues in the theory, multipersistence has not reached to its potential yet and remains largely unexplored by the ML community. Here, we provide a short summary of these technical issues. For further details. Botnan & Lesnick (2022) gives nice outline of current state of the theory and major obstacles.
In single persistence, the threshold space {a;) being subset of R. is totally ordered, i.e., birth time < death time for any topological feature appearing in the filtration sequence {A:}. By using this property, it was shown that "barcode decomposition" is well-defined in single persistence theory in 1950s (Krul-SShmidd-Azumaal decomposition makes the persistence module M (A, uniquely decomposable into barcodes. This barcode decomposition is exactly what we call a Persistence Diagram.
Theorem Botnan & Lesnick (2022)-Thooh 4.2]. This
However, when one goes to higher dimensions, i.e. d 2, then the threshold set {(a;, 3,)3 is no longer totally ordered, but becomes partially ordered (Poset). In other words. some indices have ordering relation (1, < (4, 7), while some do not, e.g., (2,3) vs. (1,5). Hence, if one has multipersistence grid { b we no longer can talk about birth time or death time as there Srull-Schmidt-Aee
Theorem is no longer true for is no ordering anymore. Furthermore, - 4.2. Hence, for general multipersistence upper dimensions Boonnan & Lesnick
modules barcode decomposition is not possible, and the direct generalization of single persistence to multipersistence fails. On the other hand, even if the multipersistence module has a good barcode decomposition, because of partial ordering, representing these barcodes faithfully is another major problem. Multipersistence modules are an important subject in commutative algebra, where one can find the details of the topic in Eisenbud (2013).
While complete generalization is out of reach for now, several attempts have been tried to utilize MP idea [Lesnick] 2015). One of the first such novel idea came from Lesnick & Wright (2015) where they suggest to use one dimensional slices in the MP grid, and get the signature of the most dominant features. Later. Carrière& & Blumberg (2020) combined several slicing directions (vineyards) and obtained vectorization by summarizing several persistence diagrams (PDs) in these directions. Slicing techniques use the persistence diagrams of predetermined one-dimensional slices in the multipersistence grid, and then combine (compress) them as one dimensional output |Botnan & Lesnick (2022). In that respect, one major issue is that the topological summary highly depends on the predetermined slicing directions in this approach, and how to decide this direction. The other problem is the loss of information when compressing the information in various persistence diagrams.
As explained above, MP approach has still technical problems to reach its full potential, and there are several attempts utilize this idea. In this paper, we do not claim to solve theoretical problems of multipersistence homology, but offer a novel, highly practical multidimensional topological summary by advancing the existing methods. We use the grid directions in the multipersistence module as natural slicing directions and produce mutidimensional topological summary of the data. As a result, these multidimensional topological fingerprints are capable of capturing very fine topological information hidden in the data. Furthermore, in the case the data provides more than two very important filtration functions, our framework easily accommodates these functions and induces corresponding substructures. Then, our EMP model capture the evolving topological patterns of these substructures and summarize them in matrices and arrays which are highly practical output format to be used with various MI. models.
Our model is highly different from previous work mostly because of its practicality and computational efficiency. Among these, the closest method to ours is Carrière & Blumberg (2020) which employs slicing techniques a different way. Like us, they have predetermined slicing options (vineyards), and they compute the single persistence diagrams on these slices and combine them in a unique way by using weight functions induced from lifespans of the topological features in this collection of persistence diagram. In our approach, we use only horizontal slices and do not compress the information. First, choosing horizontal slices computationally very feasible to obtain persistence diagrams. Second, offer variety of options on how vectorize these persistence diagrams.
18

---

[ Under review as a conference paper at ICLR 2023
Veutorfaaaton module
Fiees attrrtcco
EMP
Figure 3: Illustration of the EMP framework for networks. Using the pair of filtration functions f. y we define non-decreasing thresholds {a, and {3, HT respectively, based node features, red, and edge features, blue. Both, filtrations and vectorizations run in parallel better use computational resources and produce EMP representations in timely manner.
Hence, depending on the dataset, one can use vectorization methods which emphasize long barcodes (Silhouette with p 1, Entropy, Persistence Image) or the ones which considers all signals equally (Betti). Our experiments proved that these variety of options can be quite useful as some EMP vectorizations give much better result than others different datasets (Appendix
E
FURTHER DETAILS ON EXPERIMENTS
E. BENCHMARK DATASETS AND EXPERIMENTAL SETUP
In experiments,
11 benchmark datasets for graph classification tasks (see Table 2 We have run our models for graph classification tasks on an 8-core DO droplet machine with Intel Xeon Scalable processors base frequency of 2.5 Ghz. Table summarize the statistics the datasets in our experiments.
Table 2: Summary statistics of the datasets.
Dataset
# Graphs
Avg.
[V]
Avg.
# Class Node Attr. (Dim.) Edge Attr. (Dim.)
BZR MD
306
21.30
225.06
2
3
COX2 MD
303
26.28
335.12
2
DHFR_MP
393
23.87
283.02
2
MUTAG
188
17.93
19.79
2
PROTEINS
1113
39.06
72.82
2
IMDB-B
1000
19.77
96.53
2
IMDB-M
1500
13.00
65,94
3
REDDIT-B 2000
429.63
497.75
2
REDDIT-M-5K 4999
508.82
594.87
2
The resolution of vectorization is the most significant parameter, which may impact the computational performance and results. As such, we use a fixed resolution to get consistent results in all experiments and consider time constraints server usage. We use resolution size of 50x50 for each summary
19

---

Under review as a conference paper at ICLR 2023
function, and the standard parameters set by the Gudhi library in Python The order of landscape summary function is set to 1 (max), whilst the power of weights is set to I for silhouette summaries.
Results in Table D comes from computing MP using filtration functions follows. BZR MDD COX2_ _D_ and DHFR_M use weighted node-degree and edge-power filtrations. PROTEINS uses node-closeness and edge-betweenness power filtrations. MUTAG, IMDB-BIB -INARY, and IMDB- MULTI use node-katz centrality and edge-ricci curvature power filtrations. REDDIT-BINARY, and REDDIT-MULTI-SK use node-katz centrality and edge-ricci curvature filtrations. We performed an empirical analysis to select previous filter functions for each graph network. We use three types of vectorizations: Betti curves, silhouette functions and entropy summary functions. For each case we compute both 0-dim and I-dim MP topological features.
F COMPUTATIONAL COMPLEXITY
Computational complexity (CC) of persistence diagram (D) is O(N3), where A is the number of k-simplices in A OOter et al. 2017). CC of EMP summary M depends on the vectorization s used and the number d of the Tilrratoon functions one uses. If r the resolution size of the multipersistence grid, then one needs r(d-1) single persistence diagrams to obtain M Therefore, )
p) = O(r(d-1) AA33, Cm(m) where (m)) CC for and m the number of barcodes in RD e.g.. if yp is persistence landscape, then C₂ (m) = m² and hence CC for EMP Landscape with d = is (r complexity is again reduced to ((N)). On the other hand, as Betti numbers do not need PDx to be computed, it is possible to obtain much faster algorithms for EMP Betti Summary (Edelsbrunner & Parsa 2014). Recently, Lesnick & Wright (2022) introduced quite fast algorithm for EMP Betti summaries with (MM) time where M is the rank of the multipersistence module with minimal representation.
) In practice, r is a constant and m is small compared to M, hence the
G ABLATION STUDY
G.1 DIFTERENT TYPES OF EMP SUMMARIES
Furthermore, to evaluate the performance of different types of EMP summaries (i.c., EMP Silhouette (EMP-S). EMP Entropy (EMP-E), and EMP Betti (EMP-B) with different dimensions (i.e., Ho: O-dimensional topology, and H 1-dimensional topology) and graph-based features (i.e., fv: node features, and fe: edge features; see more details in Section 5.2 and Appendix E. We include comparative statistics using all combinations of input variables, i.e. ablation study, for 3 datasets in our analysis: BZR-MD (Table 3. DHFR-MD (Table 4.. and
(Table
Each cell shows the classification accuracy (in % + standard deviation) when using different combi- nations of variables. The best accuracy result highlighted using bold font. A row/column named as 'none' means that either graph- based features, or EMP summaries where not used to compute the experiments. As such, the top row shows all the accuracy results without using any EMP topological features. The first/left column shows the results only using EMP topological features. The cell in the bottom right corner, of each EMP group, contains the accuracy results using all graph-extracted/EMMP features available.
We can observe that: (i) best results contains 1 1-dimensional EMP summaries, demonstrating the necessity of capturing higher-order structures (e.g.. triangles/cycles), (ii) the choice of the EMP summary can significantly affect the performance, and (iii) the addition of EMP topological features generally improves accuracy of versions without EMP summaries, thus, demonstrating the importance of modeling global and topological graph structures.
G.2 ORDER FILTRATION
With our novel approach, especially sublevel/superlevel filtration, we give a computationally very efficient way to extract information of substructures of the data induced by multiple functions. Since
httpss//gudhi/ inria. htt.://iiiiiaa.r/ttttooo///ttaaa
20

---

Under review as a conference paper at ICLR 2023
Table 3: Ablation Study on BZR MD dataset.
none
fv
fv + fe
none
67.124 = 1.959
58.714 + 0.520
67.642 1.724
EMP-B Ho
67.870 + 1.677
68,499 1.962
67.514
1.868
68.037 2.035
EMP-B H1
69.205 + 1.239
69.157 = 1.220
68.935 + 0.818
69.223 + 1.058
EMP-B Hu H1
68.100 + 1.171
68.492 = 1.245
68.335 + 1.445
69.077 1.470
EMP-E Ho
65.190 + 1.484
64.930 = 2.045
64,962 + 1.682
65.288 + 1.754
EMP-E HI
77.469 + 1.144
77.438 0.727
77.441 0.830
77.766 0.952
EMP-E Ho H1
73.023 + 0.818
72.963 + 1.014
73.057 + 1.284
73.324 + 1.086
EMP-S Ho
68.135 + 1.294
68.525
+ 0.865
68.426 + 1.235
68.232 + 0.969
EMP-S H1
71.068 + 1.417
71.071 + 1.167
70.906 1.416
70.743 1.275
EMP-S Ho H1
72.282 + 1.012
72.246
0.883
72.682 + 0.913
72.904 0.901
Table Ablation Study on DHFR MD dataset.
fv
fv + fe
none
68.333 + 0.874
60.707 1.455
68.058 1.159
EMP-B Ho
71.872 + 0.804
72.097 0.876
71.794 + 0.541
72.121 0.943
EMP-B Hi
66.638 0.690
68.190 = 0.933
67.072 0.705
68.774 + 1.028
EMP-B Hu H1
73.959 + 0.746
74.087 = 0.820
74.085 0.671
74.213 0.905
EMP-E Ho
74.906 + 0.968
74.550 = 0.867
74.521 + 1.066
74.523 + 1.027
EMP-E H1
66.218 + 1.499
66.424 1.304
66.067 1.152
66.397 0.899
EMP-E Ho H1
74.947 + 0.663
74.849 + 0.819
74.667 + 0.922
74.796 + 0.960
EMP-S Ho
78.434 + 0.344
78.028 = 0.597
78.537 = 0.677
78.309 + 0.681
EMP-S H.
75.053 + 0.909
74.953 0.930
75.056 0.785
75.259 1.051
EMP-S Ho H1
80.174 + 1.081
80.503 = 1.066
80.174 + 0.864
80.126 0.939
Table 5: Ablation Study on REDDIT-B dataset.
none
fv
fs
fv + fc
none
89.680 + 0.300
79.590 + 0.394
90.125 + 0.277
EMP-B B Ho
88.925 + 0.168
90.400 045
89.145 0.193
90.520 0.204
EMP-B H1
80.715 + 0.235
87.090 + 0.217
84.620 0.160
88.225 + 0.280
EMP-B Hg H1
89.970 + 0.309
0.184 90.945
0.234 90.025
91.025 0.221
EMP-E Ho
88.140 + 0.265
89.875 +: 0.185
88.400 + 0.210
89.945 0.177
EMP-E Hi
79.850 + 0.365
87.670 0.303
84.600 = 0.214
88.640 0.156
EMP-E Ho Hi
89.285 + 0.234
90.010 = 0.234
89.240 = 0.202
90.045 + 0.221
EMP-S Ho
86.150 + 0.261
87.925 = 0.162
86.940 + 0.206
88.415 + 0.241
EMP-S H.
77.580 + 0.186
85.435 = 0.332
81.580 0.222
86.960 0.346
EMP-S Ho H1
86.790 + 0.385
88.250 = 0.266
87.410 + 0.315
88.590 + 0.377
we only use horizontal slices, the first function only used for finer filtration, and the second function gives the persistence diagrams. This makes method a-symmetric (the order is important). Hence, one can change the order and get different performance results for the model. This asymmetry enriches method not contain the same information about the multipersistence grid. To observe the effect changing the order of the filtering functions, experiments two benchmark datasets, BZR MDD and
combine both feature vectors obtained by different order they do
21

---

Under review as a conference paper at ICLR 2023
Our experiments show that in some datasets, the order can be highly important,
while others, it has negligible effect on the performance.
Table ( (BZR MD) shows significant changes in the performance for all our vectorizations (EMP- Betti, Sillhitho and EMP- MMMP-Entroyy)..... In Figure 4a we also see half of the models, one order better than the other, while in the other half of the models, the opposite is true. On the other hand, we observe that for the REDDIT-BINARY dataset, the order not as important for these functions (Table 7 & Figure 4b) the change in performance is not as significant in BZR_MD.
Table 6: Graph Dataset BZR_MD. Impact on classification accuracy when modifying the filtration ordering. Sy and We denotes sublevel filtration on nodes and weight fltration on edges, respectively, The statistical significance, when one order is better that the other, shown three levels (0.1, 0.05, 0.01) and the best overall result of each order filtration is in bold font.
Order
none
fv
fe
fv + fe
67.124 = 1.959
58.714 + 0.520
67.642 + 1.724 67.642 + 1.724
none
67.124 + 1,959
58,714 = 0.520
EMP-B
Sv ~M WE 71.414 + 1,638
71.446 + 1.166
71,351 + 1.107
71,610 + 1.125
Ho
We Sv 76.192 + 1.188 ***
76.363 0.861 ***
75.804 1.025
75.809 + 0.989
EMP-B
Sv ~9 We 69.047 = 1.092
69.337 + 0.833
69.114 0.711
69.798 + 0.845
H1
We ~ Sy 69.094 = 1.231
70.196 = 0.860**
69.648 + 0.894
70.296 + 0.973
EMP-B
Sy We 72.789 = 1.544
72.946 1.502
72.848 1.286
73,204 + 1.568
Ho + H1
We ~ Sv 75.156 = 0.647**
74.996 + 0.667
75.160 + 0.821
75.055 + 0.926
EMP-E
Sy We 71.967 = 1.091
72.129 = 1.335
71,803 + 1.253
72.198 + 1.280
Ho
We ~ Sv 73.274 + 0.963
74.285 + 1.206 T*
73.314 1.258
74.812 + 1.419
EMP-E
Sy ~ We 72.485 + 1.209
72.452 + 1.121
72.326 + 0.725 ***
72.230 + r
H1
We Sv 67.097 + 1.364
65.853 1.457
66.274 1.370
66.246 + 1.273
EMP-E
Sy ~ We 75.498 + 1.338
75.819 + 1.209
75.133 1.357
75.303 + 1.303
Ho + H, We ~ Sy 74.985 = 1.112
73.410 + 1.378
73.841 + 1.200
73.053 + 1.227
EMP-S
Sy We 69.191 = 1.138
69.717 0.859
69.224 0.960
69.417 + 1.036
Ho
We ~ Sv 75.926 + 1.051
76.320 + 0.952
75.927 + 0.597
76.187 + 0.713
EMPS
Sy We 74.067 + 0m5
74.428 + 0.723
74.432 + 1.003
74.659 + 0.919
H
We ~ Sy 70.232 + 1.211
69.903 + 1.481
70.065
1.347
70.068 + 1.141
EMP-S
Sy ~ We 77.658 + 0.692
78.025 + 0.656
77.794 + 0.496
77.861 + 0.802
Ho + H1 We ~ Sy 74.760 + 1.394
75.286 + 1.054
75.028
1.116
75.128 + 1.099
22

---

Under review as a conference paper at ICLR 2023
Table 7: Graph Dataset REDDIT-BINARY Impact on classification accuracy when modifying the filtration ordering. Sy and WE denotes sublevel filtration on nodes and weight fitration on edges, respectively. The statistical significance, when one order is better that the other, is shown at three levels (0.1, 0.05, 0.01) and the best overall result of each order filtration is in bold font.
Order
none
fv
SE
Jv + + SE
none
89.680 + 0.300
79,590 + 0.394
90.125 + 0.277
none
89.680 = 0.300
79.590 0.394
90.125 + 0.277
EMP-B
Sv ~y Wg 88.925 = 0.168
90.400 + 0.145
89.145
0.193
90.520 + 0.204
Ho
WE ~ Sy 90.005 = 0.196**
90.825 = 0.136**
90.135 + 0.161
90.925 + 0.133
EMP-B Sy We 80.715 + 0.235
87.090 + 0.217
84.620 0.160
88.225 + 0.280
H1
WE ~ Sy 80.880 + 0.335
88.300 + 0.334
85.030 + 0.363
88,895 + 0.323
EMP-B Sy WE 89.970 + 0.309
90.945 + 0.184*
90.025 + 0.234
91.025 + 0.221**
Ho + H1 We ~ Sv 90.020 = 0.200
90.650 = 0.270
90.125 + 0.154
90.770 = 0.198
EMP-E
Sy ~ WE 88. = 0.265
89.875 + 0.185
88.400 + 0.210
89.945 + 0.177
Ho
We Sy 89.695 = 0.157
90.245 = 0.147
89.850 0.199
90.450 + 0.186**
EMP-E
Sy ~ WE 79.850 = 0.365
87.670 = 0,303
84.600 + 0.214 .*
88.640 + 0.156
H1
WE ~ Sy 74.560 = 0.308
87.545 = 0.196
83.755 = 0.239
88.350 = 0.196
EMP-E
Sy WE 89.285 + 0.234
90.010 + 0.234
89,240 + 0.202
90.045 + 0.221
Ho + H1 We ~ Sy 90.015 + 0.192
90.235 + 0.243*
90.130 + 0.200
90.275 + 0.171
EMP-S
Sy We 85.150 = 0.261
87.925 = 0.162
86.940 + 0.206
88.415 + 0.241
Ho
We ~ Sv 89.380 = 0.117
90.345 = 0,205
89.545 + 0.207
90.455 + 0.156
EMP-S
Sy ~9 We 77.580 = 0.186
85.435 + 0.332
81,580 + 0.222
86.960 + 0.346
H1
We Sy 75.165 = 0.367
86.775 = 0.292***
83.125 0.415
87.295 = 0.325**
EMP-S
Sy ~ We 06.790- = 0.385
88.250 + 0.266
87.410 - 0.315
88.590 + 0.377
Ho + H1 We Sy 89.715 + 0.279
90.495 + 0.248*
89.780 + 0.337
90.580 + 0.2
none f
fo fc
none f
4e f
none
none
EMP-B
EMP-B Ho-
EMP-B H
EMP-B H2
EMP-B Ho + H1
EMP-B Ho + H1-
EMP-E Ho
EMP-E Ho-
EMP-E H1
EMP-E H1
EMP-E Ho + Hj
EMP-E Ho H
EMP-S Ho
EMP-S Ho
EMP-S H1
EMP-S H1
EMP-S Ho
EMP-S Ho
none Fr fp fo
none
Fv fe f
(a)
(b)
Figure 4: Visual summary of the impact on classification accuracy when modifying the filtration ordering, for each combination of features and EMP summaries. Whenever statistical hypothesis support winner, the corresponding cell is coloured either as blue (Sp WE), or red (We Sy).
(a) BZR MD. (b) REDDIT-BINARY.
23


Reviews:
[{"review_id": "s4XBkNp1ZP3", "reviewer": "Reviewer_mkf8", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a mathematical framework for working with graphs. The framework is based on two main tools: the multiparameter persistence and persistent homology. This build a framework for topological data analysis that is able to use the data attributes on the nodes. The experiments show promising results with strong improvement on some data sets. ", "summary_of_the_review": "This paper presents a topological data analysis framework for graphs based on persistent homology and multipersistence. This lead to a stable framework for graph learning and the experiments shows promising results. However the tools are not common in the ML community thus, the paper is hard to read and understand. Furthermore some weakness about the order of filters and the dimension of features reduce the interest of the framework. ", "strength_and_weaknesses": "## Strength\n\nThe propose topological data analysis is interesting on several points\n1. It is fairly general as it allow data attributes on nodes.\n2. It is able to catch complex structure that may appear with graphs.\n3. It is not much sensitive to structural noise.\n4. The filtration tools can be dedicated to some tasks helping to catch hidden features.\n5. There is a stability guarantee.\n\n## Weaknesses\n\nSadly this paper has several strong weaknesses.\n1. It is very hard to follow for someone not familiar with persistent homology.\n2. It is not fit for high dimensional features on the nodes.\n3. The order of the filters is important, the authors say that one can use the importance of the features. This is something that could be hard to find.\n4. The experiments only include classical GNN, there exists now more powerful GNN. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "e5abalzDGR", "reviewer": "Reviewer_xbqM", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper presents a novel topology-driven approach for feature generation in data sets. The paper is fundamentally built upon the paradigm of persistent homology, a method for obtaining multi-scale topological features of complex data sets such as point clouds and graphs. Since \"ordinary\" persistent homology is restricted to providing topological features according to a *single* scale parameter, the paper leverages multidimensional persistence theory to enable the use of multiple such parameters. This permits viewing a data set under different data lenses, such as a distance parameter versus a density parameter. Multidimensional persistence theory being mathematically more cumbersome that the single-parameter approach, the paper introduces a smart \"slicing\" strategy, turning any multi-parameter into a set of single-parameter approaches.\n\nIn addition, the paper shows how existing topological featurisation strategies, i.e. algorithms for calculating topological features from data, can be recast into such a multi-parameter setting. Experiments in graph classification serve as a culmination of the research directions outlined in the paper. \n", "summary_of_the_review": "This is an exciting contribution to the emerging field of computational topology. While the paper in its present form suffers from some issues, in particular with respect to the delineation to existing work and the clarity of the experimental setup, I do believe that these issues can be overcome within the revision cycle. Thus, I tend to conditionally endorse this paper for an eventual presentation at the conference, provided that the issues outlined above are sufficiently well addressed in a revision.\n", "strength_and_weaknesses": "The primary strength of the paper lies in providing a **novel algorithm for slicing multiparameter persistence modules**. While demonstrated for bi-filtrations on graphs, the method should also easily extend to simplicial complexes, thus opening the door towards making computational topology approaches applicable in such a scenario. The secondary aspect of the paper I appreciate is the use of featurisation techniques from persistent homology to solve graph classification tasks. This showcases the utility of persistent homology techniques in machine learning scenarios.\n\nThe primary weakness of the paper is the **missing delineation to prior work**, making it hard to judge the contribution. Specifically, I would like to see a more in-depth discussion of the [*sliced barcode* technique pioneered by Lesnick and Wright](https://arxiv.org/abs/1512.00180). The main contribution of the paper at hand appears to be a specific type of slicing, namely a \"horizontal\" slicing through a bi-persistence module, raising questions of (a) why this specific slicing technique was selected, and (b) whether the proposed method does not amount to an algorithm that essentially featurises a multiparameter persistence module along a given path (I understand that there are minor differences in the way the filtration is calculated; essentially, this method proposes to calculate *multiple* slices, but the question about the general principle still remains). To this end, the cited paper by Carrière and Blumberg should be discussed in more detail. To the best of my knowledge, they were the first to discuss such slicing techniques in a machine learning context. While I am happy to be proven wrong, I think it would be beneficial for the paper if the main contribution were to be (re)phrased in such a manner.\n\nA secondary aspect of the paper that requires some clarification concerns the **experimental results**: here, the `EMP` method uses a variety of different summary functions and featurisation strategies. Since these techniques are of different expressive powers, it would be crucial to understand *which* precise method was chosen for a given data set (or even for a specific split). If I understand the experiments correctly, different splits of the same data set could conceivably make use of different featurisation strategies, giving `EMP` a certain advantage. If this is correct, it should at least be briefly discussed; the discussion of the precise featurisation strategy for a given data set may also be of independent interest (I am imaging that \"simpler\" methods such as multiparameter Betti curves probably fare less well).\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "PTuiWQPjeJ", "reviewer": "Reviewer_t3P2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a method for dealing with multi-dimensional persistetnce in TDA, i.e., the presence of multiple filtration parameters. In particular, it proposes a method for graph data and provides a vectorization method for machine learning from the information obtained from the proposed method. Finally, the effectiveness of the proposed method for graph data is evaluated for multiple data sets.", "summary_of_the_review": "The awareness of the issue is important and the effect on the subject matter being experimented with is acknowledged. However, it is presumed that the extent to which it is adaptable and effective is limited. This point seems to have been overstated. In addition, the concept of the methodology itself has been around for some time. Even when considered as a method to improve the performance of what is being experimented with, it lacks comparison with the state-of-the-art.\n\n**Conclusion following discussion with the authors**\n\nThe authors' claim was clarified that the most core ideas about multidimensional TDA are existing, but that they give specific computational methods and vectorizations for graphs. It is also shown to be a framework that can be used in various filtration for graphs, and concrete effects are also shown. Although users will need to find the appropriate settings for their specific data, this is a good primer for those who want to apply TDA to their graphs. I hope that the authors will revise their statement, as it still contains some exaggerated misrepresentations of their claims. I will revise the score to reflect the authors' clarification of their claims, but the score will take into account the impact of their proposal.", "strength_and_weaknesses": "Strength\n\n- TDA is very powerful, but does not work well enough when there are multiple meaningful filtrations. Graph data is a target for many such examples, and this method proposes a method for handling multiple filtrations. This is very meaningful.\n- Experiments show the effect on the benchmarks of the graph data.\n\nWeakness\n\n- The difficulty in handling multiple filtrations is that there are multiple paths between two points on the filtration parameter space, and not all paths may lead to the same state. Another problem is that, depending on the definition of multiple filtration, it may be difficult to define birth and death points, and the persistent diagram may be complicated by curves instead of points in space. The proposed method cannot be said to overcome the above. It avoids the above issues for a limited number of targets with limited conditions.\n- It is admitted that the proposed method is one of the realistic methods to handle multiple filtration. However, it cannot handle any filtration. For example, the proposed method is not applicable to rips filtration and weighed rips filtration for point clouds, because one filtration would make it not a point cloud anymore. Although the authors write that the method can be applied to examples other than those in this paper, a clear discussion should be made regarding the conditions. At least the previously applied filtration should not change the data format.\n- There have been previous efforts regarding the concept of this paper. There is at least the following (though this is not a paper).\nhttps://patentimages.storage.googleapis.com/80/21/7f/3d5033afb8ef36/US11024022.pdf\nTaking the above into account, the novelty of this paper may be its application to limited graphical data. Clearly discuss where the novelty lies.\n- It is possible to find value in the method as a method for the data that is the subject of the experiment, but the comparison is never state-of-the-art. For example, U2GNN (https://arxiv.org/pdf/1909.11855.pdf), DUGNN (https://arxiv.org/abs/1909.10086), FactorGCN (https://arxiv.org/abs/2010.05421 ), etc. should also be compared.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject