Motif-based filtrations for persistent homology: A framework for graph isomorphism and property prediction
Meritxell Vila-Miñana, Robert Jankowski, Aina Ferrà Marcús, Rubén Ballester, M. Ángeles Serrano, Carles Casacuberta · 2026
Read Motif-based filtrations for persistent homology: A framework for graph isomorphism and property prediction by Meritxell Vila-Miñana, Robert Jankowski, Aina Ferrà Marcús, Rubén Ballester, M. Ángeles Serrano, Carles Casacuberta (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-15265.txt.
Introduction
Vila-Miñana and others test whether graphs are isomorphic using persistent homology over motif filtrations. Edge weights from triangle, chordless-square, and chordless-pentagon densities track shape features as filtrations evolve. Their cycle-density filtrations separate non-isomorphic graphs cleanly or nearly so across four hard families, many with symmetries. The method beats curvature- and degree-based rivals, giving a topological view of graph matching and property guesses, and it works well even where graphs mirror each other.
Catalog record
| CREATOR | Meritxell Vila-Miñana, Robert Jankowski, Aina Ferrà Marcús, Rubén Ballester, M. Ángeles Serrano, Carles Casacuberta |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52054 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.15265
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Motif-based filtrations for persistent homology: A framework for graph isomorphism and property prediction Meritxell Vila-Miñana, Robert Jankowski, Aina Ferrà Marcús, Rubén Ballester, M. Ángeles Serrano, Carles Casacuberta Abstract Determining whether two graphs are isomorphic is a fundamental problem with practical applications in areas such as molecular chemistry or social network analysis, yet it remains a challenging task, with exact solutions often being computationally expensive. We address this task using persistent homology built on motif-based filtrations of graphs, a method from topological data analysis that summarizes the shape of data by tracking the persistence of structural features along filtrations. Specifically, we use edge-weighting schemes based on the densities of triangles, chordless squares, and chordless pentagons, which have been shown to be effective for detecting network dimensionality. Our cycle-density filtrations distinguish non-isomorphic graphs perfectly or nearly perfectly across four demanding graph families, many of which exhibit symmetries. We outperform curvature-based, degree-based, and Vietoris–Rips filtrations, and match or exceed the accuracy of egonet-distance methods while incurring a lower computational cost. The expressive power of our filtrations goes beyond isomorphism testing: because they capture rich structural information from graphs, they consistently achieve top performance on property prediction tasks using real-world data, and exhibit high sensitivity to edge rewiring and removal. Together, these findings establish cycle-density filtrations as an effective and computationally tractable framework for graph comparison and characterization, bridging topological data analysis and network science. I Introduction Distinguishing whether two graphs are isomorphic is a fundamental problem with applications in different scientific domains. For instance, the verification of molecular structures and chemical compound descriptions emphasizes the need for efficient and expressive algorithms to test graph isomorphism 3 ; 27 . In biomedical research, graph isomorphism has been applied to analyze protein structures, and more broadly in social and biological networks for pattern recognition 41 . Recently, topology-based methods have emerged as a promising direction for graph comparison and isomorphism testing. In particular, persistent homology, a central tool in topological data analysis (TDA), provides descriptors capable of capturing structural properties of graphs. The effectiveness of persistent homology depends crucially on the choice of filtration, which determines how a graph is transformed into a sequence of nested graphs or higher-dimensional simplicial complexes that expose multiscale topological features of the underlying data. Despite growing interest in TDA, the impact of filtration design on the performance of several tasks, such as distinguishing non-isomorphic graphs, graph learning, or robustness to small perturbations, remains insufficiently understood 5 . In this work, we use persistent homology computed from filtrations based on the densities of chordless cycles to evaluate graph isomorphism and predict graph properties. Edge weightings based on chordless-cycle densities (triangles, squares, and pentagons) were introduced in 4 for latent dimensionality detection in complex networks, and were integrated with TDA techniques in 24 to further strengthen dimensionality detection capabilities. Densities of chordless cycles are related to Ollivier–Ricci curvature 33 , which is a discrete analog of Ricci curvature in Riemannian geometry. Positive curvature in a graph region is associated with a high density of triangles, while negative curvature is linked to increased densities of chordless longer cycles 23 ; 22 . Curvature defines local geometric invariants that are preserved under graph isometries, and has been shown to be effective for identifying community boundaries, i.e., edges separating densely connected regions, as well as for assessing the robustness and vulnerability of networks 43 ; 40 ; 22 ; 17 . Our results demonstrate that persistence descriptors computed from chordless-cycle densities are highly accurate in distinguishing non-isomorphic graphs, particularly in challenging datasets. In doing so, we extend the framework introduced in 5 to study the expressivity of persistent homology for graph learning by comparing several filtrations inspired by graph geometry and curvature. In addition to the filtrations considered in 5 (a degree-based filtration, filtrations based on the Ollivier–Ricci and augmented Forman–Ricci curvatures, and a Vietoris–Rips filtration defined by the shortest-path distance between nodes) we evaluate edge-based filtrations derived from density of triangles, density of chordless squares, density of chordless pentagons, and sum of densities of triangles, squares and pentagons 4 , as well as classical network measures such as the Randić connectivity index 37 , weights used to compute the harmonic index 16 and the repulsion-attraction rule 32 , betweenness centrality 32 , clustering coefficient 48 , egonet persistence 36 , and a graphlet-based filtration 42 . Beyond the graph isomorphism problem, we evaluate the performance of filtrations on real-world datasets using property prediction tasks, where the goal is to predict structural characteristics of graphs directly from their persistent homology features. In particular, we consider global and local network descriptors, including average clustering coefficient, average shortest-path length, degree statistics, and centrality measures. This setting allows us to assess how well persistent homology captures meaningful structural information beyond its ability to distinguish non-isomorphic graphs. We also analyze the sensitivity of filtrations to small perturbations of graphs, such as rewiring and edge removal. Across benchmark datasets, our motif-based filtrations consistently outperform filtrations based on degree, curvature, and centrality measures in distinguishing non-isomorphic graphs, including strongly regular graphs where standard methods fail. Similarly, our filtrations achieve the highest performance in property prediction and sensitivity analyses, using both synthetic and real data. I.1 Related Work Graph isomorphism is closely related to the broader problem of network comparison, where the goal is quantifying similarity between graphs. In 44 and 20 , several network comparison measures were studied. While checking whether two finite graphs are isomorphic is a complex task, they addressed the question on whether two real-world networks are similar. Comparing networks requires an inexact graph matching framework, namely the definition of a real-valued distance that converges to zero as the networks become increasingly close to being isomorphic. A wide variety of network comparison methods and algorithms were proposed in 20 , which presented a review of several approaches to network comparison. Among these, the best state-of-the-art techniques involve graphlet-based methods. Graphlets are small connected induced subgraphs, typically restricted to at most five nodes to limit computational complexity. Advanced graphlet-based methods account for automorphism orbits, thereby distinguishing the structural roles of nodes within each graphlet. Empirical evaluations in 44 show that, for undirected networks, the Graphlet Correlation Distance GCD-11 50 is the best-performing distance in discriminating between different network topologies, outperforming all other methods, while for directed networks, DGCD-129 42 led to an optimal performance. An alternative line of work focuses on egonet-based representations, which summarize local network structure around each node. In 36 , Piccardi proposed an alignment-free network comparison method based on distributions of egonet features, including normalized degree, clustering coefficient, and egonet persistence. He suggested taking the statistics of these three indicators in different combinations to define a distribution function in 1, 2, or 3 dimensions, as a synthesis of network properties. Similarly to graphlet-based techniques, the local graph structure around each node was summarized by a vector of features, which was used as a global descriptor of the network. Yet, the features used in 36 are simpler and enable rapid computation. The results of their experiments show that ego-distances perform comparably to the best graphlet-based distance (GCD-11) with similar computational requirements. A central tool for graph isomorphism detection is the Weisfeiler–Leman algorithm 49 , whose