Persistent homology based Wasserstein distance for graph networks

Abstract

The technique of measuring similarity between topological spaces using Wasserstein distance between persistence diagrams is extended to graph networks in this paper. A relationship between the Wasserstein distance of the Cartesian product of topological spaces and the Wasserstein distance of individual spaces is found to ease the comparative study of the Cartesian product of topological spaces. The Cartesian product and the strong product of weighted graphs are defined, and the relationship between the Wasserstein distance between graph products and the Wasserstein distance between individual graphs is determined. For this, clique complex filtration and the Vietoris- Rips filtration are used.

Keywords

• persistent homology
• Wasserstein distance
• cartesian product of graphs
• strong product of graphs

References

1. [1] A. Adcock, E. Carlsson, and G. Carlsson, The ring of algebraic functions on persistence bar codes, arXiv preprint arXiv:1304.0530, 2013.
2. [2] M. E. Aktas, E. Akbas, and A. El Fatmaoui, Persistence homology of networks: methods and applications, Applied Network Science 4 (1), 1-28, 2019.
3. [3] L. Babai, Graph isomorphism in quasipolynomial time in: Proceedings of the fortyeighth annual acm symposium on theory of computing, 684-697, ACM, 2016.
4. [4] S. Benzekry, J. A. Tuszynski, E. A. Rietman, and G. L. Klement, Design principles for cancer therapy guided by changes in complexity of protein-protein interaction networks, Biology direct 10 (1), 1-14, 2015.
5. [5] S. Bhagat, G. Cormode, and S. Muthukrishnan, Node classification in social networks, arXiv preprint arXiv:1101.3291, 2011.
6. [6] J. Binchi, E. Merelli, M. Rucco, G. Petri, and F. Vaccarino, jholes: A tool for understanding biological complex networks via clique weight rank persistent homology, Electronic Notes in Theoretical Computer Science 306, 5-18, 2014.
7. [7] P. Bubenik and J. A. Scott, Categorification of persistent homology, Discrete Comput. Geom. 51 (3), 600-627, 2014.
8. [8] G. Carlsson, A. Zomorodian, A. Collins, and L. Guibas, Persistence barcodes for shapes, Proceedings of the 2004 eurographics/acm siggraph symposium on geometry processing, pp. 124-135, 2004.

9. [9] S. Chowdhury and F. M. Emoli, Persistent homology of directed networks, 2016 50th asilomar conference on signals, systems and computers, pp. 77-81, 2016.
10. [10] H. Edelsbrunner and J. L. Harer, Computational topology: an introduction, American Mathematical Society, 2022.
11. [11] H. Edelsbrunner, D. Letscher, and A. Zomorodian, Topological persistence and simplification, Proceedings 41st annual symposium on foundations of computer science, pp. 454-463, 2000.
12. [12] P. Frosini, A distance for similarity classes of submanifolds of a euclidean space, Bulletin of the Australian Mathematical Society 42 (3), 407-415, 1990.
13. [13] H. Gakhar and J. A. Perea, Künneth formulae in persistent homology, arXiv preprint arXiv:1910.05656, 2019.
14. [14] R. Ghrist, Barcodes: the persistent topology of data, Bulletin of the American Mathematical Society 45 (1), 61-75, 2008.
15. [15] R. Hammack, W. Imrich, and S. Klavzar, Handbook of product graphs, Second, Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2011. With a foreword by Peter Winkler.
16. [16] A. Hatcher, Algebraic topology, cambridge univ, Press, Cambridge, 2002.
17. [17] D. Horak, S. Maletic, and M. Rajkovic, Persistent homology of complex networks, Jour- nal of Statistical Mechanics: Theory and Experiment, 2009 (03), 2009, P03034.
18. [18] I. Knyazeva, A. Poyda, V. Orlov, V. Verkhlyutov, N. Makarenko, S. Kozlov, B. Velichkovsky and V. Ushakov, Resting state dynamic functional connectivity: Network topology analysis, Biologically Inspired Cognitive Architectures 23, 43-53, 2018.
19. [19] M. Li, K. Duncan, C. N. Topp, and D. H. Chitwood, Persistent homology and the branching topologies of plants, American journal of botany 104 (3), 349-353, 2017.
20. [20] G. R. Lopes, M. M. Moro, L. K. Wives, and J. P. M. De Oliveira, Collaboration recommendation on academic social networks, Advances in conceptual modelingapplications and challenges: Er 2010 workshops acm-l, cmlsa, cms, de@ er, fp-uml, secogis, wism, vancouver, bc, canada, november 1-4, 2010. proceedings 29, pp. 190-199, 2010.
21. [21] J. R. Munkres, Elements of algebraic topology, CRC press, 2018.
22. [22] A. R. Pears, Dimension theory of general spaces, Cambridge University Press, Cambridge, England-New York-Melbourne, 1975.
23. [23] V. Robins, Towards computing homology from finite approximations, Topology proceedings, pp. 503532, 1999.
24. [24] V. Salnikov, D. Cassese, R. Lambiotte, and N. S. Jones, Co-occurrence simplicial complexes in mathematics: identifying the holes of knowledge, Applied network science 3, 1-23, 2018.
25. [25] A. H. Wallace, An introduction to algebraic topology, Pergamon Press, New York- London, Paris, 1957.
26. [26] D. B. West, Introduction to graph theory, Vol. 2, Prentice hall Upper Saddle River, 2001.
27. [27] P. Zhang and G. Chartrand, Introduction to graph theory, Tata McGraw-Hill, 2006.