【源头活水】游走图模型-聊聊Node2Vec（论文分析、代码实践）

“问渠那得清如许，为有源头活水来”，通过前沿领域知识的学习，从其他研究领域得到启发，对研究问题的本质有更清晰的认识和理解，是自我提高的不竭源泉。为此，我们特别精选论文阅读笔记，开辟“源头活水”专栏，帮助你广泛而深入的阅读科研文献，敬请关注。

来源：知乎—眼睛里进砖头了

地址：https://zhuanlan.zhihu.com/p/400849086

01

引言

前面有写过deepwalk，它是一种基于DFS游走的Graph embedding模型。

https://zhuanlan.zhihu.com/p/397710211

node2vec算是deepwalk的进阶版。模型训练原理与deepwalk差不多，但它通过调节边参数，融合DFS、BFS两种方式进行图游走，增加了游走的灵活性，进一步丰富了图表达。

02

模型优化目标函数

node2vec的目标函数： 

其中，u为中    心为邻居点，  , v为非邻居点，这个目标函数由两部分构成，min(非邻居点乘积) + max(邻居点乘积)，与deepwalk一样，都是基于skip-gram的方法进行此目标函数的优化。

03

路径采样策略

目标函数确定了，skip-gram的训练策略确定了，那就剩下路径采样（walks sample）没解决了。

deepwalk里就是直接沿着边关系进行路径采用，这种方式很直观，但太简单，它只是体现了点与点之间是存在关系的，没有体现图的结构性质，比如两个非邻居点在图里各自都有 三个邻居点。

node2vec综合了BFS、DFS图遍历算法，将其融合起来，采用赋予边一些权重参数来控制沿着哪条边行进，从而完成路径采样。

边参数定义

node2vec边的权重定义  ，由两部分组成，    为边本身的权重大小（无边权重的   =1）,  为控制BFS/DFS 采路径模式的权重， 具体定义：

结合这个公式与上面那张图，看看是怎么来通过调节p、q来实现控制BFS/DFS的。

   表示的是点t到点x的距离。举个例子，假设当前点节为v，v的上一个点为t（由t-v，当前在v），下一步走去下个点为x，    表示的就是点t到点x的距离。（有点绕，但对理解这个图与这个公式很重要）。展开一下（看图并结合文）

1. 当x为t时， 说明下一步访问t, 此时    ，这条边的路径模式权重   

2. 当x为x1时，说明下一步访问x1, 此时   

3. 当x为x2或x3时，说明下一步访问x2或x3, 此时 这样的定义下，可以发现，参数p叫做return-parameter p，控制重复访问的概率，也就是继续回到上一点的概率，p越大，则回到上一个点的几率就小。参数q叫做In-out parameter，控制着向外还是向内，即BFS/DFS游走模式的权重，q>1,倾向于访问与t接近的点（如x1，偏向于BFS），q<1,倾向于访问远离t的顶点（如x2、x3,偏向于DFS）。

以上就是node2vec的路径采样模式。采出序列后，把序列丢尽skip-gram训练，模型就完成了。

04

核心代码

在代码实现上，主要的难点就是得计算出当前点到下一点的各个概率，也就是上文涉及的p、q。因此，代码需要记录这几个信息：

1. 当前点的子节点。

2. 当前点的前一个父节点。

3. 当前点的父节点的所有子节点。

可以在外层记录以上信息，然后传上述三个信息进去，单独用一个函数去计算各边的概率，从而选出下一个点。

外层的伪代码：

def node2vec_walk(graph, nodes, max_depth, p, q):
    # 初始化 walks的起点为nodes
    初始化: walks, succ = nodes, graph.succssor(nodes)
            prev_succ, prev_node = [-1], [-1]
    for l in range(max_depth):
        # node2vec_sample 选出下一个点的函数
        sampled_succ = node2vec_sample(succ, prev_succ, prev_node, p, q)
        walks.append(sampled_succ)
        prev_nodes, prev_succs = cur_nodes, cur_succs
        cur_nodes = sampled_succ

    return walks

内层的计算各边概率p，q，选出下一个点的函数：

def node2vec_sample(succ, prev_succ, prev_node, p, q):
    succ_len = len(succ)
    prev_succ_len = len(prev_succ)

    probs = list()
    prob_sum = 0

    prev_succ_set = list()
    for i in range(prev_succ_len):
        prev_succ_set.insert(0, prev_succ[i])
    # 计算node2vec的各边权重
    for i in range(succ_len):
        if succ[i] == prev_node:
            prob = 1. / p
        elif len(prev_succ_set) > 0 and succ[i] != prev_succ_set[-1]:
            prob = 1.
        else:
            prob = 1. / q
        probs.append(prob)
        prob_sum += prob

    rand_num = random.uniform(0, 1) * prob_sum

    for i in range(succ_len):
        rand_num -= probs[i]
        if rand_num <= 0:
            sample_succ = succ[i]
            return sample_succ

具体代码细节可以看这里

https://github.com/shuxinyin/Graph-Learning

05

任务

node2vec主要是做了两种任务，1. node classification 2. link prediction

multi-label classification

结果这里就没啥好说的，肯定是好了。文中采用网格搜参 p, q ∈ {0.25, 0.50, 1, 2, 4}，做出的结果在上述两个任务上比deepwalk与node2vec要有更好的表现。

06

总结

node2vec在原来deepwalk的基础上，增加路径采样的多样性，进一步的挖掘出更多的图结构的信息，同质性、同构性），有效改善了graph embedding的结果。node2vec主要研究的还是同构图，即不区分点与边的类型，现实中还是多以异构图为主，但异构图也可以按边拆解成同构图进行研究，node2vec这种方式为研究图的结构提供了很大的参考意义。

另外的图网络同构图deepwalk与多关系异构图GATNE可以看看这两篇文章。

https://zhuanlan.zhihu.com/p/397710211

https://zhuanlan.zhihu.com/p/390705175

07

参考

1. https://github.com/PaddlePaddle/PGL

2. https://github.com/dmlc/dgl

本文目的在于学术交流，并不代表本公众号赞同其观点或对其内容真实性负责，版权归原作者所有，如有侵权请告知删除。

“源头活水”历史文章

更多源头活水专栏文章，

请点击文章底部“阅读原文”查看

分享、在看，给个三连击呗！