Blog Post

图的拉普拉斯矩阵推导

  • note
  • Math
  • LinearAlgebra
  • GCN
  • GNN
  • Graph

图的拉普拉斯矩阵推导

作者：Eric

创建时间：2025-11-08 10:57

这篇记什么

  • Nabla算子和Laplace算子简介
  • 由n维欧氏空间中的Laplace算子推导至图中的Laplace矩阵
  • Laplace矩阵的标准化

主要内容

Nabla算子和Laplace算子（三维欧氏空间）

  1. Nabla算子

    Nalba算子的含义为向量场中的梯度，为向量，又称为一阶微分算子。 具体形式如下

    ∇=ddxi⃗+ddyj⃗+ddzk⃗\nabla=\frac{d}{dx}\vec{i}+\frac{d}{dy}\vec{j}+\frac{d}{dz}\vec{k}

  2. Laplace算子

    Laplace算子为向量场中梯度的散度，表示空间中各点向量场发散的强弱程度，为标量，又称为二阶微分算子。 具体形式如下

    Δ=∇2\Delta = \nabla^2

    可推广至n维

离散形式的Laplace算子

在一元离散函数中

f′(x)=dfdx=f(x+1)−f(x)f'(x)=\frac{df}{dx}=f(x+1)-f(x) Δf=f′′(x)=∂2f∂x2=f(x+1)+f(x−1)−2f(x)\Delta f=f''(x)=\frac{\partial^2f}{\partial x^2}=f(x+1)+f(x-1)-2f(x)

对于多元离散函数（以二元为例），其Laplace算子为

Δf=∂2f∂x2+∂2f∂y2=f(x+1,y)+f(x−1,y)+f(x,y+1)+f(x,y−1)−4f(x,y)\Delta 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)-4f(x,y)

可视作从 f(x,y)f(x,y) 朝四个方向（离散函数只有四个方向）的变化差之和，即

−Δf(x,y)=(f(x,y)−f(x−1,y))+(f(x,y)−f(x+1,y))…-\Delta f(x,y) = (f(x,y)-f(x-1,y))+(f(x,y)-f(x+1,y)) \dots

也就是

离散负 Laplace=自身与左右邻居的差异之和\boxed{\text{离散负 Laplace} = \text{自身与左右邻居的差异之和}}

图的Laplace矩阵

设有一个无向图 G=(V,E)G=(V,E) ，顶点数为 nn。邻接矩阵为 AA，度矩阵为 DD。由无向图性质，AT=AA^T=A 。另外， DD 为对角矩阵。

设对于 GG 中的所有点，都存在一个函数值 ff，其中

f=(f1f2...fn)f=\begin{pmatrix} f_1 \\ f_2 \\ ... \\ f_n \\ \end{pmatrix}

由离散形式的负 Laplace算子外推，定义矩阵算子 (Lf)i(Lf)_i ，使其对于图 GG 中任一点 ViV_i

(Lf)i=∑i∼j(fi−fj)(Lf)_i = \sum_{i\sim j}(f_i-f_j)

其中，i∼ji\sim j 表示与 ViV_i 相邻接的点 VjV_j （ i≠ji\neq j ），用来衡量 GG 中不同点间差异程度。

由于节点 ii 有 DiiD_{ii} 个邻居，故 ∑i∼jfi=Diifi\sum_{i\sim j}f_i = D_{ii}f_i ，又因为 AA 有性质 (Af)i=∑i∼jfj(Af)_i = \sum_{i\sim j}f_j ，故

(Lf)i=∑i∼jfi−∑i∼jfj=(Df)i−(Af)i(Lf)_i = \sum_{i\sim j}f_i - \sum_{i\sim j}f_j = (Df)_i - (Af)_i

写成矩阵形式

L=D−AL=D-A

图的Laplace矩阵标准化

  1. 随机游走标准化

    为了消除 GG 中 ViV_i 节点的度对 (Lf)i(Lf)_i 的影响，自然想法是两边同左乘一个 D−1D^{-1} ，记 Lr=D−1LL_r = D^{-1}L ，于是图的矩阵形式的Laplace算子可改写为

    Lr=I−D−1AL_r = I - D^{-1}A

    因此，

    (Lrf)i=fi−1Dii∑i∼jfj(L_rf)_i = f_i - \frac{1}{D_{ii}}\sum_{i\sim j}f_j

    即 自身值 - 邻居的平均值\text{自身值 - 邻居的平均值}

  2. 对称标准化

    由

    L=D−AL=D-A

    记对称标准化 Ls=D−12LD−12L_s = D^{-\frac{1}{2}}LD^{-\frac{1}{2}} ，

对称标准化与图Laplace算子的一条重要性质的二次型形式维持有关 性质 fTLf=12∑i,jAij(fi−fj)2f_TLf = \frac{1}{2}\sum_{i,j}A_{ij}(f_i-f_j)^2，推导过程如下

fTLf=fT(D−A)f=fTDf−fTAff^TLf = f^T(D-A)f = f^TDf - f^TAf

由于 DD 为对角矩阵， fTDf=∑iDiif2f^TDf=\sum_iD_{ii}f^2 ；展开第二项，得 fTAf=∑i,jAijfifjf^TAf = \sum_{i,j}A_{ij}f_if_j

fTLf=∑iDiif2+∑i,jAijfifjf^TLf=\sum_iD_{ii}f^2+\sum_{i,j}A_{ij}f_if_j

由于

Dii=∑jAijD_{ii} = \sum_jA_{ij}

第一项可化为 ∑iDiif2=∑i(∑jAij)fi2=∑i,jAijfi2\sum_iD_{ii}f^2 = \sum_i(\sum_jA_{ij})f_i^2 = \sum_{i,j}A_{ij}f_i^2，即

fTLf=∑i,jAijfi2+∑i,jAijfifjf^TLf=\sum_{i,j}A_{ij}f_i^2+\sum_{i,j}A_{ij}f_if_j

由于在无向图 GG 中，Aij=AjiA_{ij}=A_{ji} ，且 ∑i,j=∑j,i\sum_{i,j} = \sum_{j,i} 交换求和下标名称

∑j,iAjifj2=∑i,jAijfi2\sum_{j,i}A_{ji}f_j^2 = \sum_{i,j}A_{ij}f_i^2

因此，可拆分 fTLff^TLf 中的第一项 ∑i,jAijfi2\sum_{i,j}A_{ij}f_i^2

fTLf=12∑i,jAijfi2+12∑j,iAjifj2+∑i,jAijfifjf^TLf=\frac{1}{2}\sum_{i,j}A_{ij}f_i^2+\frac{1}{2}\sum_{j,i}A_{ji}f_j^2+\sum_{i,j}A_{ij}f_if_j

故

fTLf=12∑i,jAij(fi2+fj2+2fifj)=12∑i,jAij(fi−fj)2f^TLf=\frac{1}{2}\sum_{i,j}A_{ij}(f_i^2+f_j^2+2f_if_j)=\frac{1}{2}\sum_{i,j}A_{ij}(f_i-f_j)^2

该式实际上是图的Dirichlet能量，用于刻画的是图上信号的平滑程度。若图上两点 ii, jj 所对应的函数值 fif_i 和 fjf_j越接近，对应的 fTLff^TLf 值越小，反之同理 > 构造 Ls=D−12LD−12L_s = D^{-\frac{1}{2}}LD^{-\frac{1}{2}} 进行标准化，能保持此性质不变，保留图边的信号差异

将 LsL_s 代回 L=D−AL=D-A ,

Ls=I−D−12AD−12L_s = I - D^{-\frac{1}{2}}AD^{-\frac{1}{2}}

因此

(Lsf)i=fi−1didj∑i∼jfj(L_sf)_i = f_i - \frac{1}{\sqrt{d_id_j}}\sum_{i\sim j}f_j

相关

  • 无