Loss Mincut

mincut

CLASS	DESCRIPTION
MinCutLoss	Differentiable MinCut loss for spectral clustering via transition probabilities.

Classes

MinCutLoss(reduce='mean', sign=1.0, eps: float = torch.finfo(torch.float32).eps, ortho_weight: float = 1.0, context_prefix: str | None = None)

Bases: Loss

Differentiable MinCut loss for spectral clustering via transition probabilities.

Implements the normalized cut objective using a transition matrix formulation, where states are identified by maximizing within-state random walk probabilities.

The loss combines two objectives:

1. Transition probability maximization: Maximizes expected probability that random walks stay within assigned states \(-\frac{\text{Tr}(S^T T S)}{\text{Tr}(S^T S)}\)

2. Orthogonality constraint: Encourages distinct, balanced clusters using a squared penalty: \(\|\frac{S^T S}{n} - I\|_F^2\), where \(n\) is the number of samples

where \(T\) is a transition matrix (e.g., from diffusion maps), \(S\) is the soft state assignment matrix, and \(I\) is the identity matrix.

Interpretation:

The term \(\text{Tr}(S^T T S)=\sum_k\sum_{i,j} S_{ik}\cdot T_{ij} \cdot S_{jk}\) computes transition probabilities weighted by state co-assignment:

• Symmetric case (markov_symmetric normalization): Maximizes expected probability that random walks stay within assigned states. Points in the same state have high mutual transition probabilities (short diffusion distances).

• Nonsymmetric case (markov_nonsymmetric): Maximizes expected probability flow circulation within states. States form around regions where directed random walks tend to circulate, accounting for anisotropic or directional structure in the data (e.g., drift, directed graphs).

Both formulations minimize the normalized cut, but with different geometric interpretations.

The normalization type is not checked internally.

PARAMETER	DESCRIPTION
reduce	Reduction method (unused for this loss). TYPE: str, optional, by default "mean" DEFAULT: 'mean'
sign	Loss sign multiplier. TYPE: float, optional, by default 1.0 DEFAULT: 1.0
ortho_weight	Weight for orthogonality constraint. Controls the trade-off between minimizing cut and enforcing balanced cluster separation. TYPE: float, optional, by default 1.0 DEFAULT: 1.0
eps	Small constant for numerical stability in divisions. TYPE: float, optional, by default torch.finfo(torch.float32).eps DEFAULT: eps

METHOD	DESCRIPTION
forward	Compute MinCut loss with orthogonality regularization.

Source code in spectre/loss/mincut.py

def __init__(
    self,
    reduce="mean",
    sign=1.0,
    eps: float = torch.finfo(torch.float32).eps,
    ortho_weight: float = 1.0,
    context_prefix: str | None = None,
):
    super().__init__(reduce=reduce, sign=sign, context_prefix=context_prefix)

    if not isinstance(eps, float):
        raise TypeError(f"eps must be float, got {type(eps)}")
    check_in_interval(eps, "[0, inf)")
    self.eps = eps

    if not isinstance(ortho_weight, float):
        raise TypeError(f"ortho_weight must be float, got {type(ortho_weight)}")
    check_in_interval(ortho_weight, "[0, inf)")
    self.ortho_weight = ortho_weight

Functions

forward(context: dict, **kwargs) -> torch.Tensor

Compute MinCut loss with orthogonality regularization.

PARAMETER	DESCRIPTION
context	Dictionary containing required tensors: K : torch.Tensor of shape (n_samples, n_samples) Transition matrix representing random walk probabilities between samples. S : torch.Tensor of shape (n_samples, n_states) Soft state assignment matrix with values in [0, 1], where S[i,k] represents the probability that sample i belongs to state k. TYPE: dict
**kwargs	Additional keyword arguments (unused). TYPE: dict DEFAULT: {}

RETURNS	DESCRIPTION
Tensor	Scalar loss combining MinCut and orthogonality objectives.

Source code in spectre/loss/mincut.py

def forward(self, context: dict, **kwargs) -> torch.Tensor:
    """
    Compute MinCut loss with orthogonality regularization.

    Parameters
    ----------
    context : dict
        Dictionary containing required tensors:

        - `K` : torch.Tensor of shape (n_samples, n_samples)
            Transition matrix representing random walk probabilities between
            samples.

        - `S` : torch.Tensor of shape (n_samples, n_states)
            Soft state assignment matrix with values in [0, 1], where
            `S[i,k]` represents the probability that sample `i` belongs to
            state `k`.

    **kwargs : dict
        Additional keyword arguments (unused).

    Returns
    -------
    torch.Tensor
        Scalar loss combining MinCut and orthogonality objectives.
    """
    K = self._get_context(context, "K", None)
    S = self._get_context(context, "S", None)

    if K is None or S is None:
        raise ValueError("MinCutLoss requires 'K' and 'S' in context")

    check_same_len(K, S)

    return _mincut_loss_impl(
        K, S, sign=self.sign, eps=self.eps, ortho_weight=self.ortho_weight
    )

Functions