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 Tensor

Batch of normalized graph adjacency matricies.

 required

Returns:

Type Description
Tensor

Batch of graph Laplacians.
Source code in gsxform/graph.py 
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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 Tensor

Batch of adjacency matricies.

 required

Returns:

Type Description
Tensor

Batch of normalized adjacency matricies.
Source code in gsxform/graph.py 
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
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 = 1.0 / torch.sqrt(torch.max(torch.ones(d.size(), device=d.device), d))
    W_norm: torch.Tensor = einsum(d_invsqrt, W, d_invsqrt, "b i, b i j, b j -> b i j")

    return W_norm

normalize_laplacian 

normalize_laplacian(L)

Normalize an graph Laplacian.

Parameters:

Name Type Description Default
L Tensor

Batch of graph Laplacians.

 required

Returns:

Type Description
Tensor

Batch of normalized graph Laplacians.
Source code in gsxform/graph.py 
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
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 = 1.0 / torch.sqrt(torch.max(torch.ones(d.size(), device=d.device), d))
    L_norm: torch.Tensor = einsum(d_invsqrt, L, d_invsqrt, "b i, b i j, b j -> b i j")

    return L_norm

lazy_diffusion 

lazy_diffusion(W)

Build the lazy diffusion operator T = 1/2 (I+A).

Parameters:

Name Type Description Default
W Tensor

Batch of adjacency matricies.

 required

Returns:

Type Description
Tensor

Batch of lazy diffusion operators.
Source code in gsxform/graph.py 
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
def lazy_diffusion(W: torch.Tensor) -> torch.Tensor:
    """Build the lazy diffusion operator T = 1/2 (I+A).

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

    Returns
    -------
    torch.Tensor
        Batch of lazy diffusion operators.

    """
    I_N = torch.eye(W.shape[-1], device=W.device)

    T = 1 / 2 * (I_N + normalize_adjacency(W))

    return T

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 Tensor

Batch of graph adjacency matricies.

 required

Returns:

Type Description
Tuple[Tensor, Tensor]

Batch of eigenvalues and eigenvectors of the graph Laplacian.
Source code in gsxform/graph.py 
 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
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