Bridging the Gap between von Neumann Graph Entropy and Structural Information: Theory and Applications
Xuecheng Liu, Luoyi Fu, Xinbing Wang · 2021
The von Neumann graph entropy (VNGE) is a measure of graph complexity based on the Laplacian spectrum. It has recently found applications in various learning tasks driven by networked data. However, it is computationally demanding and hard to interpret using simple structural patterns. Due to the close relation between Lapalcian spectrum and degree sequence, we conjecture that the structural information, defined as the Shannon entropy of the normalized degree sequence, might approximate VNGE well.