Cheeger Inequalities for Submodular Transformations

Understand

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 paper, we introduce the notion of a submodular transformation $F:\{0,1\}^n \to \mathbb{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.