A graph-matching formulation of the interleaving distance between merge trees

Matteo Pegoraro; Matteo Pegoraro

doi:10.3934/math.2025586

AIMS Mathematics

2025, Volume 10, Issue 6: 13025-13081. doi: 10.3934/math.2025586

Previous Article Next Article

Research article Special Issues

A graph-matching formulation of the interleaving distance between merge trees

Matteo Pegoraro ^,

Department of Mathematics, KTH, Stockholm, 10044, Sweden

Received: 07 March 2025 Revised: 28 April 2025 Accepted: 06 May 2025 Published: 06 June 2025
MSC : 05C05, 05C10, 55N31, 62R40

In this work, we studied the interleaving distance between merge trees from a combinatorial point of view. In the first part of the paper, we used a particular type of matching between trees to obtain a novel formulation of the distance. This formulation unveiled a link connecting the interleaving distance and edit distances between merge trees, which was of great interest due to the recursive decomposition properties and constrained formulations with polynomial time algorithms that these distances often enjoyed. In the second part of the paper, we built on this connection by applying tools from edit distances to obtain a constrained formulation of the interleaving distance and a recursive procedure which allowed us to find algorithms for upper and lower bounds of the interleaving distance. We implemented those algorithms and used them to test another upper bound presented by other authors, and tackled some simulations and case studies. Motivated by the literature on edit distances, we believe that our novel formulation could lead to novel heuristics to compute the interleaving distance and that applying our recursive scheme to the constrained interleaving distance would produce polynomial time upper bounds of practical relevance.
- topological data analysis,
- merge trees,
- interleaving distance,
- edit distance,
- binary optimization
Citation: Matteo Pegoraro. A graph-matching formulation of the interleaving distance between merge trees[J]. AIMS Mathematics, 2025, 10(6): 13025-13081. doi: 10.3934/math.2025586

Related Papers:

Abstract

In this work, we studied the interleaving distance between merge trees from a combinatorial point of view. In the first part of the paper, we used a particular type of matching between trees to obtain a novel formulation of the distance. This formulation unveiled a link connecting the interleaving distance and edit distances between merge trees, which was of great interest due to the recursive decomposition properties and constrained formulations with polynomial time algorithms that these distances often enjoyed. In the second part of the paper, we built on this connection by applying tools from edit distances to obtain a constrained formulation of the interleaving distance and a recursive procedure which allowed us to find algorithms for upper and lower bounds of the interleaving distance. We implemented those algorithms and used them to test another upper bound presented by other authors, and tackled some simulations and case studies. Motivated by the literature on edit distances, we believe that our novel formulation could lead to novel heuristics to compute the interleaving distance and that applying our recursive scheme to the constrained interleaving distance would produce polynomial time upper bounds of practical relevance.

References

[1]	H. Adams, J. Bush, N. Clause, F. Frick, M. Gómez, M. Harrison, et al., Gromov-hausdorff distances, borsuk-ulam theorems, and vietoris-rips complexes, (2022), arXiv: 2301.00246.
[2]	H. Adams, T. Emerson, M. Kirby, R. Neville, C. Peterson, P. Shipman, et al., Persistence images: A stable vector representation of persistent homology, J. Mach. Learn. Res., 18 (2017), 1–35.
[3]	P. K. Agarwal, K. Fox, A. Nath, A. Sidiropoulos, Y. S. Wang, Computing the gromov-hausdorff distance for metric trees, ACM T. Algorithms, 14 (2018), 20. https://doi.org/10.1145/3185466 doi: 10.1145/3185466
[4]	T. Akutsu, D. Fukagawa, A. Takasu, T. Tamura, Exact algorithms for computing the tree edit distance between unordered trees, Theor. Comput. Sci., 412 (2011), 352–364. https://doi.org/10.1016/j.tcs.2010.10.002 doi: 10.1016/j.tcs.2010.10.002
[5]	O. Al-Jowder, E. K. Kemsley, R. H. Wilson, Detection of adulteration in cooked meat products by mid-infrared spectroscopy, J. Agric. Food Chem., 50 (2002), 1325–1329. https://doi.org/10.1021/jf0108967 doi: 10.1021/jf0108967
[6]	M. Balasubramanian, E. L. Schwartz, The isomap algorithm and topological stability, Science, 295 (2002), 7. https://doi.org/10.1126/science.295.5552.7a doi: 10.1126/science.295.5552.7a
[7]	U. Bauer, C. Landi, F. Mémoli, The reeb graph edit distance is universal, Found. Comput. Math., 21 (2021), 1441–1464. https://doi.org/10.1007/s10208-020-09488-3 doi: 10.1007/s10208-020-09488-3
[8]	U. Bauer, E. Munch, Y. S. Wang, Strong Equivalence of the interleaving and functional distortion metrics for reeb graphs, 31st International Symposium on Computational Geometry (SoCG 2015), Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2015,461–475. https://doi.org/10.4230/LIPIcs.SOCG.2015.461
[9]	K. Beketayev, D. Yeliussizov, D. Morozov, G. H. Weber, B. Hamann, Measuring the distance between merge trees, In: Topological methods in data analysis and visualization III, Cham: Springer, 2014,151–165. https://doi.org/10.1007/978-3-319-04099-8_10
[10]	N. Berkouk, Algebraic homotopy interleaving distance, In: Geometric science of information, Cham: Springer, 2021,656–664. https://doi.org/10.1007/978-3-030-80209-7_70
[11]	H. B. Bjerkevik, M. B. Botnan, M. Kerber, Computing the interleaving distance is NP-hard, Found. Comput. Math., 20 (2020), 1237–1271. https://doi.org/10.1007/s10208-019-09442-y doi: 10.1007/s10208-019-09442-y
[12]	P. Bubenik, Statistical topological data analysis using persistence landscapes, J. Mach. Learn. Res., 16 (2015), 77–102.
[13]	R. Cardona, J. Curry, T. Lam, M. Lesnick, The universal $\ell^p$-metric on merge trees, 38th International Symposium on Computational Geometry (SoCG 2022), Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2022, 1–24. https://doi.org/10.4230/LIPIcs.SoCG.2022.24.
[14]	F. Chazal, D. Cohen-Steiner, M. Glisse, L. J. Guibas, S. Y. Oudot, Proximity of persistence modules and their diagrams, In: Proceedings of the twenty-fifth annual symposium on computational geometry, New York: Association for Computing Machinery, 2009,237–246. https://doi.org/10.1145/1542362.1542407
[15]	F. Chazal, B. T. Fasy, F. Lecci, A. Rinaldo, L. Wasserman, Stochastic convergence of persistence landscapes and silhouettes, J. Comput. Geom., 6 (2015), 140–161. https://doi.org/10.20382/jocg.v6i2a8 doi: 10.20382/jocg.v6i2a8
[16]	J. Curry, H. B. Hang, W. Mio, T. Needham, O. B. Okutan, Decorated merge trees for persistent topology, J. Appl. Comput. Topology, 6 (2022), 371–428. https://doi.org/10.1007/s41468-022-00089-3 doi: 10.1007/s41468-022-00089-3
[17]	J. Curry, W. Mio, T. Needham, O. B. Okutan, F. Russold, Convergence of leray cosheaves for decorated mapper graphs, (2023), arXiv: 2303.00130.
[18]	V. de Silva, E. Munch, A. Patel, Categorified reeb graphs, Discrete Comput. Geom., 55 (2016), 854–906. https://doi.org/10.1007/s00454-016-9763-9 doi: 10.1007/s00454-016-9763-9
[19]	V. de Silva, E. Munch, A. Stefanou, Theory of interleavings on categories with a flow, Theor. Appl. Categ., 33 (2018), 583–607.
[20]	B. Di Fabio, C. Landi, The edit distance for reeb graphs of surfaces, Discrete Comput. Geom., 55 (2016), 423–461. https://doi.org/10.1007/s00454-016-9758-6 doi: 10.1007/s00454-016-9758-6
[21]	H. Edelsbrunner, D. Letscher, A. Zomorodian, Topological persistence and simplification, Discrete Comput. Geom., 28 (2002), 511–533. https://doi.org/10.1007/s00454-002-2885-2 doi: 10.1007/s00454-002-2885-2
[22]	H. Edelsbrunner, J. Harer, Persistent homology–a survey, In: Surveys on discrete and computational geometry: twenty years later, Providence: American Mathematical Society, 2008,257–282. https://doi.org/10.1090/conm/453
[23]	Y. Elkin, V. Kurlin, The mergegram of a dendrogram and its stability, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020), Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2020, 1–13. https://doi.org/10.4230/LIPIcs.MFCS.2020.32
[24]	K. H. Esbensen, D. Guyot, F. Westad, L. P. Houmoller, Multivariate data analysis: in practice: An introduction to multivariate data analysis and experimental design, 5 Eds., AS: Camo Process, 2002.
[25]	E. F. Touli, Y. S. Wang, FPT-Algorithms for computing gromov-hausdorff and interleaving distances between trees, J. Comput. Geom., 13 (2022), 89–124. https://doi.org/10.20382/jocg.v13i1a4 doi: 10.20382/jocg.v13i1a4
[26]	M. Febrero, P. Galeano, W. González-Manteiga, Outlier detection in functional data by depth measures, with application to identify abnormal Nox levels, Environmetrics, 19 (2008), 331–345. https://doi.org/10.1002/env.878 doi: 10.1002/env.878
[27]	F. Ferraty, P. Vieu, Nonparametric functional data analysis: theory and practice, New York: Springer, 2006. https://doi.org/10.1007/0-387-36620-2
[28]	E. Gasparovic, E. Munch, S. Oudot, K. Turner, B. Wang, Y. S. Wang, Intrinsic interleaving distance for merge trees, La Matematica, 4 (2025), 40–65. https://doi.org/10.1007/s44007-024-00143-9 doi: 10.1007/s44007-024-00143-9
[29]	A. Hatcher, Algebraic topology, Cambrige: Cambridge University Press, 2001.
[30]	K. Hirata, Y. Yamamoto, T. Kuboyama, Improved max snp-hard results for finding an edit distance between unordered trees, In: Combinatorial pattern matching, Berlin: Springer, 2011,402–415. https://doi.org/10.1007/978-3-642-21458-5_34
[31]	E. Hong, Y. Kobayashi, A. Yamamoto, Improved methods for computing distances between unordered trees using integer programming, In: Combinatorial optimization and applications, Cham: Springer, 2017, 45–60. https://doi.org/10.1007/978-3-319-71147-8_4
[32]	T. Jiang, L. S. Wang, K. Z. Zhang, Alignment of trees–an alternative to tree edit, Theor. Comput. Sci., 143 (1995), 137–148. https://doi.org/10.1016/0304-3975(95)80029-9 doi: 10.1016/0304-3975(95)80029-9
[33]	L. Kanari, A. Garin, K. Hess, From trees to barcodes and back again: theoretical and statistical perspectives, Algorithms, 13 (2020), 335. https://doi.org/10.3390/a13120335 doi: 10.3390/a13120335
[34]	M. Lesnick, The theory of the interleaving distance on multidimensional persistence modules, Found. Comput. Math., 15 (2015), 613–650. https://doi.org/10.1007/s10208-015-9255-y doi: 10.1007/s10208-015-9255-y
[35]	S. M. Lane, Categories for the working mathematician, 2Eds., New York: Springer, 1998.
[36]	J. S. Marron, J. O. Ramsay, L. M. Sangalli, A. Srivastava, Functional data analysis of amplitude and phase variation, Statist. Sci., 30 (2015), 468–484. https://doi.org/10.1214/15-STS524 doi: 10.1214/15-STS524
[37]	J. W. Milnor, M. Spivak, R. Wells, Morse theory, Princeton: Princeton University Press, 1963. https://doi.org/10.1515/9781400881802
[38]	E. Munch, B. Wang, Convergence between categorical representations of Reeb space and mapper, In: 32nd International Symposium on Computational Geometry (SoCG 2016), Schloss Dagstuhl, Leibniz-Zentrum für Informatik, 2016, 1–16. https://doi.org/10.4230/LIPIcs.SoCG.2016.53
[39]	M. Pegoraro, A persistence-driven edit distance for graphs with abstract weights, (2024), arXiv: 2304.12088v3.
[40]	M. Pegoraro, A finitely stable edit distance for functions defined on merge trees, (2024), arXiv: 2108.13108.
[41]	M. Pegoraro, A finitely stable edit distance for merge trees, (2024), arXiv: 2111.02738.
[42]	M. Pegoraro, P. Secchi, Functional data representation with merge trees, (2024), arXiv: 2108.13147.
[43]	M. Pont, J. Vidal, J. Delon, J. Tierny, Wasserstein distances, geodesics and barycenters of merge trees, IEEE T. Vis. Comput. Gr., 28 (2021), 291–301. https://doi.org/10.1109/TVCG.2021.3114839 doi: 10.1109/TVCG.2021.3114839
[44]	C. R.-Carreño, J. L. Torrecilla, M. C. Berrocal, P. Manchón, A. Suárez, scikit-fda: A Python package for functional data analysis, J. Stat. Softw., 109 (2024), 1–37. https://doi.org/10.18637/jss.v109.i02 doi: 10.18637/jss.v109.i02
[45]	J. O. Ramsay, B. W. Silverman, Functional data analysis, In: International encyclopedia of the social and behavioral sciences, 2 Eds., New York: Springer, 2005,514–518. https://doi.org/10.1016/B978-0-08-097086-8.42046-5
[46]	S. M. Selkow, The tree-to-tree editing problem, Inform. Process. Lett., 6 (1977), 184–186. https://doi.org/10.1016/0020-0190(77)90064-3 doi: 10.1016/0020-0190(77)90064-3
[47]	P. Smith, V. Kurlin, Generic families of finite metric spaces with identical or trivial 1-dimensional persistence, J. Appl. Comput. Topology, 8 (2024), 839–855. https://doi.org/10.1007/s41468-024-00177-6 doi: 10.1007/s41468-024-00177-6
[48]	R. Sridharamurthy, T. B. Masood, A. Kamakshidasan, V. Natarajan, Edit distance between merge trees, IEEE T. Vis. Comput. Gr., 26 (2020), 1518–1531. https://doi.org/10.1109/TVCG.2018.2873612 doi: 10.1109/TVCG.2018.2873612
[49]	R. Sridharamurthy, V. Natarajan, Comparative analysis of merge trees using local tree edit distance, IEEE T. Vis. Comput. Gr., 29 (2021), 1518–1530. https://doi.org/10.1109/TVCG.2021.3122176 doi: 10.1109/TVCG.2021.3122176
[50]	R. D. Tuddenham, M. M. Snyder, Physical growth of California boys and girls from birth to eighteen years, Publ. Child. Dev. Univ. Calif., 1 (1954), 183–364.
[51]	L. M. Sangalli, P. Secchi, S. Vantini, V. Vitelli, Functional clustering and alignment methods with applications, Communications in Applied and Industrial Mathematics, 1 (2010), 205–224.
[52]	F. Wetzels, C. Garth, A deformation-based edit distance for merge trees, 2022 Topological Data Analysis and Visualization (TopoInVis), Oklahoma City, USA, 2022, 29–38. https://doi.org/10.1109/TopoInVis57755.2022.00010
[53]	F. Wetzels, H. Leitte, C. Garth, Branch decomposition-independent edit distances for merge trees, Comput. Graph. Forum, 41 (2022), 367–378. https://doi.org/10.1111/cgf.14547 doi: 10.1111/cgf.14547
[54]	K. Z. Zhang, A constrained edit distance between unordered labeled trees, Algorithmica, 15 (1996), 205–222. https://doi.org/10.1007/BF01975866 doi: 10.1007/BF01975866

Reader Comments

Your name:*

Email:*
© 2025 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)