# Network Density of States

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 May 2019.

## Built on by (most cited first, 13 of 13)

- [A Unifying Generative Model for Graph Learning Algorithms: Label Propagation, Graph Convolutions, and Combinations](https://mlsanity.com/paper/2101.07730/) (2021)
- [Diffusion Earth Mover's Distance and Distribution Embeddings](https://mlsanity.com/paper/2102.12833/) (2021)
- [Enhancing Supply Chain Visibility with Knowledge Graphs and Large Language Models](https://mlsanity.com/paper/2408.07705/) (2024)
- [Laplacian Change Point Detection for Single and Multi-view Dynamic Graphs](https://mlsanity.com/paper/2302.01204/) (2023)
- [Fast Attributed Graph Embedding via Density of States](https://mlsanity.com/paper/2110.05228/) (2021)
- [Sharper Bounds for Chebyshev Moment Matching, with Applications](https://mlsanity.com/paper/2408.12385/) (2024)
- [What Do LLMs Need to Understand Graphs: A Survey of Parametric Representation of Graphs](https://mlsanity.com/paper/2410.12126/) (2024)
- [Moments, Random Walks, and Limits for Spectrum Approximation](https://mlsanity.com/paper/2307.00474/) (2023)
- [Faster Spectral Density Estimation and Sparsification in the Nuclear Norm](https://mlsanity.com/paper/2406.07521/) (2024)
- [Hallucination Detox: Sensitivity Dropout (SenD) for Large Language Model Training](https://mlsanity.com/paper/2410.15460/) (2024)
- [Fast and Attributed Change Detection on Dynamic Graphs with Density of States](https://mlsanity.com/paper/2305.08750/) (2023)
- [T3former: Temporal Graph Classification with Topological Machine Learning](https://mlsanity.com/paper/2510.13789/) (2025)
- [Efficient Sparsification of Simplicial Complexes via Local Densities of States](https://mlsanity.com/paper/2502.07558/) (2025)

## Abstract (arXiv)

Spectral analysis connects graph structure to the eigenvalues and eigenvectors of associated matrices. Much of spectral graph theory descends directly from spectral geometry, the study of differentiable manifolds through the spectra of associated differential operators. But the translation from spectral geometry to spectral graph theory has largely focused on results involving only a few extreme eigenvalues and their associated eigenvalues. Unlike in geometry, the study of graphs through the overall distribution of eigenvalues - the spectral density - is largely limited to simple random graph models. The interior of the spectrum of real-world graphs remains largely unexplored, difficult to compute and to interpret. In this paper, we delve into the heart of spectral densities of real-world graphs. We borrow tools developed in condensed matter physics, and add novel adaptations to handle the spectral signatures of common graph motifs. The resulting methods are highly efficient, as we illustrate by computing spectral densities for graphs with over a billion edges on a single compute node. Beyond providing visually compelling fingerprints of graphs, we show how the estimation of spectral densities facilitates the computation of many common centrality measures, and use spectral densities to estimate meaningful information about graph structure that cannot be inferred from the extremal eigenpairs alone.