本文为转载，原文链接：
https://wmathor.com/index.php/archives/1533/
本文主要讲解两种图采样算法。前面 GCN 讲解的文章中，我使用的图 节点个数非常少，然而在实际问题中，一张图可能节点非常多，因此就没有办法一次性把整张图送入计算资源，所以我们应该使用一种有效的采样算法，从全图
中采样出一个子图
，这样就可以进行训练了。
在了解图采样算法前，我们至少应该保证采样后的子图是连通的。例如下图中，左边采样的子图就是连通的，右边的子图不是连通的。
GraphSAGE(SAmple & aggreGatE)
GraphSAGE 主要分两步：采样、聚合
采样的阶段首先选取一个点，然后随机选取这个点的一阶邻居，再以这些邻居为起点随机选择它们的一阶邻居。例如下图中，我们要预测 0 号节点，因此首先随机选择 0 号节点的一阶邻居 2、4、5，然后随机选择 2 号节点的一阶邻居 8、9；4 号节点的一阶邻居 11、12；5 号节点的一阶邻居 13、15
聚合具体来说就是直接将子图从全图中抽离出来，从最边缘的节点开始，一层一层向里更新节点
下图展示了邻居采样的优点，极大减少训练计算量这个是毋庸置疑的，泛化能力增强这个可能不太好理解，因为原本要更新一个节点需要它周围的所有邻居，而通过邻居采样之后，每个节点就不是由所有的邻居来更新它，而是部分邻居节点，所以具有比较强的泛化能力。
PinSAGE
采样时只能选取真实的邻居节点吗？如果构建的是一个与虚拟邻居相连的子图有什么优点？PinSAGE 算法将会给我们解答
PinSAGE 算法通过多次随机游走，按游走经过的频率选取邻居，例如下面以 0 号节点作为起始，随机进行了 4 次游走
其中 5、10、11 三个节点出现的频率最高，因此我们将这三个节点与 0 号节点相连，作为 0 号节点的虚拟邻居
回到上述问题，采样时选取虚拟邻居有什么好处？可以快速获取远距离邻居的信息。实际上如果是按照 GraphSAGE 算法的方式生成子图，在聚合的过程中，非一阶邻居的信息可以通过消息传递逐渐传到中心，但是随着距离的增大，离中心越远的节点，其信息在传递过程中就越困难，甚至可能无法传递到；如果按照 PinSAGE 算法的方式生成子图，有一定的概率可以将非一阶邻居与中心直接相连，这样就可以快速聚合到多阶邻居的信息
