图神经网络

github版本在这里，最好用谷歌浏览器

【图神经网络】文献阅读笔记

最近在研究图神经网络相关的内容，所以写下这篇阅读笔记。个人能力有限，所以如果您在阅读的过程中找出了错误请务必指出。另不吝赐教，相互交流学习。本文也会持续更新。😛

个人认为GNN是目前来看，唯一一个能对抗Transformer的框架了。另外，深度学习条件下的GNN的历史虽然差不多和Transformer一样，但对于GNN的研究还差得太多，因此还不够深刻和彻底，这就导致了性能和应用两方面的拉胯。不过也正是GNN的各种研究方面的缺陷才让我们有了“可乘之机”，毕竟相关领域还不是太卷，广阔天地大有可为。正所谓“熟读洋屁三百篇，不会放屁也会吟”，奥利给！兄弟们干了！

前言

众所周知，自然界的数据绝大部分都是非欧的，这些数据无头无尾，一团乱麻，处理起来非常棘手。

目前的四大主流深度学习算法(算子)：全连接，CNN,RNN,ATT（我们先暂时忽略对抗，自编码以及强化学习）。它们对于图结构的数据的处理能力有限，但问题是深度学习发展到今天，也只有这几种常见的方法。这时候研究者就面临了两种选择：

1. 要么让算法去适应非欧的数据（改算法不改数据结构）
2. 要么让非欧的数据去适应算法（改数据结构不改算法）

道理是这么个道理，但我的分类方法还是相对粗糙的。学术界的两种主流分类方法是：

1. 节点为主的建模方法，边为主的建模方法，节点和边同时建模的方法。
2. 图卷积（CNN）、时序图（RNN）、图注意力（ATT）…

无论我们采用何种分类方式，我们总是绕不开两个核心问题：

1. 图的拓扑结构应该如何表示？
2. 节点和边的信息应该如何学习？

在此，我们将图分成了两部分，即：⭐结构和信息⭐。更直白的来说，图=拓扑结构+信息。

而数学中对图的定义则是有序的节点集和边集的集合。我们所采取的这种定义方式只是比较直接的指出了图神经网络研究的主要难点，本质上和数学中的定义是相同的。我们将在后面不断的讨论这两个难点。

另外，单独一个问题的研究都是没有意义的，因为去掉任何一个要素（结构或者信息）都不能构成一个完整的图。所以，我们还需要找到一种连结两个问题的方法。幸运的是，我们目前有两种方法同时处理结构和信息，一个是谱方法（特征值分解），另一个是采样。我个人比较支持采样方法。

好了，既然现在我们知道了图的研究对象是其结构和信息，获取样本的方法是谱分解或者采样，那么这些数据应该如何计算呢？

还记得马克思的那句话吗？人是其社会关系的总和。这句话很好的启发了我们，我们可以得到节点是其关系信息的总和，这些关系包括了节点的邻居，邻边和其自身。然后我们将这些关系信息通过某种方式聚合起来，就可以得到该节点的表示了。

我们的学习顺序和之前的综述性文章是不太一样的。
我们的论文阅读顺序如下所示：

1. 图神经网络的基本建模思路（MPNN）
2. 采样方法（GraphSAGE等）
3. 时序图
4. 图卷积
5. 图注意力

本文统一的符号

先写这么多，会慢慢扩展和补充

符号	含义
$D=(V,E)$	图的定义（vertex \& edge）
$N,M$	节点和边的数量
$V = { v_1,\cdots,v_n }$	顶点集
$F^V,F^E$	节点、边的特征（属性）
$A$	邻接矩阵
$D(i,i) = \sumj A{ij}$	对角度矩阵
$L=D-A$	拉普拉斯矩阵
$Q\Lambda Q^T=L$	拉普拉斯矩阵的特征分解
$P=D^{-1}A$	转移矩阵
$\mathcal{N}_k(v)$	节点$v$的$k$阶邻居,没写$k$就是$k=1$
$H^l$	第$l$层的隐藏状态
$f_l$	$H^l$的维度
$\sigma(\cdot)$	非线性激活函数
$\Theta$	可学习的参数
$s$	采样大小
$T$	时间步
$U$	状态更新方程（update），特指隐藏层状态更新
$M$	消息（message），实际就是信息
$AGG$	聚合方程（或聚合器）（aggregater），特指节点或者边上的显示状态更新

文献阅读笔记法

按照这个顺序记笔记

【论文题目】:

【概述】:

【需要解决的问题】:

【这个问题为什么重要】：

【解决之后有什么好处】：

【解决问题的前提条件或者是假设】：

【解决问题的具体方法】：

【实验】：

【结论】：

【源码解析】：

【个人评价】：

相关术语及概念

在进入正式的学习之前，我们需要对该领域的专业术语和概念进行一定的了解，方便同行之间的沟通和交流。不敢保证能达到智取威虎山的效果，但至少能保证不至于张嘴就被击毙。

A New Model for Learning in Graph Domains

【论文题目】：图领域的一种新的学习模型

【概述】：在一些场景中，信息是自然的以图的形式所表示的。虽然这些算法能够将图信息表示成一组向量，但通常来说，处理过程会丢失掉图的拓扑结构信息，而且其向量表示也是受算法本身约束的。这片文章提出了一种广义的RNN，能够处理许多种图结构的信息。另外，本文提出了一些重要的图神经网络的术语和概念。

【需要解决的问题】：图神经网络建模方法，以及节点和边的表示方法。

【解决问题的前提条件或者是假设】：假设数据都可以表示成图结构的。

【这个问题为什么重要】：因为自然界的数据绝大多数都是以图形式出现的，所以我们必须解决图建模的基本算法问题。

【解决之后有什么好处】：可以用高维形式进行图表示，提升相关任务的准确率。

【解决问题的具体方法及实验】：

1. 论文提出了节点级(node focused)和图级(graph focused)的两种建模方法，区别就是预测的时候，是预测了图的一部分信息还是预测整张图的信息。虽然我个人感觉这种分类方式已经有点过时了，而且以当前的算力来看，似乎又会造成一定程度上的混淆，所以我个人将不再讨论这个分类方式。

2. 广义RNN ： 首先通过随机游走的方式得到一个序列，然后用这个序列上的每一个节点及其邻居节点作为一个子图，再把这个子图中的所有信息通过一定的方式聚合到一起，形成一个新的节点。这样，我们就得到了一个序列化的子图，而且这个序列化的子图可以直接使用RNN计算，因此就成了广义RNN。在这篇论文中，广义RNN实际上就是GNN的原型。

3. 消息的传递、聚合和更新：

   $$v_{t+1}=f_{\theta}(v_t,\mathcal{N}(v_t),l_{\mathcal{N}(v_t)} )$$ $$o(v_{t+1})=g_{\theta}(v_t,v_{t+1})$$

   上式对应于原文中的等式$(7)$。

   第一行实际上就是消息的传递，$l$是节点的标签信息，也就是说，GNN可以是有监督的，也可以是自监督的。

   第二行中相当于节点信息的更新。

   那么聚合体现在哪里呢？实际上原文是没有“聚合”这个概念的，传递和聚合的过程被一同合并在了$f_{\theta}$里面。

   更为具体的概念我们将会在之后的论文中讨论。

用前向传播来计算数值解
用聚合信息的方法来计算表示解

【结论】：图神经网络=采样+消息传递+消息聚合+状态更新。这四要素构成GNN的基石，缺一不可。

【源码解析】：

【个人评价】：这篇论文提出了最原始的采样、传递、聚合、更新的概念（虽然确切的来说，是没有聚合的概念）。让我们知道了GNN中的节点的状态参数应该如何更新。

RNN可以看成是一种GNN的特例，反过来说就是：GNN是广义的RNN。再比如LSTM，其中的门控机制可以看做是聚合方程，而其马尔科夫假设也可以被看做消息传递。但GNN和RNN最大的本质区别就是节点的度。在RNN中，节点的度都是2（除了头尾），而GNN的节点度就变化万千了，因此形成了特殊的拓扑结构，也正因如此，GNN才需要各种采样技术，而RNN却不需要（RNN只需要顺序遍历即可）。虽然原文没有明确的说明，但我们读完论文就能感受到。

The Graph Neural Network Model

【论文题目】:

【概述】:

【需要解决的问题】:

【这个问题为什么重要】：

【解决之后有什么好处】：

【解决问题的前提条件或者是假设】：

【解决问题的具体方法】：

【实验】：

【结论】：

【源码解析】：

【个人评价】：

Introduction to GraphNeural Networks

在我的印象中这是比较早的几篇综述文章之一。我们仅截取其中一节：第四节，Vanilla Graph Neural Networks。这一节讲道理是我最喜欢的，介绍的

【论文题目】:图神经网络介绍之图神经网络初代机

【概述】:

【需要解决的问题】:

【这个问题为什么重要】：

【解决之后有什么好处】：

【解决问题的前提条件或者是假设】：

【解决问题的具体方法】：

【实验】：

【结论】：

【源码解析】：

【个人评价】：

Neural Message Passing for Quantum Chemistry

【论文题目】：量子化学的消息传递神经网络

【概述】：化学分子可以看做是图结构，而图结构又有许多相似之处，所以可以用一种监督学习的方法来预测分子的属性，并为新药发现和材料科学做贡献。传统的监督学习方法已经取得了很好的效果，但是作者希望能够用深度学习的方法把成果推广开来。因此他们发明了MPNN框架，并希望在此框架下，各种算法变体能取得进一步的准确度，达到数据集的极限。

【需要解决的问题】：设立一个图算法的框架，并在这个框架下寻找更多更准确更快速的，用于预测分子属性的变体模型。

【这个问题为什么重要】： 快速解决分子和材料的属性预测。

【解决问题的前提条件或者是假设】：

1. 在同一种图框架下
2. 算法不受同构（例如化学中的手性）的影响
3. 算法的计算效率足够高

【解决之后有什么好处】：

1. 预测时间会下降。用DFT(离散傅里叶变换)做预测需要$10^3$量级的时间，而使用MPNN则可以降低到$10^{-2}$量级。
2. 找到更多的变体模型，这些模型可以完全准确的预测到分子属性，或者是逼近预测的极限。
3. 可以促进新药发现和材料科学。（天坑专业自救指南）

【解决问题的具体方法及实验】：

在算法方面：

• 节点之间的消息传递：

  $$m_v^{t+1} = \sum_{w \in N(v)} M_t(h_v^t,h_w^t,F^{e})$$

  上式的含义是，节点$v$的消息传递是汇聚了它自身的信息$h_v^t$以及它邻居节点的消息$h_w^t$和邻边的消息$F^{e}$。但凡能用上的消息基本都用上了。

• 消息更新的方式：

  $$h_v^{t+1}=U(h_v^t,m_v^{t+1})$$

  这里只需要说一下$U$实际上是一个状态更新函数。通常用add,mean,max.但max是不可微的，所以使用的时候要注意。

• 图表征方法（readout）:

  $$y=R(\{h_v^T|v \in G\})$$

  $y$是一个向量，它表征了整个图。

在实验数据方面，本论文在其开发的图建模环境MPNN下，通过错误率和运行时间两方面来证明MPNN框架的可行性和实用性。但是具体的数据我并没有认真研究，因为MPNN的亮点是其图建模的思想（毕竟我太菜了，也找不到比MPNN更早的相关研究了。主要是懒）。

【结论】：MPNN确实从准确率和运行时间两方面达到了理想的结果。并且实现了一些图建模的最基本要素，如：消息传递，节点和边的参数更新，图表征（readout，我翻译成图表征，因为readout指的是把一张图表示为一个向量。）

【源码解析】：MPNN确实是有一套自己的代码框架，但是我水平有限，没有看懂😂。不过MPNN的基本思想被研究者们广泛认同，被PYG（pytorch_geometric）继承，然后PYG有被OGB（open graph benchmark）所继承，所以我们来看一下OGB的源码即可😄。（torch\geometric\nn\conv\message_passing.py）

关于OGB，可以参考这篇文章

MPNN的英文文档

首先，在OGB中，我们定义MPNN的算法框架：

$$v^{t+1} = \gamma_t(v^t,\square_{u\in \mathcal{N(v)}} \phi(v^t,u^t,F^e))$$

其中，$\square$是一个可微的且组合不变的方程，比如sum,mean,max。而$\gamma$和$\phi$则是任意可微方程，如MLP（全连接）。在本文中，$\gamma$就相当于$U$或者$AGG$，$U$和$AGG$的区别仅限于运算的对象，是负责聚合和更新信息的。而$\phi$则相当于$M$，负责收集信息。

MessagePassing类内有三个主要方法：

• MessagePassing.propagate(edge_index, size=None, **kwargs):该方法的输入参数是edge_index，知道了边的编号之后，自然就知道了输入节点$v$和输出节点$u$了。该方法会在内部调用MessagePassing.aggregate和MessagePassing.update。实际上，每次采样的结果就相当于一个子图，而且这个子图还是一个二部图。
• MessagePassing.message：相当于$\phi_{\mathbf{\Theta}}$。这个方法的输入就是MessagePassing.propagate的输入，
• MessagePassing.aggregate:相当于$\square_{u\in \mathcal{N(v)}}$，
• MessagePassing.update:相当于$\gamma_{\mathbf{\Theta}}$这一部分，对每一个节点$v$进行聚合。其输入是MessagePassing.aggregate的输出。

【个人评价】：
MPNN的思想非常简单且可行：节点就是其关系的总和。简单好用易于理解，所以成为了OGB的基础层。

图上的采样方法

DeepWalk: Online Learning of Social Representations

【论文题目】：深度随机游走：社团表示的在线学习

【个人评价】： 真·随机游走。第一个使用深度优先采样的图深度学习方法。

LINE: Large-scale Information Network Embedding

【论文题目】：【LINE】大规模信息网络嵌入

【概述】：LINE使用了广度优先采样+深度优先采样

【需要解决的问题】：大规模网络节点的向量空间嵌入问题

【解决问题的前提条件或者是假设】：

从直觉的角度来说，两个有着相同朋友圈的人，其兴趣也应该接近，因此这两个人很有可能成为好朋友。从上图中的5，6节点可以看出，这两个节点有着相同的“朋友圈”，所以他们之间的向量应该较为接近。

另外，6，7的嵌入向量也应该接近，因为这两个节点是直接相连（而且关系也比较强，因为边比较粗）

根据以上两个直觉，LINE定义了两种相似度。

1. 一阶相似：类似于6，7。如果两个节点之间没有边直接相连，这两个节点的一阶相似就是0.
2. 二阶相似：类似于5，6。如果两个节点之间没有相邻的其它节点，那么这两个节点的二阶相似度就是0.

【这个问题为什么重要】：图数据是离散的。如果能把节点信息向量化，那么我们可以获得更丰富的表示信息。这些表示信息对后续任务的帮助巨大。

【解决之后有什么好处】：这种采样方法相当于NLP的pre-train。对下游任务是有很大帮助的。

【解决问题的具体方法】：

LINE的目标函数是一个由一阶相似和二阶相似共同拼凑的。

首先是一阶近似的目标函数：

1. 定义两个节点之间的概率 $$p_{ij} = \frac{1}{1+exp(-v_i,v_j)} \tag{1}$$

2. 定义两个节点之间的经验概率。这里需要说明的是，$z{ij}$ 是一个非0即1的数。因为边权的数值是不确定的，有时候很大有时候很小，这会导致梯度的大幅波动，因为方差实在是太大了。所以作者很巧妙的使用了01数值来局部归一化。所以，$Z$ 就代表了边权的数值（只能是整数），$z{ij}$ 要看两个节点间是否有边相连，有就是1，没有就是0.

   $$\hat{p}_{ij} = \frac{z_{ij}}{Z} \tag{2}$$ $$Z = \sum_{(i,j)\in E}z_{ij}$$

3. $(1)$和$(2)$代表了两个节点之间的相关性，那么我们直接联立两个方程，就可以得到一个误差值，这个误差值就代表了两个节点的一阶相似度（也可以看成是距离）。在原文中，作者使用了KL散度来计算这个距离。

   $$d(p,\hat{p}) = KL(p,\hat{p}) = \sum_{(i,j)\in E}z_{ij}\log{p(v_i,v_j)}$$

然后是二阶近似的目标函数：

根据之前对二阶近似的定义，如果想计算两个节点之间的二阶近似的目标函数，就是看看第二个节点在第一个节点的朋友圈（目标节点的全部邻居）当中的份量。

这个份量，就可以用条件概率来描述。

1. 定义条件概率

$$p(v_j|v_i) = \frac{exp(v_i \cdot v_j)}{\sum_{\mathcal{v_k \in N(v_i)}}exp(v_k \cdot v_i)} \tag{4}$$

1. 计算二阶相似度。其中，$\lambda$代表节点的权值，毕竟节点和节点的重要程度也是不一样的。同样的，$d$也是用KL散度代替。然后把$(5)$式化简一下，就能得到$(6)$

$$O_2 = \sum_{v_k\in \mathcal{N}(v_i)} \lambda_i d(\hat{p}(\cdot|v_i),p(\cdot|v_i)) \tag{5}$$ $$O_2 = \sum_{v_k\in \mathcal{N}(v_i)} z_{ij} \log{p(v_j|v_i)} \tag{6}$$

但比较拉胯的是，原文里的训练方法是分别训练，然后把两种近似情况得到的向量拼接在一起。

【实验】：

【结论】：仅从采样方法来看，LINE = deepwalk + BFS。采样的方法变多了，因此能够得到更好的效果。

【源码解析】：

这个算法的问题我个人感觉非常大（先写着，以后慢慢补充）。因为论文为了省时省力（可能是受限于当时的硬件设备），context变量本来是$v_i$的全部邻居节点，但结果却只是$v_j$的嵌入。

【个人评价】：

低情商：这个算法有问题

高情商：这个算法仍旧有很大的改进空间。

开个玩笑。实际上LINE可以看做是DEEPWALK的改进，毕竟deepwalk只是用了DFS做采样，而LINE用了BFS。但LINE的问题我个人认为有两处。

1. 在一阶相似的定义方面：我们观察公式可以发现，$p$是节点向量的内积，而$\hat{p}$是与节点之间的边权相关的量。一阶相似的目标函数是希望内积和边权尽量相同。我们现在用极端条件来验证一下：

   • 当$v_i=v_j$时，带入公式$(1)$可得：$p = \frac{1}{1+exp(-1)} =0.73$。这个误差大概是0.27

   • 当$v_i \perp v_j$时，带入公式$(1)$可得：$p =\frac{1}{1+exp(0)}= 0.5$,这个误差是0.5

   所以，我个人认为用内积来定义相似度是没有问题的，但问题出在相似度的解析方程，至少文中给出的解析方程是有问题的。另外，LINE将相似度与边权划等号，在直觉上是说得通的，但更具体的形式还要继续探索。

2. 在二阶相似的定义方面：因为在源码中，$v_j$的向量和context(也就是$v_k$，是$v_i$的全部邻域)的向量实际上都是依靠$v_j$做嵌入的，所以当前节点$v_i$的邻域信息，也就是BFS采样，并没有充分利用。如果简化来看，这种方法甚至比deepwalk还简单（LINE在极端条件下实际上就采样了一个点…也就是$v_j$）。

node2vec: Scalable Feature Learning for Networks

【论文题目】:网络的可扩展特征学习

【概述】:如何捕捉邻居节点的多样性特征一直以来都是一个难题。node2vec首次提出了一种启发式的灵活采样方法，该方法结合了DFS和BFS的精髓，并且作者认为这种采样方法能够有效的反映出节点的特性。其中的核心观点就是：

1. 邻近的节点应该相似
2. “朋友圈”相同的节点也应该相似。

【需要解决的问题】:蕴含更多更丰富信息的采样方法。

【这个问题为什么重要】：节点的向量表示在不同的采样策略下，有着不同的表示方法，而且原文中也指出，目前（2016）还没有一种通用的良好表示方法。所以，采样方法在很大程度上决定了节点向量表示学习的能力。而深度学习框架下的采样方法也几乎都是DFS和BFS，一种很自然的想法就是将二者结合。但之前的LINE算法在本质上属于拼接了DFS和BFS，而DeepWalk只有BFS，所以node2vec就搞出了启发式算法来融合DFS和BFS，作者们也认为，灵活的采样方法能够获取更加丰富的表示信息。

【解决之后有什么好处】：让节点的嵌入向量包含更多更丰富的信息，用以处理下游任务。并且可以更快更好的学习节点的嵌入表示。

【解决问题的前提条件或者是假设】：

【解决问题的具体方法】：

1. skip-gram: $$\max_v \sum_{u\in \mathcal{N}(v)} \log{p}(\mathcal{N}(v)|v) \tag{1}$$ 其中，$v$代表节点的向量。这个公式的含义就是，依靠节点$v$来最大可能的预测其周围邻居。相当于NLP中的skip-gram
2. 条件独立: $$\log{p}(\mathcal{N}(v)|v)=\prod_{u\in \mathcal{v}}p(u|v) \tag{2}$$ 有了这个假设，子图就可以按节点进行分割了。
3. 特征空间的对称性（我个人觉得，写成排列无关性更好）： $$p(n|v)=\frac{exp(n\cdot v)}{\sum_{u\in \mathcal{v}} exp(u\cdot v)} \tag{3}$$ 这个公式是说，起始点$v$和终点$n$之间的概率关系与两者之间节点的排列顺序无关。
   根据上述三个等式，最终的优化目标可以写为： $$\max_{v} \sum_{u\in \mathcal{N}(v)}[-\log{Z_u} + \sum_{n\in \mathcal{N}(u)}n\cdot u]$$ 其中： $$Z_u = \sum_{u\in \mathcal{N}(v)} u\cdot v$$

4. search bias:这是一种启发式的搜索策略。就是在搜索的过程中设置不同的转移概率$\alpha$（可以理解为一种阻力）。
   

   1. 如果节点$t$和$v$共享同一个邻居$x_1$，那么$\alpha$就是1
   2. $t$和$v$构成的边的$\alpha$是$\frac{1}{p}$

   3. 其他情况为$\frac{1}{q}$

      当然了，真正的$\alpha$还需要和边权$w{vu}$相乘，所以真正的转移概率应该是$\alpha \cdot w{vu}$。
      另外，每次采样过后，中心节点都会变更，这样才能保证采样的多样性。

【实验】：所有的实验结果以OGB为准。

【结论】：转移概率在本文中充当了胶水的角色，很好的将BFS和DFS结合在了一起。这种启发式的算法比DeepWalk和LINE这两种最优化算法要好一些。

【源码解析】：以后再补。

【个人评价】：从论文的实验结果来看，启发式确实是比最优化的采样方法要好。但更重要的信息是，不同的采样方法对结果的影响非常巨大，而且node2vec的超参$p$和$q$仍旧有讨论的空间，但更大的舞台还是设计新的采样方法。

Inductive Representation Learning on Large Graphs

【论文题目】： 大图的归纳表示学习

【概述】：之前的节点嵌入方法都是直接计算一整个较小的图，因此泛化能力差，而且对于新的节点的嵌入显得束手无策。本文采用近邻采样的方法对大图中的节点的嵌入向量进行学习。这种学习方法并非传统的直接学习节点的向量表示，而是去训练聚合器来间接学习节点的向量表示。而且学习目标不仅仅是节点的向量表示，还包括了节点的分布。这种方法速度快，效果好，对未知的节点嵌入也有较高的鲁棒性。

【需要解决的问题】：大图中的节点表示学习

【解决问题的前提条件或者是假设】：大图

【这个问题为什么重要】：节点的向量表示是下游任务的基础。不解决这个问题很难搞下去。

【解决之后有什么好处】：解决了节点向量的表示，才能为之后的任务服务。比如推荐系统，只有解决了当前用户节点的表示，才能为新用户的行为进行预测。

【解决问题的具体方法及实验】：

如图所示：

(1)表示一个节点的1阶邻居和2阶邻居，这些就是我们所要聚合的信息。

(2)表示对当前节点的信息以及它邻居的信息进行聚合。我们可以很清楚的看到，1阶聚合器和2阶聚合器是不同的，这也很好理解，毕竟你亲戚的亲戚不一定是你的亲戚。所以要区别对待。

(3)则是一个目标函数，要求当前节点去预测他的邻居以及其自身的标签。（有点类似于word2vec的CBOW步骤）

算法的伪代码如下所示：

步骤4聚合了全部的邻居信息，而步骤5则是对当前节点的状态更新。步骤7则是一个常见操作，因为不断的聚合会使节点的模长爆炸，所以需要把隐藏层的模长限定在$[0,1]$之间。这个操作就是求一个向量的单位向量。

最后是目标方程。

$$J = -log(\sigma(z_u^Tz_v)) - Q\mathbb{E}_{v_n \sim P_{n}(v) }log(\sigma(z_u^Tz_{v_n}))$$

其中，$\sigma$代表了softmax函数，$z_u$是邻居节点的向量，$z_v$是中心节点的向量。$z_u^Tz_v$代表了两者之间的内积，并用内积来代表相似度。而$P$则代表了负采样，$v_n$就是那个被负采样出来的虚假中心节点，它和$z_u$之间的内积自然会小。所以就用这样一真一假的操作让聚合器去学习。至于Q，那就是负采样的样本个数了。

【结论】：

【源码解析】：该方法的实现是较为简单的，主要就是将聚合器替换为一种带参的方程，之前提到过的四种常见算子大家有兴趣都可以挨个试一遍。（我太懒了，实际上也根本没有实践过。。。而论文的实际效果又不一定那么好，所以有空还是需要去写一遍代码的。）

【个人评价】：从直接学习转变为间接学习，可以说这个idea是可以的，反正我是想不出来。当然了，光有idea还是不够的，还必须work。我觉得GraphSAGE不仅能work还work的很好的主要原因是它的可学习参数加对了地方。因为在之前的聚合器一般都是选用mean,add等一些不带参的方程，但GraphSAGE突破了传统（虽然我也不清楚在此之前是否有人提出过这个问题）。转念一想，什么直接学习间接学习的，在深度学习里，参数的多寡是决定算法上限的最重要标准（毕竟都是拟合）。如果后来人能发现其他增加参数量的地方也一样可以发一篇好文章。

Adaptive Sampling Towards Fast Graph Representation Learning

【论文题目】：面向图表示学习的自适应采样方法

【需要解决的问题】：

1. 大规模图数据在训练时的采样问题
2. 我个人另外一个理解是：能优化期望的估计值。

【这个问题为什么重要】：因为大规模的图数据会导致内存爆炸或者运算量过大的问题
【解决之后有什么好处】：
【解决问题的具体方法及实验】：
【结论】：

以后再分类

Learning with Local and Global Consistency

【论文题目】:局部和全局一致性的学习

【概述】:这个是标签传播（LPA : label propagation algorithm） 的开山之作。文章从全局一致和局部一致两个方面分析了标签传播的算法。其优点是速度快，缺点是不准确。

【需要解决的问题】:从已标注数据到未标注数据的（半监督）学习问题。

【这个问题为什么重要】：减少标注劳动量，从而获得大量带标签数据。

【解决之后有什么好处】：未标注数据往往是容易获得的，这些未标注数据如果有了标签，就可以用于后续模型的学习，提升模型的效果。

【解决问题的前提条件或者是假设】：
The key to semi-supervised learning problems is the prior assumption of consistency, which
means: (1) nearby points are likely to have the same label; and (2) points on the same structure (typically referred to as a cluster or a manifold) are likely to have the same label.

给定一组点集$\mathcal{X}={x1,x_2,\cdots,x+_l,x{l+1},\cdots,x_n}$

以及标签集合$\mathcal{l}={1,\cdots,c}$

那么现在的目标就是从已标注数据到未标注数据的推断问题。

The keynote of our method is to let every point iteratively spread its label
information to its neighbors until a global stable state is achieved.

$\mathcal{F}$代表了一个具有非负元素的$n\times c$矩阵，矩阵$F=[F1^T,\cdots,F_n^T] \in \mathcal{F}$代表了数据集$\mathcal{x}$的一个分类，其中的每一个元素$x_i$都有一个$y_i = \argmax{j\le c}F_{ij}$的标签。我们可以认为$F$就是一个向量函数，将数据集$\mathcal{X}$映射到标签集上。$F:\mathcal{X} \rightarrow \mathbb{R}^c$

我们再定义一个$n\times c$的矩阵$Y$，$Y\in \mathcal{F}$,若$xi$具有标签$y_i = j$,则$Y{ij}=1$,其余则为0。显然，$Y$与初始标签是一致的。

算法如下：

1. 定义关联矩阵$W$,$W{ij}=exp(-\Vert x_i - x_j \Vert^2 /2\sigma^2)$ 若$i\ne j$否则$W{ii}=0$
2. 构建矩阵$S = D^{-\frac{1}{2}} W D^{-\frac{1}{2}}$,其中，$D$是一个对角矩阵，其$(i,i)$（对角）元素是$W$矩阵第$i$行的和。
3. 迭代$F(t+1)=\alpha SF(t)+(1-\alpha)Y$至收敛，$\alpha$是一个介于0，1之间的超参。
4. 记$F^{}$为${F(t)}$的极限，每一个点$xi$都被标记为$y_i = \argmax{j\le c}F^_{ij}$

我们首先在数据集$\mathcal{X}$上定义成对关系$W$，其对角线元素为零。那么我们就可以认为图$G=(V,E)$中的顶点集$V$是定义在数据集$\mathcal{X}$上的，边集$E$的权重是定义在关联矩阵$W$上。在第二步骤中，$W$的标准对角化是为了后续迭代的收敛。前两步骤和谱聚类方法完全相同。在第三个步骤中，每一次的迭代都会让顶点接收其邻居的信息，同时也保持了其自身的特征（第二项）。超参$\alpha$则代表了邻居信息与中心节点信息之间的相关程度。除此之外，信息是均匀传播的因为$S$是一个对称矩阵。最后，每一个未被标注的节点的标签会被标注为迭代过程中接收信息最多的那一类的标签。

关于收敛性的证明：

不妨设$F(0)=Y$.

迭代过程的等式可以记为：$F(t+1)=\alpha SF(t)+(1-\alpha)Y$

那么从0到$n$累加可得：

$$F(t)=(\alpha S)^{t-1}Y+(1-\alpha)\sum_{i=0}^{t-1}(\alpha S)^{i}Y \tag{1}$$

由于$0<\alpha <1$,且$S$的特征值在$[-1,1]$之间（级数收敛）（另外，$S$与随机矩阵$P=D^{-1}W=D^{-\frac{1}{2}} W D^{-\frac{1}{2}}$相似）

$$\lim_{t\rightarrow \infty} (\alpha S)^{t-1}=0 \quad and \quad \lim_{t\rightarrow \infty} \sum_{i=0}^{t-1}(\alpha S)^{i}=(I-\alpha S)^{-1} \tag{2}$$

前者是极限，后者是无穷级数求和。

所以：

$$F^* = \lim_{t\rightarrow \infty} F(t) = (1-\alpha)(I-\alpha S)^{-1}Y$$

而对于分类问题，则可以得到：

$$F^* = \lim_{t\rightarrow \infty} F(t) = (I-\alpha S)^{-1}Y \tag{3}$$

(（3）没弄明白)

【解决问题的具体方法】：

【实验】：

【结论】：

【源码解析】：

【个人评价】：