cpgsmldl

V1

2022/01/28阅读:41主题:橙心

GraphSAGE

在之前的文章里介绍过 DeepWalk 算法,DeepWak 算法的主要问题是它缺乏泛化能力。 每当有新节点加入到图中时,它必须重新训练模型以正确表示该节点( 直推式学习 )。 这种 GNN 不适用于图中节点不断变化的动态图。

GraphSage 提供了解决上述问题的解决方案,它以归纳方式学习每个节点的嵌入。 具体来讲,它将每个节点用其邻域的聚合重新表示。 因此,即使在训练时间期间未出现在图中新节点,也仍然可以由其相邻节点正确地表示。

GraphSAGE 算法基本流程

假设有一个图如下所示:

  • 计算节点 1 的相邻节点

  • 伪代码第 4 步: ,假设这里使用的 AGGREGATE 方法为均值函数(mean),则

  • 伪代码第 5 步:

采样

如果对点的所有邻居进行采样,那么时间复杂度通常会提升,通常采用均匀采样的方式,每次聚合采样固定数目的邻居节点。如果邻居节点数比要求数目多,则直接均匀采样即可。如果邻居节点数比要求数目少,则进行有放回采样。

通常进行不多于两次传播时效果较好,且假设第一次邻居节点数为 ,第二次邻居节点数为 的值最好 ≤ 500。

聚合函数

论文中提到了 3 种聚合函数:

  • Mean aggregator
  • LSTM aggregator
  • Pooling aggregator

聚合函数需要适用于无序集合,LSTM 本身是有顺序的,但是通过将输入节点随机排列,可以使得 LSTM 也可以适用于无序的集合。

mini batch 版本

假设节点 a 是当前 batch 内的一个节点,可以计算出,a 节点参与训练依赖的的节点集合为:{a, c, f, j, d, e, i, h, k, l},训练时只需要存储 a 以及训练 a 时依赖的节点,batch 内的其他节点依此类推。GraphSAGE 部分即正常的训练部分。

损失函数为:

其中 u 和 v 共同出现在一定长度的随机游走中,而 是不与 u 共同出现的负样本。这种损失函数鼓动节点在投影空间中更靠近嵌入距离更近的节点,而与那些相距很远的节点分离。通过这种方法,节点将获得越来越多其邻域的信息。

通过训练,最终得到的是 GraphSAGE 的权重函数 W,经过 GraphSAGE后,生成 embedding( ),而不是直接生成节点的 embedding。

GraphSage通过聚合其附近的节点,可以为看不见的节点生成可表示的嵌入位置。它让节点嵌入的方式可以被应用于涉及动态图的研究领域,这类动态图的图的结构是可以不断变化的。

参考

分类:

人工智能

标签:

数据挖掘

作者介绍

cpgsmldl
V1