pith. machine review for the scientific record. sign in

arxiv: 2604.15265 · v1 · submitted 2026-04-16 · 🧮 math.AT · physics.soc-ph

Recognition: unknown

Motif-based filtrations for persistent homology: A framework for graph isomorphism and property prediction

Aina Ferr\`a Marc\'us, Carles Casacuberta, M. \'Angeles Serrano, Meritxell Vila-Mi\~nana, Robert Jankowski, Rub\'en Ballester

Pith reviewed 2026-05-10 08:36 UTC · model grok-4.3

classification 🧮 math.AT physics.soc-ph
keywords filtrationsdatagraphsanalysisgraphnetworkchordlesscomputationally
0
0 comments X

The pith

Cycle-density filtrations based on motif densities enable persistent homology to distinguish non-isomorphic graphs nearly perfectly and achieve strong performance on real-world graph property prediction.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Persistent homology tracks how holes and other features in data persist as a scale parameter changes. Instead of using distances between points, this work builds filtrations by assigning weights to graph edges according to how many small cycles like triangles or squares contain that edge. The resulting persistence diagrams capture structural information that helps tell apart graphs that look similar due to symmetries. The same features also turn out to be useful for predicting properties of real networks such as social or molecular graphs.

Core claim

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.

Load-bearing premise

That weighting edges by densities of triangles, chordless squares, and chordless pentagons produces filtrations whose persistence diagrams are sufficiently discriminative for the tested isomorphism instances and property prediction tasks without requiring additional validation on broader graph classes.

Figures

Figures reproduced from arXiv: 2604.15265 by Aina Ferr\`a Marc\'us, Carles Casacuberta, M. \'Angeles Serrano, Meritxell Vila-Mi\~nana, Robert Jankowski, Rub\'en Ballester.

Figure 1
Figure 1. Figure 1: FIG. 1: Pipeline for the graph isomorphism problem. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: FIG. 2: Distribution of ranks for each filtration method [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: FIG. 3: Sensitivity of network filtrations across random graph models under edge removal (upper row) and edge [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

3 major / 2 minor

Summary. The paper proposes motif-based (cycle-density) filtrations for persistent homology on graphs, where edges are weighted by local densities of triangles, chordless 4-cycles, and chordless 5-cycles. It claims these filtrations yield persistence diagrams that distinguish non-isomorphic graphs perfectly or nearly perfectly across four demanding families (many with symmetries), outperforming curvature-based, degree-based, and Vietoris-Rips filtrations while matching or exceeding egonet-distance methods at lower cost. The same filtrations are reported to achieve top performance on real-world graph property prediction tasks and to be highly sensitive to edge rewiring and removal.

Significance. If the empirical results generalize beyond the four tested families, the framework would supply a computationally tractable topological method that injects motif information into graph filtrations, potentially useful for isomorphism testing and network characterization. The reported outperformance on selected isomorphism instances and property-prediction benchmarks constitutes a concrete empirical contribution, but the absence of theoretical injectivity guarantees or tests on standard hard instances (e.g., strongly regular graphs) keeps the significance at the level of a promising proof-of-concept rather than a general method.

major comments (3)
  1. [Experimental results on graph isomorphism] The isomorphism experiments report perfect or near-perfect separation on four families but neither identify those families against standard hard instances (strongly regular graphs, distance-regular graphs, or the nauty test suite) nor supply a proof that the motif-density map induces an injective function on isomorphism classes. This leaves open whether the observed discrimination is an artifact of the chosen examples.
  2. [Property prediction experiments] The manuscript supplies no details on exact datasets, baseline implementations, statistical tests, controls for post-hoc choices, or failure cases for the cycle-density filtrations, undermining the claim that they 'consistently achieve top performance' on property prediction.
  3. [Methods and discussion] No analysis is given of the (unspecified) cases in which the filtrations fail to separate graphs, nor is there an argument that the persistence diagrams are sufficiently discriminative without additional validation on broader graph classes.
minor comments (2)
  1. [Filtration construction] Notation for the three motif densities and the resulting edge-weight functions should be introduced with explicit formulas rather than descriptive prose only.
  2. [Figures] Figure captions for persistence diagrams should state the exact graph families and number of instances shown.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The work relies on established persistent homology theory and prior results on motif densities for network dimensionality; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • standard math Standard definitions and stability properties of persistent homology
    Invoked implicitly when using persistence diagrams to compare graphs.
  • domain assumption Effectiveness of triangle, square, and pentagon densities for capturing network structure
    Cited as previously shown for detecting network dimensionality.

pith-pipeline@v0.9.0 · 5564 in / 1265 out tokens · 29463 ms · 2026-05-10T08:36:56.889076+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

70 extracted references · 4 canonical work pages

  1. [1]

    is the best-performing distance in discriminating between different network topologies, outperforming all other methods, while for directed networks, DGCD-129

  2. [2]

    An alternative line of work focuses on egonet-based representations, which summarize local network struc- ture around each node

    led to an optimal performance. An alternative line of work focuses on egonet-based representations, which summarize local network struc- ture around each node. In [17], Piccardi proposed an alignment-free network comparison method based on dis- tributions of egonet features, including normalized de- gree, clustering coefficient, and egonet persistence. He...

  3. [3]

    Degree filtration (denoted bynD):v7→deg(v)

  4. [4]

    Filtration based on Ollivier–Ricci curvature [7] (de- noted byeO). We assign weight−1to nodes and κ(u, v) = 1−W 1(µα u, µα v ) to edges, whereW 1 denotes the first Wasserstein distance [43] andµ α u,µ α v are probability measures based on a lazy random walk in the graph: µα i (j) =    αifj=i, (1−α)/deg(i)ifi∼j, 0otherwise, whereαis as a smoothing par...

  5. [5]

    We setv7→ −1 and(u, v)7→4−deg(u)−deg(v) + 3|N(u)∩N(v)|, whereN(u)andN(v)denote the neighborhoods of uandv, respectively

    Filtration based on the augmented Forman–Ricci curvature [42] (denoted byeF). We setv7→ −1 and(u, v)7→4−deg(u)−deg(v) + 3|N(u)∩N(v)|, whereN(u)andN(v)denote the neighborhoods of uandv, respectively

  6. [6]

    Vietoris–Rips filtration (denoted bym V), where distance is given by the shortest-path length be- tween nodes [44]. This filtration is neither deter- mined by node weights nor by edge weights, but the parameter value associated with each simplex σin the Vietoris–Rips complex is the distance value at whichσappears

  7. [7]

    Filtration assigning to each edge the density of tri- angles (denoted byeT), computed by Eq. 1

  8. [8]

    Filtration assigning to each edge the density of chordless squares (denoted byeS)

  9. [9]

    Filtration assigning to each edge the density of chordless pentagons (denoted byeP)

  10. [10]

    Filtration assigning to each edge the sum of densi- ties of triangles, squares, and pentagons (denoted byeΣ)

  11. [11]

    2, wheredi andd j are the degrees of nodesiandj: R(eij) = 1p didj ,(2) 10

    Filtration assigning to each edge the Randić con- nectivity index [13] (denoted byeR), which is de- fined as shown in Eq. 2, wheredi andd j are the degrees of nodesiandj: R(eij) = 1p didj ,(2) 10

  12. [12]

    The harmonic index of a graphGis the sum of weights2/(du +d v)of all edges(u, v)ofG, whered u denotes the degree of a nodeuinG

    Filtration that assigns to each edge the weights used to compute the harmonic index [14] (denoted byeH). The harmonic index of a graphGis the sum of weights2/(du +d v)of all edges(u, v)ofG, whered u denotes the degree of a nodeuinG

  13. [13]

    Filtration that assigns to each edge a variant of the repulsion-attraction rule [15] (denoted byeA): RA(eij) = di +d j +d idj 1 +|N(i)∩N(j)| ,(3) whered i andd j denote the degrees of nodesiandj, and|N(i)∩N(j)|is the number of common neigh- bors between them

  14. [14]

    Filtration assigning to each edge its betweenness centrality [15] (denoted byeB). The betweenness centrality of an edgeeij is computed as cB(eij) = X s,t∈N σ(s, t|e ij) σ(s, t) ,(4) whereNis the set of nodes,σ(s, t)is the number of shortest paths betweensandt, andσ(s, t|e ij) is the number of those paths passing througheij

  15. [15]

    If T(v)is the number of triangles containing a node vandd v is the degree ofv, then the clustering coefficient [16] isC(v) = 2T(v)/(d v(dv −1))

    Clustering coefficient filtration (denoted bynC). If T(v)is the number of triangles containing a node vandd v is the degree ofv, then the clustering coefficient [16] isC(v) = 2T(v)/(d v(dv −1))

  16. [16]

    The egonetE i of nodeiis the subgraph on nodes {i} ∪N(i), whereN(i)is the set of neighbors ofi [17]. The egonet filtration (denoted bynE) as- signs to each node the egonet persistence, defined for undirected and unweighted networks by p(i) = P j∈Ei mint jP j∈Ei(mint j +m ext j ) ,(5) wherem int j andm ext j denote the internal and ex- ternal degrees ofjin...

  17. [17]

    real-world

    Graphlets [18] are small, connected, non-isomor- phic subgraphs. An orbit is a distinct node position withinagraphlet, defineduptoautomorphism. For each nodev, we compute its Graphlet Degree Vec- tor (GDV), whose entries count how many timesv participates in each orbit. The graphlet-based fil- tration (denoted bynG) assigns tovthe following score, whereii...

    work page doi:10.13039/501100011033 2025

  18. [18]

    Akutsu and H

    T. Akutsu and H. Nagamochi, Computational and struc- tural biotechnology journal5, e201302004 (2013)

    2013

  19. [19]

    Merkys, A

    A. Merkys, A. Vaitkus, A. Grybauskas, A. Konovalovas, M. Quirós, and S. Gražulis, Journal of cheminformatics 15, 25 (2023)

    2023

  20. [20]

    Sangkaran, A

    T. Sangkaran, A. Abdullah, N. JhanJhi, and M. Supra- maniam, International Journal of Computer Science and Network Security19, 85 (2019)

    2019

  21. [21]

    Ballester and B

    R. Ballester and B. Rieck, Proceedings of Machine Learn- ing Research269, 42:1 (2025), Third Learning on Graphs Conference, LoG 2024

    2025

  22. [22]

    Almagro, M

    P. Almagro, M. Boguñá, and M. A. Serrano, Nature Communications13, 6096 (2022)

    2022

  23. [23]

    A. F. Marcús, R. Jankowski, M. Vila-Miñana, C. Casacu- berta, and M. Serrano, Nature Communications (2026)

    2026

  24. [24]

    Ollivier, Comptes Rendus Mathematique345, 643 (2007)

    Y. Ollivier, Comptes Rendus Mathematique345, 643 (2007)

    2007

  25. [25]

    Y. Lin, L. Lu, and S.-T. Yau, Tohoku Math. J.63, 605 (2011)

    2011

  26. [26]

    Jost and S

    J. Jost and S. Liu, Discrete & Computational Geometry 51, 300 (2014)

    2014

  27. [27]

    R. P. Sreejith, K. Mohanraj, J. Jost, E. Saucan, and A. Samal, Journal of Statistical Mechanics: Theory and Experiment6, 063206 (2016)

    2016

  28. [28]

    Sandhu, T

    R. Sandhu, T. Georgiou, E. Reznik, L. Zhu, I. Kolesov, Y. Senbabaoglu, and A. Tannenbaum, Scientific Reports 14, 12323 (2015)

    2015

  29. [29]

    Fesser, S

    L. Fesser, S. Serrano de Haro Iváñez, K. Devriendt, M. Weber, and R. Lambiotte, Journal of Physics: Com- plexity5, 035010 (2024)

    2024

  30. [30]

    Randic, Journal of the American Chemical Society 97, 6609 (1975)

    M. Randic, Journal of the American Chemical Society 97, 6609 (1975)

    1975

  31. [31]

    Fajtlowicz, Congr

    S. Fajtlowicz, Congr. Numer.60, 187 (1987)

    1987

  32. [32]

    Muscoloni, J

    A. Muscoloni, J. M. Thomas, S. Ciucci, G. Bianconi, and C. V. Cannistraci, Nature Communications8, 1615 (2017)

    2017

  33. [33]

    D. J. Watts and S. H. Strogatz, Nature393, 440 (1998)

    1998

  34. [34]

    Piccardi, Scientific Reports13, 14657 (2023)

    C. Piccardi, Scientific Reports13, 14657 (2023)

    2023

  35. [35]

    Sarajlić, N

    A. Sarajlić, N. Malod-Dognin, Ö. N. Yaveroğlu, and N. Pržulj, Scientific Reports6, 35098 (2016)

    2016

  36. [36]

    Tantardini, F

    M. Tantardini, F. Ieva, L. Tajoli, and C. Piccardi, Scien- tific Reports9, 17557 (2019)

    2019

  37. [37]

    Hartle, B

    H. Hartle, B. Klein, S. McCabe, A. Daniels, G. St-Onge, C. Murphy, and L. Hébert-Dufresne, Proceedings of the Royal Society A476, 20190744 (2020)

    2020

  38. [38]

    Ö. N. Yaveroğlu, N. Malod-Dognin, D. Davis, Z. Lev- najic, V. Janjic, R. Karapandza, A. Stojmirovic, and N. Pržulj, Scientific Reports4, 4547 (2014)

    2014

  39. [39]

    Weisfeiler and A

    B. Weisfeiler and A. Leman, Nauchno-Technicheskaya In- formatsia9, 12 (1968)

    1968

  40. [40]

    Morris, M

    C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe, inProceedings of the AAAI Conference on Artificial Intelligence(2019), vol. 33, pp. 4602–4609

    2019

  41. [41]

    Molina-Abril, M

    H. Molina-Abril, M. Morón-Fernández, M. Benito- Marimón, F. Díaz-del Río, and P. Real, Applied Mathe- matics and Computation485, 128989 (2025)

    2025

  42. [42]

    Hajij, E

    M. Hajij, E. Munch, and P. Rosen, in2020 International Conference on Intelligent Data Science Technologies and Applications (IDSTA)(IEEE, 2020), pp. 110–114

    2020

  43. [43]

    Calissano and E

    A. Calissano and E. Lasalle, arXiv preprint arXiv:2512.24327 (2025)

    work page arXiv 2025

  44. [44]

    arXiv preprint arXiv:1812.09764 , year=

    B. Rieck, M. Togninalli, C. Bock, M. Moor, M. Horn, T. Gumbsch, and K. Borgwardt, arXiv preprint arXiv:1812.09764 (2018)

    work page arXiv 2018

  45. [45]

    Carrière, F

    M. Carrière, F. Chazal, Y. Ike, T. Lacombe, M. Royer, and Y. Umeda, inInternational Conference on Artificial Intelligence and Statistics(PMLR, 2020), pp. 2786–2796

    2020

  46. [46]

    A. Tola, F. M. Taiwo, C. G. Akcora, and B. Coskunuzer, arXiv preprint arXiv:2410.01778 (2024)

    work page arXiv 2024

  47. [47]

    McKay,Collection of strongly-regular graphs, URL https://users.cecs.anu.edu.au/~bdm/data/graphs

    B. McKay,Collection of strongly-regular graphs, URL https://users.cecs.anu.edu.au/~bdm/data/graphs. html

  48. [48]

    Wang and M

    Y. Wang and M. Zhang, inProceedings of the 41st International Conference on Machine Learning(2024), ICML’24

    2024

  49. [49]

    W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec, Advances in Neural Infor- mation Processing Systems33, 22118 (2020)

    2020

  50. [50]

    Adams, T

    H. Adams, T. Emerson, M. Kirby, R. Neville, C. Pe- terson, P. Shipman, S. Chepushtanova, E. Hanson, F. Motta, and L. Ziegelmeier, Journal of Machine Learn- ing Research18, 1 (2017)

    2017

  51. [51]

    Bause, F

    F. Bause, F. Jogl, P. Indri, T. Drucks, D. Penz, N. M. Kriege, T. Gärtner, P. Welke, and M. Thiessen, Transac- tions on Machine Learning Research (2025), ISSN 2835- 8856

    2025

  52. [52]

    Barabási and R

    A.-L. Barabási and R. Albert, science286, 509 (1999)

    1999

  53. [53]

    Erdős and A

    P. Erdős and A. Rényi, Publ. Math. Debrecen6, 18 (1959)

    1959

  54. [54]

    Morris, Y

    C. Morris, Y. Lipman, H. Maron, B. Rieck, N. M. Kriege, M.Grohe, M.Fey, andK.Borgwardt, JournalofMachine Learning Research24, 1 (2023)

    2023

  55. [55]

    P. A. Papp and R. Wattenhofer, inProceedings of the International Conference on Machine Learning (ICML) (PMLR, 2022), vol. 162 ofProceedings of Machine Learn- ing Research, pp. 17323–17345

    2022

  56. [56]

    N. H. May, B. Krishnamoorthy, and P. Gambill, La Matematica3, 1486 (2024)

    2024

  57. [57]

    Edelsbrunner and J

    H. Edelsbrunner and J. Harer,Computational Topology: An Introduction(American Mathematical Society, Prov- idence, RI, 2010), ISBN 978-0-8218-4925-5

    2010

  58. [58]

    T. K. Dey, T. Hou, and S. Parsa, inAlgorithms and Data Structures (WADS 2023)(Springer, Cham, 2023), vol. 14079 ofLecture Notes in Computer Science

    2023

  59. [59]

    Samal, R

    A. Samal, R. P. Sreejith, J. Gu, S. Liu, E. Saucan, and J. Jost, Scientific Reports8, 8650 (2018)

    2018

  60. [60]

    Y.Mileyko, S.Mukherjee, andJ.Harer, InverseProblems 27, 124007 (2011)

    2011

  61. [61]

    Adams and B

    H. Adams and B. Coskunuzer, SIAM Journal on Applied Algebra and Geometry6, 685 (2022)

    2022

  62. [62]

    Piccardi, PLoS ONE6, e27028 (2011)

    C. Piccardi, PLoS ONE6, e27028 (2011)

    2011

  63. [63]

    Brinkmann, K

    G. Brinkmann, K. Coolsaet, J. Goedgebeur, and H.Mélot, DiscreteAppliedMathematics161, 311(2013), ISSN 0166-218X

    2013

  64. [64]

    García-Marco and K

    I. García-Marco and K. Knauer, European Journal of Combinatorics125, 104108 (2025), ISSN 0195-6698

    2025

  65. [65]

    Coolsaet, S

    K. Coolsaet, S. D’hondt, and J. Goedgebeur, Discrete Applied Mathematics325, 97 (2023)

    2023

  66. [66]

    J.-Y. Cai, M. Fürer, and N. Immerman, Combinatorica 12, 389 (1992)

    1992

  67. [67]

    Motif-based filtrations for persistent homology: A framework for graph isomorphism and property prediction

    The GUDHI Project,GUDHI Library: Simplicial Com- plexes and Persistent Homology, GUDHI Project (2021), https://gudhi.inria.fr. Supplementary Information for “Motif-based filtrations for persistent homology: A framework for graph isomorphism and property prediction” Meritxell Vila-Miñana,1 Robert Jankowski,2, 3, 4 Aina Ferrà Marcús,5 Rubén Ballester,5 M. Á...

    2021

  68. [68]

    Wang and M

    Y. Wang and M. Zhang, inProceedings of the 41st International Conference on Machine Learning , ICML’24 (2024)

    2024

  69. [69]

    W. Hu, M. Fey, M. Zitnik, Y. Dong, H. Ren, B. Liu, M. Catasta, and J. Leskovec, Advances in Neural Information Processing Systems 33, 22118 (2020)

    2020

  70. [70]

    Ballester and B

    R. Ballester and B. Rieck, Proceedings of Machine Learning Research269, 42:1 (2025), Third Learning on Graphs Confer- ence, LoG 2024

    2025