GraphSAGE

• 背景介绍

GraphSAGE[31]和Structure2vec比较类似，都是由聚合算子构建起来的图计算模型，都是共享参数的模型。GraphSAGE是比较早期的经典GNN算法，来自斯坦福发表于2017年。很多文献都会和GraphSAGE进行比较。这篇文章明确提出了图算法中的transductive learning和inductive learning的区别。

直推式(transductive)学习：从特殊到特殊，仅考虑当前数据。在图中学习目标是学习目标是直接生成当前节点的embedding，例如DeepWalk、LINE，把每个节点embedding作为参数进行学习，就不能对新节点进行infer。

归纳(inductive)学习：也就是平时所说的一般的机器学习任务，以共享参数方式进行学习。从特殊到一般：目标是在未知数据上也有区分性。

 

• 算法原理

GraphSAGE同样采用聚合算子，其信息聚合的过程如上图所示，可以描述为以下三个步骤：

1. 1. 先对邻居随机采样，降低计算复杂度（图中一跳邻居采样数为3，二跳邻居采样数为5）
   2. 生成目标节点嵌入向量：先聚合2跳邻居特征，生成一跳邻居嵌入向量，再聚合一跳邻居嵌入向量，生成目标节点嵌入向量，从而获得二跳邻居信息。
   3. 将嵌入向量作为全连接层的输入，预测目标节点的标签。

 

算法伪代码如下：

其中4、5行的for循环描述了汇聚算子的工作过程。第4行描述了信息由k-1层汇聚到第k层。第5行描述了中心节点信息由中心节点的k-1层信息与中心节点的邻居信息进行拼接，并通过一个全连接层转换，最终得到中心节点在第k层的嵌入向量。

GraphSAGE提出了四种不同的聚合方式：平均聚合、GCN归纳聚合、LSTM聚合、pooling聚合。

a. 平均聚合：先对邻居embedding中每个维度取平均，然后与目标节点embedding拼接后进行非线性转换。

b. GCN归纳聚合：直接对目标节点和所有邻居emebdding中每个维度取平均（替换伪代码中第5、6行），后再非线性转换：

c. LSTM函数不符合“排序不变量”的性质，需要先对邻居随机排序，然后将随机的邻居序列嵌入向量作为LSTM输入。

d. 先对每个邻居节点上一层嵌入向量进行非线性转换（等价单个全连接层，每一维度代表在某方面的表示），再按维度应用 max或者mean pooling，捕获邻居集上在某方面的突出的或者综合的表现 以此表示目标节点嵌入向量。

• 实验结果

从实验结果上可以看到GraphSAGE的四种聚合方式比传统算法均有所提升。

 

 

GAT

• 算法描述

Graph Attention Networks (GAT)[32]算法的主要思想是利用attention机制来代替GCN中的卷积层，得到node embedding。同时该算法可以适用于transductive和inductive两种任务。transductive任务是指测试集的节点和节点特征在训练过程中出现过；inductive任务是指测试集中的节点不会在训练过程中出现。下面介绍其核心结构Graph Attention layer.

• 基本原理

对于每一层，输入为每一个节点的feature, h={h1,h2,⋯,hN}, hi∈RF，N为节点个数，F为输入特征维数。输出亦为每一个节点的feature, h'={h′1,h′2,⋯,h′N}, h′i∈RF′，F′为输出特征的维数。则attention 机制就是在对输入特征做线性变换W∈RF′×F后计算对于节点i其周围节点（包括自身）的权重，最后加权求和通过激活函数即得到节点i的输出特征。则节点j对节点i的权重（可以看做节点j对于节点i的重要性）为：

其中就是attention机制，后面会给出几种具体的形式。则节点i输出可由对其相邻点加权得到：

上面这一步softmax为对权重的正则化。

上面这一步就是一个加权求和。注意到这个模型只用到了节点特征，没有用到边的信息。

文中给出的attention 机制有两类：一类是单层网络，如下：

另外一类是多头注意力网络（multi-head attention）的两个例子，第一个例子是将不同的head得到的嵌入向量做拼接，第二个例子是做平均，如下:

图: Graph Attention Networks (GAT)算法的Graph Attention layer图示

因为Attention计算相互独立，方便并行计算，所以比传统的GCN高效。

• 实验结果

可以看到实验结果都还不错，尤其是PPI的结果，比GCN的结果高太多了。文章发表在ICLR 2017[32]上。

• 算法特点：

GAT算法和下面将要介绍的GeniePath算法比较相似，都是建立在GNN基础之上，只是GAT只添加了对邻居节点信息进行筛选的attention机制，而GeniePath除此之外，还采用了LSTM机制来过滤经过多层传播的信息。从效果来讲，这两种算法的表现也比较接近，并且二者的表现都明显好于之前的GNN算法。

• 应用场景：

因为算法特性一致，GNN能够使用的场景（比如前面Structure2Vec的应用场景），GAT理论上应该都适用。

 

GeniePath

• 算法发展脉络：

图: GeniePath算法的发展脉络

GraphML团队开发的GeniePath算法[33,34]可以在聚合算子上结合节点的属性信息来判断到底有多少信息需要传播，有多少信息可以过滤掉。简单来讲就是，和structure2vec相比，GeniePath的聚合算子不仅仅采用了结构信息而且还结合了节点属性信息，就具有了更强大的表达能力。

• 算法原理：

下图揭示了GeniePath的算法结构，其结构是在基本的聚合算子上做了扩展。虚线左边表示在广度上采用了attention机制来筛选邻居节点；虚线右边表示在深度上采用了LSTM机制来过滤经过多层传播的信息。

下面的方程就描述了GeniePath在深度上的attention机制以及广度上的LSTM机制。

• • LSTM机制：

其中是输入门；是遗忘门；是输出门。

• • Attention机制：

(8)

GeniePath沿用GNN的计算框架，其特点在于会根据优化目标自动选择有用的邻居信息，来生成节点特征（embedding）。GeniePath通过定义两个parametric函数：自适应广度函数、和自适应深度函数，共同对子图进行广度、深度搜索。其中自适应广度函数限定朝哪个方向搜索重要节点，自适应深度函数限定搜索的深度。实现中如上图所示，GeniePath使用一个attention网络表达自适应广度函数来来筛选邻居节点，使用一个LSTM-style网络表达自适应深度函数来过滤经过多层传播的信息。GeniePath后来进行了升级，不仅能考虑节点特征，还能考虑边的特征。

目前所有的图神经网络方法都基于如下框架，做T次迭代，相当于每个节点拿自己走T跳可达的“邻居”节点，来做传播和变换，最后的被用来直接参与到损失函数的计算，并通过反向传播优化参数。在GeniePath之前的算法：Structure2Vec、GCN、GraphSAGE，他们的共同特点是对T步内所有邻居做聚合（aggregate），且以固定的权重做聚合。这些经典的GNN方法只会根据拓扑信息选择邻居并聚合生成特征，不会过滤和筛选有价值的邻居。而我们不但要看拓扑信息还要看节点的行为特征。GeniePath关心在聚合的时候到底应该选取哪些重要的邻居信息、过滤那些不重要的节点信息。

图：自适应的感知域示例

• 优点

1). 相比其他GNN算法，在大数据上可能有更好的性能，效率更高！

2). 可解释性更强。注意力权重可以区分出重要的边和次要的边，增加了可解释性。

• 实验

Alipay的数据集有1M节点，2M边，4k特征。可以看到数据集越大，效率越高，效果越好。

对蛋白质相互作用推理，F1值提升明显。

• 应用场景：

因为GeniePath是其他GNN算法的升级版，因此其他GNN算法的应用场景（比如前面讲到的Structure2Vec的应用场景）GeniePath应该都能实现，并且一般都可以期待更好的性能。GeniePath作为一个通用图神经网络算法已经在蚂蚁金服的风控场景实际使用，并得到较理想的效果，很好地提高了支付宝保护用户账户安全的能力[35]。其论文中还实现了的GeniePath应用场景包括：引用网络、BlogCatalog社交网络、蛋白质相互作用网络。