| 電子情報通信学会 研究会発表申込システム 講演論文 詳細 |
技報閲覧サービス [ログイン] 技報アーカイブ |
| トップに戻る | 前のページに戻る | [Japanese] / [English] |
| 講演抄録／キーワード | ||
| 講演名 | 2019-03-18 15:00 ［招待講演］劣モジュラ変換に対するチーガー不等式 ○吉田悠一（NII）  COMP2018-50 |
|
| 抄録 | （和） | 無向グラフに対するチーガー不等式は， グラフのコンダクタンスとその正規化ラプラシアンの第二固有値を結びつける， スペクトラルグラフ理論における基礎的な結果である． チーガー不等式は有向グラフやハイパーグラフに対しても拡張されているが， 正規化ラプラシアンは線形ではなく区分線形変換となる． 本研究では， $m$個の劣モジュラ関数を$n$次元ベクトルに適用する劣モジュラ変換$F: {0,1}^n→R^m$， 及びそのラプラシアンと正規化ラプラシアンを導入する． 劣モジュラ変換のコンダクタンスと正規化ラプラシアンの第二固有値を結びつけるチーガー不等式を示すことで， 既存のチーガー不等式を統一及び一般化する． この結果は，無向グラフ， 有向グラフ， ハイパーグラフに対するチーガー不等式を復元し，更に相互情報量や有向情報量に対するチーガー不等式を導出する． 劣モジュラ変換に対する正規化ラプラシアンの非自明な最小固有値を計算することはSmall Set Expansion予想のもとでNP困難である． それに対し本研究では， 対称な場合にタイトな多項式時間$O(log n)$-近似アルゴリズムを与え， 一般の場合に多項式時間$O(log^2n +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(logn)-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 | Online edition: ISSN 2432-6380 | |
| 著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します．(許諾番号：10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) | |
| PDFダウンロード | COMP2018-50 |
|
| 研究会情報 | |
| 研究会 | COMP |
| 開催期間 | 2019-03-18 - 2019-03-18 |
| 開催地（和） | 東京大学 |
| 開催地（英） | The University of Tokyo |
| テーマ（和） | |
| テーマ（英） | |
| 講演論文情報の詳細 | |
| 申込み研究会 | COMP |
| 会議コード | 2019-03-COMP |
| 本文の言語 | 日本語 |
| タイトル（和） | 劣モジュラ変換に対するチーガー不等式 |
| サブタイトル（和） | |
| タイトル（英） | 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) |
| 講演者 | 第1著者 |
| 発表日時 | 2019-03-18 15:00:00 |
| 発表時間 | 60分 |
| 申込先研究会 | COMP |
| 資料番号 | COMP2018-50 |
| 巻番号（vol） | vol.118 |
| 号番号（no） | no.517 |
| ページ範囲 | p.45 |
| ページ数 | 1 |
| 発行日 | 2019-03-11 (COMP) |
[研究会発表申込システムのトップページに戻る]