Spectral density approximation methods for sparse graphs: A review

Graphs provide a simple yet powerful abstraction for representing complex systems across diverse domains, including social networks, biology, economics, and technology. In these models, vertices represent entities, and edges represent the interactions between them. The spectral density (i.e., the empirical distribution of the eigenvalues of a matrix representation of a graph) captures key global structural and dynamical properties. It supports a wide range of tasks, including community detection, denoising, spectral clustering, and graph comparison. However, the exact computation of the spectral density scales cubically with the number of vertices, making it impractical for large, sparse graphs. To address this, numerous approximation methods have been developed that trade accuracy for efficiency. In this review, we comprehensively examine existing techniques for approximating spectral densities in large, sparse graphs, encompassing both classical and recent developments. We also provide an open-source Python library that implements all reviewed methods, available at https://github.com/fujita-team/fastSpectralDensity .