图论：从拉普拉斯算子到拉普拉斯矩阵

本文内容涉及部分高等数学、线性代数、图数据结构的相关知识。如果有所遗忘或者想快速过一遍相关内容，可参阅本站文章：

SLie的【数学基础】集装箱

https://qslie.top/posts/9a95977b

计算机中的图-基本概念|数据结构Ⅳ

https://qslie.top/posts/64aa0f2d

$Ax=\lambda x$ 的几何意义

我们知道，一个 $n$ 维非零向量 $x\in \mathbb R^n$ 可以由一个线性无关组 $(\alpha_1,\alpha_2,\cdots,\alpha_n)$ 的线性组合进行表示，即：

$x=k_1\alpha_1+k_2\alpha_2+\cdots+k_n\alpha_n$

我们称这个线性无关组是一组基，称 $(k_1,k_2,\cdots,k_n)$ 为向量 $x$ 在这组基下的坐标。
特别地，当这组基是单位正交向量组时，称其为规范正交基。

我们以最熟悉的笛卡尔坐标系为背景，对上述概念的几何意义做出解释。
假设存在一组二维的规范正交基 $(i,j)$ ，那么它们的任意线性组合就可以表示整个二维空间的所有向量。

笛卡尔坐标系

如上图所示，图中的向量 $v$ 可以由确定的坐标 $(a,b)$ 表示，也就是 $v=ai+bj$ .

除此之外，我们也学习过，向量左乘一个矩阵，可以看做是对其做线性变换，几何上相当于将一个向量进行旋转，平移等操作。

于是针对某个矩阵 $A$ ，存在一系列在 $(i,j)$ 这组基下的向量 $x$ 和对应的实数 $\lambda$ 使得：

$Ax=\lambda x$

也就是说，这些向量经过矩阵 $A$ 的变换之后，并不会旋转或者改变方向，只会在原有方向上进行比例为 $\lambda$ 的缩放。
我们称这样的向量 $x$ 为特征向量， $\lambda$ 为特征值。（同一个 $A$ 可以有多个特征值和特征向量）从特征向量和特征值的定义式还可以看出，特征向量所在直线上的向量都是特征向量。

当然，我们可以计算得到某个矩阵的所有特征值，并给出一系列特征向量。（也有可能出行特征值是复数 complex number，不存在特征向量的情况，这种情况暂且不考虑）

并且，如果矩阵可以对角化，我们还可以进一步对其进行特征值分解：

$A = P\varLambda P^{-1}= P\left[ \begin{matrix} \lambda_1 & & & \\ & \lambda_2 & & \\ & & \ddots & \\ & & & \lambda_n\\ \end{matrix} \right]P^{-1}$

其中， $P$ 由 $A$ 的 $n$ 个线性无关的特征向量(正交)组成。

在几何意义上，我们知道 $A$ 包含了旋转与拉伸的作用。
而特征分解则分解出了用于旋转的 $P$ 和用于拉伸的 $\varLambda$ 。

当我们把一幅图像视为一个矩阵，对其进行奇异值分解之后，对中间的对角阵进行处理：仅保留其最大的十几个特征值，其余元素置零。还原回去之后我们发现图像得到了压缩。

更多特征值分解已经奇异值分解的相关内容参阅本站文章：

特征值与奇异值分解|EVD & SVD

https://qslie.top/posts/4a23c96

拉普拉斯矩阵

拉普拉斯算子

拉普拉斯算子 $\Delta f$ 是 $n$ 维欧几里得空间中的一个二阶微分算子，定义为函数 $f$ 的梯度 $\nabla f$ 的散度 $\nabla\cdot\nabla f$ 。

梯度场的散度

如上图所示，梯度表示某个点指向函数增加的方向（橙色箭头），而这些梯度构成了一个向量场（图中圆圈），梯度场的散度是对应点的法向量与梯度的点积之和。其中两个向量的夹角大于0时，其点积结果也大于0，反之则以。故梯度场的散度说明了极大值点和极小值点的汇聚和发散程度，系标量。

即，拉普拉斯算子衡量的是梯度场的发散程度。

二元函数 $\Delta f$

我们可以容易写出二元函数 $f(x,y)$ 的拉普拉斯算子，其中二阶导数用差分近似。
比如对于二维图像来说，在 $(x,y)$ 处的像素值为 $f(x,y)$ ，则拉普拉斯算子如下：

$\begin{aligned} \nabla^2f&=\frac{\partial^2 f}{\partial x^2}+\frac{\partial^2 f}{\partial y^2}\\ \text{where }\frac{\partial^2 f}{\partial x^2}&\approx f(x+1,y)+f(x-1,y)-2f(x,y)\\ \frac{\partial^2 f}{\partial y^2}&\approx f(x,y+1)+f(x,y-1)-2f(x,y)\\ \\ \nabla^2f&=f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)-4f(x,y) \end{aligned}$

图像的拉普拉斯算子

如上图所示，其拉普拉斯算子也可以描述为与 $(x,y)$ 相邻点的像素值之和减去同次数的自身像素值。更形象的理解是，从该点出发沿着可能变化的四条路径，分别移动一步所获得的增益，这个增益实际上就是一种发散程度，或者说是净流入。

拉普拉斯矩阵推导

图结构的表示方式有两种：邻接表和邻接矩阵。本文重点关注图的邻接矩阵以便于谱图理论分析。

对于图 $G=(V,E)$ ，或有权图 $G=(V,E,W)$ ，每个节点的值由函数 $f$ 确定。
我们可以参照二元函数的离散版本拉普拉斯算子，对每个节点 $v_i\in V$ 计算得到拉普拉斯算子：

$\Delta f(v_i)=\sum_{v_j\in N(v_i)}f(v_j)-d_i\cdot f(v_i)$

式中， $N(v_i)$ 表示节点 $v_i$ 的邻接点集， $d_i$ 表示节点 $v_i$ 的度数，它等价于与该点相邻的节点个数。

考虑边权时（如果没有边，则权重记为0）还可以改写为：

$\Delta f(v_i)=\sum_{j=1}^n w_{ij}f(v_j)-d_i\cdot f(v_i)$

记 ${\bf w}_i = [w_{i1},w_{i2},\cdots,w_{in}]$ ， ${\bf f}=[f(v_1),f(v_2),\cdots,f(v_n)]$ ，则上式第一项可以写为 $\mathbf w_i\cdot \mathbf f$ .

更进一步地化简：

$\begin{aligned} \Delta\mathbf f&=\begin{bmatrix}\Delta f(v_1)\\\Delta f(v_2)\\\vdots\\\Delta f(v_n)\end{bmatrix}=\begin{bmatrix}\mathbf w_1\cdot \mathbf f-d_1f(v_1)\\\mathbf w_2\cdot \mathbf f-d_2f(v_2)\\\vdots\\\mathbf w_n\cdot \mathbf f-d_nf(v_n)\end{bmatrix}\\\\&= \mathbf W\cdot \mathbf f-\begin{bmatrix}d_1&&&\\&d_2&&\\&&\ddots&\\&&&d_n\end{bmatrix}\mathbf f\\ &=\bf Wf-Df=(W-D)f \end{aligned}$

其中， $\bf W,\; D$ 分别是图 $G$ 的权重矩阵（不加权时，为邻接矩阵）和加权度矩阵（不加权时，为度数矩阵）。

经过以上推断，我们令 $L=D-W$ 为图 $G$ 的拉普拉斯矩阵。（注意相比上述推导多有一个负号）

$L$ 的归一化

我们一般会对所得到的拉普拉斯矩阵进行归一化。

对称归一化： $L_{sym}=I-D^{-1/2}WD^{-1/2}$ $L_{sy m} = I - D^{- 1/2} W D^{- 1/2}$ .
- 其中 $D^{-1/2}$ 是对元素而言，即 $[D^{-1/2}]_{ii}=1/\sqrt{d_{ii}}$
随机游走归一化： $L_{rw}=I-D^{-1}W$