相关概念

在介绍拉普拉斯矩阵之前,我们要了解图的一些其他的概念

无向图

无向图 G G G:

简单来说就是边没有方向的图称为无向图。对于无向图的定义为: G = < V , E > G=<V,E> G=<V,E>,其中: V V V为所有顶点组成的非空集合,称为顶点集 E E E V V V中元素构成的无序二元组的集合,称为边集,无向图中的边均是顶点的无序对,无序对通常用圆括号表示。
例如上图,顶点集 V = { A , B , C , D , E , F , G } V=\{A,B,C,D,E,F,G\} V={ A,B,C,D,E,F,G},边集 E = { ( A , C ) , ( A , E ) , ( B , G ) , ( B , E ) , ( C , E ) , ( D , G ) , ( G , F ) } E=\{(A,C),(A,E),(B,G),(B,E),(C,E),(D,G),(G,F)\} E={ (A,C),(A,E),(B,G),(B,E),(C,E),(D,G),(G,F)}

邻接矩阵

邻接矩阵: W ∈ R n × n W\in R^{n\times n} WRn×n
邻接矩阵是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图,其中 V = { v 1 , v 2 , … , v n } V=\{v_1,v_2,…,v_n\} V={ v1,v2,,vn}。无向图的邻接矩阵一定是对称的,且对角线为0,而有向图的邻接矩阵不一定对称。用邻接矩阵表示图,很容易确定图中任意两个顶点是否有边相连。下图所示就是一个无向图的邻接矩阵。

度矩阵

度矩阵: D ∈ R n × n D\in R^{n\times n} DRn×n , D i i = ∑ j W i j D_{ii}=\sum_j W_{ij} Dii=jWij,度数矩阵是一个对角矩阵。
简要来说就是从 i i i出发的所有边的权重之和,对角线元素非0,下图假设边权重为1。

拉普拉斯算子

拉普拉斯矩阵是图上的一种拉普拉斯算子,证明见论文Discrete Regularization on Weighted Graphs for Image and Mesh Filtering。
定义:拉普拉斯算子(Laplace Operator)是n维欧几里德空间中的一个二阶微分算子,定义为梯度(▽f)的散度(▽·f)。 Δ f = ∇ 2 f = ∇ ⋅ ∇ f \Delta f=\nabla^{2} f=\nabla \cdot \nabla f Δf=2f=f

连续函数

在二维空间笛卡尔坐标系中,拉普拉斯算子即二阶偏导数求和:
Δ f = ∑ i = 1 n ∂ 2 f ∂ x i 2 \Delta f=\sum_{i=1}^{n} \frac{\partial^{2} f}{\partial x_{i}^{2}} Δf=i=1nxi22f
三维空间中为对各个分量求二阶偏导再求和:
Δ f = ∂ 2 f ∂ x 2 + ∂ 2 f ∂ y 2 + ∂ 2 f ∂ z 2 \Delta f=\frac{\partial^{2} f}{\partial x^{2}}+\frac{\partial^{2} f}{\partial y^{2}}+\frac{\partial^{2} f}{\partial z^{2}} Δf=x22f+y22f+z22f

离散函数

若在离散空间中,只需要求离散函数的二阶导数求和:
一维条件(一个变量)下:
一阶导数:
∂ f ∂ x = f ′ ( x ) = f ( x + 1 ) − f ( x ) \frac{\partial f}{\partial x}=f^{\prime}(x)=f(x+1)-f(x) xf=f(x)=f(x+1)f(x)
二阶导数:
∂ 2 f ∂ x 2 = f ′ ′ ( x ) = f ′ ( x + 1 ) − f ′ ( x ) = f ( x + 1 ) + f ( x − 1 ) − 2 f ( x ) \begin{array}{l} \frac{\partial^{2} f}{\partial x^{2}}=f^{\prime \prime}(x)=f^{\prime}(x+1)-f^{\prime}(x) \\ =f(x+1)+f(x-1)-2 f(x) \end{array} x22f=f(x)=f(x+1)f(x)=f(x+1)+f(x1)2f(x)

二维条件(二个变量,例如下图)下:
一阶导数:
∂ f ∂ x = f ( x + 1 , y ) − f ( x , y ) \frac{\partial f}{\partial x}=f(x+1,y)-f(x,y) xf=f(x+1,y)f(x,y)
∂ f ∂ y = f ( x , y + 1 ) − f ( x , y ) \frac{\partial f}{\partial y}=f(x,y+1)-f(x,y) yf=f(x,y+1)f(x,y)
二阶导数:
∂ 2 f ∂ x 2 = f ( x + 1 , y ) + f ( x − 1 , y ) − 2 f ( x , y ) \begin{array}{l} \frac{\partial^{2} f}{\partial x^{2}}=f(x+1,y)+f(x-1,y)-2 f(x,y) \end{array} x22f=f(x+1y)+f(x1,y)2f(x,y)
∂ 2 f ∂ y 2 = f ( x , y + 1 ) + f ( x , y − 1 ) − 2 f ( x , y ) \begin{array}{l} \frac{\partial^{2} f}{\partial y^{2}}=f(x,y+1)+f(x,y-1)-2 f(x,y) \end{array} y22f=f(xy+1)+f(x,y1)2f(x,y)

则拉普拉斯算子可以求得: △ f = ∂ 2 f ∂ x 2 + ∂ 2 f ∂ y 2 = f ( x + 1 , y ) + f ( x − 1 , y ) + f ( x , y − 1 ) + f ( x , y + 1 ) − 4 f ( x , y ) \begin{array}{c} \triangle f=\frac{\partial^{2} f}{\partial x^{2}}+\frac{\partial^{2} f}{\partial y^{2}} \\ =f(x+1, y)+f(x-1, y)+f(x, y-1)+f(x, y+1)-4 f(x, y) \end{array} f=x22f+y22f=f(x+1,y)+f(x1,y)+f(x,y1)+f(x,y+1)4f(x,y)

欧式空间内,可以拓展为该点和周围连接点的差值求和:
Δ f i = ∑ ( i , j ) ∈ ε ( f i − f j ) \Delta f_{i}=\sum_{(i, j) \in \varepsilon}\left(f_{i}-f_{j}\right) Δfi=(i,j)ε(fifj)
其中 f = { f 1 , f 2 , ⋯   , f n } f=\{f_1,f_2,\cdots,f_n\} f={ f1,f2,,fn},代表n个节点上的信号值。当结点 i i i的每个相连节 j j j点都有一个权重 W i , j W_{i,j} Wi,j的时候可以获得:
Δ f i = ∑ ( i , j ) ∈ ε W i , j ( f i − f j ) \Delta f_{i}=\sum_{(i, j) \in \varepsilon}W_{i,j}\left(f_{i}-f_{j}\right) Δfi=(i,j)εWi,j(fifj)
则对于每一个节点:
Δ f i = ∑ ( i , j ) ∈ ε W i , j ( f i − f j ) = ∑ j = 1 n W i , j ( f i − f j ) = D i i f i − ∑ j = 1 n W i , j f j \Delta f_{i}=\sum_{(i, j) \in \varepsilon}W_{i,j}\left(f_{i}-f_{j}\right)\\=\sum_{j=1}^nW_{i,j}\left(f_{i}-f_{j}\right)\\=D_{ii}f_i-\sum_{j=1}^nW_{i,j}f_j Δfi=(i,j)εWi,j(fifj)=j=1nWi,j(fifj)=Diifij=1nWi,jfj
D i i = ∑ j = 1 n W i , j D_{ii}=\sum_{j=1}^nW_{i,j} Dii=j=1nWi,j为度矩阵,对应每条边的权重。
那么对于所有的结点:
Δ f = g θ = ( △ f 1 ⋮ Δ f n ) = ( D 11 f 1 − ∑ j = 1 n W 1 j f j ⋮ D n n f n − ∑ j = 1 n W n j f j ) = ( D 11 ⋱ D n n ) f − W f = D f − W f = L f \begin{aligned} \Delta f=g_{\theta}=\left(\begin{array}{c} \triangle f_{1} \\ \vdots \\ \Delta f_{n} \end{array}\right)=\left(\begin{array}{c} D_{11} f_{1}-\sum_{j=1}^{n} W_{1 j} f_{j} \\ \vdots \\ D_{n n} f_{n}-\sum_{j=1}^{n} W_{n j} f_{j} \end{array}\right) \\ =\left(\begin{array}{ccc} D_{11} & \\ & \ddots \\ {}&{}&D_{n n} \end{array}\right) f-W f=D f-W f=L f \end{aligned} Δf=gθ=f1Δfn=D11f1j=1nW1jfjDnnfnj=1nWnjfj=D11DnnfWf=DfWf=Lf
其中 L = D − W L=D-W L=DW, f f f为结点信号值。

拉普拉斯矩阵

下入所示,L为拉普拉斯矩阵(边权设为1):

简单明了, L = 度 矩 阵 − 邻 接 矩 阵 L = 度矩阵-邻接矩阵 L=

拉普拉斯矩阵性质

  1. 拉普拉斯是对称半正定矩阵
    证明:
    对任意 f = [ f 1 , f 2 , . . . , f n ] T f=[f_1,f_2,...,f_n]^T f=[f1,f2,...,fn]T,有:
    f T L f = f T D f − f T W f = ∑ i = 1 n d i f i 2 − ∑ i , j = 1 n f i f j W i j = 1 2 ( ∑ i = 1 n d i f i 2 − 2 ∑ i , j = 1 n f i f j W i j + ∑ j = 1 n d j f j 2 ) = 1 2 ( ∑ i , j = 1 n W i j ( f i − f j ) 2 ) ≥ 0 \begin{array}{c} f^{T} L f=f^{T} D f-f^{T} W f=\sum_{i=1}^{n} d_{i} f_{i}^{2}-\sum_{i, j=1}^{n} f_{i} f_{j} W_{i j} \\ =\frac{1}{2}\left(\sum_{i=1}^{n} d_{i} f_{i}^{2}-2 \sum_{i, j=1}^{n} f_{i} f_{j} W_{i j}+\sum_{j=1}^{n} d_{j} f_{j}^{2}\right) \\ =\frac{1}{2}\left(\sum_{i, j=1}^{n} W_{i j}\left(f_{i}-f_{j}\right)^{2}\right) \geq 0 \end{array} fTLf=fTDffTWf=i=1ndifi2i,j=1nfifjWij=21(i=1ndifi22i,j=1nfifjWij+j=1ndjfj2)=21(i,j=1nWij(fifj)2)0
    即半正定。
    半正定矩阵的性质
    1.n阶对称矩阵一定有n个线性无关的特征向量。
    2.对称矩阵的不同特征值对应的特征向量正交,这些正交的特征向量构成的矩阵为正交矩阵。
    3.实对称矩阵的特征向量一定是实向量。
    4.半正定矩阵的特征值一定非负数。

2.特征值中0出现的次数就是图连通区域的个数;
3.最小特征值是0,因为拉普拉斯矩阵每一行的和均为0;
4.最小非零特征值是图的代数连通度。

拉普拉斯矩阵的谱分解

特征分解,又称为谱分解,即将矩阵分解为由特征值和特征向量表示的矩阵之积的方法。如下,拉普拉斯为半正定矩阵,则可以分解为:
L = U Λ U − 1 = U [ λ 1 ⋱ λ n ] U − 1 U = ( u ⃗ 1 , u ⃗ 2 , ⋯   , u ⃗ n ) u ⃗ i ∈ R n , i = 1 , 2 , ⋯ n \begin{array}{l} L=U \Lambda U^{-1}=U\left[\begin{array}{ccc} \lambda_{1} & \\ & \ddots & \\ & & \lambda_{n} \end{array}\right] U^{-1} \\ U=\left(\vec{u}_{1}, \vec{u}_{2}, \cdots, \vec{u}_{n}\right) \\ \vec{u}_{i} \in \mathbb{R}^{n}, i=1,2, \cdots n \end{array} L=UΛU1=Uλ1λnU1U=(u 1,u 2,,u n)u iRn,i=1,2,n
u ⃗ i \vec{u}_{i} u i为特征向量, λ i \lambda_{i} λi为对应的特征值。
1.由于n阶对称矩阵一定有n个线性无关的特征向量,n维线性空间中的n个线性无关的向量可以构成它的一组(基的元素称为基向量,可以线性组合构成向量空间的任意向量)。那可以得出拉普拉斯矩阵的n个特征向量是线性无关的,且他们是n维空间的中的一组基。

上图二维空间中,图中两个向量组成的一组基向量可以线性表示该空间的任意向量。

2.对称矩阵的不同特征值对应的特征向量相互正交,这些正交的特征向量构成的矩阵为正交矩阵。拉普拉斯矩阵的n个特征向量是n维空间中的一组标准正交基(基向量模长均为1)。
单位正交矩阵的性质: U U T = I UU^T=I UUT=I,
正定矩阵性质: L = U Λ U − 1 = U Λ U T L=U \Lambda U^{-1}=U \Lambda U^{T} L=UΛU1=UΛUT