Many real datasets are made of groups rather than pairs. Examples include documents that share a word, players in the same match, and circuit cells on the same net. A hypergraph records each group as a single "hyperedge", and recent work lets each member carry its own weight inside each group. These are called edge-dependent vertex weights (EDVW): a document that uses a word heavily counts more in that word's hyperedge than one that mentions it once. Spectral methods for cutting such hypergraphs now have tight guarantees, but only for splitting into two parts. Anyone who wants $k > 2$ clusters must either split in two repeatedly or take $k$ eigenvectors of a linear operator and run $k$-means. Both workarounds discard exactly the properties that made the two-way theory attractive.
We propose a direct $k$-way method for EDVW hypergraphs built on the 1-Laplacian. The 1-Laplacian is the nonlinear operator whose two-way minimum equals the best cut ratio exactly, with no loss from relaxation. The key observation is that the exact two-way identity extends to $k$ parts if the $k$ continuous cluster indicators are required to have disjoint supports, meaning no vertex may carry nonzero weight in two clusters at once. Under that constraint, the continuous problem has the same optimum as the discrete $k$-way min–max cut. Each continuous solution also rounds to $k$ disjoint clusters with no loss in the worst cluster's cut ratio. We then build a practical solver that starts from the $k$ eigenvectors of the linear EDVW Laplacian and refines them under the disjoint-support constraint. Finally, we test whether this buys anything over the obvious linear-plus-$k$-means pipeline, and in which regime.
Core Claim
Fix a hypergraph whose vertices carry weights $\gamma_e(v)$ inside each hyperedge $e$. Following Hypergraph cuts with edge-dependent vertex weights, let the penalty for splitting $e$ be a submodular function $w_e(S)$ built from concave functions of the summed member weights. Write $\mathrm{cut}(S)=\sum_e w_e(S\cap e)$ and $\mathrm{vol}(S)$ for the degree volume. The $k$-way min–max Cheeger constant is
$$\rho_k=\min_{S_1,\dots,S_k \text{ disjoint, nonempty}}\ \max_i \frac{\mathrm{cut}(S_i)}{\mathrm{vol}(S_i)}.$$
Let $\mathrm{TV}(f)$ be the Lovász extension of the cut function, a convex function of a vertex-valued vector $f$ that equals $\mathrm{cut}(S)$ when $f$ is the 0/1 indicator of $S$. For nonnegative $f_1,\dots,f_k$ with pairwise disjoint supports, we claim
$$\rho_k=\min_{f_1,\dots,f_k\ge 0,\ \mathrm{supp}(f_i)\cap\mathrm{supp}(f_j)=\emptyset}\ \max_i \frac{\mathrm{TV}(f_i)}{\|f_i\|_{1,\mathrm{vol}}},$$
where $\|f\|_{1,\mathrm{vol}}$ is the volume-weighted $\ell_1$ norm. The argument is short.
- Indicators of any disjoint $k$-partition are feasible, so the continuous minimum is at most $\rho_k$.
- The coarea property of Lovász extensions of submodular functions, which Hypergraphs with Edge-Dependent Vertex Weights: Spectral Clustering based on the 1-Laplacian uses for its exact two-way result, guarantees that each $f_i$ has a level set whose ratio is no worse than $f_i$'s.
- Level sets of functions with disjoint supports are themselves disjoint, so these $k$ level sets form a feasible discrete solution.
This gives the first exact $k$-way relaxation for EDVW hypergraphs. It is linear rather than quadratic, which contrasts with the $h^2/2$ loss in Cheeger's inequality for the linear Laplacian.
The difficulty moves from the operator into the constraint. Optimizing over disjoint supports is combinatorial, so the claim we must defend empirically is narrower: a good local solver for this problem, started from linear spectral output, finds better $k$-way cuts and better clusters than the alternatives. We expect the advantage to concentrate where linear methods are known to be weak. These are imbalanced cluster sizes, the weakness emphasized in Clustering and Community Detection with Imbalanced Clusters, and heavy-tailed degrees, where the greedy rounding bounds of Spectral concentration and greedy k-clustering grow with the maximum degree.
Relation to Prior Work
Three EDVW papers motivate the work and supply its machinery, and all stop at $k=2$.
- Random Walks on Hypergraphs with Edge-Dependent Vertex Weights shows that without edge-dependent weights a hypergraph random walk collapses to a weighted clique graph. That result is the reason EDVW structure is worth preserving at all.
- The Zhu–Li–Segarra line (Hypergraphs with Edge-Dependent Vertex Weights: Spectral Clustering based on the 1-Laplacian, Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering) supplies the submodular splitting functions, the graph-reducible gadgets and the inverse-power solver using proximal first-order methods (FISTA, PDHG). We reuse all three, but replace the single-vector problem with a coupled $k$-vector problem.
- Hypergraphs as Weighted Directed Self-Looped Graphs gives a linear EDVW Laplacian with a two-way Cheeger inequality (HyperClus-G) and names $k$-way analysis as open. We use its first $k$ eigenvectors as our initialization and as our main competitor.
One paper constrains the design. Spectral Properties of Hypergraph Laplacian and Approximation Algorithms shows that higher eigenvalues of a nonlinear hypergraph Laplacian lose their classical meaning and must be replaced by procedural minimizers. This looks like a direct objection to a nonlinear $k$-way method, and we take it seriously. Our formulation never asks for a third or $k$-th nonlinear eigenvector. It replaces the orthogonality that fails in the nonlinear setting with disjointness of supports, which survives level-set rounding. Disjointness is the reason the identity above holds while higher-order identities do not.
Other $k$-way hypergraph methods avoid EDVW or the 1-Laplacian.
- Consistency of spectral hypergraph partitioning under planted partition model and Hypergraph Spectral Clustering in the Weighted Stochastic Block Model prove $k$-way consistency, but only after flattening hyperedges into pairwise or star matrices.
- Hypergraph Modeling via Spectral Embedding Connection handles $k$ clusters only for even-order uniform hypergraphs.
- Multilevel k-way Hypergraph Partitioning (hMETIS-Kway) and SHyPar are strong combinatorial $k$-way partitioners. Neither models unequal membership, and SHyPar uses spectral information only to decide which vertices to merge during coarsening.
We do not claim to beat these partitioners at their own task, balanced VLSI cuts. We claim to give the right objective, and a competitive solver, when membership weights carry the signal.
Research Program
Solver. We alternate two steps.
- Continuous step. Given a current assignment of vertices to cluster supports, each $f_i$ is updated by one inner iteration of the Zhu et al. inverse power method, restricted to its own support. These $k$ problems are independent and convex, so they run in parallel.
- Support step. Each vertex moves to the cluster whose ratio it lowers most, scored by the vertex's share of the Lovász-extension subgradient. This is the continuous analogue of hMETIS-Kway's greedy $k$-way refinement.
Supports are initialized from the $k$ eigenvectors of the HyperClus-G Laplacian, rounded by both $k$-means and greedy ball search. The objective never increases, because both steps are descent steps on the min–max ratio. A smoothed sum-of-ratios variant will be compared against the max. Vertices left outside all level sets after rounding are assigned greedily, and we will report how much the final cut ratio degrades as a result. The theory does not control this step, so it must be measured.
Analysis. We will prove the identity above, a monotone-descent result for the alternating scheme, and a bound on the extra cost of assigning leftover vertices in terms of their volume. We will not claim a $k$-way bound in terms of $\lambda_k$, which Simple and Scalable Constrained Clustering notes remains elusive.
Baselines
Naive reference points. These are random balanced $k$-partitions and clique-expanded spectral clustering using the first $k$ eigenvectors with $k$-means. The clique version tells us whether hyperedge structure helps at all. The EDVW papers indicate it should: on Halo 2 a hypergraph walk reached 71.1% match-prediction accuracy versus 61.1% for the clique graph (Random Walks on Hypergraphs with Edge-Dependent Vertex Weights).
Linear EDVW spectral $k$-way (main competitor). This is the first $k$ eigenvectors of the HyperClus-G Laplacian, rounded with $k$-means using 50 random restarts and separately with greedy ball rounding from Spectral concentration and greedy k-clustering. It is the strongest competitor because it uses the same EDVW information and is the obvious extension anyone would try. The file gives no extracted scalar for HyperClus-G; its reported advantage over the STAR++ and CLIQUE++ expansions in NCut and F1 is shown only in figures.
Recursive 1-Laplacian bisection. This applies the exact two-way solver of Zhu et al. recursively until $k$ parts exist, using the same edge-weighting parameter $\alpha$ and the same solver iteration budget.
hMETIS-Kway and KaHyPar. These run on the hypergraph with EDVW summarized as per-hyperedge weights. On ISPD98, hMETIS-Kway is reported to give 4.8% to 7.6% better sum of external degrees than recursive hMETIS and 15% to 23% better hyperedge cut than K-PM/LR (Multilevel k-way Hypergraph Partitioning). SHyPar reports a 22.53% improvement for 20-way partitioning on Titan23.
Planted-partition spectral method. This is the method of Ghoshdastidar and Dukkipati, which reports error 0.11 on Mushroom and 0.12 on Congressional Voting. Both are two-class datasets, so they serve only as sanity anchors.
Fairness and ablations. All spectral methods share the same hypergraph construction, $\alpha$ grid and wall-clock budget, and are tuned on a held-out split. Two ablations isolate the key ingredient:
- Ablation (a): our solver with the 1-norm objective replaced by the 2-norm Rayleigh quotient under the same disjoint-support refinement. This separates "nonlinear operator" from "extra local refinement".
- Ablation (b): our solver with $\gamma_e(v)$ set uniform. This separates EDVW from the $k$-way machinery.
What counts as beating the baselines. On EDVW benchmarks, our method must achieve lower $k$-way min–max ratio and lower clustering error than the best-tuned linear competitor across five seeds, with non-overlapping confidence intervals. It must also beat ablation (a).
Why not just…?
Why not just take $k$ eigenvectors of the linear EDVW Laplacian and run $k$-means? This is the real threat. On well-separated, balanced clusters it may tie us, since the quadratic Cheeger loss matters little when gaps are large. Its known weaknesses are imbalance and the sensitivity of $k$-means initialization, as discussed in Strong Consistency, Graph Laplacians, and the Stochastic Block Model. Ablation (a) and the imbalance sweep below settle the question directly. If the linear pipeline matches us everywhere once given equal refinement, we will report that the exact $k$-way identity has no practical payoff.
Why not just bisect recursively with the existing exact two-way 1-Laplacian? Each split is exact, but errors made by early splits cannot be undone, and balanced splits shear through small clusters (Clustering and Community Detection with Imbalanced Clusters). The combinatorial analogue of this comparison already favors direct $k$-way methods: hMETIS-Kway beats hMETIS-RB on sum of external degrees. We test this on planted partitions with geometrically decaying cluster sizes, where recursive splitting should fail first.
Why not just encode membership weights as hyperedge weights and call hMETIS or KaHyPar? Those tools are fast and excellent at balanced cuts. Collapsing $\gamma_e(v)$ to one number per hyperedge, however, discards exactly the within-edge asymmetry that Zhu et al. found matters: performance degrades when $\alpha=0$ on 20 Newsgroups and Covtype. On unweighted circuits we expect these partitioners to win, and we report that honestly.
Why not just train a hypergraph neural network? Clustering here is unsupervised, and DHG-Bench reports that 8 of 17 models run out of memory on Yelp and that the models are fragile to feature noise. We include HGNN embeddings followed by $k$-means only as a secondary point of comparison.
Proposed Experiments
EDVW clustering. The datasets are 20 Newsgroups and RCV1 (documents as vertices, words as hyperedges, tf-idf weights as $\gamma_e(v)$), Covtype (binned features), and Digit-24, Letter, Zoo and Car. We use the true class count $k$ (from 4 to over 20). Metrics are clustering error, NMI and achieved $\rho_k$. No exact reported numbers for EDVW clustering error on 20 Newsgroups, Covtype or RCV1 were found on Lacuna, so all baselines will be rerun.
Decisive synthetic check. We use an EDVW planted partition with $k\in\{4,8,16\}$, cluster-size imbalance ratio swept from 1 to 20, and power-law vertex degrees. The prediction is specific: the gap between our method and the linear competitor should widen with imbalance and with degree tail heaviness. If it stays flat, the claimed mechanism is wrong.
Stress test. On ISPD98 and Titan23 at $k\in\{8,16,20\}$ with uniform weights, we report hyperedge cut against hMETIS-Kway and SHyPar. The goal is to measure the cost of a spectral solver on balanced partitioning, not to win.
Scaling. Runtime is measured against $n$ and $k$, with the solver's $k$ parallel subproblems compared to the $\tilde{O}(mk)$ fast spectral clustering of Dey et al..
References
- Hypergraph cuts with edge-dependent vertex weights
- Hypergraphs with Edge-Dependent Vertex Weights: Spectral Clustering Based on the 1-Laplacian
- Clustering and Community Detection With Imbalanced Clusters
- Spectral concentration and greedy k-clustering
- Random Walks on Hypergraphs with Edge-Dependent Vertex Weights
- Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering
- Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality
- Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
- Consistency of spectral hypergraph partitioning under planted partition model
- Hypergraph Spectral Clustering in the Weighted Stochastic Block Model
- Hypergraph Modeling via Spectral Embedding Connection: Hypergraph Cut, Weighted Kernel k-Means, and Heat Kernel
- Multilevel k-way Hypergraph Partitioning
- SHyPar: A Spectral Coarsening Approach to Hypergraph Partitioning
- Simple and Scalable Constrained Clustering: a Generalized Spectral Method
- Strong Consistency, Graph Laplacians, and the Stochastic Block Model
- DHG-Bench: A Comprehensive Benchmark for Deep Hypergraph Learning