Skip to Content

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

Samples from two distributions
Left: The well-known Karate graph represents the social interactions of two martial arts clubs. Right: The spectral descriptors (NetLSD, VNGE, and Estrada Index) computed for the original graph in blue and the version with removed edges in red.

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.