Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and
Spectral Clustering
Pan Li

Olgica Milenkovic

arXiv:1803.03833v1 [cs.LG] 10 Mar 2018

Abstract
We introduce submodular hypergraphs, a family of hypergraphs that have different submodular weights associated with different cuts of hyperedges. Submodular hypergraphs
arise in clustering applications in which higher-order structures carry relevant information.
For such hypergraphs, we define the notion of p-Laplacians and derive corresponding nodal
domain theorems and k-way Cheeger inequalities. We conclude with the description of algorithms for computing the spectra of 1- and 2-Laplacians that constitute the basis of new
spectral hypergraph clustering methods.

1

Introduction

Spectral clustering algorithms are designed to solve a relaxation of the graph cut problem based
on graph Laplacians that capture pairwise dependencies between vertices, and produce sets with
small conductance that represent clusters. Due to their scalability and provable performance
guarantees, spectral methods represents one of the most prevalent graph clustering approaches [1,
2].
Many relevant problems in clustering, semisupervised learning and MAP inference [3, 4, 5]
involve higher-order vertex dependencies that require one to consider hypergraphs instead of
graphs. To address spectral hypergraph clustering problems, several approaches have been proposed that typically operate by first projecting the hypergraph onto a graph via clique expansion
and then performing spectral clustering on graphs [3]. Clique expansion involves transforming
a weighted hyperedge into a weighted clique such that the graph cut weights approximately
preserve the cut weights of the hyperedge. Almost exclusively, these approximations have been
based on the assumption that each hyperedge cut has the same weight, in which case the underlying hypergraph is termed homogeneous.
However, in image segmentation, MAP inference on Markov random fields [6, 7], network
motif studies [8, 9, 10] and rank learning [8], higher order relations between vertices captured
by hypergraphs are typically associated with different cut weights. In [8], Li and Milenkovic
generalized the notion of hyperedge cut weights by assuming that different hyperedge cuts have
different weights, and that consequently, each hyperedge is associated with a vector of weights
rather than a single scalar weight. If the weights of the hyperedge cuts are submodular, then
one can use a graph with nonnegative edge weights to efficiently approximate the hypergraph,
provided that the largest size of a hyperedge is a relatively small constant. This property of the
projected hypergraphs allows one to leverage spectral hypergraph clustering algorithms based on
clique expansions with provable performance guarantees. Unfortunately, the clique expansion
method in general has two drawbacks: The spectral clustering algorithm for graphs used in
the second step is merely quadratically optimal, while the projection step can cause a large
distortion.
To address the quadratic optimality issue in graph clustering, Amghibech [11] introduced the
notion of p-Laplacians of graphs and derived Cheeger-type inequalities for the second smallest
1

The authors are with the Coordinated Science Laboratory, Department of Electrical and Computer Engineering, University of Illinois at Urbana-Champaign (email: panli2@illinois.edu, milenkov@illinois.edu)

1

eigenvalue of a p-Laplacian, p > 1, of a graph. These results motivated Bühler and Hein’s
work [12] on spectral clustering based on p-Laplacians that provided tighter approximations of
the Cheeger constant. Szlam and Bresson [13] showed that the 1-Laplacian allows one to exactly
compute the Cheeger constant, but at the cost of computational hardness [14]. Very little is
known about the use of p-Laplacians for hypergraph clustering and their spectral properties.
To address the clique expansion problem, Hein et al. [4] introduced a clustering method for
homogeneous hypergraphs that avoids expansions and works directly with the total variation of
homogeneous hypergraphs, without investigating the spectral properties of the operator. The
only other line of work trying to mitigate the projection problem is due to Louis [15], who used a
natural extension of 2-Laplacians for homogeneous hypergraphs, derived quadratically-optimal
Cheeger-type inequalities and proposed a semidefinite programing (SDP) based algorithm whose
complexity scales with the size of the largest hyperedge in the hypergraph.
Our contributions are threefold. First, we introduce submodular hypergraphs. Submodular
hypergraphs allow one to perform hyperedge partitionings that depend on the subsets of elements involved in each part, thereby respecting higher-order and other constraints in graphs
(see [8, 6, 16] for applications in food network analysis, learning to rank, subspace clustering
and image segmentation). Second, we define p-Laplacians for submodular hypergraphs and
generalize the corresponding discrete nodal domain theorems [17, 18] and higher-order Cheeger
inequalities. Even for homogeneous hypergraps, nodal domain theorems were not known and
only one low-order Cheeger inequality for 2-Laplacians was established by Louis [15]. An analytical obstacle in the development of such a theory is the fact that p-Laplacians of hypergraphs are
operators that act on vectors and produce sets of values. Consequently, operators and eigenvalues have to be defined in a set-theoretic manner. Third, based on the newly established spectral
hypergraph theory, we propose two spectral clustering methods that learn the second smallest
eigenvalues of 2- and 1-Laplacians. The algorithm for 2-Laplacian eigenvalue computation
is
p
based on an SDP framework and can provably achieve quadratic optimality with an O( ζ(E))
approximation constant, where ζ(E) denotes the size of the largest hyperedge in the hypergraph.
The algorithm for 1-Laplacian eigenvalue computation is based on the inverse power method
(IPM) [19] that only has convergence guarantees. The key novelty of the IPM-based method is
that the critical inner-loop optimization problem of the IPM is efficiently solved by algorithms
recently developed for decomposable submodular minimization [20, 21]. Although without performance guarantees, given that the 1-Laplacian provides the tightest approximation guarantees,
the IPM-based algorithm – as opposed to the clique expansion method [8] – performs very well
empirically even when the size of the hyperedges is large. This fact is illustrated on several UC
Irvine machine learning datasets available from [22].
The paper is organized as follows. Section 2 contains an overview of graph Laplacians and
introduces the notion of submodular hypergraphs. The section also contains a description of
hypergraph Laplacians, and relevant concepts in submodular function theory. Section 3 presents
the fundamental results in the spectral theory of p-Laplacians, while Section 4 introduces two algorithms for evaluating the second largest eigenvalue of p-Laplacians needed for 2-way clustering.
Section 5 presents experimental results. All proofs are relegated to the Appendix.

2

Mathematical Preliminaries

A weighted graph G = (V, E, w) is an ordered pair of two sets, the vertex set V = [N ] =
{1, 2, . . . , N } and the edge set E ⊆ V × V , equipped with a weight function w : E → R+ .
A cut C = (S, S̄) is a bipartition of the set V , while the cut-set (boundary) of the cut C
is defined as the set of edges that have one endpoint in S and one in the complement of S, S̄,
i.e., ∂S = {(u, v) ∈ E | u ∈ S, v ∈ S̄}. The weight of the cut induced by S equals vol(∂S) =

2

P

u∈S, v∈S̄

wuv , while the conductance of the cut is defined as
c(S) =

vol(∂S)
,
min{vol(S), vol(S̄)}

P
P
where vol(S) = u∈S µu , and µu = v∈V wuv . Whenever clear from the context, for e = (uv),
we write we instead of wuv . Note that in this setting, the vertex weight values µu are determined
based on the weights of edges we incident to u. Clearly, one can use a different choice for these
weights and make them independent from the edge weights, which is a generalization we pursue
in the context of submodular hypergraphs. The smallest conductance of any bipartition of a
graph G is denoted by h2 and referred to as the Cheeger constant of the graph.
A generalization of the Cheeger constant is the k−way Cheeger constant of a graph G.
Let Pk denote the set of all partitions of V into k-disjoint nonempty subsets, i.e., Pk =
{(S1 , S2 , ..., Sk )|Si ⊂ V, Si 6= ∅, Si ∩ Sj = ∅, ∀i, j ∈ [k], i 6= j}. The k−way Cheeger constant is
defined as
hk =

min

max c(Si ).

(S1 ,S2 ,...,Sk )∈Pk i∈[k]

Spectral graph theory provides a means for bounding the Cheeger constant using the (normalized) Laplacian matrix of the graph, defined as L = D − A and L = I − D −1/2 AD −1/2 ,
respectively. Here, A stands for the adjacency matrix of the graph, D denotes the diagonal de(g)
gree matrix, while I stands for the identity matrix. The graph Laplacian is an operator △2 [1]
that satisfies
X
(g)
hx, △2 (x)i =
wuv (xu − xv )2 .
(uv)∈E

(g)

A generalization of the above operator termed the p-Laplacian operator of a graph △p
introduced by Amghibech in [11], where
X
hx, △p(g) (x)i =
wuv |xu − xv |p .

was

(uv)∈E

The well known Cheeger inequality asserts the following relationship between h2 and λ, the
(g)
second smallest eigenvalue of the normalized Laplacian △2 of a graph:
√
√
h2 ≤ 2λ ≤ 2 h2 .
It can be shown
√ that the cut ĥ2 dictated
√ by the elements of the eigenvector associated with λ
satisfies ĥ2 ≤ 2λ, which implies ĥ2 ≤ 2 h2 . Hence, spectral clustering provides a quadratically
optimal graph partition.

2.1

Submodular Hypergraphs

A weighted hypergraph G = (V, E, w) is an ordered pair of two sets, the vertex set V = [N ]
and the hyperedge set E ⊆ 2V , equipped with a weight function w : E → R+ . The relevant
notions of cuts, boundaries and volumes for hypergraphs can be defined in a similar manner
as for graphs. If each cut of a hyperedge e has the same weight we , we refer to the cut as a
homogeneous cut and the corresponding hypergraph as a homogeneous hypergraph.
For a ground set Ω, a set function f : 2Ω → R is termed submodular if for all S, T ⊆ Ω, one
has f (S) + f (T ) ≥ f (S ∪ T ) + f (S ∩ T ).
A weighted hypergraph G = (V, E, µ, w) is termed a submodular hypergraph with vertex set
V , hyperedge set E and positive vertex weight vector µ , {µv }v∈V , if each hyperedge e ∈ E
3

is associated with a submodular weight function we (·) : 2e → [0, 1]. In addition, we require the
weight function we (·) to be:
1) Normalized, so that we (∅) = 0, and all cut weights corresponding to a hyperedge e are
normalized by ϑe = maxS⊆e we (S). In this case, we (·) ∈ [0, 1];
2) Symmetric, so that we (S) = we (e/S) for any S ⊆ e;
The submodular hyperedge weight functions are summarized in the vector w , {(we , ϑe )}e∈E .
If we (S) = 1 for all S ∈ 2e /{∅, e}, submodular hypergraphs reduce to homogeneous hypergraphs.
We omit the designation homogeneous whenever there is no context ambiguity.
Clearly, a vertex v is in e if and only if we ({v}) > 0: If we ({v}) = 0, the submodularity
property implies that v is not incident to e, as for any S ⊆ e/{v}, |we (S ∪ {v}) − we (S)| ≤
we ({v}) = 0.
P
We define the degree of a vertex v as dv = e∈E: v∈e ϑe , i.e., as the sum of the max weights
N
of edges incident to the vertex v. Furthermore,
P for any vector y ∈ R , we define the projection
weight of y onto P
any subset S ⊆ V as y(S) = v∈S yv . The volume of a subset of vertices S ⊆ V
equals vol(S) = v∈S µv .
For any S ⊆ V , we generalize the notions of the boundary of S and the volume of the
boundary of S according to ∂S = {e ∈ E|e ∩ S 6= ∅, e ∩ S̄ 6= ∅}, and
X
X
vol(∂S) =
ϑe we (S) =
ϑe we (S),
(1)
e∈E

e∈∂S

respectively. Then, the normalized cut induced by S, the Cheeger constant and the k-way
Cheeger constant for hypergraphs are defined in an analogous manner as for graphs.

2.2

Laplacian Operators for Hypergraphs

We introduce next p-Laplacians of hypergraphs and a number of relevant notions associated
with Laplacian operators.
(h)
Hein et al. [4] connected the spectrum of a Laplacian △1 with the total variation via
(h)

hx, △1 (x)i =

X

e∈E

we max |xu − xv |,
u,v∈e

where we denotes the weight of a homogeneous hyperedge e. They also introduced the Inverse
(h)
Power Method (IPM) to evaluate the spectrum of the hypergraph 1-Laplacian △1 [4], but did
not establish any performance guarantees. In an independent line of work, Louis [15] introduced
a quadratic variant of a hypergraph Laplacian
X
(h)
hx, △2 (x)i =
we max (xu − xv )2 .
e∈E

u,v∈e

(h)

He also derived a Cheeger-type inequality relating the second smallest
eigenvalue
λp
of △2 and
√
p
√
ˆ
the Cheeger constant of the hypergraph h2 that reads as h2 ≤ O( log ζ(E)) λ ≤ O( log ζ(E)) h2 .
Learning the spectrum of generalizations of hypergraph Laplacians remains a challenging task.

2.3

Relevant Background on Submodular Functions

Given an arbitrary set function F : V → R satisfying F (V ) = 0, the Lovász extension [23] f :
RN → R of F is defined as follows: For any vector x ∈ RN , we order its entries in nonincreasing
order xi1 ≥ xi2 ≥ · · · ≥ xin while breaking the ties arbitrarily, and set
f (x) =

N
−1
X
j=1

F (Sj )(xij − xij+1 ),

4

(2)

with Sj = {i1 , i2 , ..., ij }. For submodular F , the Lovász extension is a convex function [23].
Let 1S ∈ RN be the indicator vector of the set S. Hence, for any S ⊆ V , one has F (S) =
f (1S ). For a submodular F , we define a convex set termed the base polytope
B , {y ∈ RN |y(S) ≤ F (S), for all S ⊆ V, and such that
y(V ) = F (V ) = 0}.

According to the defining property of submodular functions [23], we may write f (x) = maxy∈B hy, xi.
The subgradient ∇f (x) of f is defined as
{y ∈ RN | f (x′ ) − f (x) ≥ hy, x′ − xi, ∀x′ ∈ RN }.
The following lemma characterizes the subgradients ∇f (x) of a Lovász extension f of a
submodular function F .
Lemma 2.1. If f (x) is the Lovász extension of a submodular function F with base polytope B,
then
∇f (x) = arg maxhy, xi.
y∈B

Observe that ∇f (x) is a set and that the right hand side of the definition represents a set of
maximizers of the objective function. If f (x) is the Lovász extension of a submodular function,
then h∇f (x), xi = f (x).
For each hyperedge e ∈ E of a submodular hypergraph, following the above notations, we let
Be , E(Be ), fe denote the base polytope, the set of extreme points of the base polytope, and the
Lovász extension of the submodular hyperedge weight function we , respectively. Note that for
any S ⊆ V , we (S) = we (S ∩ e). Consequently, for any y ∈ Be , yv = 0 for v 6∈ e. Since ∇fe ⊆ Be ,
it also holds that (∇fe )v = 0 for v ∈
/ e. When using formula (2) to explicitly discribe the Lovász
extension fe , we can either use a vector x of dimension N or only those of its components that
lie in e. Furthermore, in the later case, |E(Be )| = |e|!.

3

p-Laplacians of Submodular Hypergraphs

We start our discussion by defining the notion of a p-Laplacian operator for submodular hypergraphs. We find the following definitions useful for our subsequent exposition.
Let sgn(·) be the sign function defined as sgn(a) = 1, for a > 0, sgn(a) = −1, for a < 0, and
sgn(a) = [−1, 1], for a = 0. For all v ∈ V , define the entries of a vector ϕp over RN according to
(ϕp (x))v = |xv |p−1 sgn(xv ). Furthermore, let U be a N ×N diagonal matrices such that Uvv = µv
for all v ∈ V .
P
Let kxkℓp ,µ = ( v∈V µv |xv |p )1/p and Sp,µ , {x ∈ RN |kxkℓp ,µ = 1}. For a function Φ over
RN , let Φ|Sp,µ stand for Φ restricted to Sp,µ .
Definition 3.1. The p-Laplacian operator of a submodular hypergraph, denoted by △p (p ≥ 1),
is defined for all x ∈ RN according to
X
hx, △p (x)i , Qp (x) =
ϑe fe (x)p .
(3)
e∈E

Hence, △p (x) may also be specified directly as an operator over RN that reads as
 P
p−1
e∈E
Pϑe fe (x) ∇fe (x) p > 1,
△p (x) =
p = 1.
e∈E ϑe ∇fe (x)

Definition 3.2. A pair (λ, x) ∈ R × RN /{0} is called an eigenpair of the p-Laplacian △p if
△p (x) ∩ λU ϕp (x) 6= ∅.
5

As fe (1) = 0, we have △p (1) = 0, so that (0, 1) is an eigenpair of the operator △p . A
p-Laplacian operates on vectors and produces sets. In addition, since for any t > 0, △p (tx) =
tp−1 △p (x) and ϕp (tx) = tp−1 ϕp (x), (tx, λ) is an eigenpair if and only if (x, λ) is an eigenpair.
Hence, one only needs to consider normalized eigenpairs: In our setting, we choose eigenpairs
that lie in Sp,µ for a suitable choice for the dimension of the space.
For linear operators, the Rayleigh-Ritz method [24] allows for determining approximate
solutions to eigenproblems and provides a variational characterization of eigenpairs based on
the critical points of functionals. To generalize the method, we introduce two even functions,
Q̃p (x) , Qp (x)|Sp,µ ,

Rp (x) ,

Qp (x)
.
kxkpℓp ,µ

Definition 3.3. A point x ∈ Sp,µ is termed a critical point of Rp (x) if 0 ∈ ∇Rp (x). Correspondingly, Rp (x) is termed a critical value of Rp (x). Similarly, x is termed a critical point of
Q̃p if there exists a σ ∈ ∇Qp (x) such that P (x)σ = 0, where P (x)σ stands for the projection
of σ onto the tangent space of Sp,µ at the point x. Correspondingly, Q̃p (x) is termed a critical
value of Q̃p .
The relationships between the critical points of Q̃p (x) and Rp (x) and the eigenpairs of △p
relevant to our subsequent derivations are listed in Theorem 3.4.
Theorem 3.4. A pair (λ, x) (x ∈ Sp,µ ) is an eigenpair of the operator △p
1) if and only if x is a critical point of Q̃p with critical value λ, and provided that p ≥ 1.
2) if and only if x is a critical point of Rp with critical value λ, and provided that p > 1.
3) if x is a critical point of Rp with critical value λ, and provided that p = 1.
The critical points of Q̃p bijectively characterize eigenpairs for all choices of p ≥ 1. However,
Rp has the same property only if p > 1. This is a consequence of the nonsmoothness of the set
S1,µ , which has been observed for graphs as well (See the examples in Section 2.2 of [14]).

3.1

Discrete Nodal Domain Theorem for p−Laplacians

Nodal domain theorems are essential for understanding the structure of eigenvectors of operators
and they have been the subject of intense study in geometry and graph theory alike [25]. The
eigenfunctions of a Laplacian operator may take positive and negative values. The signs of the
values induce a partition of the vertices in V into maximal connected components on which the
sign of the eigenfunction does not change: These components represent the nodal domains of
the eigenfunction and approximate the clusters of the graphs.
(g)
Davies et al. [26] derived the first discrete nodal domain theorem for the △2 operator.
(g)
(g)
Chang et al. [18] and Tudisco et al. [17] generalized these theorem for △1 and △p (p > 1)
of graphs. In what follows, we prove that the discrete nodal domain theorem applies to △p of
submodular hypergraphs.
As every nodal domain theorem depends on some underlying notion of connectivity, we
first define the relevant notion of connectivity for submodular hypergraphs. In a graph or a
homogeneous hypergraph, vertices on the same edge or hyperedge are considered to be connected.
However, this property does not generalize to submodular hypergraphs, as one can merge two
nonoverlapping hyperedges into one without changing the connectivity of the hyperedges. To
see why this is the case, consider two hyperedges e1 and e2 that are nonintersecting. One may
transform the submodular hypergraph so that it includes a hyperedge e = e1 ∪ e2 with weight
we = we1 + we2 . This transformation essentially does not change the submodular hypergraph,
but in the newly obtained hypergraph, according to the standard definition of connectivity, the
vertices in e1 and e2 are connected. This problem may be avoided by defining connectivity based
on the volume of the boundary set.

6

Definition 3.5. Two distinct vertices u, v ∈ V are said to be connected if for any S such that
u ∈ S and v ∈
/ S, vol(∂S) > 0. A submodular hypergraph is connected if for any non-empty
S ⊂ V , one has vol(∂S) > 0.
According to the following lemma, it is always possible to transform the weight functions of
submodular hypergraph in such a way as to preserve connectivity.
Lemma 3.6. Any submodular hypergraph G = (V, E, w, µ) can be reduced to another submodular hypergraph G′ = (V, E ′ , w′ , µ) such that w 6= w′ , without changing vol(∂S) for any
S ⊆ V and ensuring that for any e ∈ E ′ , and u, v ∈ e, u and v are connected.
Definition 3.7. Let x ∈ RN . A positive (respectively, negative) strong nodal domain is the
set of vertices of a maximally connected induced subgraph of G such that {v ∈ V |xv > 0}
(respectively, {v ∈ V |xv < 0}). A positive (respectively, negative) weak nodal domain is defined
in the same manner, except for changing the strict inequalities as {v ∈ V |xv ≥ 0} (respectively,
{v ∈ V |xv ≤ 0}).
The following lemma establishes that for a connected submodular hypergraph G, all nonconstant eigenvectors of the operator △p correspond to nonzero eigenvalues.
Lemma 3.8. If G is connected, then all eigenvectors associated with the zero eigenvalue have
constant entries.
We next state new nodal domain theorems for submodular hypergraph p−Laplacians. We
do not consider the case p = 1, although it is possible to adapt the methods for analyzing the
(g)
△1 operators of graphs to △1 operators of submodular hypergraphs. Such a generalization
requires nontrivial extensions of the critical-point theory to piecewise linear manifolds [14] that
are out of the scope of this work and will be discussed in a companion paper.
Theorem 3.9. Let p > 1 and assume that G is a connected submodular hypergraph. Further(p)
(p)
(p)
(p)
more, let the eigenvalues of △p be ordered as 0 = λ1 < λ2 ≤ · · · ≤ λk−1 < λk = · · · =
(p)

(p)

(p)

(p)

λk+r−1 < λk+r ≤ · · · ≤ λn , with λk having multiplicity r. Let x be an arbitrary eigenvector
(p)

associated with λk . Then x induces at most k +r −1 strong and at most k weak nodal domains.
Lemma 3.10. Let G be a connected submodular hypergraph. For p > 1, any nonconstant
eigenvector has at least two weak (strong) nodal domains. Hence, the eigenvectors associated
(p)
with the second smallest eigenvalue λ2 have exactly two weak (strong) nodal domains. For
(1)
p = 1, the eigenvectors associated with the second smallest eigenvalue λ2 may have only one
single weak (strong) nodal domain.
P
P
µv |xv |p−1 , µ0 (x) , v∈V :xv =0 µv ,
We define next the following three functions: µ+
p (x) ,
v∈V
:x
>0
v
P
p−1 .
and µ−
p (x) ,
v∈V :xv <0 µv |xv |

Lemma 3.11. Let G be a connected submodular hypergraph. Then, for any nonconstant
+
−
−
0
eigenvector x of △p , one has µ+
p (x) − µp (x) = 0 for p > 1, and |µ1 (x) − µ1 (x)| ≤ µ (x) for
p
p = 1. Consequently, 0 ∈ arg minc∈R kx − c1kℓp ,µ for any p ≥ 1.

The nodal domain theorem characterizes the structure of the eigenvectors of the operator,
and the number of nodal domains determines the approximation guarantees in Cheeger-type
inequalities relating the spectra of graphs and hypergraphs and the Cheeger constant. These
observations are rigorously formalized in the next section.

7

3.2

Higher-Order Cheeger Inequalities

In what follows, we analytically characterize the relationship between the Cheeger constants and
(p)
the eigenvalues λk of △p for submodular hypergraphs.
(p)

Theorem 3.12. Suppose that p ≥ 1 and let (λk , xk ) be the k−th eigenpair of the operator
△p , with mk denoting the number of strong nodal domains of xk . Then,
 p−1 

1
hmk p
(p)
≤ λk ≤ (min{ζ(E), k})p−1 hk ,
τ
p
where τ = maxv dv /µv . For homogeneous hypergraphs, a tighter bound holds that reads as
 p−1 

2
hmk p
(p)
≤ λk ≤ 2p−1 hk .
τ
p
It is straightforward to see that setting p = 1 produces the tightest bounds on the eigenvalues,
while the case p = 2 reduces to the classical Cheeger inequality. This motivates an in depth
study of algorithms for evaluating the spectrum of p = 1, 2-Laplacians, described next.

4

Spectral Clustering Algorithms for Submodular Hypergraphs

The Cheeger constant is frequently used as an objective function for (balanced) graph and hyper(p)
graph partitioning [3, 12, 13, 19, 4, 8]. Theorem 3.12 implies that λk is a good approximation
for the k-way Cheeger constant of submodular graphs. Hence, to perform accurate hypergraph
(p)
clustering, one has to be able to efficiently learn λk [2, 27]. We outline next how to do so for
k = 2.
(p)
In Theorem 4.1, we describe an objective function that allows us to characterize λ2 in a
computationally tractable manner; the choice of the objective function is related to the objective developed for graphs in [12, 13]. Minimizing the proposed objective function produces a
real-valued output vector x ∈ RN . Theorem 4.3 describes how to round the vector x and obtain
a partition which provably upper bounds c(S). Based on the theorems, we propose two algo(2)
(1)
(1)
rithms for evaluating λ2 and λ2 . Since λ2 = h2 , the corresponding partition corresponds to
(2)
the tightest approximation of the 2-way Cheeger constant. The eigenvalue λ2 can be evaluated in polynomial time with provable performance guarantees. The problem of devising good
(p)
approximations for values λk , k 6= 2, is still open.
Let Zp,µ(x, c) , kx − c1kpℓp ,µ and Zp,µ (x) , minc∈R Zp,µ (x, c), and define
Rp (x) ,

Qp (x)
.
Zp,µ (x)

(4)
(1)

(p)

Theorem 4.1. For p > 1, λ2 = inf x∈RN Rp (x). Moreover, λ2 = inf x∈RN R1 (x) = h2 .
Definition 4.2. Given a nonconstant vector x ∈ RN , and a threshold θ, set Θ(x, θ) = {v : xv >
θ}. The optimal conductance obtained from thresholding vector x equals
c(x) =

vol(∂Θ(x, θ))
.
θ∈[xmin ,xmax ) min{vol(Θ(x, θ)), vol(V /Θ(x, θ))}
inf

Theorem 4.3. For any x ∈ RN that satisfies 0 ∈ arg minc Zp,µ (x, c), i.e., such that Zp,µ (x, 0) =
Zp,µ(x), one has c(x) ≤ p τ (p−1)/p Rp (x)1/p , where τ = maxv∈V dv /µv .

8

In what follows, we present two algorithms. The first algorithm describes how to minimize
R2 (x), and hence provides a polynomial-time solution for submodular hypergraph partitioning with provable approximation guarantees, given that the size of the largest hyperedge is a
constant. The algorithm is based on an SDP, and may be computationally too intensive for
practical applications involving large hypergrpahs of even moderately large hyperedges. The
second algorithm is based on IPM [19] and aims to minimize R1 (x). Although this algorithm
does not come with performance guarantees, it provably converges and has good heuristic performance. Moreover, the inner loop of the IPM involves solving a version of the proximal-type
decomposable submodular minimization problem, which can be efficiently performed using a
number of different algorithms [28, 20, 29, 21].

4.1

An SDP Method for Minimizing R2 (x)

The R2 (x) minimization problem introduced in Equation (4) may be rewritten as
Q2 (x)
,
x:U x⊥1 kxk2
ℓ2 ,µ
min

(5)

P
P
where we observe that Q2 (x) = e∈E ϑe fe2 (x) = e∈E ϑe maxy∈E(Be ) hy, xi2 . This problem is,
in turn, equivalent to the nonconvex optimization problem
2
X 
ϑe max hy, xi
min
(6)
x∈RN

s.t.

y∈E(Be )

e

X

µv x2v = 1,

v∈V

X

µv xv = 0.

v∈V

Following an approach proposed for homogeneous hypergraphs [15], one may try to solve an
SDP relaxation of (6) instead. To describe the relaxation, let each vertex v of the graph be
associated with a vector x′v ∈ Rn , n ≥ ζ(E). The assigned vectors are collected into a matrix of
the form X = (x′1 , .., x′N ). The SDP relaxation reads as
X
ϑe ηe2
(7)
min
X∈Rn×N , η∈R|E|

s.t.
X
v∈V

kXyk22

≤

e

ηe2

∀y ∈ E(Be ), e ∈ E
X
µv kx′v k22 = 1,
µv x′v = 0.
v∈V

Note that E(Be ) is of size O(|e|!), and the above problem can be solved efficiently if ζ(E) is
small.
Algorithm 1 lists the steps of an SDP-based algorithm for minimizing R2 (x), and it comes
with approximation guarantees stated in Lemma 4.4. In contrast to homogeneous hypergraphs [15], for which the approximation factor equals O(log ζ(E)), the guarantees for general
submodular hypergraphs are O(ζ(E)). This is due to the fact that the underlying base polytope
Be for a submodular function is significantly more complex than the corresponding polytope for
the homogeneous case. We conjecture that this approximation guarantee is optimal for SDP
methods.
Lemma 4.4. Let x be as in Algorithm 1, and let the optimal value of (7) be SDPopt. Then,
with high probability, R2 (x) ≤ O(ζ(E)) SDPopt ≤ O(ζ(E)) min R2 .
This result immediately leads to the following theorem.
p
Theorem 4.5. Suppose that x is the output of Algorithm 1. Then, c(x) ≤ O( ζ(E)τ h2 ) with
high probability.
9

Algorithm 1: Minimization of R2 (x) using SDP
Input: A submodular hypergraph G = (V, E, w, µ)
1: Solve the SDP (7).
2: Generate a random Gaussian vector g ∼ N (0, In ),
where In denotes the identity matrix of order n.
3: Output x = X T g.
Algorithm 2: IPM-based minimization of R1 (x)
Input: A submodular hypergraph G = (V, E, w, µ)
Find nonconstant x0 ∈ RN s.t. 0 ∈ arg minc kx0 − c1kℓ1 ,µ
initialize λ̂0 ← R1 (x0 ), k ← 0
1: Repeat:
(
sgn(xkv )µv ,
if xkv 6= 0
k
+ k
− k
2: For v ∈ V , gv ←
µ (x )−µ (x )
µv , if xkv = 0
− 1 µ0 (xk1)
3:
4:
5:
6:
7:
8.

z k+1 ← arg minz:kzk≤1 Q1 (z) − λ̂k hz, g k i
ck+1 ← arg minc kz k+1 − c1kℓ1 ,µ
xk+1 ← z k+1 − ck+1 1
λ̂k+1 ← R1 (xk+1 )
Until |λ̂k+1 − λ̂k |/λ̂k < ǫ
Output xk+1

We describe next Algorithm 2 for optimizing R1 (x) which has guaranteed convergence properties.
Theorem 4.6. The sequence {xk } generated by Algorithm 2 satisfies R1 (xk+1 ) ≤ R1 (xk ).
The computationally demanding part of Algorithm 2 is the optimization procedure in Step 3.
The optimization problem is closely related to the problem of submodular function minimization
(SFM) due to the defining properties of the Lovász extension. Theorem 4.7 describes different
equivalent formulations of the optimization problem in Step 3.
Theorem 4.7. If the norm of the vector z in Step 3 is kzk2 , the underlying optimization problem
is the dual of the following ℓ2 minimization problem
X
min k
ye − λ̂k g k k22 , ye ∈ ϑe Be , ∀ e ∈ E,
(8)
ye

e∈E

where the primal and dual variables are related according to z =

P
λ̂k g k − e∈E ye
P
.
kλ̂k g k − e∈E ye k2

If the norm of the vector z in Step 3 is kzk∞ , the underlying optimization problem is
equivalent to the following SFM problem
X
min
ϑe we (S) − λ̂k gk (S),
(9)
S⊆V

e

where the the primal and dual variables are related according to zv = 1 if v ∈ S, and zv = −1
if v ∈
/ S.
For special forms of submodular weights, different algorithms for the optimization problems
in Theorem 4.7 may be used instead. For graphs and homogeneous hypergraphs with hyperedges
of small size, the min-cut algorithms by Karger et al. and Chekuri et al. [30, 31] allow one to
efficiently solve the discrete problem (9). Continuous optimization methods such as alternating
projections (AP) [29] and coordinate descend methods (CDM) [21] can be used to solve (8)
by “tracking” minimum norm points of base polytopes corresponding to individual hyperedges,
10

31.5
31
30.5
30
29.5
29

5
4.5
4
3.5
3
2.5
2

0

0.01

0.02

0.03

IPM-S
CEM
IPM-H

0.04

0

0.01

IPM-S
CEM
IPM-H

47.1
47
46.9
46.8
46.7
46.6
46.5

0

0.01

0.02

0.03

0.04

Cheeger constant (covertype45)

clustering error % (covertype45)

47.4

47.2

0.03

0.04

IPM-S
CEM
IPM-H

15
14.5
14
13.5
13
12.5
12
11.5
11
10.5

0

0.01

α

α
47.3

0.02

15.5

1.62 ×10

1.58

1.54
1.52
1.5
1.48

α

0

0.04

0.01

0.02

5.8 ×10

-4

IPM-S
CEM
IPM-H

8.2
8
7.8
7.6
7.4
7.2
7
6.8
6.6

0

0.01

0.03

0.04

13.5

IPM-S
CEM
IPM-H

13
12.5
12
11.5
11
10.5
10
9.5

0

0.01

0.02

0.03

0.04

0.03

0.04

0.03

0.04

-4

IPM-S
CEM
IPM-H

5.6
5.4
5.2
5
4.8
4.6

0

α

α

0.02

α

-3

1.56

1.46

0.03

8.4

α

IPM-S
CEM
IPM-H

1.6

0.02

×10

Cheeger constant % (mushroom)

32

-3

clustering error % (covertype67)

32.5

×10

5.5

Cheeger constant (covertype67)

Cheeger constant (news20)

clustering error % (news20)

IPM-S
CEM
IPM-H

clustering error % (mushroom)

6

33

0.01

0.02

α

Figure 1: Experimental clustering results for four UCI datasets, displayed in pairs of figures
depicting the Clustering error and the Cheeger constant versus α. Fine tuning the parameter
α may produce significant performance improvements in several datasets - for example, on the
Covertype67 dataset, choosing α = 0.028 results in visible drops of the clustering error and the
Cheeger constant. Both the use of 1-Laplacians and submodular weights may be credited for
improving clustering performance.
where for general submodular weights, Wolfe’s Algorithm [32] can be used. When the submodular weights have some special properties, such as that they depend only on the cardinality of
the input, there exist algorithms that operate efficiently even when |e| is extremely large [20].
In our experimental evaluations, we use a random coordinate descent method (RCDM) [21],
which ensures an expected (1+ǫ)−approximation by solving an expected number of O(|V |2 |E| log 1ǫ )
min-norm-point problems. Note that when performing continuous optimization, one does not
need to solve the inner-loop optimization problem exactly and is allowed to exit the loop as long
as the objective function value decreases. Algorithm 3 lists the step of a RCDM algorithm in
which one submodular hyperedge is sampled in one iteration, and the corresponding value of
ye is updated (Clearly, multiple values of ye can be updated simultaneously if and only if the
corresponding hyperedges do not intersect, and this parallelization step further improves the
convergence rate of the method).
Algorithm 3: A RCDM for Solving the problem (8)
Input: Submodular hypergraph G = (V, E, w, µ), λ̂k , gk .
0: Initialize ye0 ∈ ϑe Be for e ∈ E, k ← 0
1: In iteration k:
2: Sample one hyperedge e ∈ E uniformly at random.
P
3: yek+1 ← arg minye ∈ϑe Be kye + e′ ∈E/{e} ye′ − λ̂k gk k22
4: Set yek+1
← yek′ for e′ 6= e.
′
Output

5

P
λ̂k g k − e∈E ye
P
kλ̂k g k − e∈E ye k2

Experiments

In what follows, we compare the algorithms for submodular hypergraph clustering described in
the previous section to two methods: The IPM for homogeneous hypergraph clustering [4] and
the clique expansion method (CEM) for submodular hypergraph clustering [8]. We focus on
2-way graph partitioning problems related to the University of California Irvine (UCI) datasets
selected for analysis in [4], described in Table 1. The datasets include 20Newsgroups, Mush11

rooms, Covertype. In all datasets, ζ(E) was roughly 103 , and each of these datasets describes
multiple clusters. Since we are interested in 2-way partitioning, we focused on two pairs of
clusters in Covertype, denoted by (4, 5) and (6, 7), and paired the four 20Newsgroups clusters,
one of which includes Comp. and Sci, and another one which includes Rec. and Talk. The
Mushrooms and 20Newsgroups datasets contain only categorical features, while Covertype also
includes numerical features. We adopt the same approach as the one described in [4] to construct hyperedges: Each feature corresponds to one hyperedge; hence, each categorical feature
is captured by one hyperedge, while numerical features are first quantized into 10 bins of equal
size, and then mapped to hyperedges. To describe the submodular weights, we fix ϑe = 1 for all
hyperedges and parametrize we using a variable α ∈ (0, 0.5]


|S|
|e/S|
1 1
,
, ∀S ⊆ e.
we (S; α) = + min 1,
2 2
⌈α|e|⌉ ⌈α|e|⌉
The intuitive explanation behind our choice of weights is that it allows one to accommodate
categorization errors and outliers: In contrast to the homogeneous case in which any partition
of a hyperedge has weight one, the chosen submodular weights allow a smaller weight to be
used when the hyperedge is partitioned into small parts, i.e., when min{|S|, |e/S|} < ⌈α|e|⌉. In
practice, α is chosen to be relatively small – in all experiments, we set α ≤ 0.04, with α close to
zero producing homogeneous hyperedge weights.
Dataset 20Newsgroups Mushroom
|V |
16242
8124
100
112
P|E|
65451
170604
|e|
e∈E

Covertype45
12240
127
145999

Covertype67
37877
136
451529

Table 1: The UCI datasets used for experimental testing.

The results are shown in Figure 1. As may be observed, both in terms of the Clustering
error (i.e., the total number of erroneously classified vertices) and the values of the Cheeger
constant, IPM-based methods outperform CEM. This is due to the fact that for large hyperedge
sizes, CEM incurs a high distortion when approximating the submodular weights (O(ζ(E)) [8]).
Moreover, as we (S) depends merely on |S|, the submodular hypergraph CEM reduces to the
homogeneous hypergraph CEM [3], which is an issue that the IPM-based method does not face.
Comparing the performance of IPM on submodular hypergraphs (IPM-S) with that on homogeneous hypergraphs (IPM-H), we see that IPM-S achieves better clustering performance on both
20Newsgroups and Covertypes, and offers the same performance as IPM-H on the Mushrooms
dataset. This indicates that it is practically useful to use submodular hyperedge weights for
clustering purposes. A somewhat unexpected finding is that for certain cases, one observes that
when α increases (and thus, when we decreases), the corresponding Cheeger constant increases.
This may be caused by the fact that the IPM algorithm can get trapped in a local optima.

References
[1] F. R. Chung, Spectral graph theory.

American Mathematical Soc., 1997, no. 92.

[2] A. Y. Ng, M. I. Jordan, and Y. Weiss, “On spectral clustering: Analysis and an algorithm,”
in Advances in Neural Information Processing Systems, 2002, pp. 849–856.
[3] D. Zhou, J. Huang, and B. Schölkopf, “Learning with hypergraphs: Clustering, classification, and embedding,” in Advances in Neural Information Processing Systems, 2007, pp.
1601–1608.

12

[4] M. Hein, S. Setzer, L. Jost, and S. S. Rangapuram, “The total variation on hypergraphslearning on hypergraphs revisited,” in Advances in Neural Information Processing Systems,
2013, pp. 2427–2435.
[5] C. Zhang, S. Hu, Z. G. Tang, and T.-H. H. Chan, “Re-revisiting learning on hypergraphs:
Confidence interval and subgradient method,” in Proceedings of the International Conference on Machine Learning, vol. 70, 2017, pp. 4026–4034.
[6] C. Arora, S. Banerjee, P. Kalra, and S. Maheshwari, “Generic cuts: An efficient algorithm
for optimal inference in higher order MRF-MAP,” in Proceedings of the European Conference on Computer Vision. Springer, 2012, pp. 17–30.
[7] I. Shanu, C. Arora, and P. Singla, “Min norm point algorithm for higher order MRFMAP inference,” in Proceedings of the IEEE Conference on Computer Vision and Pattern
Recognition, 2016, pp. 5365–5374.
[8] P. Li and O. Milenkovic, “Inhomogeneous hypergraph clustering with applications,” in
Advances in Neural Information Processing Systems, 2017, pp. 2305–2315.
[9] A. R. Benson, D. F. Gleich, and J. Leskovec, “Higher-order organization of complex networks,” Science, vol. 353, no. 6295, pp. 163–166, 2016.
[10] C. E. Tsourakakis, J. Pachocki, and M. Mitzenmacher, “Scalable motif-aware graph clustering,” in Proceedings of the 26th International Conference on World Wide Web. International World Wide Web Conferences Steering Committee, 2017, pp. 1451–1460.
[11] S. Amghibech, “Eigenvalues of the discrete p-Laplacian for graphs,” Ars Combinatoria,
vol. 67, pp. 283–302, 2003.
[12] T. Bühler and M. Hein, “Spectral clustering based on the graph p-Laplacian,” in Proceedings
of the International Conference on Machine Learning. ACM, 2009, pp. 81–88.
[13] A. Szlam and X. Bresson, “Total variation and cheeger cuts,” in Proceedings of the International Conference on Machine Learning, 2010, pp. 1039–1046.
[14] K. C. Chang, “Spectrum of the 1-Laplacian and Cheeger’s constant on graphs,” Journal of
Graph Theory, vol. 81, no. 2, pp. 167–207, 2016.
[15] A. Louis, “Hypergraph markov operators, eigenvalues and approximation algorithms,” in
Proceedings of the ACM symposium on Theory of computing. ACM, 2015, pp. 713–722.
[16] A. Fix, T. Joachims, S. M. Park, and R. Zabih, “Structured learning of sum-of-submodular
higher order energy functions,” in Proceedings of the IEEE International Conference on
Computer Vision. IEEE, 2013, pp. 3104–3111.
[17] F. Tudisco and M. Hein, “A nodal domain theorem and a higher-order cheeger inequality
for the graph p-Laplacian,” arXiv preprint arXiv:1602.05567, 2016.
[18] K. Chang, S. Shao, and D. Zhang, “Nodal domains of eigenvectors for 1-Laplacian on
graphs,” Advances in Mathematics, vol. 308, pp. 529–574, 2017.
[19] M. Hein and T. Bühler, “An inverse power method for nonlinear eigenproblems with applications in 1-spectral clustering and sparse pca,” in Advances in Neural Information Processing
Systems, 2010, pp. 847–855.
[20] S. Jegelka, F. Bach, and S. Sra, “Reflection methods for user-friendly submodular optimization,” in Advances in Neural Information Processing Systems, 2013, pp. 1313–1321.

13

[21] A. Ene and H. Nguyen, “Random coordinate descent methods for minimizing decomposable submodular functions,” in Proceedings of the International Conference on Machine
Learning, 2015, pp. 787–795.
[22] A. Asuncion and D. Newman, “UCI machine learning repository,” 2007.
[23] L. Lovász, “Submodular functions and convexity,” in Mathematical Programming The State
of the Art. Springer, 1983, pp. 235–257.
[24] S. H. Gould, Variational methods for eigenvalue problems.
Toronto, 1966, vol. 22, no. 12.

University of Toronto Press

[25] T. Bıyıkoglu, J. Leydold, and P. F. Stadler, “Laplacian eigenvectors of graphs,” Lecture
notes in mathematics, vol. 1915, 2007.
[26] E. BrianDavies, G. L. Gladwell, J. Leydold, and P. F. Stadler, “Discrete nodal domain
theorems,” Linear Algebra and its Applications, vol. 336, no. 1-3, pp. 51–60, 2001.
[27] U. Von Luxburg, “A tutorial on spectral clustering,” Statistics and computing, vol. 17,
no. 4, pp. 395–416, 2007.
[28] V. Kolmogorov, “Minimizing a sum of submodular functions,” Discrete Applied Mathematics, vol. 160, no. 15, pp. 2246–2258, 2012.
[29] R. Nishihara, S. Jegelka, and M. I. Jordan, “On the convergence rate of decomposable submodular function minimization,” in Advances in Neural Information Processing Systems,
2014, pp. 640–648.
[30] D. R. Karger, “Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm,” in Proceedings of the ACM-SIAM Symposium on Discrete Algorithms, vol. 93,
1993, pp. 21–30.
[31] C. Chekuri and C. Xu, “Computing minimum cuts in hypergraphs,” in Proceedings of
the ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied
Mathematics, 2017, pp. 1085–1100.
[32] P. Wolfe, “Finding the nearest point in a polytope,” Mathematical Programming, vol. 11,
no. 1, pp. 128–149, 1976.
[33] F. Bach et al., “Learning with submodular functions: A convex optimization perspective,”
Foundations and Trends R in Machine Learning, vol. 6, no. 2-3, pp. 145–373, 2013.
[34] F. H. Clarke, Optimization and nonsmooth analysis.

Siam, 1990, vol. 5.

[35] F. Josellis and O. Knill, “The Lusternik-Schnirelmann theorem for graphs,” arXiv preprint
arXiv:1211.0750, 2012.
[36] K.-C. Chang, “Variational methods for non-differentiable functionals and their applications to partial differential equations,” Journal of Mathematical Analysis and Applications,
vol. 80, no. 1, pp. 102–129, 1981.
[37] T. Bühler, S. S. Rangapuram, S. Setzer, and M. Hein, “Constrained fractional set programs
and their application in local clustering and community detection,” in Proceedings of the
International Conference on Machine Learning. JMLR. org, 2013, pp. I–624.

14

6

Appendix

6.1

Preliminary Proofs

We find the following properties of the Lovász extension of normalized symmetric submodular
functions useful in the derivations to follow.
Lemma 6.1. Consider two vectors x, x′ ∈ RN . If F is a symmetric submodular function with
F ([N ]) = 0, and f (x) is the corresponding Lovász extension, then for any scalar c ∈ R,
1) f (cx) = |c|f (x).
2) ∇f (cx) = sgn(c)∇f (x), where sgn denotes the sign function defined in the main text.
3) h∇f (x), 1i = 0.
Proof. Given the definition of the Lovász extension and its subgradient, for any c > 0 we have
f (cx) = cf (x) and ∇f (cx) = ∇f (x). As F is a symmetric submodular function, f (x) = f (−x)
is even, which establishes the first claim. Also, since f (x) is even, ∇f (x) is odd, and thus, for
some c < 0, we have ∇f (cx) = ∇f ((−c) − x) = ∇f (−x) = −∇f (x). For c = 0, ∇f (0) = B =
[−1, 1]B = {ab : a ∈ [−1, 1], b ∈ B}, since F is a symmetric submodular function. Hence, the
second claim holds as well. The third claim follows from h∇f (x), 1i = F ([N ]) = 0.
Definition 6.2. Let x, x′ ∈ RN . If xu > xv ⇒ x′u > x′v for all u, v ∈ [N ], we write x ⇀ x′ .
Lemma 6.3. Assume that F is a submodular function defined on [N ] and that f is its corresponding Lovász extension. If x ⇀ x′ , then ∇f (x′ ) ⊆ ∇f (x). Furthermore, h∇f (x′ ), xi = f (x).
Proof. Consider a point y ′ ∈ ∇f (x′ ). According to Lemma 2.1, we know that y ′ ∈ arg maxy∈B hy, x′ i.
Suppose that a nonincreasing order of components in x′ reads as x′i1 ≥ x′i2 ≥ · · · ≥ x′iN . By the
duality result of Proposition 3.2 inP
[33], it is known that y ′ is an optimal solution to the above
optimization problem if and only if kj=1 yi′j = F ({i1 , ..., ik }) whenever x′ik > x′ik+1 or k = N . As
P
x ⇀ x′ , kj=1 yi′j = F ({i1 , ..., ik }) whenever xik > xik+1 or k = N, and thus y ′ is also an optimal
solution for maxy∈B hy, xi, i.e., ∇f (x′ ) ⊆ ∇f (x). Hence, h∇f (x′ ), xi ∈ h∇f (x), xi = f (x), which
concludes the proof.

6.2

Proof for Lemma 2.1

Suppose that y ′ ∈ arg maxy∈B hy, xi. Then, f (x) = hy ′ , xi, and f (x′ ) ≥ hy ′ , x′ i for all x′ ∈ RN .
Therefore, f (x′ ) − f (x) ≥ hy ′ , x′ − xi, and thus y ′ is a subgradient of f at x.
Suppose next that y ′ ∈ ∇f (x), and let S ⊆ [N ]. If S = [N ], we have f (x ± 1[N ] ) ≥
f (x) ± hy ′ , 1[N ] i. As f (x ± 1[N ] ) = f (x), so y ′ ([N ]) = 0. When S 6= [[N ]], we have
F (S) =f (1S ) = maxhy, 1S i = maxhy, x + 1S − xi ≥ maxhy, x + 1S i − maxhy, xi
y∈B

y∈B

y∈B

y∈B

1)

=f (x + 1S ) − f (x) ≥ hy ′ , x + 1S − xi = y ′ (S),
where 1) follows from the definition of the subgradient. Hence, y ′ ∈ B. As y ′ ∈ ∇f (x), we have
f (0) − f (x) ≥ hy ′ , −xi, which implies hy ′ , xi ≥ f (x). Hence, y ′ ∈ arg maxy∈B hy, xi.

6.3

Proof for Theorem 3.4

We first prove Statement 1. Note that since
∇Qp (x) = p△p (x),
y ∈ ∇Qp (x) is equivalent to y/p ∈ △p (x).
15

When p > 1, Sp,µ is a differentiable and symmetric manifold. As (∇kxkpℓp ,µ )v = pµv φp (xv ),
the tangent space of Sp,µ at x is a vector space that can be described as follows


X

X
Tx (Sp,µ ) =
cv χv , where {cv }v∈[N ] satisfies
cv µv φp (xv ) = 0 ,


v∈[N ]

v∈[N ]

where {χv }v∈[N ] is a canonical basis of RN . For a vector y ∈ ∇Qp (x), its projection onto
Tx (Sp,µ ), i.e., Pp (x)(y), vanishes if and only if y ⊥ Tx (Sp,µ ). More precisely,
Pp (x)(y) = 0 ⇔ there exists some c ∈ R such that yv = cµv φp (xv ),

for all v ∈ [N ],

which implies that y ∈ ∇Qp (x)∩cU φp (x) 6= ∅. Therefore, x is a critical point of Q̃p (x) if and only
hx,△ xi
Q (x)
if x is an eigenvector of △p . The corresponding eigenvalue is λ = hx,U φpp(x)i = kxkpp = Q̃p (x),
ℓp ,µ

i.e., the critical value of Q̃p at x.
When p = 1, Sp,µ is a piecewise linear manifold, whose tangent space at x ∈ Sp,µ is a cone.
According to Theorem 4.2 in [14], for some vector y ∈ ∇Qp (x), its projection onto the tangent
space at x, i.e., Pp (x)(y), vanishes if and only if there exists some c ∈ R and {cu }, where |cu | ≤ 1,
such that


X
X
y = c
µv sgn(xv )χv +
µu cu χu  ,
u:xu =0

v:xv 6=0

which implies y ∈ cU φp (x) ∩ ∇Qp (x) 6= ∅. Therefore, x is a critical point of Q̃p (x) if and only
Q (x)
hx,△ xi
if x is an eigenvector of △p . The corresponding eigenvalue is λ = hx,U φpp(x)i = kxkpp = Q̃p (x),
ℓp ,µ

i.e., the critical value of Q̃p at x.
Now we prove statements 2 and 3. For p > 1, kxkpℓp ,µ is differentiable, so
∇Rp (x) =

kxkpℓp ,µ ∇Qp (x) − pQp (x)U ϕp (x)
kxk2p
ℓp ,µ

=

p
(△p (x) − Rp (x)U ϕp (x)) .
kxkpℓp ,µ

(10)

Hence, 0 ∈ ∇Rp (x) is equivalent to 0 ∈ △p (x) ∩ Rp (x)U ϕp (x), i.e., (x, Rp (x)) is an eigenpair.
However, for p = 1, we only have (See Proposition 2.3.14 [34])
∇Rp (x) ⊆

kxkpℓp ,µ ∇Qp (x) − pQp (x)U ϕp (x)
kxk2p
ℓp ,µ

.

Therefore, 0 ∈ the set on the right hand side does not necessarily imply that 0 ∈ ∇Rp (x).

6.4

Proof for Lemma 3.6

The high level idea behind our proof is as follows: Given a hyperedge e, if for some nonempty
S ⊂ e we have we (S) = 0, then e can be split into two hyperedges e1 = S and e2 = e/S with two
modified submodular weights associated with e1 and e2 . As the size of e is a constant, one can
perform this procedure for all hyperedges e until all nonempty subsets S of e satisfy we (S) > 0.
Consider a hyperedge e with associated weight we (S1 ) = 0 for some nonempty S1 ⊂ e. Then,
for any S ⊆ e, it must hold that
2we (S) ≥ [we (S1 ∪ S) + we (S1 ∩ S) − we (S1 )] + [we (S1 ∪ S̄) + we (S1 ∩ S̄) − we (S1 )]
= [we (S1 ∪ S) + we (S1 ∩ S)] + [we (S/S1 ) + we (S1 /S)]

= [we (S ∩ S1 ) + we (S/S1 )] + [we (S ∪ S1 ) + we (S1 /S)]

≥ 2we (S).

16

Hence, all inequalities must be strict equalities so that
we (S) = we (S1 ∪ S) + we (S1 ∩ S) = we (S1 /S) + we (S/S1 )

= we (S ∩ S1 ) + we (S/S1 ) = we (S ∪ S1 ) + we (S1 /S).

As a result, we (S1 /S) = we (S ∩ S1 ) and we (S/S1 ) = we (S ∪ S1 ). This implies that the hyperedge
e can be partitioned into two hyperedges, e1 = S1 and e2 = e/S1 , with weights (ϑei , wei )i=1,2 ,
such that
ϑei = max we (S),
S⊂ei

ϑei wei (S) = ϑe we (S) for all S ⊂ ei .

This partition ensures that wei is a normalized, symmetric submodular function and that for
any S ⊆ e, ϑe we (S) = ϑe1 we1 (S ∩ e1 ) + ϑe2 we2 (S ∩ e2 ). Therefore, for any subset S of [N ], the
volume vol(∂S) remains unchanged.

6.5

Proof for Lemma 3.8

Let x be an eigenvector associated with the eigenvalue 0. Then, Qp (x) = hx, △p xi = 0. Therefore, for each hyperedge e, we have fe (x) = 0. Based on Lemma 3.6 of the main text, we
may assume that the weights of G have been transformed so that for any e ∈ E and any set
S ∩ e 6= {∅, e}, one has we (S) > 0. Therefore, for any v ∈ e, xv is a constant vector. As in the
transformed G, for each pair of vertices v, u ∈ [N ], one can find a hyperedge path from v to u,
so for all v ∈ [N ], xv is a constant vector

6.6
6.6.1

Proof for Theorem 3.9
Preliminaries: The Lusternik-Schnirelman Theory and Krasnoselski Genus

Once Theorem 3.4 has been established, a standard way to analyze the spectrum of △p is to study
the critical points of Rp = Qp (x)/kxkpℓp ,µ or Q̃p = Qp (x)|Sp,µ (as the two cases are equivalent
when p > 1). A crucial component within this framework is the the Lusternik-Schnirelman
theory [35]. As Qp and Sp,µ are symmetric, one needs to use the notion of a Krasnoselski genus,
defined below. This type of approach has also been used to study the spectrum of p-Laplacians
of graphs, and the readers interested in the mathematical theory behind the derivations are
referred to [14, 17] and references therein for more details.
Definition 6.4. Let A ⊂ RN /{0} be a closed and symmetric set. The Krasnoselski genus of A
is defined as

 0, if A = ∅,
inf{k ∈ Z+ |∃ odd continuous h : A → Rk /{0}}
γ(A) =
(11)

+
∞ if for any finite k ∈ Z , no such h exists.
We now focus on a particular subset of Sp,µ, defined as

Fk (Sp,µ ) , {A ⊆ Sp,µ |A = −A, closed, γ(A) ≥ k}.
As Qp may not be differentiable even when p > 1, we apply Chang’s generalization of the PalaisSmale condition for locally Lipschitz continuous functionals defined on a smooth Banach-Finsler
manifold (See Remark 3.3 [36]). We simplify the statement to our setting,
Definition 6.5. We say g : Sp,µ → R is locally Lipschitz : if for each x ∈ Sp,µ , there exists a
neighborhood Nx of x and a constant C depending on Nx such that |g(x′ ) − g(x)| ≤ Ckx′ − xkℓ2
for any x′ ∈ Sp,µ ∩ Nx .
It is easy to check Q̃p is locally Lipschitz.
17

Definition 6.6. We say a locally Lipschitz function g : Sp,µ → R satisfies the Palais-Smale
condition if any sequence {xm }m=1,2,... along which |g(xn )| is bounded and miny∈∇g(xn ) kykℓ2 → 0
possess a convergence subsequence.
As Sp,µ is smooth for p > 1, ∇Q̃p (x) is well defined and same as ∇Rp (x), i.e.,
∇Q̃p (x) =

p
(△p (x) − Rp (x)U ϕp (x)) |Sp,µ = (△p (x) − Qp (x)U ϕp (x))|Sp,µ
kxkpℓp ,µ

in equation (10). Also, as Q̃p is bounded and Sp,µ is a compact space, Q̃p satisfies the PalaisSmale condition. Given Sp,µ is reflexive, we have the following deformation theorem for locally
Lipschitz functions on Sp,µ :
Theorem 6.7 (Theorem 3.1 [36]: Deformation Theorem). Suppose function g : Sp,µ → R is
locally Lipschitz and satisfies the Palais-Smale condition. Let Ac = {x ∈ Sp,µ : g(x) ≤ c} and
Kc = {x ∈ Sp,µ : g(x) = c, 0 ∈ ∇g(x)}. If c is a real number and N is any neighborhood of Kc .
Then, for any ǫ0 > 0 there exists ǫ ∈ (0, ǫ0 ) and a homeomorphism h : Sp,µ → Sp,µ such that:
1) h(x) = x for x 6∈ Ac+ǫ0 − Ac−ǫ0
2) h(Ac+ǫ /N ) ⊂ Ac−ǫ
3) If Kc = ∅, then h(Ac+ǫ ) ⊂ Ac−ǫ .
Moreover, if g is even, h can be odd (See Remark 3.4 [36]).
As Q̃p satisfies the Palais-Smale condition and is even, there exists odd homeomorphism h
that satisfies the properties in deformation theorem, and thus the minimax principle can be
derived:
Theorem 6.8 (Theorem 3.2 [36]: Lusternik-Schnirelman theorem for locally Lipschitz functions). Suppose function g : Sp,µ → R is locally Lipschitz, even, bounded below, and satisfies
the Palais-Smale condition, then
min

max g(x)

A:Fk (Sp,µ ) x∈A

k = 1, 2, ...

characterized the critical values of g.
Since, Qp ≥ 0 and thus is bounded below. By invoking the Lusternik-Schnirelman theorem,
the critical values of Q̃p or Rp (x)|Sp,µ equal
(p)

λk =

min

max Q̃p =

A:Fk (Sp,µ ) x∈A

min

max Rp (x),

A:Fk (Sp,µ ) x∈A

k = 1, 2, ...

(12)

Formula (12) gives a variational characterization of the eigenvalues of △p as described in Theorem 3.4. Also, based on the deformation theorem again, one can guarantee that each critical
value corresponds to at least one critical point. Therefore, the following lemma applies to the
setting described above.
Lemma 6.9 (Lemma 2.2 [17]). For k ≥ 1, let A∗ ∈ Fk (Sp,µ ) be a minimizing set, i.e., a set such
that
(p)

λk =

min

max Rp (x) = max∗ Rp (x).

A:Fk (Sp,µ ) x∈A

x∈A

(p)

Then A∗ contains at least one critical point of Rp (x) with respective to the critical value λk .

18

6.6.2

Proof for Theorem 3.9

The outline of the proof is similar to the one given by Tudisco and Hein [17] for graph p−Laplacians,
with one significant change that involves careful handling of submodular hyperedges.
We start by introducing some useful notation. For a vector x ∈ RN and a set A ⊂ [N ],
define a vector x|A as

xv v ∈ A
(x|A )v =
0 v 6∈ A
We also define the strong (weak) nodal space Ξ(x) (respectively, ξ(x)) induced by x as the linear
span of x|A1 , x|A2 , · · · , x|Am , where Ai , i = 1, . . . , m are the strong (weak) nodal domains of x.
Lemma 6.10. A weak nodal space is a subspace of a strong nodal space. Hence, the number
of weak nodal domains is upper bounded by the number of strong nodal domains.
Proof. Suppose that the weak nodal domains
of a vector x equal A1 , A2 , ..., Am . Hence, its weak
P
nodal space equals to ξ(x) = {y|y =
i∈[m] αi x|Ai , αi ∈ R}. Let Z = {v ∈ [N ] : xv = 0}
and set Ci = Ai /Z for i ∈ [m]. The subgraph in G induced by the vertex set Ci may contain
several connected components, in which case one may further partition Ci into disjoint sets
Ci,1 , Ci,2 , ..., Ci,ik , each of which corresponds to a connected component. It is easy to check that
the strong nodal domains of P
x exactly consist of {Ci,j }1≤i≤m,1≤j≤ik . Therefore, the strong nodal
space equals Ξ(x) = {y|y = i,j αij x|Cij , αij ∈ R} and contains ξ(x).
Our subsequent analysis of nodal domains is primarily based on the following two lemmas.

Lemma 6.11 (Lemma 3.7 [17]). Let p > 1, a, b, x, y ∈ R, so that x, y ≥ 0. Then
|ax + by|p ≤ (|a|p x + |b|p y)(x + y)p−1 ,
where the equality if and only if xy = 0 or a = b.
Lemma 6.12. Let p ≥ 1 and let (x, λ) be an eigenpair of △p . Let Ξ(x) (ξ(x)) be the strong
(weak) nodal space induced by x. Then, for any vector x′ ∈ Ξ(x) (ξ(x)), it holds that Qp (x′ ) ≤
λkx′ kpℓp ,µ , and the inequality is tight for p = 1.
Proof. Due to Lemma 6.10, we only need to prove the claimed result for the strong nodal space.
Suppose A1 , A2 , ..., Am
Pare the strong nodal domains of x. Consider a vector in the strong nodal
space of x, say y =
i αi x|Ai , where αi ∈ R. The following observation is important when
generalizing result pertaining to graphs to the case of submodular hypergraphs. As we assume
that the submodular hypergraph G is connected, we may without loss of generality assume that
G is a hypergraph obtained from the transform described in Lemma 3.6. Then, based on the
definition of nodal domains, each hyperedge e intersects at most two strong nodal domains with
different signs. Hence, x|Ai ∩e ⇀ x|e for any i ∈ [m], e ∈ E and x|Ai ∩e ⇀ sgn(αi )y|e for any
i ∈ [m], αi 6= 0, e ∈ E. From Lemma 6.3, and for any c ∈ R, i ∈ [m], one has
h∇fe (x), cx|Ai i = ch∇fe (x|e ), x|Ai ∩e i = cfe (x|Ai ∩e ) = cfe (x|Ai ),

(13)

and
fe (y) =hfe (y), yi =
=

X
i

=

X
i

*

∇fe (y),

X

αi x|Ai

i

+

=

X
i

αi h∇fe (y), x|Ai ∩e i

αi hsgn(αi )∇fe (sgn(αi )y|e ), x|Ai ∩e i =
|αi |fe (x|Ai ).

19

X
i

|αi |fe (x|Ai ∩e )
(14)

We partition the hyperedges into two sets according to how many nodal domains they intersect,
I1 = {e : |{i|e ∩ Ai 6= ∅}| ≤ 1},

I2 = {e : |{i|e ∩ Ai 6= ∅}| = 2}.
Then, we have
Qp (y) =

X

p 1)

ϑe (fe (y)) =

e

=

X

=

X

ϑe

e

ϑe

X
i

e∈I1
2)

X

ϑe

e∈I1

X
i

X
i

|αi |p (fe (x|Ai ))p +

!p

|αi |fe (x|Ai )
X

X

ϑe

i

e∈I2

|αi |p fe (x|Ai )(fe (x))p−1 +

X

!p

|αi |fe (x|Ai )

ϑe

X
i

e∈I2

!p

|αi |fe (x|Ai )

,

where 1) follows from (14) and 2) is due to the fact that fe (x) = fe (x|Ai ) for those i such that
Ai ∩ e 6= ∅, and fe (x) = 0 for those i such that Ai ∩ e = ∅. Moreover, we have
λkykpℓp ,µ =

X
i

=

X
i

2)

=

X
i

1)

|αi |p λkx|Ai kpℓp ,µ =
p

|αi |

|αi |p

X
e

X

X
i

|αi |p hx|Ai , △p xi

ϑe h∇fe (x), x|Ai i(fe (x))p−1
ϑe fe (x|Ai )(fe (x))p−1

e

where 1) is due to
λkx|Ai kpℓp ,µ = hx|Ai , λφp (x|Ai )i = hx|Ai , λφp (x)i = hx|Ai , △p xi,
and 2) follows from (13). Therefore,
!p
#
"
X
X
X
X
p
p
p−1
ϑe f˜e (y),
|αi |fe (x|Ai ) −
=
ϑe
Qp (y) − λkykℓp ,µ =
|αi | fe (x|Ai )(fe (x))
e∈I2

i

i

e∈I2

where
f˜e (y) =

h

ip h
ih
ip−1 
p
p
|αi1 |fe (x|Ai1 ) + |αi2 |fe (x|Ai2 ) − |αi1 | fe (x|Ai1 ) + |αi2 | fe (x|Ai2 ) fe (x|Ai1 ) + fe (x|Ai2 )

and Ai1 and Ai2 are the two nodal domains intersecting e. Invoking Lemma 6.11 proves the
claimed result.
Now, we are ready to prove Theorem 3.9. The proof of the strong nodal domain result for
the graph p−Laplacian in [17] can be easily extended to our case via Lemma 6.12, while the
proof of the weak nodal domain result requires significant modifications.
(p)
Case 1: Strong nodal domains. Suppose that λk has multiplicity r and associated
eigenvector x. Let Ξ(x) be the strong nodal space induced by x. If x supports m strong nodal
(p)
domains, then γ(Ξ(x) ∩ Sp,µ ) ≤ m. For any x′ ∈ Ξ(x) ∩ Sp,µ , we have Rp (x′ ) ≤ Rp (x) = λk due
to Lemma 6.12. Therefore,
(p)
λm
=

min

max Rp (x′ ) ≤

A∈Fm (Sp,µ ) x′ ∈A

max

x′ ∈Ξ(x)∩Sp,µ

which implies m ≤ k + r − 1, where r is the mulplicity of λk .
20

(p)

Rp (x′ ) ≤ λk ,

(p)

Case 2: Weak nodal domains. Suppose that λk has multiplicity r and associated
eigenvector x. Suppose that A1 , A2 , ..., Am are the weak nodal domains of x. According to
Lemma 6.10, we know that m is upper bounded by the number of strong nodal domains which
we know from Case 1 to be upper bounded by k + r − 1.
Let ξ(x) be the weak nodal space induced by x. We use proof by contradiction and assume
that dim(ξ(x)) > k. Consider ξ(x)′ satisfying ξ(x) = Span{x} ⊕ ξ(x)′ .Then, we have γ(ξ(x)′ ∩
Span{x}) ≥ k. Again, from Lemma 6.12, it holds
(p)

Rp (x′ ) ≤
λk ≤ min max
′
A∈Fk x ∈A

max

(p)

x′ ∈ξ(x)′ ∩Sp,µ

Rp (x′ ) ≤ Rp (x) = λk ,

which implies that ξ(x)′ ∩ Sp,µ is a minimizing set in Fk . From Lemma 6.9, it follows that there
P
(p)
exists a y ∈ ξ(x)′ ∩ Sp,µ such that Rp (y) = λk . Suppose that y = i αi x|Ai . Later, we will
show the contradiction by proving that y ∈ Span{x}, i.e., αi = αj for all i, j ∈ [m]. For any
two overlapping weak nodal domains, say A1 and A2 with A1 ∩ A2 6= ∅, consider the set of
hyperedges that lie in A1 ∪ A2 , and denote this set by E ∗ . Without loss of generality, assume
that A1 is positive while A2 is negative, as no hyperedge can intersect two weak nodal domains
with the same sign. Suppose that there exists a hyperedge e ∈ E ∗ such that e ∩ (A1 /A2 ) and
e ∩ (A2 /A1 ) are both nonempty. Then, both fe (x|A1 ) and fe (x|A2 ) are positive. According
to the proof of Lemma 6.12, as e intersects two strong nodal domains A1 /A2 and A2 /A1 , in
(p)
order to have Rp (y) = λk one must also have f˜e (y) = 0, which further implies α1 = α2 . If
there is no such hyperedge, then all hyperedges in E ∗ lie either in A1 or A2 . Note that for all
u ∈ A1 ∩ A2 , α1 xu = 0, so that we have
0 = h1u , △p (α1 x)i
X
=
ϑe h∇fe (α1 x), 1u i(fe (α1 x))p−1
e:e∈E ∗

1)

=

X

e:e∈A1

ϑe h∇fe (α1 x|A1 ), 1u i(fe (α1 x|A1 ))p−1 +

X

e:e∈A2

ϑe h∇fe (α1 x|A2 ), 1u i(fe (α1 x|A2 ))p−1 ,

where 1) is due to the fact that for all e ⊆ A1 ∩ A2 , one has fe (α1 x) = 0. Similarly, as yu = 0,
we have
0 = h1u , △p (y)i
X
=
ϑe h∇fe (y), 1u i(fe (y))p−1
e:e∈E ∗

1)

=

X

e:e⊆A1

ϑe h∇fe (α1 x|A1 ), 1u i(fe (α1 x|A1 ))p−1 +

X

e:e⊆A2

ϑe h∇fe (α2 x|A2 ), 1u i(fe (α2 x|A2 ))p−1 ,

where 1) once again is due to for all e ⊆ A1 ∩ A2 , one has fe (α1 x) = 0. Subtracting the above
two equations leads to
X


ϑe h∇fe (α1 x|A2 ), 1u i(fe (α1 x|A2 ))p−1 − h∇fe (α2 x|A2 ), 1u i(fe (α2 x|A2 ))p−1
0=
e:e⊆A2

= (φp (α1 ) − φp (α2 ))
1)

= (φp (α1 ) − φp (α2 ))

X

ϑe hfe (x|A2 ∩e ), 1u i(fe (x|A2 ))p−1

X

ϑe fe (1u )(fe (x|A2 ))p−1 ,

e:e⊆A2

e:e⊆A2

where 1) is due to 1u ⇀ x|A2 ∩e . Based of the definition of a weak nodal domain, there exists
at least one
P hyperedge e intersecting both A1 ∩ A2 and A2 /A1 . Therefore, for any u ∈ A1 ∩ A2
such that e:e⊆A2 ϑe fe (1u )fe (x|A2 )p−1 > 0, one has φp (α1 ) = φp (α2 ) and consequently α1 = α2 .
Since the hypergraph is connected, it follows that α1 = α2 = ... = αn = α, which implies that
y = αx. This is a contradiction and hence the number of weak nodal domains is ≤ k.
21

6.7

Proof for Lemma 3.10

Consider a nonconstant eigenvector x and its corresponding eigenvalue λ. According to Lemma
3.8, if G is connected, then λ 6= 0. Moreover,
when p > 1, U φp (x) is a vector and not a set.
P
Therefore, h1, U φp (x)i ∈ h1, △p (x)i/λ = e ϑe h1, ∇fe (x)ife (x)p−1 /λ = 0. This implies that x
contains both positive and negative components, which correspond to at least two weak (strong)
nodal domains. Combining this result with that of Theorem 3.9 shows that the eigenvector
corresponding to the eigenvalue λ2 contains exactly two weak (strong) nodal domains.
For p = 1, we only have h1, U φp (x)i ∋ h1, △p (x)i/λ = 0, which may allow that all components of x are either nonnegative or nonpositive. An example of a graph with a single weak
(strong) nodal domain may be found in Example 11 of [18].

6.8

Proof for Lemma 3.11

According to the proof of Lemma 3.10, if p > 1, we have h1, U φp (x)i = 0 and thus µ+
p (x) =
(x).
Moreover,
we
have
µ−
p
∂kx − c1kpℓp ,µ
∂c

|c=0 = p

X

v∈[N ]

−
µv sgn(xv )|xv |(p−1) = µ+
p (x) − µp (x) = 0.

(15)

Hence, c ∈ arg minc∈R kx − c1kpℓp ,µ .
−
0
If p = 1, 0 ∈ h1, U φp (x)i, which implies |µ+
1 (x) − µ1 (x)| ≤ µ (x). Furthermore, for any c ≥ 0
we have
X
X
X
kx − c1kℓ1 ,µ =
µv (xv − c) +
µv (c − xv ) +
µv (c − xv )
v:xv >c

=

X

v:xv >0

≥

X

v:xv >0

µ v xv −
µ v xv −

X

µ v xv + 2

v:xv <0

X

v:xv <0

v:xv <0

v:0≤xv <c

X

v:0<xv <c

+
µv (c − xv ) + c(µ0 (x) + µ−
1 (x) − µ1 (x))

µv xv = kxkℓ1 ,µ .

Therefore, 0 ∈ arg minc∈R kx − c1kℓ1 ,µ .

6.9

Proof of Theorem 3.12

Let us first prove the second part of the theorem. Suppose that {S1∗ , S2∗ , ..., Sk∗ } ∈ Pk is one
k-way partition such that hk = maxi∈[k] c(Si∗ ). Let A = Span(1
S1∗ , 1S2∗ , ..., 1Sk∗ ). Choose a vector
P
x ∈ A ∩ Sp,µ and suppose that it can be written as x = i∈[k] αi 1Si∗ .
P
Lemma 6.13. If x = i∈[k] αi 1Si∗ and x ∈ Sp,µ, then
X

i∈[k]

|αi |p vol(Si∗ ) = 1.

Proof. As Si∗ ∩ Sj∗ = ∅, we have 1 = kxkpℓp ,µ =

P

22

i∈[k] kαi 1Si

∗

kpℓp ,µ =

P

p
∗
i∈[k] |αi | vol(Si ).

6.9.1

Arbitrary Submodular Weights

First, consider the following chain of inequalities that leads to an upper bound for Q̃p (x):
p

X
X
X
X
Q̃p (x) =
ϑe (fe (x))p =
ϑe h∇fe (x), xip =
ϑe 
αi h∇fe (x), 1Si∗ i
e

1)

≤

e

X

e

ϑe (min{|e|, k})p−1

e

X

i∈[k]

2)

≤ (min{max |e|, k})p−1
3)

≤ (min{max |e|, k})p−1
4)

≤ (min{max |e|, k})

p−1

|αi |p |h∇fe (x), 1Si∗ i|p
X

X

|αi |p

X

|αi |p vol(∂Si∗ )

i∈[k]

i∈[k]

P

i∈[k]

(16)

ϑe (fe (1Si∗ ))p

e

p
∗
i∈[k] |αi | vol(∂Si )
∗
p
i∈[k] |αi | vol(Si )

P

≤ (min{max |e|, k})p−1 hk .

Here, 1) follows from |{i ∈ [k]|h∇fe (x), 1Si∗ ∩e i > 0}| ≤ min{|e|, k} and Hölder’s
inequality;
P
p
∗
2)
follows
from
the
definition
of
f
;
3)
is
a
consequence
of
the
inequality
ϑ
(f
e
e e e (1Si )) ≤
P
P
∗
p
e ϑe we (Si ) = vol(∂Si ); and 4) follows from Lemma 6.13.
e ϑe we (Si ) ≤
Before establishing the lower bound, we first prove the following lemma.
Lemma 6.14. For any vector x ∈ RN
≥0 /{0} and p ≥ 1, there exists some θ ≥ 0 such that
Θ(x, θ) = {u : x(u) > θ} satisfies

 p−1 
c(S) p
1
,
Rp (x) ≥
τ
p
where τ = maxv∈[N ]

dv
µv .

Proof. Let us consider the case p > 1 first. For a vector x, we use (x)p to denote the coordip
.
natewise p-th power operation. Furthermore, let q = p−1
′
N
For a vector x ∈ R , we write the Lovász extension fe (x′ ) by only including arguments that
lie in e, i.e.,
|e|−1
′

fe (x ) =

X
k=1

we (S k,e )(x′ik (e) − x′ik+1 (e) )

23

where e = {ik (e)}1≤k≤|e| , x′i1 (e) ≥ x′i2 (e) ≥ · · · ≥ x′i

|e| (e)

and S k,e = {ij (e)}1≤j≤k . Then,

|e|−1

X

Q1 (xp ) =

ϑe fe (xp ) =

e

1) X

≤

=p

e

≤p

X
k=1

XX
k=1

e

k=1

we (S k,e )(xpik (e) − xpik+1 (e) )

1− p1

p−1

k,e
ϑ1/p
)(xik (e) − xik+1 (e) ) ϑ1/q
xik (e)
e we (S
e

k=1

≤ p(Qp (x))
≤ pτ

X

we (S k,e )p(xik (e) − xik+1 (e) ) xik (e)


X |e|−1
X


ϑe

|e|−1

e

2)

e

|e|−1

ϑe

X

ϑe

h

(17)
p/q

1
1 
q
ip  p X |e|−1
X

p
k,e
ϑ
xik (e)
we (S )(xik (e) − xik+1 (e) )

  e e
k=1

!1
q

1
p

X
v

dv xpv

1

(Qp (x)) p kxkp−1
ℓp ,µ ,

where 1) follows from the fact that a ≥ b ≥ 0 implies ap − bp ≤ p(a − b)ap−1 and 2) is a
consequence of Hölder’s inequality. As when p = 1, we naturally have Q1 (x) ≤ Q1 (x). For any
p ≥ 1, we have
1

p
Q1 (xp )
1− 1 (Qp (x))
≤ pτ p
.
p
kxkℓp ,µ
kxkℓp ,µ

(18)

Moreover, by representing Lovász extension by its integral form [33], we obtain
Z +∞ X
X Z +∞
p
p
we ({v : xpv > θ} ∩ e)dθ.
ϑe
we ({v : xv > θ} ∩ e) dθ =
Q1 (x ) =
ϑe
e

0

Q1 (xp )
=
kxkpℓp ,µ

R +∞

0

e

Then,
0

P
P
p
ϑe e we ({v : xpv > θ} ∩ e)dθ
e ϑe we ({v : xv > θ} ∩ e)
≥
inf
R +∞
p
θ≥0
µ({v : xv > θ})
µ({v : xpv > θ})dθ
0

vol(∂{v : xpv > θ})
= inf c({v : xpv > θ})
p
θ≥0 vol({v : xv > θ})
θ≥0

= inf

Therefore, the minimizer θ ∗ induces a set Θ∗ = {v : xpv > θ ∗ } ⊆ A, for which the following
inequality holds
!p
 p−1 

1
Q1 (xp )
1
c(Θ∗ ) p
Qp (x)
≥
.
=
Rp (x) =
pp τ p−1
τ
p
kxkpℓp ,µ
kxkpℓp ,µ
This proves Lemma 6.14.
(p)
Next, we turn our attention to the first inequality of Theorem 3.12. Suppose λk has a
corresponding eigenvector x that induces the strong nodal domains A1 , A2 , ..., Am . According
(p)
to Lemma 6.12, we know that λk ≥ Rp (1Ai ). Moreover, due to Lemma 6.14, for any i ∈ [m],
there exists a Bi ⊆ Ai such that

 p−1 
c(Bi ) p
1
.
Rp (1Ai ) ≥
τ
p
24

Therefore,
 p−1 

1
c(Bi ) p
≥ max Rp (1Ai ) ≥ max
p
i∈[m]
i∈[m] τ
p  p−1 

 p−1 
1
c(Bi )
hm p
1
≥
.
max
≥
min
p
τ
p
(B1 ,B2 ,...,Bm )∈Pm i∈[m] τ

(p)
λk

6.9.2

Homogeneous Weights

We can use a similar approach to prove the previous result for homogeneous weights, i.e., weights
such that we (S) = 1 for all S ∈ 2e /{∅, e}. Only several steps have to be changed.
First, the inequality (16) may be tightened. Again, consider the partition {S1∗ , S2∗ , ..., Sk∗ } ∈
Pk such that hk = maxi∈[k] c(Si∗ ). For a given hyperedge e, choose a pair of vertices (u∗ , v ∗ ) ∈
arg maxu,v∈e |xu − xv |p . If both u, v ∈ Si∗ , then fe (x) = 0. If not, assume that u ∈ Si∗ and
v ∈ Sj∗ . Then,
(fe (x))p = |xu∗ − xv∗ |p ≤ 2p−1 (|xu∗ |p + |xv∗ |p )

≤ 2p−1 (|αi |p fe (1Si∗ )p + |αj |p fe (1Sj∗ )p ) = 2p−1

X

i∈[k]

|αi |p fe (1Si∗ )p .

Therefore, in the homogeneous case, we have
Rp (x) ≤ 2p−1 hk .
Second, we will use the following lemma to prove the lower bound:
Lemma 6.15 ([11]). If a, b ≥ 0, p > 1, then
a p − bp ≤

p
1− p1

2

(a − b) (ap + bp )

1− p1

So the inequality (17) may be tightened as
p

fe (x ) =

xpi0 (e)

− xpi (e)
|e|

≤

p
1− p1

2

(xi0 (e) − xi|e| (e) )



xpi0 (e)

+

xpi (e)
|e|

1− 1

p

.

With these two modifications, we can rewrite inequality (18) as
1

Q1 (xp )
p 1− p1 (Qp (x)) p
τ
,
≤
p
1− 1
kxkℓp ,µ
kxkℓp ,µ
2 p
which leads to
(p)
λk

6.10

 p−1 

2
hm p
≥
.
τ
p

Proof of Theorem 4.1
(p)

First, we prove that λ2 ≥ inf x Rp (x). Suppose that x′ is a nonconstant eigenvector cor(p)
(p)
(p)
(p)
responding to λ2 . If λ2 = 0. If λ2 = 0, then hx′ , △p (x′ )i = hx′ , λ2 U x′ i = 0, which
′
′
′
implies that Qp (x ) = 0. Moreover, as x is nonconstant, minc∈R kx − c1kpℓp ,µ > 0, and thus
(p)

(p)

Rp (x′ ) = 0 ≤ λ2 . This proves the claim of the theorem for the case that λ2 = 0. Next,
(p)
suppose that λ2 6= 0. First, we observe that Lemma 3.11 implies 0 ∈ ∇c Zp,µ (x′ , c)|c=0 . As
25

Zp,µ(x′ , c) is convex in c, c = 0 is a minimizer of Zp,µ (x′ , c), i.e., Zp,µ (x′ , 0) = Zp,µ (x′ ). Moreover,
(p)
(p)
Qp (x′ )
Q (x′ )
′
λ2 = Rp (x′ ) = Zp,µp(x′ ,0) = Zp,µ
(x′ ) = Rp (x ). Therefore, λ2 ≥ inf x Rp (x).
(p)

Second, we prove that inf x Rp (x) ≥ λ2 . First, we focus on the case p > 1. For any
t1 ∈ R/{0} and t2 ∈ R, it is easy to show that Rp (t1 x + t2 1) = Rp (x). Therefore, to characterize the infimum of Rp (x), it suffices to consider x ∈ Sp,µ ∩ A, where A = {x ∈ RN |0 ∈
arg minc Zp,µ (x, c)}. For p > 1, Zp,µ (x, c) is differentiably convex in c. By using formula (15)
−
once again, we know that A = {x ∈ RN |µ+
p (x) − µp (x) = 0}. Furthermore, A is closed, since
+
−
the functions µp , µp are continuous. By recalling that Sp,µ is a compact space we know that
there exists a point x∗ ∈ Sp,µ ∩ A such that x∗ ∈ arg inf x Rp (x).
Consider next the subspace A′ = {t1 x∗ + t2 1 : t1 , t2 ∈ R}. As x∗ being nonconstant reduces
(p)
to x∗ 6= c1 for any scalar c ∈ R, we have γ(A ∩ Sp ) = 2. According to the definition of λ2 (12),
it follows that
(p)

λ2 ≤

max
′

x∈A ∩Sp,µ

= max
t1 ∈R

Qp (x) = max Qp (
t1 ,t2 ∈R

Qp (t1 x∗ )
= Rp (x∗ ).
Zp,µ (t1 x∗ )

t 1 x∗ + t 2 1
Qp (t1 x∗ )
) = max
p
t1 ,t2 ∈R kt1 x∗ + t2 1kℓ ,µ
kt1 x∗ + t2 1kℓp ,µ
p

For any a, b ∈ R, we can write Qp (ax + b1) = |a|p Qp (x) and Zp,µ (ax + b1) = |a|p Zp,µ (x).
(p)
(p)
Combining these expressions with λ2 ≥ inf x Rp (x) shows that λ2 = inf x Rp (x). This settles
the case p > 1.
Next, we turn our attention to proving that minx R1 (x) = h2 for p = 1. This result, combined
(1)
(1)
with the inequality h2 ≥ λ2 from Theorem 3.12 proves that inf x R1 (x) = h2 = λ2 .
|∂S|
Recall that the 2-way Cheeger constant can be written as minS⊂[N ] min{vol(S),vol([N
]/S)} . This
expression, along with the fact that inf x R1 (x) = h2 (which is a special case of Theorem 1
in [37]), allows one to reduce the proof to showing that the Lovász extensions of vol(∂S) and
min{vol(S), vol([N ]/S)} are equal to Q1 (x) and Z1,µ (x), respectively. The claim regarding Q1
naturally follows from the definition 3.1. We hence only need to show that the Lovász extension
of min{vol(S), vol([N ]/S)} equals Z1,µ (x).
For a given x ∈ RN , suppose that xi1 ≥ xi2 ≥ · · · ≥ xiN . Then, the Lovász extension of
min{vol(S), vol([N ]/S)} can be written as
N
X
k=1

N
k
X
X
µ ij ,
µij } (xij − xij+1 ).
min{
j=1

(19)

j=k+1

o
n
P
P
µ
Let k∗ be equal to min k ∈ {1, 2, ..., N } : kj=1 µij ≥ N
j=k+1 ij . In this case, (19) is equivalent to
∗ −1
kX

k=1

µik (xik − xik∗ ) +

N
X

k=k ∗ +1

µik (xik∗ − xik ) = kx − xik∗ 1kℓ1 ,µ = Z1,µ (x),

which establishes the claimed result.

6.11

Proof for Theorem 4.3

For a vector x ∈ RN , define two vector x+ , x− ∈ RN according to (x+ )v = max{xv , 0} and
(x− )v = max{−xv , 0}. Hence, x = x+ − x− and x+ , −x− ⇀ x. Then,
X
X
1) X
Qp (x) =
ϑe fe (x)p =
ϑe [h∇fe (x), x+ i + h∇fe (x), −x− i]p =
ϑe [fe (x+ ) + fe (−x− )]p
e

2)

=

X

e

+ p

e

− p

+

−

ϑe [fe (x ) + fe (x ) ] = Qp (x ) + Qp (x ),

e

26

where in 1) we used Lemma 6.3, and in 2) we used the fact that fe (x) = fe (−x) and (a + b)p ≥
ap + bp for a, b ≥ 0, p ≥ 1. Moreover, as Zp,µ(x) = kxkpℓp ,µ = kx+ kpℓp ,µ + kx− kpℓp ,µ , we have
Rp (x) ≥ min{Rp (x+ ), Rp (x− )}.
By applying Lemma 6.14 on x+ and x− , and by observing that c(x+ ), c(x− ) ≥ c(x), we have
 p−1 
p  p−1 

1
min{c(x+ ), c(x− )}
1
c(x) p
Rp (x) ≥ min{Rp (x ), Rp (x )} ≥
,
≥
τ
p
τ
p
+

−

which concludes the proof.

6.12

Proof for Lemma 4.4

First, it can be easily shown that U x ⊥ 1, since
X
X
X
µv x′v )T g = 0.
µ v xv =
µv (x′v )T g = (
v∈[N ]

v∈[N ]

v∈[N ]

Next, we establish a lower bound for kxk2ℓ2 ,µ . For this purpose, we find the following lemma
useful.
Lemma 6.16 (Lemma 7.7 [15]). Let Y1 , Y2 , P
..., Yk be zero-mean normal random variables that
are not necessarily independent, such that E[ i Yi2 ] = 1. Then,
"
#
X
1
1
2
Yi ≥
P
≥ .
2
12
i

We start by observing that
E[kxk2ℓ2 ,µ ] = E[kX T gk2ℓ2 ,µ ] =

X

v∈[N ]

µv kx′v k22 = 1.

From Lemma 6.16, it follows that


1
1
2
P kxkℓ2 ,µ ≥
≥ .
2
12
Next, we prove an upper bound for Q2 (x). For any e ∈ E, w ∈ E(Be ), we have
"
"
#

2 #
2
Xy
kXyk22
=E
E
max g,
max hy, x′ i
kXyk2
y∈E(Be )
y∈E(Be )
"
2 #

Xy
max kXy ′ k22 .
≤E
max g,
kXyk2
y ′ ∈E(Be )
y∈E(Be )

(20)

(21)

Suppose that the hyperedge e contains the following vertices e = {v1 , v2 , . . . , v|e| }. Let A =
Span(x′v1 − x′v|e| , x′v2 − x′v|e| , ..., x′v|e|−1 − x′v|e| ) and let Sn stand for the unit ball in Rn . Recall n is
the dimension of the
relaxation which is no less than ζ(E).
P space to embed the vectors for SDP
Xy
Then, given that v∈e yv = 0 and yu = 0 for u ∈
/ e, kXyk
always lies in A ∩ Sn . Therefore,
2
E

"

"
2 #
2 #

Xy
′
≤E
max g, x
= dim(A) = |e| − 1.
max g,
kXyk2
x′ ∈A∩Sn
y∈E(Be )

27

(22)

Combining (21) with (22), we have
E[( max hy, x′ i)2 ] ≤ (|e| − 1) max kXyk22 .
y∈E(Be )

As Q2 (x) =

P

e∈E

y∈E(Be )

we (maxy∈E(Be ) hy, xi)2 , using Markov’s inequality, we have
!
X
1
P Q2 (x) ≥ 13 ζ(E)
max kY w′ k22 ≤ .
′
13
w ∈E(Be )

(23)

e∈E

In addition, applying the union bound to (23) and using (20), we have
P (R2 (x) ≤ 26 SDPopt) ≥

1
.
13

(24)

which concludes the proof.
Note that the distortion term O(ζ(E)) is introduced through the inequalities (21) and (22),
which are tight for this case. This may be shown as follows. Suppose the solution of the SDP
produces a collection of vectors {x′vi }1≤i≤|e| that have the same ℓ2 −norm and are orthogonal
in Rn . Let Be denote the base polytope corresponding to a submodular function satisfying
2
min{|S|, |e| − |S|}. Define a subset of Be , Be,s , as follows
we (S) = |e|
Be,s



2
N
, y ∈ R ||y({vi })| ≤
, y({vi+|e|/2 }) = −y({vi }), for 1 ≤ i ≤ |e|/2, , y({v}) = 0, for v ∈
/e .
|e|

Then, choosing a y ′ in Be,sub such that y ′ ({vi }) =
E

"

max hg, Xyi

y∈E(Be )

2 #



hg,x′vi −x′v
i
i+|e|/2
2
|e| |hg,x′vi −x′v
i|
i+|e|/2

for 1 ≤ i ≤ |e|/2, we obtain


4 
|hg, yv′ i − yv′ |e| i||hg, yv′ j − yv′ |e| i|
E
|e|2
1≤i,j≤|e|/2
 
 2


X
4
≥ 2 E
|hg, yv′ i − yv′ |e| i|

|e| 
≥

X

1≤i≤|e|/2

≥

|e| 4
|e|
1
4
≥
≥
max kyk2 ≥ |e| max kXyk2 .
π
π |e|
π y∈E(Be )
π y∈E(Be )

Hence, the Gaussian projection X causes distortion Θ(|e|).

6.13

Proof of Theorem 4.5

By combining Lemma 4.4, Theorem 4.3, Theorem 4.1 and Theorem 3.12, we obtain

1/2
p
√
c(x) ≤ O( τ )R2 (x)1/2 ≤ O( ζ(E) τ ) inf R2 (x)
x

1/2
p
p
(2)
≤ O( ζ(E) τ h2 ) w.h.p.
= O( ζ(E) τ ) λ2

6.14

Proof of Theorem 4.6

First, according to Step 3, we have
Q1 (z k+1 ) − λ̂k hz k+1 , g k i ≤ Q1 (z k ) − λ̂k hz k , gk i.
It is also straightforward to check that gk satisfies
h1, g k i = 0,

hxk , gk i = kxk kℓ1 ,µ .
28

Therefore,
Q1 (xk+1 ) − λ̂k hxk+1 , gk i = Q1 (z k+1 ) − λ̂k hz k+1 , gk i ≤ Q1 (z k ) − λ̂k hz k , gk i

= Q1 (xk ) − λ̂k hxk , gk i = Q1 (xk ) − λ̂k kxk kℓ1 ,µ = 0,

which implies
R1 (xk+1 ) ≤ λ̂k

k+1 k
k
k+1 , g k i
hxk+1 , gk i
ℓ1 ,µ kg kℓ∞ ,µ−1 1) k
k hx
k kx
=
λ̂
≤
λ̂
≤ λ̂ .
Z1,µ (xk+1 )
kxk+1 kℓ1 ,µ
kxk+1 kℓ1 ,µ

Here, 1) follows from Lemma 3.11 which implies kg k kℓ∞ ,µ−1 ≤ 1. This proves the claimed result.

6.15

Proof of Theorem 4.7

If the norm kzk stands for kzk2 , the duality result holds since
X
λ
hye , zi − λ̂k hz, g k i + (kzk22 − 1)
z λ≥0 ye ∈ϑe Be
2
e
X
λ
hye , zi − λ̂k hz, g k i + (kzk22 − 1)
= max max min
ye ∈ϑe Be λ≥0 z
2
e
P
k e∈E ye − λ̂k gk k22 λ
= max max −
−
ye ∈ϑe Be λ≥0
2λ
2
X
k k
ye − λ̂ g k2 .
= max −k

min Q1 (z) − λ̂k hz, gk i = min max max

z:kzk2 ≤1

ye ∈ϑe Be

e∈E

λ̂k g k −

P

ye

e∈E
The relationships between the primal and dual variables read as z =
and λ =
λ
P
k
k
k e∈E ye − λ̂ g k2 .
If the norm kzk stands for kzk∞ , let z ′ = (z + 1)/2. As Q1 (z ′ ) = Q(z)/2 and hgk , z ′ i =
k
hg , zi/2, we have

1
[Q1 (z) − λ̂k hz, gk i]
2
z:kzk∞ ≤1
min

⇐⇒

min

z ′ :z ′ ≤[0,1]N

Q1 (z ′ ) − λ̂k hz ′ , gk i

The right hand side essentially reduces to the following discrete optimization problem (Proposition 3.7 [33])
X
min
ϑe we (S) − λ̂k gk (S),
S⊆[N ]

e

where the primal and dual variables satisfy zv′ = 1, if v ∈ S, or 0 if v 6∈ S.

29

