A hypergraph is a graph whose "edges" (hyperedges) can join any number of vertices at once: a circuit net wiring ten gates, a document containing a word, a set of animals sharing a trait. Splitting such data into two groups with spectral methods is now well understood. Spectral methods read cluster structure off the eigenvectors of a Laplacian matrix, and a Cheeger inequality guarantees that the resulting cut is nearly as sparse as the best one. These guarantees hold even for rich hypergraph models in which each vertex matters differently in each hyperedge. Splitting into $k>2$ groups is still done by repeated halving, and every paper that proves a two-way guarantee lists direct $k$-way splitting as open.
This note argues that the missing piece is not a better eigensolver. It is the right cost for cutting a hyperedge into many pieces. With two groups, a cut hyperedge is simply cut. With $k$ groups, a ten-vertex net can land in two pieces or in six, and circuit partitioners have long charged it by the number of pieces it touches. The pairwise graphs that current spectral hypergraph methods reduce to charge it by the number of separated vertex pairs, which is a different quantity. We propose a direct $k$-way method that takes geometry from a linear spectral embedding and hyperedge structure from a rounding step that charges each hyperedge per piece touched. We also propose a buffered $k$-way Cheeger bound for this objective.
Core Claim
For a partition $S_1,\dots,S_k$ of a hypergraph with a splitting function $w_e$ per hyperedge, the natural $k$-way cost of hyperedge $e$ is $\sum_{i=1}^k w_e(S_i\cap e)$. Here $w_e(A)$ is the penalty for separating the part $A$ of $e$ from the rest of $e$, as in the submodular hypergraphs of Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering. With the all-or-nothing penalty, summing over pieces gives the sum-of-external-degrees objective optimized by Multilevel k-way Hypergraph Partitioning. For $k=2$ this cost agrees, up to constants, with what graph reductions measure. For $k>2$ it does not.
Our claim has an empirical part and a theoretical part. Empirically, a spectral method that rounds against this per-piece cost should beat reduce-to-a-graph pipelines by a margin that is zero at $k=2$ and grows with both $k$ and hyperedge size. Theoretically, the buffered orthogonal-separator argument of Higher-Order Cheeger Inequality for Partitioning with Buffers can be lifted to this objective. That paper proves, on ordinary graphs, that $k$-way expansion with small buffer sets is at most $O_\delta(1)\cdot\frac{\log k}{\epsilon}\lambda_{\lfloor(1+\delta)k\rfloor}$. The lifted bound would carry an extra factor depending on the maximum hyperedge size $r$. The central theoretical question is whether that factor can be held to $O(\log r)$. That would match the approximation factor Spectral Properties of Hypergraph Laplacian and Approximation Algorithms shows is optimal for its $k$-way problem under the Small-Set Expansion hypothesis.
Why This Is Not the Obvious Extension
The obvious move is to take the edge-dependent vertex weight (EDVW) model and compute $k$ eigenvectors instead of one. In the EDVW model a vertex has a separate weight in each hyperedge. Hypergraphs as Weighted Directed Self-Looped Graphs shows its random walk is equivalent to a weighted directed graph with self-loops, and proves a two-way Cheeger inequality for its HyperClus-G algorithm. Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering reduces EDVW hypergraphs to directed graphs with auxiliary nodes and solves the 1-Laplacian by an inverse power method. Both papers leave $k$-way splitting open.
We suspect this extension is largely a corollary. The stationary flow of a directed walk is a circulation, so conductance measured under that flow equals conductance on a symmetrized undirected graph. Graph $k$-way results would then transfer directly, including the buffered bound and the greedy rounding of Spectral concentration and greedy k-clustering, which picks cluster centers by ball covering. What does not transfer is the objective. Any reduction to pairwise or auxiliary-node graphs charges a hyperedge split into $j$ pieces by a pair count or a star count, not by $j$. Our contribution lives in that difference, and the $k=2$ null result below tests it directly.
We also deliberately avoid nonlinear higher-order spectra. Chan et al. prove that higher eigenvalues of the diffusion hypergraph Laplacian do not behave like linear ones, and they fall back on "procedural minimizers". Generalizing p-Laplacian: spectral hypergraph theory and a partitioning algorithm proves a higher-order Cheeger inequality but computes only the second eigenvector, citing severe algebraic complexity. We read these results as a constraint on design. The nonlinearity should enter through rounding and local refinement, not through the eigenspace.
Research Program
The method has three stages. The first stage computes the bottom $\lceil(1+\delta)k\rceil$ eigenvectors of the linear normalized EDVW Laplacian, the one underlying HyperClus-G. It then scales vertex coordinates by stationary measure, as in the degree scaling of the greedy $k$-clustering paper. This stage costs a standard sparse eigensolve.
The second stage is the rounding. We sample orthogonal separators, which are random sets of embedded points that are close together and nearly orthogonal to the rest, and carve out $k$ pieces while leaving a small buffer. The difference from the graph version is how a hyperedge is charged. It is charged by the number of pieces its non-buffer vertices touch, weighted by $w_e$. The analysis must bound the expected number of pieces a hyperedge touches in terms of its spectral spread $\max_{u,v\in e}\|x_u-x_v\|^2$. We expect this step to introduce the dependence on $r$.
The third stage assigns buffer vertices greedily to minimize the per-piece cost, which yields a full partition. It then runs a short local refinement on the boundary using the 1-Laplacian inverse power method of Zhu and Segarra, restricted to pairs of adjacent pieces. This reuses a tight two-way nonlinear tool only where two-way questions actually arise.
The theoretical work has three targets. The first is the buffered upper bound for per-piece expansion. The second is a matching lower bound in terms of $\lambda_k$, of the form the buffered-graph paper proves. The third is a construction, with hyperedges of size $r$, showing how badly pairwise reductions can misrank $k$-way partitions. If the $r$-dependence turns out to be polynomial rather than logarithmic, we will report that as the finding.
Baselines
The naive reference point is recursive bisection with HyperClus-G, splitting the largest remaining piece until there are $k$. This is what the EDVW literature does today, so any direct method must beat it.
The strongest spectral competitor is the symmetrization pipeline. It forms the symmetrized directed graph of the EDVW walk, computes the same $\lceil(1+\delta)k\rceil$ eigenvectors, and rounds with both $k$-means and the greedy ball-covering rule of Spectral concentration and greedy k-clustering. It is strongest because it is what our own analysis suggests is "already solved". It shares our embedding exactly, so any gap isolates the objective and the rounding.
For clustering accuracy we also run clique expansion with standard $k$-way spectral clustering. Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering shows clique expansion distorts cuts in the two-way case.
The strongest combinatorial competitor is hMETIS-Kway, the multilevel $k$-way partitioner of Multilevel k-way Hypergraph Partitioning. It coarsens the hypergraph, partitions the coarsest level, and greedily refines while uncoarsening. On ISPD98 it reports cutting hyperedges 15% to 23% better than K-PM/LR, and 4.8% to 7.6% better sum of external degrees than its own recursive-bisection variant, hMETIS-RB. No reported result was found on Lacuna for HyperClus-G, submodular IPM, or the generalized p-Laplacian method at $k>2$, so those comparisons are new measurements.
The key ablation keeps everything in our method fixed but charges hyperedges by separated pairs instead of pieces touched. A second ablation removes the local 1-Laplacian refinement.
Fairness rules apply to every method. All methods receive the same hypergraph, the same balance tolerance, and the same wall-clock budget. Randomized methods get the same number of restarts, with the best run kept by the objective value, not by labels. Hyperparameters, which are $\delta$, $\epsilon$, and the submodular weight, are tuned on held-out synthetic instances only.
Beating the symmetrization pipeline means a statistically significant reduction in per-piece cost and clustering error at $k\ge 4$ across seeds. Beating hMETIS-Kway on ISPD98 means matching its sum of external degrees within a few percent while also providing a certified lower bound. Outright winning there is not required, because the spectral method's value on netlists is the certificate. On EDVW data, hMETIS cannot represent the vertex weights at all.
Why not just…?
Why not just symmetrize the EDVW walk and apply existing graph k-way theory? This is the real threat. For conductance, we believe it does reproduce everything. It fails only if the per-piece objective matters. The decisive test is the ablation that switches the charge from pieces to pairs. At $k=2$ the gap should vanish. On synthetic hypergraphs, the gap should grow with $k$ and with $r$. If it does not grow, the honest conclusion is that direct $k$-way EDVW clustering is a corollary of graph results, and we will publish that.
Why not just recursively bisect with HyperClus-G or the 1-Laplacian? Recursive halving commits early and cannot see the $k$-way structure. It also mishandles clusters of very different sizes, as Clustering and Community Detection with Imbalanced Clusters documents. On hypergraphs, the direct-versus-recursive gain of 4.8% to 7.6% reported for hMETIS suggests the effect is real but modest. We therefore include imbalanced synthetic instances, where the difference should be largest, rather than assuming a large gain.
Why not just use hMETIS-Kway? On unweighted netlists it may win, and we treat it as the target to approach. It cannot represent edge-dependent vertex weights or submodular split penalties, and it gives no bound relative to the optimum. Our method supplies the spectral lower bound $\lambda_k$ as a certificate. We report how close each partition comes to it.
Why not compute nonlinear higher eigenvectors directly? Chan et al. prove these do not behave like linear eigenvectors. Saito and Herbster report the algebra is prohibitive. We confine nonlinear computation to two-way boundary refinement, where it is known to be tight and tractable.
Proposed Experiments
The first experiment uses a synthetic hypergraph block model with planted $k$-way structure. It sweeps $k\in\{2,4,8,16\}$ and hyperedge size $r\in\{3,5,10,20\}$, and includes an imbalanced variant. The measures are the per-piece cost, the pair-count cost, and label recovery. The predicted signature is no advantage at $k=2$ and an advantage over the symmetrization pipeline that grows with $k$ and $r$. This experiment decides the project.
The second experiment uses UCI categorical data with natural $k>2$: Zoo (7 classes), Letter, and Covertype. It adds 20 Newsgroups and RCV1 with EDVW weights built as in Zhu and Segarra. The measures are clustering error, $k$-way normalized cut, and runtime.
The third experiment uses the ISPD98 netlists. It measures sum of external degrees and the $(K-1)$ connectivity metric at 8, 16, and 32 ways against hMETIS-Kway and hMETIS-RB, and reports the gap between each partition and the spectral lower bound.
A final diagnostic checks the theory directly. For each instance we record the empirical ratio of per-piece expansion to $\lambda_{\lfloor(1+\delta)k\rfloor}$ as $r$ varies. This shows whether the observed dependence looks logarithmic or polynomial in $r$, and so indicates which bound to try to prove.
References
- Submodular Hypergraphs: p-Laplacians, Cheeger Inequalities and Spectral Clustering
- Multilevel k-way Hypergraph Partitioning
- Higher-Order Cheeger Inequality for Partitioning with Buffers
- Spectral Properties of Hypergraph Laplacian and Approximation Algorithms
- Hypergraphs as Weighted Directed Self-Looped Graphs: Spectral Properties, Clustering, Cheeger Inequality
- Hypergraphs with edge-dependent vertex weights: p-Laplacians and spectral clustering
- Spectral concentration and greedy k-clustering
- Generalizing p-Laplacian: spectral hypergraph theory and a partitioning algorithm
- Clustering and Community Detection With Imbalanced Clusters