IEEE TRANSACTIONS ON INFORMATION THEORY 1 On the Similarity between von Neumann Graph Entropy and Structural Information:Interpretation, Computation,and Applications Xuecheng Liu,Luoyi Fu,Xinbing Wang,and Chenghu Zhou Abstract-The von Neumann graph entropy is a measure downstream tasks such as entropy-driven network design,graph of graph complexity based on the Laplacian spectrum.It has comparison,and community obfuscation. recently found applications in various learning tasks driven by the networked data.However,it is computationally demanding Index Terms-Spectral graph theory,Laplacian spectrum, and hard to interpret using simple structural patterns.Due to spectral polarization,community obfuscation. the close relation between the Laplacian spectrum and the degree sequence,we conjecture that the structural information,defined as the Shannon entropy of the normalized degree sequence,might I.INTRODUCTION be a good approximation of the von Neumann graph entropy that VIDENCE has rapidly grown in the past few years that is both scalable and interpretable. In this work,we thereby study the difference between the graphs are ubiquitous in our daily life;online social structural information and the von Neumann graph entropy networks,metabolic networks,transportation networks,and named as entropy gap.Based on the knowledge that the degree collaboration networks are just a few examples that could be sequence is majorized by the Laplacian spectrum,we for the represented precisely by graphs.One important issue in graph first time prove that the entropy gap is between 0 and log,e in analysis is to measure the complexity of these graphs [2], any undirected unweighted graphs.Consequently we certify that [3]which refers to the level of organization of the structural the structural information is a good approximation of the von Neumann graph entropy that achieves provable accuracy,scala- features such as the scaling behavior of degree distribution, bility,and interpretability simultaneously.This approximation is community structure,core-periphery structure,etc.In order further applied to two entropy-related tasks:network design and to capture the inherent structural complexity of graphs,many graph similarity measure,where a novel graph similarity measure entropy based graph measures [3]-[8]are proposed,each of and the corresponding fast algorithms are proposed.Meanwhile, which is a specific form of the Shannon entropy for different we show empirically and theoretically that maximizing the von Neumann graph entropy can effectively hide the community types of distributions extracted from the graphs. structure,and then propose an alternative metric called spectral As one of the aforementioned entropy based graph com- polarization to guide the community obfuscation. plexity measures,the von Neumann graph entropy,defined Our experimental results on graphs of various scales and types as the Shannon entropy of the spectrum of the trace rescaled show that the very small entropy gap readily applies to a wide Laplacian matrix of a graph (see Definition 1),is of special range of simple/weighted graphs.As an approximation of the von Neumann graph entropy,the structural information is the only interests to scholars and practitioners [1],[9]-[15].This spec- one that achieves both high efficiency and high accuracy among trum based entropy measure distinguishes between different the prominent methods.It is at least two orders of magnitude graph structures.For instance,it is maximal for complete faster than SLaQ [1]with comparable accuracy.Our structural graphs,minimal for graphs with only a single edge,and information based methods also exhibit superior performance in takes on intermediate values for ring graphs.Historically,the entropy measure originates from quantum information theory Manuscript received February 18,2021:revised November 9,2021:ac- and is used to describe the mixedness of a quantum system cepted January 2.2022.Date of publication TBD:date of current ver. which is represented as a density matrix.It is Braunstein et sion TBD.This work was supported by National Key R&D Program of China (No.2018YFB2100302).NSF China (No.42050105,62020106005 al.that first use the von Neumann entropy to measure the 62061146002.61960206002.61822206.61832013.61829201),2021 Tencent complexity of graphs by viewing the scaled Laplacian matrix AI Lab RhinoBird Focused Research Program (No.JR202132),and the as a density matrix [8]. Program of Shanghai Academic/Technology Research Leader under Grant No.18XD1401800.(Corresponding author:Xinbing Wang.) Built upon the Laplacian spectrum,the von Neumann graph Xuecheng Liu and Xinbing Wang are with the Department of Elec- entropy is a natural choice to capture the graph complexity tronic Engineering,Shanghai Jiao Tong University,Shanghai,200240 China since the Laplacian spectrum is well-known to contain rich in- (email:liuxuecheng@sjtu.edu.cn,xwang8@sjtu.edu.cn). Luoyi Fu is with the Department of Computer Science and En- formation about the multi-scale structure of graphs [16],[17]. gineering,Shanghai Jiao Tong University,Shanghai,200240 China As a result,it has recently found applications in downstream (email:yiluofu@sjtu.edu.cn). tasks of complex network analysis and pattern recognition. Chenghu Zhou is with the Institute of Geographical Science and Natural Resources Research,Chinese Academy of Sciences,Beijing.100101 China For example,the von Neumann graph entropy facilitates the (email:zhouch@lreis.ac.cn). measure of graph similarity via Jensen-Shannon divergence Communicated by R.Talmon,Associate Editor for Signal Processing. which could be used to compress multilayer networks [13]and Copyright (c)2017 IEEE.Personal use of this material is permitted. However,permission to use this material for any other purposes must be detect anomalies in graph streams [9].As another example, obtained from the IEEE by sending a request to pubs-permissions@ieee.org. the von Neumann graph entropy could be used to design edgeIEEE TRANSACTIONS ON INFORMATION THEORY 1 On the Similarity between von Neumann Graph Entropy and Structural Information: Interpretation, Computation, and Applications Xuecheng Liu , Luoyi Fu , Xinbing Wang , and Chenghu Zhou Abstract—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 the networked data. However, it is computationally demanding and hard to interpret using simple structural patterns. Due to the close relation between the Laplacian spectrum and the 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 the von Neumann graph entropy named as entropy gap. Based on the knowledge that the degree sequence is majorized by the Laplacian spectrum, we for the first time prove that the entropy gap is between 0 and log2 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, scala￾bility, and interpretability simultaneously. This approximation is further applied to two entropy-related tasks: network design and graph similarity measure, where a novel graph similarity measure and the corresponding fast algorithms are proposed. Meanwhile, we show empirically and theoretically that maximizing the von Neumann graph entropy can effectively hide the community structure, and then propose an alternative metric called spectral polarization to guide the community obfuscation. Our experimental results on graphs of various scales and types show that the very small entropy gap readily applies to a wide range of simple/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 [1] with comparable accuracy. Our structural information based methods also exhibit superior performance in Manuscript received February 18, 2021; revised November 9, 2021; ac￾cepted January 2, 2022. Date of publication TBD; date of current ver￾sion TBD. This work was supported by National Key R&D Program of China (No. 2018YFB2100302), NSF China (No. 42050105, 62020106005, 62061146002, 61960206002, 61822206, 61832013, 61829201), 2021 Tencent AI Lab RhinoBird Focused Research Program (No. JR202132), and the Program of Shanghai Academic/Technology Research Leader under Grant No. 18XD1401800. (Corresponding author: Xinbing Wang.) Xuecheng Liu and Xinbing Wang are with the Department of Elec￾tronic Engineering, Shanghai Jiao Tong University, Shanghai, 200240 China (email:liuxuecheng@sjtu.edu.cn, xwang8@sjtu.edu.cn). Luoyi Fu is with the Department of Computer Science and En￾gineering, Shanghai Jiao Tong University, Shanghai, 200240 China (email:yiluofu@sjtu.edu.cn). Chenghu Zhou is with the Institute of Geographical Science and Natural Resources Research, Chinese Academy of Sciences, Beijing, 100101 China (email:zhouch@lreis.ac.cn). Communicated by R. Talmon, Associate Editor for Signal Processing. Copyright (c) 2017 IEEE. Personal use of this material is permitted. However, permission to use this material for any other purposes must be obtained from the IEEE by sending a request to pubs-permissions@ieee.org. downstream tasks such as entropy-driven network design, graph comparison, and community obfuscation. Index Terms—Spectral graph theory, Laplacian spectrum, spectral polarization, community obfuscation. I. INTRODUCTION E VIDENCE has rapidly grown in the past few years that graphs are ubiquitous in our daily life; online social networks, metabolic networks, transportation networks, and collaboration networks are just a few examples that could be represented precisely by graphs. One important issue in graph analysis is to measure the complexity of these graphs [2], [3] which refers to the level of organization of the structural features such as the scaling behavior of degree distribution, community structure, core-periphery structure, etc. In order to capture the inherent structural complexity of graphs, many entropy based graph measures [3]–[8] are proposed, each of which is a specific form of the Shannon entropy for different types of distributions extracted from the graphs. As one of the aforementioned entropy based graph com￾plexity measures, the von Neumann graph entropy, defined as the Shannon entropy of the spectrum of the trace rescaled Laplacian matrix of a graph (see Definition 1), is of special interests to scholars and practitioners [1], [9]–[15]. This spec￾trum based entropy measure distinguishes between different graph structures. For instance, it is maximal for complete graphs, minimal for graphs with only a single edge, and takes on intermediate values for ring graphs. Historically, the entropy measure originates from quantum information theory and is used to describe the mixedness of a quantum system which is represented as a density matrix. It is Braunstein et al. that first use the von Neumann entropy to measure the complexity of graphs by viewing the scaled Laplacian matrix as a density matrix [8]. Built upon the Laplacian spectrum, the von Neumann graph entropy is a natural choice to capture the graph complexity since the Laplacian spectrum is well-known to contain rich in￾formation about the multi-scale structure of graphs [16], [17]. As a result, it has recently found applications in downstream tasks of complex network analysis and pattern recognition. For example, the von Neumann graph entropy facilitates the measure of graph similarity via Jensen-Shannon divergence, which could be used to compress multilayer networks [13] and detect anomalies in graph streams [9]. As another example, the von Neumann graph entropy could be used to design edge