# Just SLaQ When You Approximate: Accurate Spectral Distances for Web-Scale Graphs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Mar 2020.

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

- [MOOMIN: Deep Molecular Omics Network for Anti-Cancer Drug Combination Therapy](https://mlsanity.com/paper/2110.15087/) (2021)
- [State of the Art and Potentialities of Graph-level Learning](https://mlsanity.com/paper/2301.05860/) (2023)
- [Computing Graph Descriptors on Edge Streams](https://mlsanity.com/paper/2109.01494/) (2021)
- [A Comparison of Graph Neural Networks for Malware Classification](https://mlsanity.com/paper/2303.12812/) (2023)
- [An Evolution Kernel Method for Graph Classification through Heat Diffusion Dynamics](https://mlsanity.com/paper/2306.14688/) (2023)
- [Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs](https://mlsanity.com/paper/2601.11159/) (2026)

## Abstract (arXiv)

Graph comparison is a fundamental operation in data mining and information retrieval. Due to the combinatorial nature of graphs, it is hard to balance the expressiveness of the similarity measure and its scalability. Spectral analysis provides quintessential tools for studying the multi-scale structure of graphs and is a well-suited foundation for reasoning about differences between graphs. However, computing full spectrum of large graphs is computationally prohibitive; thus, spectral graph comparison methods often rely on rough approximation techniques with weak error guarantees. In this work, we propose SLaQ, an efficient and effective approximation technique for computing spectral distances between graphs with billions of nodes and edges. We derive the corresponding error bounds and demonstrate that accurate computation is possible in time linear in the number of graph edges. In a thorough experimental evaluation, we show that SLaQ outperforms existing methods, oftentimes by several orders of magnitude in approximation accuracy, and maintains comparable performance, allowing to compare million-scale graphs in a matter of minutes on a single machine.