The decomposition of the higher-order homology embedding constructed from the k-Laplacian
Yu-Chia Chen and Marina Meilă
arXiv (to appear at NeurIPS 2021 Oral), 2021
Abstract
The null space of the $k$-th order Laplacian $\mathbf{\mathcal L}_k$, known as the $k$-th homology vector space, encodes the non-trivial topology of a manifold or a network. Understanding the structure of the homology embedding can thus disclose geometric or topological information from the data. The study of the null space embedding of the graph Laplacian $\mathbf{\mathcal L}_0$ has spurred new research and applications, such as spectral clustering algorithms with theoretical guarantees and estimators of the Stochastic Block Model. In this work, we investigate the geometry of the $k$-th homology embedding and focus on cases reminiscent of spectral clustering. Namely, we analyze the connected sum of manifolds as a perturbation to the direct sum of their homology embeddings. We propose an algorithm to factorize the homology embedding into subspaces corresponding to a manifold’s simplest topological components. The proposed framework is applied to the shortest homologous loop detection problem, a problem known to be NP-hard in general. Our spectral loop detection algorithm scales better than existing methods and is effective on diverse data such as point clouds and images.
Extra materials
Bibtex
Recommended citation
Yu-Chia Chen and Marina Meilă. The decomposition of the higher-order homology embedding constructed from the k-Laplacian. arXiv:2107.10970 [stat.ML], July 2021. (To appear at NeurIPS 2021 as an oral presentation.)