Many real datasets record group interactions rather than pairs: a circuit net touches a dozen gates, and a paper has five authors. A hypergraph stores each group as one "hyperedge". The natural way to split such data into a tight cluster and the rest is the hypergraph Cheeger cut, a ratio that charges a hyperedge whenever the cut separates any of its members. On ordinary graphs this discrete ratio has an exact continuous counterpart: minimizing a total-variation (sum of absolute differences) ratio over real-valued node scores gives the same answer. That continuous problem is still non-convex, and its solvers get stuck at whatever local minimum their starting point leads to. On hypergraphs we have proofs about this relaxation but almost no measurements of how often, or how badly, solvers get stuck.
We propose to escape these traps by continuation in the shape of the hyperedge penalty, not by blurring the objective. We start from the penalty that treats a hyperedge as a clique of pairs. That problem is well understood and can be warm-started from a spectral eigenvector. We then deform the penalty step by step into the exact "max minus min" penalty of the true hypergraph cut, tracking the solution along the way. The second half of the work matters as much as the first. We will build a benchmark that measures entrapment directly, using exact optima on small planted instances and best-known references on real hypergraphs. Its central test is whether continuation beats the obvious competitor, many random restarts given the same time budget.
Core Claim
For node scores $x \in \mathbb{R}^n$ and a hyperedge $e$ with weight $w_e$, define the penalty family
$$T_q(x) = \sum_{e} w_e \Big( \sum_{u<v \in e} |x_u - x_v|^q \Big)^{1/q}, \qquad q \in [1,\infty].$$
At $q=1$, $T_q$ is the total variation of the clique expansion, the graph you get by joining every pair inside each hyperedge. At $q=\infty$ it equals $\sum_e w_e(\max_{u\in e}x_u-\min_{v\in e}x_v)$. That second form is the Lovász extension of the all-or-nothing hypergraph cut, meaning the standard continuous extension of a set function to real-valued inputs. The quantity to minimize is the ratio $R_q(x)=T_q(x)/\lVert x-\mathrm{med}(x)\rVert_1$, where $\mathrm{med}(x)$ is the degree-weighted median of the scores. At $q=\infty$, minimizing $R_q$ recovers the exact hypergraph Cheeger cut through the same argument that Szlam and Bresson use for graphs.
Our claim is that solving $R_q$ along an increasing schedule of $q$, warm-starting each stage from the last, reaches lower true hypergraph conductance than three alternatives given equal wall-clock time: solving $R_\infty$ directly from spectral or random starts, clique-expansion solvers, and combinatorial local search. We also claim that the size of this advantage tracks a measurable property of the hypergraph. Specifically, it should grow with hyperedge size and with how much the clique expansion distorts the cut. Every member of the family is a convex, one-homogeneous function of $x$, so each stage is the same kind of fractional problem. Only the endpoint is guaranteed to be an exact relaxation. We state this openly, because the intermediate stages are a path toward the answer, not relaxations of it.
Relation to Prior Work
Three papers motivate the gap. Total Variation, Cheeger Cuts proves that total variation exactly relaxes the Cheeger cut on pairwise graphs. It solves the relaxation with Split-Bregman iterations (a method that splits the non-smooth absolute-value terms into easy subproblems) combined with Dinkelbach's ratio method. The authors also note that the method can be trapped when its eigenvector initialization is poor. We reuse their solver structure, and our $q=1$ stage is essentially their problem. Their work is graph-only, however, and does not address the initialization trap. Cheeger Inequalities for Submodular Transformations gives the hypergraph Cheeger theory and approximation algorithms based on semidefinite programs. It contains no experiments and no scalable solver. We take its exactness viewpoint and test it numerically. Efficient Flow-based Approximation Algorithms for Submodular Hypergraph Partitioning via a Generalized Cut-Matching Game supplies the language of hyperedge cut functions, called polymatroidal cuts. It is also theory without implementation, which places it in the same validation gap.
Two papers supply methods we reuse. Flow-based Algorithms for Improving Clusters casts cluster refinement as fractional programming solved by an accelerated Dinkelbach method over exact max-flow. The authors name the hypergraph extension as future work. We use a hypergraph version only as a final polishing step and as a check for local optimality, not as the contribution. A Theoretical Analysis of Optimization by Gaussian Continuation bounds the quality of continuation solutions and warns that solution paths can disappear at bifurcations. That warning constrains our design. Gaussian blurring has no natural meaning for a discrete ratio defined over a hypergraph, which is why we deform the penalty itself. We will also log every place where tracked solutions jump between basins.
Two further papers mark the space of competitors. Local hypergraph clustering using capacity releasing diffusion is a discrete method that pushes flow across hyperedges. It argues that clique expansion optimizes a biased conductance, which is the distortion our continuation is designed to remove gradually. Combining Two Local Search Approaches to Hypergraph Partitioning escapes discrete traps with random walk moves whose randomness level has to be tuned by hand. Continuation replaces that randomness level with a schedule we can inspect.
To our knowledge from this file, none of these papers solves the hypergraph total-variation ratio at scale or measures how often hypergraph Cheeger solvers end in bad local minima. We cannot rule out work outside this file on hypergraph total variation. For that reason we rest the novelty on the continuation in penalty shape and on the certified entrapment study, not on the existence of a hypergraph total-variation solver.
Research Program
We will build a solver for $R_q$ by proximal splitting. A proximal step for a function is a small optimization that moves a point toward lower values of that function while staying close to where it started. At $q=\infty$, the proximal step for each hyperedge's max-minus-min term can be computed exactly by sorting the scores inside the hyperedge. At $q=1$, the proximal step reduces to the pairwise shrinkage step of Szlam and Bresson. For intermediate $q$ we solve the per-hyperedge proximal step with a few inner iterations. Hyperedges smaller than a cap are expanded explicitly. Larger ones are handled through a sorted representation, so the clique expansion's quadratic growth in edges is never materialized. Dinkelbach's method handles the outer ratio. The schedule runs $q$ through $1, 2, 4, 8,\infty$, and we will tune it once on held-out hypergraphs and then freeze it. After rounding, we threshold the final scores at every cut point (a sweep) and keep the best cut. We then optionally polish that cut with a hypergraph version of the fractional flow refinement.
The analysis has three parts. First, we will measure an entrapment gap on planted hypergraphs that are small enough to solve exactly by integer programming. The gap is the final conductance divided by the optimum, recorded over many starts. Second, on real hypergraphs we will record how often each method lands within 1% of the best cut ever found by any method under a large pooled budget. Third, we will correlate continuation's gain with two quantities: the mean hyperedge size, and the ratio of clique-expansion conductance to true conductance for the best-known cut. This correlation is a falsifiable prediction. If the gain does not grow with distortion, the mechanism we propose is wrong.
Baselines
The naive reference is spectral clustering on the clique expansion, followed by a sweep over the eigenvector. It is fast and convex. Total Variation, Cheeger Cuts reports about 54 seconds for the eigenvector on its MNIST graph, against 214 seconds for Split-Bregman total variation and 7,303 seconds for the p-Laplacian method. Spectral clustering also gives worse cuts on Two Moons and CIFAR-10. We expect it to be the cheapest method and the worst in quality, and we report it in every comparison.
The strongest competitor on our exact question is the same $R_\infty$ solver run without continuation, from spectral and random initializations, with as many restarts as fit in continuation's wall-clock time. This baseline isolates the single ingredient we add, and it shares our code, inner solver, stopping tolerance and rounding. Continuation beats it only if its median conductance is lower over the same seeds and time budget. A difference within the seed-to-seed spread counts as a loss. No result on Lacuna reports hypergraph Cheeger conductance for any solver, so the comparison here is new measurement, not a number to beat.
On clustering quality against ground truth, the strongest published method in the file is the capacity-releasing diffusion of Local hypergraph clustering using capacity releasing diffusion. It reports roughly 10% better precision than MAPPR on YouTube and the best F1 on Math Overflow. We will run their released algorithm on the same seed sets and reach the same cluster volumes. To claim improvement, we need higher F1 on Email-EU, Math Overflow, DBLP and Amazon, or equal F1 at lower conductance.
On partitioning, the reference is the combination of greedy node moves (FM, the Fiduccia-Mattheyses heuristic) with random walk moves from Combining Two Local Search Approaches to Hypergraph Partitioning. It reports a 30% average net-cut reduction over plain FM at 1.7 times the runtime on ISPD98, and 15% fewer cuts at 7% less runtime in its efficiency setting. Per-circuit values are not given in the file. We will reimplement both FM and the hybrid and run them on ibm01 through ibm12 under the same balance constraint. Our method will be adapted to balanced cuts by sweeping with a balance penalty. Beating FM by more than the hybrid's reported 30% at comparable time would count as a win. Matching it would count as parity.
Two ablations complete the set. In the first, the schedule stops at $q=1$ and the cut is then rounded, which amounts to clique-expansion total variation. In the second, every method skips the final flow polish. Together these show whether the gain comes from the path through the penalty family or merely from the endpoint and the polish.
Why not just…?
Why not just expand each hyperedge into a clique and run existing graph solvers? That is our $q=1$ ablation, and it is the start of our path, not a rival design. Local hypergraph clustering using capacity releasing diffusion argues that the expansion optimizes a biased conductance. From Hypergraph Energy Functions to Hypergraph Neural Networks finds that models built on fixed expansions reach about 63% accuracy on Cora co-authorship, against 77.11% for a model that treats hyperedges natively. That evidence comes from supervised classification, not cuts, so it only suggests the effect. The direct test is true hypergraph conductance at $q=1$ versus $q=\infty$, and we expect the gap to shrink to near zero on hypergraphs whose hyperedges are mostly size two.
Why not just run the exact hypergraph solver with many random restarts? This is the most serious threat. If the landscape has few basins, restarts will find the good one cheaply, and continuation adds nothing. We do not argue against this possibility. We test it as the main equal-time baseline above, and we report results separately for each benchmark. A plausible outcome is that restarts suffice on hypergraphs with small hyperedges and fail where hyperedges are large and expansion distortion is high. If restarts match continuation everywhere, we will report that negative result as the benchmark's main finding.
Why not just use combinatorial local search, such as FM with random walk moves or a multilevel scheme? On balanced circuit partitioning these methods are fast and well tuned. Combining Two Local Search Approaches to Hypergraph Partitioning shows that random moves fix much of plain FM's entrapment. These methods target balanced cuts, though, not ratio cuts. They also depend on a randomness level that has to be tuned for each hypergraph. We compare against them on ISPD98 and expect at best parity there. Our case rests on ratio-cut and local-cluster tasks, plus the use of continuation's output as an FM starting point. If FM started from our cut does no better than FM started at random, the continuous stage is not earning its cost on partitioning.
Why not just smooth with Gaussian continuation? Blurring the objective with a Gaussian, as analyzed in A Theoretical Analysis of Optimization by Gaussian Continuation, applies to the scores $x$, not to the hypergraph structure. Its bound depends on a complexity quantity that the paper computes only for closed-form functions. We will still run Gaussian-perturbed starts at the same budget as one more baseline, so the comparison is measured rather than asserted.
Proposed Experiments and Decisive Checks
We will use five groups of data. The first is planted hypergraphs of 30 to 60 nodes with controlled hyperedge sizes, where integer programming gives exact optima. The second is LFR-style synthetic hypergraphs with increasing mixing, meaning a growing fraction of hyperedges that cross communities. The third is the real hypergraphs from the capacity-releasing diffusion study: YouTube, DBLP, Amazon, Email-EU, Math Overflow and Stack Overflow. The fourth is the co-authorship and co-citation hypergraphs from the hypergraph energy-function paper: Cora, DBLP, Citeseer, Pubmed, ModelNet40 and NTU2012. Their class labels provide external checks of cluster quality. The fifth is ISPD98 ibm01 through ibm12.
Metrics are true hypergraph conductance, the entrapment gap where exact optima exist, and the hit rate within 1% of best-known. We also report F1 against ground-truth communities, net cut for ISPD98, wall-clock time and peak memory. All methods share hardware and time budgets, and each runs over 20 seeds.
Three results would decide the question. The first is whether continuation lowers the entrapment gap below that of equal-time restarts on planted instances with large hyperedges, while failing to do so on instances whose hyperedges are mostly size two. The second is whether, across real hypergraphs, the gain correlates positively with expansion distortion. The third is whether, on the energy-function benchmarks, continuation followed by flow polish reaches lower conductance than capacity-releasing diffusion at equal F1. Any one outcome failing in the predicted direction would falsify the mechanism, even if average numbers looked good. We will release the solver and benchmark harness so that the theory papers above get the empirical test they lack.
References
- Total Variation, Cheeger Cuts
- Cheeger Inequalities for Submodular Transformations
- Efficient Flow-based Approximation Algorithms for Submodular Hypergraph Partitioning via a Generalized Cut-Matching Game
- Flow-based Algorithms for Improving Clusters: A Unifying Framework, Software, and Performance
- A Theoretical Analysis of Optimization by Gaussian Continuation
- Local hypergraph clustering using capacity releasing diffusion
- Combining Two Local Search Approaches to Hypergraph Partitioning
- From Hypergraph Energy Functions to Hypergraph Neural Networks