graph

spectral_permute(B, row_labels, mode='tw', *, col_labels=None)

Perform spectral reordering of a confusion matrix using graph Laplacian eigenvectors.

This function implements spectral reordering to reveal block structures in confusion matrices by analyzing the eigenvectors of the graph Laplacian. The reordering is based on the Fiedler vector (eigenvector corresponding to the second smallest eigenvalue), which provides an optimal ordering that groups similar classes together.

Parameters:

Name	Type	Description	Default
B	ndarray	Input matrix to be reordered. For mode='tw' supports shape (n_rows, n_cols); for mode='fiedler' must be square.	required
row_labels	ndarray	Class labels corresponding to matrix rows, shape (n_rows,).	None
mode	(tw, fiedler)	Spectral reordering method: 'tw': Use two-walk Laplacian for bipartite graph analysis. Supports rectangular matrices and returns a separate column permutation via col_labels. 'fiedler': Use standard Fiedler vector approach. Only supports square matrices (n_rows == n_cols).	'tw'
col_labels	ndarray | None	Column labels for rectangular matrices. When provided (not None), returns a dict that includes the reordered columns reordered_col_labels. For confusion matrices (square, shared labels) this parameter is typically omitted.	None
labels	ndarray	Deprecated alias for row_labels. Use row_labels instead.	None

Returns:

Name	Type	Description
reordered_cm	ndarray	Reordered matrix with revealed block structure.
reordered_labels	ndarray	Row labels reordered to match the permuted matrix rows.
	_SpectralPermuteResult (when ``col_labels`` is provided)	TypedDict with fields: reordered_matrix: Reordered matrix reordered_row_labels: Row labels reordered reordered_col_labels: Col labels reordered

Raises:

Type	Description
ValueError	If mode='fiedler' is used with a non-square matrix.

See Also

mheatmap.rms_permute : Alternative reordering using merge/split patterns mheatmap.amc_postprocess : Post-processing tools for confusion matrices mheatmap.graph.two_walk_laplacian : Two-walk Laplacian computation

Notes

The algorithm proceeds in the following steps: 1. For mode='tw': - Constructs two-walk Laplacian capturing bipartite graph structure - Handles isolated vertices automatically - Computes separate row and column permutations via co-permutation 2. For mode='fiedler': - Computes standard graph Laplacian L = D - A 3. Finds Fiedler vector (second smallest eigenvector) 4. Sorts vertices based on Fiedler vector components 5. Applies resulting permutation to matrix and labels

References

.. [1] Fiedler, M. (1973). Algebraic connectivity of graphs. Czechoslovak Mathematical Journal, 23(2), 298-305. .. [2] Sun, X. (2024). Matrix, Graph and Network Analysis. CS521 Course Notes, Duke University.

Examples:

>>> import numpy as np
>>> conf_mat = np.array([[5, 2, 0], [2, 3, 1], [0, 1, 4]])
>>> labels = np.array(['A', 'B', 'C'])
>>> reordered_mat, reordered_labs = spectral_permute(conf_mat, labels)

With column labels on a rectangular matrix (mode='tw' only):

>>> import numpy as np
>>> B = np.array([[1, 0.5, 0.2, 0.1], [0.3, 1, 0.8, 0.4], [0.1, 0.2, 1, 0.9]])
>>> row_labels = np.array(['r0', 'r1', 'r2'])
>>> col_labels = np.array(['c0', 'c1', 'c2', 'c3'])
>>> result = spectral_permute(B, row_labels, col_labels=col_labels)
>>> result['reordered_col_labels']

Source code in src/mheatmap/graph/_spectral_permute.py

def spectral_permute(
    B: np.ndarray,
    row_labels: np.ndarray | None = None,
    mode: str = "tw",
    *,
    col_labels: np.ndarray | None = None,
    labels: np.ndarray | None = None,
) -> tuple[np.ndarray, np.ndarray] | _SpectralPermuteResult:
    """`spectral_permute(B, row_labels, mode='tw', *, col_labels=None)`

    Perform spectral reordering of a confusion matrix using
    graph Laplacian eigenvectors.

    This function implements spectral reordering to reveal block
    structures in confusion matrices by analyzing the eigenvectors
    of the graph Laplacian. The reordering is based on the Fiedler
    vector (eigenvector corresponding to the second smallest
    eigenvalue), which provides an optimal ordering that groups
    similar classes together.

    Parameters
    ----------
    B : np.ndarray
        Input matrix to be reordered. For ``mode='tw'`` supports shape
        ``(n_rows, n_cols)``; for ``mode='fiedler'`` must be square.
    row_labels : np.ndarray
        Class labels corresponding to matrix rows, shape ``(n_rows,)``.
    mode : {'tw', 'fiedler'}, default='tw'
        Spectral reordering method:

        - ``'tw'``: Use two-walk Laplacian for bipartite graph analysis.
          Supports rectangular matrices and returns a separate column
          permutation via ``col_labels``.
        - ``'fiedler'``: Use standard Fiedler vector approach. **Only
          supports square matrices** (``n_rows == n_cols``).

    col_labels : np.ndarray | None, optional
        Column labels for rectangular matrices. When provided (not
        ``None``), returns a dict that includes the reordered columns
        ``reordered_col_labels``. For confusion matrices (square, shared
        labels) this parameter is typically omitted.
    labels : np.ndarray, optional
        Deprecated alias for ``row_labels``. Use ``row_labels`` instead.

    Returns
    -------
    reordered_cm : np.ndarray
        Reordered matrix with revealed block structure.
    reordered_labels : np.ndarray
        Row labels reordered to match the permuted matrix rows.
    _SpectralPermuteResult (when ``col_labels`` is provided)
        TypedDict with fields:

        - ``reordered_matrix``: Reordered matrix
        - ``reordered_row_labels``: Row labels reordered
        - ``reordered_col_labels``: Col labels reordered

    Raises
    ------
    ValueError
        If ``mode='fiedler'`` is used with a non-square matrix.

    See Also
    --------
    mheatmap.rms_permute : Alternative reordering using merge/split patterns
    mheatmap.amc_postprocess : Post-processing tools for confusion matrices
    mheatmap.graph.two_walk_laplacian : Two-walk Laplacian computation

    Notes
    -----
    The algorithm proceeds in the following steps:
    1. For mode='tw':
        - Constructs two-walk Laplacian capturing bipartite graph structure
        - Handles isolated vertices automatically
        - Computes separate row and column permutations via co-permutation
    2. For mode='fiedler':
        - Computes standard graph Laplacian L = D - A
    3. Finds Fiedler vector (second smallest eigenvector)
    4. Sorts vertices based on Fiedler vector components
    5. Applies resulting permutation to matrix and labels

    References
    ----------
    .. [1] Fiedler, M. (1973). Algebraic connectivity of graphs.
           Czechoslovak Mathematical Journal, 23(2), 298-305.
    .. [2] Sun, X. (2024). Matrix, Graph and Network Analysis.
           CS521 Course Notes, Duke University.

    Examples
    --------
    >>> import numpy as np
    >>> conf_mat = np.array([[5, 2, 0], [2, 3, 1], [0, 1, 4]])
    >>> labels = np.array(['A', 'B', 'C'])
    >>> reordered_mat, reordered_labs = spectral_permute(conf_mat, labels)

    With column labels on a rectangular matrix (``mode='tw'`` only):

    >>> import numpy as np
    >>> B = np.array([[1, 0.5, 0.2, 0.1], [0.3, 1, 0.8, 0.4], [0.1, 0.2, 1, 0.9]])
    >>> row_labels = np.array(['r0', 'r1', 'r2'])
    >>> col_labels = np.array(['c0', 'c1', 'c2', 'c3'])
    >>> result = spectral_permute(B, row_labels, col_labels=col_labels)
    >>> result['reordered_col_labels']
    """
    # Handle deprecated 'labels' parameter
    if labels is not None:
        if row_labels is not None:
            raise ValueError(
                "Cannot specify both 'labels' and 'row_labels'. "
                "Use 'row_labels' only; 'labels' is deprecated."
            )
        warnings.warn(
            "The 'labels' parameter is deprecated and will be removed in a "
            "future version. Use 'row_labels' instead.",
            DeprecationWarning,
            stacklevel=2,
        )
        row_labels = labels

    if row_labels is None:
        raise ValueError("row_labels is required")

    rows, cols = B.shape

    if len(row_labels) != rows:
        raise ValueError(
            f"row_labels length ({len(row_labels)}) does not match matrix rows ({rows})"
        )
    if col_labels is not None and len(col_labels) != cols:
        raise ValueError(
            f"col_labels length ({len(col_labels)}) does not match "
            f"matrix columns ({cols})"
        )

    if mode == "fiedler":
        if rows != cols:
            raise ValueError(
                "mode='fiedler' only supports square matrices "
                f"(got shape ({rows}, {cols})). Use mode='tw' for rectangular matrices."
            )
        # Compute standard graph Laplacian L = D - A
        D = np.diag(np.sum(B, axis=1))
        L = D - B

        # Get eigendecomposition and find Fiedler vector
        eigenvalues, eigenvectors = eigh(L)
        nonzero_idx = np.where(np.abs(eigenvalues) > 1e-10)[0][0]
        fiedler_vector = eigenvectors[:, nonzero_idx]

        # Sort vertices based on Fiedler vector
        sorted_rows_indices = np.argsort(fiedler_vector)
        sorted_cols_indices = sorted_rows_indices

    elif mode == "tw":
        # Handle isolated vertices
        if col_labels is not None:
            B, row_labels, col_labels = _put_zero_rows_cols_tail(
                B, row_labels, col_labels=col_labels
            )
        else:
            B, row_labels = _put_zero_rows_cols_tail(B, row_labels)
        B_sub, Bsub_rows, Bsub_cols = _get_B_sub(B)

        # Compute two-walk Laplacian and its eigendecomposition
        L = two_walk_laplacian(B_sub)
        eigenvalues, eigenvectors = eigh(L)

        # Get Fiedler vector for spectral ordering
        nonzero_idx = np.where(np.abs(eigenvalues) > 1e-10)[0][0]
        fiedler_vector = eigenvectors[:, nonzero_idx]

        # Get permutation from Fiedler vector
        p_Asub = np.argsort(fiedler_vector)

        # Map bipartite permutation to matrix dimensions
        sorted_rows_indices, sorted_cols_indices = copermute_from_bipermute(
            [rows, cols], Bsub_rows, Bsub_cols, p_Asub
        )

    # Apply permutation to get reordered matrix and labels
    reordered_B = B[sorted_rows_indices, :][:, sorted_cols_indices]
    reordered_row_labels = row_labels[sorted_rows_indices]

    if col_labels is not None:
        reordered_column_labels = col_labels[sorted_cols_indices]
        return {
            "reordered_matrix": reordered_B,
            "reordered_row_labels": reordered_row_labels,
            "reordered_col_labels": reordered_column_labels,
        }
    return reordered_B, reordered_row_labels

copermute_from_bipermute(B_sizes, B_subrows, B_subcols, p_Asub)

Copermute from bi-permutation.

Renders row and column permutation of matrix B according to a co-permutation of a submatrix Bsub via a bi-permutation in its symmetric embedding: Asub = [[0, Bsub], [Bsub.T, 0]]

Parameters:

Name	Type	Description	Default
B_sizes	array_like	Array of shape (2,) containing [nrows, ncols] of matrix B	required
B_subrows	array_like	Integer array of shape (nrBsub,) with row indices defining the submatrix Bsub, where nrBsub <= nrows	required
B_subcols	array_like	Integer array of shape (ncBsub,) with column indices defining the submatrix Bsub, where ncBsub <= ncols	required
p_Asub	array_like	Integer array of shape (nrBsub + ncBsub,) with permutation for the symmetric embedding of Bsub	required

Returns:

Type	Description
tuple	p_Brows : Row permutation, integer array of shape (nrows,) p_Bcols : Column permutation, integer array of shape (ncols,)

Examples:

>>> import numpy as np
>>> m, n = 5, 4  # matrix dimensions
>>> B_sizes = [m, n]
>>> # Use entire matrix as submatrix
>>> p_Brows, p_Bcols = copermute_from_bipermute(
...     B_sizes,
...     np.arange(1,m+1),
...     np.arange(1,n+1),
...     np.random.permutation(m+n)+1
... )

Notes

Revision of recover_nonsymmetric_perm.m All variables renamed to be self-evident + additional documentation Nov. 22, 2024

Authors

• Dimitris Floros dimitrios.floros@duke.edu
• Xiaobai Sun
• Juntang Wang

Source code in src/mheatmap/graph/_copermute_from_bipermute.py

def copermute_from_bipermute(
    B_sizes: list[int], B_subrows: np.ndarray, B_subcols: np.ndarray, p_Asub: np.ndarray
) -> tuple[np.ndarray, np.ndarray]:
    """`copermute_from_bipermute(B_sizes, B_subrows, B_subcols, p_Asub)`

    Copermute from bi-permutation.

    Renders row and column permutation of matrix B according to
    a co-permutation of a submatrix Bsub via a bi-permutation
    in its symmetric embedding:
        Asub = [[0, Bsub], [Bsub.T, 0]]

    Parameters
    ----------
    B_sizes : array_like
        Array of shape (2,) containing [nrows, ncols] of matrix B
    B_subrows : array_like
        Integer array of shape (nrBsub,) with row indices
        defining the submatrix Bsub, where nrBsub <= nrows
    B_subcols : array_like
        Integer array of shape (ncBsub,) with column indices
        defining the submatrix Bsub, where ncBsub <= ncols
    p_Asub : array_like
        Integer array of shape (nrBsub + ncBsub,) with
        permutation for the symmetric embedding of Bsub

    Returns
    -------
    tuple
        - p_Brows : Row permutation, integer array of shape (nrows,)
        - p_Bcols : Column permutation, integer array of shape (ncols,)

    Examples
    --------
    >>> import numpy as np
    >>> m, n = 5, 4  # matrix dimensions
    >>> B_sizes = [m, n]
    >>> # Use entire matrix as submatrix
    >>> p_Brows, p_Bcols = copermute_from_bipermute(
    ...     B_sizes,
    ...     np.arange(1,m+1),
    ...     np.arange(1,n+1),
    ...     np.random.permutation(m+n)+1
    ... )

    Notes
    -----
    Revision of recover_nonsymmetric_perm.m
    All variables renamed to be self-evident + additional documentation
    Nov. 22, 2024

    Authors
    -------
    - Dimitris Floros <dimitrios.floros@duke.edu>
    - Xiaobai Sun
    - Juntang Wang
    """
    nr_B = B_sizes[0]
    nc_B = B_sizes[1]

    nr_Bsub = len(B_subrows)
    nc_Bsub = len(B_subcols)

    # Set the markers for bipartite-embedding of Bsub: 1 for rows; 2 for columns
    bi_marker = np.concatenate(
        [np.ones(nr_Bsub, dtype=int), 2 * np.ones(nc_Bsub, dtype=int)]
    )
    bi_marker = bi_marker[p_Asub]

    # Separate row and column indices in the bi-permutation
    p_r = p_Asub[bi_marker == 1]
    p_c = p_Asub[bi_marker == 2] - nr_Bsub

    # Permute the given indices at input
    pr_Bsub = B_subrows[p_r]
    pc_Bsub = B_subcols[p_c]

    # Render co-permutation in B: place Bsub first, the remaining to the end
    p_Brows = np.concatenate([pr_Bsub, np.setdiff1d(np.arange(0, nr_B), pr_Bsub)])

    p_Bcols = np.concatenate([pc_Bsub, np.setdiff1d(np.arange(0, nc_B), pc_Bsub)])

    return p_Brows, p_Bcols

two_walk_laplacia(B_sub, alpha=1)

Compute the two-walk Laplacian matrix of a bipartite graph.

For a bipartite graph with biadjacency matrix B, constructs the two-walk Laplacian by first forming the two-walk adjacency matrix A_tw and then computing L_tw = D_tw - A_tw, where D_tw is the diagonal degree matrix.

Parameters:

Name	Type	Description	Default
B_sub	ndarray	Biadjacency matrix of shape (m, n) representing connections between two vertex sets	required
alpha	float	Scaling factor for the adjacency matrix term in the Laplacian computation	1.0

Returns:

Name	Type	Description
L_tw	ndarray	Two-walk Laplacian matrix of shape (m+n, m+n)

Notes

The two-walk adjacency matrix A_tw has the block structure: [BB^T aB ] [aB^T B^TB ]

where a (alpha) is the scaling factor controlling the influence of direct connections.

The implementation automatically handles isolated vertices by removing rows/columns with all zeros before computation. The returned indices enable mapping back to the original matrix dimensions.

References

.. [1] Sun, X. (2024). Graph Algorithms for Matrix Analysis. CS521 Course Notes, Duke University.

Examples:

>>> B = np.array([[1, 0], [1, 1]])
>>> L_tw = two_walk_laplacian(B)
>>> print(L_tw.shape)
(4, 4)

Source code in src/mheatmap/graph/_two_walk_laplacian.py

def two_walk_laplacian(B_sub: np.ndarray, alpha: float = 1) -> np.ndarray:
    """`two_walk_laplacia(B_sub, alpha=1)`

    Compute the two-walk Laplacian matrix of a bipartite graph.

    For a bipartite graph with biadjacency matrix B, constructs the two-walk Laplacian
    by first forming the two-walk adjacency matrix A_tw and then
    computing L_tw = D_tw - A_tw, where D_tw is the diagonal
    degree matrix.

    Parameters
    ----------
    B_sub : np.ndarray
        Biadjacency matrix of shape (m, n) representing
        connections between two vertex sets
    alpha : float, default=1.0
        Scaling factor for the adjacency matrix term in the Laplacian computation

    Returns
    -------
    L_tw : np.ndarray
        Two-walk Laplacian matrix of shape (m+n, m+n)

    Notes
    -----
    The two-walk adjacency matrix A_tw has the block structure:
        [BB^T    aB  ]
        [aB^T   B^TB ]

    where a (alpha) is the scaling factor controlling the
    influence of direct connections.

    The implementation automatically handles isolated vertices by removing rows/columns
    with all zeros before computation. The returned indices enable mapping back to
    the original matrix dimensions.

    References
    ----------
    .. [1] Sun, X. (2024). Graph Algorithms for Matrix Analysis. CS521 Course Notes,
           Duke University.

    Examples
    --------
    >>> B = np.array([[1, 0], [1, 1]])
    >>> L_tw = two_walk_laplacian(B)
    >>> print(L_tw.shape)
    (4, 4)
    """
    # Form the two-walk adjacency matrix with block structure
    A_tw = np.block(
        [[B_sub @ B_sub.T, alpha * B_sub], [alpha * B_sub.T, B_sub.T @ B_sub]]
    )

    # Compute degree matrix and Laplacian
    D_tw = np.diag(np.sum(A_tw, axis=1))
    L_tw = D_tw - A_tw

    return L_tw