Fast Topological Clustering with Wasserstein Distance
arXiv:2112.00101
Abstract
The topological patterns exhibited by many real-world networks motivate the development of topology-based methods for assessing the similarity of networks. However, extracting topological structure is difficult, especially for large and dense networks whose node degrees range over multiple orders of magnitude. In this paper, we propose a novel and computationally practical topological clustering method that clusters complex networks with intricate topology using principled theory from persistent homology and optimal transport. Such networks are aggregated into clusters through a centroid-based clustering strategy based on both their topological and geometric structure, preserving correspondence between nodes in different networks. The notions of topological proximity and centroid are characterized using a novel and efficient approach to computation of the Wasserstein distance and barycenter for persistence barcodes associated with connected components and cycles. The proposed method is demonstrated to be effective using both simulated networks and measured functional brain networks.
arXiv commentPublished at the 10th International Conference on Learning Representations (ICLR 2022); 18 pages, 10 figures
References in corpus (13)
- Modularity and community structure in networks
- The architecture of complex weighted networks
- Statistical Mechanics of Community Detection
- A roadmap for the computation of persistent homology
- Fast Computation of Wasserstein Barycenters
- A Topological Loss Function for Deep-Learning based Image Segmentation using Persistent Homology
- Persistent homology analysis of protein structure, flexibility and folding
- Topology-Preserving Deep Image Segmentation
- A Fast Proximal Point Method for Computing Exact Wasserstein Distance
- Principal Component Analysis of Persistent Homology Rank Functions with case studies of Spatial Point Patterns, Sphere Packing and Colloids
- Progressive Wasserstein Barycenters of Persistence Diagrams
- Large Scale computation of Means and Clusters for Persistence Diagrams using Optimal Transport
- Continuous Regularized Wasserstein Barycenters