The graph Laplacian is a matrix or linear operator that measures how a function on the vertices of a graph differs from its values at neighboring vertices. For a finite, undirected graph with nonnegative edge weights, its standard form is , where is the adjacency matrix and is the diagonal matrix of weighted vertex degrees. It is a discrete counterpart of the negative Laplace operator, with closely related interpretations in energy minimization, diffusion, and potential theory.
The graph Laplacian connects graph theory with linear algebra, probability, geometry, and computation. Its eigenvalues reveal connected components and bottlenecks; its equations describe electrical potentials and averaging processes; and its determinants count spanning trees. Normalized versions underpin random walks and spectral clustering, while large sparse Laplacian systems are central to numerical algorithms. Several conventions coexist, so the choice of weights, normalization, sign, and treatment of isolated vertices is part of the operator’s definition.
Definition and normalization conventions
Let be a finite undirected graph with vertices. For distinct vertices and , let , with when there is no edge. Initially assume that the graph has no self-loops. Its adjacency matrix is , and its weighted degrees are
Writing , the combinatorial Laplacian is
A vector can be interpreted as a real-valued function on the vertices. Then
The operator therefore records weighted differences rather than absolute values. Adding the same constant to every entry of leaves unchanged.
Two normalized versions are widely used. If every degree is positive, the symmetric normalized Laplacian and random-walk Laplacian are
The former is symmetric in the ordinary Euclidean inner product. The latter acts as
comparing a value with the weighted average of its neighbors. These matrices are related by matrix similarity:
so they have the same eigenvalues, although their eigenvectors have different scalings. On an -regular graph, both reduce to .
Isolated vertices require an explicit convention because does not exist. One common choice sets the relevant inverse-degree entries to zero and defines . An isolated vertex then contributes a zero row and column. Under this convention, the formula must be modified on isolated vertices: its identity term is replaced by the projection onto positive-degree vertices. Other conventions assign a diagonal entry of one to an isolated vertex, changing zero-eigenvalue multiplicities.
Self-loops also require care because graph-theoretic degree conventions differ. If degrees are defined as adjacency row sums, loop contributions cancel in , although they can still affect normalized operators through . Finally, some authors call the Laplacian. The positive-semidefinite convention is standard in much of spectral graph theory; the negative convention more directly resembles the usual analytic sign of the differential Laplacian.
Incidence factorization, energy, and boundary problems
The Laplacian can be constructed from a discrete gradient. Assign an arbitrary orientation to each of the undirected edges, and form the incidence matrix . A row corresponding to an edge directed from to has at , at , and zero elsewhere. If is the diagonal matrix of edge weights, then
Changing an edge orientation multiplies its row of by , leaving this product unchanged. Thus the orientation is an algebraic convenience, not additional graph structure.
The vector contains differences of vertex values across edges. Multiplication by weights those differences, and aggregates them back at vertices. This factorization is the discrete analogue of composing a gradient with a divergence. In particular, the associated quadratic form is
It is often called the graph’s Dirichlet energy. A convention including an additional factor of is also common; the minimizing functions are unaffected.
This identity proves that is symmetric and positive semidefinite. It also gives an exact description of its null space: energy vanishes precisely when is constant on every connected component of the positive-weight graph. If there are components, the null space has dimension , and the rank is . The energy is therefore a measure of variation across actual edges, not of variation between arbitrary pairs of vertices.
A graph boundary-value problem fixes on a set of boundary vertices and minimizes energy over the remaining vertices. At each unconstrained vertex, the stationarity condition is
For , this becomes
Such a harmonic function equals the weighted average of its neighboring values. If every connected component meets the boundary, the interior principal submatrix of is positive definite and the extension is unique. The averaging identity also implies a discrete maximum principle: interior values cannot exceed the largest boundary value or fall below the smallest one.
Without prescribed boundary values, the graph version of Poisson’s equation is . It is solvable exactly when the entries of sum to zero separately on each component. Solutions are then unique only up to an additive constant on each component. These compatibility conditions express both the algebraic singularity of and the physical requirement that a closed component have balanced sources and sinks.
Eigenvalues, connectivity, and graph cuts
Because is real and symmetric, the spectral theorem supplies an orthonormal basis of eigenvectors with nonnegative eigenvalues. In increasing order, write
For a connected graph, the zero eigenvalue is simple and its eigenvector is the constant vector. The second eigenvalue , called the algebraic connectivity, is positive exactly when the graph is connected. Miroslav Fiedler’s 1973 work established this quantity as a central measure of graph connectivity; a corresponding eigenvector is commonly called a Fiedler vector.
The Rayleigh quotient gives the variational characterization
A small value means that some nonconstant function changes little across edges relative to its overall size. One way this occurs is when two internally well-connected regions are joined by only a few weak edges: the function can be nearly constant within each region and take different values across the weak connection. Eigenvectors thus encode more than reachability; they reveal weakly coupled parts of a connected graph.
Normalized eigenvalues are naturally tied to degree-weighted cuts. For a connected graph with at least two vertices, define
Its conductance is
If is the second eigenvalue of , the graph Cheeger inequality states
The bounds relate a continuous optimization over vectors to a discrete optimization over vertex subsets. Thresholding a suitably scaled normalized eigenvector produces candidate cuts underlying the upper bound.
Simple graphs illustrate the range of behavior. The unweighted complete graph on vertices has Laplacian spectrum . The path on vertices has eigenvalues
so its algebraic connectivity is asymptotic to . Long paths therefore have slowly varying low-energy modes.
The spectrum does not determine every feature of a graph: nonisomorphic graphs can have identical Laplacian spectra. Nevertheless, it determines several structural invariants, including the number of components and the sum of weighted degrees, since
For normalized Laplacians, all eigenvalues lie in ; a connected graph with an edge has eigenvalue exactly when it is bipartite.
Diffusion, random walks, and consensus
The graph heat equation is
Its solution is
where the exponential is a matrix function. If , the component along is multiplied by . Constant components persist, while higher-energy components decay faster. On a connected graph,
This limit follows from the one-dimensional null space and expresses conservation of the unweighted sum of vertex values.
The matrix also serves as the generator of a continuous-time Markov chain. From vertex , jumps to occur at rate , so the total departure rate is . Because the rates are symmetric, the uniform distribution is stationary on a connected graph. Here is a transition matrix as well as a heat-propagation operator. For column probability vectors, symmetry ensures that the same matrix gives forward evolution.
A different clock produces the normalized walk. The matrix
is the transition matrix of a discrete-time random walk that chooses the next vertex with probability proportional to edge weight. Its stationary distribution on a connected graph is
The operator generates a continuous-time chain whose jump attempts occur at unit rate. Acting on vertex-valued functions, its evolution converges to the degree-weighted mean:
Thus combinatorial and normalized diffusion generally conserve different averages.
The normalized spectral gap controls relaxation in continuous time. Discrete-time convergence also depends on periodicity: a random walk on a connected bipartite graph alternates between the two parts. Replacing by the lazy transition matrix introduces a holding probability and removes this oscillation. Continuous-time evolution does not have the same periodicity obstruction.
The same equations model consensus in networks of interacting agents. If agent adjusts its state according to
then , and a connected undirected network reaches agreement at the initial arithmetic mean. The slowest nonconstant mode decays as , making algebraic connectivity a convergence-rate parameter. Time-dependent weights, delays, directed interactions, and nonlinear update rules require additional analysis; the fixed undirected Laplacian supplies the basic linear model.
Electrical networks and effective resistance
An undirected weighted graph represents a resistor network when is interpreted as conductance, the reciprocal of resistance. If denotes electric potential, Ohm’s law gives current from to . Kirchhoff’s current law then becomes
where is the externally injected current at vertex . The compatibility condition on a connected network states that total injected current must equal total extracted current.
Because potential is defined only up to a constant, the Moore–Penrose pseudoinverse is useful. It inverts the positive eigenvalues of and leaves its null space at zero. For balanced , the vector is the unique solution with zero mean. Equivalently, one may ground a vertex, remove its row and column, and solve the resulting positive-definite system for the remaining potentials.
The effective resistance between vertices and is the potential difference produced by injecting one unit of current at and extracting it at :
Unlike shortest-path distance, this quantity incorporates every available route. A path of unit-resistance edges has effective resistance between its endpoints. If disjoint paths of equal resistance connect the same terminals and have no other connections, their parallel combination has resistance . In the complete graph with vertices and unit conductances, every pair has effective resistance .
The energy principle has a dual formulation in terms of edge currents. With an oriented incidence matrix , a current vector has net injection . Thomson’s principle states
assuming positive edge conductances. The electrical current uniquely minimizes dissipated energy among all unit flows between the terminals. This characterization yields Rayleigh monotonicity: adding conductance, or adding a new conducting edge, cannot increase effective resistance.
Resistance also links electrical networks to probability. For the discrete-time weighted random walk, let be the expected number of steps needed to reach starting at . Then
This commute-time identity concerns the discrete-time walk, rather than every possible continuous-time convention. Effective resistance is therefore simultaneously a voltage response, a minimum flow energy, and a measure of random-walk accessibility.
Spanning trees and determinant identities
The Laplacian encodes global combinatorial information through determinants. A spanning tree is a connected, cycle-free subgraph containing every vertex. For a weighted graph, assign a tree the weight
and let
The matrix-tree theorem, associated with Gustav Kirchhoff’s 1847 analysis of electrical networks, states that deleting any one row and the corresponding column from produces a matrix whose determinant is . For an unweighted graph, this is the ordinary number of spanning trees.
The incidence factorization explains the connection. Delete one column from , obtaining a reduced incidence matrix . The corresponding principal minor is . Applying the Cauchy–Binet determinant identity expands its determinant over sets of edges. A selected edge set contributes zero unless it is a spanning tree. For a spanning tree, the reduced incidence determinant is or , so its squared contribution is exactly the product of the selected edge weights. A determinant thus performs an exact sum over a potentially enormous family of subgraphs.
For a connected graph, the eigenvalue form is
The complete graph has nonzero eigenvalues all equal to , yielding Cayley’s formula . A cycle on vertices has spanning trees, obtained by deleting any one edge. If a graph is disconnected, no spanning tree exists, and every cofactor in this formula is zero.
Spanning-tree probabilities connect determinants back to resistance. Suppose a random tree is chosen with probability . For an edge ,
The quantity on the right is sometimes called the edge’s leverage score. It is one for a bridge, because every spanning tree must contain that edge, and is smaller when alternate routes make the edge replaceable. Summing over edges gives
matching the number of edges in every spanning tree.
Related determinant identities count forests. For example,
generates spanning rooted forests: each forest component carries one chosen root, and the power of records its number of edges. Thus a single polynomial in the Laplacian contains weighted counts of structures ranging from isolated rooted vertices to spanning trees. These identities make Laplacians useful in exact enumeration as well as in continuous optimization and stochastic processes.
Sparse computation and spectral approximation
For a graph with vertices and edges, has at most potentially nonzero entries. It is therefore naturally represented as a sparse matrix, and multiplication by a vector costs . The incidence representation permits matrix-vector multiplication directly from an edge list, without constructing a dense matrix. These properties make Laplacians a major test case in numerical linear algebra.
Solving requires handling its null space. On a connected graph, one can impose , ground one vertex, or work directly in the subspace orthogonal to constants. Grounding produces a symmetric positive-definite principal submatrix, enabling Cholesky decomposition and the conjugate gradient method. Sparse direct factorization can nevertheless introduce fill-in: entries that were initially zero become nonzero in the factors. Elimination ordering and graph structure strongly affect memory requirements and running time.
Iterative convergence depends on spectral conditioning. On the constant-orthogonal subspace, the combinatorial Laplacian has condition number . A graph with a narrow bottleneck can therefore produce a difficult unpreconditioned system even when it has few edges. Preconditioning replaces the original geometry with one in which the relevant eigenvalues are more tightly clustered. Multilevel methods, approximate factorizations, and low-stretch spanning trees exploit graph structure to construct such preconditioners.
A spectral sparsifier is a reweighted graph with fewer edges whose Laplacian satisfies
for every vector . This is stronger than preserving a selected set of eigenvalues or merely maintaining connectivity. It approximately preserves all graph energies, and consequently all cuts. On a connected graph, inversion on the constant-orthogonal subspace also gives corresponding multiplicative control of effective resistances.
Sampling edges according to quantities related to , followed by reweighting, provides a principled sparsification method. Edges that are difficult to replace electrically receive greater sampling priority. Daniel Spielman and Shang-Hua Teng’s work, announced in 2004, established nearly linear-time approaches to solving Laplacian and related symmetric diagonally dominant systems. Here “nearly linear” allows polylogarithmic factors and accuracy dependence; it does not mean that every practical implementation runs in strict time.
Large-scale spectral calculations also avoid full diagonalization. Lanczos-type methods approximate a small number of eigenpairs, while polynomial or rational approximations can apply diffusion and other spectral filters without explicitly computing eigenvectors. The choice between direct, iterative, and multilevel methods depends on graph structure, requested accuracy, and whether many systems with the same Laplacian must be solved.
Spectral clustering, graph signals, and learning
A graph can represent similarities among data points, with larger edge weights indicating stronger affinity. Laplacian eigenvectors then provide coordinates adapted to those relationships rather than to the original measurement axes. In spectral clustering, a small collection of low-frequency eigenvectors is used to embed vertices into a Euclidean space, after which a conventional clustering method partitions the embedded points. The construction is particularly useful when clusters are connected but nonconvex in the original feature space.
The connection to partitioning follows from indicator vectors. For a subset ,
Cut objectives become quadratic expressions in discrete-valued vectors. Relaxing the requirement that vectors be indicators yields eigenvalue problems. Degree-balanced objectives lead to the generalized equation
equivalent to a normalized Laplacian problem when all degrees are positive. Jianbo Shi and Jitendra Malik’s 2000 normalized-cut method applied this perspective to image segmentation. Different balancing terms produce different relaxations, so unnormalized and normalized clustering are not interchangeable.
A graph signal is simply a function , such as temperatures at connected sensors or measurements on a transportation network. If form an orthonormal eigenbasis of , its graph Fourier coefficients are
The analogy with the Fourier transform is based on energy: eigenvectors with small eigenvalues vary slowly across strongly weighted edges, while high-eigenvalue modes vary more rapidly. A spectral filter takes the form
For example, gives heat smoothing.
Polynomial filters have a useful locality property. Because multiplying by only mixes a vertex with its neighbors, a polynomial of degree depends only on vertices within graph steps. This connects spectral filtering with local message-passing procedures used in graph-based machine learning. Repeated smoothing, however, suppresses distinctions between vertices; unrestricted diffusion on a connected graph eventually leaves only a constant signal.
Laplacians also supply regularization penalties. Given labels on a subset , one can estimate a function by minimizing
The second term encodes the assumption that strongly connected vertices should have similar predictions. With fixed labels and no interior fitting term, the solution becomes a harmonic extension. The substantive assumption lies in graph construction: neighbor selection, weight bandwidth, degree normalization, and disconnected components can materially change the result. A Laplacian faithfully expresses its chosen graph, not an independently guaranteed notion of meaningful similarity.
Continuum limits, directed graphs, and higher-order operators
The analogy between graph and differential Laplacians becomes precise only after specifying scaling and geometry. On a one-dimensional grid with spacing , an interior row of the unweighted path Laplacian gives
For values sampled from a sufficiently smooth function,
Thus , not the unscaled matrix, approximates the negative second derivative. Boundary vertices require separate treatment because their degrees differ and encode particular boundary behavior.
For points sampled from a manifold, local neighborhood graphs can approximate differential operators such as the Laplace–Beltrami operator. Weights may be based on a shrinking distance kernel, and consistency depends on sample size, neighborhood scale, normalization, and regularity assumptions. Nonuniform sampling generally introduces density-dependent effects unless an appropriate correction is applied. The continuum limit is therefore not determined by the phrase “graph Laplacian” alone. Laplacian eigenmaps, introduced by Mikhail Belkin and Partha Niyogi in work published in 2003, use low eigenvectors as coordinates for nonlinear dimensionality reduction.
Geometric discretizations provide another important distinction. In the finite element method, a stiffness matrix represents a gradient energy, while a mass matrix represents the underlying measure or inner product. The resulting eigenproblem often has the form
A cotangent-weight Laplacian on a triangular mesh belongs to this geometric family. Some cotangent weights can be negative even though the assembled stiffness energy is nonnegative. Consequently, properties that rely on every edge weight being nonnegative—such as a direct averaging interpretation or certain maximum principles—need not hold without additional mesh conditions.
For a directed graph, the out-degree Laplacian generally is not symmetric. Its eigenvalues can be complex, left and right null spaces differ, and the undirected quadratic-energy formula no longer applies directly. Random-walk generators remain meaningful, but stationary distributions replace uniform measures in many constructions. Stationary-measure symmetrizations and magnetic Laplacians provide alternative ways to retain aspects of direction while obtaining self-adjoint operators; they encode different information rather than a single canonical extension.
Higher-dimensional analogues arise in algebraic topology. For a simplicial complex with boundary matrices , the unweighted combinatorial Hodge Laplacian on -chains is
At dimension zero it recovers the ordinary graph Laplacian. In higher dimensions it acts on edge flows, triangle data, and other higher-order signals. Its null space represents harmonic chains and has dimension equal to the corresponding Betti number, linking Laplacian analysis with homology and the detection of topological holes.