×
Curry, Justin; Hang, Haibin; Mio, Washington; Needham, Tom; Okutan, Osman Berat

Decorated merge trees for persistent topology. (English) Zbl 1525.55006

J. Appl. Comput. Topol. 6, No. 3, 371-428 (2022).
In the present article the authors introduce a novel invariant for persistent spaces, i.e.spaces together with a fixed filtration which is considered part of the space’s data. The new invariant, called the decorated merge tree, combines information given by \(\pi_0\) and \(\operatorname{H}_n\) in a single mathematical object. The main new feature is that the decorated merge tree associates persistent homology classes to their corresponding persistent connected components in the given filtration. This allows for the distinction of persistent spaces with identical merge trees and barcodes.
The authors provide definitions and constructions for decorated merge trees in three slightly different mathematical settings: a first one adapted to category theory, a second one adapted to representation theory, and a third one adapted to barcodes.
1.
The categorical decorated merge tree is a persistent parametrized vector space which relies on parametrization by connected components of the persistent space at hand.
2.
The concrete decorated merge tree is a functor \((\mathcal{M}_F,\leq)\rightarrow \operatorname{Vect}\) which assigns to every element \(x\in (\mathcal{M}_F,\leq)\) of the usual merge tree \((\mathcal{M}_F,\leq)\) the vector space given by the \(n\)-th homology of the persistent connected component which corresponds to \(x\).
3.
Similarly, the barcode decorated merge tree assigns the corresponding \(n\)-th barcode to a persistent connected component corresponding to an element of \((\mathcal{M}_F,\leq)\).
After a general introduction in the first section and the mathematical introduction of the three different variants of decorated merge trees in the second section, the authors investigate the continuity and stability properties of decorated merge trees in the third section. In the fourth section, the authors give a criterion for when a decorated merge tree can be decomposed into a direct sum of decorated merge trees over a totally ordered index set. Sections five and six are about computational and algorithmic aspects of decorated merge trees and distances between them. The authors conclude the article with a summary of the results and a discussion of possible future directions in Section 7. The appendices provide more theoretical background and technical proofs which have been removed from the main body of the article.
Reviewer: Julian Brüggemann (Bonn)

Cited in 3 Documents

MSC:

55N31 Persistent homology and applications, topological data analysis

Keywords:

topological data analysis; persistent homology; merge trees; interleaving distance

Software:

Python; SciPy; SECT; Ripser; POT; Scikit-tda; Scikit; Gudhi; giotto-tda
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Agarwal, PK; Fox, K.; Nath, A.; Sidiropoulos, A.; Wang, Y., Computing the Gromov-Hausdorff distance for metric trees, ACM Trans. Algorithms (TALG), 14, 2, 1-20 (2018) · Zbl 1454.68174 · doi:10.1145/3185466
[2] Alvarez-Melis, D., Jegelka, S., Jaakkola, T.S.: Towards optimal transport with global invariances. In: The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1870-1879. PMLR (2019)
[3] Bainbridge, G.: Directional cellular sheaves for multicast network routing. In Preparation (2022)
[4] Bauer, U.: Ripser: efficient computation of vietoris-rips persistence barcodes (2019). Preprint · Zbl 1476.55012
[5] Bauer, U., Lesnick, M.: Persistence diagrams as diagrams: a categorification of the stability theorem. In: Topological Data Analysis, pp. 67-96. Springer (2020) · Zbl 1453.55004
[6] Blumberg, A.J., Lesnick, M.: Universality of the homotopy interleaving distance. arXiv preprint arXiv:1705.01690 (2017)
[7] Botnan, M.; Crawley-Boevey, W., Decomposition of persistence modules, Proc. Am. Math. Soc., 148, 11, 4581-4596 (2020) · Zbl 1461.16013 · doi:10.1090/proc/14790
[8] Bowditch, B.H.: Notes on Gromov’s hyperbolicity criterion for path-metric spaces. In: Group Theory From a Geometrical Viewpoint (1991) · Zbl 0843.20031
[9] Bubenik, P.; De Silva, V.; Scott, J., Metrics for generalized persistence modules, Found. Comput. Math., 15, 6, 1501-1531 (2015) · Zbl 1345.55006 · doi:10.1007/s10208-014-9229-5
[10] Bubenik, P.; Scott, JA, Categorification of persistent homology, Discret. Comput. Geom., 51, 3, 600-627 (2014) · Zbl 1295.55005 · doi:10.1007/s00454-014-9573-x
[11] Burago, D., Burago, I.D., Burago, Y., Ivanov, S., Ivanov, S.V., Ivanov, S.A.: A course in metric geometry, vol. 33. American Mathematical Society (2001) · Zbl 0981.51016
[12] Carlsson, G., Topological pattern recognition for point cloud data, Acta. Numer., 23, 289-368 (2014) · Zbl 1398.68615 · doi:10.1017/S0962492914000051
[13] Carlsson, G.; De Silva, V., Zigzag persistence, Found. Comput. Math., 10, 4, 367-405 (2010) · Zbl 1204.68242 · doi:10.1007/s10208-010-9066-0
[14] Carlsson, G.; Mémoli, F., Classifying clustering schemes, Found. Comput. Math., 13, 2, 221-252 (2013) · Zbl 1358.62057 · doi:10.1007/s10208-012-9141-9
[15] Chapel, L., Alaya, M.Z., Gasso, G.: Partial Gromov-Wasserstein with applications on positive-unlabeled learning. arXiv preprint arXiv:2002.08276 (2020)
[16] Chazal, F., Cohen-Steiner, D., Glisse, M., Guibas, L.J., Oudot, S.Y.: Proximity of persistence modules and their diagrams. In: Proceedings of the Twenty-fifth Annual Symposium on Computational Geometry, pp. 237-246 (2009) · Zbl 1380.68387
[17] Chowdhury, S., Mémoli, F.: The Gromov-Wasserstein distance between networks and stable network invariants. CoRR abs/1808.04337 (2018). arXiv:1808.04337 · Zbl 1471.62387
[18] Chowdhury, S., Needham, T.: Generalized spectral clustering via Gromov-Wasserstein learning. arXiv preprint arXiv:2006.04163 (2020)
[19] Chowdhury, S., Needham, T.: Gromov-wasserstein averaging in a riemannian framework. In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition Workshops, pp. 842-843 (2020)
[20] Clark, K.; Vendt, B.; Smith, K.; Freymann, J.; Kirby, J.; Koppel, P.; Moore, S.; Phillips, S.; Maffitt, D.; Pringle, M., The cancer imaging archive (tcia): maintaining and operating a public information repository, J. Digit. Imaging, 26, 6, 1045-1057 (2013) · doi:10.1007/s10278-013-9622-7
[21] Crawford, L.; Monod, A.; Chen, AX; Mukherjee, S.; Rabadán, R., Predicting clinical outcomes in glioblastoma: an application of topological and functional data analysis, J. Am. Stat. Assoc., 115, 531, 1139-1150 (2020) · Zbl 1441.62316 · doi:10.1080/01621459.2019.1671198
[22] Crawley-Boevey, W., Decomposition of pointwise finite-dimensional persistence modules, J. Algebr. Appl., 14, 5, 1550066 (2015) · Zbl 1345.16015 · doi:10.1142/S0219498815500668
[23] Curry, J., The fiber of the persistence map for functions on the interval, J. Appl. Comput. Topol., 2, 3-4, 301-321 (2018) · Zbl 1426.55006 · doi:10.1007/s41468-019-00024-z
[24] Curry, J., Mukherjee, S., Turner, K.: How many directions determine a shape and other sufficiency results for two topological transforms. arXiv preprint arXiv:1805.09782 (2018)
[25] Curry, JM, Topological data analysis and cosheaves, Jpn. J. Ind. Appl. Math., 32, 2, 333-371 (2015) · Zbl 1323.55002 · doi:10.1007/s13160-015-0173-9
[26] De Silva, V.; Munch, E.; Patel, A., Categorified reeb graphs, Discret. Comput. Geom., 55, 4, 854-906 (2016) · Zbl 1350.68271 · doi:10.1007/s00454-016-9763-9
[27] de Silva, V.; Munch, E.; Stefanou, A., Theory of interleavings on categories with a flow, Theory Appl. Categories, 33, 21, 583-607 (2018) · Zbl 1433.18002
[28] Dey, T.K., Shi, D., Wang, Y.: Comparing graphs via persistence distortion. In: 31st International Symposium on Computational Geometry (SoCG 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015) · Zbl 1378.05037
[29] Edelsbrunner, H., Letscher, D., Zomorodian, A.: Topological persistence and simplification. In: Proceedings 41st Annual Symposium on Foundations of Computer Science, pp. 454-463. IEEE (2000) · Zbl 1011.68152
[30] Emrani, S.; Gentimis, T.; Krim, H., Persistent homology of delay embeddings and its application to wheeze detection, IEEE Signal Process. Lett., 21, 4, 459-463 (2014) · doi:10.1109/LSP.2014.2305700
[31] Farahbakhsh Touli, E., Wang, Y.: FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees. In: 27th Annual European Symposium on Algorithms (ESA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019) · Zbl 1507.68322
[32] Flamary, R., Courty, N.: Pot python optimal transport library (2017). https://pythonot.github.io/
[33] Frosini, P.; Landi, C.; Mémoli, F., The persistent homotopy type distance, Homol. Homot. Appl., 21, 2, 231-259 (2019) · Zbl 1503.55003 · doi:10.4310/HHA.2019.v21.n2.a13
[34] Gasparovic, E., Munch, E., Oudot, S., Turner, K., Wang, B., Wang, Y.: Intrinsic interleaving distance for merge trees. arXiv preprint arXiv:1908.00063 (2019)
[35] Gromov, M.: Hyperbolic groups. In: Essays in group theory, pp. 75-263. Springer (1987) · Zbl 0634.20015
[36] Hajij, M., Munch, E., Rosen, P.: Graph similarity using pagerank and persistent homology. arXiv preprint arXiv:2002.05158 (2020)
[37] Hang, H.; Mémoli, F.; Mio, W., A topological study of functional data and fréchet functions of metric measure spaces, J. Appl. Comput. Topol., 3, 4, 359-380 (2019) · Zbl 1435.62449 · doi:10.1007/s41468-019-00037-8
[38] Hang, H., Mio, W.: Correspondence modules and persistence sheaves: a unifying framework for one-parameter persistent homology. arXiv preprint arXiv:2006.08557 (2020)
[39] Heine, C., Leitte, H., Hlawitschka, M., Iuricich, F., De Floriani, L., Scheuermann, G., Hagen, H., Garth, C.: A survey of topology-based methods in visualization. In: Computer Graphics Forum, vol. 35, pp. 643-667. Wiley Online Library (2016)
[40] Hendrikson, R., et al.: Using Gromov-Wasserstein distance to explore sets of networks. University of Tartu, Master Thesis 2 (2016)
[41] Hofer, C., Graf, F., Rieck, B., Niethammer, M., Kwitt, R.: Graph filtration learning. In: International Conference on Machine Learning, pp. 4314-4323. PMLR (2020)
[42] Hu, X., Li, F., Samaras, D., Chen, C.: Topology-preserving deep image segmentation. In: Wallach, H., Larochelle, H., Beygelzimer, A., Alché, F., Fox, E., Garnett, R. (eds.) Advances in neural information processing systems, vol. 32. Curran Associates, Inc. https://proceedings.neurips.cc/paper/2019/file/2d95666e2649fcfc6e3af75e09f5adb9-Paper.pdf (2019)
[43] Hu, X., Wang, Y., Fuxin, L., Samaras, D., Chen, C.: Topology-aware segmentation using discrete morse theory. In: International Conference on Learning Representations (2020)
[44] Kim, W., Memoli, F.: Generalized persistence diagrams for persistence modules over posets. arXiv preprint arXiv:1810.11517 (2018) · Zbl 1500.55004
[45] Landi, C.: The rank invariant stability via interleavings. In: Chambers, E.W., Terese, F.B., Lori, Z. (eds.) Research in computational topology, pp. 1-10. Springer International Publishing, Cham. doi:10.1007/978-3-319-89593-2_1 (2018) · Zbl 1432.55012
[46] Lesnick, M., The theory of the interleaving distance on multidimensional persistence modules, Found. Comput. Math., 15, 3, 613-650 (2015) · Zbl 1335.55006 · doi:10.1007/s10208-015-9255-y
[47] Lesnick, M., Wright, M.: Interactive visualization of 2-d persistence modules. arXiv preprint arXiv:1512.00180 (2015)
[48] Li, M., Palande, S., Wang, B.: Sketching merge trees. arXiv e-prints arXiv:2101 (2021)
[49] Mandell, M.A.: Cochains and homotopy type. Publications Mathématiques de l’IHÉS 103, 213-246 (2006). doi:10.1007/s10240-006-0037-6. http://www.numdam.org/item/PMIHES_2006__103__213_0/ · Zbl 1105.55003
[50] Martínez, DHD; Lee, CH; Kim, PT; Mio, W., Probing the geometry of data with diffusion fréchet functions, Appl. Comput. Harmon. Anal., 47, 3, 935-947 (2019) · Zbl 1441.62042 · doi:10.1016/j.acha.2018.01.003
[51] Mémoli, F.: On the use of Gromov-Hausdorff distances for shape comparison. The Eurographics Association (2007)
[52] Mémoli, F., Gromov-Wasserstein distances and the metric approach to object matching, Found. Comput. Math., 11, 4, 417-487 (2011) · Zbl 1244.68078 · doi:10.1007/s10208-011-9093-5
[53] Mémoli, F., Munk, A., Wan, Z., Weitkamp, C.: The ultrametric Gromov-Wasserstein distance. arXiv preprint arXiv:2101.05756 (2021)
[54] Mémoli, F., Okutan, O.B.: Metric graph approximations of geodesic spaces. arXiv preprint arXiv:1809.05566 (2018) · Zbl 1429.05197
[55] Mémoli, F., Smith, Z., Wan, Z.: Gromov-Hausdorff distances on \(p \)-metric spaces and ultrametric spaces. arXiv preprint arXiv:1912.00564 (2019)
[56] Morozov, D.; Beketayev, K.; Weber, G., Interleaving distance between merge trees, Discret. Comput. Geom., 49, 22-45 (2013) · Zbl 1272.68414 · doi:10.1007/s00454-012-9465-x
[57] Oudot, S., Solomon, E.: Barcode embeddings for metric graphs. arXiv preprint arXiv:1712.03630 (2017) · Zbl 1478.55003
[58] Oudot, S., Solomon, E.: Inverse problems in topological persistence. In: Topological Data Analysis, pp. 405-433. Springer (2020) · Zbl 1447.55006
[59] Patel, A., Generalized persistence diagrams, J. Appl. Comput. Topol., 1, 3, 397-419 (2018) · Zbl 1398.18015 · doi:10.1007/s41468-018-0012-6
[60] Pedregosa, F.; Varoquaux, G.; Gramfort, A.; Michel, V.; Thirion, B.; Grisel, O.; Blondel, M.; Prettenhofer, P.; Weiss, R.; Dubourg, V.; Vanderplas, J.; Passos, A.; Cournapeau, D.; Brucher, M.; Perrot, M.; Duchesnay, E., Scikit-learn: Machine learning in Python, J. Mach. Learn. Res., 12, 2825-2830 (2011) · Zbl 1280.68189
[61] Perea, JA; Harer, J., Sliding windows and persistence: An application of topological methods to signal analysis, Found. Comput. Math., 15, 3, 799-838 (2015) · Zbl 1325.37054 · doi:10.1007/s10208-014-9206-z
[62] Peyré, G., Cuturi, M., Solomon, J.: Gromov-wasserstein averaging of kernel and distance matrices. In: International Conference on Machine Learning, pp. 2664-2672 (2016)
[63] Reiss, A.; Indlekofer, I.; Schmidt, P.; Van Laerhoven, K., Deep ppg: large-scale heart rate estimation with convolutional neural networks, Sensors, 19, 14, 3079 (2019) · doi:10.3390/s19143079
[64] Riehl, E., Category theory in context (2017), New York: Courier Dover Publications, New York · Zbl 1348.18001
[65] Saul, N., Tralie, C.: Scikit-tda: Topological data analysis for python (2019). doi:10.5281/zenodo.2533369
[66] Scarpace, L.; Mikkelsen, L.; Cha, T.; Rao, S.; Tekchandani, S.; Gutman, S.; Pierce, D., Radiology data from the cancer genome atlas glioblastoma multiforme [tcga-gbm] collection, The Cancer Imaging Archive, 11, 4, 1 (2016)
[67] Smith, Z., Chowdhury, S., Mémoli, F.: Hierarchical representations of network data with optimal distortion bounds. In: 2016 50th Asilomar Conference on Signals, Systems and Computers, pp. 1834-1838. IEEE (2016)
[68] Stefanou, A.: Dynamics on categories and applications. Ph.D. Thesis (2018)
[69] Sturm, KT, On the geometry of metric measure spaces, Acta Math., 196, 1, 65-131 (2006) · Zbl 1105.53035 · doi:10.1007/s11511-006-0002-8
[70] Sturm, K.T.: The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. arXiv preprint arXiv:1208.0434 (2012)
[71] Takens, F.: Detecting strange attractors in turbulence. In: Dynamical Systems and Turbulence, Warwick 1980, pp. 366-381. Springer (1981) · Zbl 0513.58032
[72] Tauzin, G., Lupo, U., Tunstall, L., Pérez, J.B., Caorsi, M., Medina-Mardones, A., Dassatti, A., Hess, K.: giotto-tda: A topological data analysis toolkit for machine learning and data exploration. J. Mach. Learn. Res. 22, 39-1 (2021) · Zbl 1541.68324
[73] The GUDHI Project: GUDHI User and Reference Manual, 3.4.1 edn. GUDHI Editorial Board (2021). https://gudhi.inria.fr/doc/3.4.1/
[74] Turner, K.; Mukherjee, S.; Boyer, DM, Persistent homology transform for modeling shapes and surfaces, Inf. Inf. A J. IMA, 3, 4, 310-344 (2014) · Zbl 06840289
[75] Vayer, T.; Chapel, L.; Flamary, R.; Tavenard, R.; Courty, N., Fused Gromov-Wasserstein distance for structured objects, Algorithms, 13, 9, 212 (2020) · doi:10.3390/a13090212
[76] Venkataraman, V., Ramamurthy, K.N., Turaga, P.: Persistent homology of attractors for action recognition. In: 2016 IEEE International Conference on Image Processing (ICIP), pp. 4150-4154. IEEE (2016)
[77] Villani, C., Optimal Transport: Old and New (2008), Berlin: Springer, Berlin · Zbl 1156.53003
[78] Virtanen, P., Gommers, R., Oliphant, T.E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S.J., Brett, M., Wilson, J., Millman, K.J., Mayorov, N., Nelson, A.R.J., Jones, E., Kern, R., Larson, E., Carey, C.J., Polat, İ., Feng, Y., Moore, E.W., VanderPlas, J., Laxalde, D., Perktold, J., Cimrman, R., Henriksen, I., Quintero, E.A., Harris, C.R., Archibald, A.M., Ribeiro, A.H., Pedregosa, F., van Mulbregt, P., SciPy 1.0 Contributors: SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods 17, 261-272 (2020). doi: doi:10.1038/s41592-019-0686-2
[79] Xu, H., Luo, D., Carin, L.: Scalable Gromov-Wasserstein learning for graph partitioning and matching. In: Advances in Neural Information Processing Systems, pp. 3052-3062 (2019)
[80] Xu, H., Luo, D., Henao, R., Shah, S., Carin, L.: Learning autoencoders with relational regularization. arXiv preprint arXiv:2002.02913 (2020)
[81] Yan, L.; Masood, TB; Sridharamurthy, R.; Rasheed, F.; Natarajan, V.; Hotz, I.; Wang, B., Scalar field comparison with topological descriptors: properties and applications for scientific visualization, Comput. Graph. Forum, 40, 3, 599-633 (2021) · doi:10.1111/cgf.14331
[82] Yan, L.; Wang, Y.; Munch, E.; Gasparovic, E.; Wang, B., A structural average of labeled merge trees for uncertainty visualization, IEEE Trans. Visual Comput. Graphics, 26, 1, 832-842 (2019) · doi:10.1109/TVCG.2019.2934242
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.