Graph Laplacian

In graph theory, the graph Laplacian, also referred to as Laplacian matrix, admittance matrix, or Kirchhoff matrix, is a matrix representation of a graph. The graph Laplacian matrix can be viewed as a matrix form of the negative discrete Laplace operator on a graph approximating the negative continuous Laplacian obtained by the finite difference method.

Graph Laplacian naturally captures the phenomenon of network flooding. For example in social network modeling, Graph Laplacians are used to model spread of information (such as opinions and rumors) over time, due to diffusion property. Simple models operate under the assumption that every initial condition evolves towards consensus, defined as locally-constant solutions, However in more complex settings this is not necessarily the case.

Definition

Given a graph $G$ with adjacency matrix $\mathbf{A}$ and a degree matrix $\mathbf{D}$, the graph Laplacian $\mathbf{L}_G$ is defined as:

$$\mathbf{L}_G = \mathbf{D}_G - \mathbf{A}_G$$

Physical meaning

Given a vertex $v \in G$ equipped with a time-dependent function $x(t)$, the Laplacian operator acts on it by diffusion for some $\alpha > 0$:

$$\dot{x}(t) = -\alpha \mathbf{L}_G x(t)$$

Equivalently, in discrete time case, where the state the state of a node is given by a sequence $(x_t)$:

$$x_{n+1} = (\mathbf{I} - \alpha \mathbf{L}_G) x_n$$

Discrete Laplacians can be thought of in a familiar setting for engineers in the context of Kirchhoff's current laws which state that an algebraic sum of directed currents meeting at a node is zero.

Symmetric Laplacian

The Symmetrically normalized Laplacian is defined as:

$$\mathbf{L}^\mathrm{sym}_G := (\mathbf{D}^+_G)^{1/2} \mathbf{L}_G(\mathbf{D}^+_G)^{1/2}$$

For undirected graph with weighted edges one can define a weighted incidence matrix $\mathbf{W}_G$ and use it to construct the corresponding symmetric Laplacian as

$$\mathbf{L}_G = \mathbf{W}_G\mathbf{W}_G^\mathrm{T}$$

Properties

For an undirected graph $G$ and it's Laplacian $\mathbb{L}$ with eigenvalues $\lambda_0 \leq \lambda_1 \leq \cdots \leq \lambda_{n-1}$:

• Graph Laplacian is symmetric.
• Graph Laplacian is positive-semidefinite, (real parts of its eigenvalues are non-negative).
• Graph Laplacian's off-diagonal entries are nonpositive, yet the real parts of its eigenvalues are nonnegative.
• Every row sum and column sum of Graph Laplacian is zero.
• The number of connected components in the graph is the dimension of the nullspace of the Laplacian, (this is equivalent to 0-th Betti number).

The smallest non-zero eigenvalue of the graph Laplacian extends the notion of a spectral gap to graph theory. The second smallest eigenvalue of L (could be zero) is the algebraic connectivity (or Fiedler value) of G and approximates the sparsest cut of a graph.

Graph Fourier Transform

The graph Fourier transform extends the notion of Fourier transform to graphs and eigendecomposes the Laplacian matrix of a graph into eigenvalues and eigenvectors. Analogously to the classical case, the eigenvalues represent frequencies and eigenvectors form what is known as a graph Fourier basis.

The Graph Fourier transform is important in spectral graph theory. It is widely applied in the recent study of graph structured learning algorithms, such as the widely employed convolutional networks.

Given an undirected weighted graph $G = (V,E)$, where $V$ is the set of nodes with $|V| = N$ ($N$ being the number of nodes) and $E$ is the set of edges, a graph signal $f: V \rightarrow \mathbb{R}$ is a function defined on the vertices of the graph $G$. The signal $f$ maps every vertex $\{v_i\}_{i=1,\ldots,N}$ to an associated height function $f_i : v_i \to \mathbb{R}$. Any graph signal can be projected on the eigenvectors of the Laplacian matrix $\mathbf{L}$.

Let $\lambda_l$ and $\mu_l$ be the $l_\text{th}$ eigenvalue and eigenvector of the [[Laplacian]] matrix $\mathbf{L}$ (the eigenvalues are sorted in an increasing order, i.e., $\lambda_0\leq\lambda_1\leq\cdots\leq\lambda_{N-1}$, the graph Fourier transform (GFT) [$\hat{f}$ of a graph signal $f$ on the vertices of $G$ is the expansion of $f$ in terms of the eigenfunctions of $\mathbb{L}$.

$$\mathrm{G F}[f](\lambda_{l})=\hat{f}\left(\lambda_{l}\right)=\langle f, \mu_{l}\rangle=\sum_{i=1}^{N} f(i) \mu_{l}^*(i)$$

where $\mu_l^* = \mu_l^\text{T}$.

Since $\mathbb{L}$ is a real symmetric matrix, its eigenvectors $\{\mu_l\}_{l=0,\cdots, N-1}$ form an orthogonal basis. Hence an inverse graph Fourier transform (IGFT) exists, and it is written as:

$$\mathrm{IGF}[\hat{f}](i)=f(i)=\sum_{l=0}^{N-1} \hat{f}(\lambda_l) \mu_l(i)$$

See also

• Laplacian
• Laplacian centrality
• Spectral sheaf theory
• Hodge theorem

(edit) Topics in Graph Theory, Networks, and Econophysics (📁) Phenomena Centrality • Scale-free networks • Social network analysis • Community identification • Systems biology • Resilience • Cascade • Network scaling • Dynamical networks • Adaptive networks • Trophic coherence • Neural gas model • Quenched Disorder

(edit) Topics in Topological Data Analysis (📁) Background Point-set topology • Algebraic topology Manifolds Manifold • Configuration space • Differentiability • Vector space (bundle) • Tangent space (bundle) • Cotangent space (bundle) • Vector field (Flow, Critical points) • Braid • Transversality • Whitney embedding theorem • Stratified space Complexes CW Complex • Δ-Complex • Regular Complex (Simplicial, Cubical, Vietoris-Rips, Čech, Witness, Flag, Strategy • Decision Task) • Nerve • Phylogenetic tree • Discretized graph configuration space • State complex Euler Characteristic Euler characteristic • Curvature • Nonvanishing vector field • Fixed point index • Tame topology • Euler calculus • Target enumeration • Fubini theorem • Euler integral transform • Intrinsic volume • Gaussian random field Exact Sequences Chain homotopy • Snake lemma • Good pair • Mayer-Vietoris sequence • 5-lemma • Cellular homology • Coverage • Degree • Sperner's Lemma • Borsuk-Ulam theorem • Short exact sequence • Lefschetz index • Nash equilibrium • Hex • Barcode • Space of natural images • Zigzag persistence Homology Simplicial homology • Künneth theorem • Coefficient • Singular homology • Reduced homology • Čech homology • Relative homology • Excision Theorem • Local homology • Relation homology • Functoriality • Inverse kinematics • Winding number • Brouwer fixed point theorem Cohomology Duality • Cochain complex • Cohomology • Universal coefficient theorem • Poincaré duality • Alexander duality • Helly's Theorem • Numerical Euler integration • Forms • De Rham cohomology • Cup product • Helicity Theorem • Laplacian • Hodge Theorem • Cohomological coordination Morse Theory Morse homology • Excursion set • Definable functional • Euler-Fourier transform • Stratified Morse theory • Conley index • Forcing theory • Attractor-repeller pairs • Floer homology • Symplectic form • Hamiltonian field • Arnold's Conjecture • Lefschetz-Hopf theorem • Stratified Lefschetz-Morse Index • Discrete Morse theory • LS category • Unimodal decomposition Homotopy Fundamental group • Van-Kampen theorem • Covering space • Knot • Braid • Seifert conjecture • Higher homotopy groups • Biaxial nematics • Hurewicz Theorem • Whitehead Theorem • Eilenberg-MacLane space • Topological social choice • Fiber bundle • Section • Path space • Farber lemma • Sectional category • Topological complexity • Fibration • Homotopy extension property • Model category • Homotopy type theory Sheaves Cellular sheaf • Local cohomology • Fiber homology • Sheaf cohomology • Global sections theorem • Linear sheaf • Flow sheaf • Network coding sheaf • Information flow theorem • Čech cohomology • Preseaf • Stalk • Gluing axiom • PDE sheaf • Operations on sheaves • Vietoris mapping theorem • Sheaf-theoretic Nyquist-Shannon • Fourier-Sato transform • Cosheaf • Bézier curve • Barcodes • Interval Indecomposables • Étale Space • Leray spectral sequence • Spectral sheaf theory • Sheaf neural network Categorification Category • Groupoid • Monoid • Morphism • Equalizer • Functor • Kan complex • Nerve • Clustering • Natural transformation • Cone • Interleaving Limit • Terminal object • Product • Pullback • Homology Colimit • Initial object • Coproduct • Pushout • Cohomology Topological sheaf • Sheaf operations • Derived functors