Skip to content

graph

spectral_permute(B, labels, mode='tw')

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 confusion matrix to be reordered, shape (n_classes, n_classes)

 required
labels ndarray

Class labels corresponding to matrix rows/columns, shape (n_classes,)

 required
mode (tw, fiedler)

Spectral reordering method: - 'tw': Use two-walk Laplacian for bipartite graph analysis - 'fiedler': Use standard Fiedler vector approach

 'tw'

Returns:

Name Type Description
reordered_cm ndarray

Reordered confusion matrix with revealed block structure
reordered_labels ndarray

Class labels reordered to match the permuted matrix rows/columns
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 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)
Source code in mheatmap/graph/_spectral_permute.py 
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
def spectral_permute(
    B: np.ndarray, labels: np.ndarray, mode: str = "tw"
) -> tuple[np.ndarray, np.ndarray]:
    """`spectral_permute(B, labels, mode='tw')`

    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 confusion matrix to be reordered, shape (n_classes, n_classes)
    labels : np.ndarray
        Class labels corresponding to matrix rows/columns, shape (n_classes,)
    mode : {'tw', 'fiedler'}, default='tw'
        Spectral reordering method:
        - 'tw': Use two-walk Laplacian for bipartite graph analysis
        - 'fiedler': Use standard Fiedler vector approach

    Returns
    -------
    reordered_cm : np.ndarray
        Reordered confusion matrix with revealed block structure
    reordered_labels : np.ndarray
        Class labels reordered to match the permuted matrix rows/columns

    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
    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)
    """
    rows, cols = B.shape

    if mode == "fiedler":
        # 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]

        # Visualize eigenspectrum
        plot_eigen(eigenvalues, eigenvectors)

        # 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
        B, labels = _put_zero_rows_cols_tail(B, 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]

        # Visualize eigenspectrum
        plot_eigen(eigenvalues, eigenvectors)

        # 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_labels = labels[sorted_rows_indices]

    # Visualize result
    plot_bipartite_confusion_matrix(reordered_B, reordered_labels)

    return reordered_B, reordered_labels

copermute_from_bipermute(B_sizes, B_subrows, B_subcols, p_Asub)

Copermute from bi-permutation.

Renders row permutation 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

A 1x2 array containing the dimensions of matrix B: [nrows, ncols]

 required
B_subrows array_like

Row indices defining the submatrix Bsub, nrBsub x 1 integer array where nrBsub <= nrB

 required
B_subcols array_like

Column indices defining the submatrix Bsub, ncBsub x 1 integer array where ncBsub <= ncB

 required
p_Asub array_like

Permutation vector for the symmetric embedding of Bsub, (nr+nc)x1 integer array

 required

Returns:

Type Description
tuple
  • p_Brows : Row permutation vector for matrix B, Bsizes[0]x1
  • p_Bcols : Column permutation vector for matrix B, Bsizes[1]x1

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
Source code in mheatmap/graph/_copermute_from_bipermute.py 
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
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 permutation 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
        A 1x2 array containing the dimensions of matrix B: [nrows, ncols]
    B_subrows : array_like
        Row indices defining the submatrix Bsub, nrBsub x 1 integer array where nrBsub <= nrB
    B_subcols : array_like
        Column indices defining the submatrix Bsub, ncBsub x 1 integer array where ncBsub <= ncB
    p_Asub : array_like
        Permutation vector for the symmetric embedding of Bsub, (nr+nc)x1 integer array

    Returns
    -------
    tuple
        - p_Brows : Row permutation vector for matrix B, Bsizes[0]x1
        - p_Bcols : Column permutation vector for matrix B, Bsizes[1]x1

    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 <[email protected]>
    - 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)
Bsub_rows ndarray

Indices of non-zero rows in the input matrix
Bsub_cols ndarray

Indices of non-zero columns in the input matrix
Notes

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

where α 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, rows, cols = two_walk_laplacian(B)
>>> print(L_tw.shape)
(4, 4)
Source code in mheatmap/graph/_two_walk_laplacian.py 
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
def two_walk_laplacian(
    B_sub: np.ndarray, alpha: float = 1
) -> tuple[np.ndarray, np.ndarray, 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)
    Bsub_rows : np.ndarray
        Indices of non-zero rows in the input matrix
    Bsub_cols : np.ndarray
        Indices of non-zero columns in the input matrix

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

    where α 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, rows, cols = 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