张智作者

从源头探讨 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 个 keyKi 对应的 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 为邻接矩阵。最小化上式即最小化:

约束为  FTDF =1


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

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


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


结合GCN

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

适用方向

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

频域特征变换

基本思想

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

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

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

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

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

 FTF =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-1LD-1 (即对称归一化的拉普拉斯矩阵),并使用训练参数对其进行了变换。从而,GCN 具有了图上的频域叠加、平移和卷积能力。

适用方向

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

后记

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

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

极验
极验

极验是全球顶尖的交互安全技术服务商,于2012年在武汉成立。全球首创 “行为式验证技术” ,利用生物特征与人工智能技术解决交互安全问题,为企业抵御恶意攻击防止资产损失提供一站式解决方案。

理论图神经网络逻辑回归收敛权重
3
相关数据
权重技术

线性模型中特征的系数,或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0,则相应的特征对模型来说没有任何贡献。

相关分析技术

相关分析就是对总体中确实具有联系的标志进行分析,其主体是对总体中具有因果关系标志的分析。它是描述客观事物相互间关系的密切程度并用适当的统计指标表示出来的过程。在一段时期内出生率随经济水平上升而上升,这说明两指标间是正相关关系;而在另一时期,随着经济水平进一步发展,出现出生率下降的现象,两指标间就是负相关关系。

参数技术

在数学和统计学裡,参数(英语:parameter)是使用通用变量来建立函数和变量之间关系(当这种关系很难用方程来阐述时)的一个数量。

收敛技术

在数学,计算机科学和逻辑学中,收敛指的是不同的变换序列在有限的时间内达到一个结论(变换终止),并且得出的结论是独立于达到它的路径(他们是融合的)。 通俗来说,收敛通常是指在训练期间达到的一种状态,即经过一定次数的迭代之后,训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说,如果采用当前数据进行额外的训练将无法改进模型,模型即达到收敛状态。在深度学习中,损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变,暂时形成收敛的假象。

人脸识别技术

广义的人脸识别实际包括构建人脸识别系统的一系列相关技术,包括人脸图像采集、人脸定位、人脸识别预处理、身份确认以及身份查找等;而狭义的人脸识别特指通过人脸进行身份确认或者身份查找的技术或系统。 人脸识别是一项热门的计算机技术研究领域,它属于生物特征识别技术,是对生物体(一般特指人)本身的生物特征来区分生物体个体。

计算机视觉技术

计算机视觉(CV)是指机器感知环境的能力。这一技术类别中的经典任务有图像形成、图像处理、图像提取和图像的三维推理。目标识别和面部识别也是很重要的研究领域。

推荐系统技术

推荐系统(RS)主要是指应用协同智能(collaborative intelligence)做推荐的技术。推荐系统的两大主流类型是基于内容的推荐系统和协同过滤(Collaborative Filtering)。另外还有基于知识的推荐系统(包括基于本体和基于案例的推荐系统)是一类特殊的推荐系统,这类系统更加注重知识表征和推理。

映射技术

映射指的是具有某种特殊结构的函数,或泛指类函数思想的范畴论中的态射。 逻辑和图论中也有一些不太常规的用法。其数学定义为:两个非空集合A与B间存在着对应关系f,而且对于A中的每一个元素x,B中总有有唯一的一个元素y与它对应,就这种对应为从A到B的映射,记作f:A→B。其中,y称为元素x在映射f下的象,记作:y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域,记作f(A)。同样的,在机器学习中,映射就是输入与输出之间的对应关系。

流形学习技术

流形学习(manifold learning)是机器学习、模式识别中的一种方法,在维数约简方面具有广泛的应用。它的主要思想是将高维的数据映射到低维,使该低维的数据能够反映原高维数据的某些本质结构特征。流形学习的前提是有一种假设,即某些高维数据,实际是一种低维的流形结构嵌入在高维空间中。流形学习的目的是将其映射回低维空间中,揭示其本质。

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式,所以目标函数就是设计变量的函数,是一个标量。从工程意义讲,目标函数是系统的性能标准,比如,一个结构的最轻重量、最低造价、最合理形式;一件产品的最短生产时间、最小能量消耗;一个实验的最佳配方等等,建立目标函数的过程就是寻找设计变量与目标的关系的过程,目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

降维技术

降维算法是将 p+1 个系数的问题简化为 M+1 个系数的问题,其中 M<p。算法执行包括计算变量的 M 个不同线性组合或投射(projection)。然后这 M 个投射作为预测器通过最小二乘法拟合一个线性回归模型。两个主要的方法是主成分回归(principal component regression)和偏最小二乘法(partial least squares)。

查询技术

一般来说,查询是询问的一种形式。它在不同的学科里涵义有所不同。在信息检索领域,查询指的是数据库和信息系统对信息检索的精确要求

信号处理技术

信号处理涉及到信号的分析、合成和修改。信号被宽泛地定义为传递“关于某种现象的行为或属性的信息(如声音、图像和生物测量)”的函数。例如,信号处理技术用于提高信号传输的保真度、存储效率和主观质量,并在测量信号中强调或检测感兴趣的组件。我们熟悉的语音、图像都可以看做是一种信号形式。因此,对于语音、图像的增强、降噪、识别等等操作本质上都是信号处理。

自然语言处理技术

自然语言处理(英语:natural language processing,缩写作 NLP)是人工智能和语言学领域的分支学科。此领域探讨如何处理及运用自然语言;自然语言认知则是指让电脑“懂”人类的语言。自然语言生成系统把计算机数据转化为自然语言。自然语言理解系统把自然语言转化为计算机程序更易于处理的形式。

信息抽取技术

信息/数据抽取是指从非结构化或半结构化文档中提取结构化信息的技术。信息抽取有两部分:命名实体识别(目标是识别和分类真实世界里的知名实体)和关系提取(目标是提取实体之间的语义关系)。概率模型/分类器可以帮助实现这些任务。

聚类技术

将物理或抽象对象的集合分成由类似的对象组成的多个类的过程被称为聚类。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对象彼此相似,与其他簇中的对象相异。“物以类聚,人以群分”,在自然科学和社会科学中,存在着大量的分类问题。聚类分析又称群分析,它是研究(样品或指标)分类问题的一种统计分析方法。聚类分析起源于分类学,但是聚类不等于分类。聚类与分类的不同在于,聚类所要求划分的类是未知的。聚类分析内容非常丰富,有系统聚类法、有序样品聚类法、动态聚类法、模糊聚类法、图论聚类法、聚类预报法等。

知乎机构

知乎作为中文互联网知名知识内容平台,致力于构建一个人人都可接入的知识分享网络,让人们便捷地与世界分享知识、经验和见解,高效获得可信赖的解答。 目前,知乎已经覆盖「问答」社区、一站式知识服务平台「知乎大学」、短内容分享功能「想法」等一系列产品和服务,并建立了包括音频、视频在内的多元媒介形式。截止 2018 年 8 月底,知乎用户数已突破 2 亿,回答数超过 1.2 亿。未来,知乎进一步加大对 AI 技术和应用的投入,构建一个由 AI 驱动的智能社区,让知识普惠每一个人。

https://www.zhihu.com
仿射变换技术

仿射变换,又称仿射映射,是指在几何中,一个向量空间进行一次线性变换并接上一个平移,变换为另一个向量空间。 一个对向量平移,与旋转放大缩小的仿射映射为 上式在齐次坐标上,等价于下面的式子 在分形的研究里,收缩平移仿射映射可以制造制具有自相似性的分形

暂无评论
暂无评论~