On the Similarity Between von Neumann Graph Entropy and Structural Information: Interpretation, Computation, and Applications
文献类型：期刊论文
| 作者 | Liu, Xuecheng1; Fu, Luoyi2; Wang, Xinbing1; Zhou, Chenghu3 |
| 刊名 | IEEE TRANSACTIONS ON INFORMATION THEORY
 |
| 出版日期 | 2022-04-01 |
| 卷号 | 68期号:4页码:2182-2202 |
| ISSN号 | 0018-9448 |
| 关键词 | Spectral graph theory Laplacian spectrum spectral polarization community obfuscation |
| DOI | 10.1109/TIT.2022.3142860 |
| 通讯作者 | Wang, Xinbing(xwang8@sjtu.edu.cn) |
| 英文摘要 | 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 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 entropyrelated 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 (Tsitsulin et al., 2020) with comparable accuracy. Our structural information based methods also exhibit superior performance in downstream tasks such as entropy-driven network design, graph comparison, and community obfuscation. |
| 资助项目 | National Key Research and Development Program of China[2017YFB1003000] ; National Key Research and Development Program of China[2018YFB2100302] ; NSF China[42050105] ; NSF China[62020106005] ; NSF China[62061146002] ; NSF China[61960206002] ; NSF China[61822206] ; NSF China[61832013] ; NSF China[61829201] ; NSF China[JR202132] ; Program of Shanghai Academic/Technology Research Leader[18XD1401800] |
| WOS研究方向 | Computer Science ; Engineering |
| 语种 | 英语 |
| 出版者 | IEEE-INST ELECTRICAL ELECTRONICS ENGINEERS INC |
| WOS记录号 | WOS:000770590900009 |
| 资助机构 | National Key Research and Development Program of China ; NSF China ; Program of Shanghai Academic/Technology Research Leader |
| 源URL | [http://ir.igsnrr.ac.cn/handle/311030/172891]  |
| 专题 | 中国科学院地理科学与资源研究所 |
| 通讯作者 | Wang, Xinbing |
| 作者单位 | 1.Shanghai Jiao Tong Univ, Dept Elect Engn, Shanghai 200240, Peoples R China 2.Shanghai Jiao Tong Univ, Dept Comp Sci & Engn, Shanghai 200240, Peoples R China 3.Chinese Acad Sci, Inst Geog Sci & Nat Resources Res, Beijing 100101, Peoples R China |
| 推荐引用方式 GB/T 7714 | Liu, Xuecheng,Fu, Luoyi,Wang, Xinbing,et al. On the Similarity Between von Neumann Graph Entropy and Structural Information: Interpretation, Computation, and Applications[J]. IEEE TRANSACTIONS ON INFORMATION THEORY,2022,68(4):2182-2202. |
| APA | Liu, Xuecheng,Fu, Luoyi,Wang, Xinbing,&Zhou, Chenghu.(2022).On the Similarity Between von Neumann Graph Entropy and Structural Information: Interpretation, Computation, and Applications.IEEE TRANSACTIONS ON INFORMATION THEORY,68(4),2182-2202. |
| MLA | Liu, Xuecheng,et al."On the Similarity Between von Neumann Graph Entropy and Structural Information: Interpretation, Computation, and Applications".IEEE TRANSACTIONS ON INFORMATION THEORY 68.4(2022):2182-2202. |
入库方式： OAI收割
来源：地理科学与资源研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。