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

arXiv: https://arxiv.org/abs/1805.11769 · HTML: https://mlsanity.com/paper/1805.11769/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 May 2018.

## Built on by (most cited first, 8 of 8)

- [Principle of Relevant Information for Graph Sparsification](https://mlsanity.com/paper/2206.00118/) (2022)
- [Self-organization Preserved Graph Structure Learning with Principle of Relevant Information](https://mlsanity.com/paper/2301.00015/) (2022)
- [State of the Art and Potentialities of Graph-level Learning](https://mlsanity.com/paper/2301.05860/) (2023)
- [Computing Graph Descriptors on Edge Streams](https://mlsanity.com/paper/2109.01494/) (2021)
- [Applications of Entropy in Data Analysis and Machine Learning: A Review](https://mlsanity.com/paper/2503.02921/) (2025)
- [The Maximum von Neumann Entropy Principle: Theory and Applications in Machine Learning](https://mlsanity.com/paper/2602.02117/) (2026)
- [Large Engagement Networks for Classifying Coordinated Campaigns and Organic Twitter Trends](https://mlsanity.com/paper/2503.00599/) (2025)
- [Ego-based Entropy Measures for Structural Representations on Graphs](https://mlsanity.com/paper/2102.08735/) (2021)

## Abstract (arXiv)

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.