从源头探讨 GCN 的行文思路

今年，IJCAI、CVPR、MM 上 Graph 相关的论文已经呈现井喷式的增长。相信领域内的小伙伴也都感受到了不同程度的压力，加紧撰写或是修改论文。在相关文献中，有些文章行云流水，insight 和 GCN 的特点结合的很棒；也有些文章生硬牵强，给人一种不太合理的感觉。

在顺藤摸瓜梳理 GCN 的分析视角的过程中，有四个历史悠久的研究方向与 GCN 的思路异曲同工。虽然他们的光辉暂时被 GCN 掩盖，但是在优秀的 GCN 论文中，他们分析思路仍被广泛使用。

下面，我们将从简单到困难介绍这四种研究方向的 基本思想、从该视角对 GCN 的理解，以及适用的领域。希望给正在写论文和找不到应用方向的小伙伴一些帮助。

PageRank

基本思想

PageRank 是一种用于量化网络中网页重要程度的算法。在 PageRank 诞生前，人们通常使用指向一个网页的网页数量来衡量该网页的重要程度（指向一个网页的网页越多，人们访问该网页的概率越大）。但是这种做法只考虑了链接（一个网页对另一个网页的指向）的数量而忽视了链接的质量，即所有链接都是同等重要的。

一个大流量网页的链接和两个小流量网页的链接

PageRank 解决了重要性的量化和累积问题，赋予了大流量网页更高的权重 。PageRank 的做法是：

1. 假设世界上总共有 4 个网页，则在不考虑链接时每个网页被访问的概率为  1/4 ，因此将每个网页的重要程度初始化为  1/4 。将 A 网页的重要程度用  PR(A)  表示，则  PR(A)=1/4 ;

2. 假设 A 网页共指向了 L(A) 个网页，则每个指向的重要程度（被使用的概率）为 PR(A) / L(A);

3. D 页面的重要程度可以表示为指向 D 的链接的重要程度之和，即使用下面的公式更新 D页面的重要程度：

4. 根据所有页面新的重要程度，重复第 2、3 步，直至 收敛 （更新前的  PR(D) 与更新后的 PR(D) 的差异小与某个设定的阈值）。

结合GCN

考虑 GCN 中的卷积公式 ，其中 X 为图中每个节点的特征向量， A 为图的邻接矩阵， D 为度矩阵， H 为训练 参数 （推导过程中省略）。观察 Conv(X) 第 i 行的值（即图中第 i 个节点的特征向量是如何更新的）：

可以发现 GCN 和 PageRank 的思路大同小异，只是链接的 权重 PR(A) 被替换为了边的权值 Aij  ，链接数量 L(A) 被替换为了相邻边的权值之和  。 但两者的本质都是通过边的权值计算节点的重要程度，并通过迭代（GCN 里是多层卷积）累积重要程度直至收敛 。

适用方向

PageRank 方向的研究在 大规模 Network 的分析和处理中积累了大量的研究经验，因此在大规模关系网络的分析和处理中，往往可以找到 PageRank 的 相关分析 进行解释。例如，在社交网络、 推荐系统 、团伙发现等任务中，往往可以 强调 User 的重要性程度不同（关键用户、团伙头目等）。

Attention —— 查询 重要性

基本思想

Attention 是一种能够进行（一般用于长上下文或状态集合中） 信息抽取 的网络结构。Attention 的实质是 使用查询 条件（query）在一个包含大量键值对（key-value）的字典中，匹配符合要求的 key 并获得对应的 value 的过程。令 query 为 Q ，第  i 个 key Ki 对应的 value 为 Vi  ，Attention 机制可以被描述为以下三部分：

1. 计算 query 与所有 key 的相似度，得到评分。以下四种方法都较为常见：

2. 使用 Softmax 对评分进行归一化：

3. 将归一化后的评分与 value 加权求和得到 Attention 的结果：

在 自然语言处理 任务中，key 和 value 通常相同，即都为输入的一系列词向量，query 为当前状态。这样，网络就可以像人类一样，忽略不想关注的部分，而从需要关注的词向量提取信息。

除了这种静态的 Attention 外，Self-Attention 和 Transformer 也被广泛使用在 自然语言处理 和 计算机视觉 任务中。在 Self-Attention 中，原始向量到 query、key、value 的 映射 是可以通过反向传播学习的，因此不再需要我们手动定义 query 与 key 的相似度的计算方法。

上文中的操作可以替换为：

其中， Wq   、 Wk   和 Wv  为训练 参数 。

结合GCN

观察 GCN 中的卷积公式  ，其中 X 为图中每个节点的特征向量， A 为图的邻接矩阵， D 为度矩阵， H 为训练 参数 （推导过程中省略）。其实，这个过程可以理解为， 通过邻接矩阵 A 定义了当前节点与周围节点的相似度评分，即 。使用度矩阵（当前节点所有相邻边的权值之和）的倒数 D-1 对评分进行了归一化。最后通过乘 X 完成了对 value 的提取。

在此基础上，也有同学提出了 Graph Transformer 进行 Self-Attention。

1. 对于当前节点 i 对应的特征向量 xi 和相邻节点 j 对应的特征向量 xj  ，他们的相似度评分为：

2. 使用 Softmax 对评分进行归一化：

3. 将归一化后的评分与 value 加权求和得到 Attention 的结果：

适用方向

Attention 方向的研究在 计算机视觉 和自然语言处理 等方向都得到了长足发展。以 计算机视觉 领域为例子，例如，Attention 可以分为 对 channel 和对 feature map 的 attention。feature map 中包含 ROI，而 channel 可以代表颜色、深度、轮廓、时间序列等信息，这些信息都可以作为 Graph 中的 Node 进行 Attention。（图像标注、视频内容分析等）。

Spectral Clustering 

基本思想

Spectral Clustering 是一种用于图的 聚类 算法。图上的 聚类 可以理解为图的割， 即将图划分为不同顶点集，使得顶点集之间的边权值和最小。但是，这样的优化目标容易导致 聚类 后的到的簇很不均匀（为了最小化割边的权值，算法会只割一条边）。因此，我们需要对优化目标进行归一化，即在优化 聚类 目标的同时，需要保证每个顶点集差不多大。

假设我们将图 A 划分为 k 个部分 ( A1 , A2 ,..., Ak ) ，  表示顶点集 Ai 和其他顶点集之间的边的权值和。优化目标『将图划分为不同顶点集，使得顶点集之间的边权值和最小』可以表示为：

通常，我们使用  vol( Ai) 即顶点集 Ai 中顶点的度之和度量顶点集的大小（比起顶点数量，我们更关注边的数量），来对优化目标进行归一化：

对 目标函数 进行化简：

令：

可得：

将 fij 代入化简后的 目标函数 ， 目标函数 可以化简为：

其中， L=D-W 为拉普拉斯矩阵，其中 D 为度矩阵， W 为邻接矩阵。最小化上式即最小化：

约束为   FTDF =1。

该式可以转化为瑞立熵公式，我们令 F=D-1/2G ，上式可以转化为：

由 Rayleigh quotient 可以知道，如果 R(A,x)=(xAx)/(xx) ，那么 R 的最小值为 A 的最小特征值，该值在  x 为特征值对应的特征向量时取到。

也就是说，我们只需要求   D-1/2L D-1/2 的特征值并选择最小的 k 个特征值对应的特征向量，（往往无法直接通过维数约简获得结果，需要再对其进行一次 KMeans 聚类 ）就可以得到 聚类 的结果了。

结合GCN

Spectral Clustering 的实质是使用拉普拉斯特征 映射 在 降维 的同时保留局部特征（原本距离较近的特征点在特征 映射 之后距离仍然近，原本距离较远的特征点在特征 映射 之后仍然远），在此基础上使用 聚类 算法（如KMeans）对 降维 后的特征点进行 聚类 。 D-1/2L D-1/2  的特征向量具有保留局部特征的作用。 因此，GCN 的卷积公式 D-1/2LD-1/2XH 可以近似看做通过 仿射变换 求特征向量的过程。

适用方向

Laplacian Eigenmaps 是 流形学习 的研究内容之一，因此在流行学习任务上（例如 人脸识别 中人脸特征随光照、方向等因素连续变化）往往可以找到 LLP、ISOMAP 的 相关分析 进行解释。因此，如果能够确定数据集的分布处于一个流形上，或是需要根据相似度手动构建 Graph 时，该研究方向是非常值得借鉴的，研究过程中可以使用可视化等方法佐证自己的理论（流形的可视化较为简单）。

频域特征变换

基本思想

与图像 信号处理 中的空域信号（又叫像素域，描述像素的特征，可以对像素进行叠加）和频域信号（描述空域的变化，通过傅立叶变换得到）相似，图 信号处理 中也有顶点域信号和频域。其中顶点域信号对应图中每个顶点的特征（例如社交网络中的年龄、爱好等），频域信号对应另一种信号分析维度（图的傅立叶变换基），描述了相邻顶点的特征差异。

令 k 为顶点数量， w 为邻接矩阵， f 为空域信号（即节点特征），相邻顶点的特征差异可以被量化为：

将 fij 代入化简后的 目标函数 ， 目标函数 可以化简为对该式进行化简：

其中， L=D-W 为拉普拉斯矩阵，其中 D为度矩阵， W 为邻接矩阵。上式可以转化为：

令   FTF =1 ，由 Rayleigh quotient 可以知道，如果 R(A,x)=(xAx)/(xx)  ，那么 R 的最小值为 A 的最小特征值，该值在 x 为特征值对应的特征向量时取到；那么 R 的最大值为 A 的最大特征值，该值在 x 为特征值对应的特征向量时取到。

也就是说，我们只需要求 L 的特征值 λ，较大的 λ 对应  较大，即空域信号变化较大的高频信号；较小的 λ 对应   较大，即空域信号变化较小的低频信号。

因而，图傅立叶变换可以定义为：

其中， u(t)(i) 为 L 的第 t 个特征向量的第 i 个元素， u*(t)(i) 为其共轭。可以发现， 图傅立叶变换只是将傅立叶变换中的算子   替换为了 L 的特征向量 ut  。二者都包含了明显的频率信息，在低频时震荡较慢（低），高频时震荡较快（变化率高）。

结合GCN

考虑 GCN 中的卷积公式   ，其中 X 为图中每个节点的特征向量， H 为训练 参数 。 其实是将频率信息 L 进行了对称归一化得到   D-1L D-1 （即对称归一化的拉普拉斯矩阵），并使用训练 参数 对其进行了变换。从而，GCN 具有了图上的频域叠加、平移和卷积能力。

适用方向

在四种研究方向中，频谱理论最为艰涩但是也最 make sense。约简后的频谱操作即目前适用最为广泛的 GCN，相信在未来该领域也仍是研究图卷积算子的必经之路。如果实在找不到 GCN 与当前任务的结合点，也可以直接使用该理论引出图卷积的公式（这样的顶会论文也不少）。

后记

本文只探讨了几个主要的图研究方向的视角，其实万法归一，没有提及到的很多领域也有着相似出色的工作，比如 Random Walk 等。在学习过程中希望大家能一起举一反三啦。

另外，近期准备着写一些 Vanilla PyTorch 实现图卷积的最佳实践教程，就不怎么玩 知乎 啦～感兴趣的同学可以关注我的 Github: tczhangzhi。此举并不是妄想重新造像 PyG 或者 DGL 一样的轮子，而是在参考了各位同学和开源库的实现后发现，Vanilla PyTorch 实现 GCN 可以让我们的代码更为简洁和灵活。因此希望总结一些最佳实践，一方面向大佬致敬，另一方面也为同学们的研究提供方便。