GraphSAGE 是一篇发表于2017年的文章，至今在工业界仍然备受关注，主要原因在于其标题中强调的两个关键词：inductive 和 large graph。本文将梳理这篇文章的核心思想及一些常被忽视的细节。
为何选择 GraphSAGE
图数据的流行可归结为几个原因：丰富的数据来源和大量的信息承载。因此，研究者们一直在探索如何更有效地利用图中蕴含的信息。
使用图的目标是利用其结构信息，为每个节点学习到合适的嵌入向量（embedding vector）。只要得到了适合的嵌入结果，后续的工作可以轻松地将其应用于模型中。
在 GraphSAGE 出现之前，主流的方法如 DeepWalk 和 GCN 都存在需要对整个图进行学习的不足。这些方法主要依赖于转导学习（transductive learning），意味着在训练时，图中必须包含所有待预测的节点。
考虑到实际应用中图的结构会频繁变化，预测阶段可能会新增节点，该如何处理呢？GraphSAGE 正是为了解决这一问题而提出。其核心理念在于其名称的构成：Graph Sample Aggregate，即对图进行采样和聚合。
GraphSAGE 的思路
我们提到的采样（sample）与聚合（aggregate）具体指的是什么？这个过程是如何进行的？为何能够适用于大规模图？接下来，我们将用通俗易懂的语言解释这一过程。
采样简单来说就是选择一些节点，聚合则是将它们的信息整合起来。整个流程如下所示：
在第一幅图中，我们学习了采样的过程。假设有一张图，需要更新中心节点的嵌入向量，首先从其邻居中选择 S1 个节点（本例中为 3 个）。假设 K=2，那么我们对第二层进行采样，即从刚选择的 S1 个邻居中再选择它们的邻居。
在第三幅图中，若我们要预测一个未知节点的信息，只需利用其邻居进行预测即可。
再来理清这个思路：若想了解小明的性格，可以先观察几个他关系亲密的小伙伴，然后再选择这些小伙伴的其他朋友进行进一步确认。通过小明的小伙伴们的朋友来推测小明的性格，便可以大致得出结论。
GraphSAGE 思路补充
现在我们已了解 GraphSAGE 的基本思路，但可能会有疑问：单个节点的处理方式是这样的，整体训练过程又是如何进行的？为何 GraphSAGE 能够应用于大规模图和具备 inductive 特性？
接下来，我们将补充 GraphSAGE 的训练过程及其优势。
首先，我们需从初始特征出发，逐层更新嵌入向量。我们如何决定需要聚合哪些点呢？应用前面提到的采样思路，来看一下算法：
算法的第 2-7 行实际上是一个采样过程，并将采样结果保存到 B 中。接下来的 9-15 行则是聚合过程，将对应的邻居信息聚合到目标节点上。
细心的读者会发现，采样过程是从 K 到 1（见第 2 行），而聚合过程是从 1 到 K（第 9 行）。这个道理很简单，采样时我们从整个图中选择要为哪些节点生成嵌入，然后对这些节点的邻居进行采样，逐步扩展到更远的邻居。
而在聚合过程中，首先从最远的邻居开始聚合，直到第 K 层时，才能将信息聚合到目标节点上。这就是 GraphSAGE 的完整思路。
那么，这样简单的思路中隐藏着哪些奥妙呢？
GraphSAGE 的精妙之处
首先，GraphSAGE 的提出主要是由于 inductive learning 的特性。最近在多个讨论群中看到同学们对转导学习和归纳学习的讨论，归纳学习无疑支持在测试阶段对新加入内容进行推理。
因此，GraphSAGE 的一大优点在于，训练完成后，可以对新加入的图节点进行推理，这在实际应用中非常重要。
另一方面，图网络通常涉及庞大的数据集，因此小批量（Mini Batch）处理能力至关重要。正因如此，GraphSAGE 的方法使我们只需对采样数据进行聚合，无需考虑其它节点。每个小批量可以是几个采样结果的组合。
再来看聚合函数部分，聚合函数在训练结果中占据重要地位。选择聚合函数时有两个条件：
首先，聚合函数需可导，以便反向传播训练目标的参数；
其次，聚合过程应对称，意味着对输入顺序不敏感，因为在聚合时，节点关系没有顺序特性。
因此，原文中使用的聚合器如均值（Mean）和最大池化（Max pooling）等是合理的。尽管作者也使用了 LSTM，但在输入之前会对节点进行洗牌操作，表明 LSTM 无法从序列顺序中学习到有用信息。
此外，文中还有一个小细节，我在首次阅读时未加注意，后来在朋友的提醒下才发现。原文中提到：
这里提到的算法中的第 11 和 12 行，即为算法中的第 4 和 5 行。
也就是说，作者提到的 GraphSAGE-GCN 实际上是使用上述聚合函数，替代了其它方法中先聚合再连接的操作。作者指出这种方法是局部谱卷积的线性近似，因此称其为 GCN 聚合器。
补充一些基本信息
最后，简单补充一些常见且易于理解的内容：GraphSAGE 通常用于哪些方面？
作者指出，它可用于无监督学习和有监督学习。在有监督情况下，可以直接使用最终预测的损失函数进行反向传播训练。而无监督学习呢？
无论哪种用途，需注意的是图本身，主要用于完成嵌入操作，即获取节点的有效特征向量。在无监督学习中，如何判断嵌入结果的准确性呢？
作者提出了一个易于理解的思路，即邻居关系。默认情况下，两个距离较近的节点，其嵌入结果应相似，而距离较远的节点则应有较大差异。因此，损失函数的构造也变得明了：
z_v 表示目标节点 u 的邻居，而 v_n 则表示非邻居，P_n(v) 是负样本的分布，Q 是负样本的数量。
最后一个问题是，邻居如何定义？
作者选择了一个简单的方式：直接使用 DeepWalk 进行随机游走，步长为 5，测试 50 次，得到的便是邻居。
总结
实验结果在此不作展示，实际上可以看到作者在多个方面采用了比较基线的思路，读者可根据自己的需求进行调整和替换。
后续我们将继续分享关于 GNN 和嵌入方面的经典与启发性论文，欢迎大家持续关注~~~
