《图表示学习入门1》中，讨论了为什么要进行图（graph）表示，以及两种解决图表示问题的思路。这篇把Node2Vec来作为线性化思路的一个典型来讨论。
如果你了解Word2Vec的话，这个就太简单了。
代码实现：（https://github.com/leichaocn/graph_representation_learning）
目录
核心想法
准备节点序列
用节点序列来训练Node2Vec
指标评价
总结
参考文献
核心想法
回想文本中Word2Vec中抽取单词Embedding的方式，是怎么做的？
- 准备句子语料，用一个词预测周围词来组成无监督训练的样本对。
- 用这些样本来训练一个2层的Word2Vec网络，抽出隐层权重作为Embedding。
那我们只要准备好节点序列，是否也可以用Word2Vec的思路来抽取节点Embedding？
但是我们需要首先给节点创造一些序列，或者说语料“句子”。
如果清楚了这一点，我们的想法就大致如下：
-
准备节点序列
图（graph）结构中，按照节点的连接关系生成节点序列，很容易。然而如果任意生成序列，也会导致序列的意义坏掉。正如一个随机生成的文本肯定是糟糕的语料，一个随意生成的节点序列也必然糟糕。
所以，我们需要针对每个节点，适度地有中心的产生语料。
-
用节点序列来训练Node2Vec
以skip-gram（中心词预测周围词）的方式，生成样本对，来训练Node2Vec网络，最终从隐层权重中抽取出Embedding，自带一定的相似度信息。
显然，这是一种无监督的特征学习，只需要利用现成的图（graph）结构准备好节点序列就可以了。
准备节点序列
如我们刚才讨论的，我们的节点序列必须围绕一些节点，稍微带点”中心思想“，而不能瞎走。
BFS与DFS
这是两种耳熟能详的常见做法：
-
广度优先搜索（BFS）
覆盖度较好，但是太局部（local）。
-
深度优先搜索（DFS）
搜索深度较好，但是太全局（global），过于远的邻居对表征帮助不大。
图1.广度优先搜索与深度优先搜索的对比（source）
然而，这两种做法都有点极端，本着中庸之道的精神，综合BFS和DFS，请出我们的主角：带偏随机游走（Biased random walk）。
Biased Random Walk
它相当于"插值"BFS和DFS，用两个参数，
来调节两者的比例，命名为Biased，意在强调人为引入的这两个参数。
图2.带偏随机游走的核心思想（source）
带偏随机游走做法是：
对一个图遍历num_walks轮；每轮都用图中全部节点，生成一段话；每句话是一个节点开头，为预定长度walk_length。
对每个节点，读入概率数据，进行以下1/2步的循环，直到达到预定长度。
1.用Alias Method采样下一个节点。
2.采到的那个节点加入到节点序列里。该节点切换为当前节点。
在原始代码（含链接）里，最核心就是下面这两个方法：
def node2vec_walk(self, walk_length, start_node):
'''
Simulate a random walk starting from start node.
'''
G = self.G
alias_nodes = self.alias_nodes
alias_edges = self.alias_edges
walk = [start_node]
while len(walk) < walk_length:
cur = walk[-1]
cur_nbrs = sorted(G.neighbors(cur))
if len(cur_nbrs) > 0:
if len(walk) == 1:
walk.append(cur_nbrs[alias_draw(alias_nodes[cur][0], alias_nodes[cur][1])])
else:
prev = walk[-2]
next = cur_nbrs[alias_draw(alias_edges[(prev, cur)][0],
alias_edges[(prev, cur)][1])]
walk.append(next)
else:
break
return walk
def simulate_walks(self, num_walks, walk_length):
'''
Repeatedly simulate random walks from each node.
'''
G = self.G
walks = []
nodes = list(G.nodes())
print 'Walk iteration:'
for walk_iter in range(num_walks):
print str(walk_iter+1), '/', str(num_walks)
random.shuffle(nodes)
for node in nodes:
walks.append(self.node2vec_walk(walk_length=walk_length, start_node=node))
return walks
simulate_walks（）用来生成“一篇文章”，对一个图遍历多轮（可以想成生成了多个自然段），每轮随机一下（每轮生成一个自然段），遍历所有节点（每个节点对应一句话）。最终获得walks，格式为数组的数组，可以理解成一篇文章，每个自然段是对图的一种随机解读，每个元素都是一句子的开头。多个自然段可以理解为对图结构的一种反复解读：）。
node2vec_walk（）则是传入一个节点，生成一句话（节点序列）。由于提前把概率设置并储存在图数据中，这里调用alias_draw（）即可获得。alias_draw实现的就是Alias Method采样方法。对Alias Method采样方法有兴趣的小伙伴可以进一步了解。
生成的结果在图3中进行了举例，有助于理解。
可能需要注意：最终生成的序列很有可能有一个节点重复出现多次的情况。
无论走的方向是往前或往回或平行，都是随机的，因此很可能会往前走了又走回来了。这没关系，因为这都是由起始节点及图（graph）结构造成的，我们给它多产生一些序列即可，即丰富的“语料”。
用节点序列来训练Node2Vec
通过之前的操作，我们已经准备好了节点序列，按照skip-gram思想，即对于输入的句子，我们用中心词预测周边词们；对于准备好的节点序列串，我们也用某个中心节点预测周边节点们。
注意：这里的周边，指的是节点序列里某元素的周边，而不是图（graph）的某元素的周边。用表示基于策略
（本文指）生成的序列，节点
的周围节点的集合，如图3所示。
图3.节点序列及周围节点集合生成示意图
优化目标
假设节点的one-hot向量为
，在一串序列中，它周围节点one-hot向量为
，这些
组成的集合为
。
对自己周围的预测概率
，通过引入朴素贝叶斯假设，可以简化为：
我们希望这个尽可能地大，根据公式，现在的问题是如何求
。
这个好办，我们只要学一个函数，输入
，输出对节点
的预测概率
。
而这个函数正是我们要训练的神经网络。
这下我们就清楚了，可以定义如图3所示的这个优化目标：
图4.node2vec的学习目标
神经网络结构
下图中的神经网络即实现这个，只要输入一个样本
，前向传播一次，从向量
的元素中，即可获得每一个标签
对应的
。
图5.Node2Vec神经网络的结构
在训练中，将被纳入我们的目标函数进行寻优。
具体的训练涉及细节较多，我们将在Word2Vec中详细讨论。
Embedding的获得
待网络训练结束，只要输入节点的one-hot向量
，前向传播到隐层，生成
，即为节点
的Embedding。
更简便的方式是，由于训练时都是用one-hot向量训练，其实，只需要把对应里为1的那个元素，所对应的权重序列拿出来，即为节点
的Embedding。
这部分，将在Word2Vec中详细讨论。
指标评价
由于是无监督训练，同时获取的Embedding也只是节点的特征表示，因此需要结合具体项目表现来对Node2vec结果进行评价。
例如节点分类项目，训出Embedding，再结合节点已标注的类别标签，训练一个分类器，根据分类结果的指标对Embedding进行间接评价。需要注意的是，节点序列生成策略、Node2Vec网络的隐层维度、分类器的选型和参数，均影响分类结果的指标。
总结
通过合适的策略生成节点序列，当做训练Node2Vec的“语料”。
训练Node2Vec网络，即以Word2Vec的思路训练神经网络，抽出隐层权重作为对应节点的Embedding。
参考文献
[1] Jure Leskovec, 《Graph Representation Learning》
[2] Jure Leskovec, 《Representation Learning on Networks》
http://snap.stanford.edu/proj/embeddings-www/
[3] https://github.com/aditya-grover/node2vec/tree/master/src
（如有错误及表述不清，请不吝反馈）
