graphLaplacian

The graph Laplacian, or simply the Laplacian, is a matrix associated with a graph that encodes its connectivity. For an undirected graph G=(V,E) with adjacency matrix A and degree matrix D (diagonal with vertex degrees), the unnormalized Laplacian is L = D − A. Normalized variants include the symmetric Laplacian L_sym = I − D^(-1/2) A D^(-1/2) and the random-walk Laplacian L_rw = I − D^(-1) A. These matrices are real and symmetric, and they are positive semidefinite.

Key properties: L is zero on constant vectors on each connected component; the multiplicity of eigenvalue 0 equals the number of connected components. For a connected graph, the nullspace is spanned by the all-ones vector. The spectrum of L lies in [0, ∞); the spectrum of L_sym lies in [0, 2]. The quadratic form x^T L x = ∑_(u~v) w_uv (x_u − x_v)^2 expresses the smoothness of a signal x on the graph, with larger edge differences increasing the value.

Applications: spectral clustering and graph partitioning use the eigenvectors corresponding to the smallest nonzero eigenvalues to reveal community structure. The Laplacian underpins diffusion processes on graphs via du/dt = −L u and is central to graph signal processing and regularization in machine learning. It also relates to the Cheeger inequality, linking eigenvalues to conductance.

Computation and extensions: for large graphs, L is typically sparse, and eigen-decomposition of L or L_sym yields low-dimensional embeddings. For directed graphs, generalized or alternative Laplacians are used, since the standard definitions assume undirected graphs.