GCN 为什么是低通滤波器？具体在干啥？

本文脉络

• 卷积、滤波、频率的直观理解

• 基于"基"的信号合成与分解

• 图网络的 谱分析

• 图卷积有什么问题

• ChebNet 与 GCN

01

—

卷积、滤波、频率的直观理解

03

—

图网络的 谱分析

在介绍图卷积之前，还得从普通卷积讲起， 首先 介绍一维连 续卷积的定义，f 和 g 的卷积定义如下，附上几乎每个老师上课都用过的动图：

实际应用中，我们更多的是处理二维离散信号，二维离散卷积定义如下：

简单概括卷积过程就是：旋转、平移、相乘、求和。可以看出卷积运算是很复杂的，所以有没有办法不去直接求卷积呢？

这里就要 介绍一个 前面提过的 定理， 卷积定理 ： 函数卷积的傅里叶变换等于函数傅里叶变换的乘积 。可见对函数傅里叶变换后的乘积在进行傅里叶逆变换就可以得到原始函数的卷积。

上式中  代表傅里叶变换   表示傅里叶逆变换。

回到图网络上，时域的卷积不仅计算难，连定义一个卷积核都难。因此也是依靠卷积定理，在频域来做些骚操作，下图所示：

现在我们目标就是定义好 图傅里叶变换 和逆变换即可！

类比普通的傅里叶变换就是求信号在   上的投影，那么图傅里叶变换也是求信号 x 在一组正交基   上 的投影。   图傅里叶变换如下：

那么上图中的这组基   从哪里来呢？分析得到的特征值   又是什么意思呢?

关于 ，特征值/特征向量听名字就知道很有用是不是，都叫特征了，肯定是能代表信号的属性的。 学过线性代数的都很熟悉，就不啰嗦了。直接来说这组傅里叶基     怎么求。

先约定下关于图网络的符号表示。对于一个 graph 网络 G，那么可以用节点 V （N 个），和边 E 来表示。对于任意一个网络，可以得到2个矩阵A和D。邻接矩阵 A 的定义是表示如果2个节点有边关联则未1，否则未0. 度矩阵 D 的定义是该节点的度数（对角阵）。

有了 A 和 D，就可以计算出网络 G 的拉普拉斯矩阵：L = D-A。

网络的拉普拉斯矩阵 L 是一个对称的半正定矩阵，可以分解成 的形式。并且这里的     就是我们想要的傅里叶变换的基，     就是信号的特征频率。

到此，我们就可以用利用卷积定理和图傅里叶变换得到图卷积的解法了：

图信号 f 和 g 的图卷积，类比普通信号f 和 g 的普通卷积，形式是一样的。

参考第一小节的图片滤波，那么对于一个图信号 x，也是先做傅里叶变换到频域 ，然后在频域进行滤波即和同样傅里叶变换后的滤波器   进行乘积得到   ； 最后再傅里叶逆变换回去即得到时域得结果 y=     。

画成矩阵的形式就是下面这样：

为了更加直观一点，我们进一步变换一下，把前面介绍的拉普拉斯矩阵 L 再引入回来：

所以图卷积计算，相当于就是 拿拉普拉斯矩阵 L 的函数来对信号进行一个处理 ！这个函数的参数也就是我们的卷积核参数，模型需要学习的参数。这个处理会做些啥呢，和低通滤波器又有什么关系呢？

04

—

图卷积有什么问题

复用一个台大课程上具体的例子来说明下拉普拉斯矩阵 L 的函数在图 graph 上操作的过程。

上面定义了一个简单的图网络信号 f，共有4个节点，每个节点就一维数值。那么这个graph f 的度矩阵 D和邻接矩阵A，以及拉普拉斯矩阵 L 和对应的分解结果如上所示（上图矩阵 A 写错了）。

用最简单的拉普拉斯 L 的函数 来作用 到这个 图 f 上，得到结果 Lf 是如下：

仔细看上面的计算过程，当计算 Lf 的第一个值 a 时， a=(4-2) + (4-4); 可以从参与计算的数值（黄色框、红色框、军绿色框中数值）看出，第一项(4-2) 中的4代表 v0节点的信号大小4，其中的2代表 v1的信号大小；第二项（4-4）中的第一个4代表 v0节点信号大小，第二个4代表 v2节点信号大小。之所以是有2项是因为 v0节点的度=2，即有2个邻居（v1和 v2）。

有没有总结出规律！当用 L 作用到图 f 上时，某种程度上可以看作是计算节点信号与自己邻边节点信号的差值。 这个差值的大小变化程度是不是就类似于第一小节说的图片像素的差距，差距变化越快就是高频，反之则代表低频 。

再思考一个问题，上面计算过程发现，当我们计算第一个节点 v0时，只用到了邻居 v1和 v2的值，没有用到 v3，因为 v0和 v3直接没有边。下图矩阵直观的看出当 时，这个函数作用的 f 上， 求 y第一行 的2时，由于 L[0][3]=0,代表和 v3节点没有邻边，所以用不到 v3节点的信息。

这样肯定是有信息损失的，相当于我们每次更新一个节点时，只用了1阶邻居节点的信息。如果我们的函数再复杂点呢，比如取2次方 。

此时可以看出L 的函数包含其2次方项后，矩阵中都是非0项，则更新节点 v0时，v3节点的信息也会被用到。因为 v3和 v0虽然不是直接邻居，但是他们存在着2阶邻边，所以当   时，更新某一个节点时会用到其所有2阶邻居的信息。

讲到这里就引出当前 graph 卷积的几个问题。

1）卷积函数   中包含 L 的M次方，更新节点时就会用到它的 M 阶邻居。 比如   时，其中就包含了 N 次方 ，那么 更新任何一个节点时，都需要用到所有节点信息，这个显然是不合理 也不现实的 ，N 很大时没法算了 ，这种性质称为 非localize，Nonlocal 的。对比图像卷积，每个值就只和卷积核大小内的像素有关。所以graph 卷积这样不具备 localize 特性。

2）前面提到学习图卷积的参数就是   ， 这个参数个数是 N ，即和图的节点个数有关，每增加一个节点，这个参数就要变化。

3）需要对 L 进行矩阵分解，大矩阵的矩阵分解计算量是非常庞大的。

05

—

ChebNet 与 GCN

讨论上面几个问题，就必须要提 ChebNet 这个里程碑工作了。

ChebNet 简单解释就是用切比雪夫多项式拟合 L 的 K 次多项式作为卷积函数。如上图公式所示，这样设计后，每个节点更新就最多和 K 阶邻居有关，实现了 localize。 同时参数个数也定死是 K 个，不会随着 graph 的变化而变化。拟合的过程如下：

最终得到的卷积公式就是上式y的计算过程，这样处理后，计算量就下来了，从 O(N*N) 变成 O(KE)：

原理有点类似下面的函数求问题(2)时用变换后的多项式分解来求解会简化计算。（这个变换我也没深入推导过）

用了  ChebNet  后 ，上一小节的 3个问题就都解决了。 使用 广泛的 GCN 就是  ChebNet   K= 1时 的一阶近似 。

上面推导依赖几个思路：1）最大的特征值 比2略小，约等于2.  2） 这里的拉普拉斯矩阵 L 可以正则化为：

3）参数 的关系 是人为 设定 的，不是理论 。 renormalization trick 也是作者这么定义的一个计算方法。其中  ， A相当于加了一次自己。

同时可以看到上面的特征值范围是[-1,1],那么在频率进行滤波时，即频率响应函数的范围也是在这范围内，属于低频段，所以 GCN 可以看作是一个低通滤波器。

经过上图变换后得到了最终网络下一层的输出    的计算方法 。如果觉得这个式子不好理解，可以换成下面的形式：

就是讲输入特征 x 经过一次变化 W 后，再将所有邻居（包括自己）的这些值求和相加，再求均值，最后经过一次"激活"函数 f，得到输出。这个式子理解起来就很传统了。

GCN 的效果如何，存在什么问题？关于这个，网上有很多资料，我就不介绍了，简单说即是经过多层后，有 over-smoothing 问题。效果的话，一般般吧，至少在很多图片任务上，效果非常差。在实际工作中，很少会直接用这么单纯的 GCN 的，应用较广的还是graphsage、gat 这些。