图拉普拉斯矩阵的定义 推导 性质 应用

导语：在学习图神经网络时，不可避免地要遇到拉普拉斯算子，拉普拉斯矩阵，图傅里叶变换，拉普拉斯特征分解向量等等一堆概念，了解其中的来源，定义，推导，对于后续图卷积神经网络的演进过程会有更深刻的理解

文章目录

基本概念偏导数拉普拉斯算子图拉普拉斯矩阵-来源推导-方法1：娓娓道来推导-方法2：直接干脆图拉普拉斯矩阵-性质两种表示形式二次型加权聚合总结

公众号：一直学习一直爽，整理的GNN入门之路系列文章包含：GNN入门之路：01.图拉普拉斯矩阵的定义、推导、性质、应用GNN入门之路：02.谱域方法：Spectral CNN，ChebyNet，GCNGNN入门之路：03.空间域方法：GraphSAGE，GAT，MPNNGNN入门之路：04.图神经网络的表达能力，图表示学习

注：本文由于公式较多,iOS深色主题显示不友好，建议调成浅色主题阅读

本系列面向的对象是希望从更底层理解图神经网络的读者，我们一起来啃一啃图神经网络的演进过程，达到入门水平。

如果读者直接从空间方法开始学习图神经网络，那么基于消息传递的框架，会发现图神经网络就是在做各种聚合，学习曲线比较平滑，从GraphSAGE,GAT学起基本上没啥问题；反之，对于从谱方法开始学起的读者， 就会发现遇到很多图信号处理，图傅里叶变换，图滤波等概念，但这条脉络奠定了图神经网络的理论基础，空间方法与谱方法不是对立的关系，谱方法在不断朝着实用话的演进过程了，空间方法和谱方法得到了统一，最终才有了我们今天简洁的空间方法百花齐放的局面。

本文主要是关于图拉普斯矩阵相关的知识，涉及了其定义，推导过程，物理含义，作用在图上的性质。

基本概念

偏导数

对于我们熟悉的一元一次函数，导数描述的是因变量随自变量的变化率，如y=3x+1y = 3x + 1y=3x+1, 一阶导数为3；

在多元函数中，自变量的个数不止一个，如z=f(x,y)z = f(x, y)z=f(x,y)函数中包含2个自变量，函数关于自变量的变化率比一元函数复杂得多，为了描述多元函数的变化率，引入了偏导数的概念，当求函数关于其中一个自变量的导数(变化率)时，其余的自变量被视作为常数， 假设函数fff在某个区域内存在偏导数，对于其中的任意一点(x0,y0)(x_0,y_0)(x0​,y0​), 其偏导数一般记作：

fx(x0,y0)=∂f∂x∣(x=x0,y=y0)fy(x0,y0)=∂f∂y∣(x=x0,y=y0)\begin{aligned} f_x(x_0,y_0) &= \frac{\partial f}{\partial x} \Big |_{(x=x_0,y=y_0)} \\ f_y(x_0,y_0) &= \frac{\partial f}{\partial y} \Big |_{(x=x_0,y=y_0)} \end{aligned} fx​(x0​,y0​)fy​(x0​,y0​)​=∂x∂f​∣∣∣​(x=x0​,y=y0​)​=∂y∂f​∣∣∣​(x=x0​,y=y0​)​​

偏导数是个标量,以一个例子来让大家简单回顾一下：

求函数f=x2+3xy+y2f = x^2 + 3xy + y^2f=x2+3xy+y2 在点(1, 2)的偏导数

将yyy看做常数： ∂f∂x=2x+3y\frac{\partial f}{\partial x} = 2x + 3y∂x∂f​=2x+3y；将xxx看做常数： ∂f∂y=3x+2y\frac{\partial f}{\partial y} = 3x + 2y∂y∂f​=3x+2y；将（1，2）分别带入， ∂f∂x∣(x=1,y=2)=8\frac{\partial f}{\partial x} \Big|_{(x=1,y=2)} =8∂x∂f​∣∣∣​(x=1,y=2)​=8, ∂f∂y∣(x=1,y=2)=7\frac{\partial f}{\partial y} \Big|_{(x=1,y=2)} = 7∂y∂f​∣∣∣​(x=1,y=2)​=7

拉普拉斯算子

拉普拉斯算子是nnn维欧式空间中对函数的二阶微分算子, 也是一个标量，下面给出了连续函数和离散函数的拉普拉斯算子的定义：

对于3维函数f(x,y,z)f(x,y,z)f(x,y,z)，其拉普拉斯算子表示为：

Δf=∂2f∂x2+∂2f∂y2+∂2f∂z2\begin{aligned} \Delta f = \frac{\partial^2 f}{\partial x^2} + \frac{\partial^2 f}{\partial y^2} + \frac{\partial^2 f}{\partial z^2} \end{aligned} Δf=∂x2∂2f​+∂y2∂2f​+∂z2∂2f​​

对于nnn维函数f(x1,x2,...xn)f(x_1,x_2,...x_n)f(x1​,x2​,...xn​)，其拉普拉斯算子表示为:

Δf=∂2f∂x12+∂2f∂x22+∂2f∂x32+...+∂2f∂xn2=∑i=1n∂2f∂xi2\begin{aligned} \Delta f &= \frac{\partial^2 f}{\partial x_1^2} + \frac{\partial^2 f}{\partial x_2^2} + \frac{\partial^2 f}{\partial x_3^2} + ...+ \frac{\partial^2 f}{\partial x_n^2} \\ &= \sum_{i=1}^n \frac{\partial^2 f}{\partial x_i^2} \end{aligned} Δf​=∂x12​∂2f​+∂x22​∂2f​+∂x32​∂2f​+...+∂xn2​∂2f​=i=1∑n​∂xi2​∂2f​​

对于离散函数f(x)f(x)f(x), 其一阶导数可以近似得到(相邻两个自变量间隔为1)：

∂f∂x=f′(x)=f(x+1)−f(x)∂2f∂x2=f′′(x)=f′(x)−f′(x−1)=f(x+1)−f(x)−f(x)+f(x−1)=f(x+1)+f(x−1)−2f(x)\begin{aligned} \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) -f(x) + f(x-1) \\ &= f(x+1) + f(x-1) - 2f(x) \end{aligned} ∂x∂f​∂x2∂2f​​=f′(x)=f(x+1)−f(x)=f′′(x)=f′(x)−f′(x−1)=f(x+1)−f(x)−f(x)+f(x−1)=f(x+1)+f(x−1)−2f(x)​

因此，离散函数f(x)f(x)f(x)的拉普拉斯算子为：

Δf=f(x+1)+f(x−1)−2f(x)\begin{aligned} \Delta f = f(x+1) + f(x-1) - 2f(x) \end{aligned} Δf=f(x+1)+f(x−1)−2f(x)​

对于离散函数f(x,y)f(x,y)f(x,y)其拉普拉斯算子为：

Δf=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)\begin{aligned} \Delta f &= 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) \end{aligned} Δf​=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)​

图拉普拉斯矩阵-来源

初次接触图神经网络时，大家肯定会看到图拉普拉斯矩阵定义为L=D−AL = D - AL=D−A,或者归一化形式的拉普拉斯矩阵Lsym=I−D−12AD−12L_{sym} = I - D^{-\frac{1}{2}}AD^{-\frac{1}{2}}Lsym​=I−D−21​AD−21​, 你是不是会感到有点突兀，想知道为什么需要这么定义， 为了解决长久以来的好奇，下面给出了两种推导方法。

为了引入图的邻接矩阵和度矩阵等结构信息到拉普拉斯算子计算过程中，将邻接矩阵表示为AAA,度矩阵表示为DDD:

邻接矩阵

邻接矩阵A∈RN×NA \in \mathbb{R}^{N \times N}A∈RN×N, aij=1a_{ij}=1aij​=1表示节点iii和节点jjj之间是相互连接，如果在邻接矩阵中加入自环，即aii=1a_{ii}=1aii​=1, 矩阵形式表示为A^=A+I\hat{A} = A + IA^=A+I, 单位矩阵用I∈RN×NI \in \mathbb{R}^{N \times N}I∈RN×N表示度矩阵

度矩阵为对角矩阵，在矩阵的对角线上取值为Di=∑j∈NaijD_{i} = \sum_{j \in N}a_{ij}Di​=∑j∈N​aij​，其他区域取值为0,同理，在邻接矩阵包含自环的情况下，D^=D+I\hat{D} = D + ID^=D+I

推导-方法1：娓娓道来

对于包含NNN个节点的图GGG, 可以将其看做为一个包含NNN个变量的离散函数fff,节点iii的取值用xix_ixi​表示，用NiN_iNi​表示图中节点iii的一阶邻居节点集合，j∈Nij \in N_ij∈Ni​表示节点iii的一个一阶邻居节点。

根据上述离散函数f(x)f(x)f(x)拉普拉斯算子的结果形式，对于节点iii进行类比，如下等式所示，节点$i$的拉普拉斯算子描述的是节点与邻居节点之间信号的差异:

Δfxi=∑j∈Ni(xi−xj)\begin{aligned} \Delta f_{x_i} = \sum_{j \in N_i} (x_i - x_j) \end{aligned} Δfxi​​=j∈Ni​∑​(xi​−xj​)​

为了对上述节点的邻居节点集合NiN_iNi​使用邻接矩阵进行替换，需要继续对上述图中的拉普拉斯算子进行矩阵形式的推导；首先，将图GGG中的各个节点的取值表示成矩阵的形式：

XN×1=(x1x2⋮xN)X^{N \times 1} = \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_{N} \end{pmatrix} XN×1=⎝⎜⎜⎜⎛​x1​x2​⋮xN​​⎠⎟⎟⎟⎞​

aia_iai​ 表示邻接矩阵中的第iii行,定义Ai=[ai1,ai2,⋯,aiN]A_i =[a_{i1}, a_{i2}, \cdots ,a_{iN}]Ai​=[ai1​,ai2​,⋯,aiN​], 那么对于节点iii, 可以进一步进行展开：

Δfxi=∑j∈Ni(xi−xj)=∑j∈Naij(xi−xj)=∑j∈Naijxi−∑j∈Naijxj=xi∑j∈Naij−∑j∈Naijxj=xiDi−∑j∈Naijxj=xiDi−AiX\begin{aligned} \Delta f_{x_i} &= \sum_{j \in N_i} (x_i - x_j) \\ &= \sum_{j \in N} a_{ij}(x_i - x_j) \\ &= \sum_{j \in N} a_{ij}x_i - \sum_{j \in N}a_{ij}x_j \\ &= x_i \sum_{j \in N}a_{ij} - \sum_{j \in N} a_{ij}x_j \\ &= x_i D_{i} - \sum_{j \in N} a_{ij}x_j \\ &= x_i D_{i} - A_i X \end{aligned} Δfxi​​​=j∈Ni​∑​(xi​−xj​)=j∈N∑​aij​(xi​−xj​)=j∈N∑​aij​xi​−j∈N∑​aij​xj​=xi​j∈N∑​aij​−j∈N∑​aij​xj​=xi​Di​−j∈N∑​aij​xj​=xi​Di​−Ai​X​

对所有节点进行计算拉普拉斯计算取值，构成矩阵：

Δf=(Δfx1Δfx2⋮ΔfxN)=(x1D1−A1Xx2D2−A2X⋮xNDN−ANX)=(x1D1x2D2⋮xNDN)−(A1XA2X⋮ANX)\Delta f = \begin{pmatrix} \Delta f_{x_1} \\ \Delta f_{x_2} \\ \vdots \\ \Delta f_{x_N} \end{pmatrix} = \begin{pmatrix} x_1 D_1 - A_1 X \\ x_2 D_2 - A_2 X \\ \vdots \\ x_N D_N - A_N X \end{pmatrix} = \begin{pmatrix} x_1 D_{1} \\ x_2 D_{2} \\ \vdots \\ x_N D_{N} \end{pmatrix} - \begin{pmatrix} A_1 X \\ A_2 X \\ \vdots \\ A_N X \end{pmatrix} Δf=⎝⎜⎜⎜⎛​Δfx1​​Δfx2​​⋮ΔfxN​​​⎠⎟⎟⎟⎞​=⎝⎜⎜⎜⎛​x1​D1​−A1​Xx2​D2​−A2​X⋮xN​DN​−AN​X​⎠⎟⎟⎟⎞​=⎝⎜⎜⎜⎛​x1​D1​x2​D2​⋮xN​DN​​⎠⎟⎟⎟⎞​−⎝⎜⎜⎜⎛​A1​XA2​X⋮AN​X​⎠⎟⎟⎟⎞​

我们继续进行简化，时刻记住要将邻接矩AAA阵和度矩阵DDD凑进去：

(A1XA2X⋮ANX)=AN×NXN×1=AX\begin{pmatrix} A_1 X \\ A_2 X \\ \vdots \\ A_N X \end{pmatrix} = A^{N\times N} X^{N\times 1} = AX ⎝⎜⎜⎜⎛​A1​XA2​X⋮AN​X​⎠⎟⎟⎟⎞​=AN×NXN×1=AX

(x1D1x2D2⋮xiDN)=(D100⋯00D20⋯0⋮⋮⋮⋱⋮000⋯DN)N×NXN×1=DN×NXN×1=DX\begin{pmatrix} x_1 D_{1} \\ x_2 D_{2} \\ \vdots \\ x_i D_{N} \end{pmatrix} = \begin{pmatrix} D_1 & 0 & 0 & \cdots & 0 \\ 0 & D_2 & 0 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & D_N\\ \end{pmatrix} ^{N\times N} X^{N\times 1} = D^{N\times N} X^{N \times 1} = DX ⎝⎜⎜⎜⎛​x1​D1​x2​D2​⋮xi​DN​​⎠⎟⎟⎟⎞​=⎝⎜⎜⎜⎛​D1​0⋮0​0D2​⋮0​00⋮0​⋯⋯⋱⋯​00⋮DN​​⎠⎟⎟⎟⎞​N×NXN×1=DN×NXN×1=DX

综上，得到了拉普拉斯算子在图上的等式,LLL被称作为拉普拉斯矩阵

Δf=DX−AX=(D−A)XL=D−A\begin{aligned} \Delta f &= DX - AX = (D - A) X \\ L &= D - A \end{aligned} ΔfL​=DX−AX=(D−A)X=D−A​

推导-方法2：直接干脆

基于上述推导过程，以及单个节点的定义，我们可以再反过来直接从定义入手，快速推演一遍;

先看原本的定义公式，可以展开，假如节点iii的邻域内有NiN_{i}Ni​个节点,即节点的度DiD_iDi​，那么：

Δfxi=∑j∈Ni(xi−xj)=Ni∗xi−xj1−xj2⋯−xjN=Dixi−xj1−xj2⋯−xjN\begin{aligned} \Delta f_{x_i} &= \sum_{j \in N_i} (x_i - x_j) \\ &= N_{i} * x_i - x_{j1} - x_{j2} \cdots -x_{jN} \\ &= D_i x_i - x_{j1} - x_{j2} \cdots -x_{jN} \end{aligned} Δfxi​​​=j∈Ni​∑​(xi​−xj​)=Ni​∗xi​−xj1​−xj2​⋯−xjN​=Di​xi​−xj1​−xj2​⋯−xjN​​

上式中的xj1,xj2,⋯,xjNx_{j1}, x_{j2} , \cdots , x_{jN}xj1​,xj2​,⋯,xjN​来自于X=[x1,x2,⋯,xN]TX=[x_1,x_2, \cdots, x_N]^TX=[x1​,x2​,⋯,xN​]T,为了理解方便下列等式方便，只假设节点111的有两个邻居：2,N−12,N-12,N−1, 节点222的也有2邻居为1,31,31,3，:

Δf=(Δfx1Δfx2⋮ΔfxN)=(∑j∈N1(x1−xj)∑j∈N2(x2−xj)⋮∑j∈NN(xN−xj))=(D1∗x1−x2−xN−1D2∗x2−x1−x3⋮DN∗xN−xj1−xj2⋯−xjN)=(D1−10⋯−1−1D2−1⋯0⋮⋮⋮⋱⋮000⋯DN)(x1x2⋮xN)=(D−A)X=LX\begin{aligned} \Delta f &= \begin{pmatrix} \Delta f_{x_1} \\ \Delta f_{x_2} \\ \vdots \\ \Delta f_{x_N} \end{pmatrix} = \begin{pmatrix} \sum_{j \in N_{1}} (x_1 - x_j) \\ \sum_{j \in N_{2}} (x_2 - x_j) \\ \vdots \\ \sum_{j \in N_{N}} (x_N - x_j) \end{pmatrix} \\& = \begin{pmatrix} D_1 * x_1 - x_2 - x_{N-1} \\ D_2 * x_2 - x_1 - x_3 \\ \vdots \\ D_N * x_N - x_{j1} - x_{j2} \cdots - x_{jN} \end{pmatrix} \\ &= \begin{pmatrix} D_1 & -1 & 0 & \cdots & -1 \\ -1 & D_2 & -1 & \cdots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \cdots & D_N\\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ \vdots \\ x_{N} \end{pmatrix} \\ &= (D - A) X \\ &= LX \end{aligned} Δf​=⎝⎜⎜⎜⎛​Δfx1​​Δfx2​​⋮ΔfxN​​​⎠⎟⎟⎟⎞​=⎝⎜⎜⎜⎛​∑j∈N1​​(x1​−xj​)∑j∈N2​​(x2​−xj​)⋮∑j∈NN​​(xN​−xj​)​⎠⎟⎟⎟⎞​=⎝⎜⎜⎜⎛​D1​∗x1​−x2​−xN−1​D2​∗x2​−x1​−x3​⋮DN​∗xN​−xj1​−xj2​⋯−xjN​​⎠⎟⎟⎟⎞​=⎝⎜⎜⎜⎛​D1​−1⋮0​−1D2​⋮0​0−1⋮0​⋯⋯⋱⋯​−10⋮DN​​⎠⎟⎟⎟⎞​⎝⎜⎜⎜⎛​x1​x2​⋮xN​​⎠⎟⎟⎟⎞​=(D−A)X=LX​

虽然这里说是给了两种推导形式，本质上都是从图上节点拉普拉斯的定义开始，利用矩阵形式来表示了而已，整个推导过程都是在写成矩阵相乘的过程。

图拉普拉斯矩阵-性质

有了图拉普拉斯矩阵，我们就来看看它有什么优点，性质，能够为后续图神经网络带来什么，在本文中不会涉及到图拉普拉斯矩阵分解相关的内容，下一篇图傅里叶变换相关内容中将详细介绍；另外值得注意的是，图拉普拉斯矩阵不是为了图神经网络而生，而在之前就存在了很久很久，早到PageRank这样的算法之前。

两种表示形式

标准拉普拉斯矩阵形式为：

Lij={Dii,ifi=j−1,ifi,jinedgeset0,otherwiseL_{ij} = \begin{cases} D_{ii}, & \text{if i = j} \\ -1, & \text{if i,j in edge set} \\ 0, & \text{otherwise} \end{cases} Lij​=⎩⎪⎨⎪⎧​Dii​,−1,0,​ifi=jifi,jinedgesetotherwise​

拉普拉斯矩阵的对角线上取值为节点的度如果节点iii和节点jjj相邻，那么取值为-1显然，拉普拉斯矩阵为对称的矩阵

归一化的拉普拉斯矩阵LsymL_{sym}Lsym​,各元素取值：

Lij={1,ifi=j−1DiiDjj,ifi,jinedgeset0,otherwiseL_{ij} = \begin{cases} 1, & \text{if i = j} \\ \frac{-1}{ \sqrt{D_{ii}} \sqrt{D_{jj}}}, & \text{if i,j in edge set} \\ 0, & \text{otherwise} \end{cases} Lij​=⎩⎪⎪⎨⎪⎪⎧​1,Dii​​Djj​​−1​,0,​ifi=jifi,jinedgesetotherwise​

大家见的比较多的形式为：

Lsym=D−12LD−12=I−D−12AD−12\begin{aligned} L_{sym} = D^{-\frac{1}{2}}L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}}A D^{-\frac{1}{2}} \end{aligned} Lsym​=D−21​LD−21​=I−D−21​AD−21​​

假设度矩阵取值为：

D=(200030004),thenD−12=(120001300014)\begin{aligned} D = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 4 \\ \end{pmatrix}, \text{then } D^{-\frac{1}{2}} = \begin{pmatrix} \frac{1}{\sqrt2} & 0 & 0 \\ 0 & \frac{1}{\sqrt3} & 0 \\ 0 & 0 & \frac{1}{\sqrt 4} \\ \end{pmatrix} \end{aligned} D=⎝⎛​200​030​004​⎠⎞​,thenD−21​=⎝⎜⎛​2​1​00​03​1​0​004​1​​⎠⎟⎞​​

二次型

根据给定的图拉普斯定义(推导2)，或者直接给定了图拉普拉斯矩阵LLL,可以得到图中任意节点的经过拉普拉斯矩阵聚合后的结果：

LX=(D−A)X=[⋯,∑j∈Nxi(xi−xj),⋯]T\begin{aligned} LX = (D-A)X = \Big[ \cdots, \sum_{j \in N_{x_i}} (x_i - x_j), \cdots \Big]^T \end{aligned} LX=(D−A)X=[⋯,j∈Nxi​​∑​(xi​−xj​),⋯]T​

其中，LX∈RN×1LX \in \mathbb{R}^{N\times 1}LX∈RN×1那么：

XTLX=[x1,x2,⋯,xi,⋯,xN][⋯,∑j∈Nxi(xi−xj),⋯]T=∑i=1N∑j∈Nxixi(xi−xj)=∑aij=1(xi−xj)2\begin{aligned} X^T LX &= \Big[x_1, x_2, \cdots, x_i, \cdots,x_N \Big] \Big[ \cdots, \sum_{j \in N_{x_i}} (x_i - x_j), \cdots \Big]^T \\ &= \sum_{i=1}^N \sum_{j \in N_{x_i}} x_i (x_i - x_j) \\ &= \sum_{a_{ij}=1} (x_i - x_j)^2 \end{aligned} XTLX​=[x1​,x2​,⋯,xi​,⋯,xN​][⋯,j∈Nxi​​∑​(xi​−xj​),⋯]T=i=1∑N​j∈Nxi​​∑​xi​(xi​−xj​)=aij​=1∑​(xi​−xj​)2​

这里需要来解释一下，为啥图信号XXX经过拉普拉斯矩阵LLL的二次型会是上述形式：图任意两条边上信号之差的平方和.

假设节点iii和节点jjj互为一阶邻居时，在邻接矩阵中表示为aij=1a_{ij}=1aij​=1, 上式展开后最多有N×NN \times NN×N项相加，但我们现在仅考虑节点xix_ixi​和xjx_jxj​，即其展开后其中的两项，即：

xi(xi−xj)+xj(xj−xi)=xi2−2xixj+xj2=(xi−xj)2x_i(x_i - x_j) + x_j(x_j - x_i) = x_i^2 - 2x_ix_j + x_j^2 = (x_i - x_j)^2 xi​(xi​−xj​)+xj​(xj​−xi​)=xi2​−2xi​xj​+xj2​=(xi​−xj​)2

因此对于图中任意的一条边，都可以表示成(xi−xj)2(x_i - x_j)^2(xi​−xj​)2的形式，在图信号处理中，将$TV(X) = X^T L X $看做为图信号的总变差,其物理含义为图上各边上信号差值的平方和，刻画了整体信号的平滑度。

在图信号处理中，还有另外一种推导方式，与之前的定义相同， 对于包含NNN个节点的图GGG, 可以将其看做为一个包含NNN个变量的离散函数fff，对于图中相连的一条边e=(i,j)e=(i,j)e=(i,j)，定义：

边的导数

∂f∂e∣i=xi−xj\begin{aligned} \frac{\partial f}{\partial e} \Big |_i = x_i - x_j \end{aligned} ∂e∂f​∣∣∣​i​=xi​−xj​​

图的梯度，在节点iii处，如果存在多条边aij=1a_{ij}=1aij​=1,构成一个集合，那么：

∇if={∂f∂e∣i}\begin{aligned} \nabla_i f = \{ \frac{\partial f}{\partial e} \Big |_i \} \end{aligned} ∇i​f={∂e∂f​∣∣∣​i​}​

求模：

∣∣∇if∣∣=∑aij=1(xi−xj)2\begin{aligned} || \nabla_i f||= \sum_{a_{ij}=1} (x_i - x_j)^2 \end{aligned} ∣∣∇i​f∣∣=aij​=1∑​(xi​−xj​)2​

加权聚合

如果将归一化的拉普拉斯矩阵作用在图上，即：

Δf=LsymX=(I−D−12AD−12)X\begin{aligned} \Delta f &= L_{sym}X = (I - D^{-\frac{1}{2}}A D^{-\frac{1}{2}}) X \end{aligned} Δf​=Lsym​X=(I−D−21​AD−21​)X​

如果我们仅仅关注D−12AD−12XD^{-\frac{1}{2}}A D^{-\frac{1}{2}}XD−21​AD−21​X,可以理解其作用：对节点的一阶邻居信息的加权聚合，权重与节点的度成反比

那怎么来理解上述结论呢？下面给出证明过程。

对于节点iii,如果要利用D−12AD−12XD^{-\frac{1}{2}}A D^{-\frac{1}{2}}XD−21​AD−21​X来汇聚其邻居的信息，推导过程如下：

首先，根据上式从左向右进行矩阵相乘，对于节点iii, D−12AD^{-\frac{1}{2}}AD−21​A生成的矩阵表示为CCC，CCC的第iii行，第jjj列的元素取值如下，由于度矩阵中仅对角线上存在非零取值，当且仅当k=ik=ik=i有值，可以简化成：

Cij=∑k=0N−1Dik−12Akj=Dii−12Aij\begin{aligned} C_{ij} &= \sum_{k=0}^{N-1} D^{-\frac{1}{2}}_{ik} A_{kj} \\ &= D^{-\frac{1}{2}}_{ii} A_{ij} \end{aligned} Cij​​=k=0∑N−1​Dik−21​​Akj​=Dii−21​​Aij​​

根据上述矩阵相乘过程得到的矩阵CCC，再次利用矩阵CCC和 D−12D^{-\frac{1}{2}}D−21​相乘，结果用QQQ表示，其中各元素的计算逻辑为：

Qi,j=∑k=0N−1CikDkj−12=CijDjj−12\begin{aligned} Q_{i,j} &= \sum_{k=0}^{N-1} C_{ik} D^{-\frac{1}{2}}_{kj} \\ &= C_{ij} D^{-\frac{1}{2}}_{jj} \end{aligned} Qi,j​​=k=0∑N−1​Cik​Dkj−21​​=Cij​Djj−21​​​

由于度矩阵中仅对角线上存在非零取值，当且仅当k=jk=jk=j有值，可以简化成上式；其中QQQ矩阵可以表述为：

Qij=Dii−12AijDjj−12=AijDiiDjj\begin{aligned} Q_{ij} &= D^{-\frac{1}{2}}_{ii} A_{ij} D^{-\frac{1}{2}}_{jj} \\ &= \frac{A_{ij}}{\sqrt{D_{ii} D_{jj}}} \end{aligned} Qij​​=Dii−21​​Aij​Djj−21​​=Dii​Djj​​Aij​​​

即，邻接矩阵元素的取值被加权了，节点iii和节点jjj的权重分别与各自的度成反比，度越大，两个节点之间的权重越小(这一点在后续图神经网络的通用框架部分在做解释)；

有了上述结果，得到矩阵QQQ, QXQXQX为最终的信息聚合过程，假设X∈RN×1X\in \mathbb{R}^{N \times 1}X∈RN×1,即各个节点的维度为111,那么，对于节点iii能够聚合的信息为：

Aggi=∑k=0N−1Qi,kXk=∑k=0N−1AikDiiDkkXk\begin{aligned} Agg_i &= \sum_{k=0}^{N-1} Q_{i,k} X_k \\ &= \sum_{k=0}^{N-1} \frac{A_{ik}}{\sqrt{D_{ii} D_{kk}}} X_k \end{aligned} Aggi​​=k=0∑N−1​Qi,k​Xk​=k=0∑N−1​Dii​Dkk​​Aik​​Xk​​

假设节点iii有3个相邻的节点(Dii=3D_{ii}=3Dii​=3)，p,q,kp,q,kp,q,k, 那么利用归一化的拉普斯矩阵，节点iii能够聚合到的信息为：

Aggi=xpDiiDpp+xqDiiDqq+xkDiiDkk\begin{aligned} Agg_i = \frac{x_p}{\sqrt{D_{ii} D_{pp}}} + \frac{x_q}{\sqrt{D_{ii} D_{qq}}} + \frac{x_k}{\sqrt{D_{ii} D_{kk}}} \end{aligned} Aggi​=Dii​Dpp​​xp​​+Dii​Dqq​​xq​​+Dii​Dkk​​xk​​​

总结

首先，本文先从连续函数和离散函数出发，给出了拉普拉斯算子的定义，衍生到图数据上，给定了节点域上各个节点的拉普拉斯算子的形式；为了将刻画了图结构信息的度矩阵和邻接矩阵融合到图拉普拉斯矩阵LLL的推导中来，根据定义，从两个不同的角度推导出了L=D−AL = D - AL=D−A，解决了被动接受定义的状态；有了拉普拉斯矩阵LLL的定义和推导过程，我们进一步了解了其两种形式，标准和归一化形式Lsym=I−D−12AD−12L_{sym} = I - D^{-\frac{1}{2}}A D^{-\frac{1}{2}}Lsym​=I−D−21​AD−21​；为了进一步理解拉普拉斯矩阵LLL的作用，分别介绍了给定图信号XXX，经过XTLXX^TLXXTLX变换后的二次型的形式，引出了图信号中总变差的概念，其刻画信号平滑程度的物理意义；同时从信息聚合的角度，推导了归一化的拉普拉斯矩阵LLL是对节点的一阶邻居信息的加权聚合，权重与节点的度成反比;

如果觉得《图拉普拉斯矩阵的定义 推导 性质 应用》对你有帮助，请点赞、收藏，并留下你的观点哦！