关于算法:PGL图学习之图神经网络GraphSAGEGIN图采样算法系列七

0. PGL 图学习之图神经网络 GraphSAGE、GIN 图采样算法[系列七]

本我的项目链接：https://aistudio.baidu.com/aistudio/projectdetail/5061984?contributionType=1

相干我的项目参考：更多材料见主页

对于图计算 & 图学习的基础知识概览：前置知识点学习（PGL）[系列一] https://aistudio.baidu.com/ai…

图机器学习 (GML)& 图神经网络(GNN) 原理和代码实现(前置学习系列二）：https://aistudio.baidu.com/ai…

在图神经网络中，应用的数据集可能是亿量级的数据，而因为 GPU/CPU 资源无限无奈一次性全图送入计算资源，须要借鉴深度学习中的 mini-batch 思维。

传统的深度学习 mini-batch 训练每个 batch 的样本之间无依赖，多层样本计算量固定；而在图神经网络中，每个 batch 中的节点之间相互依赖，在计算多层时会导致计算量爆炸，因而引入了图采样的概念。

GraphSAGE 也是图嵌入算法中的一种。在论文 Inductive Representation Learning on Large Graphs 在大图上的演绎示意学习中提出。github 链接和官网介绍链接。

与 node2vec 相比较而言，node2vec 是在图的节点级别上进行嵌入，GraphSAGE 则是在整个图的级别上进行嵌入。之前的网络示意学习的 transductive，难以从而提出了一个 inductive 的 GraphSAGE 算法。GraphSAGE 同时利用节点特色信息和构造信息失去 Graph Embedding 的映射，相比之前的办法，之前都是保留了映射后的后果，而 GraphSAGE 保留了生成 embedding 的映射，可扩展性更强，对于节点分类和链接预测问题的体现也比较突出。

0.1 提出背景

现存的办法须要图中所有的顶点在训练 embedding 的时候都呈现；这些前人的办法实质上是 transductive，不能天然地泛化到未见过的顶点。文中提出了 GraphSAGE，是一个 inductive 的框架，能够利用顶点特色信息（比方文本属性）来高效地为没有见过的顶点生成 embedding。GraphSAGE 是为了学习一种节点示意办法，即如何通过从一个顶点的部分街坊采样并聚合顶点特色，而不是为每个顶点训练独自的 embedding。
这个算法在三个 inductive 顶点分类 benchmark 上超过了那些很强的 baseline。文中基于 citation 和 Reddit 帖子数据的信息图中对未见过的顶点分类，试验表明应用一个 PPI（protein-protein interactions）多图数据集，算法能够泛化到齐全未见过的图上。

0.2 回顾 GCN 及其问题

在大型图中，节点的低维向量 embedding 被证实了作为各种各样的预测和图剖析工作的特色输出是十分有用的。顶点 embedding 最根本的根本思维是应用降维技术从高维信息中提炼一个顶点的街坊信息，存到低维向量中。这些顶点嵌入之后会作为后续的机器学习零碎的输出，解决像顶点分类、聚类、链接预测这样的问题。

• GCN 尽管能提取图中顶点的 embedding，然而存在一些问题：
• GCN 的根本思维：把一个节点在图中的高纬度邻接信息降维到一个低维的向量示意。
• GCN 的长处：能够捕获 graph 的全局信息，从而很好地示意 node 的特色。

• GCN 的毛病：Transductive learning 的形式，须要把所有节点都参加训练能力失去 node embedding，无奈疾速失去新 node 的 embedding。

  1. 图采样算法

  1.1 GraphSage: Representation Learning on Large Graphs

图采样算法：顾名思义，图采样算法就是在一张图中进行采样失去一个子图，这里的采样并不是随机采样，而是采取一些策略。典型的图采样算法包含 GraphSAGE、PinSAGE 等。

文章码源链接：

https://cs.stanford.edu/peopl…

https://github.com/williamlei…

后面 GCN 解说的文章中，我应用的图节点个数非常少，然而在理论问题中，一张图可能节点十分多，因而就没有方法一次性把整张图送入计算资源，所以咱们应该应用一种无效的采样算法，从全图中采样出一个子图，这样就能够进行训练了。

GraphSAGE 与 GCN 比照：

既然新增的节点，肯定会扭转原有节点的示意，那么为什么肯定要失去每个节点的一个固定的示意呢？何不间接学习一种节点的示意办法。去学习一个节点的信息是怎么通过其街坊节点的特色聚合而来的。学习到了这样的“聚合函数”，而咱们自身就已知各个节点的特色和街坊关系，咱们就能够很不便地失去一个新节点的示意了。

GCN 等 transductive 的办法，学到的是每个节点的一个惟一确定的 embedding；而 GraphSAGE 办法学到的 node embedding，是依据 node 的街坊关系的变动而变动的，也就是说，即便是旧的 node，如果建设了一些新的 link，那么其对应的 embedding 也会变动，而且也很不便地学到。

在理解图采样算法前，咱们至多应该保障采样后的子图是连通的。例如上图图中，右边采样的子图就是连通的，左边的子图不是连通的。

GraphSAGE 的外围：GraphSAGE 不是试图学习一个图上所有 node 的 embedding，而是学习一个为每个 node 产生 embedding 的映射。 GraphSage 框架中蕴含两个很重要的操作：Sample 采样和 Aggregate 聚合。这也是其名字 GraphSage(Graph SAmple and aggreGatE)的由来。GraphSAGE 次要分两步：采样、聚合。GraphSAGE 的采样形式是街坊采样，街坊采样的意思是在某个节点的街坊节点中抉择几个节点作为原节点的一阶街坊，之后对在新采样的节点的街坊中持续抉择节点作为原节点的二阶节点，以此类推。

文中不是对每个顶点都训练一个独自的 embeddding 向量，而是训练了一组 aggregator functions，这些函数学习如何从一个顶点的部分街坊聚合特色信息（见图 1）。每个聚合函数从一个顶点的不同的 hops 或者说不同的搜寻深度聚合信息。测试或是推断的时候，应用训练好的零碎，通过学习到的聚合函数来对齐全未见过的顶点生成 embedding。

GraphSAGE 是 Graph SAmple and aggreGatE 的缩写，其运行流程如上图所示，能够分为三个步骤：

• 对图中每个顶点街坊顶点进行采样，因为每个节点的度是不统一的，为了计算高效，为每个节点采样固定数量的街坊
• 依据聚合函数聚合街坊顶点蕴含的信息
• 失去图中各顶点的向量示意供上游工作应用

街坊采样的长处：

• 极大缩小计算量
• 容许泛化到新连贯关系，集体了解相似 dropout 的思维，能加强模型的泛化能力

采样的阶段首先选取一个点，而后随机选取这个点的一阶街坊，再以这些街坊为终点随机抉择它们的一阶街坊。例如下图中，咱们要预测 0 号节点，因而首先随机抉择 0 号节点的一阶街坊 2、4、5，而后随机抉择 2 号节点的一阶街坊 8、9；4 号节点的一阶街坊 11、12；5 号节点的一阶街坊 13、15

聚合具体来说就是间接将子图从全图中抽离进去，从最边缘的节点开始，一层一层向里更新节点

上图展现了街坊采样的长处，极大缩小训练计算量这个是毋庸置疑的，泛化能力加强这个可能不太好了解，因为本来要更新一个节点须要它四周的所有街坊，而通过街坊采样之后，每个节点就不是由所有的街坊来更新它，而是局部街坊节点，所以具备比拟强的泛化能力。

1.1.1 论文角度看 GraphSage

聚合函数的选取

在图中顶点的街坊是无序的，所以心愿结构出的聚合函数是对称的（即也就是对它输出的各种排列，函数的输入后果不变），同时具备较高的表达能力。聚合函数的对称性（symmetry property）确保了神经网络模型能够被训练且能够利用于任意程序的顶点街坊特色汇合上。

a. Mean aggregator ：
mean aggregator 将指标顶点和街坊顶点的第 $k−1$ 层向量拼接起来，而后对向量的每个维度进行求均值的操作，将失去的后果做一次非线性变换产生指标顶点的第 $k$ 层示意向量。

卷积聚合器 Convolutional aggregator：
文中用上面的式子替换算法 1 中的 4 行和 5 行失去 GCN 的 inductive 变形：

$$
\mathbf{h}_{v}^{k} \leftarrow \sigma\left(\mathbf{W} \cdot \operatorname{MEAN}\left(\left\{\mathbf{h}_{v}^{k-1}\right\} \cup\left\{\mathbf{h}_{u}^{k-1}, \forall u \in \mathcal{N}(v)\right\}\right)\right) $$

原始算法 1 中的第 4,5 行是

$$\begin{array}{l}
\mathbf{h}_{\mathcal{N}(v)}^{k} \leftarrow \operatorname{AGGREGATE}_{k}\left(\left\{\mathbf{h}_{u}^{k-1}, \forall u \in \mathcal{N}(v)\right\}\right) \\
\mathbf{h}_{v}^{k} \leftarrow \sigma\left(\mathbf{W}^{k} \cdot \operatorname{CONCAT}\left(\mathbf{h}_{v}^{k-1}, \mathbf{h}_{\mathcal{N}(v)}^{k}\right)\right)
\end{array}$$

** 论文提出的均值聚合器 Mean aggregator：**

$$\begin{array}{l}
\mathbf{h}_{v}^{k} \leftarrow \sigma\left(\mathbf{W} \cdot \operatorname{MEAN}\left(\left\{\mathbf{h}_{v}^{k-1}\right\} \cup\left\{\mathbf{h}_{u}^{k-1}, \forall u \in \mathcal{N}(v)\right\}\right)\right) \\
\mathbf{h}_{v}^{k} \leftarrow \sigma\left(\mathbf{W}^{k} \cdot \operatorname{CONCAT}\left(\mathbf{h}_{v}^{k-1}, \mathbf{h}_{\mathcal{N}(v)}^{k}\right)\right)
\end{array}$$

* 均值聚合近似等价在 transducttive GCN 框架中的卷积流传规定
* 这个批改后的基于均值的聚合器是 convolutional 的。然而这个卷积聚合器和文中的其余聚合器的重要不同在于它没有算法 1 中第 5 行的 CONCAT 操作——卷积聚合器没有将顶点前一层的示意 $\mathbf{h}^{k-1}_{v}$ 聚合的街坊向量 $\mathbf{h}^k_{\mathcal{N}(v)}$ 拼接起来
* 拼接操作能够看作一个是 GraphSAGE 算法在不同的搜寻深度或层之间的简略的 **skip connection**[Identity mappings in deep residual networks]的模式，它使得模型的表征性能取得了微小的晋升
* 举个简略例子，比方一个节点的 3 个街坊的 embedding 别离为 [1,2,3,4],[2,3,4,5],[3,4,5,6] 依照每一维别离求均值就失去了聚合后的街坊 embedding 为[2,3,4,5]

**b. LSTM aggregator**

文中也测试了一个基于 LSTM 的简单的聚合器[Long short-term memory]。和均值聚合器相比，LSTMs 有更强的表达能力。然而，LSTMs 不是对称的（symmetric），也就是说不具备排列不变性（permutation invariant），因为它们以一个序列的形式解决输出。因而，须要先对街坊节点 ** 随机程序 **，而后将街坊序列的 embedding 作为 LSTM 的输出。

* 排列不变性（permutation invariance）：指输出的程序扭转不会影响输入的值。

**c. Pooling aggregator**

pooling 聚合器，它既是对称的，又是可训练的。Pooling aggregator 先对指标顶点的街坊顶点的 embedding 向量进行一次非线性变换，之后进行一次 pooling 操作(max pooling or mean pooling)，将失去后果与指标顶点的示意向量拼接，最初再通过一次非线性变换失去指标顶点的第 k 层示意向量。
一个 element-wise max pooling 操作利用在街坊汇合上来聚合信息：

$$\begin{aligned}
\mathbf{h}_{\mathcal{N}(v)}^{k}=& \mathrm{AGGREGATE}_{k}^{\text {pool}}=\max \left(\left\{\sigma\left(\mathbf{W}_{\text {pool}} \mathbf{h}_{u}^{k-1}+\mathbf{b}\right), \forall u \in \mathcal{N}(v)\right\}\right) \\
&\mathbf{h}_{v}^{k} \leftarrow \sigma\left(\mathbf{W}^{k} \cdot \operatorname{CONCAT}\left(\mathbf{h}_{v}^{k-1}, \mathbf{h}_{\mathcal{N}(v)}^{k}\right)\right)
\end{aligned}$$

其中

* $max$ 示意 element-wise 最大值操作，取每个特色的最大值
* $\sigma$ 是非线性激活函数
* 所有相邻节点的向量共享权重，先通过一个非线性全连贯层，而后做 max-pooling
* 按维度利用 max/mean pooling，能够捕捉街坊集上在某一个维度的突出的/综合的体现。

####（有监督和无监督）参数学习

在定义好聚合函数之后，接下来就是对函数中的参数进行学习。文章别离介绍了无监督学习和监督学习两种形式。

** 基于图的无监督损失 **

基于图的损失函数偏向于使得相邻的顶点有类似的示意，但这会使互相远离的顶点的示意差别变大：

$$J \mathcal{G}\left(\mathbf{z}_{u}\right)=-\log \left(\sigma\left(\mathbf{z}_{u}^{T} \mathbf{z}_{v}\right)\right)-Q \cdot \mathbb{E}_{v_{n} \sim P_{n}(v)} \log \left(\sigma\left(-\mathbf{z}_{u}^{T} \mathbf{z}_{v_{n}}\right)\right)$$

其中
* $\mathbf{z}_{u}$ 为节点 $u$ 通过 GraphSAGE 生成的 embedding
* 节点 $v$ 是节点 $u$ 随机游走达到的“街坊”
* $\sigma$ 是 sigmoid 函数
* $P_{n}$ 是负采样的概率分布，相似 word2vec 中的负采样
* $Q$ 是负样本的数目
* embedding 之间类似度通过向量点积计算失去

文中输出到损失函数的示意 $\mathbf{z}_u$ 是从蕴含一个顶点部分街坊的特色生成进去的，而不像之前的那些办法（如 DeepWalk），对每个顶点训练一个举世无双的 embedding，而后简略进行一个 embedding 查找操作失去。

** 基于图的有监督损失 **

无监督损失函数的设定来学习节点 embedding 能够供上游多个工作应用。监督学习模式依据工作的不同间接设置指标函数即可，如最罕用的节点分类工作应用穿插熵损失函数。

** 参数学习 **

通过前向流传失去节点 $u$ 的 embedding $z_u$, 而后梯度降落（实现应用 Adam 优化器）进行反向流传优化参数 $\mathbf{W}^{k}$ 和聚合函数内的参数。

** 新节点 embedding 的生成 **

这个 $\mathbf{W}^{k}$ 就是所谓的 dynamic embedding 的外围，因为保留下来了从节点原始的高维特色生成低维 embedding 的形式。当初，如果想得到一个点的 embedding，只须要输出节点的特征向量，通过卷积（利用曾经训练好的 $\mathbf{W}^{k}$ 以及特定聚合函数聚合 neighbor 的属性信息），就产生了节点的 embedding。

** 有了 GCN 为啥还要 GraphSAGE？**

“`
GCN 灵活性差、为新节点产生 embedding 要求 额定的操作，比方“对齐”：

GCN 是 直推式（transductive）学习，无奈间接泛化到新退出（未见过）的节点；
GraphSAGE 是 演绎式（inductive）学习，能够为新节点输入节点特色。
GCN 输入固定：

GCN 输入的是节点 惟一确定 的 embedding；
GraphSAGE 学习的是节点和邻接节点之间的关系，学习到的是一种 映射关系，节点的 embedding 能够随着其邻接节点的变动而变动。
GCN 很难利用在超大图上：

无论是拉普拉斯计算还是图卷积过程，因为 GCN 其须要对 整张图 进行计算，所以计算量会随着节点数的减少而递增。
GraphSAGE 通过采样，可能造成 minibatch 来进行批训练，能用在超大图上
“`

**GraphSAGE 有什么长处？**

“`
采纳 演绎学习 的形式，学习街坊节点特色关系，失去泛化性更强的 embedding；
采样技术，升高空间复杂度，便于构建 minibatch 用于 批训练，还让模型具备更好的泛化性；
多样的聚合函数，对于不同的数据集 / 场景能够选用不同的聚合形式，使得模型更加灵便。
“`
** 采样数大于邻接节点数怎么办？**
“`
设采样数量为 K：

若节点街坊数少于 K，则采纳 有放回 的抽样办法，直到采样出 K 个节点。
若节点街坊数大于 K，则采纳 无放回 的抽样。
“`

** 训练好的 GraphSAGE 如何失去节点 Embedding？**
“`
假如 GraphSAGE 曾经训练好，咱们能够通过以下步骤来取得节点 embedding，具体算法请看下图的算法 1。

训练过程则只须要将其产生的 embedding 扔进损失函数计算并反向梯度流传即可。

对图中每个节点的邻接节点进行 采样，输出节点及其 n 阶邻接节点的特征向量
依据 K 层的 聚合函数 聚合邻接节点的信息
就产生了各节点的 embedding
“`

**minibatch 的子图是怎么失去的？**


那 ** 和 DeepWalk、Node2vec 这些有什么不一样？**
“`
DeepWalk、Node2Vec 这些 embedding 算法间接训练每个节点的 embedding，实质上仍然是直推式学习，而且须要大量的额定训练能力使他们能预测新的节点。同时，对于 embedding 的正交变换（orthogonal transformations），这些办法的指标函数是不变的，这意味着生成的向量空间在不同的图之间不是人造泛化的，在再次训练（re-training）时会产生漂移（drift）。

与 DeepWalk 不同的是，GraphSAGE 是通过聚合节点的邻接节点特色产生 embedding 的，而不是简略的进行一个 embedding lookup 操作失去。
“`
论文仿真后果：

试验比照了四个基线：随机分类，基于特色的逻辑回归（疏忽图构造），DeepWalk 算法，DeepWork+ 特色；同时还比照了四种 GraphSAGE，其中三种在 3.3 节中曾经阐明，GraphSAGE-GCN 是 GCNs 的演绎版本。具体超参数为：K=2，s1=25，s2=10。程序应用 TensorFlow 编写，Adam 优化器。


对于跨图泛化的工作，须要学习节点角色而不是训练图的构造。应用跨各种生物蛋白质 - 蛋白质相互作用 (PPI) 图，对蛋白质性能进行分类。在 20 个图表上训练算法，2 个图用于测试，2 个图用于验证，均匀每图蕴含 2373 个节点，均匀度为 28.8。从试验后果能够看出 LSTM 和池化办法比 Mean 和 GCN 成果更好。

比照不同聚合函数：

如表 - 1 所示，LSTM 和 POOL 办法成果最好，与其它办法相比有显著差别，LSTM 和 POOL 之间无显著差别，但 LSTM 比 POOL 慢得多(≈2x)，使 POOL 聚合器在总体上略有劣势。

### 1.1.2 更多问题
“`
采样
为什么要采样？
采样数大于邻接节点数怎么办？
采样的街坊节点数应该选取多大？
每一跳采样须要一样吗？
适宜有向边吗？
采样是随机的吗？

聚合函数
聚合函数的选取有什么要求？
GraphSAGE 论文中提供多少种聚合函数？
均值聚合的操作是怎么的？
pooling 聚合的操作是怎么的？
应用 LSTM 聚合时须要留神什么？
均值聚合和其余聚合函数有啥区别？
max- 和 mean-pooling 有什么区别？
这三种聚合办法，哪种比拟好？
个别聚合多少层？层数越多越好吗？
什么时候和 GCN 的聚合模式“等价”？

无监督学习
GraphSAGE 怎么进行无监督学习？
GraphSAGE 如何定义邻近和远处的节点？
如何计算无监督 GraphSAGE 的损失函数？
GraphSAGE 是怎么随机游走的？
GraphSAGE 什么时候思考边的权重了？

训练
如果只有图、没有节点特色，是否应用 GraphSAGE？
训练好的 GraphSAGE 如何失去节点 Embedding？
minibatch 的子图是怎么失去的？
减少了新的节点来训练，须要为所有“旧”节点从新输入 embeding 吗？
GraphSAGE 有监督学习有什么不一样的中央吗？
“`
参考链接：https://zhuanlan.zhihu.com/p/184991506

https://blog.csdn.net/yyl424525/article/details/100532849

## 1.2 PinSAGE


采样时只能选取实在的街坊节点吗？如果构建的是一个与虚构街坊相连的子图有什么长处？PinSAGE 算法将会给咱们解答，PinSAGE 算法通过屡次随机游走，按游走通过的频率选取街坊，上图右侧为进行随机游走失去的节点序列，统计序列的频数能够发现节点 5,10,11 的频数为 2，其余为 1，当咱们心愿采样三个节点时，咱们选取 5,10,11 作为 0 号节点的虚构街坊。之后如果心愿失去 0 号节点的二阶虚构街坊则在已采样的节点持续进行随机游走即可。

回到上述问题，采样时选取虚构街坊有什么益处？** 这种采样形式的益处是咱们能更快的聚合到远处节点的信息。**。实际上如果是依照 GraphSAGE 算法的形式生成子图，在聚合的过程中，非一阶街坊的信息能够通过消息传递逐步传到核心，然而随着间隔的增大，离核心越远的节点，其信息在传递过程中就越艰难，甚至可能无奈传递到；如果依照 PinSAGE 算法的形式生成子图，有肯定的概率能够将非一阶街坊与核心间接相连，这样就能够疾速聚合到多阶街坊的信息

### 1.2.1 论文角度看 PinSAGE


** 和 GraphSAGE 相比，PinSAGE 改良了什么？**
* 采样：应用重要性采样代替 GraphSAGE 的平均采样；
* 聚合函数：聚合函数思考了边的权重；
* 生产者 - 消费者模式的 minibatch 构建：在 CPU 端采样节点和构建特色，构建计算图；在 GPU 端在这些子图上进行卷积运算；从而能够低提早地随机游走构建子图，而不须要把整个图存在显存中。
* 高效的 MapReduce 推理：能够分布式地为百万以上的节点生成 embedding，最大化地缩小反复计算。
这里的计算图，指的是用于卷积运算的部分图（或者叫子图），通过采样来造成；与 TensorFlow 等框架的计算图不是一个概念。

**PinSAGE 应用多大的计算资源？**
“`
训练时，PinSAGE 应用 32 核 CPU、16 张 Tesla K80 显卡、500GB 内存；
推理时，MapReduce 运行在 378 个 d2.8xlarge Amazon AWS 节点的 Hadoop2 集群。
“`

**PinSAGE 和 node2vec、DeepWalk 这些有啥区别？**
“`
node2vec，DeepWalk 是无监督训练；PinSAGE 是有监督训练；
node2vec，DeepWalk 不能利用节点特色；PinSAGE 能够；
node2vec，DeepWalk 这些模型的参数和节点数呈线性关系，很难利用在超大型的图上；
“`
**PinSAGE 的单层聚合过程是怎么的？**

和 GraphSAGE 一样，PinSAGE 的外围就是一个 部分卷积算子，用来学习如何聚合街坊节点信息。

如下图算法 1 所示，PinSAGE 的聚合函数叫做 CONVOLVE。次要分为 3 局部：

* 聚合（第 1 行）：k- 1 层街坊节点的表征通过一层 DNN，而后聚合（能够思考边的权重），是聚合函数符号，聚合函数能够是 max/mean-pooling、加权求和、求均匀；
* 更新（第 2 行）：拼接 第 k - 1 层指标节点的 embedding，而后再通过另一层 DNN，造成指标节点新的 embedding；
* 归一化（第 3 行）：归一化 指标节点新的 embedding，使得训练更加稳固；而且归一化后，应用近似最近街坊搜寻的效率更高。


**PinSAGE 是如何采样的？**
“`
如何采样这个问题从另一个角度来看就是：如何为指标节点构建街坊节点。

和 GraphSAGE 的平均采样不一样的是，PinSAGE 应用的是重要性采样。

PinSAGE 对街坊节点的定义是：对指标节点 影响力最大 的 T 个节点。
“`

**PinSAGE 的街坊节点的重要性是如何计算的？**
“`
其影响力的计算方法有以下步骤：

从指标节点开始随机游走；
应用 正则 来计算节点的“拜访次数”，失去重要性分数；
指标节点的街坊节点，则是重要性分数最高的前 T 个节点。

这个重要性分数，其实能够近似看成 Personalized PageRank 分数。

对于随机游走，能够浏览《Pixie: A System for Recommending 3+ Billion Items to 200+ Million Users in Real-Time》
“`
** 重要性采样的益处是什么？**
“`
和 GraphSAGE 一样，能够使得 街坊节点的数量固定，便于管制内存 / 显存的应用。
在聚合街坊节点时，能够思考节点的重要性；在 PinSAGE 实际中，应用的就是 加权均匀（weighted-mean），原文把它称作 importance pooling。
“`
** 采样的大小是多少比拟好？**
“`
从 PinSAGE 的试验能够看出，随着街坊节点的减少，而收益会递加；

并且两层 GCN 在 街坊数为 50 时可能更好的抓取节点的街坊信息，同时放弃运算效率。
“`

**PinSage 论文中还介绍了落地过程中采纳的大量工程技巧。**

1. ** 负样本生成 **：首先是简略采样：在每个 minibatch 蕴含节点的范畴之外随机采样 500 个 item 作为 minibatch 所有正样本共享的负样本汇合。但思考到理论场景中模型须要从 20 亿的物品 item 汇合中辨认出最类似的 1000 个，即要从 2 百万中辨认出最类似的那一个，只是简略采样会导致模型分辨的粒度过粗，分辨率只到 500 分之一，因而减少一种“hard”负样本，即对于每个 对，和物品 q 有些类似但和物品 i 不相干的物品汇合。这种样本的生成形式是将图中节点依据绝对节点 q 的个性化 PageRank 分值排序，随机选取排序地位在 2000~5000 的物品作为“hard”负样本，以此进步模型分辨正负样本的难度。

2. ** 渐进式训练(Curriculum training**：如果训练全程都应用 hard 负样本，会导致模型收敛速度减半，训练时长加倍，因而 PinSage 采纳了一种 Curriculum 训练的形式，这里我了解是一种渐进式训练方法，即第一轮训练只应用简略负样本，帮忙模型参数疾速收敛到一个 loss 比拟低的范畴；后续训练中逐渐退出 hard 负样本，让模型学会将很类似的物品与些微类似的辨别开，形式是第 n 轮训练时给每个物品的负样本汇合中减少 n - 1 个 hard 负样本。

3. ** 样本的特色信息 **：Pinterest 的业务场景中每个 pin 通常有一张图片和一系列的文字标注（题目，形容等），因而原始图中每个节点的特色示意由图片 Embedding（4096 维），文字标注 Embedding（256 维），以及节点在图中的度的 log 值拼接而成。其中图片 Embedding 由 6 层全连贯的 VGG-16 生成，文字标注 Embedding 由 Word2Vec 训练失去。

4. ** 基于 random walk 的重要性采样 **：用于街坊节点采样，这一技巧在下面的算法了解局部曾经解说过，此处不再赘述。

5. ** 基于重要性的池化操作 **：这一技巧用于上一节 Convolve 算法中的 函数中，聚合通过一层 dense 层之后的街坊节点 Embedding 时，基于 random walk 计算出的节点权重做聚合操作。据论文形容，这一技巧在离线评估指标中晋升了 46%。

6. **on-the-fly convolutions：疾速卷积操作 **，这个技巧次要是绝对原始 GCN 中的卷积操作：特色矩阵与全图拉普拉斯矩阵的幂相乘。波及到全图的都是计算量超高，这里 GraphSage 和 PinSage 都是统一地应用采样街坊节点动静构建部分计算图的办法晋升训练效率，只是二者采样的形式不同。

7. ** 生产者消费者模式构建 minibatch**：这个点次要是为了进步模型训练时 GPU 的利用率。保留原始图构造的街坊表和数十亿节点的特色矩阵只能放在 CPU 内存中，GPU 执行 convolve 卷积操作时每次从 CPU 取数据是很耗时的。为了解决这个问题，PinSage 应用 re-index 技术创立以后 minibatch 内节点及其街坊组成的子图，同时从数十亿节点的特色矩阵中提取出该子图节点对应的特色矩阵，留神提取后的特色矩阵中的节点索引要与后面子图中的索引保持一致。这个子图的邻接列表和特色矩阵作为一个 minibatch 送入 GPU 训练，这样一来，convolve 操作过程中就没有 GPU 与 CPU 的通信需要了。训练过程中 CPU 应用 OpenMP 并设计了一个 producer-consumer 模式，CPU 负责提取特色，re-index，负采样等计算，GPU 只负责模型计算。这个技巧升高了一半的训练耗时。

8. ** 多 GPU 训练超大 batch**：前向流传过程中，各个 GPU 等分 minibatch，共享一套参数，反向流传时，将每个 GPU 中的参数梯度都聚合到一起，执行同步 SGD。为了适应海量训练数据的须要，增大 batchsize 从 512 到 4096。为了在超大 batchsize 下疾速收敛保障泛化精度，采纳 warmup 过程：在第一个 epoch 中将学习率线性晋升到最高，前面的 epoch 中再逐渐指数降落。

9. ** 应用 MapReduce 高效推断 **：模型训练实现后生成图中各个节点的 Embedding 过程中，如果间接应用上述 PinSage 的 minibatch 算法生 Embedding，会有大量的反复计算，如计算以后 target 节点的时候，其相当一部分街坊节点曾经计算过 Embedding 了，而当这些街坊节点作为 target 节点的时候，以后 target 节点极有可能须要再从新计算一遍，这一部分的反复计算既耗时又节约。

### 1.2.2 更多问题

“`
聚合函数
PinSAGE 的单层聚合过程是怎么的？
为什么要将街坊节点的聚合 embedding 和以后节点的拼接？

采样
PinSAGE 是如何采样的？
PinSAGE 的街坊节点的重要性是如何计算的？
重要性采样的益处是什么？
采样的大小是多少比拟好？

MiniBatch
PinSAGE 的 minibatch 和 GraphSAGE 有啥不一样？
batch 应该选多大？

训练
PinSAGE 应用什么损失函数？
PinSAGE 如何定义标签(正例 / 负例)？
PinSAGE 用什么办法进步模型训练的鲁棒性和收敛性？

负采样
PinSAGE 如何进行负采样？
训练时简略地负采样，会有什么问题？
如何解决简略负采样带来的问题？
如果只应用“hard”负样本，会有什么问题？
如何解决只应用“hard”负采样带来的问题？
如何辨别采样、负采样、”hard“负采样？

推理
间接为应用训练好的模型产生 embedding 有啥问题？
如何解决推理时反复计算的问题？
上游工作如何利用 PinSAGE 产生的 embedding？
如何为用户进行个性化举荐？

工程性技巧
pin 样本的特色如何构建？
board 样本的特色如何构建？
如何应用多 GPU 并行训练 PinSAGE？
PinSAGE 为什么要应用生产者 - 消费者模式？
PinSAGE 是如何应用生产者 - 消费者模式？
“`
https://zhuanlan.zhihu.com/p/195735468

https://zhuanlan.zhihu.com/p/133739758?utm_source=wechat_session&utm_id=0

## 1.3 小结

学习大图、一直扩大的图，未见过节点的表征，是一个很常见的利用场景。GraphSAGE 通过训练聚合函数，实现优化未知节点的示意办法。之后提出的 GAN（图注意力网络）也针对此问题优化。
论文中提出了：传导性问题和演绎性问题，传导性问题是已知全图状况，计算节点表征向量；演绎性问题是在不齐全理解全图的状况下，训练节点的表征函数（不是间接计算向量示意）。
图工具的处理过程每轮迭代（一次 propagation）个别都蕴含：收集信息、聚合、更新，从本文也能够更好地了解，其中聚合的重要性，及优化办法。

GraohSage 次要奉献如下：
* 针对问题：大图的节点表征
* 后果：训练出的模型可利用于表征没见过的节点
* 外围办法：改良图卷积办法；从街坊节点中采样；思考了节点特色，退出更简单的特色聚合办法

个别状况下一个节点的表式通过聚合它 k 跳之内的邻近节点计算，而全图的示意则通过对所有节点的池化计算。GIN 应用了 WL-test 办法，即图同构测试，它是一个辨别网络结构的强效办法，也是通过迭代聚合街坊的办法来更新节点，它的弱小在于应用了 injective（见后）聚合更新办法。而这里要评测 GNN 是否能达到相似 WL-test 的成果。文中还应用了多合集 multiset 的概念，指可能蕴含反复元素的汇合。

GIN 次要奉献如下：

* 展现了 GNN 模型可达到与 WL-test 相似的图构造辨别成果
* 设计了聚合函数和 Readout 函数，使 GNN 能达到更好的辨别成果
* 发现 GCN 及 GraphSAGE 无奈很好表白图构造，而 GNN 能够
* 开发了简略的网络结构 GIN（图同构网络），它的辨别和示意能力与 WL-test 相似。

# 2. 街坊聚合

在图采样之后，咱们须要进行街坊聚合的操作。经典的街坊聚合函数包含取均匀、取最大值、求和。

评估聚合表达能力的指标——单射（一对一映射），在上述三种经典聚合函数中，取均匀偏向于学习散布，取最大值偏向于疏忽反复值，这两个不属于单射，而求和可能保留街坊节点的残缺信息，是单射。单射的益处是能够保障对聚合后的后果可辨别。


## 2.1 GIN 模型的聚合函数

Graph Isomorphic Net（GIN）的聚合局部是基于单射的。

如上图所示，GIN 的聚合函数应用的是求和函数，它非凡的一点是在核心节点加了一个自连边（自环），之后对自连边进行加权。

这样做的益处是即便咱们调换了核心节点和街坊节点，失去的聚合后果仍旧是不同的。所以带权重的自连边可能保障核心节点和街坊节点可辨别。


## 2.2 其余简单的聚合函数


## 2.3 令居聚合语义场景


# 3. 数据集介绍

数据源：http://snap.stanford.edu/graphsage/ 斯坦福

## 3.1 Citation 数据集

应用科学网引文数据集，将学术论文分类为不同的主题。数据集共蕴含 302424 个节点，均匀度 9.15，应用 2000-2004 年数据作为训练集，2005 年数据作为测试集。应用节点的度以及论文摘要的句嵌入作为特色。

## 3.2 Reddit 数据集

https://aistudio.baidu.com/aistudio/datasetdetail/177810

将 Reddit 帖子归类为属于不同社区。数据集蕴含 232965 个帖子，均匀度为 492。应用现成的 300 维 GloVe Common Crawl 单词向量；对于每个帖子，应用特色蕴含：(1) 帖子题目的均匀嵌入 (2) 帖子所有评论的均匀嵌入 (3) 帖子的分数 (4)帖子的评论数量

为了对社区进行抽样，依据 2014 年的评论总数对社区进行了排名，并抉择了排名 [11,50]（含）的社区。省略了最大的社区，因为它们是大型的通用默认社区，大大扭曲了类散布。抉择了在这些社区的联结上定义的图中最大的连通重量。

更多数据资料见：

http://files.pushshift.io/reddit/comments/

https://github.com/dingidng/reddit-dataset


最新数据曾经更新到 2022.10 了

## 3.3 PPI（Protein–protein interactions）蛋白质交互作用

https://aistudio.baidu.com/aistudio/datasetdetail/177807

PPI 网络是蛋白质相互作用（Protein-Protein Interaction,PPI）网络的简称，在 GCN 中次要用于节点分类工作

PPI 是指两种或以上的蛋白质联合的过程，通常旨在执行其生化性能。

个别地，如果两个蛋白质独特参加一个生命过程或者协同实现某一性能，都被看作这两个蛋白质之间存在相互作用。多个蛋白质之间的简单的相互作用关系能够用 PPI 网络来形容。

PPI 数据集共 24 张图，每张图对应不同的人体组织，均匀每张图有 2371 个节点，共 56944 个节点 818716 条边，每个节点特色长度为 50，其中蕴含地位基因集，基序集和免疫学特色。基因本体基作为 label(总共 121 个)，label 不是 one-hot 编码。

* alid_feats.npy 文件保留节点的特色，shape 为(56944, 50)(节点数目，特色维度)，值为 0 或 1，且 1 的数目稀少

* ppi-class_map.json 为节点的 label 文件，shape 为(121, 56944), 每个节点的 label 为 121 维

* ppi-G.json 文件为节点和链接的形容信息，节点：{“test”: true, “id”: 56708, “val”: false}, 示意节点 id 为 56708 的节点是否为 test 集或者 val 集，链接：”links”: [{“source”: 0, “target”: 372}, {“source”: 0, “target”: 1101}, 示意节点 id 为 0 的节点和为 1101 的节点之间有 links，

* ppi-walks.txt 文件中为链接信息

* ppi-id_map.json 文件为节点 id 信息

参考链接：

https://blog.csdn.net/ziqingnian/article/details/112979175

# 4 基于 PGL 算法实际

## 4.1 GraphSAGE

GraphSAGE 是一个通用的演绎框架，它利用节点特色信息（例如，文本属性）为以前看不见的数据无效地生成节点嵌入。GraphSAGE 不是为每个节点训练独自的嵌入，而是学习一个函数，该函数通过从节点的本地邻域中采样和聚合特色来生成嵌入。基于 PGL，咱们重现了 GraphSAGE 算法，在 Reddit Dataset 中达到了与论文等同程度的指标。此外，这是 PGL 中子图采样和训练的一个例子。

超参数
“`
epoch: Number of epochs default (10)
normalize: Normalize the input feature if assign normalize.
sample_workers: The number of workers for multiprocessing subgraph sample.
lr: Learning rate.
symmetry: Make the edges symmetric if assign symmetry.
batch_size: Batch size.
samples: The max neighbors for each layers hop neighbor sampling. (default: [25, 10])
hidden_size: The hidden size of the GraphSAGE models.

“`

“`
parser = argparse.ArgumentParser(description=’graphsage’)
parser.add_argument(
“–normalize”, action=’store_true’, help=”normalize features”) # normalize：归一化节点特色
parser.add_argument(
“–symmetry”, action=’store_true’, help=”undirect graph”) # symmetry：聚合函数的对称性
parser.add_argument(“–sample_workers”, type=int, default=5) # sample_workers：多线程数据读取器的线程个数
parser.add_argument(“–epoch”, type=int, default=10)
parser.add_argument(“–hidden_size”, type=int, default=128)
parser.add_argument(“–batch_size”, type=int, default=128)
parser.add_argument(“–lr”, type=float, default=0.01)
parser.add_argument(‘–samples’, nargs=’+’, type=int, default=[25, 10]) # samples_1：第一级街坊采样时候抉择的最大街坊个数（默认 25）#,samples_2：第而级街坊采样时候抉择的最大街坊个数（默认 10）
“`
局部后果展现：

“`
[INFO] 2022-11-18 16:45:44,177 [train.py: 63]: Batch 800 train-Loss [0.5213774] train-Acc [0.9140625]
[INFO] 2022-11-18 16:45:45,783 [train.py: 63]: Batch 900 train-Loss [0.65641916] train-Acc [0.875]
[INFO] 2022-11-18 16:45:47,385 [train.py: 63]: Batch 1000 train-Loss [0.57411766] train-Acc [0.921875]
[INFO] 2022-11-18 16:45:48,977 [train.py: 63]: Batch 1100 train-Loss [0.68337256] train-Acc [0.890625]
[INFO] 2022-11-18 16:45:50,434 [train.py: 160]: Runing epoch:9 train_loss:[0.58635516] train_acc:[0.90786038]
[INFO] 2022-11-18 16:45:57,836 [train.py: 165]: Runing epoch:9 val_loss:0.55885834 val_acc:0.9139818
[INFO] 2022-11-18 16:46:05,259 [train.py: 169]: Runing epoch:9 test_loss:0.5578749 test_acc:0.91468066
100%|███████████████████████████████████████████| 10/10 [06:02<00:00, 36.29s/it]
[INFO] 2022-11-18 16:46:05,260 [train.py: 172]: Runs 0: Model: graphsage Best Test Accuracy: 0.918849
“`

目前官网最佳性能是 95.7%，我这里没有调参

| Aggregator | Accuracy_me_10 epochs | Accuracy_200 epochs|Reported in paper_200 epochs|
| ——– | ——– | ——– |——– |
| Mean | 91.88% | 95.70% | 95.0% |

其余聚合器下官网和论文性能比照：

| Aggregator | Accuracy_200 epochs|Reported in paper_200 epochs|
| ——– | ——– |——– |
| Meanpool | 95.60% | 94.8% |
| Maxpool | 94.95% | 94.8% |
| LSTM | 95.13% | 95.4% |

## 4.2 Graph Isomorphism Network (GIN)

图同构网络（GIN）是一个简略的图神经网络，冀望达到 Weisfeiler-Lehman 图同构测试的能力。基于 PGL 重现了 GIN 模型。

超参数
* data_path：数据集的根门路
* dataset_name：数据集的名称
* fold_idx：拆分的数据集折叠。这里咱们应用 10 折穿插验证
* train_eps：是否参数是可学习的。

“`
parser.add_argument(‘–data_path’, type=str, default=’./gin_data’)
parser.add_argument(‘–dataset_name’, type=str, default=’MUTAG’)
parser.add_argument(‘–batch_size’, type=int, default=32)
parser.add_argument(‘–fold_idx’, type=int, default=0)
parser.add_argument(‘–output_path’, type=str, default=’./outputs/’)
parser.add_argument(‘–use_cuda’, action=’store_true’)
parser.add_argument(‘–num_layers’, type=int, default=5)
parser.add_argument(‘–num_mlp_layers’, type=int, default=2)
parser.add_argument(‘–feat_size’, type=int, default=64)
parser.add_argument(‘–hidden_size’, type=int, default=64)
parser.add_argument(
‘–pool_type’,
type=str,
default=”sum”,
choices=[“sum”, “average”, “max”])
parser.add_argument(‘–train_eps’, action=’store_true’)
parser.add_argument(‘–init_eps’, type=float, default=0.0)
parser.add_argument(‘–epochs’, type=int, default=350)
parser.add_argument(‘–lr’, type=float, default=0.01)
parser.add_argument(‘–dropout_prob’, type=float, default=0.5)
parser.add_argument(‘–seed’, type=int, default=0)
args = parser.parse_args()
“`
GIN github 代码复现含数据集下载：How Powerful are Graph Neural Networks? [https://github.com/weihua916/powerful-gnns](https://github.com/weihua916/powerful-gnns)

https://github.com/weihua916/powerful-gnns/blob/master/dataset.zip

论文应用 9 个图形分类基准：**4 个生物信息学数据集（MUTAG、PTC、NCI1、PROTEINS）** 和 **5 个社交网络数据集（COLLAB、IMDB-BINARY、IMDB-MULTI、REDDITBINARY 和 REDDIT-MULTI5K）（Yanardag & Vishwanathan，2015）**。重要的是，我指标不是让模型依赖输出节点特色，而是次要从网络结构中学习。因而，在生物信息图中，节点具备分类输出特色，但在社交网络中，它们没有特色。对于社交网络，按如下形式创立节点特色：对于 REDDIT 数据集，将所有节点特征向量设置为雷同（因而，这里的特色是无信息的）；对于其余社交图，咱们应用节点度数的 one-hot 编码。

** 社交网络数据集。**

* IMDB-BINARY 和 IMDB-MULTI 是电影合作数据集。每个图对应于每个演员 / 女演员的自我网络，其中节点对应于演员 / 女演员，如果两个演员 / 女演员呈现在同一部电影中，则在两个演员 / 女演员之间绘制一条边。每个图都是从预先指定的电影类型派生的，工作是对其派生的类型图进行分类。

* REDDIT-BINARY 和 REDDIT-MULTI5K 是均衡数据集，其中每个图表对应一个在线探讨线程，节点对应于用户。如果其中至多一个节点回应了另一个节点的评论，则在两个节点之间绘制一条边。工作是将每个图分类到它所属的社区或子版块。

* COLLAB 是一个迷信合作数据集，源自 3 个公共合作数据集，即高能物​​理、凝聚态物理和天体物理。每个图对应于来自每个畛域的不同钻研人员的自我网络。工作是将每个图分类到相应钻研人员所属的畛域。

** 生物信息学数据集。**

* MUTAG 是一个蕴含 188 个诱变芳香族和杂芳香族硝基化合物的数据集，具备 7 个离散标签。

* PROTEINS 是一个数据集，其中节点是二级构造元素 (SSE)，如果两个节点在氨基酸序列或 3D 空间中是相邻节点，则它们之间存在一条边。它有 3 个离散标签，代表螺旋、薄片或转弯。

* PTC 是一个蕴含 344 种化合物的数据集，报告了雄性和雌性大鼠的致癌性，它有 19 个离散标签。

* NCI1 是由美国国家癌症研究所 (NCI) 公开提供的数据集，是通过筛选以克制或克制一组人类肿瘤细胞系成长的化学化合物均衡数据集的子集，具备 37 个离散标签。
局部后果展现：
“`
[INFO] 2022-11-18 17:12:34,203 [main.py: 98]: eval: epoch 347 | step 2082 | | loss 0.448468 | acc 0.684211
[INFO] 2022-11-18 17:12:34,297 [main.py: 98]: eval: epoch 348 | step 2088 | | loss 0.393809 | acc 0.789474
[INFO] 2022-11-18 17:12:34,326 [main.py: 92]: train: epoch 349 | step 2090 | loss 0.401544 | acc 0.8125
[INFO] 2022-11-18 17:12:34,391 [main.py: 98]: eval: epoch 349 | step 2094 | | loss 0.441679 | acc 0.736842
[INFO] 2022-11-18 17:12:34,476 [main.py: 92]: train: epoch 350 | step 2100 | loss 0.573693 | acc 0.7778
[INFO] 2022-11-18 17:12:34,485 [main.py: 98]: eval: epoch 350 | step 2100 | | loss 0.481966 | acc 0.789474
[INFO] 2022-11-18 17:12:34,485 [main.py: 103]: best evaluating accuracy: 0.894737
“`

后果整合：（这里就不把数据集一一跑一遍了）

| | MUTAG | COLLAB | IMDBBINARY | IMDBMULTI |
| ——– | ——– | ——– |——– | ——– |
| PGL result | 90.8 | 78.6 |76.8 |50.8|
| paper reuslt | 90.0 | 80.0 | 75.1 | 52.3 |

原论文所有后果：