Graph Laplacian
📂Graph TheoryGraph Laplacian
Definition
Let the degree matrix of a graph be D and the adjacency matrix be A. Then, the graph Laplacian L of G is defined as follows:
L:=D−A
Explanation
Unlike the Laplacian Δ=i∑∂xi2∂2 defined for functions over Euclidean space, it depends on the given graph.
For the graph G=(V,E), denote f:V→R as the node signal and represent it as f=[f(v1)⋯f(vn)]T. Then, each component of Lf indicates how much the value at each vertex differs from the values at adjacent vertices.
Derivation
For a multivariable function g:Rn→R, the Laplacian is defined as follows:
∇2g=Δg=∂x12∂2g+⋯+∂xn2∂2g
The differential of a function f:R→R defined over real space can be numerically approximated as follows:
f′(x)=hf(x+h)−f(x)
f′′(x)=h2f(x+h)−2f(x)+f(x−h)(1)
Let’s consider the above equation for a graph. If we see x as a vertex, x+h and x−h can be viewed as vertices connected to x. f(x) preceding 2 indicates that there are two adjacent points to x. Therefore, from the graph perspective, (1) represents subtracting the value of the reference vertex from the values at adjacent vertices by the degree. Expressing it mathematically yields A−D, but reversing the sign yields a positive definite matrix, thus defined as follows:
L:=D−A
■
Properties
- The graph Laplacian L is a positive definite matrix.
Proof
1.
Let D=[Dij] and A=[Aij] be the degree matrix and adjacency matrix, respectively. Let x∈Rn be as follows:
xTLx=xT(D−A)x=xTDx−xTAx=i=1∑nDiixi2−i,j=1∑nAijxixj=i=1∑n(j=1∑nAij)xi2−i,j=1∑nAijxixj
Here, i,j is a dummy index and since A is a symmetric matrix, ∑i,jAijxi=∑i,jAijxj holds true. Therefore, we obtain the following:
xTLx=i,j=1∑nAij(xi2−xixj)=21i,j=1∑nAij(2xi2−2xixj)=21i,j=1∑nAij(xi2+xj2−2xixj)=21i,j=1∑nAij(xi−xj)2
Since Aij≥0, L is a positive definite matrix.
■