图神经网络核心总结

图神经网络最初的使用是在社交关系中，社交网络中，用户和用户间的关系包含大量的信息。但已有的两大领域的特征抽取工具（CNN、RNN）无法有效利用这种关系。由于用户间的关系天生就是一个图的特征，因此有人想到利用图的结构信息来辅助建模。

本文参考论文原文，知乎浅梦的文章zhuanlan.zhihu.com/p/56542707 ，掺杂个人理解写成

DeepWalk

Q：现在有了一个图的结构数据，我们怎么样才能有效利用这个图的关系，将其转化为一个向量空间中的向量呢（训出Embedding）？

A：怎么利用图的关系不知道，但最近有个很火的东西叫Word2Vec，他可以将一个序列结构的数据变成Embedding。

Q：既然Word2Vec可以输入一个序列，输出每一个结点的Emb。我们在这个图中搜集一个个的序列，不也可以得到整个图的Embedding了吗

A：可以啊，问题在于，我们怎么样得到这个序列？

Q：直接随机游走！

A：随机？可行吗？？

Q：随机游走后，节点的出现次数复合幂律分布，与自然语言中的词的分布非常接近

既然该分布下的自然语言序列可以用Word2Vec，那咱们随机游走后得到的序列也可以！

A：那就试试吧！

首先是RandomWalk的算法，我们看看论文中的伪代码

思想很简单，针对每个节点随机游走N次，每次得到一个序列，用于利用Skip-Gram训练，训练时使用window size大小的数据进行预测。序列长度及窗口大小均为超参数，需要人工设定。

具体实现时，为让每个节点能够以均匀的方式被训练，所以先外层循环N次，再内层训练每个节点。

Word2Vec：输入一个语句序列（[word1, word2, word3]），以通过部分word预测其他word作为训练目标，来训练word的vec（本质上和MLM一样，基于共现关系）。Word2Vec主要有两种方法：Skip-Gram，通过输入的word预测上下文；CBoW，通过上下文预测word。

Line

感觉效果不好，待填坑

node2vec

Q：DeepWalk的时候纯随机游走，能不能针对这个部分进行改进？

A：可以，更有效的利用节点间的关系？比如离得近的优先访问（BFS），或者不重复访问已经访问的节点。

Q: 好想法，但是不同的图可能设定不同的策略比较好。不如直接设一系列超参数让人去调吧

A：好！

Node2Vec主要设定了三个转移概率，包含两个超参数：

1. 1/p：回退概率，返回上一个节点点的概率，若该值为0，则不会 进行 a-b-a这样的访问，但可能出现a-b-c-a的访问
2. 1/q：二跳关系访问概率，访问二跳关系节点的概率，若该值为0，则不会访问二跳关系
3. 1: 一跳关系访问概率，默认为1。也就是说只要1/q大于1，就优先访问2跳节点，做DFS。否则就优先做BFS。

见下图：

t为上次访问的节点，v为当前节点，x1为t的一跳节点，x2、x3都为t的二跳节点。

Q：除了节点关系，把节点的权重也用上

最终，v访问某一个节点的概率为，转移概率乘以边的权重： $\alpha * w$ 。
针对某一个节点的所有邻居节点，基于该概率进行Alias采样（待填坑）

GCN

待填坑

GraphSage

待填坑

其他思考

图本质上能够描述任何实体间的关系。

CV的数据是高度冗余、连续性极强的三维数据，最初利用CNN作为特征抽取器，可以有效地利用空间特性。在Attention发展起来后，也有使用Transformer和纯MLP的方法（为什么这两种方法这么有效？）。

NLP的数据是高度抽象、序列性强的概念数据。利用RNN能够有效利用序列性的特点，利用Attention能够人工捕捉Embedding之间的关系。