Fact-checked by Grok 2 weeks ago

Laplacian matrix

The Laplacian matrix of an undirected graph G = (V, E) with n vertices is the n \times n symmetric matrix L = D - A, where D is the diagonal degree matrix with D_{ii} equal to the degree of vertex i, and A is the adjacency matrix with A_{ij} = 1 if (i,j) \in E and 0 otherwise.^[1]^[2] This matrix serves as a discrete analogue of the continuous Laplacian operator from multivariable calculus, measuring how much a function on the graph deviates from its average on neighboring vertices.^[2] The origins of the Laplacian matrix trace back to Gustav Kirchhoff's 1847 paper on the solution of linear equations arising in electrical network analysis, where it modeled the flow of currents through circuits via Kirchhoff's laws.^[3] In this context, Kirchhoff introduced what is now known as the matrix-tree theorem, which states that the number of spanning trees in a connected graph equals any cofactor (e.g., the determinant of a principal minor obtained by removing one row and column) of the Laplacian matrix.^[4] This theorem provides a deterministic method to count spanning trees, linking algebraic properties of the matrix to combinatorial structures of the graph.^[4] Key properties of the Laplacian matrix include its positive semidefiniteness, meaning all eigenvalues are non-negative, with the smallest eigenvalue \lambda_1 = 0 and the all-ones vector as its eigenvector.^[2]^[1] The multiplicity of the zero eigenvalue equals the number of connected components in the graph, while the second-smallest eigenvalue \lambda_2 (known as the algebraic connectivity) quantifies how well-connected the graph is, with \lambda_2 > 0 if and only if G is connected.^[2]^[1] The quadratic form x^T L x = \sum_{(u,v) \in E} w(u,v) (x_u - x_v)^2 (for weighted graphs with weights w) interprets the matrix as encoding edge differences, which underpins its use in optimization and diffusion processes.^[2] In spectral graph theory, the eigenvalues and eigenvectors of the Laplacian provide insights into graph partitioning, expansion, and synchronization; for instance, the Fiedler vector (eigenvector for \lambda_2) can approximate graph cuts.^[5] Applications extend to machine learning for spectral clustering, where the Laplacian normalizes data similarities to reveal clusters, and to network analysis in computer science for studying random walks and resistance distances.^[5] A related construct, the signless Laplacian Q = D + A, shares similar spectral properties but focuses on even subgraphs and bipartite components.^[1]

Definitions for Simple Graphs

Undirected Graphs

For an undirected simple graph G = (V, E) with vertex set V = \{v_1, \dots, v_n\} and edge set E, the Laplacian matrix L is an n \times n matrix defined as L = D - A, where A is the adjacency matrix with entries A_{ij} = 1 if \{v_i, v_j\} \in E and $0 otherwise (and A_{ii} = 0), and D is the diagonal degree matrix with D_{ii} equal to the degree of vertex v_i (i.e., the number of edges incident to v_i).^[6] This construction encodes the graph's structure: the off-diagonal entries of L are negative indicators of edges, while the diagonal entries reflect local connectivity via degrees.^[7] To illustrate, consider the path graph P_3 on vertices v_1, v_2, v_3 with edges \{v_1, v_2\} and \{v_2, v_3\}. The adjacency matrix is

A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix},

and the degree matrix is

D = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix}.

Thus, the Laplacian is

L = \begin{pmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{pmatrix}.

^[6] Each row sums to zero, as the diagonal entry equals the sum of the absolute values of the off-diagonal entries in that row, reflecting that the degree equals the number of adjacent vertices. This property implies L \mathbf{1} = \mathbf{0}, where \mathbf{1} is the all-ones vector, so \mathbf{1} lies in the kernel of L.^[7] Since G is undirected, A is symmetric and D is diagonal (hence symmetric), making L symmetric. For positive semi-definiteness in a connected graph, consider the quadratic form \mathbf{x}^T L \mathbf{x} = \sum_{\{i,j\} \in E} (x_i - x_j)^2 \geq 0 for any \mathbf{x} \in \mathbb{R}^n, with equality if and only if \mathbf{x} is constant (i.e., the kernel is spanned by \mathbf{1}). To see this, expand \mathbf{x}^T L \mathbf{x} = \sum_i d_i x_i^2 - \sum_{\{i,j\} \in E} 2 x_i x_j = \sum_{\{i,j\} \in E} (x_i^2 + x_j^2 - 2 x_i x_j).^[6]

Directed Graphs

In directed graphs, the directionality of edges introduces asymmetries not present in undirected graphs, necessitating adapted definitions for the Laplacian matrix. One rigorous construction begins with the oriented incidence matrix B, a |V| \times |E| matrix where rows index vertices and columns index directed edges. For an edge e directed from tail vertex u to head vertex v, the entry B_{u,e} = -1, B_{v,e} = +1, and all other entries in column e are 0.^[8] A symmetric variant of the Laplacian is defined as L = B B^T. This yields a symmetric matrix whose diagonal entries equal the sum of each vertex's in-degree and out-degree, and off-diagonal entries L_{ij} (for i \neq j) equal the negative of the number of directed edges between i and j in either direction, effectively symmetrizing the adjacency.^[8] The undirected case arises as a special symmetric instance when all edges are bidirectional. The combinatorial Laplacian for directed graphs is alternatively defined as L = \Delta_{\text{out}} - A, where \Delta_{\text{out}} is the diagonal matrix with out-degrees on the diagonal, and A is the directed adjacency matrix with A_{ij} = 1 if there is a directed edge from i to j (and 0 otherwise).^[9] This form is generally asymmetric, reflecting the graph's directional structure, in contrast to the symmetric incidence-based version.^[9] For a concrete example, consider a directed 3-cycle graph with vertices \{1,2,3\} and edges $1 \to 2, $2 \to 3, $3 \to 1. The adjacency matrix is

A = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix},

and \Delta_{\text{out}} = \operatorname{diag}(1,1,1), so the combinatorial Laplacian is

L = \Delta_{\text{out}} - A = \begin{pmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ -1 & 0 & 1 \end{pmatrix}.

The oriented incidence matrix is

B = \begin{pmatrix} -1 & 0 & 1 \\ 1 & -1 & 0 \\ 0 & 1 & -1 \end{pmatrix},

and the symmetric Laplacian is

L = B B^T = \begin{pmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{pmatrix}.

Extensions for Weighted and Multigraphs

Weighted Graphs

In weighted graphs, edges are assigned real-valued weights w_{ij} \in \mathbb{R}, which generalize the binary structure of unweighted graphs by allowing the unweighted case to emerge as a special instance where existing edges have weight 1 and absent edges have weight 0.^[10] The weighted Laplacian matrix L_w extends the standard definition and is given by L_w = D_w - A_w, where A_w is the weighted adjacency matrix with off-diagonal entries (A_w)_{ij} = w_{ij} for i \neq j and zeros on the diagonal, while D_w is the diagonal weighted degree matrix with (D_w)_{ii} = \sum_{j \neq i} w_{ij}.^[11] This formulation captures the strength of connections via weights, with the diagonal entries reflecting the total weighted degree at each vertex.^[10] For graphs with positive edge weights, the weighted Laplacian admits an alternative construction using the weighted incidence matrix B_w, an oriented |V| \times |E| matrix where the entry corresponding to vertex v and edge e = \{u, v\} (oriented from u to v) is +\sqrt{w_e} at v, -\sqrt{w_e} at u, and 0 otherwise for non-incident pairs.^[11] In this case, L_w = B_w B_w^T, which underscores the positive semi-definiteness of L_w for nonnegative weights, as the quadratic form x^T L_w x = \sum_{e=\{u,v\} \in E} w_e (x_u - x_v)^2 \geq 0 for all x \in \mathbb{R}^{|V|}.^[10] When negative edge weights are permitted, the weighted Laplacian L_w can become indefinite, losing the positive semi-definite property that holds for nonnegative weights.^[12] Negative weights introduce the possibility of "repulsive" connections, and the matrix is indefinite if the absolute value of a negative weight on a single edge exceeds the inverse of the effective resistance between its endpoints in the graph formed by the positive-weight edges. For example, consider the complete graph K_3 on vertices labeled 1, 2, 3 with edge weights w_{12} = 1, w_{13} = 2, and w_{23} = -1. The weighted adjacency matrix is

A_w = \begin{pmatrix} 0 & 1 & 2 \\ 1 & 0 & -1 \\ 2 & -1 & 0 \end{pmatrix},

and the weighted degree matrix is

D_w = \begin{pmatrix} 3 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}.

Thus, the weighted Laplacian is

L_w = \begin{pmatrix} 3 & -1 & -2 \\ -1 & 0 & 1 \\ -2 & 1 & 1 \end{pmatrix}.

This matrix is indefinite, as the quadratic form for x = (0, 1, -1)^T yields x^T L_w x = -1 < 0, while forms like (1, 0, 0)^T L_w (1, 0, 0)^T = 3 > 0 are positive.^[12]

Multigraphs and Loops

In multigraphs, the off-diagonal entries of the adjacency matrix A_{ij} (for i \neq j) are defined as the multiplicity of edges connecting vertices i and j, generalizing the simple graph case where multiplicities are 0 or 1. The degree d_i of vertex i is the sum of multiplicities of all edges incident to i, counting parallel edges according to their number and self-loops with multiplicity 2 each. The Laplacian matrix is then constructed as L = D - A, where D is the diagonal matrix with entries d_i, resulting in L_{ij} = - (multiplicity between i and j) for i \neq j and L_{ii} = d_i - A_{ii}. This extension preserves the core properties of the Laplacian while accounting for edge multiplicity, and it aligns with definitions for weighted graphs where multiplicities act as integer weights.^[13] Self-loops introduce additional structure in the Laplacian for undirected graphs. A self-loop at vertex i contributes 2 to the degree d_i (to maintain the handshaking lemma) and sets A_{ii} = 1 (for a single unweighted loop, or the number of loops in general). In the Laplacian, this leads to an adjustment where the diagonal entry becomes L_{ii} = d_i including the 2 from the loop minus the 1 from A_{ii}, effectively adding 1 to the diagonal beyond the contributions from other edges. The off-diagonal entries L_{ij} (for i \neq j) remain unaffected by self-loops at i, as they depend only on edge multiplicities between distinct vertices. This convention ensures the Laplacian reflects the increased "self-connection" while the row sums equal the number of self-loops at each vertex.^[14] To illustrate, consider an undirected multigraph with vertices v_1 and v_2, two parallel edges between them, and one self-loop at v_1. The multiplicity between v_1 and v_2 is 2, and the self-loop multiplicity at v_1 is 1. The degrees are d_1 = 4 (2 from the two parallel edges plus 2 from the self-loop) and d_2 = 2 (from the two parallel edges). The adjacency matrix is

A = \begin{pmatrix} 1 & 2 \\ 2 & 0 \end{pmatrix},

the degree matrix is

D = \begin{pmatrix} 4 & 0 \\ 0 & 2 \end{pmatrix},

and the Laplacian is

L = D - A = \begin{pmatrix} 3 & -2 \\ -2 & 2 \end{pmatrix}.

Here, the self-loop increases L_{11} by 1 relative to a loop-free case with the same parallel edges.^[13] For directed multigraphs, the construction uses out-degrees instead, where the out-degree d_i^{\text{out}} sums the multiplicities of directed edges leaving i, with each self-loop contributing 1 (as it is both outgoing and incoming at i). The adjacency A_{ij} counts directed edges from i to j, including self-loops on the diagonal, and the Laplacian is L = D^{\text{out}} - A, yielding L_{ij} = - (directed multiplicity from i to j) for i \neq j and L_{ii} = d_i^{\text{out}} - A_{ii}. Self-loops thus add 1 to both the out-degree and A_{ii}, resulting in no net change to L_{ii} from the loop alone, differing from the undirected case.^[13]

Normalization Techniques

Symmetric Normalization

The symmetrically normalized Laplacian matrix, often denoted \mathcal{L}, for an undirected simple graph G with n vertices is defined as

\mathcal{L} = I_n - D^{-1/2} A D^{-1/2},

where A is the n \times n adjacency matrix with A_{ij} = 1 if vertices i and j are adjacent and 0 otherwise, D is the n \times n diagonal degree matrix with D_{ii} = d_i (the degree of vertex i), D^{-1/2} is the diagonal matrix with entries $1/\sqrt{d_i} (assuming no isolated vertices), and I_n is the n \times n identity matrix.^[15] Equivalently, \mathcal{L} = D^{-1/2} L D^{-1/2}, where L = D - A is the unnormalized Laplacian matrix.^[15] This construction scales the unnormalized Laplacian by the square roots of the vertex degrees, resulting in a symmetric matrix whose off-diagonal entries are \mathcal{L}_{ij} = -1 / \sqrt{d_i d_j} for adjacent vertices i and j, and diagonal entries \mathcal{L}_{ii} = 1.^[15] For weighted graphs, the symmetrically normalized Laplacian follows the same form, with the adjacency matrix A replaced by the weighted adjacency matrix A_w where (A_w)_{ij} = w_{ij} (the weight of edge \{i,j\}, typically positive), and D replaced by the weighted degree matrix D_w with (D_w)_{ii} = d_w(i) = \sum_{j} w_{ij}.^[15] The off-diagonal entries then become \mathcal{L}_{ij} = -w_{ij} / \sqrt{d_w(i) d_w(j)} for edges with positive weight, while the diagonal remains 1.^[15] This extension preserves the normalization, making \mathcal{L} applicable to graphs where edge weights reflect varying connection strengths, such as in network analysis.^[15] To illustrate the computation, consider the path graph P_3 with vertices labeled 1, 2, 3 and edges \{1,2\}, \{2,3\}. The adjacency matrix is

A = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{pmatrix},

and the degree matrix is

D = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{pmatrix},

D^{-1/2} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1/\sqrt{2} & 0 \\ 0 & 0 & 1 \end{pmatrix}.

The normalized adjacency is D^{-1/2} A D^{-1/2} = \begin{pmatrix} 0 & 1/\sqrt{2} & 0 \\ 1/\sqrt{2} & 0 & 1/\sqrt{2} \\ 0 & 1/\sqrt{2} & 0 \end{pmatrix}, and thus

\mathcal{L} = I_3 - D^{-1/2} A D^{-1/2} = \begin{pmatrix} 1 & -1/\sqrt{2} & 0 \\ -1/\sqrt{2} & 1 & -1/\sqrt{2} \\ 0 & -1/\sqrt{2} & 1 \end{pmatrix}.

This matrix normalizes the rows and columns by the degree scalings, with off-diagonals adjusted by \sqrt{d_i d_j}.^[15] A key property of \mathcal{L} is that its eigenvalues are real and lie in the interval [0, 2], with the eigenvalue 0 having multiplicity equal to the number of connected components in G.^[15] For a connected graph, the smallest eigenvalue is 0 with multiplicity 1, and the corresponding eigenvector is proportional to D^{1/2} \mathbf{1} (the all-ones vector scaled by square-root degrees).^[15] The largest eigenvalue is at most 2, achieved with multiplicity if the graph (or a component) is bipartite and non-trivial.^[15] These bounds hold for both unweighted and weighted cases, providing scale-invariant spectral information independent of degree variations.^[15]

Random-Walk Normalization

The random-walk normalization of the Laplacian matrix introduces asymmetric variants tailored to model transition probabilities in random walks on graphs, particularly useful for analyzing Markov chain behaviors and diffusion processes. For undirected graphs, the left normalized Laplacian is defined as L_{\text{left}} = I - D^{-1} A, where I is the identity matrix, D is the diagonal degree matrix with entries d_i = \sum_j A_{ij}, and A is the adjacency matrix.^[16] This matrix arises naturally as the generator of a continuous-time random walk, where D^{-1} A represents the row-stochastic transition matrix P, with entries P_{ij} = A_{ij} / d_i denoting the probability of moving from vertex i to adjacent vertex j.^[16] The corresponding right normalized Laplacian is L_{\text{right}} = I - A D^{-1}, which yields a column-stochastic transition matrix and is the transpose of the left variant due to the symmetry of A in undirected graphs.^[17] In directed graphs (assuming all vertices have positive out-degree to ensure invertibility), the standard random-walk Laplacian is often L_{\text{rw}} = D_{\text{out}}^{-1} L, where L = D_{\text{out}} - A is the combinatorial Laplacian with D_{\text{out}} the diagonal matrix of out-degrees d_i^{\text{out}} = \sum_j A_{ij}, and A the directed adjacency matrix (with A_{ij} = 1 if there is an edge from i to j).^[17] This yields L_{\text{rw}} = I - D_{\text{out}}^{-1} A, mirroring the left normalization for undirected cases but using out-degrees to define forward transitions in the associated Markov chain. A right variant can be constructed using in-degrees on the reversed graph, L_{\text{right}} = I - A D_{\text{in}}^{-1}, facilitating analysis of backward walks.^[17] These forms ensure the transition matrix P = D_{\text{out}}^{-1} A is row-stochastic, modeling the probabilities of stepping along outgoing edges. The eigenvalues of the random-walk Laplacian provide insights into the graph's connectivity and mixing properties. For a directed graph, the eigenvalue 0 has multiplicity equal to the number of terminal strongly connected components (those with no outgoing edges to other SCCs), with the corresponding right eigenvector being the all-ones vector restricted to each such component (assuming regularity within components); the left eigenvector relates to the stationary distribution within components.^[17] All other eigenvalues have positive real parts, ensuring convergence of the random walk to the stationary distribution \pi, which satisfies \pi^T P = \pi^T and \sum_i \pi_i = 1, serving as the left eigenvector of L_{\text{rw}} for eigenvalue 0.^[17] In the context of Markov chains, this stationary distribution \pi (often proportional to out-degrees in undirected graphs, \pi_i = d_i / (2m) where m is the number of edges) captures the long-term proportion of time spent at each vertex.^[16] Consider a simple directed graph with three vertices and edges $1 \to 2, $2 \to 3, and $3 \to 1, forming a cycle (strongly connected). The out-degree matrix is D_{\text{out}} = \operatorname{diag}(1,1,1), and A = \begin{pmatrix} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \end{pmatrix}, so L_{\text{rw}} = I - D_{\text{out}}^{-1} A = \begin{pmatrix} 1 & -1 & 0 \\ 0 & 1 & -1 \\ -1 & 0 & 1 \end{pmatrix}. The eigenvalues include 0 (with left eigenvector \pi = (1/3, 1/3, 1/3)^T, the uniform stationary distribution) and two complex conjugates with positive real parts, confirming rapid mixing in this ergodic chain.^[17] For example, if the graph consists of two disjoint directed cycles, each with positive out-degrees, the multiplicity of eigenvalue 0 is 2, reflecting the multiple terminal components.^[17] Unlike the symmetric normalization, which offers a balanced scaling for undirected spectral analysis, the random-walk normalization prioritizes asymmetric structures to directly model probabilistic transitions in walks.^[15]

Algebraic and Spectral Properties

Matrix Characteristics

The Laplacian matrix L of an undirected graph with non-negative edge weights is symmetric and positive semi-definite, meaning all its eigenvalues are non-negative real numbers.

\] This property holds for both unweighted simple graphs and graphs with positive weights, as the semi-definiteness arises from the structure of the degree matrix $D$ minus the weighted adjacency matrix $A$, where $D$ is diagonal with non-negative entries and $A$ has non-positive off-diagonals.\[

The trace of L equals the sum of the vertex degrees, since \operatorname{tr}(L) = \operatorname{tr}(D) = \sum_i d_i, where d_i is the degree of vertex i.$$] A key algebraic characterization is the quadratic form x^T L x = \sum_{(i,j) \in E} w_{ij} (x_i - x_j)^2 for any real vector x, where w_{ij} \geq 0 are the edge weights (with w_{ij} = 1 for unweighted edges); this expression is non-negative and equals zero if and only if x is constant on each connected component, directly proving the positive semi-definiteness.[

The kernel of $L$ has dimension equal to the number of connected components of the graph, and it is spanned by the indicator vectors of these components.

] Consequently, L is singular with \det(L) = 0 for any graph with at least one vertex, as the all-ones vector (or its component-wise analogs) lies in the kernel.[$$ For directed graphs, the Laplacian matrix—typically defined using out-degrees as L_{ii} = d_i^{\text{out}} and L_{ij} = -a_{ij} for i \neq j, where a_{ij} > 0 indicates an edge from i to j—is generally not symmetric and thus not positive semi-definite in the real symmetric sense.

\] However, its eigenvalues have non-negative real parts.\[

Like the undirected case, the directed Laplacian is singular due to row sums being zero.$$]

Eigenvalues and Eigenvectors

The eigenvalues of the Laplacian matrix L of an undirected graph are real and non-negative, a consequence of its positive semi-definiteness.^[18] The smallest eigenvalue \lambda_1 = 0 has multiplicity equal to the number of connected components of the graph, with the all-ones vector as the corresponding eigenvector. A key quantity is the algebraic connectivity, defined as the second-smallest eigenvalue \lambda_2, introduced by Miroslav Fiedler in 1973.^[19] For a connected graph, \lambda_2 > 0, and its value provides a measure of connectivity. The eigenvector corresponding to \lambda_2, known as the Fiedler vector, encodes structural information about the graph and is utilized in partitioning schemes to identify cuts that separate the graph into balanced components.^[19] Several bounds characterize the Laplacian spectrum. The largest eigenvalue satisfies \lambda_n \leq 2\Delta, where \Delta is the maximum degree of the graph. For induced subgraphs, Weyl's inequalities imply eigenvalue interlacing: if H is an induced subgraph of G on m vertices, then \lambda_k(H) \leq \lambda_k(G) for k = 1, \dots, m.^[20] For the normalized Laplacian \mathcal{L} = D^{-1/2} L D^{-1/2}, the eigenvalues lie in the interval [0, 2].^[21] Here, \lambda_2 relates to the Cheeger constant h(G) (the minimum conductance over subsets) via Cheeger's inequality: \frac{\lambda_2}{2} \leq h(G) \leq \sqrt{2 \lambda_2}.^[22] A representative example is the cycle graph C_n on n vertices, whose Laplacian eigenvalues are $2 - 2 \cos\left(\frac{2\pi k}{n}\right) for k = 0, 1, \dots, n-1.^[18] This spectrum illustrates the progression from \lambda_1 = 0 to \lambda_n = 4 (for even n), with \lambda_2 = 2 - 2 \cos\left(\frac{2\pi}{n}\right) quantifying the cycle's connectivity.

Interpretations and Applications

Discrete Laplace Operator

The graph Laplacian serves as a discrete analog of the continuous Laplace-Beltrami operator on Riemannian manifolds, providing a finite-dimensional approximation to the differential operator -\Delta that governs phenomena such as heat diffusion and harmonic functions in continuous domains.^[11] In this context, vertices of the graph represent sampled points on the manifold, while edges encode local connectivity, allowing the Laplacian to capture geometric structure through differences in function values at neighboring points.^[23] In finite element and finite difference discretizations, the graph Laplacian L approximates the negative continuous Laplacian -\Delta on graphs embedded in \mathbb{R}^d, where the operator scales with the mesh size h as O(h^2) to mimic the second-order nature of the differential operator.^[23] For instance, on a meshed surface, the discrete operator can be defined using kernel-based weights, such as Gaussian functions over neighboring simplices, ensuring pointwise convergence to the Laplace-Beltrami operator as the mesh refines.^[23] This approximation enables numerical solutions to partial differential equations (PDEs) on irregular domains by transforming continuous problems into linear systems solvable via matrix inversion.^[11] Graphs constructed from point clouds or meshes approximate manifolds by treating vertices as discretization points and edges as local geodesic connections, with the eigenvalues of the graph Laplacian converging to those of the continuous Laplace-Beltrami operator under refinement.^[23] Specifically, the spectrum \{ \lambda_k \} of L aligns with the eigenvalues of -\Delta, where small eigenvalues correspond to low-frequency modes on the manifold, facilitating spectral analysis in discrete settings.^[11] A representative example is the 1D path graph, which discretizes the interval [0,1] into n vertices with uniform spacing h = 1/n. Here, the Laplacian matrix L is tridiagonal with entries L_{i,i} = 2/h^2 on the diagonal and L_{i,i+1} = L_{i+1,i} = -1/h^2, directly approximating the second derivative operator d^2/dx^2.^[24] This setup allows solving the discrete Poisson equation L u = f, where f is a source term vector, yielding approximations to solutions of -\Delta u = f with boundary conditions incorporated via fixed vertex values.^[11] Convergence theorems establish that, as the graph refines (e.g., h \to 0), the discrete spectrum and eigenfunctions converge to their continuous counterparts on the manifold, with error bounds depending on mesh quality and function smoothness.^[23] For pointwise approximation, the operator error is O(h^2) under suitable conditions on the embedding and kernel choice.^[23] The quadratic form u^T L u further interprets this as a discrete Dirichlet energy, measuring total variation across edges.^[11]

Graph Clustering and Partitioning

The Laplacian matrix plays a central role in spectral clustering, a method that leverages the spectrum of the graph Laplacian to partition vertices into clusters by identifying natural groupings based on connectivity. In the basic spectral clustering algorithm, the unnormalized or normalized Laplacian is computed from the graph's adjacency matrix, and the k smallest non-zero eigenvectors are obtained via eigendecomposition. These eigenvectors form a low-dimensional embedding of the vertices, where each vertex is represented by its coordinates in this space; subsequent application of k-means clustering on these embeddings yields the final partition. This approach, popularized in a simple and effective implementation, approximates solutions to NP-hard graph partitioning problems by relaxing them into eigenvector computations.^[25] For binary partitioning (bipartition), the Fiedler vector—the eigenvector corresponding to the second-smallest eigenvalue of the Laplacian—provides a particularly effective cut, as its components naturally separate the graph into two sets by thresholding at zero or the median value, minimizing the cut while balancing cluster sizes. This vector, named after its discoverer, captures the graph's algebraic connectivity and has been foundational for recursive bisection strategies in spectral methods. A key refinement is the normalized cut criterion, which addresses imbalances in traditional min-cut by penalizing partitions that isolate small subsets; it minimizes \min_{S} \frac{\mathrm{cut}(S)}{\mathrm{vol}(S)} + \frac{\mathrm{cut}(S)}{\mathrm{vol}(V \setminus S)}, where \mathrm{cut}(S) is the sum of edge weights crossing from subset S to its complement, and \mathrm{vol}(S) is the sum of degrees of vertices in S. This combinatorial objective is relaxed into a generalized Rayleigh quotient involving the normalized Laplacian \mathcal{L} = D^{-1/2} L D^{-1/2}, solved approximately via its eigenvectors, leading to balanced clusters that preserve intra-cluster affinities.^[26] An illustrative example is the barbell graph, formed by two densely connected cliques joined by a single bridge edge; the Fiedler vector of its Laplacian exhibits a clear sign change across the bridge, assigning positive values to one clique and negative to the other, thereby perfectly separating the two natural clusters despite the min-cut favoring an unbalanced split.^[27] For multiway partitioning into k > 2 clusters, the first k smallest non-trivial eigenvectors are used to embed vertices into \mathbb{R}^k, followed by k-means or similar discretization; this extends the binary case by capturing higher-order separations, with theoretical guarantees on approximation quality for ratio cuts. Seminal work on k-way spectral methods demonstrates improved edge cuts over greedy heuristics on sparse matrices.^[28] The computational bottleneck of spectral clustering is the eigendecomposition of the n \times n Laplacian, with complexity O(n^3) in dense graphs, though Lanczos or Arnoldi iterations reduce it to O(n^2) for the top k eigenvectors in sparse cases; practical implementations often employ approximate methods like Nyström sampling for scalability to large graphs without sacrificing much accuracy.^[29]

Advanced Generalizations

Signless and Magnetic Laplacians

The signless Laplacian matrix Q(G) of an undirected graph G with adjacency matrix A(G) and degree matrix D(G) is defined as Q(G) = D(G) + A(G).^[30] This matrix differs from the standard Laplacian L(G) = D(G) - A(G) by the sign of the adjacency component, leading to distinct spectral properties suited for analyzing structural features like bipartiteness.^[31] Unlike L(G), which has a zero eigenvalue with multiplicity equal to the number of connected components, the eigenvalues of Q(G) relate directly to bipartite subgraphs and the matching number of G, with the number of eigenvalues in intervals like [0, 2n-2] providing bounds on the size of maximum matchings.^[32] For any graph G, Q(G) is positive semi-definite, ensuring all eigenvalues are non-negative real numbers.^[30] In a connected graph, the smallest eigenvalue q_{\min}(G) = 0 if and only if G is bipartite, offering a spectral criterion for bipartiteness that contrasts with the algebraic connectivity of L(G), which measures expansion via the second-smallest eigenvalue.^[31] Moreover, q_{\min}(G) provides alternative bounds on vertex connectivity and edge expansion, particularly for non-bipartite graphs where q_{\min} > 0, highlighting differences in how Q(G) and L(G) capture graph cohesion.^[33] As an example, for the complete graph K_n (n \geq 2), the spectrum of Q(K_n) consists of the eigenvalue $2n-2 with multiplicity 1 and n-2 with multiplicity n-1.^[1] The signless Laplacian finds applications in studying equitable partitions of the vertex set, where a partition is equitable if the number of neighbors in each part is constant across vertices in a given part; the spectrum of Q(G) can then be derived from the eigenvalues of the corresponding quotient matrix.^[34] The magnetic Laplacian L_{\theta}(G) extends the standard Laplacian to incorporate directional or phase information, defined as L_{\theta}(G) = D(G) - A_{\theta}(G), where A_{\theta}(G) is a complex Hermitian adjacency matrix with entries (A_{\theta})_{uv} = e^{i \theta_{uv}} if uv is an edge (and conjugate for vu), and \theta_{uv} represents a phase or flux parameter.^[35] This construction arises in modeling quantum mechanical effects on graphs, such as Aharonov-Bohm phases, and is particularly useful for directed graphs by encoding edge orientations through the phases.^[36] The eigenvalues of L_{\theta}(G) remain real and non-negative due to Hermiticity, enabling spectral analysis similar to the undirected case but sensitive to the flux \theta, which measures net phase around cycles.^[37] In applications, the magnetic Laplacian facilitates the study of flux in networks, such as detecting cyclic imbalances in directed structures akin to magnetic fields in physics, and supports quantum walk algorithms where phases influence propagation.^[37] It is employed in community detection and visualization of directed networks, where eigenfunctions reveal directional communities through flux-adjusted embeddings.^[38]^[39]

Deformed and Generalized Variants

Deformed variants of the Laplacian matrix introduce parameter-dependent modifications to the standard form, enhancing robustness in applications such as consensus algorithms and semisupervised learning. One common deformation is the quadratic form \Delta(s) = I - s A + s^2 (D - I), where A is the adjacency matrix, D is the degree matrix, and s is a real parameter; this reduces to the identity matrix at s=0 and equals the standard Laplacian at s=1.^[40] This structure arises in network centrality analysis, where solving linear systems involving \Delta(s) yields Katz-style measures robust to parameter tuning.^[41] A linear variant, L_\alpha = \alpha D + (1 - \alpha) L for \alpha \in [0,1], interpolates between the degree matrix and the standard Laplacian L = D - A, effectively adding self-loops proportional to degrees and serving as a basis for weighted generalizations.^[42] Nonlinear deformations further adapt the Laplacian for robustness against noisy or ambiguous data. In semisupervised learning, the deformed graph Laplacian \hat{L} = I - \kappa W - \kappa^2 (I - D) (with \kappa \in (0,1] and W the adjacency matrix) incorporates higher-order terms to regularize the smoothness assumption, degenerating to the standard graph Laplacian at \kappa = 1. This form improves label propagation on datasets with manifold irregularities by bounding generalization error through spectral properties.^[42] Under positive edge weights, such deformations preserve positive semi-definiteness, ensuring stable eigenvalues for optimization tasks.^[41] In electrical engineering, the admittance matrix Y for AC circuits generalizes the Laplacian to complex domains, defined as Y = G + iB, where G is the conductance matrix (real part) and B the susceptance matrix (imaginary part).^[43] Explicitly, Y = B \Upsilon B^T, with B the incidence matrix and \Upsilon the diagonal matrix of branch admittances y_e = g_e + i b_e (conductances g_e > 0); off-diagonal entries are negative admittances between nodes, while diagonals sum incident admittances.^[44] This structure analogs the weighted Laplacian, treating conductances as edge weights to model nodal voltage-current relations Y v = i in phasor domain, with semi-definiteness holding for positive real parts in connected networks.^[43] Generalized Laplacians extend to hypergraphs, capturing higher-order interactions beyond pairwise edges. The hypergraph Laplacian is L_H = D_H - B_H \Upsilon_H B_H^T, where B_H is the vertex-hyperedge incidence matrix (entries 1 if vertex in hyperedge, 0 otherwise), \Upsilon_H is diagonal with entries $1/|e| for hyperedge sizes |e|, and D_H is the diagonal degree matrix with D_{H,ii} equal to the number of hyperedges containing vertex i.^[45] For a single triangle hyperedge on three vertices, B_H is a $3 \times 1 vector of ones and D_H = I_3, yielding [ L_H = \begin{pmatrix} \frac{2}{3} & -\frac{1}{3} & -\frac{1}{3} \ -\frac{1}{3} & \frac{2}{3} & -\frac{1}{3} \ -\frac{1}{3} & -\frac{1}{3} & \frac{2}{3} \end{pmatrix},

which differs from the pairwise complete graph Laplacian (diagonals 2, off-diagonals -1) by uniform scaling over the hyperedge.[](https://arxiv.org/abs/1605.01483) With positive weights, $L_H$ remains positive semi-definite, with kernel spanned by the all-ones vector, facilitating spectral clustering on hypergraph data like social interactions or biological networks.[](https://arxiv.org/abs/1605.01483)

References

[1]
Laplacian Matrices | An Introduction to Algebraic Graph Theory
The signless Laplacian matrix of G is the n × n matrix defined as Q ( G ) := M M T When no confusion arises we write Q instead of Q ( G ) . Notice that ...
[2]
[PDF] The Laplacian
Sep 4, 2009 · The Laplacian matrix of a weighted graph G will be denoted LG. Last class, we defined it by. LG = DG − AG. We will now see a more convenient ...
[3]
[PDF] EMPIRICAL DISTRIBUTIONS OF LAPLACIAN ... - School of Statistics
Now we study the normalized Laplacian matrix Ln in (1.3). ... Kirchhoff, Über die Auflösung der Gleichungen, auf welche man bei der unter- ... 72 (1847) 497–508.
[4]
[PDF] 1 The Matrix-Tree Theorem. - MIT OpenCourseWare
The Matrix-Tree Theorem is a formula for the number of spanning trees of a graph in terms of the determinant of a certain matrix. We begin with the.
[5]
[PDF] The Laplacian Spectrum of Graphs - MIT
In this thesis we investigate the spectrum of the Laplacian matrix of a graph. Although its use dates back to Kirchhoff, most of the major results are much more ...
[6]
Laplacian matrices of graphs: a survey - ScienceDirect.com
Its Laplacian matrix is the n-by-n matrix L(G) D(G)−A(G), where A(G) is the familiar (0,1) adjacency matrix, and D(G) is the diagonal matrix of vertex degrees.
[7]
[PDF] Spectral and Algebraic Graph Theory - Computer Science
G × H is the graph with Laplacian matrix. (LG ⊗ IW )+(IV ⊗ LH). 5.3.1 The Hypercube. The d-dimensional hypercube graph, Hd, is the graph with vertex set {0,1}.
[8]
[PDF] 18.S995 - L26 - MIT Mathematics
... matrix provides an important characterization of the underlying graph. The |V |⇥|V |-Laplacian matrix can also be expressed in terms of the directed incidence.
[9]
Properties of adjacency, in-degree Laplacian, and ... - AIP Publishing
Dec 19, 2019 · A directed graph can be represented by several matrix representations, such as adjacency matrix, in-degree Laplacian matrix, and out-degree ...
[10]
[PDF] Chapter 16 - Spectral Graph Theory - Computer Science
The Laplacian matrices of weighted graphs arise in many applications. ... This is defined by a weighted complete graph H de- termined by a S ⊂ V in ...
[11]
[PDF] Graph Laplacian Tutorial
The Laplacian allows a natural link between discrete representations, such as graphs, and continuous representations, such as vector spaces and manifolds. The ...
[12]
[PDF] On the Definiteness of the Weighted Laplacian and its ... - arXiv
Aug 10, 2014 · With an appropriate labeling of the edges, we can always express the incidence matrix as E(G) = E(T ) E(C) (E(G) = E(F) E(C) ). An important ...
[13]
laplacian_matrix — NetworkX 3.5 documentation
Returns the Laplacian matrix of G. The graph Laplacian is the matrix L = D - A, where A is the adjacency matrix and D is the diagonal matrix of node degrees.
[14]
Graph.degree — NetworkX 3.5 documentation
The node degree is the number of edges adjacent to the node. The weighted node degree is the sum of the edge weights for edges incident to that node. This ...
[15]
[PDF] Lectures on Spectral Graph Theory Fan R. K. Chung
Spectral graph theory has a long history. In the early days, matrix theory and linear algebra were used to analyze adjacency matrices of graphs. Algebraic.
[16]
[PDF] Graph Laplacians and their Convergence on Random ...
In particular, we define the three graph Laplacians used in machine learning so far, which we call the normalized, the unnormalized and the random walk ...
[17]
[PDF] A Primer on Laplacian Dynamics in Directed Graphs - arXiv
Feb 7, 2020 · Common examples are: the combinatorial (comb). Laplacian, Lc ≡ D − DS = D − Q, and the random walk (rw) Laplacian,. L ≡ I − S. Here Q, D, and S ...Missing: Δ_out - | Show results with:Δ_out -
[18]
[PDF] Lectures on Spectral Graph Theory Fan R. K. Chung
Spectral graph theory has a long history. In the early days, matrix theory and linear algebra were used to analyze adjacency matrices of graphs. Algebraic.
[19]
[PDF] Eigenvalues and the Laplacian of a graph - Fan Chung Graham
Spectral graph theory has a long history. In the early days, matrix theory and linear algebra were used to analyze adjacency matrices of graphs.
[20]
[PDF] Algebraic connectivity of graphs. - SNAP: Stanford
By a well known result from the matrix theory [1] all eigenvalues of A(G, x. × G₂) are of the form μ + v where μ, v resp. are eigenvalues of A(G₁), A(G2) respec ...
[21]
[PDF] Old and new results on algebraic connectivity of graphs
This paper is a survey of the second smallest eigenvalue of the Laplacian of a graph G, best-known as the algebraic connectivity of G, denoted a(G).
[22]
[PDF] Spectra of graphs - CWI
Godsil [185] and Godsil & Royle [190]. For association schemes and distance ... where LZ is the Laplacian of ΓZ, and D is the diagonal matrix of the row sums.
[23]
[PDF] LIMIT POINTS FOR NORMALIZED LAPLACIAN EIGENVALUES
Dec 18, 2006 · values of L lie in the interval [0, 2], and that for any graph, 0 is an eigenvalue of the corresponding normalized Laplacian matrix. We note ...<|control11|><|separator|>
[24]
[PDF] Four proofs for the Cheeger inequality and graph partition algorithms
Fan Chung ∗†. Abstract. We will give four proofs of the Cheeger ... The normalized Laplacian L is defined by. L = I − D. −1/2. AD. −1/2. = D. 1/2.Missing: formula | Show results with:formula
[25]
[PDF] Discrete Laplace Operator on Meshed Surfaces
The Laplacian can be used as a smoothness penalty to choose functions varying smoothly along the manifold [23] or to smooth the surface itself via the mean ...
[26]
[PDF] DISCRETE DIFFERENTIAL GEOMETRY - Keenan Crane
For a 1D Laplace equation, can we always satisfy Dirichlet conditions? Yes: a line can interpolate any two points. 1D Laplace: Solutions: Page 50. Laplace w ...
[27]
[PDF] On Spectral Clustering: Analysis and an algorithm Andrew Y. Ng CS ...
In this paper, we present a simple spectral clustering algorithm that can be implemented using a few lines of Matlab. Using tools from matrix perturbation ...
[28]
[PDF] Normalized cuts and image segmentation - People @EECS
SHI AND MALIK: NORMALIZED CUTS AND IMAGE SEGMENTATION. 889. Fig. 1. A case where minimum cut gives a bad partition. Page 3. groups, are in fact identical and ...
[29]
[PDF] A Tutorial on Spectral Clustering - People | MIT CSAIL
Each adjacency matrix which coincides with W on all off-diagonal positions leads to the same unnormalized graph Laplacian L. In particular, self-edges in a ...
[30]
https://journals.uwyo.edu/index.php/ela/article/view/857/857
[31]
[PDF] Fast Approximate Spectral Clustering - People @EECS
ABSTRACT. Spectral clustering refers to a flexible class of clustering proce- dures that can produce high-quality clusterings on small data sets.
[32]
View of Graphs determined by their (signless) Laplacian spectra
Feb 10, 2010 · A graphGis said tobe determined by its Laplacian spectrum(resp.adjacencyspectrum, signless Laplacian spectrum) if there does not exist a non ...
[33]
[PDF] BIPARTITE SUBGRAPHS AND THE SIGNLESS LAPLACIAN MATRIX
The signless Laplacian matrix (Q) is related to bipartite subgraphs; its smallest eigenvalue indicates if a graph is not bipartite. The smallest eigenvalue of ...Missing: origin | Show results with:origin
[34]
Distribution of signless Laplacian eigenvalues and graph invariants
Oct 1, 2024 · In this paper, we give relationships between the number of signless Laplacian eigenvalues in specific intervals in and graph invariants including matching ...
[35]
[PDF] 1 Key Matrices in Graph Theory
• Eigenvalues are non-negative. • positive definite, diagonally dominant. Theorem 2. The least eigenvalue of the signless Laplacian of a connected graph is ...
[36]
Signless Laplacian spectrum of power graphs of finite cyclic groups
Mar 19, 2019 · In particular, using the theory of Equitable Partitions, we have completely determined the Signless Laplacian spectrum of power graph of Z n ...
[37]
[PDF] MagNet: A Neural Network for Directed Graphs - arXiv
Jun 11, 2021 · MagNet is a spectral GNN for directed graphs using a magnetic Laplacian, a complex Hermitian matrix, to encode directional information.
[38]
[PDF] Magnetic Eigenmaps for the Visualization of Directed Networks
Oct 28, 2016 · Abstract. We propose a framework for the visualization of directed networks relying on the eigenfunctions of the magnetic Laplacian, called ...
[39]
[PDF] The discrete magnetic Laplacian: geometric and spectral preorders ...
important applications is in chemical graph theory [Bal76; Tri92], where the graph theory is a useful tool because a graph is a mathematical object to represent ...
[40]
Magnetic eigenmaps for community detection in directed networks
It is widely known in the physics community that the presence of a magnetic flux can be detected in quantum mechanics thanks to the Aharonov-Bohm effect [23] .
[41]
Magnetic Eigenmaps for the visualization of directed networks
We propose a framework for the visualization of directed networks relying on the eigenfunctions of the magnetic Laplacian, called here Magnetic Eigenmaps.
[42]
[PDF] The Deformed Graph Laplacian and Its Applications to Network ...
Jun 18, 2021 · The deformed graph Laplacian has been studied in [36] because of its applications to consensus algorithms in multiagent systems and robotics.
[43]
The Deformed Graph Laplacian and Its Applications to Network ...
We show that the resulting Katz-style centrality measure may be computed via the so-called deformed graph Laplacian---a quadratic matrix polynomial that can be ...
[44]
[PDF] Deformed Graph Laplacian for Semisupervised Learning
of a more general theory of deformed differential operators developed in mathematical physics [13]. The deformation technique was initially proposed for the ...
[45]
[PDF] Electrical Networks and Algebraic Graph Theory - Francesco Bullo
The grounded Laplacian. Lground is also an interesting algebraic graph and matrix theory concept in its own right and studied in [100], [69]. Non-singular ...
[46]
[PDF] The Admittance Matrix and Network Solutions - arXiv
Jul 21, 2025 · Mathematically, the admittance matrix is equivalent to a weighted graph Laplacian. The ordinary graph Laplacian is the matrix as just ...
[47]
[1605.01483] Spectral Properties of Hypergraph Laplacian and ...
May 5, 2016 · In this paper we introduce a new hypergraph Laplacian operator generalizing the Laplacian matrix of graphs.