图神经网络：GraphSage策略原理学习笔记

摘要：图神经网络，graphsage

GraphSage概述

GraphSage是基于GCN的改进策略，它对GCN进行了两点改进：

• 子图随机组合训练：将GCN的全图训练方式改造成以节点为中心的小批量训练方式，使得模型可以在大规模的图数据上进行训练，并且可以在新的图结构上做预测，大大提供了工业场景的应用性
• 邻居聚合操作拓展：提出了替换卷积操作的其他集中提取邻居特征的方式

---

采样邻居

GraphSage从一组一组中心节点出发进行模型训练，而不是GCN从全图角度出发，因此GraphSage对节点的聚合操作需要考虑高阶下的复杂度，GraphSage采用对邻居进行随机采样来控制节点k阶子图的数据规模，在此基础上对采样的子图进行随机组个来完成小批量式的训练。

节点多阶/层聚合的节点范围

节点在第k+1层的特征只与节点的第k阶的邻居有关，如果GCN的层数是2，则拿到中心节点经过2阶卷积之后的特征需要将下图中所有的节点纳入计算。

采样邻居

邻居节点的指数级增长和超级节点问题

假设图上一个节点的平均度是d，如果要进行k层的GCN，一共需要纳入的节点数量1+d+d²+...+d^k，其中1为中心节点自己，d为第一阶，后面分别是第k阶，整个呈指数级增长，导致计算复杂度极高，同时会存在某些节点的度非常大，就会进一步放大指数问题，导致高阶的特征计算成本昂贵。

GraphSage的采样策略

邻居节点的指数级增长和超级节点的问题导致从中心节点遍历子图聚合计算变得非常不稳定和不可控。GraphSage使用采样邻居的方式来控制子图散发的增长率。具体的做法是给每一层的采样设置采样倍率S_k，例如

S₁ = 3，S₂ = 2： 所有中心节点第一阶的邻居不超过3，第二阶的邻居节点不超过2，因此一个二阶模型的中心节点涉及的最多节点个数是1+3+3×2=10个（分别代表中心节点，第一层节点，第二层节点）

因此一个k阶模型所有节点的数量复杂度为S_k的阶乘（最后一阶，个数是每层S_k相乘），采样的时候GraphSage默认采用随机均匀分布采样。GraphSage的采样策略使得模型节点的规模维持在阶乘级别。

---

聚合邻居

GraphSage提出了几种新的集合操作（aggregator），首先节点聚合输出的要求：

• 聚合输出维度一致：在GCN中输出维度通过邻接矩阵乘以节点特征控制，输出为每个节点相同维度的特征向量，在GraphSage中每层都有采样倍率S_k，也要保证聚合之后输出维度一致
• 聚合操作具有排列不变性：即Agg(v₁, v₂)=Agg(v₂, v₁)，聚合方式要保证和顺序无关

比较简单的符合致谢要求的聚合方式有：
*（1）平均/加和聚合算子：类似GCN的邻居特征相加求和取平均，公式如下

Agg^sum=α(SUM{Wh_j + b, v_j∈N(v_i)})

其中w和b是聚合操作的学习参数，注意聚合结束有激活函数

*（2）池化聚合算子：类似CNN中的最大值池化，公式如下

Agg^pool=MAX{α(Wh_j + b), v_j∈N(v_i)}

其中w和b是聚合操作的学习参数，对激活函数之后的特征向量的逐个元素取最大值

---

GraphSage算法过程

GraphSage实现小批量训练的具体流程如下

GraphSage算法流程

（1）采样操作部分

其中1~7行是采样部分

（2）聚合操作部分