Press "Enter" to skip to content

从源头探讨 GCN 的行文思路

本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.

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

 

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

 

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

 

PageRank

 

基本思想

 

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 个节点的特征向量是如何更新的):

 

 

可以发现 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 机制可以被描述为以下三部分:

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  为训练参数。

从 Attention 角度理解 GCN

 

结合GCN

 

观察 GCN 中的卷积公式 ,其中 X 为图中每个节点的特征向量, A 为图的邻接矩阵, 为度矩阵, 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 是一种用于图的聚类算法。图上的聚类可以理解为图的割, 即将图划分为不同顶点集,使得顶点集之间的边权值和最小。 但是,这样的优化目标容易导致聚类后的到的簇很不均匀(为了最小化割边的权值,算法会只割一条边)。因此,我们需要对优化目标进行归一化,即在优化聚类目标的同时,需要保证每个顶点集差不多大。

Cut 和 Normalized Cut(NCut)

 

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

 

 

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

 

 

对目标函数进行化简:

 

 

令:

 

 

可得:

 

 

fij 代入化简后的目标函数,目标函数可以化简为:

 

 

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

 

 

约束为   F TDF =1

 

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

 

 

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

 

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

 

结合GCN

 

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

 

适用方向

 

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

 

频域特征变换

 

基本思想

 

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

频域信号描述了相邻顶点的特征差异

 

k 为顶点数量, 为邻接矩阵, f 为空域信号(即节点特征),相邻顶点的特征差异可以被量化为:

 

 

fij 代入化简后的目标函数,目标函数可以化简为对该式进行化简:

 

 

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

 

 

  F TF =1 ,由 Rayleigh quotient 可以知道,如果 R(A,x)=(x’Ax)/(x’x) ,那幺 R 的最小值为 A 的最小特征值,该值在 为特征值对应的特征向量时取到;那幺 R 的最大值为 A 的最大特征值,该值在 x 为特征值对应的特征向量时取到。

 

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

 

因而,图傅立叶变换可以定义为:

 

 

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

图上的频域分解

 

结合GCN

 

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

 

适用方向

 

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

 

后记

 

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

 

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

Be First to Comment

发表评论

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