Graph Laplacian

Background

The graph Laplacian $L = D - A$ encodes a graph's connectivity, where $A$ is the adjacency matrix and $D$ the diagonal degree matrix. It is the discrete analogue of the Laplace operator and the engine behind spectral clustering, graph signal processing, and graph neural networks — its eigenvalues and eigenvectors reveal community structure and smooth functions defined on the graph.

Problem statement

Implement graph_laplacian(adjacency, normalized=False). The combinatorial Laplacian is:

$$L = D - A, \qquad D_{ii} = \sum_{j} A_{ij}$$

The symmetric normalized Laplacian (when normalized=True) is:

$$L_{\text{sym}} = I - D^{-1/2} A\, D^{-1/2}$$

with the contribution of any isolated node (degree 0) set to 0.

Input

• adjacency — np.ndarray (n, n): the (possibly weighted) adjacency matrix.
• normalized — bool: if True, return the symmetric normalized Laplacian; otherwise the combinatorial $L = D - A$.

Output

Returns an np.ndarray of shape (n, n): the Laplacian.

Examples

Example 1

Input:  adjacency = [[0,1,1],[1,0,1],[1,1,0]], normalized = False
Output: [[2,-1,-1],[-1,2,-1],[-1,-1,2]]

Explanation: every node has degree 2, so $D = 2I$; subtracting $A$ places the degree on the diagonal and $-1$ wherever an edge exists. Each row sums to 0.

Constraints

• $D$ is diagonal with $D_{ii}$ the (weighted) degree — the row sum of $A$.
• Combinatorial: $L = D - A$; every row of it sums to 0.
• Normalized: $L_{\text{sym}} = I - D^{-1/2} A D^{-1/2}$; guard against division by zero for degree-0 nodes.

Notes

• The combinatorial Laplacian is positive semi-definite, with one zero eigenvalue per connected component — the multiplicity of eigenvalue 0 counts the components.
• The normalized Laplacian's eigenvalues lie in $[0, 2]$, which is what makes it the preferred operator for spectral clustering and GNN message propagation.