node2vec和deep walk到底在捕捉网络的什么特性
- 2020 年 12 月 16 日
- AI
上图为bfs随机游走策略产生的embedding结果，下图为dfs随机游走策略产生的embedding结果的可视化，颜色接近的节点代表其embedding的相似性更强，可以看到bfs的搜索策略非常类似于社区发现所得到的社区相似性，即更加接近一种直观容易解释的思路，偏向于一阶和二阶近邻这类的相似性，也就是距离接近，特别是直接连接的nodes之间的embedding结果接近，也就是“结构性”，可以理解为，BFS的搜索策略能够捕捉到“近邻相似性”；
而dfs则看起来比较不那么直观了，但是其实从传统graph的一些评价指标可以进行分析和总结，例如pagerank，pagerank值计算的是节点的流行度，比如说中国的明星和美国的明星，二者的近邻相似度肯定是非常低的，但是它们都在“演艺圈”这个巨大的graph中扮演着相似的角色，这一点我们可以通过pagerank这类统计方法来得到，成龙和杰森斯坦森之间的pagerank值的差异相对于成龙或杰森斯坦森和其它18线小明星的pagerank值的差异明显要小得多，而我们的dfs捕捉的相似性指的就是这种相似性，即 节点在更大的范围内（可能横跨多个社区而形成的大子图，具体根据random walk的步数来决定）中扮演的角色（同质性，同样性质的相似性），例如我们看第二幅图，连接不同nodes的“枢纽节点”其embedding的相似度往往比较高，从社交网络的角度来说，这些枢纽节点都是“交际花”，虽然她们彼此之间的直接相连的近邻相似度可能非常低，但是它们“交际”的性质是非常相似的，即在局部的子图中扮演着相似的角色；
然后是关于deepwalk的问题，首先我们需要知道的是，目前开源的框架里大部分只实现了node2vec，因为我们可以通过将p和q这两个超参数设定为1，使得node2vec退化为deepwalk来使用，即：
上图的公式中，p和q均为1的时候，node2vec退化为deepwalk，因此实际上我们可以知道，deepwalk本身并不是基于什么dfs之类的做游走的，就是一个纯粹的随机乱走，它即可以捕捉到部分结构性也可以捕捉到部分同质性，具体deepwalk能够捕捉到什么样的性质，就看天意了，所以我们不能说deepwalk就是基于dfs的游走策略游走主要捕捉同质性，而应该说deepwalk同时捕捉两种特性然而两种特性都捕捉的不是非常到位，而node2vec更像是基于deepwalk上的一个灵活的框架，因为我们可以通过指定超参数来改变我们想要进行embedding的目的，如果我们面临的实际问题，定义相似性为同质性，这里举个例子：
以欺诈问题为例，我们看一下capital one的这篇经典论文里的场景：
将二分图投影成2个同构图，然后利用deepwalk各自生成embedding：
用户-用户关系图：两个用户在同一个商户中发生交易，则两个用户之间存在一条边。
商户-商户关系图：同一个用户与两个商户发生交易，则两个商户之间有一条边。
我们假设使用的是 用户-用户关系图，并且认为欺诈分子的欺诈模式是 欺诈用户集中在两三家商户上疯狂消费刷漏洞骗钱，则在graph中，这些用户会呈现出比较明显的社区结构，即他们之间的距离都是非常接近的甚至可能互相直接连接，而不同用户在不同的局部社区结构中扮演的相同角色的相似性，和欺诈的手段完全没有关系，那么这个时候我们可以使用node2vec，令p越小越好，q越大越好从而尽量cover这种近邻相似性，而反过来，如果欺诈分子的欺诈模式是分散的，例如一个欺诈用户x1在a、b、c三个商家消费，一个欺诈用户x2的d、e、f三个商家消费，二者的近邻相似性较低，但是假设存在这种情况，x1和x2之间虽然存在一定的距离，但是这个距离并不十分远，这两个用户分别处于近邻的社区结构，并且恰好分别是这两个社区结构中流行度很高的用户，则我们可以考虑使用node2vec，令p越大越好，q越小越好从而cover这种“网络角色”相似性，注意，这里我们强调的是近邻的社区，因为假设两个节点之间虽然在各自的局部社区扮演相同或相似的角色，比如流行度都很高，但是这两个局部社区之间的间隔非常的遥远，那么node2vec根本cover不到这种远距离局部社区相同或相似角色的相似性，因为我们random walk的步数是有限的，比如二者距离了50个hops，而walks的数量只有10步，走到死也没法恰好在同一个random walk产生的序列里；
因此，只能说deepwalk能够捕捉节点之间的共现性，这个共现性可能包含了同质性也可能包含了结构性，而node2vec可以让使用者灵活的定义我们要捕捉更多的结构性还是更多的同质性，置于基于整个graph的同质性，比如上面所说的远距离局部社区相同或者相似角色的embedding问题，我们就需要考虑使用别的embedding算法来解决了，比如计算复杂度非常高基本没法在大规模graph上运行的struc2vec。
