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.

本文提出了一种有效的图谱比较方法 SLaQ，该方法使用谱分析技术计算大规模图结构的相似度，可在线性时间内获取误差较小的结果。实验结果表明 SLaQ 的精度比现有方法提高了数个数量级，且在单机上能够在几分钟内比较百万级别的图。