graph_laplacian: Graph Laplacian

hypercoil.functional.graph.graph_laplacian(W: Tensor, normalise: bool = True, topk: bool = True) → Tensor

hypercoil.functional.graph.graph_laplacian(W: BCOO, normalise: bool = True, topk: bool = True) → BCOO

Laplacian of a graph.

Given the diagonal matrix of matrix degrees \(D\), the Laplacian \(L\) of a graph with adjacency matrix \(A\) is

\(L = D - A\)

For many applications, vertices with large degrees tend to dominate properties of the Laplacian, and it is desirable to normalise the Laplacian before further analysis.

\[ \begin{align}\begin{aligned}\widetilde{L} = D^{-\frac{1}{2}} L D^{-\frac{1}{2}}\\\widetilde{L} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}\end{aligned}\end{align} \]

Note

For an undirected graph, each edge should be duplicated in the index and weight tensors, with source and target vertices swapped in the index.

Note

For a directed graph, this computes the row Laplacian. This could be either the in-degree Laplacian or the out-degree Laplacian, depending on the convention adopted for the input.

Dimension:

W : \((*, N, N)\) or \((*, E)\)

* denotes any number of preceding dimensions, N denotes number of vertices, and E denotes number of edges. The shape should be \((*, N, N)\) if edge_index is not provided and \((*, E)\) if edge_index is provided.

edge_index : \((*, 2, E)\)

As above.

Output : \((*, N, N)\) or tuple(\((*, E)\), \((*, 2, E)\))

As above.

Parameters:

Wtensor

Edge weight tensor. If edge_index is not provided, then this should be the graph adjacency matrix; otherwise, it should be a list of weights corresponding to the edges in edge_index.

normalisebool (default True)

Indicates that the Laplacian should be normalised using the degree matrix.

topkbool (default True)

Indicates that the input is a top-k sparse matrix. Has no effect if W is not a sparse matrix.