H-RCut – Hypergeometric RatioCut
H-RCut extends PRCut with a hypergeometric envelope \({}_{2}F_{1}(-m, 1; 2; \bar{\alpha}_\ell)\) that provides a tighter bound on the expected RatioCut (Theorem 1).
Quick usage
from pgcuts import HyCut
labels = HyCut(n_clusters=10, objective="hyp_rcut").fit_predict(X)
Objective
where \(M_{i\ell}(P) = \sum_j w_{ij} p_{i\ell}(1 - p_{j\ell})\) and \(\bar{\alpha}_\ell\) is the EMA cluster proportion.
The envelope is the same for every vertex (\(\beta = 1\)), making H-RCut simpler than H-NCut but less expressive for graphs with heterogeneous degree distributions.
When to use H-RCut
Clusters are roughly equal-sized
Graph degrees are relatively uniform
You want a simpler objective with fewer hyperparameters (no binning)
For unbalanced clusters or heavy-tailed degree distributions, use H-NCut instead.
Low-level API
from pgcuts.algorithms import hyp_rcut_step
cut_loss, balance, p_ema = hyp_rcut_step(
logits, left_idx, right_idx, w, p_ema,
m=512, ema=0.9,
)
Property |
PRCut |
H-RCut |
|---|---|---|
Envelope |
\(1/\bar{\alpha}_\ell\) |
\({}_{2}F_{1}(-m, 1; 2; \bar{\alpha}_\ell)\) |
Bound tightness |
Looser |
Tighter |
Per-vertex weights |
No |
No (see H-NCut – Hypergeometric NCut for per-vertex) |