Fast Incremental von Neumann Graph Entropy Computation: Theory, Algorithm, and Applications
arXiv:1805.11769
Abstract
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.
arXiv commentPublished at ICML 2019
References in corpus (12)
- Emergence of scaling in random networks
- Semi-Supervised Classification with Graph Convolutional Networks
- The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
- Variational Graph Auto-Encoders
- Layer aggregation and reducibility of multilayer interconnected networks
- Entropy measures for complex networks: Toward an information theory of complex topologies
- Spectra and eigenvectors of scale-free networks
- Properties of Classical and Quantum Jensen-Shannon Divergence
- LanczosNet: Multi-Scale Deep Graph Convolutional Networks
- Graph2Seq: Graph to Sequence Learning with Attention-based Neural Networks
- The Shannon and the Von Neumann entropy of random networks with heterogeneous expected degree
- D2KE: From Distance to Kernel and Embedding