| 講演名 | 2019-03-18 ［招待講演］劣モジュラ変換に対するチーガー不等式 吉田 悠一(NII), |
|---|---|
| PDFダウンロードページ |  PDFダウンロードページへ |
| 抄録(和) | 無向グラフに対するチーガー不等式は， グラフのコンダクタンスとその正規化ラプラシアンの第二固有値を結びつける， スペクトラルグラフ理論における基礎的な結果である． チーガー不等式は有向グラフやハイパーグラフに対しても拡張されているが， 正規化ラプラシアンは線形ではなく区分線形変換となる．本研究では， $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 |
| 資料番号 | COMP2018-50 |
| 発行日 | 2019-03-11 (COMP) |
| 研究会情報 | |
| 研究会 | COMP |
|---|---|
| 開催期間 | 2019/3/18(から1日開催) |
| 開催地（和） | 東京大学 |
| 開催地（英） | The University of Tokyo |
| テーマ（和） | |
| テーマ（英） | |
| 委員長氏名（和） | 藤戸 敏弘(豊橋技科大) |
| 委員長氏名（英） | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| 副委員長氏名（和） | 中野 眞一(群馬大) |
| 副委員長氏名（英） | Shinichi Nakano(Gunma Univ.) |
| 幹事氏名（和） | 玉置 卓(京大) / 大舘 陽太(熊本大) |
| 幹事氏名（英） | Suguru Tamaki(Kyoto Univ.) / Yota Otachi(Kumamoto Univ) |
| 幹事補佐氏名（和） | 脊戸 和寿(成蹊大) |
| 幹事補佐氏名（英） | Kazuhisa Seto(Seikei Univ.) |
| 講演論文情報詳細 | |
| 申込み研究会 | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| 本文の言語 | JPN |
| タイトル（和） | ［招待講演］劣モジュラ変換に対するチーガー不等式 |
| サブタイトル（和） | |
| タイトル（英） | [Invited Talk] Cheeger Inequalities for Submodular Transformations |
| サブタイトル（和） | |
| キーワード(1)（和/英） | 劣モジュラ関数 / Submodular Functions |
| キーワード(2)（和/英） | スペクトラルグラフ理論 / Spectral Graph Theory |
| キーワード(3)（和/英） | チーガー不等式 / Cheeger’s Inequality |
| 第 1 著者 氏名（和/英） | 吉田 悠一 / Yuichi Yoshida |
| 第 1 著者 所属（和/英） | 国立情報学研究所(略称：NII) National Institute of Informatics(略称：NII) |
| 発表年月日 | 2019-03-18 |
| 資料番号 | COMP2018-50 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | COMP-517 |
| ページ範囲 | pp.45-45(COMP), |
| ページ数 | 1 |
| 発行日 | 2019-03-11 (COMP) |