Node2vec

作者: Jarkata | 来源:发表于2021-06-22 11:40 被阅读0次

    本文转载自 【Graph Embedding】node2vec:算法原理,实现和应用 - 浅梦的文章 - 知乎
    https://zhuanlan.zhihu.com/p/56542707

    前面介绍过基于DFS邻域的DeepWalk和基于BFS邻域的LINE

    node2vec是一种综合考虑DFS邻域和BFS邻域的Graph Embedding方法。简单来说,可以看作是deepwalk的一种扩展,是结合了DFS和BFS随机游走的deepwalk

    node2vec算法原理

    优化目标

    f(u)是将顶点u映射为embedding向量的映射函数,对于图中每个顶点u,定义N_S(u)为通过采样策略S采样出的顶点u的近邻点集合。

    node2vec优化的目标是给定每个顶点条件下,令其近邻顶点(如何定义近邻顶点很重要)出现的概率最大。

    为了将上述最优化问题可解,文章提出两个假设:

    • 条件独立性假设
      假设给定源顶点下,其近邻顶点出现的概率与近邻集合中其余顶点无关

    • 特征空间对称性假设
      这里是说一个顶点作为源顶点和作为近邻顶点的时候共享同一套embedding向量。(对比LINE中的2阶相似度,一个顶点作为源点和近邻点的时候是拥有不同的embedding向量的)
      在这个假设下,上述条件概率公式可以表示为

    根据以上两个假设条件,最终的目标函数表示为:


    由于归一化因子

    的计算代价高,所以采用负采样技术优化。

    顶点序列采样策略

    node2vec依然采用随机游走的方式获取顶点的近邻序列,不同的是node2vec采用的是一种有偏的随机游走。

    给定当前顶点v,访问下一个顶点x的概率为:

    其中\pi_{vx}是顶点v和顶点x之间的未归一化转移概率,Z是归一化常数。

    node2vec引入两个超参数pq来控制随机游走的策略,假设当前随机游走经过边(t,v)到达顶点v\pi_{vx} = \alpha_{pq}(t,x) \cdot w_{vx}w_{vx}是顶点vx之间的边权


    d_{tx}为顶点t和顶点x之间的最短路径距离。

    考虑超参数pq对游走策略的影响:

    • Return parameter, p

    • In-out parameter, q


    学习算法

    采样完顶点序列后,剩下的步骤就和deepwalk一样了,用word2vec去学习顶点的embedding向量。 值得注意的是node2vecWalk中不再是随机抽取邻接点,而是按概率抽取,node2vec采用了Alias算法进行顶点采样。
    Alias Method:时间复杂度O(1)的离散采样方法

    node2vec算法伪代码

    node2vecWalk

    通过上面的伪代码可以看到,node2vec和deepwalk非常类似,主要区别在于顶点序列的采样策略不同,所以这里我们主要关注node2vecWalk的实现。
    由于采样时需要考虑前面2步访问过的顶点,所以当访问序列中只有1个顶点时,直接使用当前顶点和邻居顶点之间的边权作为采样依据。 当序列多余2个顶点时,使用文章提到的有偏采样

    作者:浅梦
    链接:https://zhuanlan.zhihu.com/p/56542707
    来源:知乎
    著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
    
    def node2vec_walk(self, walk_length, 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 = list(G.neighbors(cur))        
            if len(cur_nbrs) > 0:            
                if len(walk) == 1:                
                    walk.append(cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])])            
                else:                
                    prev = walk[-2]                
                    edge = (prev, cur)                
                    next_node = cur_nbrs[alias_sample(alias_edges[edge][0],alias_edges[edge][1])]                
                    walk.append(next_node)        
            else:            
                break
        return walk
    

    构造采样表

    preprocess_transition_probs分别生成alias_nodesalias_edgesalias_nodes存储着在每个顶点时决定下一次访问其邻接点时需要的alias表(不考虑当前顶点之前访问的顶点)。
    alias_edges存储这在前一个访问顶点为t,当前访问顶点为v时到下一个顶点x的未归一化转移概率\pi_{vx} = \alpha_{pq}(t,x) \cdot w_{vx}

    def get_alias_edge(self, t, v):
        G = self.G    
        p = self.p    
        q = self.q
        unnormalized_probs = []    
        for x in G.neighbors(v):        
            weight = G[v][x].get('weight', 1.0)# w_vx        
            if x == t:# d_tx == 0            
                unnormalized_probs.append(weight/p)        
            elif G.has_edge(x, t):# d_tx == 1            
                unnormalized_probs.append(weight)        
            else:# d_tx == 2            
                unnormalized_probs.append(weight/q)    
        norm_const = sum(unnormalized_probs)    
        normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]
        return create_alias_table(normalized_probs)
    
    def preprocess_transition_probs(self):
        G = self.G
        alias_nodes = {}    
        for node in G.nodes():        
            unnormalized_probs = [G[node][nbr].get('weight', 1.0) for nbr in G.neighbors(node)]        
            norm_const = sum(unnormalized_probs)        
            normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]                 
            alias_nodes[node] = create_alias_table(normalized_probs)
        alias_edges = {}
        for edge in G.edges():        
            alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])
        self.alias_nodes = alias_nodes    
        self.alias_edges = alias_edges
        return
    

    node2vec应用

    使用node2vec在wiki数据集上进行节点分类任务和可视化任务。 wiki数据集包含 2,405 个网页和17,981条网页之间的链接关系,以及每个网页的所属类别。 通过简单的超参搜索,这里使用p=0.25,q=4的设置。

    G = nx.read_edgelist('../data/wiki/Wiki_edgelist.txt',create_using=nx.DiGraph(),nodetype=None,data=[('weight',int)])
    
    model = Node2Vec(G,walk_length=10,num_walks=80,p=0.25,q=4,workers=1)
    model.train(window_size=5,iter=3)    
    embeddings = model.get_embeddings()
    
    evaluate_embeddings(embeddings)
    plot_embeddings(embeddings)
    
    

    分类任务

    'micro-F1': 0.6548856548856549,
    'macro-F1': 0.5725043917959665
    这个结果相比于DeepWalk和LINE是有提升的。

    可视化

    这个结果相比于DeepWalk和LINE可以看到不同类别的分布更加分散了。


    最后补充一个node2vec在业界的应用介绍

    当机器学习遇上复杂网络:解析微信朋友圈 Lookalike 算法

    相关文章

      网友评论

          本文标题:Node2vec

          本文链接:https://www.haomeiwen.com/subject/pcbcyltx.html