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

paper · pdf · Google AI blog · code
TL;DR
SLaQ is a new technique to approximate spectral quantities of very large graphs:
- Fast — \( O(m) \) in the number of edges of the graph
- Extendable — works with any positive definite function of the graph
Spectral analysis provides quintessential tools for studying the multi-scale structure of graphs. However, computing full spectrum of large graphs is computationally prohibitive. 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.