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

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

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$

图傅里叶变换

传统傅里叶变换告诉了我们以下知识：
➢傅里叶反变换：把任意一个函数表示成了若干正交基函数的线性组合。
➢傅里叶正变换：求线性组合系数。具体做法是由原函数和基的共轭的内积求得。

对应图上的信号 $f ∈ \mathbb R^n$ ，如果要进行傅里叶变换，很自然的我们能想到：我们也要找到一组正交基，通过这组正交基的线性组合来表达 $f$ .

事实上，经典傅里叶变换的基函数是拉普拉斯算子的特征函数。（算子在指定一个点的计算结果是一个数值，所以对应有特征值；而算子用特定函数表示时，就对应有特征函数）

所以图傅里叶变换则是将拉普拉斯矩阵的特征向量作为图傅里叶变换的基函数。
于是有：

$f=\hat{f}(\lambda_1)\psi_1+\hat{f}(\lambda_2)\psi_2+\cdots+\hat{f}(\lambda_n)\psi_n$

这就是图中的傅里叶逆变换。
因为这 $n$ 个特征向量 $\psi_i$ 组成 $L=U\varLambda U^T$ 中的 $U$ 。所以上式也可以写为：

$f=U\hat{f},\quad \hat{f}=[\hat{f}(\lambda_2),\;\hat{f}(\lambda_2),...,\hat{f}(\lambda_n)]^T$

而 $\hat{f}$ 就是谱域/频域中的信号，它的自变量为 $n$ 个特征值。

不难得出，还有 $\hat{f}=U^Tf$ ，这是图中的傅里叶正变换。

图谱上的卷积

类比经典傅里叶变换的性质：时域上的卷积结果等于频域上的乘积再反变换回来。

我们得到图在空域上的卷积就等于图在谱域中的乘积再逆变换。所以有：

$f*g={\cal F^{-1}}(\hat{f}\odot\hat{g})=U(U^Tg\odot U^Tf)$

如果令 $g_{\theta}(\varLambda)=\text{diag}(\hat g)=\text{diag}(U^Tg)$ ，则 $U^Tg\odot U^Tf$ 就可以写成 $g_\theta(\varLambda) U^Tf$ ，所以：

$f*g=Ug_\theta(\varLambda) U^Tf$

在工程应用中，我们还可以利用切比雪夫最佳逼近多项式来进一步对卷积操作进行计算优化。关于这一点可以参考本站文章：图网络浅学：图神经网络及其发展 - GNN

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

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