Skip to yearly menu bar Skip to main content


Fast Incremental von Neumann Graph Entropy Computation: Theory, Algorithm, and Applications

Pin-Yu Chen · Lingfei Wu · Sijia Liu · Indika Rajapakse

Pacific Ballroom #265

Keywords: [ Unsupervised Learning ] [ Others ] [ Other Applications ] [ Networks and Relational Learning ] [ Computational Biology and Genomics ]


The von Neumann graph entropy (VNGE) facilitates measurement of information divergence and distance between graphs in a graph sequence. It has been successfully applied to various learning tasks driven by network-based data. While effective, VNGE is computationally demanding as it requires the full eigenspectrum of the graph Laplacian matrix. In this paper, we propose a new computational framework, Fast Incremental von Neumann Graph EntRopy (FINGER), 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 equivalence of FINGER to the exact VNGE, and derive its approximation error bounds. Based on FINGER, we propose efficient algorithms for computing Jensen-Shannon distance between graphs. Our experimental results on different random graph models demonstrate the computational efficiency and the asymptotic equivalence of FINGER. In addition, we apply FINGER to two real-world applications and one synthesized anomaly detection dataset, and corroborate its superior performance over seven baseline graph similarity methods.

Live content is unavailable. Log in and register to view live content