TopER: Topological Embeddings in Graph Representation Learning

## Abstract

Abstract Graph embeddings play a critical role in graph representation learning, allowing machine learning models to explore and interpret graph-structured data. However, existing methods often rely on opaque, high-dimensional embeddings, limiting interpretability and practical visualization. In this work, we introduce Topological Evolution Rate (TopER), a novel, low-dimensional embedding approach grounded in topological data analysis. TopER simplifies a key topological approach, Persistent Homology, by calculating the evolution rate of graph substructures, resulting in intuitive and interpretable visualizations of graph data. This approach not only enhances the exploration of graph datasets but also delivers competitive performance in graph clustering and classification tasks. Our TopER-based models achieve or surpass state-of-the-art results across molecular, biological, and social network datasets in tasks such as classification, clustering, and visualization.

## 1 Introduction

Graphs are a fundamental data structure utilized extensively to model complex interactions within various domains, such as social networks (Leskovec et al.,, ), molecular structures (You et al.,, ), and transportation systems (Duan et al.,, ). Their inherent flexibility, however, introduces significant challenges when applied to machine learning tasks, primarily due to their irregular and high-dimensional nature. Due to the fact that graph data lacks inherent ordering and consistent dimensionality, traditional machine learning methods—designed for data in vector spaces—struggle with it.

Graph Neural Networks (GNNs) have emerged as the state-of-the-art models for tackling graph machine learning tasks due to their ability to learn effectively from graph-structured data. In the predominant paradigm of message-passing GNNs, the process begins by generating node embeddings. These embeddings can then be used in tasks such as node classification or link prediction. However, for graph-related tasks, such as molecular property prediction, the embeddings must be aggregated through a pooling layer to form graph-level representations. This method is computationally intensive, largely because the generation and management of node embeddings as intermediate steps substantially increase the overall computational burden. Ideally, an approach would allow for the direct creation of graph embeddings, circumventing the need to generate node-level representations first. Furthermore, these graph embeddings must be both low-dimensional and interpretable to maximize their practical utility and efficiency in various applications.

Topological Data Analysis (TDA) is well-suited for directly constructing graph representations without costly node embeddings. Topology studies the shape of data, and TDA primarily focuses on the qualitative properties of space, such as continuity and connectivity (Coskunuzer and Akçora,, ). A particularly effective technique in TDA is Persistent Homology (PH), which tracks topological features—like connected components and cycles—across various scales via a process known as filtration. Filtration is adept at revealing both local and global structures within graphs. It proves exceptionally useful for comparing graphs of different sizes that maintain the same inherent structure, which may suggest similar properties in graph datasets. For instance, similar substructures in protein interaction networks across different species may indicate comparable biological functions. By focusing on data shape, PH proves invaluable in graph tasks that benefit from a graph-centric approach, offering insights that might not be as apparent when focusing on individual node analysis. This shift from a node-centric to a graph-centric perspective can dramatically improve the understanding and application of graph data in fields like bioinformatics and network analysis. However, the utility of Persistent Homology is limited by the high computational demands involved in extracting topological features during the filtration process, mainly due to its cubic time complexity (Otter et al.,, ). This constraint reduces its practicality for large-scale graphs and has restricted the broader integration of PH in graph representation learning.

With this work, we take a significant step forward in addressing the challenges of topological graph representation learning and introduce Topological Evolution Rate (TopER). This novel approach refines the Persistent Homology process to efficiently capture graph substructures, thereby mitigating the significant computational demands of calculating complex topological features. As graph representation learning aligns naturally with Topological Data Analysis, TopER excels in graph clustering and classification tasks where it achieves the best rank in experiments. Furthermore, simplifying graph data into a low dimensional space, TopER creates intuitive visualizations that reveal clusters, outliers, and other essential topological features, as demonstrated in Figure 1. As a result, TopER merges interpretability with efficiency in graph representation learning, providing an ideal balance that can scale to large graphs.

To our knowledge, TopER is the first topology-based graph representation learning method that can create low-dimensional, efficient, and scalable graph representations.

Figure: (a)
Refer to caption: x1.png

Our contributions can be summarized as follows:

- •
New Graph Embedding Method: We introduce TopER, a compact and computationally feasible graph representation designed to capture the evolution of graph substructures.
- •
Interpretable Visualizations: TopER generates interpretable, low-dimensional embeddings, enabling clear visualization of clusters and outliers. It excels in providing insights within individual graph datasets and across multiple datasets, facilitating comparative analysis.
- •
Enhanced Use of Persistent Homology: TopER optimizes the filtration process in PH, offering computational efficiency and compact outputs, while boosting the performance of traditional PH methods.
- •
Theoretical Stability: We establish theoretical stability guarantees for TopER, ensuring that the embeddings are reliable and robust across various filtration functions.
- •
Competitive Performance: Our extensive experiments on benchmark datasets demonstrate that TopER delivers consistently competitive or superior performance in clustering and classification tasks compared to state-of-the-art models.

## 2 Related Work

Graph Representation Learning. Graph representation learning is a dynamic subfield of machine learning, focusing on transforming graph data into efficient, low-dimensional vector representations that encapsulate essential features of the data (Hamilton,, ; Gao et al.,, ). These representations facilitate a deeper analytical understanding of graphs, which is critical for various applications such as molecular graph property prediction (Dong et al.,, ).

Graph Neural Networks. Graph Neural Networks have revolutionized the analysis of graph data, drawing parallels with the success of Convolutional Neural Networks in image processing (Errica et al.,, ). GNNs utilize spectral and spatial approaches to graph convolutions based on the graph Laplacian and direct graph convolutions, respectively (Bruna et al.,, ; Defferrard et al.,, ; Kipf and Welling,, ). Despite their success, GNNs often suffer from issues like over-smoothing and lack transparency, making them less ideal for applications requiring interpretability (Günnemann,, ).

TDA in Graph Representation Learning.
Topological Data Analysis provides a robust and computationally efficient framework to address the interpretability and over-smoothing issues present in GNNs (Aktas et al.,, ). Persistent Homology, a key technique in TDA, has been applied successfully to graph data, demonstrating potential to match or even exceed the performance of traditional methods in classification and clustering tasks (Hensel et al.,, ; Demir et al.,, ; Hiraoka et al.,, ; Immonen et al.,, ; ; Loiseaux et al.,, ). However, the computational intensity of PH limits its scalability (Hofer et al.,, ; Zhao et al.,, ; Akcora et al.,, ).

Graph Embeddings and Visualization. Graph embedding techniques, including spectral methods, random walk-based approaches, and deep learning-based models, transform graph data into vector representations to support tasks like visualization and machine learning (Cai et al.,, ; Goyal and Ferrara,, ; Xu,, ). Approaches such as Laplacian Eigenmaps and DeepWalk have been particularly effective in revealing clusters within graphs (Belkin and Niyogi,, ; Perozzi et al.,, ). However, these methods are predominantly applied to visualize a single graph in node classification tasks, focusing on cluster identification (Wang et al.,, ; Mavromatis and Karypis,, ; Tsitsulin et al.,, ). Furthermore, they often overlook domain-specific information, which can limit their effectiveness in more specialized applications (Jin and Zafarani,, ).

TopER addresses these challenges by combining the interpretative benefits of TDA with the analytical strength of modern graph machine learning. Distinct from current approaches, TopER employs a simplified filtration process to create embeddings that are both interpretable and computationally efficient. By extending the filtration to multiple functions, TopER stands out as one of the first methods to offer effective and interpretable visualizations of graph datasets, while also achieving superior performance in clustering and classification tasks.

## 3 Background

TDA has emerged as a promising approach in graph representation learning (Aktas et al.,, ). Among its various techniques, persistence homology (PH) is notable for its robust capacity to quantify and monitor topological features across different scales.

### 3.1 Persistent Homology for Graphs

Persistent Homology applies algebraic topology to reveal hidden shape patterns within data, capturing these insights by tracking the evolution of topological features like components, loops, and cavities at varying resolutions (Coskunuzer and Akçora,, ). The PH process involves constructing filtrations, obtaining persistence diagrams, and vectorizations. Our model, however, primarily utilizes the filtration step, reformulating the evolution information in a novel manner.

In the crucial filtration step, PH decomposes a graph $\mathcal{G}$ into a nested sequence of subgraphs $\mathcal{G}_{1}\subseteq\mathcal{G}_{2}\subseteq\ldots\subseteq\mathcal{G}_{n}
=\mathcal{G}$. For each $\mathcal{G}_{i}$, an abstract simplicial complex $\widehat{\mathcal{G}}_{i}$ is defined, forming a filtration of simplicial complexes. Clique complexes are typical choices, where each $(k+1)$-complete subgraph in $\mathcal{G}$ corresponds to a $k$-simplex (Aktas et al.,, ). To obtain effective filtrations, utilizing relevant filtration functions is essential.

Filtration Functions. Filtration functions are essential in PH. For a given graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, a common approach is to define a node filtration function $f:\mathcal{V}\to\mathbb{R}$, which establishes a hierarchy among the nodes. By selecting a monotone increasing set of thresholds $\mathcal{I}=\{\epsilon_{i}\}_{i=1}^{n}$, this method generates subgraphs $\mathcal{G}_{i}=(\mathcal{V}_{i},\mathcal{E}_{i})$ where $\mathcal{V}_{i}=\{v\in\mathcal{V}\mid f(v)\leq\epsilon_{i}\}$ and $\mathcal{E}_{i}$ is the set of edges in $\mathcal{E}$ with endpoints in $\mathcal{V}_{i}$. This is called a sublevel filtration induced by $f$ (See Figure 2). Similarly, superlevel filtrations can be constructed by defining $\mathcal{V}_{i}=\{v\in\mathcal{V}\mid f(v)\geq\epsilon_{i}\}$ for decreasing thresholds (Aktas et al.,, ).

Similarly, one can use edge filtration functions $g:\mathbb{E}\to\mathbb{R}$ to define such a filtration. Similarly, by defining $\mathcal{E}_{i}=\{e_{jk}\in\mathcal{E}\mid g(e_{jk})\leq\epsilon_{i}\}$, and $\mathcal{V}_{i}$ as the all endpoints of $\mathcal{E}_{i}$, one can define a nested sequence $\{\mathcal{G}_{i}\}_{i=1}^{n}$. Especially, for weighted graphs, this method is highly preferable as weights naturally defines an edge filtration function. The common node filtration functions are degree, betweenness, centrality, heat kernel signatures, and node functions coming from the domain of the datasets (e.g., atomic number for molecular graphs). Common edge filtration functions are Ollivier and Forman Ricci curvatures, and edge weights (e.g. transaction amounts for financial networks).

Figure: Figure 2: Filtration. For $\mathcal{G}=\mathcal{G}_{3}$ in both examples, the top figure illustrates superlevel filtration with node degree function for thresholds $\{1,2,3\}$. Similarly, the bottom figure illustrates sublevel filtration for edge weights with thresholds $\{1.5,1.8,2.1\}$.
Refer to caption: extracted/5897538/figures/rg2.png

We developed a new filtration function, Popularity, in addition to existing approaches, to enhance the topological representation of graph-structured data in our studies. Popularity is similar to the degree function (Newman,, ), but also considers the average degree of neighboring nodes of a given node $v$. This function enriches node filtration by incorporating broader neighborhood information, potentially revealing deeper insights into graph structure. Mathematically, for each node $v$ in the graph, we define the popularity function as: $\mathcal{P}(v)=\deg(v)+\frac{\sum_{u\in\mathcal{N}(v)}\deg(u)}{|\mathcal{N}(v)|}$, where $\deg(v)$ is the degree of node $v$ and $\mathcal{N}(v)$ denotes the set of nodes adjacent to $v$. This function incorporates $2$-neighborhood information by giving more weight to high-degree (popular) neighbors. Popularity can be considered an improved version of the degree function, as it also accounts for the popularity of a node’s neighbors. The intuition is that if degree represents the number of friends, popularity accounts for the popular friends (node neighbors with high degree) with greater weight.

## 4 TopER: Topological Evolution Rate

TopER innovatively extends the concept of filtration used in Persistent Homology to track graph substructures more efficiently. This reformulation reduces the computational overhead typically required for detailed topological feature extraction. Unlike traditional Persistent Homology, which extracts costly topological features, TopER summarizes the filtration process through two key parameters derived via regression: filtration sequences and evolution.

Filtration sequences. We first decompose a graph $\mathcal{G}$ into a nested sequence of subgraphs (filtration graphs) $\mathcal{G}_{1}\subseteq\mathcal{G}_{2}\ldots\subseteq\mathcal{G}_{n}=\mathcal
{G}$ by using a filtration function, such as node degree or closeness. Let $\mathcal{G}_{i}\subset\mathcal{G}$, $\mathcal{V}_{i}$ represent nodes in $\mathcal{G}_{i}$ and $\mathcal{E}_{i}$ represent the edges. Next, we compute $x_{i}=|\mathcal{V}_{i}|$ as the count of nodes, and $y_{i}=|\mathcal{E}_{i}|$ as the count of edges. Then, for each filtration graph $\mathcal{G}_{i}$, we obtain the pair $(x_{i},y_{i})\in\mathbb{R}^{2}$, which creates two monotone sequences, $x_{1}\leq x_{2}\leq\dots\leq x_{n}$ and $y_{1}\leq y_{2}\leq\dots\leq y_{n}$. Hence, TopER yields two ordered sets $\mathcal{X},\mathcal{Y}$ describing the evolution of the filtration graphs $\mathcal{G}_{1}\subseteq\ldots\subseteq\mathcal{G}_{n}=\mathcal{G}$, $\mathcal{X}=(x_{1},x_{2},\dots,x_{n})$ and $\mathcal{Y}=(y_{1},y_{2},\dots,y_{n})$. Here, $n$ corresponds to number of thresholds $\{\epsilon_{i}\}_{i=1}^{n}$ used in the filtration step.

Figure: Figure 3: TopER steps. The filtration process on three different graphs using node or edge filtration. The graphs undergo filtration, and for each graph, a best-fit line is determined through the filtration data. The coefficients of these best-fit lines are then used as descriptors for the graphs.
Refer to caption: x4.png

Consider the top row of Figure 2 where we have three filtration graphs (i.e., $n$=3); we have $\mathcal{X}=(2,3,7)$ for node counts and $\mathcal{Y}=(0,2,6)$ for edge counts.

Evolution. In the next step, PH would typically compute topological features on each filtration and create a persistence diagram to summarize the features. Not only it is costly, but the approach would require efforts to vectorize the persistence diagrams. We circumvent this computationally costly step and analyze how the number of edges $\{y_{i}\}$ relates to the number of nodes $\{x_{i}\}$ throughout the filtration sequence. We use line fitting to characterize this relationship as follows.

Simple linear regression, often applied through the least squares method (James et al.,, ), is a standard approach in regression analysis for fitting a linear equation to a set of data points $\{(x_{i},y_{i})\}\subset\mathbb{R}^{2}$. This method calculates the line $\mathcal{L}(x)=a+bx$ that best fits the data by minimizing the loss function $\mathrm{E}=\sum^{N}_{i=1}[\mathcal{L}(x_{i})-y_{i}]^{2}$. The coefficients $(a,b)$, obtained from this regression on the filtration sequences, effectively describe the graph’s structure during filtration (see the descriptor step in Figure 3). Algorithm 1 unifies the filtration and evolution steps.

Figure: Algorithm 1 TopER: Topological Evolution Rate

With evolution on filtration sequences, we define the topological evolution rate of a graph as follows:

###### Definition 1 (Topological Evolution Rate (TopER)) .

Let $f:\mathcal{V}\to\mathbb{R}$ be a filtration function on graph $\mathcal{G}$ and $\mathcal{I}=\{\epsilon_{i}\}_{i=1}^{n}$ be the threshold set. Let $\mathcal{G}_{i}=(\mathcal{V}_{i},\mathcal{E}_{i})$ be the induced filtration. Let $x_{i}=|\mathcal{V}_{i}|$ and $y_{i}=|\mathcal{E}_{i}|$. Let $\mathcal{L}(x)=a+bx$ be the best fitting line to $\{(x_{i},y_{i})\}_{i=1}^{n}$.
Then, we define theTopER vector of $\mathcal{G}$ with respect to $f$ as $\rm{TE}$$(\mathcal{G},f,\mathcal{I})=(a,b)$. We call $a$ the pivot and $b$ the growth of $\mathcal{G}$.

In practice, line fitting may not always be a linear choice and requires multiple controls, which we cannot report here due to space limitations. We discuss these choices and linear/polynomial fit options in Appendix B. We also show visual samples of graph evolution rates in Appendix Figure 6. Furthermore, we define and visualize the most fundamental evolution patterns in Appendix Figure 7.

###### Definition 1 (Topological Evolution Rate (TopER)) .

### 4.1 Computational Complexity

The primary computational steps in TopER include constructing filtration graphs and performing regression on node and edge counts, which incur the following costs.

Analyzing each node and edge across $n$ filtration thresholds typically requires $O(n\times(|\mathcal{V}|+|\mathcal{E}|))$ operations, where $\mathcal{V}$ and $\mathcal{E}$ denote the numbers of vertices and edges, respectively. The regression step involves fitting a line to the pairs $(x_{i},y_{i})$ using the least squares method. The complexity of calculating the necessary sums for this regression is $O(n)$, and solving for the regression coefficients (slope and intercept) from these sums involves a constant amount of additional computation.

Thus, the overall complexity of TopER predominantly hinges on the graph filtration process, summing up to $O(n\times(|\mathcal{V}|+|\mathcal{E}|))$ where $|\mathcal{V}|\gg n$. As we will show in the next section, the runtime costs of TopER are notably low, demonstrating its practicality and efficiency for large-scale applications.

### 4.2 Stability Results

This section states our theorems on the stability of TopER. In the following, $\mathcal{W}_{p}(.,.)$ represents $p$-Wasserstein distance, and $\rm{PD}_{k}(\mathcal{X},f)$ represents $k^{th}$ persistence diagram of $\mathcal{X}$ with sublevel filtration with respect to $f$. Similarly, $\|.\|_{p}$ represents $L^{p}$-norm and $d_{p}(.,.)$ represents $l_{p}$-distance in $\mathbb{R}^{m}$. We fix a threshold set $\mathcal{I}=\{\epsilon_{i}\}_{i=1}^{n}$ for both functions to keep the exposition simple. Further, to keep the setting general, we use the pairs $\{(\beta_{0}(\epsilon_{i}),\beta_{1}(\epsilon_{i}))\}_{i=1}^{n}$ in $\mathbb{R}^{2}$ to fit the least squares line $y=a+bx$ defining $\rm{TE}(\mathcal{X})=(a,b)$.

###### Theorem 1 .

Let $\mathcal{X}$ be a compact metric space, and $f,g:\mathcal{X}\to\mathbb{R}$ be two filtration functions. Then, for some $C>0$,

$$ $\|\rm{TE}_{f}(\mathcal{X})-\rm{TE}_{g}(\mathcal{X})\|_{1}\leq C\cdot\mathcal{W }_{1}(\rm{PD}_{k}(\mathcal{X},f),\rm{PD}_{k}(\mathcal{X},g)).$ $$

By combining the above result with the stability result for sublevel filtrations, we obtain the stability with respect to filtration functions as follows.

###### Corollary 1 .

Let $\mathcal{X}$ be a compact metric space, and $f,g:\mathcal{X}\to\mathbb{R}$ be two filtration functions. Then, for some $C>0$,

$$ $\|\rm{TE}_{f}(\mathcal{X})-\rm{TE}_{g}(\mathcal{X})\|_{1}\leq C\cdot\|f-g\|_{1}$ $$

By adapting the above results to the graph setting, when two metric graphs $\mathcal{G}_{1},\mathcal{G}_{2}$ are close in Gromov-Hausdorff sense, one can obtain a similar stability result for the filtrations of $\mathcal{G}_{i}$ induced by the same filtration function. Due to space limitations, details and the proof of the theorem are given in Appendix C.

###### Theorem 1 .

###### Corollary 1 .

## 5 Experiments

We evaluate the performance of TopER in classification, clustering and visualization. Our Python implementation is available at
[https://anonymous.4open.science/r/TopER-AA38](https://anonymous.4open.science/r/TopER-AA38).

### 5.1 Experimental Setup

Datasets. We conduct experiments on nine benchmark datasets for graph classification. These are (i) the molecule graphs of BZR, and COX2 (Mahé and Vert,, ); (ii) the biological graphs of MUTAG and PROTEINS (Kriege et al.,, ); and (iii) the social graphs of IMDB-Binary (IMDB-B), IMDB-Multi (IMDB-M), REDDIT-Binary (REDDIT-B), and REDDIT-Multi-5K (REDDIT-5K) (Yanardag and Vishwanathan,, ). Finally, the OGBG-MOLHIV is a large molecular property prediction dataset, part of open graph benchmark (OGB) datasets (Hu et al.,, ). Details are given in Table 1.

**Table 1: Characteristics of the benchmark graph classification datasets.**
| Datasets | #Graphs | $\left|\mathcal{V}\right|$ | $\left|\mathcal{E}\right|$ | Classes |
| --- | --- | --- | --- | --- |
| BZR | 405 | 35.75 | 38.36 | 2 |
| COX2 | 467 | 41.22 | 43.45 | 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-5K | 4999 | 508.52 | 594.87 | 5 |
| OGBG-MOLHIV | 41127 | 243.4 | 2266.1 | 2 |

Hardware. We ran experiments on a single machine with 12th Generation Intel Core i7-1270P vPro Processor (E-cores up to 3.50 GHz, P-cores up to 4.80 GHz), and 32Gb of RAM (LPDDR5-6400MHz).

Model Setup and Metrics.
We employ a rigorous experimental setup to ensure a fair comparison and the selection of the best graph classification model. We begin by applying BatchNormalization to the input features to maintain consistent scaling. We employ a 90/10 train-test split, adopt the StratifiedkFold strategy, and present the average accuracy from ten-fold cross-validation across all our models. We employ accuracy as the evaluation metric, a widely utilized performance measure within graph classification tasks (Errica et al.,, ).

Filtration functions. In TopER, we use both node and edge filtrations during filtration (Definition 1). Alongside with popularity, we apply degree, closeness, and degree centrality  (Evans and Chen,, ) as node filtration functions and Forman- and Ollivier-Ricci functions (Lin et al.,, ) as edge filtration functions. We also use atomic weight as a node function for molecular and biological datasets (BZR, COX2, and MUTAG), and node attributes (PROTEINS). We utilized the t-test to assess the statistical significance of each function and applied the Lasso method for regularization, setting the cross-validation parameter to $cv=10$. Functions were retained in the model only if they achieved p-values less than 0.05 in the t-test and had non-zero coefficients in the Lasso model (James et al.,, ). This approach ensures that the selected filtration functions contribute statistically significant and regularized features to the model. Incorporating additional filtration functions can enhance TopER’s ability to analyze graphs from diverse perspectives. However, as we will next illustrate in Table 6, TopER demonstrates strong performance even in its most basic form using the simple and scalable node degree function. This balance of performance and simplicity suits our scalability philosophy; we avoid complex and costly schemes for learning dataset-specific activation functions and homogenize the filtration step in all datasets.

Classifier. We utilize a Multilayer Perceptron (MLP) in our graph classification task. The hyperparameters are detailed in Section A.1.

Figure: Figure 4: TopER run time for synthetic power law graphs (Holme and Kim,, ) with node degree filtration. The mean node degree is $30$, and 100 filtration steps are used.
Refer to caption: x5.png

Baselines. We compare our method with 19 state-of-the-art and recent models in graph classification, including variants of graph neural networks: six GNNs including GCN, DGCNN, Diffpool, ECC, GIN, GraphSAGE which are compared in (Errica et al.,, ) (best results of these six GNNs are given in the 6 GNNs row), FF-GCN (Paliotta et al.,, ); topological methods: DMP (Bodnar et al.,, ), FC-V (O’Bray et al.,, ), WWLS (Fang et al.,, ), MP-HSM (Loiseaux et al.,, ) and EMP (); GNNs enhanced with data augmentation methods: SubMix (Yoo et al.,, ), G-Mix (Han et al.,, ), and EPIC (Heo et al.,, ); GNNs enhanced with contrastive learning methods: RGCL (Li et al.,, ), AutoGCL (Yin et al.,, ), TopoGCL () and prototype-based methods: PGOT (Qian et al.,, ).

**Table 2: Graph Classification. Accuracy results on eight benchmark datasets using 10-fold CV. Baseline results are sourced from the corresponding papers. The best performance is highlighted in bold blue, while the second-best performance is underlined. The final column presents the average deviation of each model’s performance from the best result across all datasets.**
| Model | BZR | COX2 | MUTAG | PROTEINS | IMDB-B | IMDB-M | REDDIT-B | REDDIT-5K | Avg.$\downarrow$ |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| 6 GNNs (Errica et al.,, ) | – | – | 80.42$\pm$2.07 | 75.80$\pm$3.70 | 71.20$\pm$3.90 | 49.10$\pm$3.50 | 89.90$\pm$1.90 | 56.10$\pm$1.60 | 4.13 |
| DMP (Bodnar et al.,, ) | – | – | 84.00$\pm$8.60 | 75.30$\pm$3.30 | 73.80$\pm$4.50 | 50.90$\pm$2.50 | 86.20$\pm$6.80 | 51.90$\pm$2.10 | 4.20 |
| FC-V (O’Bray et al.,, ) | 85.61$\pm$0.59 | 81.01$\pm$0.88 | 87.31$\pm$0.66 | 74.54$\pm$0.48 | 73.84$\pm$0.36 | 46.80$\pm$0.37 | 89.41$\pm$0.24 | 52.36$\pm$0.37 | 4.01 |
| SubMix (Yoo et al.,, ) | 86.34$\pm$2.00 | 84.68$\pm$3.70 | 80.99$\pm$0.60 | 67.80$\pm$2.00 | 70.30$\pm$1.40 | 46.47$\pm$2.50 | – | – | 6.15 |
| G-Mix (Han et al.,, ) | 84.15$\pm$2.30 | 83.83$\pm$2.10 | 81.96$\pm$0.60 | 66.28$\pm$1.10 | 69.40$\pm$1.10 | 46.40$\pm$2.70 | – | – | 6.91 |
| RGCL (Li et al.,, ) | 84.54$\pm$1.67 | 79.31$\pm$0.68 | 87.66$\pm$1.01 | 75.03$\pm$0.43 | 71.85$\pm$0.84 | 49.31$\pm$0.42 | 90.34$\pm$0.58 | 56.38$\pm$0.40 | 3.56 |
| AutoGCL (Yin et al.,, ) | 86.27$\pm$0.71 | 79.31$\pm$0.70 | 88.64$\pm$1.08 | 75.80$\pm$0.36 | 72.32$\pm$0.93 | 50.60$\pm$0.80 | 88.58$\pm$1.49 | 56.75$\pm$0.18 | 3.08 |
| FF-GCN (Paliotta et al.,, ) | 89.00$\pm$5.00 | 78.00$\pm$8.00 | 71.00$\pm$4.00 | 62.00$\pm$1.00 | 63.00$\pm$8.00 | – | – | – | 11.53 |
| WWLS (Fang et al.,, ) | 88.02$\pm$0.61 | 81.58$\pm$0.91 | 88.30$\pm$1.23 | 75.35$\pm$0.74 | 75.08$\pm$0.31 | 51.61$\pm$0.62 | – | – | 2.26 |
| EPIC (Heo et al.,, ) | 88.78$\pm$2.30 | 85.53$\pm$1.60 | 82.44$\pm$0.70 | 69.06$\pm$1.00 | 71.70$\pm$1.00 | 47.93$\pm$1.30 | – | – | 4.67 |
| EMP () | – | – | 88.79$\pm$0.63 | 72.78$\pm$0.54 | 74.44$\pm$0.45 | 48.01$\pm$0.42 | 91.03$\pm$0.22 | 54.41$\pm$0.32 | 2.97 |
| MP-HSM (Loiseaux et al.,, ) | – | 77.10$\pm$3.00 | 85.60$\pm$5.30 | 74.60$\pm$2.10 | 74.80$\pm$2.50 | 47.90$\pm$3.20 | – | – | 4.67 |
| TopoGCL () | 87.17$\pm$0.83 | 81.45$\pm$0.55 | 90.09$\pm$0.93 | 77.30$\pm$0.89 | 74.67$\pm$0.32 | 52.81$\pm$0.31 | 90.40$\pm$0.53 | – | 1.76 |
| PGOT (Qian et al.,, ) | 87.32$\pm$3.90 | 82.98$\pm$5.21 | 92.63$\pm$2.58 | 73.21$\pm$2.59 | 62.90$\pm$3.05 | 51.33$\pm$1.76 | – | – | 3.85 |
| TopER | 90.13$\pm$4.14 | 82.01$\pm$4.59 | 90.99$\pm$6.64 | 74.58$\pm$3.92 | 73.20$\pm$3.43 | 50.00$\pm$4.02 | 92.70$\pm$2.38 | 56.51$\pm$2.22 | 1.60 |

Runtime. TopER is highly scalable and can be applied to a 100K node graph in  2 minutes (see Figure 4). Our small network experiments took about two days in a shared resource setting, whereas the OGBG-MOLHIV experiments took 16.5 hours. One of the most demanding datasets, REDDIT-5K, requires $34.6$ hours to calculate all node and edge functions. The runtime of our methods is dominated by the computation of node functions such as closeness and Riccis. Using approximate values for centrality metrics instead could greatly decrease computation time (Brandes and Pich,, ). Since this is not our current focus, we leave it as future work.

### 5.2 Graph Classification Results

Table 2 shows the accuracy results for the given models. We use the reported results in the corresponding references for each model. “$-$" entries in the table mean the reference did not report any result for that dataset. In (Errica et al.,, ), the authors compare the six most common GNNs on the graph classification task (see the GNNs row). The last column summarizes each model’s overall performance. We report the average of the differences between each model’s performance and the best performance in the column across all datasets. If a model’s performance is missing for a dataset, it is excluded from the average computation for the model.

Out of eight datasets, TopER achieves the best results in two and ranks second in two other datasets. For the remaining four datasets, TopER’s performance is within 4% of the SOTA results. For overall performance, TopER outperforms all other models with an average deviation of 1.60% from the best performances. The closest competitor is TopoGCL, which has an average deviation of 1.76%.

**Table 3: AUC results for OGBG-MOLHIV dataset.**
| Model | AUC |
| --- | --- |
| GIN-VN (Xu et al.,, ) | 77.80$\pm$1.82 |
| HGK-WL (Togninalli et al.,, ) | 79.05$\pm$1.30 |
| WWL (Borgwardt et al.,, ) | 75.58$\pm$1.40 |
| PNA (Corso et al.,, ) | 79.05$\pm$1.32 |
| DGN (Beaini et al.,, ) | 79.70$\pm$0.97 |
| GraphSNN (Wijesinghe and Wang,, ) | 79.72$\pm$1.83 |
| GCN-GNorm (Cai et al.,, ) | 78.83$\pm$1.00 |
| Graphormer (Ying et al.,, ) | 80.51$\pm$0.53 |
| Cy2C-GCN (Choi et al.,, ) | 78.02$\pm$0.60 |
| GAWL (Nikolentzos and Vazirgiannis,, ) | 78.34$\pm$0.39 |
| LLM-GIN (Zhong et al.,, ) | 79.22$\pm$NA |
| GMoE-GIN (Wang et al.,, ) | 76.90$\pm$0.90 |
| TopER | 80.21$\pm$0.15 |

OGBG-MOLHIV results. To evaluate our model’s performance on large datasets, we compare it with recently published models on OGBG-MOLHIV dataset, as shown in Table 3. The performances of these models are listed in chronological order based on their publication dates, with baseline performances reported from (Choi et al.,, ; Ying et al.,, ) or the respective model’s references. In Section A.2, we give further details for TopER performance and contribution of each function on this dataset. TopER achieves the second-best result on the MOLHIV dataset, while the top-performing model requires learning a significantly larger model with 119.5 million parameters.

**Table 4: Accuracy results for TopER vs. Persistent Homology in graph classification tasks.**
|  | BZR | COX2 | PROTEINS | IMDB-B | IMDB-M | RED-5K |
| --- | --- | --- | --- | --- | --- | --- |
| PH | 88.4$\pm$0.6 | 82.0$\pm$0.6 | 74.0$\pm$0.4 | 69.5$\pm$0.5 | 46.5$\pm$0.3 | 54.1$\pm$0.1 |
| TopER | 90.1$\pm$4.1 | 82.0$\pm$4.6 | 74.6$\pm$3.9 | 73.2$\pm$3.4 | 50.0$\pm$4.0 | 56.5$\pm$2.2 |

TopER vs. PH. TopER-based models are more accurate than those based on Persistent Homology. We present a comparison across six datasets in Table 4. The PH results are obtained from (Cai,, ), which extensively examines PH methods in graph classification tasks using four common filtration functions (centrality, degree, fiedler_s, and Ricci), coupled with four popular vectorization techniques. For each dataset, these methods yield 16 outcomes, and we bring in the top-performing combination of filtration and vectorization for each dataset. The results show that TopER outperforms PH in all benchmark datasets.

### 5.3 Graph Clustering Results

We employ cluster quality metrics to assess the embeddings of graphs sourced from all datasets in Table 2. The embeddings are labeled with their respective dataset memberships, and we assume that good embeddings will have graphs of the same dataset clustered together. We evaluate embeddings based on three widely used clustering metrics: Silhouette (SILH), Calinski-Harabasz (CH), and Davies-Bouldin (DB) (Gagolewski et al.,, ). Table 5 compares the clustering performance of TopER and Spectral Zoo (Jin and Zafarani,, ), which is, to our knowledge, the only model that allows low-dimensional graph embeddings. Detailed results are provided in Section A.3. The findings demonstrate that the embeddings generated by TopER outperform those created by Spectral Zoo. This is evident from the superior cluster quality metrics observed for five out of eight datasets in the case of Silhouette and CH, and for all eight datasets in the case of DB.

**Table 5: Clustering Performances. Comparison of Spectral Zoo vs. TopER. The detailed results are given in Section A.3.**
| Metric | Method | BZR | COX2 | MUTAG | PROT. | IMDB-B | IMDB-M | REDD-B | REDD-5K |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Silh $\uparrow$ | Spec. Zoo | 0.050 | 0.049 | 0.344 | 0.050 | 0.097 | -0.024 | 0.108 | -0.121 |
| TopER | 0.249 | 0.414 | 0.258 | 0.086 | 0.064 | -0.032 | 0.196 | -0.067 |  |
| CH $\uparrow$ | Spec. Zoo | 3.51 | 6.13 | 120.73 | 38.77 | 85.24 | 30.98 | 269.94 | 119.81 |
| TopER | 42.58 | 26.00 | 72.52 | 151.64 | 60.52 | 11.77 | 446.12 | 1209.95 |  |
| DB $\downarrow$ | Spec. Zoo | 7.25 | 6.07 | 0.95 | 4.55 | 2.78 | 10.73 | 2.20 | 25.74 |
| TopER | 1.93 | 2.29 | 0.88 | 1.54 | 2.19 | 6.87 | 1.32 | 2.78 |  |

### 5.4 Graph Visualization

In the case of a single filtration function, TopER creates $2D$ graph embeddings $(a,b)$ that can be visualized with ease (see Figure 1). Traditional dimensionality reduction techniques such as PCA can be used to visualize point cloud data, but accurately depicting graph data has historically been a significant challenge (Giovannangeli et al.,, ). To our knowledge, the only model that allows graph visualization is the GraphZoo (Jin and Zafarani,, ).

TopER creates highly interpretable graph visualizations. To recall, the pair $(a,b)$ represents the coefficients of the best-fitting function $L(x)=a+bx$, where $a$ is the pivot (y-intercept) and $b$ is growth (the slope). Specifically, the pivot $a$ reflects graph connectivity, while $b$ reflects the growth rate of edges/nodes for the filtration function. In particular, a higher value of $a$ corresponds to a more interconnected graph. As we demonstrate in Figure 7, graph connectivity and community structure can be analyzed using three types of pivot behavior. In the following, we illustrate how these quantities can be employed to interpret our two-dimensional representations of the graph datasets.

Figure: (a)
Refer to caption: x6.png

In Figure 1(b) of the MUTAG dataset, class B has a higher growth rate and smaller pivot than the red class. This shows that the class is growing faster than class A with respect to the closeness function in the MUTAG dataset, i.e., the graph has a low diameter. Similarly, in contrast, in the PROTEINS dataset (Figure 5(a)), the growth rates are similar for both classes ($\sim 1.5-1.7$), but the pivot (initial graph size) is smaller in class A. This implies that class A has fewer edges in relation to the number of nodes. Such patterns, as described in Section B.4, can reveal key insights into graph topology. In a similar vein, TopER visualizations can be used for anomaly detection. For example, in Figure 1(a), an outlier PROTEINS graph alone has a positive pivot in the figure and appears as the rightmost data point.

More importantly, TopER homogenizes graph embeddings, allowing us to compare graphs across datasets, which may open new paths in training graph foundation models. For example, Figure 1(a) visualizes graphs of three datasets on the same panel where we see that Mutag and COX2 differ in their pivot only. The similarity is not surprising; MUTAG and COX2 are datasets of molecular graphs where nodes are atoms and edges are chemical bonds. As the molecules in both datasets have similar types of atoms and bond configurations (e.g., ring structures), TopER captures these similarities, leading to similar embeddings.

### 5.5 Ablation Study

In an ablation study, we evaluate the individual performance of each function as well as their combined effect on classification. As shown in Table 6, the common filtration functions we employ from TDA exhibit strong individual performance. Moreover, when combined, they synergistically enhance overall performance.

**Table 6: Ablation Study. Individual and altogether performances of filtration functions with TopER.**
| Datasets | Degree-cent. | Popularity | Closeness | Degree | F. Ricci | O. Ricci | Atom weight | TopER |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| BZR | 82.22$\pm$2.13 | 82.20$\pm$3.42 | 81.48$\pm$1.99 | 82.73$\pm$2.12 | 80.75$\pm$1.73 | 80.99$\pm$1.48 | 82.23$\pm$2.12 | 90.13$\pm$4.14 |
| COX2 | 75.38$\pm$3.96 | 69.21$\pm$8.19 | 67.90$\pm$7.96 | 73.88$\pm$5.02 | 70.46$\pm$7.28 | 73.03$\pm$4.21 | 69.82$\pm$8.27 | 82.01$\pm$4.59 |
| MUTAG | 76.61$\pm$7.87 | 77.66$\pm$6.12 | 80.88$\pm$4.79 | 74.97$\pm$6.40 | 80.85$\pm$9.25 | 82.46$\pm$7.84 | 73.45$\pm$8.01 | 90.99$\pm$6.64 |
| PROTEINS | 67.66$\pm$3.16 | 70.71$\pm$4.41 | 69.01$\pm$4.24 | 69.01$\pm$3.48 | 72.96$\pm$3.47 | 71.25$\pm$2.66 | 73.59$\pm$3.33 | 74.58$\pm$3.92 |
| IMDB-B | 73.00$\pm$4.49 | 71.90$\pm$3.48 | 72.60$\pm$4.20 | 73.10$\pm$4.18 | 69.80$\pm$2.44 | 66.40$\pm$3.35 | - | 73.20$\pm$3.43 |
| IMDB-M | 48.47$\pm$3.90 | 47.87$\pm$3.07 | 48.33$\pm$3.49 | 47.93$\pm$2.88 | 48.13$\pm$4.11 | 43.60$\pm$3.17 | - | 50.00$\pm$4.02 |
| REDDIT-B | 76.70$\pm$3.69 | 79.35$\pm$3.46 | 78.10$\pm$3.23 | 79.55$\pm$2.20 | 72.35$\pm$2.91 | 68.20$\pm$2.28 | - | 92.70$\pm$2.38 |
| REDDIT-5K | 42.85$\pm$1.74 | 50.87$\pm$2.63 | 50.03$\pm$1.49 | 47.01$\pm$1.89 | 50.27$\pm$1.92 | 45.81$\pm$2.08 | - | 56.51$\pm$2.22 |

## 6 Conclusion

We have introduced a novel graph embedding method, TopER, leveraging Persistent Homology from Topological Data Analysis. TopER demonstrates strong performance in graph classification tasks, rivaling SOTA models. Furthermore, it naturally generates effective 2D visualizations of graph datasets, facilitating the identification of clusters and outliers.
For future research, one promising direction is to extend TopER to temporal graph learning tasks, enabling the capture of dynamic graph trajectories that reflect evolving user behaviors over time. Another avenue worth exploring is the integration of TopER embeddings into graph foundation models, where the homogenization of graph structures could enhance the learning of transferable representations across different domains.

## Appendix A Further Experimental Details

### A.1 Hyperparameters

Our proposed MLP algorithm is constructed with a single hidden layer. The output layer’s activation function is set to log softmax, and the loss function we used is Negative Log Likelihood Loss. The learning rate is chosen between 0.01 and 0.001. Subsequently, we investigate the impact of the number of neurons in the hidden layer, considering values from the set {16, 64, 128}, the optimizer is set to be Adam, and the number of epochs is 500. To prevent large weights and overfitting, we apply L2 regularization coefficients of 1e-3, 1e-4. The activation function for the hidden layer varies between relu, gelu, and elu. Lastly, we consider the cases of adding or not a batch normalization layer to the output of the hidden layer and set dropout values to be 0.0 or 0.5.

**Table 7: Employed hyperparameters for each dataset.**
| Dataset | Neurons | Dropout | Batch Norm. | Decay | Learning rate | Activation |
| --- | --- | --- | --- | --- | --- | --- |
| BZR | 64 | 0.5 | True | 1e-4 | 0.001 | gelu |
| COX2 | 128 | 0 | True | 1e-4 | 0.01 | relu |
| MUTAG | 16 | 0.5 | False | 1e-3 | 0.01 | gelu |
| PROTEINS | 64 | 0.5 | True | 1e-3 | 0.01 | elu |
| IMDB-B | 128 | 0 | False | 1e-3 | 0.001 | relu |
| IMDB-M | 16 | 0 | False | 1e-3 | 0.01 | elu |
| REDDIT-B | 64 | 0.5 | False | 1e-3 | 0.01 | relu |
| REDDIT-5K | 128 | 0 | False | 1e-3 | 0.01 | elu |

### A.2 OGBG-MOLHIV Results

For OGBG-MOLHIV dataset, we further evaluated the improvements of TopER with addition of new filtration functions.
Table 8 provides the performance of each TopER$-i$, where $i$ represents number of filtration functions used in the model, i.e., TopER-$i$ uses $\{(a_{1},b_{1},\dots,a_{i},b_{i})\}$ as graph embedding where $(a_{i},b_{i})$ is the pivot and growth for function $f_{i}$. We used XGBoost to rank the importance of filtration functions first, and the functions are added iteratively with this ranking.
We fixed maximum tree depth $=3$, learning rates $=0.035$, subsample ratios $=0.95$, the number of estimators = 1000, and the regularization parameter lambda $=45$, where the objective function is rank:pairwise, with log loss as the evaluation metric. The seed is set to be $16$.

**Table 8: Results for OGBG-MOLHIV of each TopER$-i$.**
| Method | Added Function | Filtration | Valid. AUC | Test AUC |
| --- | --- | --- | --- | --- |
| TopER-1 | degree-centrality | sublevel | 72.76$\pm$0.23 | 74.44$\pm$0.20 |
| TopER-2 | atomic weight | sublevel | 71.89$\pm$0.12 | 74.25$\pm$0.16 |
| TopER-3 | Ollivier Ricci | sublevel | 70.11$\pm$0.28 | 76.79$\pm$0.24 |
| TopER-4 | Forman Ricci | superlevel | 71.76$\pm$0.18 | 78.15$\pm$0.15 |
| TopER-5 | degree | superlevel | 71.79$\pm$0.35 | 79.26$\pm$0.14 |
| TopER-6 | popularity | superlevel | 72.27$\pm$0.29 | 79.88$\pm$0.24 |
| TopER-7 | closeness | sublevel | 71.30$\pm$0.18 | 80.21$\pm$0.15 |

### A.3 Clustering Performances

In Table 9, we showcase our clustering performance across eight benchmark graph classification datasets using three widely adopted clustering metrics: Silhouette, Calinski-Harabasz, and Davies-Bouldin. These metrics serve as evaluative measures for assessing the efficacy of clustering algorithms in partitioning datasets into meaningful clusters. They gauge the degree of similarity or dissimilarity within and between clusters, offering insights into the quality of clustering outcomes. For precise definitions of Silhouette, Calinski-Harabasz, and Davies-Bouldin metrics, as well as additional details on clustering measures, refer to Gagolewski et al., ().

**Table 9: The clustering performances of Spectral Embeddings and TopER with different metrics. Best performances are given in blue.**
| Silhouette Scores ($\uparrow$) |  |  |  |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Method | BZR | COX2 | MUTAG | PROT. | IMDB-B | IMDB-M | REDD-B | REDD-5K |
| Spec Zoo | 0.050 | 0.049 | 0.344 | 0.050 | 0.097 | -0.024 | 0.108 | -0.121 |
| degree | -0.108 | 0.414 | 0.258 | 0.048 | 0.030 | -0.032 | 0.049 | -0.169 |
| popularity | 0.249 | -0.015 | 0.134 | -0.000 | 0.008 | -0.159 | 0.196 | -0.173 |
| closeness | 0.019 | 0.036 | 0.036 | 0.086 | nan | nan | 0.087 | -0.185 |
| degree | 0.084 | 0.030 | 0.017 | 0.065 | 0.056 | -0.075 | 0.034 | -0.067 |

## Appendix B More on TopER

### B.1 Refining the point set

While we have described the main steps of TopER in Section 4, due to the repetitions of the points in $\mathcal{A}=\{(x_{i},y_{i})\}\subset\mathbb{R}^{2}$, there are some choices to be made before defining the set $\mathcal{A}$ (i.e., $\mathcal{X}$ and $\mathcal{Y}$) to get the best fitting function $L:\mathcal{X}\to\mathcal{Y}$. The main reason is that the set $\{(x_{i},y_{i})\}_{i=1}^{N}$ can contain repetitions of $x$-values ($x_{i}=x_{i+1}$), repetitions of $y$-values ($y_{i}=y_{i+1}$) or repetitions of both ($(x_{i},y_{i})=(x_{i+1},y_{i+1})$) depending on the filtration function, the threshold set $\mathcal{I}$, and the graph $\mathcal{G}$.

For the filtrations induced by node filtration functions, the number of edges can not change unless the number of nodes changes, i.e., $x_{i}=x_{i+1}\Rightarrow y_{i}=y_{i+1}$. Hence, with this elimination, we still allow keeping $y$-values the same while $x$-values are increasing. This means there can be horizontal jumps in $\mathcal{A}_{u}$. In this paper, to eliminate all horizontal jumps for filtrations with node functions, we eliminate all repetitions of $y$-values from $\mathcal{A}_{u}$. AIn particular, we remove all the points with the same $\widehat{y}$-value and add a point with a mean of $x$-values. In other words, if $y_{i}=y_{i+1}=\dots=y_{i+k}=\widehat{y}$,
we define $\widehat{x}=\mbox{mean}\{x_{i},x_{i+1},\dots,x_{i+k}\}$. Then, we replace (k+1) points $\{(x_{i},\widehat{y}),(x_{i+1},\widehat{y}),\dots,(x_{i+k},\widehat{y})\}$ with one point $(\widehat{x},\widehat{y})$ in $\mathcal{A}_{u}$. This process eliminates all repetitions and horizontal jumps in $\mathcal{A}$, and we define our best-fitting line on this refined set.

### B.2 TopER with Alternative Quantities

While we use the most general quantities for a graph—the count of vertices and edges—in our algorithm, depending on the problem, there might be other induced quantities $(x_{i},y_{i})$ for a given subgraph $\mathcal{G}_{i}$ which can give better vectors.
To keep the line-fitting approach meaningful in our model, as long as the sequences $\{x_{i}\}$ and $\{y_{i}\}$ are monotone like our node-edge counts above,
for a given dataset in a domain (e.g., biochemistry, finance), one can use other domain-related quantities induced by substructure $\mathcal{G}_{i}$ as $(x_{i},y_{i})$ pair to obtain a TopER vector.

### B.3 Linear or Higher Order Fitting

In our experiments, we observe that linear fitting captures the growth information for node-edge pair $\{(x_{i},y_{i})\}$ well (See Figure 6), and quadratic fit and linear fit stays very close to each other. However, if one decides to use other quantities as described above and loses the monotonicity of the sequences $\{x_{i}\}$ and $\{y_{i}\}$, trying higher order fits (e.g., $y=ax^{2}+bx+c$) can be more meaningful.

Figure: (a)
Refer to caption: x8.png

### B.4 Interpreting TopER

Our approach involves accurately modeling the evolution of a graph throughout the filtration process.
One can easily identify clusters for each class and outliers in the other datasets given in Figure 1(a) and make inferences about the different clusters and outliers. Furthermore, when the pivot $a_{f}$ is positive or negative, it can be interpreted as graph density behavior in the filtration sequence (See Figure 7).

Figure: Figure 7: Pivot Behavior. A graph can exhibit three distinct pivot behaviors. Positive pivot graphs display a cluster of vertices that are closely interconnected and appear early in the filtration process. On the other hand, negative pivot graphs feature loosely connected nodes where the edges enter the filtration at a later stage. Graphs with zero pivot are usually quasi-complete graphs.
Refer to caption: extracted/5897538/figures/discerntypes.png

## Appendix C Proofs of Stability Theorems

In this part, we prove the stability results for our TopER.

###### Lemma 1 .

Skraba and Turner, () Let $\mathcal{X}$ be a compact metric space, and $f,g:\mathcal{X}\to\mathbb{R}$ be two filtration functions. Then, for any $p\geq 1$, we have
$\mathcal{W}_{p}(\rm{PD}_{k}(\mathcal{X},f),\rm{PD}_{k}(\mathcal{X},g))\leq\|f-
g\|_{p}$

The next lemma is on the stability of Betti curves by Dłotko and Gurnari, () [Proposition 1].

###### Lemma 2 .

Dłotko and Gurnari, () Let $\beta_{k}(\mathcal{X})$ is the $k^{th}$ Betti function obtained from the persistence module $\rm{PM}_{k}(\mathcal{X})$.

$$ $\|\beta_{k}(\mathcal{X})-\beta_{k}(\mathcal{Y})\|_{1}\leq 2\mathcal{W}_{1}(\rm {PD}_{k}(\mathcal{X}),\rm{PD}_{k}(\mathcal{Y}))$ $$

Now, we are ready to prove our stability result.

###### Theorem 2 .

Let $\mathcal{X}$ be a compact metric space, and $f,g:\mathcal{X}\to\mathbb{R}$ be two filtration functions. Then, for some $C>0$,

$$ $\|\rm{TE}_{f}(\mathcal{X})-\rm{TE}_{g}(\mathcal{X})\|_{1}\leq C\cdot\mathcal{W }_{1}(\rm{PD}_{k}(\mathcal{X},f),\rm{PD}_{k}(\mathcal{X},g))$ $$

###### Proof.

We will utilize the stability theorems from topological data analysis given above.

First, we employ the stability of Betti curves by Lemma 2.

$$ $\|\beta_{k}(\mathcal{X})-\beta_{k}(\mathcal{Y})\|_{1}\leq 2\mathcal{W}_{1}(\rm {PD}_{k}(\mathcal{X}),\rm{PD}_{k}(\mathcal{Y}))$ (1) $$

Hence to obtain $\rm{TE}_{f}(\mathcal{X})=(a_{f},b_{f})$, we fit least squares line $y=a_{f}+b_{f}x$ to the set of $N$ points in $\mathbb{R}^{2}$, i.e., $\mathcal{Z}_{f}=\{(\beta^{f}_{0}(\epsilon_{i}),\beta^{f}_{1}(\epsilon_{i}))\}_
{i=1}^{N}$. Similarly, we obtain $\rm{TE}_{g}(\mathcal{X})=(a_{g},b_{g})$ by fitting least squares line to $\mathcal{Z}_{g}=\{(\beta^{g}_{0}(\epsilon_{i}),\beta^{g}_{1}(\epsilon_{i}))\}_
{i=1}^{N}$.
By Equation 1, we have

$$ $\mathbf{D}_{H}(\mathcal{Z}_{f},\mathcal{Z}_{g})\leq 4\mathcal{W}_{1}(\rm{PD}_{ k}(\mathcal{X}),\rm{PD}_{k}(\mathcal{Y}))$ (2) $$

where $\mathbf{D}_{H}(\mathcal{Z}_{f},\mathcal{Z}_{g})$ represent Hausdorff distance between the point clouds $\mathcal{Z}_{f}$ and $\mathcal{Z}_{g}$ in $\mathbb{R}^{2}$.

Now, by the stability of least squares fit with respect to Hausdorff distance (Chernov et al., () [Theorem 3.1]), we have

$$ $\|\rm{TE}_{f}(\mathcal{X})-\rm{TE}_{g}(\mathcal{X})\|_{1}\leq C\cdot\mathbf{D} _{H}(\mathcal{Z}_{f},\mathcal{Z}_{g})$ (3) $$

Hence, when we combine Equations 2 and 3, we have

$$ $\|\rm{TE}_{f}(\mathcal{X})-\rm{TE}_{g}(\mathcal{X})\|_{1}\leq C\cdot\mathcal{W }_{1}(\rm{PD}_{k}(\mathcal{X}),\rm{PD}_{k}(\mathcal{Y}))$ $$

The proof follows.
∎

By combining the above result with Lemma 1, we obtain the following corollary.

###### Corollary 2 .

Let $\mathcal{X}$ be a compact metric space, and $f,g:\mathcal{X}\to\mathbb{R}$ be two filtration functions. Then, for some $C>0$,

$$ $\|\rm{TE}_{f}(\mathcal{X})-\rm{TE}_{g}(\mathcal{X})\|_{1}\leq C\cdot\|f-g\|_{1}$ $$

###### Proof.

By Lemma 1, we have

$$ $\mathcal{W}_{1}(\rm{PD}_{k}(\mathcal{X},f),\rm{PD}_{k}(\mathcal{X},g))\leq\|f- g\|_{1}$ (4) $$

By Theorem 2, we have

$$ $\|\rm{TE}_{f}(\mathcal{X})-\rm{TE}_{g}(\mathcal{X})\|_{1}\leq C\cdot\mathcal{W }_{1}(\rm{PD}_{k}(\mathcal{X},f),\rm{PD}_{k}(\mathcal{X},g))$ (5) $$

By combining Equations 4 and 5, we conclude

$$ $\|\rm{TE}_{f}(\mathcal{X})-\rm{TE}_{g}(\mathcal{X})\|_{1}\leq\widehat{C}\cdot \|f-g\|_{1}$ $$

The proof follows.
∎

###### Lemma 1 .

###### Lemma 2 .

###### Theorem 2 .

###### Proof.

###### Corollary 2 .

###### Proof.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: See from Paper Weaknesses.
soundness: 2
strengths: Innovative Approach: The paper introduces TopER, a novel method based on Topological Data Analysis (TDA) that simplifies Persistent Homology for graph embedding. By tracking the evolution rate of graph substructures, TopER provides a low-dimensional, interpretable graph representation, enabling it to capture graph structure effectively without high computational costs.
ss
Computational Efficiency: The limitations in computational efficiency are crucial since they directly impact the scalability of TopER for large real-world applications, a primary goal of embedding methods. Improving this area could make TopER more viable for large-scale datasets in practice.

Good Interpretability and Visualization: The two-dimensional embeddings produced by TopER offer strong interpretability, allowing users to easily identify clusters, outliers, and structural features within datasets. Unlike higher-dimensional embeddings, which are often challenging to interpret, TopER is well-suited for data exploration and graph visualization.
summary: This paper presents TopER, an innovative method for graph embedding based on topological data analysis (TDA). TopER introduces an efficient approach to graph representation learning by simplifying Persistent Homology, particularly in creating embeddings that capture the evolution of graph substructures. Instead of traditional graph neural network (GNN)-based methods, TopER focuses on generating interpretable, low-dimensional embeddings through filtration and linear regression on subgraph evolution rates. It shows competitive performance in clustering and classification tasks across various datasets, such as molecular and social networks, underscoring its utility for interpretable, scalable graph embeddings.
weaknesses: Lack of Threshold Setting Details: The paper does not explain how thresholds are set for different filtration functions, nor how the number of subgraphs n is determined. Since both threshold choice and n could impact results, further analysis would be valuable.

Clarity on Embedding Dimension: The paper lacks details on TopER’s final embedding dimension and does not directly compare it to the embedding dimensions of other algorithms. Embedding dimension is crucial for evaluating performance and computational efficiency, so specifying and comparing the dimensions of different methods would enhance the clarity and interpretability of the results.

Dataset-Specific Dimension Variability: Line 394 mentions "top-performing combinations of filtration and vectorization for each dataset," which suggests that embedding dimensions might vary across datasets. However, the paper does not clarify what these combinations are or discuss the impact of using different combinations across datasets, especially given the many possible configurations with the eight filtration functions.

Ablation Study Needs More Analysis: The ablation study does not analyze the effects of each filtration function on individual datasets, missing insights into how specific functions influence results across different types of data.

---

confidence: 3
contribution: 2
initial_rating: 6
presentation: 3
questions: See above weaknesses.
soundness: 3
strengths: - The paper is well-written with minimal typos and gives a good background of topological learning. 
- Experiments are mostly thorough and provide a comparison against different baselines, especially for graph classification. 
- The ability to train a shared interpretable embedding space of different graph datasets is interesting and has a lot of potential impact.
- The proposed method is computationally efficient and shows significant gains in performance.
summary: The paper presents a novel approach to train low-dimensional graph embeddings inspired by topological graph data analysis. Their method, Topological Evolution Rate (TopER), argues that the graph structure can be characterized by the linear function that relates how the number of edges relates to the number of nodes in the graphs induced by the nodes/edges that have a given value of a property such as degree. Through experiments, they show superior performance in graph classification, clustering, and interpretability. Furthermore, their method enables embedding different graph datasets in a shared embedding space, which is interesting.
weaknesses: - Motivation behind the method is lacking: The paper provides very little motivation behind the actual methodology. 
  - It is not clear what the correlation between the number of edges and number of nodes of the induced graphs wrt a filtration function has to do with how the graph is characterized/classified. 
  - It is not clearly stated why there should be a linear correlation between the two numbers. The motivating figures also do not motivate a linear correlation, except for MUTAG.
  - If there is a relation with persistence homology, then it should be discussed. 
- The method is limited to non-attributed graphs and cannot easily extend to attributed graphs, for which it might depend on other graph kernels to be devised.
- High sensitivity to filtration functions: As can be noted by the ablation study, the performance is highly sensitive to the filtration functions used for a particular dataset. This limits the strengths since it is not clear if the set of filtration functions considered in this work are even exhaustive. 
- Training an MLP on top of (a, b) of different filtration functions also limits the interpretability since the discriminative features may be formed as a combination of different filtration trends. Furthermore, using a single filtration function is always less performative than using multiple functions, which means the evolution rate of no one function is capable of classifying the graphs accurately. 
- A simpler comparison should be provided that compares persistent homology and TopER in their time complexity and graph classification accuracy assuming the same filtration function. 
- Hyperparameter analysis of the number of thresholds is missing. 
- Empirical comparison with some important baselines is not provided:
  - Immonen, Johanna, Amauri Souza, and Vikas Garg. "Going beyond persistent homology using persistent homology." Advances in Neural Information Processing Systems 36 (2024).
  - Hofer, Christoph, et al. "Graph filtration learning." International Conference on Machine Learning. PMLR, 2020.
  - Rieck, Bastian, Christian Bock, and Karsten Borgwardt. "A persistent weisfeiler-lehman procedure for graph classification." International Conference on Machine Learning. PMLR, 2019.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 2
questions: Can the authors clarify why combining these specific filtration functions enhances performance in ablation study?
soundness: 2
strengths: 1. TopER introduces a topologically grounded, low-dimensional embedding approach that efficiently captures graph substructure evolution, simplifying the computation-heavy process of Persistent Homology.

2. TopER provides clear, low-dimensional embeddings that highlight key topological features such as clusters and outliers, enhancing the ability to analyze individual and cross-dataset graphs.
summary: This paper presents Topological Evolution Rate (TopER), a novel low-dimensional embedding method based on topological data analysis for intuitive and interpretable graph representations. TopER achieves competitive performance in graph clustering and classification, with strong results across diverse datasets.
weaknesses: 1. The methodology briefly mentions alternatives to linear fitting, such as polynomial fits, but lacks detailed explanations. This omission raises questions about the impact of different fitting methods on the TopER vector and its adaptability to diverse graph types.
2. Although the linear regression on filtration sequences is computationally simpler than full Persistent Homology, the paper does not clarify how this process scales for large graphs with numerous filtration levels, making it uncertain whether the approach maintains efficiency for complex, high-dimensional data.
3. The ablation study shows that combining different filtration functions improves performance. However, it does not clearly explain how each function helps or why they work well together. This makes it hard to know which functions are truly needed and which may just add extra complexity without much benefit.

---

confidence: 4
contribution: 4
initial_rating: 8
presentation: 4
questions: 1. The `functions_to_calculate_[a,b]` folder in the anonymous repository appears to be empty. Could you explain why?
2. Is there a theoretical basis for the linear correlation between $a$ and $b$ ? How would the model performance when applying other fitting functions, such as polynomials?
soundness: 3
strengths: + A novel simple yet framework to represent graphs with persistence homology.
+ Compared with existing mainstream graph contrastive learning based method, the proposed TopER is parameter-free while achieving promising results.
+ Solid experiments and ablation studies on the proposed TopER.
+ The paper is well written and easy to follow.
summary: This paper focuses on characterizing graph topological structures with persistent homology methods. The proposed TopER rerpesents graphs with a sereis of graph filtrations and characterizes graphs with merely two parameters. Experimental results validate the effectiveness of the proposed TopER in generating self-supervised graph representations.
weaknesses: - The reason of adapting linear regression to fit the filtration sequences is mentioned in the Appendix, yet no theoretical or experimental support are provided.
- The key parts of TopER's implementation are missing from the provided repo link.
- The used filtration functions require further introduction and explanation.

Meta-review: This work introduces TopER, an approach to graph embedding that incorporates topological data analysis (TDA) principles to produce low-dimensional. By simplifying Persistent Homology and focusing on the evolution of graph substructures through filtration and linear regression, TopER demonstrates competitive performance in clustering and classification tasks across various datasets. The experimental results support the effectiveness of TopER in generating self-supervised graph representations, highlighting its ability to characterize graph topological structures using only two linear parameters (a and b).

However, I have concerns that this work may not be suited for a machine learning conference like ICLR. The method relies heavily on hand-designed components and very low dimensional representations, which limits its generality and adaptability to new tasks without heavy engineering. While the results look promising, the approach seems to be more of an application of existing TDA techniques to graph representation learning rather than a fundamental contribution to machine learning on graphs. I would like to see a stronger machine learning contribution, with more emphasis on learning-based approaches to the filtration, rather than relying solely on hand-designed features and linear regression.

Decision: Reject