拉普拉斯矩阵【Laplacian Matrix】
拉普拉斯矩阵【Laplacian Matrix】
拉普拉斯矩阵是图论中的一个重要概念，它将图的结构信息编码为矩阵形式，广泛应用于图信号处理、机器学习等领域。本文将从梯度和拉普拉斯算子的基本概念出发，逐步推导出图的拉普拉斯矩阵，并解释其背后的含义。
1. 梯度
对于一个二维输入的函数，函数可视化如下图所示，其中箭头即是此二维输入函数在每个点处的梯度在二维平面中的投射。
用数学函数表示：$f(x, y)$在$(x, y)$处的一阶连续偏导数向量$\nabla f = \frac{\partial f}{\partial x} \vec{i} + \frac{\partial f}{\partial y} \vec{j}$表示的就是该函数在该点处的梯度，记作$\nabla f(x, y)$。
梯度的物理意义：欧式空间函数在某一点处的梯度就是该函数在该点变化率最大的方向。
2. 拉普拉斯算子
拉普拉斯算子是在N维欧式空间中的一个二阶微分算子，定义为梯度的散度Div(Grad(f))，即二阶导数。
拉普拉斯算子计算了周围点与中心点的梯度差，得到的是对该点进行微小扰动后可能获得的总变化。
通俗来说，它告诉我们梯度的变化程度。
拉普拉斯算子表示为：$\Delta f = \nabla^2 f = \nabla f \cdot \nabla f = \frac{\partial^2 f}{\partial x^2} + \frac{\partial^2 f}{\partial y^2}$
扩展到n维形式如下：$\Delta f = \sum_i \frac{\partial^2 f}{\partial x_i^2}$
- $\Delta f > 0$，表示该点是有散发通量的正源（发散源）。如图中的蓝圈，即散度大于0，该点是一个极值点，并且是极小值。
- $\Delta f < 0$，表示该点是有吸收通量的负源（汇聚源）。如图中的红圈，即散度小于0，该点是一个极值点，并且是极大值。
- $\Delta f = 0$，表示该点无源。
3. 梯度与拉普拉斯算子
- 梯度反映了函数的极值情况。
- 拉普拉斯算子（梯度的散度）则反映了函数的极值是极大值还是极小值。
4. 图的拉普拉斯矩阵
4.1 拉普拉斯矩阵的定义
给定一个无向图$G = (V, E)$，其中$V$是顶点集合，$E$是边集合。
其普通形式的拉普拉斯矩阵：$L = D - A$为对称矩阵
- 邻接矩阵$A$：$A(i, j) = \begin{cases} 1,& (i,j)\in E \ 0,& (i,j)\notin E \end{cases}$，注意其中$A(i, i) = 0$。
- 度矩阵$D$是一个对角矩阵，对角线上每个元素：$D(i, i) = \sum_{j=1}^N A(i, j)$
- 拉普拉斯矩阵$L$：$L = D - A = \begin{cases} \sum_{k≠j}^N A(i, k) & \text{ if } i=j\ -A(i, j) & \text{ else} \end{cases}$
此外，还有其他几种拉普拉斯矩阵的变种形式：
- 对称归一化拉普拉斯矩阵$L^{sys}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}=I_N-D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$
- $L^{sys}{ij}=\begin{cases} 1 &\text{ if } i=j\ -\frac{A{ij}}{\sqrt{D_{ii}}\sqrt{D_{jj}}} &\text{ else} \end{cases}$
- 随机游走归一化拉普拉斯矩阵$L^{rw}=D^{-1}L=I_N-D^{-1}A$
- $L^{rw}{ij}=\begin{cases} 1 &\text{ if } i=j\ -\frac{A{ij}}{D_{ii}} &\text{ else} \end{cases}$
4.2 图的拉普拉斯矩阵公式推导及含义
拉普拉斯算子推导
对于拉普拉斯算子：$\Delta f = \sum_i \frac{\partial^2 f}{\partial x_i^2}$
一阶导数：$\frac{\partial f}{\partial x} = \frac{f(x+ \Delta x) - f(x)}{\Delta x}$
假设增量$\Delta x = 1$，则：
$\frac{\partial f}{\partial x} = f'(x) = f(x+1)-f(x)$
$\frac{\partial^2 f}{\partial x^2} = f''(x) = f'(x)-f'(x-1) = f(x+1)+f(x-1)-2f(x)$
以二维坐标为例，将拉普拉斯算子转化为离散形式：
$\Delta f = \frac{\partial^2 f}{\partial x^2} + \frac{\partial^2 f}{\partial y^2}$
$=f(x+1,y) + f(x-1,y) - 2f(x,y) + f(x, y+1) + f(x,y-1) - 2f(x,y)$
$= f(x+1,y) + f(x-1,y) +f(x,y+1) + f(x,y-1) - 4f(x,y)$
实际上，拉普拉斯算子计算了周围点与中心点的梯度差。
当$f(x, y)$受到扰动之后，其可能变为相邻的$f(x-1, y)$，$f(x+1, y)$，$f(x, y-1)$，$f(x, y+1)$之一，拉普拉斯算子得到的是对该点进行微小扰动后可能获得的总收益（或总变化）。
【形象说明】假设五个原点都是人，黑色线代表绳子。所有人同时拉绳子，每个人的力气大小分别为$f(x, y)$，$f(x-1, y)$，$f(x+1, y)$，$f(x, y-1)$，$f(x, y+1)$。$\Delta f$的值就代表中间的人（粉红色）的状态（被拉跑、拉过来其他人、原地不动）。
- $\Delta f > 0$时他会被拉跑
- $\Delta f < 0$时他会把所有人拉过来
- $\Delta f = 0$时五个人处于僵持状态，都原地不动
从拉普拉斯算子到拉普拉斯矩阵
假设具有$N$个节点的图$G$，其节点$i$的一阶邻域为$N_i$，图上定义一个函数$f = (f_1, f_2, \dots, f_N)$，$f_i$表示函数$f$在节点$i$处的函数值。则对其中一个节点$i$进行微扰，它可能变为图中任意一个与它相邻的节点$j \in N_i$。
我们已经知道通过拉普拉斯算子可以计算一个点在它所有自由度上微小扰动的增益，通过图来表示就是任意一个节点$i$变化到节点$j$所带来的增益。
设节点$i$和节点$j$之间的连边$e_{ij}$的权值为$w_{ij}$，则考虑图中边的权值，有：$\Delta f_i = \sum_{j \in N_i} w_{ij}(f_i-f_j)$
假设节点$i$和节点$j$不相邻时$w_{ij}=0$，将上面式子进行简化：
$\Delta f_i = \sum_{j \in N} w_{ij}(f_i-f_j)$
$=\sum_{j \in N} w_{ij}f_i - \sum_{j \in N} w_{ij}f_j$
$=d_if_i-w_{i:}f$
其中，$d_i = \sum_{j \in N_i} w_{ij}$表示顶点的度，$w_{i:}=(w_{i1},\dots,w_{iN})$表示$N$维的行向量，$f=\begin{pmatrix} f_1\ \vdots\ f_N \end{pmatrix}$表示$N$维的列向量。
对于所有的$N$个节点来说：
$\Delta f = \begin{pmatrix} \Delta f_1\ \vdots\ \Delta f_N \end{pmatrix} = \begin{pmatrix} d_1f_1-w_{1:}f \ \vdots\ d_Nf_N-w_{N:}f \end{pmatrix}$
$= \begin{pmatrix} d_1 & \cdots & 0\ \vdots & \ddots & \vdots\ 0 & \cdots & d_N \end{pmatrix} f - \begin{pmatrix} w_{1:}\ \vdots\ w_{N:} \end{pmatrix} f$
$=diag(d_i)f-Wf$
$= (\textbf{D}-\textbf{W}) f$
$= \textbf{L}f$
这里的$(\textbf{D}-\textbf{W})$实际上就是拉普拉斯矩阵$\textbf{L}$。
拉普拉斯矩阵中的第$i$行实际上反应了第$i$个节点在对其他所有节点产生扰动时所产生的增益累积。
参考文献
- 图论|拉普拉斯矩阵
- 从Laplacian矩阵到GCN——相关理论及证明
- Del算符与梯度、散度、旋度与Laplacian
- 图谱论学习—拉普拉斯矩阵背后的含义