| Presentation | 2019-03-18 [Invited Talk] Cheeger Inequalities for Submodular Transformations Yuichi Yoshida, |
|---|---|
| PDF Download Page |  PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | 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. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Submodular Functions / Spectral Graph Theory / Cheeger’s Inequality |
| Paper # | COMP2018-50 |
| Date of Issue | 2019-03-11 (COMP) |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 2019/3/18(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | The University of Tokyo |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | Toshihiro Fujito(Toyohashi Univ. of Tech.) |
| Vice Chair | Shinichi Nakano(Gunma Univ.) |
| Secretary | Shinichi Nakano(Kyoto Univ.) |
| Assistant | Kazuhisa Seto(Seikei Univ.) |
| Paper Information | |
| Registration To | Technical Committee on Theoretical Foundations of Computing |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | [Invited Talk] Cheeger Inequalities for Submodular Transformations |
| Sub Title (in English) | |
| Keyword(1) | Submodular Functions |
| Keyword(2) | Spectral Graph Theory |
| Keyword(3) | Cheeger’s Inequality |
| 1st Author's Name | Yuichi Yoshida |
| 1st Author's Affiliation | National Institute of Informatics(NII) |
| Date | 2019-03-18 |
| Paper # | COMP2018-50 |
| Volume (vol) | vol.118 |
| Number (no) | COMP-517 |
| Page | pp.pp.45-45(COMP), |
| #Pages | 1 |
| Date of Issue | 2019-03-11 (COMP) |