PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Pan Li, Olgica Milenkovic

arXiv:1803.03833v4cs.LGcs.DMcs.DScs.SI

TL;DR

Higher-order clustering relations can have different cut weights, while common spectral approaches project hypergraphs to graphs under a uniform-cut-weight assumption. The paper defines p-Laplacians for submodular hypergraphs, derives spectral theorems, and proposes SDP-based 2-Laplacian and inverse-power 1-Laplacian eigenvalue algorithms. For a connected submodular hypergraph and p > 1, an eigenvector for eigenvalue λ_k^(p) with multiplicity r induces at most k+r−1 strong and k weak nodal domains.

  • Problem

    Higher-order clustering relations can have different cut weights, while common spectral approaches project hypergraphs to graphs under a uniform-cut-weight assumption.

    Source: §1 · p. 1

  • Method

    The paper defines p-Laplacians for submodular hypergraphs, derives spectral theorems, and proposes SDP-based 2-Laplacian and inverse-power 1-Laplacian eigenvalue algorithms.

    Source: §1 · p. 2

  • Results

    For a connected submodular hypergraph and p > 1, an eigenvector for eigenvalue λ_k^(p) with multiplicity r induces at most k+r−1 strong and k weak nodal domains.

    Source: §3.1 · p. 8

  • Takeaways & Limitations

    The theory provides nodal-domain and Cheeger results for submodular hypergraphs, while proposed clustering methods learn the second-smallest eigenvalues of the 2- and 1-Laplacians.

    Source: §1 · p. 2

    The critical points of R_p characterize eigenpairs only for p > 1, and the k-way Cheeger approximation for k ≠ 2 remains open.

    Source: §3 · p. 6, §4 · p. 10

Abstract

from arXiv · show

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 extends naturally from graphs to hypergraphs when clustering depends on higher-order vertex relations, but conventional clique expansion assumes uniform cut weights and can distort cuts. The paper develops submodular-hypergraph spectral theory and clustering algorithms, while identifying wider applications as future possibilities.

1 Introduction

  • Submodular hypergraphs model higher-order relations by assigning different submodular weights to different hyperedge cuts, unlike homogeneous hypergraphs’ uniform cut-weight assumption.Clique expansion can approximate these cuts, but its projection may cause large distortion and the graph-clustering step is only quadratically optimal.Source: §1 · p. 1
  • Earlier hypergraph clustering work either avoids expansions without investigating operator spectra or uses a homogeneous-hypergraph 2-Laplacian and an SDP whose complexity scales with the largest hyperedge.The paper situates its work against approaches by Hein et al. and Louis.Source: §1 · p. 2
  • The paper defines p-Laplacians for submodular hypergraphs, generalizes nodal-domain theorems and higher-order Cheeger inequalities, and proposes spectral clustering algorithms for 1- and 2-Laplacians.Hypergraph p-Laplacians are set-valued operators, requiring set-theoretic definitions of operators and eigenvalues.Source: §1 · p. 2
  • The 2-Laplacian eigenvalue algorithm uses an SDP framework and has quadratic optimality with an O(ζ(E)) approximation constant, where ζ(E) is the largest hyperedge size.The 1-Laplacian algorithm uses the inverse power method and has convergence guarantees, but no performance guarantees; it performs well empirically even for large hyperedges.Source: §1 · p. 2

1.1 Other related works and applications

  • The paper identifies potential applications of submodular Laplacians to signal-processing frames and network embeddings, but presents these as directions for investigation.It also notes that spectral theory for the broader concept of submodularity over edges remains unclear.Source: §1.1 · pp. 2–3
  • The paper’s stated organization moves from preliminaries and spectral theory to clustering algorithms and experiments, with proofs in the Appendix.The introduction also points to follow-up work on min-cut and PageRank for submodular hypergraphs [22] [34], and distinguishes an independent 2-Laplacian study [35].Source: §1.1 · p. 3

2 Mathematical Preliminaries

The preliminaries establish graph and hypergraph cut quantities, define submodular hypergraphs through cut-dependent weights, and introduce the operator and submodular-function tools used later. They also situate the spectral challenges of extending Laplacians to these hypergraphs.

2 Mathematical Preliminaries

  • Graph cuts use edges crossing a bipartition, with cut weight and conductance defined from boundary weights and vertex volumes; the k-way Cheeger constant extends the minimum-conductance partition concept.Graph Laplacians provide spectral bounds on the Cheeger constant.Source: §2 · pp. 3–4

2.2 Laplacian Operators for Hypergraphs

  • Graph p-Laplacians generalize graph Laplacians, while existing hypergraph work includes total-variation-based operators and quadratic variants with Cheeger-type bounds.For homogeneous hypergraphs, the cited quadratic result has an additional log ζ(E) approximation difficulty; learning spectra of generalizations can be more challenging.Source: §2 · p. 4, §2.2 · p. 5

2.1 Submodular Hypergraphs

  • A homogeneous hypergraph assigns each hyperedge cut the same weight, whereas submodular hypergraphs associate each hyperedge with a normalized, symmetric submodular cut-weight function.The homogeneous case is recovered when every nontrivial cut of each hyperedge has weight 1.Source: §2.1 · p. 4
  • Submodular-hypergraph vertex degrees sum incident hyperedge maximum weights, while vertex volumes use the supplied vertex weights and boundaries comprise hyperedges meeting both sides of a cut.Hypergraph normalized cuts and Cheeger constants are defined analogously to their graph counterparts.Source: §2.1 · p. 4

2.2 Laplacian Operators for Hypergraphs

  • The paper introduces p-Laplacians for hypergraphs; their subdifferentials are set-valued, so the spectral formulation must account for sets of operator values.For the Lovász extension associated with a hyperedge, subgradients vanish outside that hyperedge.Source: §2.2 · p. 4, §2.3 · p. 5

2.3 Relevant Background on Submodular Functions

  • The Lovász extension of a submodular set function is convex and equals the maximum inner product over its base polytope; its subdifferential is a set of maximizers.For each hyperedge, its Lovász extension and base polytope are restricted to that hyperedge’s vertices.Source: §2.3 · p. 5

3 p-Laplacians for submodular hypergraphs and the spectra

The section develops a variational spectral theory for submodular-hypergraph p-Laplacians, then establishes nodal-domain bounds and higher-order Cheeger inequalities. The results distinguish p=1 from p>1 and connect p=1 and p=2 to the tightest bounds and the classical Cheeger inequality, respectively.

3 p-Laplacians for submodular hypergraphs and the spectra

  • Critical points of Q̃p characterize p-Laplacian eigenpairs for every p≥1, while critical points of Rp do so only when p>1.The distinction follows from the nonsmoothness of S1,µ.Source: §3 · p. 6
  • Lusternik-Schnirelman theory applied to Q̃p yields a sequence of critical values that are eigenvalues of the p-Laplacian.The analysis uses Krasnoselski genus for the symmetric functional and constraint set.Source: §3 · pp. 6–7

3.1 Discrete Nodal Domain Theorem for p−Laplacians

  • Boundary-volume connectivity avoids falsely connecting disjoint hyperedges merged into one, and the hypergraph can be reduced while preserving every boundary volume.The usual same-hyperedge connectivity can change under a representation that leaves the submodular hypergraph unchanged.Source: §3.1 · p. 8
  • For connected submodular hypergraphs and p>1, an eigenvector at eigenvalue λ_k with multiplicity r has at most k+r−1 strong and k weak nodal domains.The nodal-domain theorem is not established here for p=1; extending it requires critical-point theory on piecewise linear manifolds.Source: §3.1 · p. 8
  • For p>1, nonconstant eigenvectors have at least two weak and strong nodal domains, and those for the second-smallest eigenvalue have exactly two; at p=1 they may have only one.The paper also states that connected hypergraphs have only constant eigenvectors at eigenvalue zero.Source: §3.1 · p. 8

3.2 Higher-Order Cheeger Inequalities

  • The paper relates submodular-hypergraph Cheeger constants to p-Laplacian eigenvalues; homogeneous hypergraphs admit a tighter bound.The p=1 case gives the tightest eigenvalue bounds, while p=2 reduces to the classical Cheeger inequality.Source: §3.2 · p. 9

4 Spectral Clustering Algorithms for Submodular Hypergraphs

The section develops spectral objectives and rounding for submodular-hypergraph clustering, then presents SDP- and IPM-based algorithms for evaluating the 2-Laplacian spectrum and producing partitions.

4 Spectral Clustering Algorithms for Submodular Hypergraphs

  • The 2-Laplacian eigenvalue can be evaluated in polynomial time with provable performance guarantees.Approximations for λ(p)_k when k ≠ 2 remain open.Source: §4 · p. 10
  • Theorem 4.3 rounds a vector minimizing the proposed objective to a partition whose conductance is bounded by c(x) ≤p τ (p−1)/p Rp(x)1/p.The objective characterizes λ(p)_2 and is related to graph objectives in.Source: §4 · pp. 9–10
  • The section proposes an SDP to minimize R2(x), with approximation guarantees, and an IPM to minimize R1(x), which converges but lacks performance guarantees.The SDP may be computationally intensive for large hyperedges; the IPM inner loop uses decomposable submodular minimization.Source: §4 · p. 10

4.1 An SDP Method for Minimizing R2(x)

  • With high probability, Algorithm 1 returns x satisfying c(x) ≤ O(ζ(E)τ h2).The SDP approximation factor is O(ζ(E)) for general submodular hypergraphs, compared with O(log ζ(E)) for homogeneous hypergraphs; its base-polytope complexity motivates the difference.Source: §4.1 · p. 11
  • Algorithm 2 produces a nonincreasing sequence of R1(x) values, and its computationally demanding inner optimization is related to submodular function minimization.The inner problem can be efficiently solved using algorithms for decomposable submodular minimization.Source: §4 · p. 10, §4.1 · p. 11

5 Experiments

In the UCI clustering experiments, IPM-based methods outperform clique expansion, while submodular IPM improves on homogeneous IPM for two datasets and matches it on Mushrooms. The experiments vary submodular weights using α, which controls the treatment of small hyperedge parts.

5 Experiments

  • The experiments use 20Newsgroups, Mushrooms, and Covertype, with Covertype and 20Newsgroups configured as two-way cluster pairings.Each feature defines a hyperedge; numerical features are quantized into 10 equal-size bins before being mapped to hyperedges.Source: §5 · p. 13
  • For the chosen weights, α ≤ 0.04 in all experiments, and α near zero produces homogeneous hyperedge weights.Smaller weights are assigned when a hyperedge is split into parts with min{|S|, |e/S|} < ⌈α|e|⌉.Source: §5 · p. 13
  • IPM-based methods outperform CEM on both clustering error and Cheeger constant; IPM-S improves over IPM-H on 20Newsgroups and Covertype and matches it on Mushrooms.The authors attribute CEM's difficulty with large hyperedges to O(ζ(E)) distortion when approximating submodular weights.Source: §5 · pp. 13–14

A Preliminary Proofs

The preliminary lemmas establish scaling and sign properties of the Lovász extension and relate its subgradients at ordered vectors.

A Preliminary Proofs

  • f(cx) = |c|f(x), while ∇f(cx) = sgn(c)∇f(x) for symmetric submodular F with F([N]) = 0.The proof uses that f is even and its subgradient is odd.Source: A Preliminary Proofs · p. 17
  • The proof also establishes ⟨∇f(x), 1⟩ = 0 for the normalized symmetric function.It follows from F([N]) = 0.Source: A Preliminary Proofs · p. 17
  • Whenever x ⇀ x′, ∇f(x′) ⊆ ∇f(x), and ⟨∇f(x′), x⟩ = f(x).The proof uses an optimizer of the Lovász-extension representation that remains optimal at x.Source: A Preliminary Proofs · p. 17

B Proof for Equation (3)

The proof characterizes subgradients of the Lovász extension through maximization over its base polytope.

B Proof for Equation (3)

  • A maximizer y′ of ⟨y, x⟩ over B is a subgradient of f at x.The maximizing property gives f(x) = ⟨y′, x⟩ and f(x′) ≥ ⟨y′, x′⟩ for every x′.Source: B Proof for Equation (3) · p. 17
  • Every subgradient y′ at x satisfies y′([N]) = 0 and belongs to B.The proof obtains the zero-sum condition using invariance of f under shifts by ±1[N].Source: B Proof for Equation (3) · p. 17

C Proof for Theorem 3.4

The proof connects critical points of the constrained p-Laplacian objective to eigenvectors, then shows how zero-weight cuts can be split without changing volume.

C Proof for Theorem 3.4

  • For p > 1 and p = 1, a point is critical for ˜Qp exactly when it is an eigenvector of △p, with eigenvalue equal to the critical value.The proof treats p > 1 on a differentiable symmetric manifold and p = 1 on a piecewise-linear manifold with a cone tangent space.Source: C Proof for Theorem 3.4 · p. 18
  • For p = 1, membership in the set on the right does not necessarily imply 0 ∈ ∇Rp(x).Thus that set relation alone does not establish the converse implication in this case.Source: C Proof for Theorem 3.4 · p. 18

D Proof for Lemma 3.9

  • A hyperedge with a nonempty zero-weight subset can be split into two hyperedges with modified submodular weights.Repeating this split yields weights that are positive on every nonempty subset of each hyperedge.Source: D Proof for Lemma 3.9 · p. 18
  • The split preserves each subset’s weighted cut value, so the volume vol(∂S) remains unchanged.The resulting weights are normalized, symmetric, and submodular.Source: D Proof for Lemma 3.9 · p. 19

E Proof for Lemma 3.11

The proof shows that a zero-eigenvalue eigenvector is constant across vertices.

E Proof for Lemma 3.11

  • If x has eigenvalue 0, then Qp(x) = 0 and each hyperedge has fe(x) = 0, forcing x to be constant on each hyperedge.After the weight transformation of Lemma 3.9, hyperedge paths connect every vertex pair, so x is constant across all vertices.Source: E Proof for Lemma 3.11 · p. 19

F Proof for Discrete Nodal Domain Theorems

The proof bounds weak nodal domains through their inclusion in the strong nodal space, then handles the sharper p > 1 bound by analyzing how hyperedges meet overlapping weak domains. These bounds, together with the sign structure of eigenvectors, yield the stated nodal-domain conclusions.

F Proof for Discrete Nodal Domain Theorems

  • The proof of the strong-domain result extends the graph p-Laplacian argument, while the weak-domain result requires modifications for submodular hyperedges.For connected hypergraphs, each hyperedge intersects at most two strong nodal domains with different signs, a key step in the strong-space argument.Source: F Proof for Discrete Nodal Domain… · pp. 19–21
  • For an eigenvalue of index k and multiplicity r, the proof bounds strong nodal domains by k + r − 1 and, for p > 1, weak nodal domains by k.The weak nodal space is contained in the strong nodal space; the sharper p > 1 bound uses a contradiction argument on overlapping weak domains.Source: F Proof for Discrete Nodal Domain… · pp. 19, 21, 22

F.1 Proof for Lemma 3.13

  • For p > 1, an eigenvector for the second-smallest eigenvalue has exactly two weak and two strong nodal domains.A connected hypergraph gives at least two of each, and the nodal-domain theorem supplies the corresponding upper bound.Source: F Proof for Discrete Nodal Domain… · p. 21, §F.1 · pp. 22–23
  • For p = 1, an eigenvector for the second-smallest eigenvalue may have only one weak or strong nodal domain.The proof's zero-sum argument for p = 1 does not rule out an eigenvector whose components are all nonnegative or all nonpositive.Source: §F.1 · p. 23

G Proof for Lemma 3.14

These proof sections establish a weighted centering property, develop bounds for arbitrary and homogeneous submodular weights, and reduce spectral claims to Cheeger and threshold-set arguments. They also use positive and negative parts of vectors in the proof of Theorem 4.3.

G Proof for Lemma 3.14

  • For the centering result, the proof concludes that 0 minimizes the weighted ℓ1 distance from x to a constant vector.It states 0 ∈ arg min_c ∥x − c1∥_{ℓ1,µ}.Source: G Proof for Lemma 3.14 · p. 23

H.1 Arbitrary Submodular Weights

  • For arbitrary submodular weights, the proof bounds the partition-based quantity using Hölder's inequality and the definition of f_e.The displayed argument also invokes Lemma H.1; the excerpt introduces a threshold-set lemma before the lower-bound proof.Source: §H.1 · p. 24

H.2 Homogeneous Weights

  • For homogeneous weights, the proof tightens inequalities by selecting, on each hyperedge, a vertex pair with maximum |x_u − x_v|^p.The pairwise choice is described for the partition used in the argument.Source: §H.2 · p. 26

I Proof of Theorem 4.1

  • For p > 1, the proof identifies λ_2^(p) with inf_x R_p(x).It uses invariance of the quotient under shifts and nonzero rescaling to restrict the infimum to a normalized set.Source: I Proof of Theorem 4.1 · p. 27
  • For p = 1, the proof reduces min_x R_1(x) = h_2 to equality between Lovász extensions and the corresponding cut and volume terms.The cut term follows from Definition 3.1; the remaining step identifies the extension of min{vol(S), vol([N]\S)} with Z_1,µ(x).Source: I Proof of Theorem 4.1 · p. 27

J Proof for Theorem 4.3

  • For p > 1, the proof of Theorem 4.3 splits a vector into positive and negative parts and applies Lemma H.2 to each part.The argument uses that the threshold-set costs of the positive and negative parts are at least the cost of the original vector.Source: J Proof for Theorem 4.3 · p. 28

K Proof for Lemma 4.4

The proof of Lemma 4.4 identifies a setting in which the Gaussian projection incurs distortion proportional to hyperedge size. The stated distortion term is tight under the described equal-norm, orthogonality conditions.

K Proof for Lemma 4.4

  • Under equal ℓ2 norms and mutual orthogonality of the embedded vectors, Gaussian projection causes distortion Θ(|e|).The passage notes that the O(ζ(E)) distortion term arises through inequalities (22) and (23), which are tight in this case.Source: K Proof for Lemma 4.4 · p. 29

L Proof of Theorem 4.5

The proof of Theorem 4.5 combines earlier theorems and lemmas. The following proof sections establish a norm bound for g_k and recast a dual optimization in discrete terms.

L Proof of Theorem 4.5

  • The passage says that combining Theorem 4.1, Theorem 4.3, Lemma 4.4, and Theorem (3.15) yields an ensuing conclusion, but the conclusion itself is not shown.Source: L Proof of Theorem 4.5 · p. 30

M Proof of Theorem 4.6

  • The passage states that item 1 follows from Lemma 3.11, which implies ∥gk∥ℓ∞,µ−1 ≤ 1; it then says this proves the claimed result.Source: M Proof of Theorem 4.6 · p. 30

N Proof of Theorem 4.7

  • The proof of Theorem 4.7 reduces the right-hand optimization to a discrete optimization problem.The passage attributes this reduction to Proposition 3.7 and specifies that the primal and dual variables encode membership in a set S.Source: N Proof of Theorem 4.7 · p. 30

Related papers

Loading 1803.03833v4…