  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. 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 paper, we present a polynomial-time $O(\log n)$-approximation algorithm
for the symmetric case, which is tight, and a polynomial-time $O(\log^2n+\log n
\cdot \log m)$-approximation algorithm for the general case.
  We expect the algebra concerned with submodular transformations, or
\emph{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.
