今天看的论文是斯坦福大学的同学的论文《Inductive Representation Learning on Large Graphs》,于 2017 年发表于 NIPS,目前被引次数超过 1200 次。
对于大规模网络图来说,低维的分布编码具有举足轻重的意义,但现有的诸多模型都属于直推式学习(transductive),其可以解决参与训练的节点的编码问题,但无法泛化到未知节点(即,如果有新节点加入需要重新训练)。针对这一痛点,斯坦福大学的同学提出了归纳式学习算法(inductive)——GraphSAGE,该算法可以利用的方式解决了未知节点无法 Embedding 的问题,接下来我们看一下 GraphSAGE 的具体实现过程。
NetWork Representation 应用广泛,模型可以通过将网络中的节点编码为低维的 Embedding 向量,为下游机器学习任务提供了有效的特征输入,但目前的模型都无法应对网络中的未知节点,属于直推式学习。而在真实场景中,新节点随处可见,如新用户、新帖子、新视频等等。
为了解决这一问题,我们需要一个具有归纳能力模型,它可以利用节点的邻域特征归纳出节点的 Embedding 向量。
相比于直推式学习而言,归纳式学习方式尤其困难。因为要想泛化新节点的 Embedding 向量,则需要模型将新网络与先前的网络对齐,以识别新节点的邻域结构,并捕获节点在图中的局部特征和全局特征。
针对这一痛点,本文作者在 GCN 的基础上提出了 GraphSAGE 算法(SAmple and aggreGatE)用于归纳学习节点的 Embedding 向量,其不仅将 GCN 扩展到无监督的归纳学习任务中,还泛化了 GCN 的聚合函数。
与 GCN 直接学习某个节点的 Embedding 向量不同的是,GraphSAGE 「是利用一组聚合函数进行学习」。这些聚合函数可以从节点的邻居中学到节点的特征信息,所以即使是新节点也可以通过其邻域信息进行学习。
接下来我们看一下 GraphSAGE 是如何利用聚合函数学习的。
我们先概览下 GraphSAGE:
所以 GraphSAGE 大概思想就是聚合邻居信息,然后不断迭代。
放出 GraphSAGE 的伪代码:
简单来说就是用 k-1 层的节点的邻居信息和自身信息来更新 k 层的节点信息。这里的聚合函数我们待会再讨论,现在可以默认是一个提取邻居特征的方法。
但这样会出现一个问题:如果我们只是想计算某个新的节点的 Embedding,其实没有必要把整张图的节点的 Embedding 都更新一遍。
针对这个问题,作者给出了算法二:
这里出现的
是指对节点 u 在第 k 层进行邻居采样(每层独立采样)。这里「邻居采样的大小是固定的」,以保证每个批处理单元大小都是固定的。
学习节点的 Embedding 向量是一个非监督学习,我们希望节点与较近的节点的 Embedding 向量相似,而与较远的节点不相似,其损失函数为:
其中,节点 v 是节点 u 在定长随机游走算法中邻居节点;
是负采样分布,Q 定义了负采样的个数。
对于一个无序网络来说,理想的聚合器是对称的,即:不考虑节点顺序。同时也需要保证 Embedding 向量具有较好的效果。这里作者提出了三种不同的聚合器:
我们来看一下实验部分。
下表表示 GraphSAGE 的不同聚合器和其他基准算法在不同数据集下的指标,我们看到 LSTM 和 Pooling 聚合器的效果差不多。
下图展示了不同参数聚合器下的模型的运行时间。
一句话总结:GraphSAGE 通过聚合节点邻居的特征将 GCN 扩展成归纳学习的方式,解决了未知 Embedding 的难题。此外,GraphSAGE 也支持修改聚合函数,使其更具扩展性。特别是使用 LSTM 和 Pooling 聚合器后,模型的效果得到了显著的提升。