  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.
