# Efficient Sparsification of Simplicial Complexes via Local Densities of States

arXiv: https://arxiv.org/abs/2502.07558 · HTML: https://mlsanity.com/paper/2502.07558/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 43 references that are in the map.
- First posted on arXiv 11 Feb 2025.

## Builds on (most cited first, 21 of 21)

- [Networks beyond pairwise interactions: structure and dynamics](https://mlsanity.com/paper/2006.01764/) (2020)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [Simplicial Neural Networks](https://mlsanity.com/paper/2010.03633/) (2020)
- [Topological Signal Processing over Simplicial Complexes](https://mlsanity.com/paper/1907.11577/) (2019)
- [Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian](https://mlsanity.com/paper/1807.05044/) (2018)
- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [Principled Simplicial Neural Networks for Trajectory Prediction](https://mlsanity.com/paper/2102.10058/) (2021)
- [What are higher-order networks?](https://mlsanity.com/paper/2104.11329/) (2021)
- [Hutch++: Optimal Stochastic Trace Estimation](https://mlsanity.com/paper/2010.09649/) (2020)
- [Simplicial Convolutional Neural Networks](https://mlsanity.com/paper/2110.02585/) (2021)
- [Approximate Gaussian Elimination for Laplacians: Fast, Sparse, and Simple](https://mlsanity.com/paper/1605.02353/) (2016)
- [Demystifying Graph Sparsification Algorithms in Graph Properties Preservation](https://mlsanity.com/paper/2311.12314/) (2023)
- [Network Density of States](https://mlsanity.com/paper/1905.09758/) (2019)
- [Signal processing on simplicial complexes](https://mlsanity.com/paper/2106.07471/) (2021)
- [Spectral Sparsification of Hypergraphs](https://mlsanity.com/paper/1807.04974/) (2018)
- [A Notion of Harmonic Clustering in Simplicial Complexes](https://mlsanity.com/paper/1910.07247/) (2019)
- [Point-Level Topological Representation Learning on Point Clouds](https://mlsanity.com/paper/2406.02300/) (2024)
- [A Simple, Combinatorial Algorithm for Solving SDD Systems in Nearly-Linear Time](https://mlsanity.com/paper/1301.6628/) (2013)
- [Cholesky-like Preconditioner for Hodge Laplacians via Heavy Collapsible Subcomplex](https://mlsanity.com/paper/2401.15492/) (2024)
- [Topological Trajectory Classification and Landmark Inference on Simplicial Complexes](https://mlsanity.com/paper/2412.03145/) (2024)

## Abstract (arXiv)

Simplicial complexes (SCs) have become a popular abstraction for analyzing complex data using tools from topological data analysis or topological signal processing. However, the analysis of many real-world datasets often leads to dense SCs, with many higher-order simplicies, which results in prohibitive computational requirements in terms of time and memory consumption. The sparsification of such complexes is thus of broad interest, i.e., the approximation of an original SC with a sparser surrogate SC (with typically only a log-linear number of simplices) that maintains the spectrum of the original SC as closely as possible. In this work, we develop a novel method for a probabilistic sparsification of SCs that uses so-called local densities of states. Using this local densities of states, we can efficiently approximate so-called generalized effective resistance of each simplex, which is proportional to the required sampling probability for the sparsification of the SC. To avoid degenerate structures in the spectrum of the corresponding Hodge Laplacian operators, we suggest a ``kernel-ignoring'' decomposition to approximate the sampling probability. Additionally, we utilize certain error estimates to characterize the asymptotic algorithmic complexity of the developed method. We demonstrate the performance of our framework on a family of Vietoris--Rips filtered simplicial complexes.