SAGEConv

论文名称：Inductive Representation Learning on Large Graphs

论文链接：https://arxiv.org/pdf/1706.02216.pdf

现在存在方法具有内在transductive，不能generalize未见到的节点,。我们提出GraphSAGE是基于inductive开发的，对于未见到数据具备泛化能力。在训练的过程中，对邻居的节点采用抽样的方式，而不是对所有的节点进行训练。

GraphSAGE学习的主要方法是收集局部的邻居信息，例如度特征或者邻居节点的属性特征。接下来，首先描述推理算法，假设参数已经学习，如何生成节点的Embedding。然后，我们在讲一下如何通过随机梯度下降法和后向传播算法学习模型的参数。

1、Embedding产生算法（前向传播算法）

假设我们已经学习K 聚合函数（AGGREGATEk,k∈{1,…,K}AGGREGATE_k,k\in\{1,\dots,K\}AGGREGATEk​,k∈{1,…,K}）的参数和一系列的权重矩阵Wk,∀k∈{1,…,K}W^k,\forall k \in\{1, \ldots, K\}Wk,∀k∈{1,…,K}, 其中K指搜索的深度，这些参数主要用于前向传播。

Algorithm 1是在一次迭代、深度搜索并aggregate局部邻居的信息，随着迭代次数的增加，能够获取到更深层次的信息。

$\mathcal{G}=(\mathcal{V},\mathcal{E})$表示整张图,

${\text{x}}_v，\forall v\in \mathcal{V}$表示节点的特征。

$k$表示当前step下，每个节点$v\in \mathcal{V}$ 收集邻居节点特征表示${\text{h}}_u^{k-1},\forall u\in \mathcal{N}(v)$，生成单一的节点表示${\text{h}}_{N(v)}^{k-1}$. 注意本次迭代aggregate取决于前一次迭代的输出。其中bad case $k=0$是节点的特征输入。将汇总的邻居向量${\text{h}}_{\mathcal{N}(v)}^{k-1}$和当前的节点特征$h_v^{k-1}$进行拼接, 进行全连接层和非线性激活函数$\sigma$的转换，生成的结果作为下一次迭代的输入。最终输出的特征表示为${\mathbf{z}}_v\equiv {\mathbf{h}}_v^K,\forall v\in \mathcal{V}$。

在minibatch的设置中，对邻居节点和边进行采样。相对于全部节点的向量的计算，GraphSAGE只是对必要的节点minibatch集合$\mathcal{B}$进行计算。

主要的思想就是抽样出需要的节点进行计算，Algorithm的Line 2-7描述了抽样的过程。

从Line1-6看出： 每个${\mathcal{B}}^k$包含节点$v\in {\mathcal{B}}^{k+1}$的 表示。

Line9-15 描述聚合过程，${\mathcal{N}}_k(u)$采用独立的均匀采样。

Relation to the Weisfeiler-Lehman Isomorphism Test. GraphSAGE的灵感来自同构图检验的经典算法。在Algorithm中，我们 (i)设$K=|V|$ (ii) 边权重是相等的。(iii) 使用Hash函数作为aggregator。如果两个子图输出{zv,∀v∈V}\{\text{z}_v, \forall v\in\mathcal{V}\}{zv​,∀v∈V}是相同的，我们认为两个子图是同构的。当然，我们的目标学习节点的表示，不是测试是否同构。

Neighborhood defination 均匀采样固定大小的邻居节点的数量, 即$\mathcal{N}(v)$是固定的，每次迭代均匀采样不同的样本。如果不采样，一个Batch的大小为$O(|\mathcal{V}|)$. 采样后， GraphSAGE的复杂度固定在$O\left({\prod }_{i=1}^K{S}_i\right)$, 其中Si,i∈{i,⋯ ,K}S_i, i\in\{i,\cdots,K\}Si​,i∈{i,⋯,K}, $K$用户自定义的。在实际应用中，一般$K=2$， $S_1\cdot S_2\le 500$。

2、GraphSAGE参数学习

使用graph-based loss function学习节点的表示,${\text{z}}_u,\forall u\in \mathcal{V}$, 学习权重矩阵Wk,∀k∈{1,⋯ ,K}W^k, \forall k\in\{1,\cdots, K\}Wk,∀k∈{1,⋯,K}, 采用随机梯度下降的方法。graph-based loss function会使得相近的节点有相同的表示，同时兼顾不同的节点学习表示不相同的。
$$J_{\mathcal{G}}\left({\mathbf{z}}_u\right)=-\log \left(\sigma \left({\mathbf{z}}_u^{\top }{\mathbf{z}}_v\right)\right)-Q\cdot {\mathbb{E}}_{v_n\sim P_n(v)}\log \left(\sigma \left(-{\mathbf{z}}_u^{\top }{\mathbf{z}}_{v_n}\right)\right)\text{\hspace{1em}(1)}$$
其中，节点v和节点u是在固定长度随机游走过程共现的。$\sigma$是激活函数，$P_n$是负采样的分布， $Q$是定义负样本的数量, 损失函数输入表示${\text{z}}_u$包含来自邻居节点的特征。

3、Aggregator Architectures

节点的邻居和文本、图像不一样，他们的无序、对称的，测试如下三个aggregator functions：

Mean aggregator

用以下公式替换Algorithm1中Line4和Line5
$${\mathbf{h}}_v^k\leftarrow \sigma (\mathbf{W}\cdot \mathrm{MEAN}\left(\left\{{\mathbf{h}}_v^{k-1}\right\}\cup \left\{{\mathbf{h}}_u^{k-1},\forall u\in \mathcal{N}(v)\right\}\right)\text{\hspace{1em}(2)}$$
计算当前节点${\mathbf{h}}_v^{k-1}$和邻居节点拼接起来, 计算均值，这种操作可以将不同深度的节点进行"skip connnection"。

LSTM aggregator

LSTM不具备对称性，简单地将邻居节点处理成无序的序列作为输入。

Pooling aggregator
$${\text{ AGGREGATE }}_k^{\text{pool }}=\max \left(\left\{\sigma \left({\mathbf{W}}_{\text{pool }}{\mathbf{h}}_{u_i}^k+\mathbf{b}\right),\forall u_i\in \mathcal{N}(v)\right\}\right)\text{\hspace{1em}(3)}$$