  The von Neumann graph entropy 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 computational 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 be a good approximation of the von Neumann graph entropy that
is both scalable and interpretable.
  In this work, we thereby study the difference between the structural
information and von Neumann graph entropy named as {\em entropy gap}. Based on
the knowledge that the degree sequence is majorized by the Laplacian spectrum,
we for the first time prove the entropy gap is between $0$ and $\log_2 e$ in
any undirected unweighted graphs. Consequently we certify that the structural
information is a good approximation of the von Neumann graph entropy that
achieves provable accuracy, scalability, and interpretability simultaneously.
This approximation is further applied to two entropy-related tasks: network
design and graph similarity measure, where novel graph similarity measure and
fast algorithms are proposed. Our experimental results on graphs of various
scales and types show that the very small entropy gap readily applies to a wide
range of graphs and weighted graphs. As an approximation of the von Neumann
graph entropy, the structural information is the only one that achieves both
high efficiency and high accuracy among the prominent methods. It is at least
two orders of magnitude faster than SLaQ with comparable accuracy. Our
structural information based methods also exhibit superior performance in two
entropy-related tasks.
