精华内容
下载资源
问答
  • 【Graph Embedding】node2vec:算法原理,实现和应用

    万次阅读 多人点赞 2019-02-12 20:12:13
    前面介绍过基于DFS邻域的DeepWalk和基于BFS邻域的LINE。node2vec则是一种综合考虑...简单来说,node2vecdeepwalk的一种扩展,可以看作是结合了dfs和bfs随机游走的deepwalk。 nodo2vec 算法原理 优化目标 设f(u)...

    前面介绍过基于DFS邻域的DeepWalk和基于BFS邻域的LINE。
    在这里插入图片描述

    DeepWalk:算法原理,实现和应用
    LINE:算法原理,实现和应用

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

    nodo2vec 算法原理

    优化目标

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

    node2vec优化的目标是给定每个顶点条件下,令其近邻顶点出现的概率最大。

    maxfuVlogPr(NS(U)f(u))max_f {\sum_{u\in V}\log{Pr(N_S(U)|f(u))}}

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

    • 条件独立性假设
      假设给定源顶点下,其近邻顶点出现的概率与近邻集合中其余顶点无关。
      Pr(Ns(u)f(u))=niNs(u)Pr(nif(u))Pr(N_s(u)|f(u))=\prod_{n_i\in N_s(u)} Pr(n_i|f(u))
    • 特征空间对称性假设
      这里是说一个顶点作为源顶点和作为近邻顶点的时候共享同一套embedding向量。(对比LINE中的2阶相似度,一个顶点作为源点和近邻点的时候是拥有不同的embedding向量的)
      在这个假设下,上述条件概率公式可表示为Pr(nif(u))=expf(ni)f(u)vVexpf(v)f(u)Pr(n_i|f(u))=\frac{\exp{f(n_i)\cdot f(u)}}{\sum_{v\in V}{\exp{f(v)\cdot f(u)}}}

    根据以上两个假设条件,最终的目标函数表示为
    maxfuV[logZu+niNs(u)f(ni)f(u)]max_f{\sum_{u\in V}[-\log{Z_u}+\sum_{n_i\in N_s(u)}{f(n_i)\cdot f(u)}]}

    由于归一化因子Zu=niNs(u)exp(f(ni)f(u))Z_u=\sum_{n_i\in N_s(u)}{\exp(f(n_i)\cdot f(u))}的计算代价高,所以采用负采样技术优化。

    采样策略

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

    给定当前顶点vv,访问下一个顶点xx的概率为
    P(ci=xci1=v)={πvxZif (v,x)E0otherwise P(c_i=x|c_{i-1}=v)=\left\{ \begin{aligned} \frac{\pi_ {vx}}{Z} & & \text{if }(v,x)\in E \\ 0 & & \text{otherwise} \\ \end{aligned} \right.
    πvx\pi_{vx}是顶点vv和顶点xx之间的未归一化转移概率,ZZ是归一化常数。

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

    αpq(t,x)={1p=if dtx=01=if dtx=11q=if dtx=2 \alpha_{pq}(t,x)=\left\{ \begin{aligned} \frac{1}{p} & = & \text{if }d_{tx}=0\\ 1 & = & \text{if }d_{tx}=1\\ \frac{1}{q} & = & \text{if }d_{tx}=2\\ \end{aligned} \right.
    dtxd_{tx}为顶点tt和顶点xx之间的最短路径距离。

    下面讨论超参数ppqq对游走策略的影响

    • Return parameter,p
      参数pp控制重复访问刚刚访问过的顶点的概率。
      注意到pp仅作用于dtx=0d_{tx}=0的情况,而dtx=0d_{tx}=0表示顶点xx就是访问当前顶点vv之前刚刚访问过的顶点。
      那么若pp较高,则访问刚刚访问过的顶点的概率会变低,反之变高。
    • In-out papameter,q
      qq控制着游走是向外还是向内,若q>1,随机游走倾向于访问和tt接近的顶点(偏向BFS)。若q<1q<1,倾向于访问远离tt的顶点(偏向DFS)。

    下面的图描述的是当从t访问到v时,决定下一个访问顶点时每个顶点对应的α\alpha
    在这里插入图片描述

    学习算法

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

    node2vec核心代码

    node2vecWalk

    通过上面的伪代码可以看到,node2vec和deepwalk非常类似,主要区别在于顶点序列的采样策略不同,所以这里我们主要关注node2vecWalk的实现。

    由于采样时需要考虑前面2步访问过的顶点,所以当访问序列中只有1个顶点时,直接使用当前顶点和邻居顶点之间的边权作为采样依据。
    当序列多余2个顶点时,使用文章提到的有偏采样。

    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存储着在前一个访问顶点为tt,当前顶点为vv时决定下一次访问哪个邻接点时需要的alias表。

    get_alias_edge方法返回的是在上一次访问顶点tt,当前访问顶点为vv时到下一个顶点xx的未归一化转移概率πvx=αpq(t,x)wvx\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的设置。

    本例中的训练,评测和可视化的完整代码在下面的git仓库中,

    https://github.com/shenweichen/GraphEmbedding

    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.6757
    macro-F1: 0.5917

    这个结果相比于DeepWalk和LINE是有提升的。

    可视化

    这个结果相比于DeepWalk和LINE可以看到不同类别的分布更加分散了。
    在这里插入图片描述

    参考资料

    图算法干货汇总

    我把近年来主流的图表示学习方法的paper和对应的代码实现进行了汇总整理,扫码关注公众号【浅梦的学习笔记】,后台回复【图算法】即可打包下载。

    在这里插入图片描述

    展开全文
  • 看到一个很有意思的算法,而且腾讯朋友圈lookalike一文中也有提及到,于是蹭一波热点,学习一下。论文是也发KDD2016 ...a、微博洪亮劼 :【论文每日读】node2vec: Scalable Feature Learning for Networksb

    看到一个很有意思的算法,而且腾讯朋友圈lookalike一文中也有提及到,于是蹭一波热点,学习一下。论文是也发KDD2016
    .
    .

    一、主要论文:node2vec: Scalable Feature Learning for Networks

    本节引用自
    a、微博洪亮劼 :【论文每日读】node2vec: Scalable Feature Learning for Networks

    b、简书:node2vec: Scalable Feature Learning for Networks

    本文的特征抽取方式类似于聚类分析的非监督方法,本质上都是利用相邻节点之间的联系。文中提到了网络中的节点一般有两种相似度量:1.内容相似性,2.结构相似性。其中内容相似性主要是相邻节点之间的相似性,而结构上相似的的点并不一定是相邻的,可能隔得很远,这也是文中为何要把BFS和DFS相结合来选择邻居节点的原因。

    文章的主要想法就是,利用SkipGram的方法,来为Networks抽取Representation。那么,自然,根据SkipGram的思路,最重要的就是定义这个Context,或者说是Neighborhood。​从文本的角度来说,这个Neighborhood当然就是当前Word周围的字,这个定义非常自然。但是对于Graph或者Network来说就来得没那么容易了。

    文章阐述了一般所采用Depth-First Search或者是Breadth-First Search来Sample一个Node的周边Node的问题。简单来说,BFS比较容易有一个Microscopic的View而DFS容易有一个Macro-view,两者都有Representative的问题。

    文章的核心思想是采用Random Walk来代替DFS或者BFS。文章定义了一种二阶的Random Walk,拥有两个参数,来控制多大的概率反复经过一些Node和控制所谓的Inward和Outward。总之,整个Random Walk的目的就是在DFS和BFS之间采取某种平衡。

    文章虽然提出的是关于Node Feature提取的算法,但是Edge Feature也可以很容易从Node Feature导出。

    总体感觉是,硬要用SkipGram或者WordVec的想法在Networks上做,还显得比较牵强。因为有这个Neighborhood的概念,在Graph上,反而不是那么直观得定义,因此所有类似的工作都显得比较别扭。当然,这篇文章也不失为一种不错的Heuristic。​
    这里写图片描述

    这里写图片描述

    .
    .
    .

    二、python实现

    github网址

    案例:
    To run node2vec on Zachary’s karate club network, execute the following command from the project home directory:

    python src/main.py --input graph/karate.edgelist --output emb/karate.emd

    Options

    You can check out the other options available to use with node2vec using:

    python src/main.py --help

    Input

    The supported input format is an edgelist:

    node1_id_int node2_id_int <weight_float, optional>

    The graph is assumed to be undirected and unweighted by default. These options can be changed by setting the appropriate flags.

    Output

    The output file has n+1 lines for a graph with n vertices. The first line has the following format:

    num_of_nodes dim_of_representation

    The next n lines are as follows:

    node_id dim1 dim2 ... dimd

    where dim1, … , dimd is the d-dimensional representation learned by node2vec.
    .
    .
    .

    三、腾讯对node2vec的应用

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

    这个横轴是与广告进行互动的好友个数,纵轴是用户对广告的关注率(包括查看,点赞或者评论),我们发现这个关注率会随着好友数的增加而上升。这个数据拐点差不多是3到5个好友。
    这里写图片描述

    重点会挖掘这两个价值,就是社交同质性和社交影响力。
    实际上在一个社交网络的节点也是这样的,我们经常会存在一些大的节点,他会有非常多的好友,有的人好友就达不到那么多。所以说其实在社交网络里面的一个节点的分布也是幂律分布。如何把Wodrd2Vec迁移到node2vec,这个时候就要产生一个节点的序列,它对应到了自然语言处理的一条句子,图结构里面的节点相当于NLP的一个单词。

    所以在图网络上按照一个搜索的方法生成节点序列,这个节点的序列可以对应到自然语言的一个句子,后面我们通过Wodrd2Vec的框架,将节点embedding为一个向量。所以对于做network embedding的时候,这个生成节点序列的搜索策略非常重要。最简单的一个方法,就是随机游走,随机游走一方面生成节点序列,另一方面也是对图的一种采样,降低了计算量。

    这里写图片描述

    比如说我们的一个社交网络,我的同学会形成一个社团,设计这个P往回走,就更容易走到我这个群体。当P越大,它会越能体现同质性。Q越大的时候,它其实能够体现这种结构的相似性,不同的节点有不同的作用。比如说F节点和E节点它是连接这两个社团的桥接点。当Q大的时候,它体现的是网络结构的相似性。这时候我们怎么选P和Q?这个可以根据实际任务进行半监督的学习。

    这里写图片描述

    给大家看一下node2vec的结果,先给大家看这个算法的输出。这里有一个简单的图,做embedding之后的结果,1和2的节点向量是一样的,它会是重叠的一个向量,3、4、5、6也是一个重合的节点,它表达的是什么呢?为什么1和2完全重叠?其实1和2的网络环境是一模一样的,这个embedding的结果表达是是节点的社交网络环境,也就是我们说的拓扑特征。
    对社交相似性的学习框架,大家可以看下面的图。 我们建立一个回归的model。现在做的是SVR模型。输入好友网络,沟通网络、文章的转发阅读网络等等,进行embedding得到特征向量表达,通过SVR模型,学习到这些特征和广告相似度的函数关系。这个函数关系计算出好友相似度,可以对好友进行排序。

    这里写图片描述

    我们看一下算法的效果。我们评估算法的效果,最直接的就是说我有多个算法,广告主需要100万的用户,我这几个算法都给出100万用户,然后看一下这100万的用户点击量是怎么样的,我们叫Lift值。其他的算法跟它进行对比,看一下它的效果有没有提升。那我们的算法相比直接的二分类模型有2倍-3倍的lift。

    这里写图片描述

    .


    延伸一:网络与词向量

    来源于:网络与几何的纠缠 | 张江
    最近,深度学习成为了科学界的新宠。人们将大量的数据扔进了神经网络中,以期待它能够自己学习到数据中蕴藏的模式。然而,目前的深度学习处理的数据大多仅仅局限在图像和文本,但却不包括网络。这是因为,网络的本质在于节点之间的连接信息,而这种信息很难被结构化为标准的数据。怎么办呢?

    答案就在于空间。只要我们将网络嵌入到了一个几何空间中,我们就可以将每个节点的坐标视作该节点的特征,从而放到神经网络中进行学习和训练。那么,针对一个一般性的网络,我们又如何计算每一个节点的空间坐标呢?

    答案就在于DeepWalk算法。它首先在网络上释放大量的随机游走粒子,这些粒子在给定的时间内就会走出一个节点构成的序列。我们不妨将节点视作单词,于是它们生成的序列就构成了句子,我们便可以得到一种节点由序列构成的“语言”。接下来,我们就可以应用强大的Word2Vec算法,计算出每个节点“单词”的向量表示,也就是空间坐标了。
    这里写图片描述
    这种节点嵌入的算法可以很好地反映节点之间的连接信息,或者我们可以将DeepWalk算法得到的节点坐标视作对每个节点连接信息的编码。那些连接结构上相似的节点会在空间中彼此靠近。
    这里写图片描述
    有了从结构到空间的这种转换,我们便可以利用普通的聚类和分类算法来对复杂网络进行处理。
    .


    延伸二:NE(Network Embedding)论文小览

    来源:http://blog.csdn.net/dark_scope/article/details/74279582

    自从word2vec横空出世,似乎一切东西都在被embedding,今天我们要关注的这个领域是Network Embedding,也就是基于一个Graph,将节点或者边投影到低维向量空间中,再用于后续的机器学习或者数据挖掘任务,对于复杂网络来说这是比较新的尝试,而且取得了一些效果。

    本文大概梳理了最近几年流行的一些方法和论文,paper主要是来自thunlp/NRLPapers 这个List,并掺杂了一些其他论文。大概看了一遍,简单总结一下,希望对大家有所帮助,如有不严谨的地方,还望指正。
    抛开一些传统的流形学习方法不谈,下面大概以这个outline组织(区分并不严格):
    此处输入图片的描述
    这里写图片描述

    DeepWalk(Online Learning of Social Representations.)

    DeepWalk是KDD 2014的一篇文章,彼时word2vec在文本上的成功应用掀起来一波向量化的浪潮,word2vec是根据词的共现关系,将词映射到低维向量,并保留了语料中丰富的信息。DeepWalk算法思路其实很简单,对图从一个节点开始使用random walk来生成类似文本的序列数据,然后将节点id作为一个个「词」使用skip gram训练得到「词向量」。
    思路虽然简单,背后是有一定道理的,后面一些工作有证明这样做其实等价于特殊矩阵分解(Matrix Factorization)。而DeepWalk本身也启发了后续的一系列工作。

    node2vec(Scalable Feature Learning for Networks)

    node2vec在DW的基础上,定义了一个bias random walk的策略生成序列,仍然用skip gram去训练。
    论文分析了BFS和DFS两种游走方式,保留的网络结构信息是不一样的。
    DeepWalk中根据边的权重进行随机游走,而node2vec加了一个权重调整参数α:t是上一个节点,v是最新节点,x是候选下一个节点。d(t,x)是t到候选节点的最小跳数。
    通过不同的p和q参数设置,来达到保留不同信息的目的。当p和q都是1.0的时候,它等价于DeepWalk。

    这里写图片描述

    MMDW(Max-Margin DeepWalk Discriminative Learning of Network Representation)

    DW本身是无监督的,如果能够引入label数据,生成的向量对于分类任务会有更好的作用。
    之前提到过有证明DW实际上是对于一个特殊矩阵M的分解,
    这篇文章将DeepWalk和Max-Margin(SVM)结合起来,从损失函数看是这两部分组成:
    1.训练的时候是分开优化,固定X,Y优化W和ξ,其实就是multi class 的 SVM。
    2.固定W和ξ优化X,Y的时候稍微特殊一点,算了一个biased Gradient,因为损失函数里有x和w的组合。
    这样在训练中同时优化discrimination和representation两部分,达到一个好的效果。

    这里写图片描述

    TADW(Network Representation Learning with Rich Text Information.)

    文章里有DeepWark等同于M的矩阵分解的简单证明,而在实际中,一些节点上旺旺会有文本信息,所以在矩阵分解这个框架中,将文本直接以一个子矩阵的方式加入,会使学到的向量包含更丰富的信息。
    文本矩阵是对TFIDF矩阵的SVD降维结果。
    此处输入图片的描述
    .


    延伸三:基于word2vec和doc2vec用户表示方法

    (1)用户表示方法

    本文采用了五种用户表示方法,分别是One-Hot表示、基于用户文本的分布式表示、基于用户关系网络的分布式表示、半监督的网络分布式表示和联合表示。
    本节使用word2vec和doc2vec两个工具通过用户的文本数据分别学习用户的分布式表示,并采用逻辑回归分类器对用户的不同属性进行分类。

    利用基于word2vec(生成的向量长度为100,窗口大小为5,模型为CBOW模型,算法为Hierarchical Softmax模型)生成的用户分布式表示实验结果见表 2。
    这里写图片描述
    利用基于doc2vec(生成的向量长度为100,窗口大小为5,模型为CBOW模型,算法为Hierarchical Softmax模型错误。)生成的用户分布式表示实验结果见表3。
    这里写图片描述
    从实验结果的对比可以看出,单纯词向量累加的形式所获取到的用户分布式表示并不能有效地提高实验的效果,相反,各个参数都有所下降。与之相比,采用doc2vec工具直接得到的用户分布式的表现表示虽然较之词袋模型仍然有所下降,但是却要高于word2vec累加的表现。

    (2)用户的关系网络

    我们使用Deepwalk和LINE两个工具通过用户的关系网络数据分别学习用户的分布式表示,并采用逻辑回归分类器对用户的不同属性进行分类。

    来源:赛尔原创 | 用户表示方法对新浪微博中用户属性分类性能影响的研究
    作者: 哈工大SCIR 孙晓飞,丁效,刘挺
    .


    延伸四:Flownetwork:流网络的开源Python包

    该包的主要功能如下:https://github.com/chengjun/flownetwork
    来源: 集智小仙女,《Flownetwork:流网络的开源Python包》

    南京大学的王成军老师和芝加哥大学的吴令飞博士开发了一个开源工具包Flownetwork,将常用的计算都集成到了一起。初学者可以直接调用该包完成各种有关开放流网络的计算。
    这里写图片描述

    然后进行注意力网络的分析:

    首先我们可以用help语句来查看一下这个流网络的结构:

    help(fn.constructFlowNetwork)
    Help on function constructFlowNetwork in module flownetwork.flownetwork:
    constructFlowNetwork(C)
       C is an array of two dimentions, e.g.,
       C = np.array([[user1, item1],
          [user1, item2],
          [user2, item1],
          [user2, item3]])
       Return a balanced flow networ

    在了解了这个网络的架构之后,我们就可以自己创建一个流网络:

    demo = fn.attention_data
    gd = fn.constructFlowNetwork(demo)

    为了更好的了解这个流网络的结构,我们可以利用matplotlib画出这个demo的流网络:

    # drawing a demo network
    fig = plt.figure(figsize=(12, 8),facecolor='white')
    pos={0: np.array([ 0.2 ,  0.8]),
     2: np.array([ 0.2,  0.2]),
     1: np.array([ 0.4,  0.6]),
     6: np.array([ 0.4,  0.4]),
     4: np.array([ 0.7,  0.8]),
     5: np.array([ 0.7,  0.5]),
     3: np.array([ 0.7,  0.2 ]),
     'sink': np.array([ 1,  0.5]),
    'source': np.array([ 0,  0.5])}
    width=[float(d['weight']*1.2) for (u,v,d) in gd.edges(data=True)]
    
    edge_labels=dict([((u,v,),d['weight']) for u,v,d in gd.edges(data=True)])nx.draw_networkx_edge_labels(gd,pos,edge_labels=edge_labels,
    font_size = 15, alpha = .5)
    
    nx.draw(gd, pos, node_size = 3000, node_color = 'orange',
     alpha = 0.2, width = width, edge_color='orange',style='solid')
    nx.draw_networkx_labels(gd,pos,font_size=18)
    
    plt.show()

    然后我们就画出了这个demo的流网络图:

    这里写图片描述

    展开全文
  • node2vec的一些理解

    千次阅读 2020-07-22 22:11:56
    node2vec也是一种网络嵌入的表示方法,它是基于DeepWalk的基础上进行改进的。主要改进的地方在于它在随机游走的过程中加入了一个权重,使得游走可以采用深度优先和广度优先的策略进行游走。 Search bias α 使得随机...

    node2vec

    node2vec也是一种网络嵌入的表示方法,它是基于DeepWalk的基础上进行改进的。主要改进的地方在于它在随机游走的过程中加入了一个权重,使得游走可以采用深度优先和广度优先的策略进行游走。

    Search bias α

    使得随机游走产生片偏差的最简单的方法是根据静态边缘权重WvxW_vx进行采样,在未加权图的情况下Wvx=1W_{vx}=1,但是这并不能解释我们的网络结构,并且指导我们探索不同的网络邻居。此外,与BFS和DFS不同,BFS和DFS是分别适用于结构等价性和同质性的极端抽样范式,我们的随机游动应该适应这样一个事实:这些等价性的概念不是竞争的或排他的,而现实世界的网络通常表现出两者的混合。
    所以我们定义了一个2阶随机游走,并且定义了两个参数分别是p和q用来指导我们进行随机游走。
    search bias α
    假设我们有一个随机游走已经穿过了(t,v)节点并且现在暂时居住在如图所示的V节点。我们现在要考虑下一步怎么走,那么我们可以使用边(v,x)的转移概率ΠvxΠ_{vx}用来引导我们从v的下一步怎么走。我们假定了一个转移概率Πvx=αpq(t,x)WvxΠ_vx=α_{pq}(t,x)*W_{vx} 其中αpq(t,x)α_{pq}(t,x)定义如下:

    其中dtxd_{tx}表示t和x之间的最短路径,注意的是dtxd_{tx}的取值一定是{0,1,2}的其中一个,所以p,q两个参数能够很好的指导游走。
    例如当终点为t时,我们相当于往回走了,不为t时我们则是向外游走或是向深游走。
    返回参数 p:p代表我们游走时重复游走的可能性,如果我们把p设置为一个很高的值(> max(q,1))则可以用来确保我们有极小的可能性重复游走一个节点(除非下一个节点没有其他邻居)。这个策略鼓励我们适度探索,而不是产生冗余。另一方面,如果我们把p的值设为很小(< min(q,1)),则他会使得walk接近我们的起始位置。
    In-Out参数 q:他更倾向于访问距离节点t更远的节点,这种行为反映了鼓励向外探索的DFS。然而,这里的一个本质区别是,我们在随机行走框架中实现了类似DFS的探索。

    node2vec 算法流程

    node2vec算法流程
    如上图所示,我们一开始主要是要进行我们的静态权重的赋值,用它来引导我们继续随机游走得到随机游走序列,然后我们将得到的序列利用skip-gram模型进行嵌入,最后得到嵌入矩阵。

        def _precompute_probabilities(self):
            """
            Precomputes transition probabilities for each node.
            """
    
            d_graph = self.d_graph
    
            nodes_generator = self.graph.nodes() if self.quiet \
                else tqdm(self.graph.nodes(), desc='Computing transition probabilities')
    
            for source in nodes_generator:
    
                # Init probabilities dict for first travel
                if self.PROBABILITIES_KEY not in d_graph[source]:
                    d_graph[source][self.PROBABILITIES_KEY] = dict()
    
                for current_node in self.graph.neighbors(source):
    
                    # Init probabilities dict
                    if self.PROBABILITIES_KEY not in d_graph[current_node]:
                        d_graph[current_node][self.PROBABILITIES_KEY] = dict()
    
                    unnormalized_weights = list()
                    d_neighbors = list()
    
                    # Calculate unnormalized weights
                    for destination in self.graph.neighbors(current_node):
    
                        p = self.sampling_strategy[current_node].get(self.P_KEY,
                                                                     self.p) if current_node in self.sampling_strategy else self.p
                        q = self.sampling_strategy[current_node].get(self.Q_KEY,
                                                                     self.q) if current_node in self.sampling_strategy else self.q
    
                        if destination == source:  # Backwards probability
                            ss_weight = self.graph[current_node][destination].get(self.weight_key, 1) * 1 / p
                        elif destination in self.graph[source]:  # If the neighbor is connected to the source
                            ss_weight = self.graph[current_node][destination].get(self.weight_key, 1)
                        else:
                            ss_weight = self.graph[current_node][destination].get(self.weight_key, 1) * 1 / q
    
                        # Assign the unnormalized sampling strategy weight, normalize during random walk
                        unnormalized_weights.append(ss_weight)
                        d_neighbors.append(destination)
    
                    # Normalize
                    unnormalized_weights = np.array(unnormalized_weights)
                    d_graph[current_node][self.PROBABILITIES_KEY][
                        source] = unnormalized_weights / unnormalized_weights.sum()
    
                    # Save neighbors
                    d_graph[current_node][self.NEIGHBORS_KEY] = d_neighbors
    
                # Calculate first_travel weights for source
                first_travel_weights = []
    
                for destination in self.graph.neighbors(source):
                    first_travel_weights.append(self.graph[source][destination].get(self.weight_key, 1))
                first_travel_weights = np.array(first_travel_weights)
                d_graph[source][self.FIRST_TRAVEL_KEY] = first_travel_weights / first_travel_weights.sum()
    

    具体代码实现如图所示,我们首先进入函数利用d_graph生成一个字典,在其中加入概率标签,然后我们通过循环节点以及节点的邻居对权重进行赋值,同时对我们的p,q进行策略的更改。最后的d_graph则是我们修改之后的带有我们设置的权重的重要参数,然后我们将d_graph带入到我们的游走序列生成的函数当中去。

    def parallel_generate_walks(d_graph: dict, global_walk_length: int, num_walks: int, cpu_num: int,
                                sampling_strategy: dict = None, num_walks_key: str = None, walk_length_key: str = None,
                                neighbors_key: str = None, probabilities_key: str = None, first_travel_key: str = None,
                                quiet: bool = False) -> list:
        """
        Generates the random walks which will be used as the skip-gram input.
    
        :return: List of walks. Each walk is a list of nodes.
        """
    
        walks = list()
    
        if not quiet:
            pbar = tqdm(total=num_walks, desc='Generating walks (CPU: {})'.format(cpu_num))
    
        for n_walk in range(num_walks):
    
            # Update progress bar
            if not quiet:
                pbar.update(1)
    
            # Shuffle the nodes
            shuffled_nodes = list(d_graph.keys())
            random.shuffle(shuffled_nodes)
    
            # Start a random walk from every node
            for source in shuffled_nodes:
    
                # Skip nodes with specific num_walks
                if source in sampling_strategy and \
                        num_walks_key in sampling_strategy[source] and \
                        sampling_strategy[source][num_walks_key] <= n_walk:
                    continue
    
                # Start walk
                walk = [source]
    
                # Calculate walk length
                if source in sampling_strategy:
                    walk_length = sampling_strategy[source].get(walk_length_key, global_walk_length)
                else:
                    walk_length = global_walk_length
    
                # Perform walk
                while len(walk) < walk_length:
    
                    walk_options = d_graph[walk[-1]].get(neighbors_key, None)
    
                    # Skip dead end nodes
                    if not walk_options:
                        break
    
                    if len(walk) == 1:  # For the first step
                        probabilities = d_graph[walk[-1]][first_travel_key]
                        walk_to = np.random.choice(walk_options, size=1, p=probabilities)[0]
                    else:
                        probabilities = d_graph[walk[-1]][probabilities_key][walk[-2]]
                        walk_to = np.random.choice(walk_options, size=1, p=probabilities)[0]
    
                    walk.append(walk_to)
    
                walk = list(map(str, walk))  # Convert all to strings
    
                walks.append(walk)
    
        if not quiet:
            pbar.close()
    
        return walks
    

    生成游走的序列的代码如上图所示,我们可以看出将d_graph当中的概率取出,然后带入到np.random.choice这个函数当中去,这样我们就是按照一定的概率进行随机游走,而游走的概率是可以通过修改p,q两个参数进而进行修改的。最后我们则将我们得到的游走序列walks带入skip-gram模型进行训练,得到我们想要的嵌入矩阵。

        def fit(self, **skip_gram_params):
            """
            Creates the embeddings using gensim's Word2Vec.
            :param skip_gram_params: Parameteres for gensim.models.Word2Vec - do not supply 'size' it is taken from the Node2Vec 'dimensions' parameter
            :type skip_gram_params: dict
            :return: A gensim word2vec model
            """
    
            if 'workers' not in skip_gram_params:
                skip_gram_params['workers'] = self.workers
    
            if 'size' not in skip_gram_params:
                skip_gram_params['size'] = self.dimensions
    
            return gensim.models.Word2Vec(self.walks, **skip_gram_params)
    
    展开全文
  • 京东广告算法面试

    2021-06-11 22:59:48
    没有答得很好得问题 一面 1.bert原理->transformer简介(attention机制,除了self attention还有没有用到其他attention,mask原理) 2.xgb原理->相比GBDT有哪些改进?...6.Note2vecDeepwalk知道吗?

    没有答得很好得问题

    一面

    1.bert原理->transformer简介(attention机制,除了self attention还有没有用到其他attention,mask原理)
    2.xgb原理->相比GBDT有哪些改进?如何判断每个结点是否要分裂?
    3.Xgb和lgb有哪些不同点?
    4.SVM为什么要求解它的对偶问题?
    5.Fasttext的原理->和word2vec有哪些不同?为什么要使用n-gram? Word2vec有哪些作用?
    6.Note2vec,Deepwalk知道吗?
    7.有哪些评判特征重要度的方法?特征缺失的处理方法?如何处理样本不平衡?决策树如何分裂的?
    8.FM原理?DeepFM如何做的?
    9.有哪些评价指标?AUC的意义?(物理上的)
    展开全文

空空如也

空空如也

1
收藏数 4
精华内容 1
关键字:

deepwalknode2vec