Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2604.15265 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910136021286912 |
|---|---|
| author | Vila-Miñana, Meritxell Jankowski, Robert Marcús, Aina Ferrà Ballester, Rubén Serrano, M. Ángeles Casacuberta, Carles |
| author_facet | Vila-Miñana, Meritxell Jankowski, Robert Marcús, Aina Ferrà Ballester, Rubén Serrano, M. Ángeles Casacuberta, Carles |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_15265 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Motif-based filtrations for persistent homology: A framework for graph isomorphism and property prediction Vila-Miñana, Meritxell Jankowski, Robert Marcús, Aina Ferrà Ballester, Rubén Serrano, M. Ángeles Casacuberta, Carles Algebraic Topology Physics and Society 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. |
| title | Motif-based filtrations for persistent homology: A framework for graph isomorphism and property prediction |
| topic | Algebraic Topology Physics and Society |
| url | https://arxiv.org/abs/2604.15265 |