前语

Hello！

非常感谢您阅读海轰的文章，假使文中有过错的地方，欢迎您指出～

自我介绍 ଘ(੭ᵕ)੭

昵称：海轰

标签：程序猿｜C++选手｜学生

简介：因C言语结识编程，随后转入核算机专业，获得过国家奖学金，有幸在比赛中拿过一些国奖、省奖…已保研。

学习经验：厚实基础 + 多做笔记 + 多敲代码 + 多思考 + 学好英语！

唯有努力

知其然 知其所以然！

本文仅记录自己感兴趣的内容

简介

原文链接：dl.acm.org/doi/abs/10.…

会议：NIPS’17: Proceedings of the 31st International Conference on Neural Information Processing Systems （CCF A类）

年度：2017/06/07

Abstract

大型图中节点的低维嵌入已被证明在从内容推荐到辨认蛋白质功用的各种猜测使命中非常有用

但是，大多数现有的办法要求图中的一切节点在嵌入的练习进程中都存在

这些曾经的办法本质上是传导性的，不能天然地推行到看不见的节点

在这里，咱们提出了GraphSAGE，这是一个通用的概括结构，它运用节点特征信息(例如，文本特点)来有效地为曾经未见的数据生成节点嵌入

咱们不是为每个节点练习单独的嵌入，而是学习一个函数，该函数经过采样和聚合节点的部分邻域中的特征来生成嵌入

1 Introduction

事实证明，大型图形中节点的低维向量嵌入关于各种猜测和图形分析使命非常有用[5，11，28，35，36]

节点嵌入办法的根本思维是运用降维技能将关于节点图邻域的高维信息提取到密布的向量嵌入中

这些节点嵌入然后能够被馈送到下流机器学习体系，并协助履行比如节点分类、聚类和链接猜测之类的使命

---

但是，曾经的作业首要会集在从单个固定的图中嵌入节点，而且许多现实世界的运用程序需要快速地为看不见的节点或全新的(子)图生成嵌入

这种概括才能关于高通量发生式机器学习体系至关重要，这些体系在不断演变的图表上运转，不断遇到看不见的节点(例如，Reddit上的帖子、YouTube上的用户和视频)

一种生成节点嵌入的概括办法也促进了具有相同特征形式的图的泛化：

• 例如，能够练习来自模型生物体的蛋白质-蛋白质相互作用图的嵌入生成器，然后运用练习的模型容易地为收集到的新生物体上的数据发生节点嵌入。

与换能式设置比较，概括节点嵌入问题特别困难

由于要泛化到看不见的节点，需要将新观察到的子图与算法现已优化过的节点嵌入“对齐”

概括结构必须学会辨认节点邻域的结构特点，这些特点既提醒了节点在图中的部分人物，也提醒了节点的全局位置

---

大多数现有的生成节点嵌入的办法都是固有的传导性的

这些办法中的大多数运用根据矩阵分化的方针直接优化每个节点的嵌入，并不天然地推行到不行见的数据

由于它们对单个固定图中的节点进行猜测

这些办法能够修改为在概括设置(例如，[28])中操作，但这些修改往往核算贵重，需要额定的几轮梯度下降才能做出新的猜测

最近也有运用卷积运算符学习图结构的办法，它们供应了作为嵌入办法的期望

到目前为止，图形卷积网络(GCNS)只运用于图固定的换能式环境[17，18]

在这项作业中，咱们将GCNS扩展到概括无监督学习使命，并提出了一个结构，该结构推行了GCN办法来运用可练习的集合函数(不限于简略的卷积)。

---

咱们提出了一个通用的概括节点嵌入结构，称为GraphSAGE(Sample And Aggregate)

• 与根据矩阵分化的嵌入办法不同，咱们运用节点特征(例如，文本特点、节点轮廓信息、节点度)来学习概括到不行见节点的嵌入函数
• 经过在学习算法中参加节点特征，咱们一起学习到每个节点邻域的拓扑结构以及节点特征在邻域中的分布

虽然咱们专心于特征丰厚的图表(例如，具有文本特点的引文数据，具有功用/分子标记的生物数据)

但咱们的办法也能够运用一切图表中存在的结构特征(例如，节点度)

因而，咱们的算法也能够运用于无节点特征的图

咱们没有为每个节点练习不同的嵌入向量，而是练习了一组聚合器函数，这些函数学习从节点的部分邻域集合特征信息(图1)

每个聚合器功用从远离给定节点的不同跳数或查找深度集合信息

在测验或推理时，咱们运用咱们练习的体系经过运用学习的聚合函数来生成彻底不行见的节点的嵌入

在之前关于生成节点嵌入的作业的基础上，咱们规划了一个无监督丢失函数

该函数允许在没有特定使命监督的状况下对GraphSAGE进行练习

咱们还表明，GraphSAGE能够在彻底监督的办法下进行练习

2 Related work

咱们的算法在概念上与曾经的节点嵌入办法、在图上学习的一般有监督办法以及在将卷积神经网络运用于图结构数据方面的最新进展有关

---

根据因式分化的嵌入办法

最近有许多节点嵌入办法运用随机游走核算和根据矩阵分化的学习方针来学习低维嵌入[5，11，28，35，36]

这些办法还与更经典的谱聚类[23]、多维缩放[19]以及PageRank算法[25]有着密切的联系

由于这些嵌入算法直接练习各个节点的节点嵌入，因而它们本质上是传导性的，而且至少需要贵重的附加练习(例如，经由随机梯度下降)来对新节点进行猜测

此外，关于这些办法中的许多办法(例如，[11，28，35，36])，方针函数关于嵌入的正交变换是不变的，这意味着嵌入空间不会在图之间天然泛化，而且可能在从头练习期间漂移

这一趋势的一个明显例外是由Yang等人介绍的Planetid-I算法。[40]这是一种根据概括、嵌入的半监督学习办法

但是，Planetid-I在推理进程中不运用任何图形结构信息；相反，它在练习期间运用图形结构作为正则化形式

与曾经的办法不同，咱们运用特征信息来练习模型，以便为看不见的节点生成嵌入

---

图上的有监督学习

除了节点嵌入办法，还有大量关于图结构数据上的监督学习的文献

这包括各式各样的根据核的办法，其间图的特征向量从各种图核中派生(拜见[32]及其参考文献)

最近也有一些神经网络办法在图结构上进行监督学习[7，10，21，31]

咱们的办法在概念上受到了许多这样的算法的启发

但是，虽然这些曾经的办法企图对整个图(或子图)进行分类，但这项作业的重点是为单个节点生成有用的表明

---

图卷积网络

近年来，现已提出了几种用于图上学习的卷积神经网络结构(例如，[4，9，8，17，24])

这些办法中的大多数不适用于大型图或规划用于全图分类(或两者兼有)[4、9、8、24]

但是，咱们的办法与Kipf等人提出的图卷积网络(GCN)密切相关[17，18]

最初的GCN算法[17]是为换能式环境下的半监督学习而规划的，而准确的算法要求在练习进程中知道完整的图拉普拉斯

咱们算法的一个简略变体能够被视为GCN结构到概括环境的扩展，咱们在3.3节中从头讨论了这一点。

3 Proposed method: GraphSAGE

咱们办法背面的关键思维是：学习怎么从节点的部分邻域中聚合特征信息(例如，邻近节点的度数或文本特点)

• 首要描绘GraphSAGE嵌入生成(即前向传达)算法，该算法在假定现已学习了GraphSAGE模型参数的状况下为节点生成嵌入(3.1节)
• 然后，咱们描绘怎么运用规范随机梯度下降和反向传达技能来学习GraphSAGE模型参数(第3.2节)。

3.1 Embedding generation (i.e., forward propagation) algorithm

在本节中，咱们描绘嵌入生成或前向传达算法(算法1)，它假定模型现已被练习而且参数是固定的

具体地说，咱们假定咱们现已学习了$K$个集合器函数的参数

记为AGGREGATEk，∀k∈1，…，KAGGREGATE_k，∀k∈{1，…，K}AGGREGATEk​，∀k∈1，...，K

它们集合了来自节点街坊的信息，以及一组权重矩阵Wk，∀k∈1，…，KW^k，∀k∈{1，…，K}Wk，∀k∈1，...，K

它们被用来在模型的不同层之间或“查找深度”之间传达信息

第3.2节描绘了怎么练习这些参数

算法1背面的直觉是，在每次迭代或查找深度时，节点从它们的本地街坊那里收集信息

而且跟着这个进程的迭代，节点从图的更远的范围逐渐获得越来越多的信息

---

算法1描绘了在供应整个图$G=(V，E)$和一切节点的特征XvX_vXv​、$\forall v\in V$作为输入的状况下的嵌入生成进程

咱们将描绘怎么将其推行到下面的小型批处理设置

算法1的外环中的每个步骤如下进行，其间

• $k$表明外环中的当时步骤(或查找深度)
• hkh^khk表明该步骤中的节点表明

首要，每个节点$v\in V$集合其直接邻域中的节点的表明，huk−1，∀u∈N(v){h^{k-1}_u，∀u∈N(v)}huk−1​，∀u∈N(v)，转化成单个载体hN(v)k−1h^{k-1}_{N(v)}hN(v)k−1​

留意，该集合步骤依赖于在外部循环的前一迭代处生成的表明(即，$k-1$)，而且$k=0$(根本状况)表明被界说为输入节点特征

在聚合相邻特征向量后，GraphSAGE然后将节点的当时表明hvk−1h^{k-1}_vhvk−1​与聚合的邻域向量hN(v)k−1h^{k-1}_{N(v)}hN(v)k−1​衔接

而且该衔接的向量经过具有非线性激活函数的全连通层馈送，其转化将在算法的下一步运用的表明(即，hvk，∀v∈Vh^k_v，∀v∈Vhvk​，∀v∈V)

为了符号方便，咱们将深度$K$处输出的终究表明表明为zv≡hvk，∀v∈Vz_v≡ h^k_v，∀v∈Vzv​≡hvk​，∀v∈V

街坊表明的集合能够经过各种集合器架构(由算法1中的AGGREGATE占位符表明)来完成

咱们将在下面的第3.3节中讨论不同的架构挑选

---

为了将算法1扩展到小批量设置

给定一组输入节点，咱们首要对所需的邻域集(直到深度$K$)进行前向采样

然后运转内循环(算法1中的第3行)，但咱们不是迭代一切节点，而是仅核算在每个深度满足递归所需的表明(附录A包含完整的小批量伪代码)

---

Relation to the Weisfeiler-Lehman Isomorphism Test

GraphSAGE算法的概念创意来自于测验图同构的经典算法

如果在算法1中

• (i)设置$K=|V|$
• (Ii)设置权重矩阵为单位
• (iii)运用适当的散列函数作为集合器(没有非线性)

则算法1是Weisfeler-Lehman(WL)同构测验的一个实例，也称为“朴素极点求精”[32]

如果算法1为两个子图输出的表明集{zv，∀v∈V}\{z_v，∀v∈V\}{zv​，∀v∈V}相同，则WL测验宣告这两个子图同构

众所周知，这个测验在某些状况下会失利，但对大类图是有效的[32]

GraphSAGE是WL测验的接连近似，在WL测验中，咱们用可练习的神经网络集合器替换哈希函数

当然，咱们运用GraphSAGE来生成有用的节点表明–而不是测验图形同构

但是，GraphSAGE和经典的WL测验之间的联系为咱们的算法规划学习节点邻域的拓扑结构供应了理论布景

Neighborhood definition

在这项作业中，咱们对固定巨细的邻域集进行均匀采样，而不是运用算法1中的完整邻域集，以保持每批的核算空间固定

也就是说，运用重载记法，咱们将$N(v)$界说为从集合$u\in V：(U，v)\in E$中的固定巨细的均匀抽取，而且在算法1中的每次迭代$k$处抽取不同的均匀样本

如果没有这个采样，单个批处理的内存和预期运转时刻是不行猜测的，在最坏的状况下是$O(|V|)$

相反，GraphSAGE的每批空间和时刻杂乱度固定为O(∏i=1KSi)O(∏^K_{i=1}S_i)O(∏i=1K​Si​)，其间Si，i∈1，…，KS_i，i∈{1，…，K}Si​，i∈1，...，K和$K$是用户指定的常量

实际上，咱们发现咱们的办法能够在$K=2$和$S1\cdot S2\le 500$时获得高功能(有关详细信息，请拜见第4.4节)。

3.2 Learning the parameters of GraphSAGE

为了在彻底无监督的环境中学习有用的猜测表明

咱们将根据图的丢失函数运用于输出表明zu，∀u∈Vz_u，∀u∈Vzu​，∀u∈V，并经过随机梯度下降来调整权重矩阵Wk，∀k∈1，…，KW^k，∀k∈{1，…，K}Wk，∀k∈1，...，K和集合器函数的参数

根据图的丢失函数鼓励邻近节点具有类似的表明，一起强制不同节点的表明高度不同：

其间

• $v$是在定长随机游走上在$u$邻近一起呈现的节点
• 是Sigmoid函数
• PnP_nPn​是负采样分布
• $Q$界说了负采样的数量

重要的是，与曾经的嵌入办法不同，咱们馈送到该丢失函数的表明zuz_uzu​是从节点的部分邻域中包含的特征生成的，而不是(经过嵌入查找)为每个节点练习仅有的嵌入

此无监督设置模拟将节点功用作为服务或在静态存储库中供应给下流机器学习运用程序的状况

在表明仅用于特定下流使命的状况下，能够简略地用特定于使命的方针(例如，交叉熵丢失)来替换或增加非监督丢失(公式1)

3.3 Aggregator Architectures

与N-D网格(例如，句子、图画或3-D体积)上的机器学习不同，节点的街坊没有天然的次序

因而，算法1中的集合器函数必须在一组无序的向量上操作

理想状况下，聚合器函数应该是对称的(即，不随其输入的摆放而变化)，一起仍然是可练习的，并保持高的表明才能

集合函数的对称性保证了咱们的神经网络模型能够练习并运用于恣意排序的节点邻域特搜集

---

咱们研讨了三个候选聚合器函数：

Mean aggregator

咱们的第一个候选集合器函数是均匀值运算符，其间咱们只取{huk−1，∀u∈N(v)}\{h^{k-1}_u，∀u∈N(v)\}{huk−1​，∀u∈N(v)}中向量的元素均匀值

均匀集合器简直等同于在传导GCN结构中运用的卷积传达规则[17]

具体地说，咱们能够经过将算法1中的第4行和第5行替换为以下内容来导出GCN办法的概括变体：

咱们称这种修正的根据均值的集合器为卷积，由于它是部分谱卷积的大略的线性近似[17]

该卷积集合器与咱们提出的其他集合器之间的一个重要区别是，它不履行算法1第5行中的级联操作

即，卷积集合器确实将节点的先前层表明hvk−1h^{k-1}_vhvk−1​与集合的邻域向量hN(v)kh^k_{N(v)}hN(v)k​级联

这种串联能够被视为GraphSAGE算法的不同“查找深度”或“层”之间的“跳过衔接”[13]的简略形式，而且它导致明显的功能提升(第4节)

LSTM aggregator

咱们还研讨了一个根据LSTM架构的更杂乱的聚合器[14]

与均值集合器比较，LSTM具有表达才能更强的优势

但是，重要的是要留意，LSTM自身并不对称(即，它们不是摆放不变的)，由于它们以次序的办法处理它们的输入

经过简略地将LSTM运用于节点街坊的随机摆放，咱们使LSTM适应于在无序集合上操作

Pooling aggregator

咱们研讨的终究聚合器既是对称的，也是可练习的

在这种池化办法中，每个街坊的向量经过彻底衔接的神经网络独立馈送

在此转化之后，运用根本的最大池化操作来聚合街坊集合中的信息：

其间

• max表明根据元素的max算子
• 而表明非线性激活函数

原则上，在最大值兼并之前运用的函数能够是恣意深度的多层感知器，但在本文中咱们首要重视简略的单层体系结构

这种办法的创意来自于最近在运用神经网络结构来学习一般点集方面的前进[29]

直观地说，多层感知器能够被认为是为街坊会集的每个节点表明核算特征的一组函数

经过将最大池化算子运用于每个核算的特征，该模型有效地捕获了邻域集合的不同方面

还要留意，原则上，能够运用任何对称向量函数来替代最大运算符(例如，元素式均匀值)

咱们在开发测验中没有发现最大池化和均匀池化之间的明显差异，因而在咱们其他的实验中专心于最大池化

4 Experiments

4.1 Inductive learning on evolving graphs: Citation and Reddit data && 4.2 Generalizing across graphs: Protein-protein interactions

4.3 Runtime and parameter sensitivity

5 Theoretical analysis

略

6 Conclusion

咱们介绍了一种新的办法，能够有效地为看不见的节点生成嵌入

GraphSAGE始终优于最先进的基准，经过采样节点街坊有效地权衡了功能和运转时刻，咱们的理论分析为咱们的办法怎么了解本地图结构供应了洞悉

许多扩展和潜在的改进是可能的，例如扩展GraphSAGE以兼并有向图或多形式图

未来作业的一个特别风趣的方向是探索非均匀邻域采样函数，甚至可能将这些函数作为GraphSAGE优化的一部分进行学习

读后总结

下午读了这篇文章 老实说

没有咋看懂 哈哈

还得再认真读读！

---

凭借他人的博客想想

• 来历：www.cnblogs.com/BlairGrowin…

结语

文章仅作为个人学习笔记记录，记录从0到1的一个进程

期望对您有一点点协助，如有过错欢迎小伙伴纠正

• 我正在参加技能社区创作者签约方案招募活动，点击链接报名投稿。