deep walk
DeepWalk方法是第一个提出用node embedding的无监督算法。其训练过程与词向量方法有很大程度的相似度。原理是将图中节点的分布与文本中的单词分布一样，将具有相似特征数据映射到相近的坐标空间中。
这个算法包含两个步骤：
- 在图上进行随机游走，最后产生节点的序列。
- 在节点度为1的情况下，以输入节点为中心节点，生成周边节点。
每一次随机游走，我们都会根据之前的一个节点对下一个节点进行采样，因此，生成每个序列的长度应该为，在这里，是skip-gram的窗口大小。what is skip-gram?
在该文中，考虑到图节点的数量问题，使用softmax计算的开销为。
其中，为图中节点的个数。
通常情况下，Hierarchical softmax使用二叉树来优化此问题，在二叉树中，叶节点（）都是图的顶点，每一个非叶节点，都是一个二元分类器，用于决定往哪条路走。
为了计算给定顶点的概率，一个简单的方法就是计算从根节点到每个叶节点的概率值。因为所有的叶节点对应的概率值之和为1，所以计算每个元素的开销就降低为，对应二叉树中的开销则为，其中，是叶子节点的数量。
在训练DeepWalk之后，模型能够很好的表示每一个节点的特征。在下图中，不同的节点表示图中不同的标签值，可以看到，在输出图中（embedding之后每个节点有均是2维的特征）具有相同标签的节点汇聚在一起了。
然而，DeepWalk最大的缺点在于，其适用性不强，当图中有新的节点进入时，需要重新训练整个图，因此，这种GNN模型并不适用于动态图。
GraphSage
论文地址在这里。
这种模型能够解决上述问题，在进行embedding的学习过程中，适用的是inductive方法，每个节点都由其邻居节点进行表示，因此，即使节点并未参与模型的训练，但是仍然可以较好地由邻居节点进行表示。下面是该算法的计算流程。
上述算法中，最外层循环说明了更新迭代的次数。
- ：第次迭代后节点的隐状态，该值由汇聚函数AGGREGATE()更新，该函数所需要的参数有：之前节点及其邻居节点的特征以及权重矩阵。
在论文中，AGGREGATE function有以下三种：
Mean aggregator
该函数的主要作用是取节点及其相邻节点隐状态的均值，公式如下：
与原始的算法相比，该方法移除了伪代码算法中第5步的concatenation操作。该方法可以看做是“skip-connection”，该方法能够显著的提升模型效果。
LSTM aggregator
Pooling aggregator
这种方法是元素级别的操作。
其中，pooling方法可以使用mean-pooling和其他的symmetric pooling函数。经过论文证明，pooling aggregator的效果是最好的，mean和max pooling具有相同的效果，论文使用max pooling作为默认的聚合函数。
loss function
在上述公式中，是固定长度随机游走的序列，另外，是不出现在序列中的节点，这种loss函数能够使得相近的节点具有更加相似的embedding结果，不相近的节点则在投影空间中距离较远。通过这种方式，节点能够从邻居节点中得到更多的信息。