On the Similarity between von Neumann Graph Entropy and Structural Information: Interpretation, Computation, and Applications

Xuecheng Liu, Luoyi Fu, Xinbing Wang, Chenghu Zhou

Introduction

Measuring the structural complexity of a network is a fundamental task in fields ranging from anomaly detection to network design. The von Neumann graph entropy ($H_{vn}$), derived from the Laplacian spectrum, has long been considered the gold standard for capturing multi-scale structural richness. However, $H_{vn}$ suffers from two significant drawbacks: it is computationally prohibitive for large-scale networks (requiring $O(n^3)$ eigenvalue decomposition) and lacks intuitive geometric interpretability.

This paper addresses these challenges by formalizing the relationship between $H_{vn}$ and structural information ($H_1$), which is defined as the Shannon entropy of a graph's normalized degree sequence. The authors prove that $H_1$ serves as a highly accurate, scalable, and interpretable proxy for $H_{vn}$, enabling near-instantaneous complexity analysis for massive graphs.

Theoretical Framework: Bridging Spectral and Combinatorial Entropy

The core contribution of this work is the theoretical bridge between spectral graph theory and information theory. Using Majorization Theory, the authors demonstrate that the degree sequence of an undirected graph is majorized by its Laplacian spectrum.

Comparison of Laplacian spectrum and degree sequence across various graph models and real-world networks.

They define the "entropy gap" as $\Delta H = H_1 - H_{vn}$ and prove that for any undirected unweighted graph, this gap is bounded: $0 < \Delta H \le \log_2 e$ (approximately 1.44 bits). This small, constant bound ensures that $H_1$ is a reliable approximation regardless of graph size. This "Aha!" moment reveals that the structural complexity of a graph is largely driven by its degree heterogeneity, giving $H_{vn}$ a tangible geometric meaning.

Methods and Algorithms

Leveraging the efficiency of $H_1$, the authors propose several practical applications:

  • EntropyAug: A greedy algorithm designed to maximize graph entropy. This is particularly useful for increasing network robustness or "cloaking" community structures by flattening spectral gaps.
  • IncreSim: A fast, incremental algorithm for calculating graph similarity in dynamic streams. By processing changes in $O(|V_k|)$ time, it avoids the need to recompute the entire graph's properties from scratch.
  • Spectral Polarization: A new metric introduced to guide community obfuscation, perturbing graphs so that standard community detection algorithms fail.

Empirical Validation

The study validates these theoretical findings using a diverse set of synthetic models (ER, BA, WS, SBM) and real-world datasets, including social networks (YouTube, Pokec), biological networks (C. elegans), and internet topologies (Skitter).

Key Results

  • High Accuracy: On real-world graphs, the relative approximation error between $H_1$ and $H_{vn}$ is remarkably low, typically around 1%.
  • Superior Efficiency: $H_1$-based methods are at least two orders of magnitude faster than state-of-the-art stochastic approximations like SLaQ.
  • Massive Scalability: Since $H_1$ only requires node degrees, it can be computed in $O(m)$ time. This allows for the analysis of graphs with millions of nodes where traditional spectral methods are impossible to apply.
  • Universality: The entropy gap remains stable across different graph types and is insensitive to changes in graph size, confirming the robustness of the approximation.

Limitations and Future Work

While the results are transformative for undirected graphs, several avenues for future research remain. The current study focuses on undirected networks; extending these tight bounds to directed graphs, where the Laplacian matrix is more complex, remains an open challenge. Additionally, in scenarios where the full degree sequence is not visible (e.g., the World Wide Web), sampling-based methods to estimate structural information will be necessary. Finally, further exploration of the submodularity and monotonicity of these measures could lead to even more efficient optimization algorithms for network design.

Summary updated

BibTeX
@article{liu2022similarity,
  author = {Xuecheng Liu and Luoyi Fu and Xinbing Wang and Chenghu Zhou},
  title = {{On the Similarity between von Neumann Graph Entropy and Structural Information: Interpretation, Computation, and Applications}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  doi = {10.1109/tit.2022.3142860},
}
Figure