The von Neumann graph entropy (VNGE) facilitates the measure of information divergence and distance between graphs in a graph sequence and has successfully been applied to various network learning tasks. Albeit its effectiveness, it is computationally demanding by requiring the full eigenspectrum of the graph Laplacian matrix. In this paper, we propose a Fast Incremental von Neumann Graph EntRopy (FINGER) framework, which approaches VNGE with a performance guarantee. FINGER reduces the cubic complexity of VNGE to linear complexity in the number of nodes and edges, and thus enables online computation based on incremental graph changes. We also show asymptotic consistency of FINGER to the exact VNGE, and derive its approximation error bounds. Based on FINGER, we propose ultra-efficient algorithms for computing Jensen-Shannon distance between graphs. Our experimental results on different random graph models demonstrate the computational efficiency and the asymptotic consistency of FINGER. In addition, we also apply FINGER to two real-world applications and one synthesized dataset, and corroborate its superior performance over seven baseline graph similarity methods.

本文提出基于 FINGER 方法的数据流图相似性度量算法，通过优化时间复杂度解决 von Neumann 图熵计算的问题，并在实验中验证了其卓越性能。

快速增量 Von Neumann 图熵计算：理论、算法和应用