Loss Spectral Clustering

spectral_clustering

CLASS	DESCRIPTION
SpectralClusteringLoss	Spectral clustering loss for graph partitioning.

FUNCTION	DESCRIPTION
spectral_clustering_loss	Compute spectral clustering loss.

Classes

SpectralClusteringLoss(reduce: Literal['ncut', 'rcut', 'trace'] = 'ncut', sign: float = 1.0, eps: float = torch.finfo(torch.float32).eps, context_prefix: str | None = None, **kwargs)

Bases: Loss

Spectral clustering loss for graph partitioning.

PARAMETER	DESCRIPTION
reduce	Reduction method. "ncut": Normalized cut loss "rcut": Ratio cut loss "trace": Trace of H^T L H (for trace maximization) TYPE: Literal["ncut", "rcut", "trace"], optional, by default "ncut" DEFAULT: 'ncut'
sign	Loss sign multiplier. Use -1.0 for maximization objectives. TYPE: float, optional, by default 1.0 DEFAULT: 1.0
eps	Small value for numerical stability. TYPE: float, optional, by default torch.finfo(torch.float32).eps DEFAULT: eps

Examples:

>>> loss_fn = SpectralClusteringLoss(reduce="ncut", sign=1.0)
>>> # Laplacian matrix
>>> L = torch.tensor([[2.0, -1.0, -1.0], [-1.0, 2.0, -1.0], [-1.0, -1.0, 2.0]])
>>> # Embedding matrix
>>> H = torch.randn(3, 2)
>>> context = {"K": L, "Z": H}
>>> loss = loss_fn(context)

METHOD	DESCRIPTION
forward	Compute spectral clustering loss.

Source code in spectre/loss/spectral_clustering.py

def __init__(
    self,
    reduce: Literal["ncut", "rcut", "trace"] = "ncut",
    sign: float = 1.0,
    eps: float = torch.finfo(torch.float32).eps,
    context_prefix: str | None = None,
    **kwargs,
):
    super().__init__(
        reduce=reduce, sign=sign, context_prefix=context_prefix, **kwargs
    )

    if not isinstance(eps, (int, float)) or eps <= 0:
        raise ValueError("`eps` must be a positive number.")
    self.eps = eps

Functions

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

Compute spectral clustering loss.

Arguments

**kwargs: dict Additional keyword arguments.

RETURNS	DESCRIPTION
loss	Spectral clustering loss. TYPE: Tensor

Source code in spectre/loss/spectral_clustering.py

def forward(self, context: dict, **kwargs) -> torch.Tensor:
    """
    Compute spectral clustering loss.

    Arguments
    ---------
    context: dict
        A dictionary containing Laplacian matrix and Z.

    **kwargs: dict
        Additional keyword arguments.

    Returns
    -------
    loss: torch.Tensor
        Spectral clustering loss.
    """
    K = self._get_context(context, "K", None)
    Z = self._get_context(context, "Z", None)

    if K is None:
        raise ValueError("`SpectralClusteringLoss` requires `K` in context.")
    if Z is None:
        raise ValueError("`SpectralClusteringLoss` requires `Z` in context.")

    check_2d(K)
    check_2d(Z)

    if K.shape[0] != K.shape[1]:
        raise ValueError("Laplacian matrix must be square.")
    if K.shape[0] != Z.shape[0]:
        raise ValueError("Laplacian and Z must have compatible dimensions.")

    return spectral_clustering_loss(
        K=K,
        Z=Z,
        reduce=self.reduce,
        sign=self.sign,
        eps=self.eps,
    )

Functions

spectral_clustering_loss(K: torch.Tensor, Z: torch.Tensor, reduce: Literal['ncut', 'rcut', 'trace'] = 'ncut', sign: float = 1.0, eps: float = torch.finfo(torch.float32).eps) -> torch.Tensor

Compute spectral clustering loss.

PARAMETER	DESCRIPTION
K	Graph Laplacian matrix (n_nodes, n_nodes). TYPE: Tensor
Z	Node Z matrix (n_nodes, n_clusters). TYPE: Tensor
reduce	Reduction method. TYPE: Literal["ncut", "rcut", "trace"], optional, by default "ncut" DEFAULT: 'ncut'
sign	Loss sign multiplier. TYPE: float, optional, by default 1.0 DEFAULT: 1.0
eps	Small value for numerical stability. TYPE: float, optional, by default float = torch.finfo(torch.float32).eps DEFAULT: eps

RETURNS	DESCRIPTION
Tensor	Computed spectral clustering loss.

Source code in spectre/loss/spectral_clustering.py

def spectral_clustering_loss(
    K: torch.Tensor,
    Z: torch.Tensor,
    reduce: Literal["ncut", "rcut", "trace"] = "ncut",
    sign: float = 1.0,
    eps: float = torch.finfo(torch.float32).eps,
) -> torch.Tensor:
    """
    Compute spectral clustering loss.

    Parameters
    ----------
    K : torch.Tensor
        Graph Laplacian matrix (n_nodes, n_nodes).

    Z : torch.Tensor
        Node Z matrix (n_nodes, n_clusters).

    reduce : Literal["ncut", "rcut", "trace"], optional, by default "ncut"
        Reduction method.

    sign : float, optional, by default 1.0
        Loss sign multiplier.

    eps : float, optional, by default float = torch.finfo(torch.float32).eps
        Small value for numerical stability.

    Returns
    -------
    torch.Tensor
        Computed spectral clustering loss.
    """
    check_2d(K)
    check_2d(Z)

    if reduce == "trace":
        # Trace of H^T L H
        loss = torch.trace(Z.T @ K @ Z)
    elif reduce in ["ncut", "rcut"]:
        # For normalized/ratio cut, we use the relaxed continuous version
        # This computes tr(H^T L H) / tr(H^T D H) for normalized cut
        # or tr(H^T L H) / n for ratio cut

        numerator = torch.trace(Z.T @ K @ Z)

        if reduce == "ncut":
            # Degree matrix is diagonal of Laplacian + adjacency
            # For normalized Laplacian: L = D - A, so D = L + A
            # We approximate volume with sum of degrees
            degree = torch.diag(K) + torch.sum(
                torch.abs(K - torch.diag(torch.diag(K))), dim=1
            )
            denominator = torch.trace(Z.T @ torch.diag(degree) @ Z) + eps
        else:  # rcut
            # For ratio cut, denominator is number of nodes
            denominator = Z.shape[0]

        loss = numerator / denominator
    else:
        raise ValueError(f"Unknown reduce method: {reduce}")

    return sign * loss