持续创作,加速成长!这是我参与「掘金日新计划 · 10 月更文挑战」的第23天,机器学习指标:查准率、召回率等
注意力机制(Attention Mechanism)
编码器阶段,LSTM对整句话进行编码,得到一个中间编码C。注意力机制,则是对针对不同的单词采用生成不同的中间编码C1,C2等。
GNN的变体与框架
GCN的出现带动了将神经网络技术运用到图数据的学习任务中去的一大类方法,为了该处一个涵盖更广范围的定义,一般统称这类方法为图神经网络,即Graph Nerual Networks(GNN)。
GCN本质上就是一个迭代式地聚合邻居的过程,这启发了一大类模型对于这种聚合操作的重新设计,大大增强了GNN对于图数据的适应性。基于这些设计的解构,一些GNN的通用表达框架被相继提出。
这些变体与框架都是为了更好地表示节点的特征(包括节点的属性信息和结构信息)。
GraphSAGE(Graph SAmple and aggreGatE)图采样和聚合
GraphSAGE可以看作是GCN的一个改进。
GCN只能学习图中已有节点的表示,换句话说,GCN是整张图的节点一起训练的,用到了拉普拉斯矩阵,对于没有在训练过程中出现过的节点,GCN无法表示。节点的表示相对固定,当添加新的节点时需要对全图进行重新训练才能得到每个节点的新的表示。
思路转换:既然新增的节点,一定会改变原有节点的表示,那么为何一定要得到每个节点的一个固定的表示呢?何不直接学习一种节点的表示方法。这样不管graph怎么改变,都可以很容易地得到新的表示。
对于GCN的问题,GraphSAGE采用采样邻居和聚合邻居的方法进行改进。
先决知识
归纳学习(Inductive Learning):归纳学习是指在训练阶段见不到的数据(在图数据中,可以指新节点,也可以指新的图)直接进行预测而不需要重新训练的方法。
转导学习(Transductive Learning):转导学习是指所有的数据在训练阶段都可以拿到,学习过程是作用在这个固定的数据上的,一旦数据发生变化,需要进行重新学习训练。典型的比如图形上的随机游走算法,一旦图数据发生改变,所有节点的表示学习都需要重新进行。
参考:Transductive Learning和Inductive Learning区别
采样邻居
在GCN模型中,训练方式是一种全图方式,即一轮迭代,所有节点样本的损失只会贡献一次梯度数据,无法进行小批量更新,效率较低。且在很多实际业务场景中,图的规模往往十分巨大。
GCN存在问题:
-
子图的节点数存在呈指数级增长的问题。
-
真实世界中图数据节点的度往往呈现幂律分布,加上节点数呈指数级增长,计算代价非常高。
GraphSAGE从聚合邻居的操作出发,对邻居进行随机采样来控制实际运算时节点k阶子图的数据规模,在此基础上对采样的子图进行随机组合来完成小批量市的训练。
GraphSAGE采样:
设每个节点在第k层的邻居采样倍率为S_k(该参数是GraphSAGE的超参数,由用户自行设计和调节),即每个节点采样的一阶邻居的个数不超过S_k,那么对于任意一个中心节点的表达计算,所涉及的总节点数将在阶乘级别以下。
例如对于一个两层的模型来说,S1=3,S2=2,则总的节点数不超过1+3+3*2=10个,远远小于采用GCN采样邻居节点的个数,降低计算量。这里对节点采样,GraphSAGE选择了均匀分布,可以根据实际选择其它形式的分布来代替均匀分布。
聚合邻居
聚合操作需要满足的条件:
-
聚合操作必须要对聚合节点的数量做到自适应,不管节点的邻居数量怎么变化,聚合操作后的输出的维度必须是一致的,一般是一个统一长度的向量。
-
聚合操作对聚合节点具有排列不变性,即无论邻居节点的排列顺序如何,聚合操作的输出结果是一样的。
常用的简单聚合操作算子:
(1)**平均聚合:**先对邻居embedding中每个维度取平均,然后与目标节点embedding拼接后进行非线性转换。v是中心节点,u是邻居节点,h是节点特征,W是聚合操作需要学习的参数。
(2)**归纳式聚合:**直接对目标节点和所有邻居emebdding中每个维度取平均,后再非线性转换:
(3)**LSTM聚合:**LSTM函数不符合“排序不变量”的性质,需要先对邻居随机排序,然后将随机的邻居序列embedding作为LSTM输入。
(4)**Pooling聚合器:**先对每个邻居节点上一层embedding进行非线性转换(等价单个全连接层,每一维度代表在某方面的表示(如信用情况)),再按维度应用 max/mean pooling,捕获邻居集上在某方面的突出的/综合的表现 以此表示目标节点embedding。
GraphSAGE算法过程
算法思路:先将小批集合B内的中心节点聚合所要涉及的k阶子图一次性全部遍历出来,然后在这些节点上进行K次聚合操作的迭代计算。
1、首先作者给出了不引入minibatch的训练算法:
伪代码:
算法很简单,就是普通GCN节点聚合传播的算法。第5行作者采用了前面提到的平均聚合方式,并采用了拼接处理。第7行对节点的表示进行了归一化(单位向量)。另外可以看出,为了进行inductive learning,作者不再是学习每个节点的表示,而是学习一系列的聚合函数(Aggregate_k),并且节点的输入不再是one-hot,而是节点的特征表示向量x_v。这样对于未知节点,可以把它的节点特征和它的邻居节点通过学习好的聚合函数进行聚合,就可以得到未知节点的表示。不引入minibatch每次更新参数都要在整张图上进行计算,耗时耗空间。
2、引入minibatch的训练算法:
伪代码:
这里是在一个batch中进行参数更新的操作,B是需要更新的一批节点集合。在每次batch更新之前,首先需要找出此次batch更新需要用到的节点集合。1-7行描述了这一过程,因为要聚合K次,所以需要K+1个节点结合,B_0~B_k,B_k−1是B_k和对B_k中节点的邻居节点采样得到的并集(3-5行)。求节点的邻居节点并不是利用全部的邻居节点,而是对邻居节点进行了采样,采样的节点数固定,如果节点的邻居数大于采样数,则采用均匀不放回采样;否则采用均匀放回采样。
聚合过程如上图所示,伪代码中的8~15行是从底层到顶层进行聚合操作,第11行是调用聚合操作完成对每个节点邻居特征的整合输出,12行是将聚合后的邻居特征与中心节点上一层的特征进行拼接,然后送到一个单层网络里面得到中心节点新的特征向量,13行对节点的特征向量进行归一化处理,将所有节点的向量都统一到单位尺度上。对这3行操作迭代K次就完成了对B内所有节点特征向量的提取。
第K层是最顶层,1层是最底层,所以采样时是从第顶层到底层去找邻居节点,聚合时从底层到顶层逐层进行聚合。
GraphSAGE全程完全没有拉普拉斯矩阵的参与,每个节点的学习仅仅只与其K阶邻居有关,不需要考虑全图的结构信息。对于新出现的节点数据,只需要便利得到k阶子图,就可以带入模型进行预测,因为聚合函数已经学习到了。
小结
GCN学习得到的是每个节点固定的表示,需要全局节点参与到其中(运算的过程中用到了拉普拉斯矩阵),所以每次有新节点的时候就需要重新进行训练,得到新的所有节点的表示。
GraphSAGE学习得到的是一个聚合函数,通过这个聚合函数来获得节点的表示,即只需要中心节点的K阶子图就能得到该中心节点的表示,训练过程中不需要拉普拉斯矩阵的参与。所以,对于一个新的节点只需要知道该节点的邻居,然后通过聚合函数就能得到该节点的表示,不需要整张图参与到其中。
图注意力网络(Graph Attention Networks,GAT)
图注意力网络通过注意力机制来对邻居节点做聚合操作,实现了对不同邻居权重的自适应分配,从而大大提高了图神经网络模型的表达能力。
注意力机制
注意力机制的核心在于对给定信息进行权重分配,权重高的信息意味着需要系统进行重点加工。注意力机制的数学表达式如下图所示。
如图所示,Source是需要系统处理的信息源,Query代表某种条件或者先验信息,Attention Value是给定Query信息的条件下,通过注意力机制从Source中提取得到的信息。此时给定Target中的某个元素Query,通过计算Query和各个Key的相似性或者相关性,得到每个Key对应Value的权重系数,然后对Value进行加权求和,即得到了最终的Attention数值。所以本质上Attention机制是对Source中元素的Value值进行加权求和,而Query和Key用来计算对应Value的权重系数。注意力机制的定义如下:
聚焦的过程体现在权重系数的计算上,权重越大越聚焦于其对应的Value值上,即权重代表了信息的重要性,而Value是其对应的信息。
传统神经网络学习的参数,比如W是所有节点共享的参数,而注意力机制学习的权重是针对单个节点的,不同节点的权重是不同的。
图注意力层
根据注意力机制的三大要素:Query、Source、Attention Value,将Query设置为当前中心节点的特征向量,将Source设置为所有邻居的特征向量,将Attention Value设置为中心节点经过聚合操作后的新的向量。
定义如下:设图中任意节点 v_i 在第L层所对应的特征向量为 h_i,经过一个以注意力机制为核心的聚合操作后,输出的是每个节点新的特征向量 h_i‘ 。通常将这个操作称为图注意力层(Graph Attention Layer,GAL)。
假设中心节点为V_i,则邻居节点V_j到V_i的权重系数为:e_ij=a(Wh_i,Wh_j),W是该层节点特征变换的参数,a(·)是计算两个节点相关度的函数。原则上我们可以计算图中任意一个节点到节点V_i的权重系数,这里为了简化计算,将其限制在一阶邻居内。
注意力机制权重系数的计算公式如下:
按照注意力机制加权求和的思路,节点V_i新的特征向量为:
注意:所有邻居节点共享一个参数矩阵W
-
如果不使用注意力机制,那么对每一个邻居节点h的特征向量都采用相同的W相乘(或者其他计算),再进行激活更新得到新的节点特征,这时每个邻居节点对中心节点的贡献是相同的。
-
添加了注意力机制之后就是,虽然每一个邻居节点h的特征向量都是和同一个W相乘(或者是其他计算),但是每个节点又分别乘了一个不同的权重系数a,这时每个邻居节点对中心节点的贡献是不同的。
多头注意力层
进一步提升注意力层的表达能力,可以加入多头注意力机制(multi-head attention),即对节点调用K组相互独立的注意力机制,然后将输出的结果拼接在一起:
||表示拼接操作,**a_k_ij **是K组注意力机制计算出的权重系数,W_k是对应的学习参数。
多头注意力机制计算流程如下图所示
图注意力机制也保留了非常完整的局部性,也可以进行归纳学习。
R-GCN
知识图谱
一种典型的包含多种关系的图数据就是知识图谱(Knowledge Graph)。知识图谱是一种规模非常庞大的语义网络,其主要作用是描述通用或专用场景下实体间的关联关系,主要应用场景为搜多引擎、语音助手、智能问答等。
知识图谱构建所依赖的核心技术是信息抽取与知识构建。该技术旨在从大规模非结构化的自然语言文本中抽取结构化信息,决定了知识图谱可持续扩增的能力。
R-GCN
R-GCN基于GCN的邻居聚合操作,又增加了一个聚合关系的维度,使得节点的聚合操作变成一个双重聚合操作,核心公式如下:
GCN考虑的是同构图(节点和边的类型只有一种)建模,节点之间只存在一种关系,因此GCN只需要一组权重参数来对节点的特征进行变换。
R-GCN考虑的是异构图(节点或边的类型多于一种)建模,考量关系的因素对邻居进行分类操作:对于每一种关系的邻居引入不同的权重参数,分别对属于同一关系类型的邻居聚合之后,再进行一次总的聚合。过程如下图所示:
上图中先对同种关系的邻居进行单独聚合,这里考虑了关系的正反方向,同时对于自身加入了自连接的关系,将所有不同关系的邻居聚合之后,再进行一次总的聚合。
知识图谱中往往存在大量的关系,如果为每一组关系设计一组权重,那么R-GCN需要学习的参数量将十分庞大,因此提出了一种对W_r进行基分解(basic decomposition)的方案,即:
a_rb是W_r再V_b上的分解系数,B是超参数,控制着V_b的个数,通过上式W_r变成了一组基的线性加和。
GNN通用框架
所谓的通用框架就是对多种变体GNN网络结构的一般化总结。
消息传播神经网络(Message Passing Neural Network,MPNN)
通过消息传递机制对多种GNN模型做出了一般化总结。基本思路为:节点的表示向量都是通过消息传递函数M(Message)和更新函数U(Update)进行K轮消息传播机制迭代后得到的,消息传播过程如下:
h表示节点特征,e_ij表示边<v_i,v_j>上的特征向量,k次表示第k次消息传播。
MPNN计算示意图:
上图中并没有对边的表示向量进行迭代更新,如果有必要(比如边具有重要意义的时候)可以与节点一样,对边的向量始终维护一个状态向量。
MPNN的核心在于消息函数和更新函数,原则上可以把它设计成任意一种DNN模型。如下:
非局部神经网络(Non-Local Nerual Network,NLNN)
NLNN是对注意力机制的一般化总结,通过non-local操作将任意位置的输出响应计算为所有位置特征的加权和。通用的non-local如下:
i是输出位置的索引,j是枚举所有可能位置的索引。f(x_i,x_j)是i位置和j位置上元素之间的相关度函数,g(x_j)表示对输入x_j进行变换的变换函数,1/C(x)用于归一化。
NLNN的核心也在两个函数:f和g,通常使用线性变换函数作为函数g:g(x_j)=W_gh_j,W_g是需要学习的权重参数。
f通常选择:
-
内积:两个节点特征的内积
-
全连接:使用输出为一维标量的全连接层定义f
-
高斯函数
图网络(Craph Network,GN)
GN相较于MPNN和NLNN做出了更一般的总结。基本计算包含三个元素:节点状态 h_i,边的状态 e_ij,图的状态 u。并设计了3个更新函数φ、3个聚合函数ρ,具体如下:
GN的更新思路:由点更新边,边聚合更新点,点聚合与边聚合更新图,这里更新的时候还需要考虑上一轮自身的状态。
上述的更新步骤并不是一成不变的,可以从全局出发到每个节点,再到每条边。
另外全图状态u的初始值,可以看成是图的某种固有属性或者先验知识的编码向量。如果去除这个全图状态的维护,GN就退化成了一个维护边状态的的MPNN。
GN的更新过程如下:
图分类
图分类是一个重要的图层面的学习任务,图分类需要关注图数据的全局信息,包括图的结构信息和属性信息。
给定多张图,以及每张图的标签,图分类任务就是通过学习得出一个由图到相应标签的图分类模型,模型的重点在于如何通过学习得出一个优秀的全图表示向量。
和CNN类似,都需要对全局信息进行融合学习,CNN中通常采用层次化池化(Hierarchical Pooling)机制来逐渐提取全局信息。
基于全局池化的图分类
前文介绍的MPNN,除了为图中节点的表示学习提出了一般框架外,还设计了一个读出(readout)机制对经过K轮迭代的所有节点进行一次性聚合操作,从而输出图的全局表示:
与读出机制类似的一种做法是,引入一个与所有节点相连的虚拟节点,将全图的表示等价与这个虚拟节点的表示。
读出机制的缺点:
读出机制本质上是将数据看作一种平整且规则的结构数据,将所有的节点都等同看待,这样处理丢失了图数据里面丰富的结构信息。
从这个角度看,读出机制更适合对小图数据的学习。
-
一方面小图数据中的结构信息相对单一
-
一方面是因为经过K轮消息传播机制的迭代之后,图中各个节点的表达更加接近全局表达,此时读出机制能更好的提取全局信息
基于层次化池化的图分类
通常有三类:
-
基于图坍缩(Graph Coarsening)的池化机制
-
基于TopK的池化机制
-
基于边收缩(Edge Contraction)的池化机制
基于图坍缩(Graph Coarsening)的池化机制
图坍缩
图坍缩就是将图中的节点划分为几个节点簇(子图),将每个节点簇看作一个超级节点,从而形成一个坍缩的图,并作为下一次图坍缩的节点。图坍缩与GNN结合过程:
图坍缩中涉及到两个重要矩阵:簇分配矩阵S和采样矩阵C,详见下图
DIFFPOOL
DIFFPOLL是首个将图坍缩过程与GNN结合起来进行图层面任务学习的算法。
详解如下:
DIFFPOOL机制通过一个GNN为每个节点学习出所属各个簇的概率分布,节点以概率的形式分配到每一个簇中,属于软分配机制
EigenPooling
EigenPooling也是一种基于图坍缩的池化机制,EigenPooling没有对图分类模型引入任何需要学习的参数。
对两个步骤进行介绍:
1、图坍缩
EigenPooling的思路是借用一些图分区的算法实现图的划分,比如选用谱聚类算法。谱聚类是一类比较典型的聚类算法,其基本思路是先将数据变换到特征空间以凸显更好的区分度,然后执行聚类算法(比如选用K-means算法进行聚类),算法的输入是邻接矩阵和簇数K,输出的是每个节点所属的簇。使用K-means算法进行聚类,那么簇的分配就是一种硬分配,每个节点仅能属于一个簇,这种硬分配机制保持了图坍缩之后的超级节点之间连接的稀疏性。
2、池化操作
确定了子图划分以及相应的邻接矩阵后,对每个子图中的信息进行整合抽取。
DIFFPOOL中选择了对节点特征进线性加和,但这种方式损失了子图的结构信息。
EigenPooling则采用子图上的图信号在该子图上的傅里叶变换来代表结构信息与属性信息的整合输出。
总的来说,EigenPooling作为一种不带参数的池化机制,可以很方便的整合到一般的GNN模型中,实现对图信息的层次化抽取学习。
基于TopK的池化机制
TopK池化机制和图坍缩不同,图坍缩是将图的节点不断聚合成簇的过程,而TopK是一个不断抛弃节点的过程,具体来说就是设置一个超参数k,其中k的取值范围为(0,1),接着学习出表示节点重要度的值z,并按照重要度对节点进行降序排序,然后将全图中N个节点下采样至最重要的kN个节点,公式表示如下:
X’表示按照向量i的值对特征矩阵进行行切片,A‘表示按照向量i的值对邻接矩阵同时进行行切片与列切片。
关于重要度 z 的计算,这里引入了一个全局基向量 **p **将节点向量在该向量上的投影作为重要度:
相较于基于图坍缩的池化机制对图中所有节点不断融合学习的过程,gpool层采取层层丢弃节点的做法来提高远距离节点的融合效率,但是这种做法会缺少对所有节点进行有效信息融合的手段。基于此,文中选择在gpool层之后添加要给读出层,实现对该尺度下的图的全局信息的一次性聚合。读出层的具体实现方式就是将全局平均池化与全局最大池化拼接起来:
最终为了得到全图的表示,将各层的 s 相加:
一种参考模型:
该模型设置了两层gpool层,对应设置了两个读出层,再对两层读出层进行加和得到全图的向量表示。
关于丢弃节点的池化机制:自注意力图池化(SAGPool),该方法使用GNN对节点的重要度进行学习。
基于边收缩(Edge Contraction)的池化机制
基本思路:迭代式地对每条边上的节点进行两两归并形成一个新的节点,同时胞瘤合并前两个节点的连接关系到新节点上。
对于存在多条边的情况,EdgePool对每条边设计了一个分数,依据该分数进行非重复式的挑选与合并,具体操作:
首先对于每条边计算一个原始分数:
计算过程如下:
计算方法参考:TopK池化机制分数计算
小结:
正是利用了边收缩的原理,EdgePool仅将相近的邻居节点进行归并,这样做的优点:节点的融合都是从边进行的,这契合了图的结构信息,更加合理。
基于GNN的图表示学习
图表示学习
通常使用邻接矩阵A表示图的结构信息,但A往往是一个高维且稀疏的矩阵,难以使用相关的机器学习模型处理。
图表示学习的主要目标就是将图数据转化为一种低维稠密的向量化表示,同时保证图数据的某些性质在向量空间中也能够得到对应。
一种图数据的表示如果能够包含丰富的语义信息,那么下游的相关任务就能得到相当优秀的输入特征,通常在这种情况下,我们直接用线性分类器对任务进行学习。
图表示学习过程如下:
图表示学习的两个重要作用:
-
将图数据表示成线性空间中的向量。从工程上而言,这种向量化的表示为擅长处理线性结构数据的计算机体系提供了极大的便利。
-
为之后的学习任务奠定基础。图数据的学习任务种类繁多,有节点层面的,边层面的,还有全图层面的,一个好的图表示学习方法可以统一高效地辅助这些任务的相关设计与学习。
图表示学习方法:
-
基于分解的图表示学习
-
基于游走的图表示学习
-
基于深度学习的图表示学习
基于分解的图表示学习
在早期,图节点的嵌入学习一般是基于分解的方法,这些方法通过对描述图数据结构信息的矩阵进行矩阵分解,将节点转化到低维向量空间中去,同时保留结构上的相似性。这种描述结构信息的矩阵比如有邻接矩阵,拉普拉斯矩阵,节点相似度矩阵。一般来说,这类方法均有解析解,但是由于结果依赖于相关矩阵的分解计算,因此,这类方法具有很高的时间复杂度和空间复杂度。
类似于转换到频域上进行计算。
基于游走的图表示学习
如果两个词向量之间的距离近,那么它们对应的词就具有越高的语义相似性,这种思想即word2vec。核心思想就是:相近(词向量距离近)即相似(语义相似)。
Word2Vec的思想放到图(graph)上来说也是类似的,考虑图中的边表相似关系,如果两个结点之间的路径越短,则意味着这两个结点之间的相似度越高。
将图中随机游走产生的序列看作句子,节点看作词,对比词向量方法学习出节点的表示,自动地学习结点特征,生成隐含表示(latent representation)。典型方法有DeepWalk、Node2Vec等。
DeepWalk
在DeepWalk中通过使用随机游走(RandomWalk)的方式在图中进行节点采样来模拟语料库中的语料,进而使用word2vec的方式学习出节点的共现关系。
RandomWalk是一种可重复访问已访问节点的深度优先遍历算法。随机取起始点,规定路径长度,从其邻居中随机采样节点作为下一个访问节点,重复此过程,直到访问序列长度满足预设条件。
随机游走的好处:
-
并行性:显然可以同时开多个walker从不同结点出发进行游走
-
适应性:可以轻松应对动态网络,一旦有网络结构更新,只要有足够多的walker进行重新采样,就可以对其嵌入表示进行更
DeepWalk算法主要包括两个步骤,第一步为随机游走采样节点序列,第二步为使用skip-gram model学习表达向量。
伪代码:
输入为图G,窗口大小w,表示向量大小d,总的迭代次数y,游走序列长度t
1行初始化节点向量矩阵。4行是打乱节点(词汇表),生成一个随机排序来遍历所有节点。5~8行对于每一个节点进行随机游走获得游走序列,并使用Skip-Gram模型训练。6行使用随机游走算法获得游走序列。7行使用Skip-Gram模型进行训练,获得节点的向量表示。
参考:【Graph Embedding】DeepWalk:算法原理及应用
Node2Vec
DeepWalk一个很明显的缺点就是它均匀地对每个结点的邻居进行采样,这样会造成其无法很好控制其访问的邻居,因此node2vec的最大改进之处就是将采样方式给参数化了。
形式化地来说,对于每一源结点u∈V,定义其由采样策略S得到的邻居为Ns(u)⊂V(这里一定要注意,采样策略得到的邻居并不一定是直接邻居,后面会再阐述),希望在给定嵌入表示的前提下,最大化该邻居出现的概率,即:
详细内容参照从入门DeepWalk到实践Node2vec中的Node2Vec部分。
参考:【Graph Embedding】node2vec——知乎
基于GNN的图表示学习
基于重构损失的GNN
这一部分可以参照前文的表示学习中的基于重构损失的表示学习部分的内容。
类比自编码器的思路,将节点之间的邻接关系进行重构学习,可以定义如下的图自编码器:
其中,Z 是所有节点的表示,这里借助 GNN 模型同时对图的属性信息与结构信息进行编码学习。A^ 是重构之后的邻接矩阵,这里使用了向量的内积来表示节点之间的邻接关系。图自编码器的重构损失可以定义如下:
由于过平滑的问题,GNN 可以轻易地将相邻节点学习出相似的表达,这就导致解码出来的邻接矩阵 A^ 能够很快趋近于原始邻接矩阵 A,模型参数难以得到有效优化。因此,为了使 GNN 习得更加有效的数据分布式表示,同自编码器一样,我们必须对损失函数加上一些约束目标。比如添加噪声:
-
对原图数据的特征矩阵 X 适当增加随机噪声或置零处理;
-
对原图数据的邻接矩阵 A 删除适当比例的边,或者修改边上的权重值。
另外也可以借鉴变分自编码器的设计思路。
基于对比损失的GNN
类比于词向量,我们将对比损失的落脚点放到词与上下文上。词是表示学习的研究主体,在这里,自然代表的是图数据中的节点了,上下文代表的是与节点有对应关系的对象。通常,从小到大,图里的上下文依次可以是节点的邻居、节点所处的子图、全图。作为节点与上下文之间存在的固有关系,我们希望评分函数提高节点与上下文对的得分,同时降低节点与非上下文对的得分。用式子表示如下:
c 表示上下文的表示向量,cˉ 表示非上下文的表示向量。
依次比较损失函数在不同上下文时的形式:
1、邻居作为上下文
如果把邻居作为上下文 ,那么上述对比损失就在建模节点与邻居节点的共现关系。在 GraphSAGE 的论文中就描述了这样的一种无监督学习方式,与 DeepWalk 一样,我们可以将在随机游走时与中心节点 vi 一起出现在固定长度窗口内的节点 vj 视为邻居,同时通过负采样的手段,将不符合该关系的节点作为负样本。与 DeepWalk 不一样的是,节点的表示学习模型还是使用 GNN,即:
这里的 pn是一个关于节点出现概率的负采样分布,得分函数使用了向量内积加 sigmoid 函数,将分数限制在[0, 1]内。这个方法在优化目标上与图自编码器基本等同,但是这种负采样形式的对比优化,并不需要与图自编码器一样显式地解码出邻接矩阵 A^,由于 A^ 破坏掉了原始邻接矩阵的稀疏性,因此该方法不需要承担 O(N2) 的空间复杂度。
2、将子图作为上下文
将邻居作为上下文时,强调的是节点之间的共现关系,这种共现关系更多反应了图中节点间的远近距离,缺乏对节点结构相似性的捕捉。而通常节点局部结构上的相似性,是节点分类任务中一个比较关键的因素[9]。比如图上两个相距很远的节点如果具有一样的子图结构,基于共现关系的建模方法就难以有效刻画这种结构上的对等性。因此,论文[10]就提出了直接将子图作为一种上下文进行对比学习。具体子图的定义如图所示:
对于一个中心节点,如图 3,图中的红色节点所示,我们用一个 GNN 在其 K 阶子图上提取其表示向量,同时我们将处于中心节点 r1-hop 与 r2-hop 之间的节点定义为该中心节点的上下文锚点,如图 3 所示。设 K=2、r1=1、r2=4,我们用另一个 GNN 来提取每个节点作为上下文锚点时的表示向量,同时为了得到一个总的,固定长度的上下文表示向量,将使用读出机制来聚合上下文锚点的表示向量。式子表示如下:
3、全图作为上下文
节点与全图之间的对比损失的学习机制具体做法如下:
首先为了得到负采样的样本,需要对图数据进行相关扰动,得到(Xcurrupt,Aaurrupt)。然后将这两组图数据送到同一个 GNN 模型中进行学习。为了得到图的全局表示,使用读出机制对局部节点的信息进行聚合。过程示意图如下: