Title: Spectral Sparsification of Simplicial Complexes for Clustering and Label Propagation,
Abstract: As a generalization of the use of graphs to describe pairwise interactions,
simplicial complexes can be used to model higher-order interactions between
three or more objects in complex systems. There has been a recent surge in
activity for the development of data analysis methods applicable to simplicial
complexes, including techniques based on computational topology, higher-order
random processes, generalized Cheeger inequalities, isoperimetric inequalities,
and spectral methods. In particular, spectral learning methods (e.g. label
propagation and clustering) that directly operate on simplicial complexes
represent a new direction for analyzing such complex datasets.
To apply spectral learning methods to massive datasets modeled as simplicial
complexes, we develop a method for sparsifying simplicial complexes that
preserves the spectrum of the associated Laplacian matrices. We show that the
theory of Spielman and Srivastava for the sparsification of graphs extends to
simplicial complexes via the up Laplacian. In particular, we introduce a
generalized effective resistance for simplices, provide an algorithm for
sparsifying simplicial complexes at a fixed dimension, and give a specific
version of the generalized Cheeger inequality for weighted simplicial
complexes. Finally, we introduce higher-order generalizations of spectral
clustering and label propagation for simplicial complexes and demonstrate via
experiments the utility of the proposed spectral sparsification method for
these applications.