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.

通过引入子模变换的概念并定义其 Laplacian 和规范化 Laplacian，本文综合和概括了现有的 Cheeger 不等式，并且引出新的 Cheeger 不等式。本文还提出了一种多项式时间的保证算法，以计算子模变换的规范化 Laplacian 的最小非平凡特征值。

子模转换的 Cheeger 不等式

Cheeger Inequalities for Submodular Transformations

We consider the nonlinear graph $p$-Laplacian and its set of eigenvalues and
associated eigenfunctions of this operator defined by a variational principle.
We prove a nodal domain theorem for the graph $p$-Laplacian for any $p\geq 1$.
While for $p>1$ the bounds on the number of weak and strong nodal domains are
the same as for the linear graph Laplacian ($p=2$), the behavior changes for
$p=1$. We show that the bounds are tight for $p\geq 1$ as the bounds are
attained by the eigenfunctions of the graph $p$-Laplacian on two graphs.
Finally, using the properties of the nodal domains, we prove a higher-order
Cheeger inequality for the graph $p$-Laplacian for $p>1$. If the eigenfunction
associated to the $k$-th variational eigenvalue of the graph $p$-Laplacian has
exactly $k$ strong nodal domains, then the higher order Cheeger inequality
becomes tight as $p\rightarrow 1$.

本文研究非线性图上的 $p$-Laplacian 算子的特征值、特征函数与 nodal 区域，证明 $p≥1$ 时 nodal 区域数目的界是紧的，并且当 $p>1$ 时，边界与线性 Laplacian 相同，$p=1$ 时不同，然后用 nodal 区域的性质证明了 $p>1$ 时的高阶 Cheeger 不等式。