文献

J-GLOBAL ID：202202232750822247   整理番号：22A0977009

von Neumannグラフエントロピーと構造情報の類似性について:解釈,計算および応用【JST・京大機械翻訳】

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

著者 (4件)： Liu Xuecheng (Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai, China) ,  Fu Luoyi (Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China) ,  Wang Xinbing (Department of Electronic Engineering, Shanghai Jiao Tong University, Shanghai, China) ,  Zhou Chenghu (Chinese Academy of Sciences, Institute of Geographical Science and Natural Resources Research, Beijing, China)
資料名： IEEE Transactions on Information Theory  (IEEE Transactions on Information Theory)
巻： 68  号： 4  ページ： 2182-2202  発行年： 2022年 
JST資料番号： C0231A  ISSN： 0018-9448  CODEN： IETTAW  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： von Neumannグラフエントロピーはラプラシアンスペクトルに基づくグラフ複雑度の尺度である。それはネットワーク化データによって駆動される様々な学習タスクにおいて最近応用されている。しかし,単純な構造パターンを用いて解釈するのは,計算的に要求され,困難である。ラプラシアンスペクトルと次数配列の間の密接な関係により,正規化次数シーケンスのShannonエントロピーとして定義される構造情報が,スケーラブルで解釈可能なvon Neumannグラフエントロピーの良好な近似であると推測した。本研究では,エントロピーギャップと呼ばれる構造情報とvon Neumannグラフエントロピーの違いを調べた。次数シーケンスがラプラシアンスペクトルによって主になるという知識に基づいて,著者らは,エントロピーギャップが任意の無向加重グラフにおいて0とlog_2eの間にあることを初めて証明した。その結果,構造情報がvon Neumannグラフエントロピーの良好な近似であると証明し,同時に,証明可能な精度,スケーラビリティ,および解釈可能性を達成した。この近似を2つのエントロピー関連タスク,すなわちネットワーク設計とグラフ類似性測度に適用し,ここでは新しいグラフ類似性測度と対応する高速アルゴリズムを提案した。一方,von Neumannグラフエントロピーの最大化はコミュニティ構造を効果的に隠し,次にコミュニティの混乱を導くためにスペクトル偏光と呼ばれる代替メトリックを提案した。種々のスケールとタイプのグラフに関する著者らの実験結果は,非常に小さなエントロピーギャップが広範囲の単純/加重グラフに容易に適用できることを示した。von Neumannグラフエントロピーの近似として,構造情報は,顕著な方法の中で高効率と高精度の両方を達成する唯一のものである。それは,SLaQ(Titsulin et al.,2020)よりも少なくとも2桁速く,同等の精度であった。また,構造情報ベースの方法は,エントロピー駆動ネットワーク設計,グラフ比較,およびコミュニティ混乱のような下流タスクにおいて優れた性能を示す。Copyright 2022 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *エントロピー ,  *グラフ ,  測度 ,  偏光 ,  学習 ,  構造 ,  スペクトル ,  高速アルゴリズム ,  カオス ,  正規化 ,  Laplace演算子
準シソーラス用語： 高効率 ,  ネットワーク設計 ,  ネットワーク化 ,  情報エントロピー , 【Automatic Indexing@JST】

分類 (1件)： グラフ理論基礎  (IA02020S)

タイトルに関連する用語 (5件)： グラフ ,  エントロピー ,  類似性 ,  計算 ,  応用