PRCut – Probabilistic RatioCut

PRCut is the baseline probabilistic graph cut objective from Yu et al. (2023).

Quick usage

from pgcuts import HyCut

labels = HyCut(n_clusters=10, objective="prcut").fit_predict(X)

Objective

PRCut minimizes the expected RatioCut normalized by cluster proportions:

\[\text{PRCut} = \sum_\ell \frac{1}{\bar{\alpha}_\ell} \cdot \frac{1}{|E|} \sum_{(i,j) \in E} w_{ij} \, p_{i\ell} (1 - p_{j\ell})\]

where \(p_{i\ell} = \text{softmax}(f_\theta(x_i))_\ell\) and \(\bar{\alpha}_\ell\) is the EMA cluster proportion.

A balance loss prevents cluster collapse:

\[\mathcal{L}_\text{balance} = -\sum_\ell \bar{p}_\ell \log \bar{p}_\ell\]

Both losses are combined via gradient mixing (each gradient is unit-normalized before summing).

Low-level API

For custom training loops, use the step functions directly:

from pgcuts.algorithms import prcut_step

cut_loss, balance, p_ema = prcut_step(
    probs, left_idx, right_idx, w, p_ema,
    ema=0.9,
)

Or the loss classes:

from pgcuts.losses import PRCutBatchLoss

loss_fn = PRCutBatchLoss(num_clusters=K, gamma=0.95)
loss_fn.update_cluster_p(P)
loss = loss_fn(W_batch, P_left, P_right)