Persistent Laplacians: properties, algorithms and implications
share
The combinatorial graph Laplacian has been a fundamental object in the analysis of and optimization on graphs. Its spectral structure has been widely used in graph optimization problems (e.g, clustering), and it is also connected to network circuit theory. There is also a topological view of the graph Laplacian, which permits the extension of the graph Laplacian to the more general q-th combinatorial Laplacian Δ_q^K for a simplicial complex K. In this way, the standard graph Laplacian is simply the 0-th case (when q=0) of this family of operators. Taking this topological view, Wang et al. introduced the so-called persistent Laplacian Δ_q^K,L, which is an extension of the combinatorial Laplacian to a pair of simplicial complexes K ↪ L. In this paper, we present a thorough study of properties and algorithms for persistent Laplacians. We first prove that the nullity of Δ_q^K,L gives rise to the q-th persistent Betti number from K to L. We then present a first algorithm to compute the matrix representation of Δ_q^K,L, which helps reveal insights into the meaning of persistent Laplacian. We next show a new relation between the persistent Laplacian and the so-called Schur complement of a matrix. This has several interesting implications. For example, in the graph case, this uncovers a relation with the notion of effective resistance, as well as a persistent version of the Cheeger inequality. This also gives a second, very simple algorithm to compute the q-th persistent Laplacian. This in turn leads to a new algorithm to compute the q-th persistent Betti number for a pair of spaces which can be significantly more efficient than existing algorithms under some conditions. Finally, we also study persistent Laplacians for a filtration of simplicial complexes, and present interesting stability results for their eigenvalues.
READ FULL TEXT