電子情報通信学会 研究会発表申込システム
講演論文 詳細
技報閲覧サービス
技報オンライン
‥‥ (ESS/通ソ/エレソ/ISS)
技報アーカイブ
‥‥ (エレソ/通ソ)
 トップに戻る 前のページに戻る   [Japanese] / [English] 

講演抄録/キーワード
講演名 2019-03-18 15:00
[招待講演]Cheeger Inequalities for Submodular Transformations
吉田悠一NII
技報オンラインサービス実施中
抄録 (和) 無向グラフに対するチーガー不等式は, グラフのコンダクタンスとその正規化ラプラシアンの第二固有値を結びつける, スペクトラルグラフ理論における基礎的な結果である. チーガー不等式は有向グラフやハイパーグラフに対しても拡張されているが, 正規化ラプラシアンは線形ではなく区分線形変換となる.
本研究では, $m$個の劣モジュラ関数を$n$次元ベクトルに適用する劣モジュラ変換$F: {0,1}^n→R^m$, 及びそのラプラシアンと正規化ラプラシアンを導入する. 劣モジュラ変換のコンダクタンスと正規化ラプラシアンの第二固有値を結びつけるチーガー不等式を示すことで, 既存のチーガー不等式を統一及び一般化する. この結果は,無向グラフ, 有向グラフ, ハイパーグラフに対するチーガー不等式を復元し,更に相互情報量や有向情報量に対するチーガー不等式を導出する.
劣モジュラ変換に対する正規化ラプラシアンの非自明な最小固有値を計算することはSmall Set Expansion予想のもとでNP困難である. それに対し本研究では, 対称な場合にタイトな多項式時間$O(log ⁡n)$-近似アルゴリズムを与え, 一般の場合に多項式時間$O(log^2⁡n +log ⁡n cdot log ⁡m)$-近似アルゴリズムを与える.
劣モジュラ変換に対する代数, 劣モジュラ代数は, スペクトラルグラフ理論だけでなく他の区分線形関数を扱う問題, 例えば深層学習, を解析する上でも有用であると期待される. 
(英) The Cheeger inequality for undirected graphs, which relates the conductance of an undirected graph and the second smallest eigenvalue of its normalized Laplacian, is a cornerstone of spectral graph theory. The Cheeger inequality has been extended to directed graphs and hypergraphs using normalized Laplacians for those, that are no longer linear but piecewise linear transformations.
In this work, we introduce the notion of a submodular transformation $F: {0,1}^n→R^m$, which applies $m$ submodular functions to the $n$-dimensional input vector, and then introduce the notions of its Laplacian and normalized Laplacian. With these notions, we unify and generalize the existing Cheeger inequalities by showing a Cheeger inequality for submodular transformations, which relates the conductance of a submodular transformation and the smallest non-trivial eigenvalue of its normalized Laplacian. This result recovers the Cheeger inequalities for undirected graphs, directed graphs, and hypergraphs, and derives novel Cheeger inequalities for mutual information and directed information.
Computing the smallest non-trivial eigenvalue of a normalized Laplacian of a submodular transformation is NP-hard under the small set expansion hypothesis. In this work, we present a polynomial-time O(log⁡n)-approximation algorithm for the symmetric case, which is tight, and a polynomial-time $O(log^2⁡ n +log ⁡n cdot log ⁡m)$-approximation algorithm for the general case.
We expect the algebra concerned with submodular transformations, or submodular algebra, to be useful in the future not only for generalizing spectral graph theory but also for analyzing other problems that involve piecewise linear transformations, e.g., deep learning.
キーワード (和) 劣モジュラ関数 / スペクトラルグラフ理論 / チーガー不等式 / / / / /  
(英) Submodular Functions / Spectral Graph Theory / Cheeger’s Inequality / / / / /  
文献情報 信学技報, vol. 118, no. 517, COMP2018-50, pp. 45-45, 2019年3月.
資料番号 COMP2018-50 
発行日 2019-03-11 (COMP) 
ISSN Print edition: ISSN 0913-5685  Online edition: ISSN 2432-6380

研究会情報
研究会 COMP  
開催期間 2019-03-18 - 2019-03-18 
開催地(和) 東京大学 
開催地(英) The University of Tokyo 
テーマ(和)  
テーマ(英)  
講演論文情報の詳細
申込み研究会 COMP 
会議コード 2019-03-COMP 
本文の言語 日本語 
タイトル(和) Cheeger Inequalities for Submodular Transformations 
サブタイトル(和)  
タイトル(英) Cheeger Inequalities for Submodular Transformations 
サブタイトル(英)  
キーワード(1)(和/英) 劣モジュラ関数 / Submodular Functions  
キーワード(2)(和/英) スペクトラルグラフ理論 / Spectral Graph Theory  
キーワード(3)(和/英) チーガー不等式 / Cheeger’s Inequality  
キーワード(4)(和/英) /  
キーワード(5)(和/英) /  
キーワード(6)(和/英) /  
キーワード(7)(和/英) /  
キーワード(8)(和/英) /  
第1著者 氏名(和/英/ヨミ) 吉田 悠一 / Yuichi Yoshida / ヨシダ ユウイチ
第1著者 所属(和/英) 国立情報学研究所 (略称: NII)
National Institute of Informatics (略称: NII)
第2著者 氏名(和/英/ヨミ) / /
第2著者 所属(和/英) (略称: )
(略称: )
第3著者 氏名(和/英/ヨミ) / /
第3著者 所属(和/英) (略称: )
(略称: )
第4著者 氏名(和/英/ヨミ) / /
第4著者 所属(和/英) (略称: )
(略称: )
第5著者 氏名(和/英/ヨミ) / /
第5著者 所属(和/英) (略称: )
(略称: )
第6著者 氏名(和/英/ヨミ) / /
第6著者 所属(和/英) (略称: )
(略称: )
第7著者 氏名(和/英/ヨミ) / /
第7著者 所属(和/英) (略称: )
(略称: )
第8著者 氏名(和/英/ヨミ) / /
第8著者 所属(和/英) (略称: )
(略称: )
第9著者 氏名(和/英/ヨミ) / /
第9著者 所属(和/英) (略称: )
(略称: )
第10著者 氏名(和/英/ヨミ) / /
第10著者 所属(和/英) (略称: )
(略称: )
第11著者 氏名(和/英/ヨミ) / /
第11著者 所属(和/英) (略称: )
(略称: )
第12著者 氏名(和/英/ヨミ) / /
第12著者 所属(和/英) (略称: )
(略称: )
第13著者 氏名(和/英/ヨミ) / /
第13著者 所属(和/英) (略称: )
(略称: )
第14著者 氏名(和/英/ヨミ) / /
第14著者 所属(和/英) (略称: )
(略称: )
第15著者 氏名(和/英/ヨミ) / /
第15著者 所属(和/英) (略称: )
(略称: )
第16著者 氏名(和/英/ヨミ) / /
第16著者 所属(和/英) (略称: )
(略称: )
第17著者 氏名(和/英/ヨミ) / /
第17著者 所属(和/英) (略称: )
(略称: )
第18著者 氏名(和/英/ヨミ) / /
第18著者 所属(和/英) (略称: )
(略称: )
第19著者 氏名(和/英/ヨミ) / /
第19著者 所属(和/英) (略称: )
(略称: )
第20著者 氏名(和/英/ヨミ) / /
第20著者 所属(和/英) (略称: )
(略称: )
講演者
発表日時 2019-03-18 15:00:00 
発表時間 60 
申込先研究会 COMP 
資料番号 IEICE-COMP2018-50 
巻番号(vol) IEICE-118 
号番号(no) no.517 
ページ範囲 p.45 
ページ数 IEICE-1 
発行日 IEICE-COMP-2019-03-11 


[研究会発表申込システムのトップページに戻る]

[電子情報通信学会ホームページ]


IEICE / 電子情報通信学会