图表示学习入门2——Node2Vec

作者: soplars | 来源:发表于2019-10-10 14:52 被阅读0次

《图表示学习入门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），过于远的邻居对表征帮助不大。

2im1.png

图1.广度优先搜索与深度优先搜索的对比（source）

然而，这两种做法都有点极端，本着中庸之道的精神，综合BFS和DFS，请出我们的主角：带偏随机游走（Biased random walk）。

Biased Random Walk

它相当于"插值"BFS和DFS，用两个参数 $p$ ， $q$ 来调节两者的比例，命名为Biased，意在强调人为引入的这两个参数。

2im2.png

图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）的某元素的周边。用 $N_S(i)$ 表示基于策略 $S$ （本文指）生成的序列，节点 $i$ 的周围节点的集合，如图3所示。

2im3.png

图3.节点序列及周围节点集合生成示意图

优化目标

假设节点 $i$ 的one-hot向量为 $u_i$ ，在一串序列中，它周围节点one-hot向量为 $u_j$ ，这些 $u_j$ 组成的集合为 $N_S(u_i)$ 。

$u_i$ 对自己周围的预测概率 $P(N_S(u_i)|u_i)$ ，通过引入朴素贝叶斯假设，可以简化为：
$P(N_S(u_i)|u_i)=\prod_{n_j\in N_s(u_i)} P(n_j|u_i)$
我们希望这个 $P(N_S(u_i)|u_i)$ 尽可能地大，根据公式，现在的问题是如何求 $P(n_j|u_i)$ 。