Skip to content

Graph utility API documentation

adjacency_to_laplacian 

adjacency_to_laplacian(W)

Convert an adjacency matrix into the graph Laplacian.

Parameters:

Name Type Description Default
W torch.Tensor

Batch of normalized graph adjacency matricies.

 required

Returns:

Type Description
torch.Tensor

Batch of graph Laplacians.
Source code in gsxform/graph.py 
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def adjacency_to_laplacian(W: torch.Tensor) -> torch.Tensor:
    """Convert an adjacency matrix into the graph Laplacian.

    Parameters
    ----------
    W: torch.Tensor
        Batch of normalized graph adjacency matricies.

    Returns
    -------
    torch.Tensor
        Batch of graph Laplacians.

    """
    L = torch.diag_embed(W.sum(1)) - W

    return L

normalize_adjacency 

normalize_adjacency(W)

Normalize an adjacency matrix.

Parameters:

Name Type Description Default
W torch.Tensor

Batch of adjacency matricies.

 required

Returns:

Type Description
torch.Tensor

Batch of normalized adjacency matricies.
Source code in gsxform/graph.py 
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
def normalize_adjacency(W: torch.Tensor) -> torch.Tensor:
    """Normalize an adjacency matrix.

    Parameters
    ----------
    W: torch.Tensor
        Batch of adjacency matricies.

    Returns
    -------
    torch.Tensor
        Batch of normalized adjacency matricies.

    """
    # build degree vector
    d = W.sum(1)
    # normalize
    D_invsqrt = torch.diag_embed(1.0 / torch.sqrt(torch.max(torch.ones(d.size()), d)))
    W_norm = D_invsqrt.matmul(W).matmul(D_invsqrt)

    return W_norm

normalize_laplacian 

normalize_laplacian(L)

Normalize an graph Laplacian.

Parameters:

Name Type Description Default
L torch.Tensor

Batch of graph Laplacians.

 required

Returns:

Type Description
torch.Tensor

Batch of normalized graph Laplacians.
Source code in gsxform/graph.py 
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
def normalize_laplacian(L: torch.Tensor) -> torch.Tensor:
    """Normalize an graph Laplacian.

    Parameters
    ----------
    L: torch.Tensor
        Batch of graph Laplacians.

    Returns
    -------
    torch.Tensor
        Batch of normalized graph Laplacians.
    """
    # build degree vector
    # batch diagonal
    # (https://pytorch.org/docs/stable/generated/torch.diagonal.html#torch.diagonal)
    d = torch.diagonal(L, dim1=-2, dim2=-1)
    # normalize
    D_invsqrt = torch.diag_embed(1.0 / torch.sqrt(torch.max(torch.ones(d.size()), d)))
    L_norm = D_invsqrt.matmul(L).matmul(D_invsqrt)

    return L_norm

compute_spectra 

compute_spectra(W)

Compute the spectra of graph Laplacian from its adjacency matrix.

Performs an eigendecomposition (w/o assuming additional structure) using torch.linalg.eigh (previously used torch.symeig) on a normalized graph laplacian. Converts from the adjacency matrix to the laplacian internally.

Parameters:

Name Type Description Default
W torch.Tensor

Batch of graph adjacency matricies.

 required

Returns:

Type Description
Tuple[torch.Tensor, torch.Tensor]

Batch of eigenvalues and eigenvectors of the graph Laplacian.
Source code in gsxform/graph.py 
 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
def compute_spectra(W: torch.Tensor) -> Tuple[torch.Tensor, torch.Tensor]:
    """Compute the spectra of graph Laplacian from its adjacency matrix.

    Performs an eigendecomposition (w/o assuming additional structure)
    using `torch.linalg.eigh` (previously used `torch.symeig`) on a normalized
    graph laplacian. Converts from the adjacency matrix to the laplacian
    internally.

    Parameters
    ----------
    W: torch.Tensor
        Batch of graph adjacency matricies.

    Returns
    -------
    Tuple[torch.Tensor, torch.Tensor]
        Batch of eigenvalues and eigenvectors of the graph Laplacian.
    """
    # compute laplacian
    L = adjacency_to_laplacian(W)
    # normalize laplacian
    L_norm = normalize_laplacian(L)
    # perform eigen decomp
    # come out in ascending order,
    E, V = torch.linalg.eigh(L_norm, UPLO="L")

    return E, V