论文浅尝 | GraphSAINT—基于图采样的归纳学习方法

论文笔记整理：杨海宏，浙江大学博士生，研究方向为开放世界下的多语言知识问答。

---

     

 

1. 简介

受显存的因素限制，应用图神经网络于大规模图学习任务上面临“邻居爆炸（Neighbor Explosion）”问题，导致网络深度局限于少数几层（否则指数爆炸），计算量过大等问题。前人工作提出了众多基于采样邻居节点的方法，并利用多类型的聚合函数提高魔性的表达能力。

 

这篇文章提出一种全新的采样方法，以改进图卷积网络（GCN）的训练方式，从而提高模型的训练效率和准确率。一言以蔽之，这篇文章从原图中采样子图，在结果子图上使用GCN学习。

 

             

图1：GraphSAINT 训练方案。来源：原论文

 

GraphSAINT 的算法流程如下图所示。其中，变量SAMPLE主要有两点要求。（1）相互影响较大的节点应在同一子图中采样。（2）每条边的采样概率均不可忽略。对于要求（1），理想的SAMPLE要求衡量节点连接的联合信息以及属性。但这种算法可能具有很高的复杂度，所以，为简单起见，我们从图连接性角度定义“影响力”，并设计基于拓扑的采样器。要求（2）可使神经网络能够探索整个特征和标签空间。

             

2. 子图采样

作者认为：保留图连通性特征的采样器几乎不可避免地会在小批量估计中引入偏差。因此作者引入自行设计的归一化技术，以消除偏差。其中的重点是估计每个节点、边、子图的采样概率，

l  节点的采样概率分布为：

             

l  边的采样概率分布为：

             

l  子图的采样概率分布为：

              ，其中              

3. 实验结果

             

实验部分作者展示了这篇文章提出的子图采样方式可以灵活地集成到图神经网络模型中，并取得超越前人的表现。这极大地刷新了学界对于图神经网络使用方式的认知，是一篇值得深入研究的论文。

---

 

OpenKG

开放知识图谱（简称 OpenKG）旨在促进中文知识图谱数据的开放与互联，促进知识图谱和语义技术的普及和广泛应用。

点击阅读原文，进入 OpenKG 博客。