全面入门:图卷积网络(GCN)的谱分析

技术讨论 小白学CV ⋅ 于 2个月前 ⋅ 387 阅读

Author:大家都叫我0号 注:转载请注明出处\~\~ 本文简要介绍了信号处理的一些概念,介绍了图卷积的定义和各种谱方法下的GNN,最后分析了GCN过平滑的原因。大约5千余字,里面有一些公式比较复杂,可能需要手推一下\~\~。

1 Introduction

某的上一篇文章图表示学习极简教程介绍了图嵌入(Graph Embedding)、图神经网络(GNNs)的一些发展。图表示学习极简教程对GCN、GraphSAGE、GAT等模型进行了介绍,这些介绍都是从空域的角度对图卷积进行分析,也就是说GNNs每层的网络就是对邻居结点的聚合操作。这样的idea似乎很好理解,也很好想到。其实,这些方法的背后蕴含着许多信号分析的重要背景。 ​ 近日听了ICT沈老师相关知识的讲授后,某自认为对图卷积网络的谱分析有了更进一步的理解。下面就开始进入正题吧。 【注】:如果读者已经了解过卷积、傅里叶变换的相关概念,可以对部分章节选择性跳过。

2 卷积

【注意】:下列公式中的积分、求和上下限在遇到具体问题是会退化为具体的数字。积分上下限为无穷只是它的一般定义。

  • 一维连续卷积

卷积的名字似乎听上去让人感觉有些晦涩,其实它的计算难度并不大。我们给定两个函数 \$f(x)\$ 和 \$g(x)\$ ,这两个函数的卷积 \$(f*g)(x)\$ 的计算公式如下(这个公式应该小伙伴们都在概率论中见过):

\$ (f*g)(x) = \int_{-\infty}\^{+\infty}f(\tau)g(x-\tau)d\tau \\\$

图1 连续卷积动图

  • 二维连续卷积(这里不太重要,理解是怎么算的就行)

和一维卷积类似,对于多元函数 \$f(x,y)、g(x, y)\$ ,二维的连续函数卷积可以表示为:

\$(f*g) = \int_{\tau_{1}=-\infty}\^{+\infty}\int_{\tau_{2}=-\infty}\^{+\infty}f(\tau_{1},\tau_{2})g(x-\tau_{1},y-\tau_{2})d\tau_{2}d\tau_{1} \\\$

  • 一维离散卷积

将连续卷积的积分号变为求和号,就可以得到两个离散函数\$f(x)\$ 和\$g(x)\$ 一维离散卷积的公式: \$ (f*g)(n) = \sum_{k=-\infty}\^{+\infty}f(k)g(n-k) \\\$ 在此,引用一张很形象的图(结合公式)来帮助小伙伴们理解什么是一维离散卷积:

图2 一维离散卷积示意图

  • 二维离散卷积

这是卷积神经网络(CNN)的基础,和上述的卷积类似,对两个信号\$f(x,y)\$、\$g(x, y)\$,我们定义他的二维离散卷积公式为: \$ (f*g) = \sum_{k_{1}=-\infty}\^{+\infty}\sum_{k_{2}=-\infty}\^{+\infty}f(k_{1},k_{2})g(x-k_{1},y-k_{2}) \\\$ 这里还是借助一个动图来看看二维的卷积是如何卷的:

图3 二维离散卷积

不难发现二维离散的卷积是将卷积核进行一个中心对称的翻转后,在进行对应位置相乘求和得到的。然而,实际上大家在CNN的计算中可以省去旋转的步骤,因为卷积核的参数是学来的。

3 傅里叶变换与卷积的另一种求法

由于一些信号在时域内部难以分析,我们将信号先变换到频域,再变换回时域,以便于我们的分析。 ​ 我们对一个时域信号函数 \$f(t)\$ 做傅里叶变换: \$ \mathcal{F}\{f\} = \int_{-\infty}\^{+\infty}f(t)e\^{-j\omega t}dt \\\$ 有时候,我们在时域很难求卷积,我们就要利用下面的卷积公式求解: \$\mathcal{F}\{f*g\}=\mathcal{F}\{f\}\mathcal{F}\{g\} \\\$ 这个公式告诉我们,时域卷积的傅里叶变换等于傅里叶变换的乘积。因此,我们可以这样求卷积:\$f*g=\mathcal{F}\^{-1}\{\mathcal{F}\{f\}\mathcal{F}\{g\}\}\\\$ 其中, \$\mathcal{F}\^{-1}\$ 代表傅里叶变换的逆变换。

4 拉普拉斯算子

我们知道,一个二元函数 \$f(x, y)\$ 的Nabla算子,可以表示为: \$\nabla=\frac{\partial }{\partial x}\vec{i} + \frac{\partial }{\partial y}\vec{j} \\\$ 那么梯度就可以表示为: \$\nabla f=\frac{\partial f}{\partial x}\vec{i} + \frac{\partial f}{\partial y}\vec{j}\\\$ 下面定义拉普拉斯算子:

\$\begin{eqnarray} \Delta f \&=\&\nabla \cdot \nabla f\ \\\&=\&\frac{\partial\^2 f}{\partial x\^2} + \frac{\partial\^2 f}{\partial y\^2}\ \end{eqnarray} \\\$

显然,我们可以把拉普拉斯算子视为二阶导数。

上述的拉普拉斯算子表示的是连续函数 \$f(x, y)\$ 的拉普拉斯算子。那么离散情况下的拉普拉斯算子是什么呢? 我们可以用差分来近似我们的“导数”概念。对于一个离散的二元函数\$f(x,y)\$,它的拉普拉斯算子可表示为:
$$\begin{eqnarray} \Delta f &=&\frac{\partial^2 f}{\partial x^2} + \frac{\partial^2 f}{\partial y^2}\ \ &\approx& [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{eqnarray}\$$

我们可以观察一下上面这个式子,它可以写成:
$$
\begin{eqnarray}\Delta f &=& f(x+1,y)+f(x-1,y)+f(x,y+1)+f(x,y-1)-4f(x,y)\ \&=& [f(x+1,y)-f(x,y)] \&&+[+f(x-1,y)-f(x,y)] \ &&+[f(x,y+1)-f(x,y)]\ &&+[f(x,y-1)-f(x,y)]\ \end{eqnarray}
$$

从直观上看,拉普拉斯算子体现的离散值之间的关系为:

图4 拉普拉斯算子的直观表示

根据拉普拉斯算子的定义和图4相关可视化表示,我们可以看出离散拉普拉斯算子描述的是二维空间上与上、下、右邻居局部差异的和。下一步我们就可以将这个概念迁移到图上去定义图的拉普拉斯矩阵。

5 拉普拉斯矩阵

离散拉普拉斯算子描述的是二维空间上与上、下、右邻居局部差异的和。迁移到图上,我们将拉普拉斯算子定义为与邻居结点特征信息 \$f\$ 差异的和,即: \$\Delta f_{i} = \sum_{j\in \mathcal{N_i}}(f_i-f_j) \\\$ 其中 \$\mathcal N_i\$ 表示结点 \$i\$ 的邻居结点,这里的 \$f_i\$ 表示第 \$i\$ 个结点的特征(信号),简便起见,\$f_i\$ 只有一维(看做数字、标量)。我们用 \$a_{ij}\$ 表示结点之间的邻接关系: \$a_{ij} =\begin{cases} 1, \:结点i同j邻接\\ 0, \:结点i同j不邻接\ \end{cases} \\\$ 下面我们将 \$\Delta f_{i}\$ 扩充到所有结点集合 \$V\$ 进行表示:

\$ \begin{eqnarray} \Delta f_{i} \&=\& \sum_{j\in \mathcal{N_i}}(f_i-f_j)\\ \&=\&\sum_{j\in V}a_{ij}(f_i-f_j)\\ \&=\&\sum_{j\in V}a_{ij}f_i-\sum_{j\in V}a_{ij}f_j\\ \&=\&d_{i}f_{i}-\sum_{j\in V}a_{ij}f_j \end{eqnarray} \\\$

其中 \$d_{i}\$ 表示结点 \$i\$ 的度数。

我们将每个结点的 \$\Delta f_{i}\$ 扩充到整个图上,得到:

\$\begin{eqnarray} \Delta f \&=\& \begin{bmatrix} \Delta f_1\\ \Delta f_2\\ ...\\ \Delta f_n \end{bmatrix}\\ \&=\&\begin{bmatrix} d_{1}f_{1}-\sum_{j\in V}a_{1j}f_j\\ d_{2}f_{2}-\sum_{j\in V}a_{2j}f_j\\ ...\\ d_{3}f_{3}-\sum_{j\in V}a_{3j}f_j\ \end{bmatrix}\\ \&=\&\begin{bmatrix} d_1 \& \& \& \\ \&d_2 \& \& \\ \&\& \ddots \& \\ \& \& \& d_n \end{bmatrix}f -\begin{bmatrix} a_{11} \& ... \& a_{1n} \\ \vdots \& \ddots \& \vdots \\ a_{n1} \& ... \& a_{nn} \end{bmatrix}f\\ \&=\&\boldsymbol Df-\boldsymbol Af\\ \&=\&(\boldsymbol D-\boldsymbol A)f=\boldsymbol Lf \end{eqnarray} \\\$

这样我们就定义了图的拉普拉斯矩阵\$\boldsymbol L\$。\$\boldsymbol L\$ 的对角线元素对应着各个结点的度数,非对角线元素对应着图的邻接矩阵。我们给出一个拉普拉斯矩阵的范例

图5 拉普拉斯矩阵示例

  • 性质1:拉普拉斯矩阵有\$n\$ 个线性无关的特征向量

原因:拉普拉斯矩阵是实对称矩阵。

  • 性质2:特征值非负

首先,我们定义图的总变差为矩阵 \$\boldsymbol L\$ 的二次型:

\$ \begin{eqnarray} TV(\boldsymbol L) \&=\& f\^T \boldsymbol Lf\\ \&=\& \sum_{i}\sum_{j\in \mathcal{N_i}}f_{i}(f_{i}-f_{j})\\ \&=\&\sum_{i, j邻接}(f_i-f_j)\^2\ge0 \end{eqnarray} \\\$

所以 \$\boldsymbol L\$ 是半正定的矩阵(证明手推一下难度不大)。所以它的特征值均为非负。

注意一下,这里存在一个特殊的特征值0,它对应的特征向量为 \$(1,1,…,1)\^T\$ ,这个代入验证即可。

  • 性质3:特征向量相互正交

\$\boldsymbol L\$ 是实对称矩阵,它的特征向量相互正交,构成一个特征空间。

6 图傅里叶变换与图卷积

普通的傅里叶变化公式为:\$ \mathcal{F}\{f\} = \int_{-\infty}\^{+\infty}f(t)e\^{-j\omega t}dt \\\$ 其中 \$e\^{-j\omega t}\$ 为傅里叶基。我们有:\$\Delta e\^{-j\omega t}=\frac{\partial\^2e\^{-j\omega t}}{\partial t\^2}=-\omega\^2e\^{-j\omega t}\\\$ 根据广义的特征方程 \$\boldsymbol Lv=\lambda v\$ ,我们可以看出 \$e\^{-j\omega t}\$ 就是拉普拉斯算子的特征向量, \$-\omega\^2\$ 相当于特征值 \$\lambda\$ , \$\Delta\$ 就相当于拉普拉斯矩阵。

把傅里叶变换的定义扩充到图上。传统傅里叶变换是求信号在 \$e\^{-j\omega t}\$ 上的投影,图傅里叶变换求的是一个信号 \$f\$ 在正交基 \$v\$ 上的投影(这里信号\$f\$ 是一个 \$n\$ 维的列向量,表示每一个结点 \$i\$ 仅为一个数 \$f_i\$ )。我们定义图信号的傅里叶变换为: \$ \hat f = U\^Tf \\\$ 其中,\$U\^T\$ 是矩阵 \$\boldsymbol L\$ 特征分解矩阵 \$U\$ 的转置( \$\boldsymbol L = U\Lambda U\^T\$ )。这里我们注意一下, \$U\$ 的每一个列向量为 \$\boldsymbol L\$ 的一个特征向量,\$ U \^ T\$ 的每一个行向量为 \$\boldsymbol L\$ 的一个特征向量。这样 \$U\^T\$ 与 \$f\$ 的乘积就实现了一个信号 \$f\$ 在正交基 \$v\$ 上的投影,图傅里叶变换完成。

接下来我们就可以很容易地实现傅里叶逆变换: \$ f = U\hat f=UU\^Tf=f \\\$ 这里用到了矩阵分解的性质: \$U\^T=U\^{-1}\$ 。

在信号处理中我们有如下的卷积公式:

\$f*g \leftrightarrow \mathcal{F}(f)·\mathcal{F}(g)\\ 即:f*g = \mathcal{F}\^{-1}\{\mathcal{F}\{f\}· \mathcal{F}\{g\}\}= \mathcal{F}\^{-1}\{\mathcal{F}\{g\}· \mathcal{F}\{f\}\} \$

应用到图上,我们定义卷积公式:

\$(f*g)_G =U(U\^Tf\odot U\^Tg)=U(U\^Tg\odot U\^Tf) \\\$

其中 \$\odot\$ 表示哈达玛积,就是向量的对应元素相乘(不是矩阵相乘)。我们把其中的向量 \$U\^Tg\$ 写成对角阵的形式,这样我们就可以把哈达玛积写成是矩阵相乘的形式了,即:

\$(f*g)_G = U \begin{bmatrix} \hat g(\lambda_1) \& \& \& \\ \&\hat g(\lambda_2) \& \& \\ \&\& \ddots \& \\ \& \& \& \hat g(\lambda_n) \end{bmatrix} U\^Tf \\\$

我们将对角阵用 \$g_{\theta}\$ 来表示: \$ g_{\theta}f=(f*g)G = Ug_{\theta} U\^Tf \$ 其实这里的对角阵 \$g_{\theta}\$ 就是可供学习的卷积核了。

终于!!!把图信号 \$f\$ 的卷积定义完了!

7 基于谱方法的各种Net

7.1 Spectral Graph CNN

根据上述的定义,我们知道了如何定义图上的卷积操作。那么网络的前传也就可以定义了:

\$X_{j}\^{k+1} = \sigma (U \sum_{i=1}\^{f_{k}}F\^{k}_{i, j}U\^TX\^{k}_{i})\:(j=1, 2,…, f_{k+1}) \\\$

其中:

  • 在此之前我们讨论的 \$f\$ 都只有一个特征信息(通道)。这里增加了通道数, \$f_{k}\$ , \$f_{k+1}\$ 分别表示第 \$k\$ 层和第 \$k+1\$ 层的通道数。
  • \$F\^{k}_{i, j}\$ 表示第 \$k\$ 层的可供学习的卷积核,是一个对角阵。
  • \$X\^{k}_{i}\in \mathbb R\^{n \times f_{k}}\$ 表示具有 \$f_k\$ 个通道(信号)的 \$n\$ 个结点

    该模型存在的问题主要有三:

  • 模型不是spatial localization(局部连接)的;
  • 依赖矩阵分解,前传的时候多次用到矩阵乘法,计算代价大;
  • 卷积核的规模参数 \$n\$ 收到图规模的控制,特别是对大图而言。

7.2 ChebNet

对于上述的卷积核 \$g_{\theta}\$ ,我们可以使用 \$K\$ 阶多项式进行拟合:

\$ \begin{eqnarray} g_{\theta}(\Lambda)\&\approx\&\sum_{k=0}\^{K}\theta_k\Lambda\^{k}\ \end{eqnarray} \\\$

那么图卷积就变成了:

\$\begin{eqnarray} g_{\theta}*x\&=\& U\sum_{k=0}\^K\theta_k\Lambda\^kU\^Tx\\ \&=\&\sum_{k=0}\^K\theta_kU\Lambda\^kU\^Tx\\ \&=\&\sum_{k=0}\^K\theta_k(U\Lambda U\^T)\^kx\\ \&=\&\sum_{k=0}\^K\theta_k\boldsymbol L\^kx\ \end{eqnarray} \\\$

这样的操作就将参数个数减少到 \$K\$ 个,同时也不需要进行矩阵的分解了。同时就算复杂度大大下降。注意,这里的 \$\boldsymbol L\$ 的 \$k\$ 次方就体现了局部相关特性,这和邻接矩阵 \$k\$ 次幂的含义类似,代表着 \$k\$ 阶可达。 ChebNet引入了切比雪夫多项式 \$T_k\$ 对 \$g_{\theta}\$ 进行拟合。切比雪夫多项式的递归定义为:

\$ \begin{cases} T_0(x) = 1\\ T_1(x) = x\\ T_k(x) = 2xT_{k-1}(x)-T_{k-2}(x)\ \end{cases} \\\$

\$g_{\theta}\$ 的 \$K\$ 阶近似为:\$g_{\theta}(\Lambda)\approx\sum_{k=0}\^{K}\theta'_kT_k(\tilde\Lambda)\ \\\$ 其中 \$\tilde\Lambda=2·\frac{\Lambda}{\lambda_{max}}-I\$ ,\$\lambda_{max}\$ 是最大的特征值,这个操作的意义是将特征值调整到 \$[-1,1]\$ 的范围中,因为我们知道拉普拉斯矩阵的特征值非负,且有最小值为0(稍加推导就可以得到范围了)。这个操作可以防止梯度爆炸。

现在我们的图卷积公式就可以被进一步写成是:

\$ \begin{eqnarray} g_{\theta}*x\&=\& U\sum_{k=0}\^K\theta'_kT_{k}(\tilde \Lambda)U\^Tx\\ \&=\& \sum_{k=0}\^K\theta'_kUT_{k}(\tilde \Lambda)U\^Tx \tag 1\\ \&=\& \sum_{k=0}\^K\theta'_kT_{k}(U\tilde \Lambda U\^T)x \tag 2\\ \&=\& \sum_{k=0}\^K\theta'_kT_{k}(\boldsymbol {\tilde L})x \tag3\ \end{eqnarray} \$

下面介绍公式 \$(1),(2),(3)\$ 之间是如何进行转换的。

  • \$(1)\to(2)\$ 的证明:

只要证明: \$UT_{k}(\tilde \Lambda)U\^T =T_{k}(U\tilde \Lambda U\^T) \\\$ 对上述式子应用数学归纳法:

  1. \$k=0\$ 或 \$k=1\$ 时,根据切比雪夫多项式的定义, \$T_{0}(\tilde \Lambda)=I,T_{1}(\tilde \Lambda)=\tilde \Lambda\$ 。

\$\begin{eqnarray} UT_{0}(\tilde \Lambda)U\^T=UU\^T=I=T_{0}(U\tilde \Lambda U\^T)\\ UT_{1}(\tilde \Lambda)U\^T=U\tilde \Lambda U\^T=T_{1}(U\tilde \Lambda U\^T) \end{eqnarray} \\\$

  1. 假设小于 \$k\$ 的时候都成立。

\$ \begin{eqnarray} \&\&UT_{k}(\tilde \Lambda)U\^T \\ \&=\&U(2\tilde \Lambda T_{k-1}(\tilde \Lambda)-T_{k-2}(\tilde \Lambda))U\^T\\ \&=\&2U\tilde \Lambda T_{k-1}(\tilde \Lambda)U\^T-UT_{k-2}(\tilde \Lambda)U\^T\\ \&=\&2U\tilde \Lambda U\^TU T_{k-1}(\tilde \Lambda)U\^T-UT_{k-2}(\tilde \Lambda)U\^T\\ \&=\&2(U\tilde \Lambda U\^T)(U T_{k-1}(\tilde \Lambda)U\^T)-UT_{k-2}(\tilde \Lambda)U\^T\\ \&=\&T_{k}(U\tilde \Lambda U\^T)\ \end{eqnarray} \\\$ 证毕。

  • \$(2)\to(3)\$ 的转换:

\$\begin{eqnarray} \boldsymbol{\tilde L}\&=\& U\tilde \Lambda U\^T\\ \&=\&U(2·\frac{\Lambda}{\lambda_{max}}-I)U\^T\\ \&=\&(2·\frac{U\Lambda U\^T}{\lambda_{max}}-I)\\ \&=\&(2·\frac{\boldsymbol{L}}{\lambda_{max}}-I)\\ \end{eqnarray} \\\$

由此我们就得到了新的卷积公式: \$ g_{\theta}*x = \sum_{k=0}\^K\theta'_kT_{k}(\boldsymbol {\tilde L})x\\ \$ 可以看出,ChebNet解决了7.1中Spectral Graph CNN存在的3个问题。

7.3 平时看到的GCN——ChebNet的一阶近似

我们对ChebNet进行一阶近似,即 \$K=1\$ 。我们可以得到下面的公式:

\$ \begin{eqnarray} g_{\theta}x \&=\&\sum_{k=0}\^1\theta'_kT_{k}(\boldsymbol {\tilde L})x\\ \&=\&\theta'_0x + \theta'_1\boldsymbol {\tilde L}x\tag 4 \ \end{eqnarray}\\\$

对 \$\boldsymbol {L}\$ 进行正则化,得到正则化后的表示: \$\boldsymbol {L\^{sym}}=D\^{-\frac{1}{2}}\boldsymbol {L}D\^{-\frac{1}{2}}=D\^{-\frac{1}{2}}(D-A)D\^{-\frac{1}{2}}=I-D\^{-\frac{1}{2}}AD\^{-\frac{1}{2}}\\\$ 正则化后的拉普拉斯矩阵特征值不超过2,所以将 \$\boldsymbol { L\^{sym}}\$ 的最大特征值近似为为2, \$\widetilde { \boldsymbol { L\^{sym}}}=\boldsymbol { L\^{sym}}-I\$ 。将 \$ \widetilde { \boldsymbol { L\^{sym}}}\$ 带入 \$\boldsymbol {\tilde L}\$ , \$\theta'_0=-\theta'_1=\theta\$ , \$(4)\$ 可以转换成:

\$ \begin{eqnarray} g_{\theta}x \&=\&\theta'_0x + \theta'_1\boldsymbol {\tilde L}x \\ \&=\&\theta'_0I + \theta'_1 \widetilde { \boldsymbol { L\^{sym}}}x\\ \&=\&\theta'_0I + \theta'_1(\boldsymbol {L\^{sym}}-I)x\\ \&=\&\theta ( D\^{-\frac{1}{2}}AD\^{-\frac{1}{2}}+I)x\\ \&=\&\theta (\tilde D\^{-\frac{1}{2}}\tilde A\tilde D\^{-\frac{1}{2}})x \end{eqnarray} \\\$

其中 \$\tilde A=A+I, \tilde D_{ii}=\sum {}_jA_{ij}\$ ,值得注意的是,这里的 \$\theta\$ 是一个标量。我们将: \$\theta\in \mathbb R\longrightarrow\Theta\in \mathbb R\^{F\times D}\$ , \$F,D\$ 分别表示输入输出的通道数。网络层与层时间的传递公式可以表示为: \$X\^{l+1}=\sigma((\tilde D\^{-\frac{1}{2}}\tilde A\tilde D\^{-\frac{1}{2}})X\^{l}\Theta\^l) \\\$ 在这个公式中,结合上一篇文章图表示学习极简教程,我们可以看出这个模型是对邻居结点的聚合(1-hop),当网络加深到K层的时候就会将聚合关系扩充到K跳。

8 GCN——一个低通滤波器

8.1 为什么叫它低通滤波器?

我们有 \$\widetilde { \boldsymbol { L\^{sym}}}=I-\tilde D\^{-\frac{1}{2}}L\tilde D\^{-\frac{1}{2}}=I-\tilde L_s\$ (这里其实有一点不太严谨的地方,不影响阅读,详细可参考一下从 Graph Convolution Networks (GCN) 谈起)。我们知道 \$\tilde L_s=U\tilde \Lambda U\^T\$ ,特征值的范围是0\~2。所以有: \$\widetilde { \boldsymbol { L\^{sym}}}=I-\tilde L_s=I-U\tilde \Lambda U\^T=I-\tilde L_s=U(I- \tilde \Lambda) U\^T\\\$ 可以看出,它的特征值范围为 \$(-1,1)\$ 。在信号与系统中,我们可以将信号转换到频域,通过频率响应函数滤波,再将信号转换到时域完成滤波的操作。这里的频率响应函数为 \$(I- \tilde \Lambda)\in (-1,1)\$ 。不难看出,它对信号进行了低通滤波。

8.2 GCN的大问题——Over Smoothing

根据实验,我们的GCN一直无法像CNN那样将网络做深,很大的一个原因就是过平滑(Over smoothing)。那么这种现象为什么会产生?

在GCN堆叠 \$k\$ 层的过程中,矩阵 \$\widetilde { \boldsymbol { L\^{sym}}}\$ 被乘了 \$k\$ 次。我们看看它展开会是什么样子:

\$\begin{eqnarray} \widetilde { \boldsymbol { L\^{sym}}}\^k\&=\&(I-\tilde L_s)\^k\\ \&=\&U(I- \tilde \Lambda)\^k U\^T\\ \&=\&U\:diag((1- \tilde \lambda_1)\^k,(1- \tilde \lambda_2)\^k,…,(1- \tilde \lambda_n)\^k)\: U\^T \end{eqnarray}\\\$

其中的 \$(1- \tilde \lambda_:)\^k\$ 只有在当 \$\tilde \lambda_:=0\$ 时,有 \$(1-\tilde \lambda_:)\^k\equiv1\$ 。其余情况下 \$(1-\tilde \lambda_:)\^k\$ 绝对值都不超过1。所以有: \$\lim_{k\to +\infty} (1-\tilde \lambda_:)\^k=0 \\\$

这时:

\$\begin{eqnarray} \lim_{k\to +\infty}\widetilde { \boldsymbol { L\^{sym}}}x \&=\&U\:diag(1,0,…,0)\: U\^Tx\\ \&=\&\hat x(1)·u_1 \:\:\:\:\:\:\:\:\:\:\:\:\:\:(\hat x(1)表示\hat x的第一个维度) \end{eqnarray} \\\$

这里有: \$u_1=D\^{\frac{1}{2}}·\boldsymbol 1\$ ( \$\boldsymbol 1\$ 表示全1向量)。如果在往下乘,会出现一项:

\$\begin{eqnarray} u_1\&=\&\tilde L_sD\^{\frac{1}{2}}·\boldsymbol 1\\ \&=\&\tilde D\^{-\frac{1}{2}}L\tilde D\^{-\frac{1}{2}}D\^{\frac{1}{2}}·\boldsymbol 1\\ \&=\&\tilde D\^{-\frac{1}{2}}L\boldsymbol 1=\tilde D\^{-\frac{1}{2}}\boldsymbol 0=\boldsymbol 0\ \end{eqnarray}\\\$

信号在往下乘的时候就会出现处处相等的情况,所有的结点特征就会趋于一致,过平滑由此产生。

另外,有一种更为容易理解的方法。一层的GCN是对一阶邻居信息的聚合,k层对应的就是k-hop。相信大家听过六度空间理论,几乎每一个结点的聚合都可以做到很快就把几乎全图进行覆盖。

9 一些很优质的参考资料

【papers】:

联系我:Data_LH_ChenAToutlook.com.(AT改为\@) 炼丹时间半年多,初涉该领域,如有理解不当或错误的地方欢迎指正。

大白

成为第一个点赞的人吧 :bowtie:
回复数量: 0
暂无回复~
您需要登陆以后才能留下评论!