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.

Key Insights:

Filtration-based summary — simple, fast, and highly scalable graph embeddings
TopER gives 2D pivot-growth representations that are directly interpretable
Achieves best per second-best accuracy on multiple datasets
Outperforms persistent homology methods on both accuracy and runtime
Multiple filtration functions (degree, closeness, Ricci, etc.) improve robustness
Produces strong clustering quality and clear cross-dataset visual patterns

TopER Python Package

TopER is available as a Python package and can be installed directly using:

    pip install toper

More information, examples, and source code can be found in the TopER repository.

Preliminaries

A graph \( G = (V, E) \) consists of nodes \( V \) and edges \( E \).

A filtration is a nested sequence of subgraphs:

\( G_1 \subseteq G_2 \subseteq \cdots \subseteq G_n = G \)

Filtrations are constructed using:

Node functions \( f: V \rightarrow \mathbb{R} \), such as degree, closeness, heat kernel signatures, or domain-specific attributes (e.g., atom types).
Edge functions \( g: E \rightarrow \mathbb{R} \), such as weights or curvature measures.

A sublevel filtration adds nodes or edges of increasing function value:

\( V_i = \{v \in V \mid f(v) \leq \epsilon_i\} \)
\( E_i = \{(u,v) \in E \mid \max(f(u), f(v)) \leq \epsilon_i\} \)

where \( \mathcal{T} = \{\epsilon_1, \ldots\} \).

TopER

TopER is a topology-inspired method for understanding graph evolution via filtration.

Motivations:

Standard graph embeddings are high-dimensional and mainly for dataset-level visualization.
Low-dimensional graph-level embeddings are largely missing.
Persistent Homology is expressive but produces complex, hard-to-read outputs.

TopER Scatter Plots for PROTEINS and BZR

TopER Pipeline

Filtration Sequences

Given a graph G = (V, E), we first construct a nested sequence of subgraphs: G₁ ⊆ G₂ ⊆ ... ⊆ Gₙ = G using a chosen filtration function, such as degree, closeness, or an edge-based function. For each filtration graph Gᵢ, we record:

xᵢ = |V|: number of nodes
yᵢ = |E|: number of edges

This yields two monotone sequences x = {x₁, x₂, ..., xₙ} and y = {y₁, y₂, ..., yₙ}, which describe how the graph grows across filtration thresholds t = {t₁, t₂, ...}.

Evolution via Line Fitting

In traditional PH, the next step would compute topological features for each Gᵢ and vectorize persistence. TopER instead examines how nodes and edges accumulate relative to nodes across the filtration.

We fit a line to the filtration pairs {(xᵢ, yᵢ)} ∈ ℝ² using simple linear regression:

L(x) = a + b·x

The regression minimizes the squared error:

E = Σᵢ (L(xᵢ) - yᵢ)²

resulting in coefficients (a, b) that summarize the graph’s structural evolution.

Results

We applied degree, closeness, degree centrality, and popularity as node filtration functions and Forman- and Ollivier-Ricci functions as edge filtration functions. We also used atomic weight as a node function for BZR, COX2, and MUTAG, and node attributes for PROTEINS.

To increase the performance, we remove correlated functions by using the t-test to assess statistical significance and the Lasso for model regularization, with the cross-validation parameter cv=10. Functions are kept in the model if the p-values from the t-test are less than 0.05 and the related Lasso coefficients are non-zero.

Graph Classification

Clustering Performance

We evaluate graph embeddings using three clustering metrics: Silhouette, Calinski-Harabasz, and Davies-Bouldin, and find that TopER embeddings show superior clustering compared to those generated by Spectral Zoo.