拉普拉斯矩阵与拉普拉斯算子的关系

先说结论:

图拉普拉斯矩阵,如果把它看作线性变换的话,它起的作用与数学分析中的拉普拉斯算子是一样的。也就是说拉普拉斯矩阵就是图上的拉普拉斯算子,或者说是离散的拉普拉斯算子。

如果 \(f\) 是欧式空间中的二阶可微实函数,那么

\(\Delta f\) 就是在欧式空间中求其二阶微分(散度)。( \(\Delta\) 是拉斯矩阵算子)

如果 \(f\) 是图上定义的一组高维向量,那么

\(Lf\) 就是在图空间中求其二阶微分(散度)。( \(L\) 是图的拉普拉斯矩阵)

解释如下:

直接套用导数的定义,无法直观理解拉普拉斯矩阵的物理含义。从散度入手,才是正确的打开方式。

梯度(矢量) :梯度 “ \(\nabla\) ” 的本意是一个向量(矢量),表示某一函数在该点处的方向导数沿着该方向取得最大值,即函数在该方向处沿着该方向(此梯度方向)变化最快,变化率最大(为该梯度的模)。假设一个三元函数 \(u=f(x,y,z)\) 在空间区域 \(G\) 内具有一阶连续偏导数,点 \(P(x,y,z) \in G\) , 称向量

\(\left\{ {\frac{{\partial f}}{{\partial x}},\frac{{\partial f}}{{\partial y}},\frac{{\partial f}}{{\partial z}}} \right\} = \frac{{\partial f}}{{\partial x}}\vec i + \frac{{\partial f}}{{\partial y}}\vec j + \frac{{\partial f}}{{\partial z}}\vec k\)

为函数 \(u=f(x,y,z)\) 在点 \(P\) 处的梯度,记为 \(gradf(x,y,z)\) 或 \(\nabla f(x,y,z)\)

其中: \(\nabla = \frac{\partial }{{\partial x}}\vec i + \frac{\partial }{{\partial y}}\vec j + \frac{\partial }{{\partial z}}\vec k\)

称为(三维)向量的微分算子或 Nabla 算子。

散度(标量) 散度 ” \(\nabla \cdot\) ” (divergence)可用于表针空间中各点矢量场发散的强弱程度,物理上,散度的意义是场的有源性。当 \(div(F)>0\) ,表示该点有散发通量的正源(发散源);当 \(div(F)<0\) 表示该点有吸收能量的负源(洞或汇);当 \(div(F)=0\) ,表示该点无源。

拉普拉斯算子: 拉普拉斯算子(Laplace Operator)是 \(n\) 维欧几里得空间中的一个二阶微分算子,定义为梯度( \(\nabla f\) )的散度( \(\nabla \cdot\) )。 \(\Delta f = {\nabla ^2}f = \nabla \cdot \nabla f = div(gradf)\)

笛卡尔坐标系下的表示法:

\(\Delta f = \frac{{{\partial ^2}f}}{{\partial {x^2}}} + \frac{{{\partial ^2}f}}{{\partial {y^2}}} + \frac{{{\partial ^2}f}}{{\partial {z^2}}}\)

\(n\) 维形式 \(\Delta = \sum\limits_i {\frac{{{\partial ^2}}}{{\partial x_i^2}}} \)

下面推导离散函数的导数:

\(\frac{{\partial f}}{{\partial x}} = f'(x)=f(x + 1) – f(x)\)

\(\begin{align*}&\frac{{{\partial ^2}f}}{{\partial {x^2}}} = f”(x)\approx f'(x) – f'(x – 1)= f(x + 1) + f(x – 1) – 2f(x) \end{align*}\)

则我们可以将拉普拉斯算子也转化为离散形式(以二维为例)

\(\begin{array}{l} \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){\kern 1pt} + 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) \end{array}\)

现在用散度的概念解读一下:

  • 如果 \(\Delta f =0\) ,可以近似认为中心点 \(f(x,y)\) 的势和其周围点的势是相等的, \(f(x,y)\) 局部范围内不存在势差。所以该点无源
  • \(\Delta f >0\) ,可以近似认为中心点 \(f(x,y)\) 的势低于周围点,可以想象成中心点如恒星一样发出能量,补给周围的点,所以该点是正源
  • \(\Delta f <0\) ,可以近似认为中心点 \(f(x,y)\) 的势高于周围点,可以想象成中心点如吸引子一样在吸收能量,所以该点是负源

另一个角度,拉普拉斯算子计算了周围点与中心点的梯度差。当 \(f(x,y)\)受到扰动之后,其可能变为相邻的\(f(x-1,y),f(x+1,y),f(x,y-1),f(x,y+1)\)之一,拉普拉斯算子得到的是对该点进行微小扰动后可能获得的总增益 (或者说是总变化)。

我们现在将这个结论推广到图: 假设具有 \(N\) 个节点的图 \(G\) ,此时以上定义的函数 \(f\) 不再是二维,而是 \(N\) 维向量: \(f=(f_1,f_2,…,f_N)\) ,其中 \(f_i\) 为函数 \(f\) 在图中节点 \(i\) 处的函数值。类比于 \(f(x,y)\) 在节点 \((x,y)\) 处的值。对 \(i\) 节点进行扰动,它可能变为任意一个与它相邻的节点 \(j \in N_i\) , \(N_i\) 表示节点 \(i\) 的一阶邻域节点。

我们上面已经知道拉普拉斯算子可以计算一个点到它所有自由度上微小扰动的增益,则通过图来表示就是任意一个节点 \(j\) 变化到节点 \(i\) 所带来的增益,考虑图中边的权值相等(简单说就是1)则有:

\(\Delta {f_i} = \sum\limits_{j \in {N_i}} {({f_i} – } {f_j})\)

而如果边 \(E_{ij}\) 具有权重 \(W_{ij}\) 时,则有:

\(\Delta {f_i} = \sum\limits_{j \in {N_i}} {{W_{ij}}({f_i} – } {f_j})\)

由于当 \(W_{ij} = 0\) 时表示节点 \(i,j\) 不相邻,所以上式可以简化为: \(\Delta {f_i} = \sum\limits_{j \in {N}} {{W_{ij}}({f_i} – } {f_j})\) 继续推导有:

\( \begin{array}{l} \Delta {f_i} = \sum\limits_{j \in N} {{w_{ij}}({f_i} – {f_j})} \ \\= \sum\limits_{j \in N} {{w_{ij}}{f_i} – \sum\limits_{j \in N} {{w_{ij}}{f_j}} } \ \\= {d_i}{f_i} – {w_{i:}}f \end{array} \)

其中 \(d_i=\sum\limits_{j \in N} {{w_{ij}}}\) 是顶点 \(i\) 的度;

\(w_{i:}= \left( {\matrix{ {w_{i1}} , \dots , {w_{iN}} } } \right)\) 是 \(N\)维的行向量, \(f= \left( {\matrix{ f_1 \cr \vdots \cr f_N } } \right)\) 是 \(N\)维的列向量;

\({w_{i:}}f\) 表示两个向量的内积。

对于所有的 \(N\) 个节点有:

\(\eqalign{ & \Delta {f} =\left( {\matrix{ {\Delta {f_1}} \cr \vdots \cr {\Delta {f_N}} \cr } } \right) = \left( {\matrix{ {{d_1}{f_1} – {w_{1:}}f} \cr \vdots \cr {{d_N}{f_N} – {w_{N:}}f} \cr } } \right) \cr & =\left( {\matrix{ {{d_1}} & \cdots & 0 \cr \vdots & \ddots & \vdots \cr 0 & \cdots & {{d_N}} \cr } } \right) f – \left( {\matrix{ {{w_{1:}}} \cr \vdots \cr {{w_{N:}}} \cr } } \right)f \cr & = diag({d_i})f – Wf \cr & = (D -W)f \cr & = Lf \cr} \)

这里的\((D-W)\)就是拉普拉斯矩阵 \(L\) 根据前面所述,拉普拉斯矩阵中的第 \(i\) 行实际上反应了第 \(i\) 个节点在对其他所有节点产生扰动时所产生的增益累积。直观上来讲,图拉普拉斯反映了当我们在节点 \(i\) 上施加一个势,这个势以哪个方向能够多顺畅的流向其他节点。谱聚类中的拉普拉斯矩阵可以理解为是对图的一种矩阵表示形式。

以上的解释部分参考了图:谱聚类方法推导和对拉普拉斯矩阵的理解 ,在其基础上进行了调整和修改。

Follow me!

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注