精华内容
下载资源
问答
  • 2022-01-25 09:13:45

    Node2Vec

    论文名称:node2vec: Scalable Feature Learning for Networks

    论文地址:https://www.kdd.org/kdd2016/papers/files/rfp0218-groverA.pdf

    Node2Vec是用于学习网络节点的连续特征表示。node2vec将节点映射为低维特征表示,最大化网络邻居节点的似然表示。定义一组弹性的邻居节点的概念,设计有偏的随机游走策略,学习探索各种各样的邻居表示。

    1.FEATURE LEARNING FRAMEWORK

    G = ( V , E ) G=(V,E) G=(V,E)表示网络, 我们分析方法适用于有向(无向),有权(无权)的网络模型。 f : V → R d f:V\rightarrow \mathbb{R}^d f:VRd将节点映射为 特征表示,用于下游的预测任务。 d d d表示特征表示的维度。 f f f是大小为 ∣ V ∣ × d |V|\times d V×d的参数矩阵。对于每个source node u ∈ V u \in V uV, 我们定义 N S ( u ) ⊂ V N_{S}(u) \subset V NS(u)V 为通过采样策略 S S S获得 u u u节点的邻居节点。

    我们采用扩展的Skip-gram结构。给定节点 u u u的特征表示,最大化邻居节点的log-probability。 f f f表示如下:
    max ⁡ f ∑ u ∈ V log ⁡ Pr ⁡ ( N S ( u ) ∣ f ( u ) ) (1) \max _{f} \sum_{u \in V} \log \operatorname{Pr}\left(N_{S}(u) \mid f(u)\right)\tag{1} fmaxuVlogPr(NS(u)f(u))(1)
    为了使得优化过程易于处理,我们作出两个假设:

    • 条件独立假设. 在给定source node的节点,他们的邻居节点是是独立的。
      Pr ⁡ ( N S ( u ) ∣ f ( u ) ) = ∏ n i ∈ N S ( u ) Pr ⁡ ( n i ∣ f ( u ) ) \operatorname{Pr}\left(N_{S}(u) \mid f(u)\right)=\prod_{n_{i} \in N_{S}(u)} \operatorname{Pr}\left(n_{i} \mid f(u)\right) Pr(NS(u)f(u))=niNS(u)Pr(nif(u))

    • Symmertry in feature space。 source node和neighborhood在feature space之间的影响是对称。

    对source-neighborhood node pair的特征进行softmax dot product操作:
    Pr ⁡ ( n i ∣ f ( u ) ) = exp ⁡ ( f ( n i ) ⋅ f ( u ) ) ∑ v ∈ V exp ⁡ ( f ( v ) ⋅ f ( u ) ) \operatorname{Pr}\left(n_{i} \mid f(u)\right)=\frac{\exp \left(f\left(n_{i}\right) \cdot f(u)\right)}{\sum_{v \in V} \exp (f(v) \cdot f(u))} Pr(nif(u))=vVexp(f(v)f(u))exp(f(ni)f(u))
    根据以上假设Eq.1 简化为:
    max ⁡ f ∑ u ∈ V [ − log ⁡ Z u + ∑ n i ∈ N S ( u ) f ( n i ) ⋅ f ( u ) ] (2) \max _{f} \sum_{u \in V}\left[-\log Z_{u}+\sum_{n_{i} \in N_{S}(u)} f\left(n_{i}\right) \cdot f(u)\right]\tag{2} fmaxuVlogZu+niNS(u)f(ni)f(u)(2)
    对于每个节点的partition function, Z u = ∑ v ∈ V exp ⁡ ( f ( u ) ⋅ f ( v ) ) Z_{u}=\sum_{v \in V} \exp (f(u) \cdot f(v)) Zu=vVexp(f(u)f(v))对于大型网络的计算代价是非常大的,因此,我们采用负采样。采用随机梯度法优化Eq.2中的模型参数。

    在文本中,基于连续的文字序列,通过window size定义它们的邻居。在网络中,采用随机策略生成source节点的不同的邻居,他们的邻居节点依赖于抽样策略 S S S

    2.node2vec

    基于BFS和DFS, 我们设计两者之间平滑的抽样策略。

    2.1 Random Walks

    设随机游走的长度 l l l, c i c_i ci是游走的第 i i i个节点, 起始节点 c 0 = u c_0=u c0=u。节点 c i c_i ci通过以下方式产生:
    P ( c i = x ∣ c i − 1 = v ) = { π v x Z  if  ( v , x ) ∈ E 0  otherwise  P\left(c_{i}=x \mid c_{i-1}=v\right)=\left\{\begin{array}{ll} \frac{\pi_{v x}}{Z} & \text { if }(v, x) \in E \\ 0 & \text { otherwise } \end{array}\right. P(ci=xci1=v)={Zπvx0 if (v,x)E otherwise 
    π v x \pi_{vx} πvx是 节点v和节点x之间非标准化的转移概率, Z Z Z是用于标准化的常数。

    2.2 Search bias α \alpha α

    最简单直接的随机游走方式是基于边的权重 w v x w_{vx} wvx进行下一个节点的抽样。例如: π v x = w v x \pi_{vx}=w_{vx} πvx=wvx。(对于无权图 w v x = 1 w_{vx}=1 wvx=1)。但是,这种情况没有考虑到网络的结构,不能进行不同形式邻居节点的探查。BFS和DFS分别适合结构等价和同质的网络的极端采样范式。现实多是两种情况的融合,我们的随机游走对两者作出平衡。

    在这里插入图片描述

    根据 p p p q q q我们定义 2 n d 2^{nd} 2nd阶的随机游走, p p p q q q引导游走的方式:假设刚游走过一条边 ( t , v ) (t,v) (t,v), 现在处于节点 v v v,(Figure 2)。现在基于边 ( v , x ) (v,x) (v,x), 决定下一步游走的转移概率 π v x \pi_{vx} πvx。我们设未标准化的转移概率 π v x = α p q ( t , x ) ⋅ w v x \pi_{vx}=\alpha_{pq}(t,x)\cdot w_{vx} πvx=αpq(t,x)wvx,其中:
    α p q ( t , x ) = { 1 p  if  d t x = 0 1  if  d t x = 1 1 q  if  d t x = 2 \alpha_{p q}(t, x)=\left\{\begin{array}{ll} \frac{1}{p} & \text { if } d_{t x}=0 \\ 1 & \text { if } d_{t x}=1 \\ \frac{1}{q} & \text { if } d_{t x}=2 \end{array}\right. αpq(t,x)=p11q1 if dtx=0 if dtx=1 if dtx=2
    d t x d_{tx} dtx是节点 t t t和节点 x x x之间的最短路径。 d t x d_{tx} dtx是集合 { 0 , 1 , 2 } \{0,1,2\} {0,1,2}中的一个。两个参数对于引导游走的方式是非常必要的。

    直观上,参数 p p p和参数 q q q是用来控制离开起始节点 u u u邻域的速度。特别的,这些参数允许我们的搜索过程在BFS和DFS之间进行插值,从而反映对不同节点的亲和力。

    Return parameter p p p

    参数 p p p控制在游走的过程中,折返( revisiting)访问节点可能性。如果将其设置一个较高的值 ( > max ⁡ ( q , 1 ) ) (\gt \max(q,1)) (>max(q,1)),采样到已经访问过节点的概率是非常小的(除非下一个节点没有邻居节点)。这个策略鼓励新的探索,避免重复过去无效2-hop。另一方面,如果 p p p比较小 ( < min ⁡ ( q , 1 ) ) (\lt\min(q,1)) (<min(q,1)),它将会导致游走的回溯(Figure 2), 将会导致在节点 u u u附近进行local walk。

    In-out parameter q q q

    参数 q q q控制“inward”和“outward”的参数。如Figure 2,如果 q > 1 q\gt1 q>1, 随机游走偏向节点 t t t。这个游走获得起始节点的局部视图,类似BFS,获取都是局部样本点。

    如果 q < 1 q<1 q<1, 游走会远离节点 t t t, 进行更深层次访问。这种行为类似DFS探索。与DFS不同的是,我们基于随机游走的框架实现类似DFS探索。给定样本点 u u u, 抽样的样本不是严格遵循DFS的distance 递增过程,但是采样的效率是非常高的且易于处理。设 π v , x \pi_{v,x} πv,x是在 t t t时刻, 当前进行节点的函数,它们的随机游走符合马尔科夫性。

    Benefits of random walks

    在这里插入图片描述

    在时间和空间复杂度方面,相对于 BFS和DFS, 随机游走的计算非常高效的。在空间复杂度方面, 存储节点邻居 O ∣ E ∣ O|E| OE. 在 2 n d 2^{nd} 2nd随机游走过程中,存储邻居间的交互,它们的空间复杂度是 O ( a 2 ∣ V ∣ ) O(a^2|V|) O(a2V), 其中 a a a是图平均度。在时间复杂度方面,通过在样本生成过程施加图连接,随机游走一种方便的机制,通过跨不同源节点重用样本来提高采样的效率。假设模拟 l > k l>k l>k随机游走, 由于马尔可夫性, 我们可以为 l − k l-k lk个节点一次产生 k k k个样本。因此,每个样本的复杂度为 O ( l k ( l − k ) ) O(\frac{l}{k(l-k)}) O(k(lk)l)。举例来说,我们随机游走 l = 6 l=6 l=6, 序列为 { u , s 4 , s 5 , s 6 , s 8 , s 9 } \{u, s_4, s_5, s_6, s_8, s_9\} {u,s4,s5,s6,s8,s9}, 会产生如下: N S ( u ) = { s 4 , s 5 , s 6 } N_{S}(u)=\left\{s_{4}, s_{5}, s_{6}\right\} NS(u)={s4,s5,s6} N S ( s 4 ) = { s 5 , s 6 , s 8 } N_{S}\left(s_{4}\right)=\left\{s_{5}, s_{6}, s_{8}\right\} NS(s4)={s5,s6,s8} N S ( s 5 ) = { s 6 , s 8 , s 9 } N_S(s_5)=\{s_6,s_8,s_9\} NS(s5)={s6,s8,s9}。需要注意的是:重用样本在整个过程中会引入偏差,但效率大大提高。

    2.3 The node2vec algorithm

    在这里插入图片描述

    Algorithm 1是node2vec的伪代码,由于起始节点 u u u的选择, 在随机游走过程中,会存在隐含的偏差。因为我们要学习所有节点的表示,我们将每个节点作为起始节点,随机游走固定的长度 l l l, 游走 r r r次。每一步的游走基于转移概率 π v x \pi_{vx} πvx。对于二阶马尔科夫转移概率 π v x \pi_{vx} πvx可以事先计算。因此,对于节点的采样可以在 O ( 1 ) O(1) O(1)时间内完成。node2vec可以分为3个阶段:转移概率预计算、随机游走序列生成、SGD优化,三个过程串联进行。每个阶段可以并行、异步执行,对全局进行优化。

    3 Learning edge features

    node2vec提供半监督的方式学习节点特征表示。然而,相对个体节点,我们通常对节点对的预测任务更加感兴趣。例如,在链路预测任务中,判断两个节点是否存在边。因为随机游走自然地学习到网络节点之间的连接性。我们基于个体节点的特征表示,使用bootstrapping的方法,可以学习节点对之间的关系。

    考虑两个节点 u u u v v v, 我们基于特征向量 f ( u ) f(u) f(u) f ( v ) f(v) f(v)定义二值算子 ∘ \circ ,用于计算表征向量 g ( u , v ) g(u,v) g(u,v), g : V × V → R d ′ g: V \times V \rightarrow \mathbb{R}^{d^{\prime}} g:V×VRd, 其中, d ′ d^{\prime} d是节点对 ( u , v ) (u,v) (u,v)表征大小。我们想让我们的算子对任何算子定义有效,即使节点之间的边不存在。这样做是方便链路预测。我们的测试数据包含真假边。我们考虑几种算子 ∘ \circ , 使得 d ′ = d d^{\prime}=d d=d, 总结在Table 1中。

    在这里插入图片描述

    更多相关内容
  • node2vec 使用数据集cora的node2vec的示例
  • Node2Vec JAVA实现 参考 在图的遍历时,通过p和q两个参数,平衡深度优先(DFS)和广度优先(BFS)。 git: 存储图的结构czzGraph 1.1 图的存储,图的节点,图的边 1.2 图的输入(邻接表,邻接矩阵) 1.3 图的可视化...
  • node2vec论文里面的代码,
  • 嵌入表示学习是当下研究热点,从word2vec,到node2vec, 到graph2vec,出现大量X2vec的算法。但如何构建向量嵌入理论指导算法设计?最近RWTH Aachen大学的计算机科学教授ACM Fellow Martin Grohe教授给了《X2vec: ...
  • 斯坦福大学的node2vec模型,做图嵌入的,说明很详细分享一下,,原文件是Python2做的,我改的Python3的,分享一下
  • matlab中代码英文node2vec-c 无依赖C ++中的实现。 node2vec使用短偏差随机游动来学习未加权图中顶点的表示。 可在中找到其他实现,并在中找到参考实现。 该代码被开发用于纸面文件,以进行公平的性能比较。 此外,...
  • node2vec源码

    2019-02-06 19:01:03
    复杂网络的特征提取 将节点输入 获取特征向量 能更好的保存拓扑结构
  • node2vec随机游走的多线程实现。 介绍 该存储库提供了node2vec随机遍历的多线程实现,并具有基于LRU缓存的别名表,它可以在有限的内存使用情况下进行处理,因此可以在单台计算机上遍历大型图。 测试了包含参数的...
  • node2vec-master-python3_node2vec_blanketk2r_源码.rar
  • 普通数据字段的特征提取大家做得很多,但为了扩大推荐算法的准确性,引入关系网络的特征提取是业界研究新动向,广泛应用于广告、SNS等领域。
  • node2vec

    2021-05-11 14:05:46
    node2vec: Scalable Feature Learning for Networks》 《node2vec:大规模网络节点的表征学习》

    1. 学习任务

        《node2vec: Scalable Feature Learning for Networks》

    《node2vec:大规模网络节点的表征学习》Adiya Grover,Jure Leskovec 等; 单位:Stanford;  KDD 2016

    1.1 论文结构

    在这里插入图片描述

    1.2 研究背景

      图是一种描述复杂数据的模型(任意的节点数量、复杂的关系) vs 图片(CNN)、文本结构(word2vec)
    在这里插入图片描述
    snap数据集 - 链接 是Jure等人不间断收集的网络数据集,极大地 推动社交网络领域的发展

      研究涵盖:节点分类(node classification)、边预测(link prediction)、社群检测(community detection)、网络营销(viral marketing)、网络相似度(network similarity)

    2. node2vec 结构框架

    Network embedding 学习目标

    在这里插入图片描述

    • 给定图 G = (V, E),目标是去学习一个映射 f : u → R d f: u \rightarrow \mathbb{R}^{d} f:uRd

    论文核心:通过随机游走策略生成 N S ( u ) \mathcal{N}_{S}(u) NS(u)

    2.1 优化目标

    node2vec 的优化目标 类似Skip-gram,给定顶点 u u u,在低维空间中最大化其邻居 N S ( u ) \mathcal{N}_{S}(u) NS(u) 的对数似然函数
    max ⁡ f ∑ u ∈ V log ⁡ Pr ⁡ ( N S ( u ) ∣ f ( u ) ) \max _{f} \sum_{u \in V} \log \operatorname{Pr}\left(\mathcal{N}_{S}(u) \mid f(u)\right) fmaxuVlogPr(NS(u)f(u))

      假设邻居节点 N S ( u ) \mathcal{N}_{S}(u) NS(u) 之间互不影响
    Pr ⁡ ( N S ( u ) ∣ f ( u ) ) = ∑ n i ∈ N S ( u ) Pr ⁡ ( n i ∣ f ( u ) ) ⇒ \operatorname{Pr} (N_{S}(u) \mid f(u))=\sum_{n_{i} \in N_{S}(u)} \operatorname{Pr}\left(n_{i} \mid f(u)\right) \quad\Rightarrow \quad Pr(NS(u)f(u))=niNS(u)Pr(nif(u))
    log ⁡ Pr ⁡ ( N S ( u ) ∣ f ( u ) ) = ∑ n i ∈ N S ( u ) log ⁡ Pr ⁡ ( f ( n i ) ∣ f ( u ) ) \log \operatorname{Pr} (N_{S}(u) \mid f(u))=\sum_{n_{i} \in N_{S}(u)} \log \operatorname{Pr}\left(f\left(n_{i}\right) \mid f(u)\right) logPr(NS(u)f(u))=niNS(u)logPr(f(ni)f(u))

      通过softmax函数来建模条件概率 σ ( z ) j = e z j ∑ k = 1 K e z k  for  j = 1 , … , K \sigma(\mathbf{z})_{j}=\frac{e^{z_{j}}}{\sum_{k=1}^{K} e^{z_{k}}} \quad \text { for } j=1, \ldots, K σ(z)j=k=1Kezkezj for j=1,,K
    Pr ⁡ ( f ( n i ) ∣ f ( u ) ) = exp ⁡ ( f ( n i ) ⋅ f ( u ) ) ∑ v ∈ V exp ⁡ ( f ( v ) ⋅ f ( u ) ) \operatorname{Pr}\left(f\left(n_{i}\right) \mid f(u)\right)=\frac{\exp \left(f\left(n_{i}\right) \cdot f(u)\right)}{\left.\sum_{v \in V} \exp (f(v) \cdot f(u)\right)} Pr(f(ni)f(u))=vVexp(f(v)f(u))exp(f(ni)f(u))

      最后node2vec优化函数为:
    max ⁡ f ∑ u ∈ V [ − log ⁡ Z u + ∑ n i ∈ N S ( u ) f ( n i ) ⋅ f ( u ) ] \max _{f} \sum_{u \in V}\left[-\log Z_{u}+\sum_{n_{i} \in N_{S}(u)} f\left(n_{i}\right) \cdot f(u)\right] fmaxuVlogZu+niNS(u)f(ni)f(u)

      优化函数中的常数对结果无影响,可省略。其中 Z u = ∑ v ∈ V exp ⁡ ( f ( u ) ⋅ f ( v ) ) Z_{u}=\sum_{v \in V} \exp (f(u) \cdot f(v)) Zu=vVexp(f(u)f(v))

    2.2 一阶相似性与二阶相似性

      文章中使用BFSDFS两种策略采样得到的邻居 N S ( u ) \mathcal{N}_{S}(u) NS(u)

    在这里插入图片描述
    一阶相似性与二阶相似性描述-参考链接

    一阶相似性:在Node2Vec中也叫做 同质性(homophily)。一阶相似性捕捉的是图中实际存在的结构,比如两个节点由一条边相连,则这两个节点应该具有相似的表示。按照Node2Vec中的说法,高度互连且属于相似网络集群或社区的节点表示应该比较相近。一阶相似性往往可以通过对节点的DFS遍历得到。

    二阶相似性:在Node2Vec中也叫做 结构对等性(structural equivalence)。在网络中具有相似结构的节点表示应该相近,它并不强调两个节点是否在图中存在连接,即使两个节点离得很远,但由于结构上相似(连接的邻居节点相似),它们的表示也应该相似,所以二阶相似性可以发现不同的社区。二阶相似性可以通过对节点的BFS遍历得到。

    2.3 Random Walk

      传统的random walk不具备探索节点不同类型领域的能力,本文中认为网络同时具备 结构相似性[通过BFS]同质/社群相似性[通过DFS]

      传统的random walk:给定源点 u u u,采样一个长度为 l l l 的随机游走序列,序列起始顶点为 c 0 = u c_0=u c0=u c i c_i ci 的采样策略为:
    P ( c i = x ∣ c i − 1 = v ) { π v , x Z ,  if  ( v , x ) ∈ E 0 ,  else  P\left(c_{i}=x \mid c_{i-1}=v\right)\left\{\begin{array}{ll} \frac{\pi_{v, x}}{Z}, & \text { if }(v, x) \in E \\ 0, & \text { else } \end{array}\right. P(ci=xci1=v){Zπv,x,0, if (v,x)E else 

    其中 π v , x \pi_{v, x} πv,x为非归一化的、从顶点 v v v 转移到顶点 x x x 的概率, Z Z Z 为归一化常数。

    2.4 Biased Random Walk - 2nd order

    在这里插入图片描述

    • d t x d_{tx} dtx t t t x x x之间的最短路径, p p p q q q 控制了从源点V离开其邻居的快慢。

      图中T时刻处于V点,由T-1时刻从t位置转移过来。此时看上一时刻(T-1)处的t点到其他四个点( t , X 1 , X 2 , X 3 t, X_1,X_2,X_3 t,X1,X2,X3)的距离,分别为 0,1,2,2;对应的概率分别为 1 p , 1 , 1 q , 1 q \frac{1}{p},1,\frac{1}{q},\frac{1}{q} p1,1,q1,q1

    超参数的理解

    p值大:对应的 α \alpha α小,倾向不回溯,降低了2-hop的冗余度;p值小:倾向回溯,采样序列集中在起始点的周围。
    q > 1:则 α = 1 q < 1 \alpha=\frac{1}{q} < 1 α=q1<1,转移到 X 1 X_1 X1概率大,BFS占主导;q < 1DFS占主导。

    2.5 alias sampling

    Darts, Dice, and Coins: Sampling from a Discrete Distribution-The Alias Method - 链接
    在这里插入图片描述
    具体理解可查看 Alias method:时间复杂度O(1)的离散采样方法 - 链接



    附录

    1. 图结构中 BFS、DFS

      定义一个无向图,如下图所示。参考链接 -CSDN-黄蜜桃-Python图的BFS与DFS

    # 定义图结构
    graph = {
        "A": ["B","C"],
        "B": ["A", "C", "D"],
        "C": ["A", "B", "D","E"],
        "D": ["B", "C", "E","F"],
        "E": ["C", "D"],
        "F": ["D"],
    }
    

    1.1 图的广度优先遍历 BFS

    # BFS: 使用queue队列, FIFO 先进先出
    def BFS(Graph, vertex):
        queue = []
        queue.append(vertex)  # 首节点添加
    
        seen = set()      # 集合中存储已访问过的节点
        seen.add(vertex)
    
        res = list()
    
        while queue:
            temp = queue.pop(0)   # 队首元素出队
            res.append(temp)
    
            adjnodes = Graph[temp]   # 获取邻接点; 不同的存储结构,得到邻接点的方式不一样
    
            for node in adjnodes:
                if node not in seen:
                    queue.append(node)
                    seen.add(node)
        return res
    

    1.2 图的深度优先遍历 DFS

    # DFS: 使用 stack 栈
    def DFS(Graph, vertex):
        stack = []
        stack.append(vertex)  # 添加首节点
    
        seen = set()
        seen.add(vertex)
    
        res = list()
        while stack:
            temp = stack.pop()  # 栈顶元素
            res.append(temp)
    
            adjnodes = Graph[temp]  # 获取邻接点;
    
            for node in adjnodes:
                if node not in seen:
                    stack.append(node)
                    seen.add(node)
        return res
    

    参考链接- 深度之眼- 图神经网络精讲班
    参考链接- 深度之眼Paper带读笔记GNN.01.Node2Vec

    展开全文
  • PecanPy:Python中并行,高效且加速的node2vec 学习大型图中节点的低维表示(嵌入)是在大型生物网络上应用机器学习的关键。 Node2vec是使用最广泛的节点嵌入方法。 PecanPy是一种快速,并行,高效存储和缓存优化...
  • 论文名称:node2vec: Scalable Feature Learning for Networks 论文下载:https://arxiv.org/abs/1607.00653# 论文年份:SIGKDD 2016 论文被引:7065(2022/04/26) 数据集+实现:http://snap.stanford.edu/node2vec...

    论文名称:node2vec: Scalable Feature Learning for Networks

    论文下载:https://arxiv.org/abs/1607.00653#

    论文年份:SIGKDD 2016

    论文被引:7065(2022/04/26)

    数据集+实现:http://snap.stanford.edu/node2vec

    论文总结

    什么是 node2vec?

    node2vec,一种用于网络中可扩展特征学习的半监督算法框架。其可以用于学习网络中结点的连续特征表示。其学习结点到特征的低维空间映射,最大限度地保留节点的网络邻域的似然。定义了节点的网络邻域的概念,并设计了有偏随机游走用于探索不同的邻域

    ABSTRACT

    网络中节点和边缘的预测任务需要在学习算法所使用的工程特征上做出认真的努力。最近在更广泛的表示学习领域的研究通过学习特征本身在自动预测方面取得了重大进展。然而,目前的特征学习方法的表现力不足以捕捉网络中观察到的连接模式的多样性

    在这里,我们提出了 node2vec,这是一种用于学习网络中节点的连续特征表示的算法框架。在 node2vec 中,我们学习节点到特征的低维空间的映射,最大限度地保留节点的网络邻域的似然。我们定义了一个节点的网络邻域的灵活概念,并设计了一个有偏随机游走程序,它有效地探索了不同的邻域。我们的算法概括了基于严格的网络邻域概念的先前工作,我们认为在探索邻域时增加的灵活性是学习更丰富表示的关键

    我们展示了 node2vec 在来自不同领域的几个真实世界网络中对多标签分类和链接预测的现有最先进技术的功效。总之,我们的工作代表了一种在复杂网络中有效学习最先进的任务无关表示的新方法。

    1. INTRODUCTION

    网络分析中的许多重要任务都涉及对节点和边的预测。在典型的节点分类任务中,我们感兴趣的是预测网络中最可能的节点标签 [33]。例如,在社交网络中,我们可能对预测用户的兴趣感兴趣,或者在蛋白质-蛋白质相互作用网络中,我们可能对预测蛋白质的功能标签感兴趣 [25, 37]。类似地,在链路预测中,我们希望预测网络中的一对节点是否应该有一条边连接它们[18]。链接预测在各种领域都很有用;例如,在基因组学中,它可以帮助我们发现基因之间的新相互作用,在社交网络中,它可以识别现实世界的朋友 [2, 34]。

    任何有监督的机器学习算法都需要一组信息丰富的、有辨别力的和独立的特征。在网络上的预测问题中,这意味着必须为节点和边构建特征向量表示。一个典型的解决方案是基于专家知识手工设计特定领域的特征。即使人们不考虑特征工程所需的繁琐工作,这些特征通常也是为特定任务设计的,并且不能泛化到不同的预测任务中

    另一种方法是通过解决优化问题来学习特征表示 [4]。特征学习的挑战在于定义一个目标函数,这涉及平衡计算效率和预测准确性的权衡。在频谱的一方面,人们可以直接针对找到优化下游预测任务性能的特征表示。虽然这种有监督的过程具有良好的准确性,但由于需要估计的参数数量激增,它的代价是训练时间复杂度高。在另一个极端,可以将目标函数定义为独立于下游预测任务,并且可以以纯无监督的方式学习表示。这使得优化在计算上变得高效,并且具有精心设计的目标,它导致与任务无关的特征在预测准确性方面与特定于任务的方法密切匹配 [21, 23]。

    然而,当前的技术未能令人满意地定义和优化网络中可扩展的无监督特征学习所需的合理目标。基于线性和非线性降维技术的经典方法,如主成分分析、多维缩放及其扩展 [3、27、30、35] 优化目标,该目标转换网络的代表性数据矩阵,使其最大化数据表示的方差。因此,这些方法总是涉及适当数据矩阵的特征分解,这对于大型现实世界网络来说是昂贵的。此外,由此产生的潜在表示在网络上的各种预测任务上表现不佳。

    或者,我们可以设计一个旨在保护节点的局部邻域的目标。可以使用类似于仅在单个隐藏层前馈神经网络上的反向传播的随机梯度下降 (SGD) 来有效地优化目标。最近在这个方向上的尝试 [24, 28] 提出了有效的算法,但是依赖于网络邻域的严格概念,这导致这些方法很大程度上对网络特有的连接模式不敏感。具体来说,网络中的节点可以根据它们所属的社区(即同质性,homophily)进行组织;在其他情况下,组织可以基于网络中节点的结构角色(即结构等效性,structural equivalence)[7,10,36]。例如,在图 1 中,我们观察到节点 u 和 s1 属于同一个紧密联系的节点社区,而两个不同社区中的节点 u 和 s6 共享中心节点的相同结构角色。现实世界的网络通常表现出这种等价的混合。因此,必须允许一种灵活的算法来学习节点表示,同时遵守以下两个原则:学习将来自同一网络社区的节点紧密嵌入在一起的表示的能力,以及学习具有相似角色的节点具有相似嵌入的表示的能力。这将允许特征学习算法在广泛的领域和预测任务中进行泛化
    在这里插入图片描述
    现在的工作。我们提出了 node2vec,一种用于网络中可扩展特征学习的半监督算法。我们使用 SGD 优化了一个定制的基于图的目标函数,这是由自然语言处理的先前工作所激发的 [21]。直观地说,我们的方法返回的特征表示可以最大限度地保留 d 维特征空间中节点的网络邻域的似然。我们使用二阶随机游走方法为节点生成(样本)网络邻域

    我们的主要贡献是定义了一个灵活的节点网络邻居的概念。通过选择适当的邻域概念,node2vec可以学习基于节点的网络角色和/或它们所属的社区来组织节点的表示。我们通过开发有偏随机游(biased random walks)走来实现,这种有偏随机游走有效地探索给定节点的不同邻域。与先前工作[24,28]中的严格搜索过程相比,所得到的算法是灵活的,通过可调参数给予我们对搜索空间的控制。因此,我们的方法概括了以前的工作,可以模拟网络中观察到的等价的全部频谱。控制搜索策略的参数有一个直观的解释,并且偏向于不同的网络探索策略。这些参数也可以使用一小部分标记数据以半监督的方式直接学习

    我们还展示了如何将单个节点的特征表示扩展到节点对(即边)。为了生成边的特征表示,我们使用简单的二元算子组合各个节点的学习特征表示。这种组合性使 node2vec 可以用于涉及节点和边的预测任务。

    我们的实验集中在网络中两个常见的预测任务:一个多标签分类任务,其中每个节点都被分配一个或多个类标签和一个链接预测任务,我们在给定一对节点的情况下预测一条边的存在。我们将 node2vec 的性能与最先进的特征学习算法 [24, 28] 进行对比。我们对来自不同领域的几个真实世界网络进行实验,例如社交网络、信息网络以及系统生物学的网络。实验表明,node2vec 在多标签分类方面的性能优于最先进的方法高达 26.7%,在链接预测方面的性能高达 12.6%。该算法即使在 10% 的标记数据上也显示出具有竞争力的性能,并且对噪声或边缘缺失形式的扰动也具有鲁棒性。在计算上,node2vec 的主要阶段可以简单地并行化,它可以在几个小时内扩展到具有数百万个节点的大型网络。

    总的来说,我们的论文做出了以下贡献:

    1. 我们提出了 node2vec,这是一种用于网络中特征学习的高效可扩展算法,它使用 SGD 有效地优化了一种新颖的网络感知、邻域保留目标。
    2. 我们展示了 node2vec 如何符合网络科学中的既定原则,为发现符合不同等价的表示提供了灵活性。
    3. 我们扩展了 node2vec 和其他基于邻域保留目标的特征学习方法,从节点到节点对,用于基于边缘的预测任务。
    4. 我们根据经验评估 node2vec 在多个真实数据集上的多标签分类和链接预测

    本文的其余部分的结构如下。在第 2 节中,我们简要调查了网络特征学习的相关工作。我们在第 3 节中介绍了使用 node2vec 进行特征学习的技术细节。在第 4 节中,我们经验性地评估 node2vec 在各种现实世界网络上的节点和边缘上的预测任务,并评估我们算法的参数敏感性、扰动分析和可扩展性。我们以对 node2vec 框架的讨论结束,并在第 5 节中强调未来工作的一些有希望的方向。node2vec 的数据集和参考实现可在项目页面上找到:http://snap.stanford.edu/node2vec。

    2. RELATED WORK

    机器学习社区已经在各种标题下对特征工程进行了广泛的研究。在网络中,为节点生成特征的传统范例基于特征提取技术,该技术通常涉及一些基于网络属性的种子手工制作特征 [8, 11]。相比之下,我们的目标是通过将特征提取作为表示学习问题来自动化整个过程,在这种情况下,我们不需要任何手工设计的特征

    无监督特征学习方法通常利用图的各种矩阵表示的谱属性,尤其是拉普拉斯矩阵和邻接矩阵。在这种线性代数的观点下,这些方法可以被视为降维技术。已经提出了几种线性(例如,PCA)和非线性降维技术(例如,IsoMap)[3,27,30,35]。这些方法存在计算和统计性能缺陷。在计算效率方面,数据矩阵的特征分解是昂贵的,除非解决方案的质量受到近似值的严重影响,因此这些方法很难扩展到大型网络。其次,这些方法对网络中观察到的不同模式(例如同质性和结构等价)的目标进行优化时不够鲁棒,并对底层网络结构和预测任务之间的关系做出假设。例如,谱聚类做出了一个强烈的同质性假设,即图切分(graph cuts)对分类很有用[29]。这样的假设在许多情况下是合理的,但在跨不同网络的有效泛化方面效果不佳

    自然语言处理的表征学习的最新进展为离散对象(例如单词)的特征学习开辟了新途径。特别是,Skip-gram 模型 [21] 旨在通过优化邻域保留似然目标来学习单词的连续特征表示。该算法如下进行:它扫描文档的单词,并针对每个单词嵌入该单词,以便单词的特征可以预测附近的单词(即,某个上下文窗口内的单词)。通过使用带有负采样的 SGD [22] 优化似然目标来学习单词特征表示。 Skip-gram 目标基于分布假设,该假设指出相似上下文中的单词往往具有相似的含义 [9]。也就是说,相似的词往往会出现在相似的词邻域中

    受 Skip-gram 模型的启发,最近的研究通过将网络表示为“文档”[24、28],建立了网络的类比。就像文档是有序的单词序列一样,可以从底层网络中采样节点序列,并将网络转换为有序的节点序列。然而,节点有许多可能的采样策略,导致学习到的特征表示不同。事实上,正如我们将要展示的,没有明确的抽样策略适用于所有网络和所有预测任务。这是先前工作的一个主要缺点,这些工作未能提供从网络中采样节点的任何灵活性 [24, 28]我们的算法 node2vec 通过设计一个灵活的目标来克服这个限制,该目标不依赖于特定的采样策略,并提供参数来调整探索的搜索空间(参见第 3 节)font>。

    最后,对于基于节点和边缘的预测任务,最近有大量基于现有和新颖的特定于图的深度网络架构的监督特征学习工作 [15、16、17、31、39]。这些架构使用几层非线性变换直接最小化下游预测任务的损失函数,从而实现高精度,但由于高训练时间要求而以可伸缩性为代价

    3. FEATURE LEARNING FRAMEWORK

    我们将网络中的特征学习表述为最大似然优化问题。让 G = ( V , E ) G = (V, E) G=(V,E) 是一个给定的网络。我们的分析是通用的,适用于任何 (非) 定向、 (非) 加权网络。 f : V → R d f : V → \R^d f:VRd 是从节点到特征表示的映射函数,旨在学习下游预测任务。这里 d d d 是一个参数,指定特征表示的维数。等效地, f f f 是大小为 ∣ V ∣ × d |V|× d V×d 的参数矩阵。对于每个源节点 u ∈ V u ∈ V uV,将 N S ( u ) ⊂ V N_S(u) ⊂ V NS(u)V 定义为节点 u u u 通过邻域采样策略 S S S 生成的网络邻域
    在这里插入图片描述
    为了使优化问题易于处理,我们做了两个标准假设:

    • 条件独立。给定源的特征表示,我们通过假设观察邻域节点的可能性独立于观察任何其他邻域节点来分解可能性:
      在这里插入图片描述

    • 特征空间的对称性。源节点和邻域节点在特征空间中具有相互对称的影响。因此,我们将每个源-邻域节点对的条件似然建模为一个 softmax 单元,通过它们的特征的点积参数化:
      在这里插入图片描述

    有了上述假设,方程 1 中的目标简化为:
    在这里插入图片描述
    对于大型网络来说,每个节点的分区函数 Z u = ∑ v ∈ V e x p ( f ( u ) ⋅ f ( v ) ) Z_u = \sum _{v∈V} exp(f(u) · f(v)) Zu=vVexp(f(u)f(v)) 计算成本很高,我们使用负采样 [22] 对其进行近似。我们在定义特征 f f f 的模型参数上使用随机梯度上升优化方程 2。

    基于Skip-gram架构的特征学习方法最初是在自然语言环境中开发的[21]。给定文本的线性性质,邻域的概念可以自然地使用连续单词上的滑动窗口来定义。然而,网络不是线性的,因此需要更丰富的邻域概念。为了解决这个问题,我们提出了一个随机过程,该过程对给定源节点u的许多不同的邻域进行采样。邻域NS(u)不仅限于直接邻居,而是可以根据采样策略s具有非常不同的结构

    基于 Skip-gram 架构的特征学习方法最初是在自然语言的背景下开发的 [21]。鉴于文本的线性性质,邻域的概念可以使用连续单词上的滑动窗口自然地定义。然而,网络不是线性的,因此需要更丰富的邻域概念。为了解决这个问题,我们提出了一个随机过程,它对给定源节点 u u u 的许多不同邻域进行采样。邻域 N S ( u ) N_S(u) NS(u) 不仅限于直接邻域,还可以根据采样策略 S S S 具有截然不同的结构。

    3.1 Classic search strategies

    我们将源节点的邻域采样问题视为局部搜索的一种形式。如图 1 所示,其中给定一个源节点 u,我们旨在生成(采样)其邻域 N S ( u ) N_S(u) NS(u)。重要的是,为了能够公平地比较不同的采样策略 S S S,我们将邻域集 N S N_S NS 的大小限制为 k k k 个节点,然后为单个节点 u u u 采样多个集合。通常,有两种极端的采样策略来生成 k k k 个节点的邻域集 N S N_S NS

    • 广度优先采样 (Breadth-first Sampling,BFS):邻域 N S N_S NS 仅限于与源直接相邻的节点。例如,在图 1 中,对于大小为 k = 3 的邻域,BFS 对节点 s1、s2、s3 进行采样。
    • 深度优先采样 (Depth-first Sampling,DFS):邻域由在距源节点越来越远的距离处按顺序采样的节点组成。在图 1 中,DFS 采样 s4、s5、s6。

    广度优先和深度优先采样代表了他们探索的搜索空间的极端场景,从而对学习的表示产生了有趣的影响。

    特别是,网络中节点上的预测任务经常在两种相似性之间穿梭:同质性结构等价性[12]。

    • 在同质性假设 [7, 36] 下,高度互连且属于相似网络簇或社区的节点应该紧密嵌入在一起(例如,图 1 中的节点 s 1 s_1 s1 u u u 属于同一个网络社区)。
    • 相比之下,根据结构等效假设 [10],在网络中具有相似结构的节点应紧密嵌入在一起(例如,图 1 中的节点 s 6 s_6 s6 u u u 充当其相应社区的中心)。重要的是,与同质性不同,结构等价并不强调连通性节点在网络中可能相距很远,但仍具有相同的结构

    在现实世界中,这些等价概念并不是唯一的。网络通常表现出两种行为,其中一些节点表现出同质性,而另一些则反映结构等价

    我们观察到 BFS 和 DFS 策略在生成反映上述任何一个等价的表示方面起着关键作用。特别是,BFS 采样的邻域导致嵌入与结构等价密切对应。直观地,我们注意到,为了确定结构等效性,准确地描述局部邻域通常就足够了。例如,仅通过观察每个节点的直接邻域,就可以推断出基于网络角色(如网桥和集线器)的结构等效性。通过将搜索限制在附近的节点,BFS 实现了这种表征并获得了每个节点附近的微观视图。此外,在 BFS 中,采样邻域中的节点往往会重复多次。这也很重要,因为它减少了表征 1 跳节点(1-hop nodes)相对于源节点的分布的方差然而,对于任何给定的 k,BFS 只能探索图的一小部分

    DFS 则相反,它可以探索网络的更大部分,因为它可以远离源节点 u u u(样本大小 k k k 是固定的)。在 DFS 中,采样节点更准确地反映了邻域的宏观视图,这对于基于同质性推断社区至关重要然而,DFS 的问题在于,不仅要推断网络中存在哪些节点到节点的依赖关系,而且还要描述这些依赖关系的确切性质,这一点很重要。这很难,因为我们对样本量有限制,而且要探索的邻域很大,导致方差很大。其次,移动到更大的深度会导致复杂的依赖关系,因为采样节点可能远离源并且可能不太具有代表性

    3.2 node2vec

    基于上述观察,我们设计了一种灵活的邻域采样策略,使我们能够在 BFS 和 DFS 之间进行平滑插值。我们通过开发一种灵活的有偏随机游走程序来实现这一点,该程序可以以 BFS 和 DFS 方式探索邻域。

    3.2.1 Random Walks

    形式上,给定一个源节点 u,我们模拟一个固定长度 l 的随机游走。令 ci 表示遍历中的第 i 个节点,从 c0 = u 开始。节点 ci 由以下分布生成
    在这里插入图片描述
    其中 πvx 是节点 v 和 x 之间的非归一化转移概率,Z 是归一化常数。

    3.2.2 Search bias α

    使我们的随机游走产生偏差的最简单方法是根据静态边权重 wvx 对下一个节点进行采样,即 πvx = wvx(在未加权图 wvx = 1 的情况下)。但是,这不允许考虑网络结构并指导搜索过程来探索不同类型的网络邻域。此外,与分别适用于结构等价和同质性的极端采样范式 BFS 和 DFS 不同,我们的随机游走应该适应这样一个事实,即这些等价概念不是竞争或排他性的,并且现实世界的网络通常表现出两者的混合。
    在这里插入图片描述
    我们用两个参数 p 和 q 来定义一个二阶随机游走来引导游走:考虑一个随机游走,它刚刚遍历边 (t, v),现在位于节点 v(图 2)。游走现在需要决定下一步,因此它评估从 v 开始的边 (v, x) 上的转移概率 πvx。我们将非归一化转移概率设置为 πvx = αpq(t, x) · wvx,其中
    在这里插入图片描述
    dtx 表示节点 t 和 x 之间的最短路径距离。请注意,dtx 必须是 {0, 1, 2} 之一,因此,这两个参数对于引导游走是必要且充分的。

    直观地说,参数 p 和 q 控制游走探索和离开起始节点 u 邻域的速度。特别是,这些参数允许我们的搜索过程(近似)在 BFS 和 DFS 之间进行插值,从而反映对不同节点等价概念的亲和力。

    返回参数,p。参数 p 控制在行走中立即重新访问节点的可能性

    • 将 p 设置为较高的值 (> max(q, 1)) 可确保我们在接下来的两个步骤中不太可能对已经访问过的节点进行采样(除非遍历中的下一个节点没有其他邻居)。该策略鼓励适度探索并避免采样中的 2 跳冗余
    • 另一方面,如果 p 很低(< min(q, 1)),它将导致游走回溯一步(图 2),这将使游走“局部”靠近起始节点 u。

    进出参数,q。参数 q 允许搜索区分“向内”和“向外”节点。回到图 2,如果 q > 1,随机游走偏向靠近节点 t 的节点。这样的游走获得了相对于游走中的起始节点获得底层图的局部视图,并在由小区域内的节点组成的样本方面,近似 BFS 行为。

    相反,如果 q < 1,则游走更倾向于访问距离节点 t 较远的节点。这种行为反映了鼓励向外探索的 DFS。然而,这里的一个本质区别是在随机游走框架内实现了类似 DFS 的探索。因此,采样节点与给定源节点 u 的距离并没有严格增加,但反过来,受益于易于处理的预处理和随机游走的卓越采样效率。请注意,通过将 πv,x 设置为游走 t 中前一个节点的函数,随机游走是二阶马尔可夫

    随机游走的好处。与纯 BFS/DFS 方法相比,随机游走有几个好处。

    • 随机游走在空间和时间要求方面都具有计算效率。存储图中每个节点的直接邻居的空间复杂度为 O ( ∣ E ∣ ) O(|E|) O(E)。对于二阶随机游走,存储每个节点的邻居之间的互连是有帮助的,这会产生 O ( a 2 ∣ V ∣ ) O(a^2|V|) O(a2V) 的空间复杂度,其中 a 是图的平均度(degree),对于现实世界的网络通常很小。
    • 与经典的基于搜索的采样策略相比,随机游走的另一个关键优势是它的时间复杂度。特别是,通过在样本生成过程中施加图连通性,随机游走提供了一种方便的机制,通过跨不同源节点重用样本来提高有效采样率
    • 通过模拟长度为 l > k 的随机游走,由于随机游走的马尔可夫性质,我们可以一次为 l - k 个节点生成 k 个样本。因此,每个样本的有效复杂度是 O ( l k ( l − k ) ) O (\frac{l} {k(l−k)}) O(k(lk)l)例如,在图 1 中,对长度为 l = 6 的随机游走 {u, s4, s5, s6, s8, s9} 进行采样,结果 NS(u) = {s4, s5, s6},NS(s4) = {s5, s6, s8} 和 NS(s5) = {s6, s8, s9}请注意,样本重复使用可能会在整个过程中引入一些偏差。但是,我们观察到它大大提高了效率

    3.2.3 The node2vec algorithm

    在这里插入图片描述
    node2vec 的伪代码在算法 1 中给出。在任何随机游走中,起始节点 u 的选择存在隐式偏差。由于学习了所有节点的表示,通过模拟从每个节点开始的 r 个固定长度 l 的随机游走来抵消这种偏差。在游走的每一步,采样都是基于转移概率 πvx 进行的。可以预先计算二阶马尔可夫链的转移概率 πvx,因此,使用别名采样可以在 O(1) 时间内有效地在模拟随机游走时对节点进行采样。 node2vec 的三个阶段,即计算转移概率的预处理、随机游走模拟和使用 SGD 的优化,是按顺序执行的。每个阶段都是可并行化和异步执行的,有助于 node2vec 的整体可扩展性。

    3.3 Learning edge features

    node2vec 算法提供了一种半监督方法学习网络中节点的丰富特征表示。然而,我们经常对涉及节点对而不是单个节点的预测任务感兴趣。例如,在链接预测中,我们预测网络中两个节点之间是否存在链接。由于我们的随机游走自然基于底层网络中节点之间的连接结构,因此我们使用自举方法 (bootstrapping approach) 对单个节点的特征表示将它们扩展到节点对

    给定两个节点 u 和 v,在相应的特征向量 f(u) 和 f(v) 上定义一个二元算子 ◦ 以生成表示 g(u, v) 使得 g : V × V → R d ′ g : V × V → \R^{d'} g:V×VRd 其中 d’ 是对 (u, v) 的表示大小。我们希望为任何一对节点定义算子,即使这对节点之间不存在边,因为这样做使得表示对于链接预测有用,其中测试集包含真边和假边(即,不存在)。我们考虑了几种运算符 ◦ 的选择,如表 1 中总结的 d’ = d。
    在这里插入图片描述

    4. EXPERIMENTS

    Eq2 中的目标独立于任何下游任务,并且 node2vec 提供的探索灵活性将学习的特征表示提供给下面讨论的各种网络分析设置。

    4.1 Case Study: Les Misérables network

    在第 3.1 节中,我们观察到 BFS 和 DFS 策略代表了基于同质性(即网络社区)和结构等效性(即节点的结构角色)原则的嵌入节点频谱的极端。我们现在的目标是通过经验证明这一事实,并表明 node2vec 实际上可以发现符合这两个原则的嵌入。

    我们使用一个网络,其中节点对应于小说 Les Misérables [13] 中的角色边连接共同出现的角色。该网络有 77 个节点和 254 条边。我们设置 d = 16 并运行 node2vec 来学习网络中每个节点的特征表示。使用 k-means 对特征表示进行聚类。然后,在二维中可视化原始网络,节点现在根据聚类分配颜色
    在这里插入图片描述
    图 3(顶部)显示了设置 p = 1、q = 0.5 时的示例。注意网络区域(即网络社区)是如何使用相同颜色着色的。在此设置中,node2vec 发现了在小说的主要子情节中经常相互交互的角色聚类/社区由于字符之间的边缘基于共现,我们可以得出结论,这种表征与同质性密切相关

    为了发现哪些节点具有相同的结构角色,我们使用相同的网络但设置 p = 1, q = 2,使用 node2vec 获取节点特征,然后根据获得的特征对节点进行聚类。这里 node2vec 获得了节点到聚类的互补分配,使得颜色对应于结构等价,如图 3(底部)所示。例如,node2vec 将蓝色节点嵌入在一起。这些节点代表充当小说不同子情节之间桥梁的角色。类似地,黄色节点主要代表处于外围且互动有限的角色。可以为这些节点聚类分配替代语义解释,但关键是 node2vec 不依赖于特定的等效概念。正如我们通过实验所表明的那样,这些等价概念通常在大多数现实世界的网络中表现出来,并且对预测任务的学习表示的性能产生重大影响。

    4.2 Experimental setup

    我们的实验评估了通过 node2vec 在标准监督学习任务上获得的特征表示:节点的多标签分类和边缘的链接预测。对于这两个任务,我们针对以下特征学习算法评估 node2vec 的性能:

    • Spectral clustering [29]:这是一种矩阵分解方法,我们将图 G 的归一化拉普拉斯矩阵的顶部 d 特征向量作为节点的特征向量表示。
    • DeepWalk [24]:这种方法通过模拟均匀随机游走来学习 d 维特征表示DeepWalk 中的采样策略可以看作是 node2vec 的一个特例,其中 p = 1 和 q = 1
    • LINE [28]:这种方法在两个独立的阶段学习 d 维特征表示。在第一阶段,它通过 BFS 风格的模拟在节点的直接邻居上学习 d/2 维。在第二阶段,它通过在距源节点 2 跳距离处严格采样节点来学习下一个 d/2 维

    我们排除了其他矩阵分解方法,这些方法已经被证明不如DeepWalk [24]。我们还排除了最近的方法,GraRep [6],该方法将LINE一般化,以合并来自超过 2 跳的网络邻域的信息,但是不能有效地扩展到大型网络。

    与先前工作中用于评估基于采样的特征学习算法的设置相比,我们为每种方法生成相同数量的样本,然后评估在预测任务中获得的特征的质量。在这样做时,我们完全因为实现语言(C/C++/Python)而忽略了观察到的性能提升,因为它是算法的次要因素。因此,在采样阶段,DeepWalk、LINE 和 node2vec 的参数设置为在运行时生成相同数量的样本。例如,如果 K 是总体采样预算,则 node2vec 参数满足 K = r·l·|V|。在优化阶段,所有这些基准测试都使用 SGD 进行优化,我们纠正了两个关键差异。首先,DeepWalk 使用分层采样来逼近 softmax 概率,其目标类似于 node2vec 使用的目标。然而,与负采样相比,分层 softmax 效率低下 [22]。因此,在保持其他一切不变的情况下,我们切换到 DeepWalk 中的负采样,这也是 node2vec 和 LINE 中事实上的近似。

    其次,node2vec 和 DeepWalk 都有一个用于优化上下文邻域节点数量的参数,数量越大,需要的优化轮次就越多。对于 LINE,此参数设置为 unity,但由于 LINE 比其他方法更快地完成单个 epoch,我们让它运行 k 个 epoch。

    用于 node2vec 的参数设置与用于 DeepWalk 和 LINE 的典型值一致。具体来说,我们设置 d = 128, r = 10, l = 80, k = 10,并且针对单个 epoch 运行优化。我们对 10 次随机种子初始化重复我们的实验,我们的结果在 p 值小于 0.01 时具有统计学意义。最佳输入输出和返回超参数是使用 10% 标记数据的 10 倍交叉验证来学习的在 p 上进行网格搜索,q ∈ {0.25, 0.50, 1, 2, 4}

    4.3 Multi-label classification

    在多标签分类设置中,每个节点都从有限集 L 中分配一个或多个标签。在训练阶段,我们观察一定比例的节点及其所有标签。任务是预测剩余节点的标签。这是一项具有挑战性的任务,尤其是在 L 很大的情况下。我们使用以下数据集:

    • BlogCatalog [38]:这是 BlogCatalog 网站上列出的博客作者的社会关系网络。标签代表通过博主提供的元数据推断出的博主兴趣。该网络有 10,312 个节点、333,983 条边和 39 个不同的标签。
    • Protein-Protein Interactions (PPI) [5]:我们使用智人的 PPI 网络子图。子图对应于由节点诱导的图,我们可以从标记基因集 [19] 中获得标签并表示生物状态。该网络有 3,890 个节点、76,584 条边和 50 个不同的标签。
    • Wikipedia [20]:这是出现在Wikipedia 转储的前一百万字节中的单词的共现网络。标签表示使用斯坦福词性标注器 [32] 推断的词性 (POS) 标签。该网络有 4,777 个节点、184,812 条边和 40 个不同的标签。

    所有这些网络都表现出同质和结构等价的公平混合。例如,我们期望博主的社交网络表现出强烈的基于同质性的关系;然而,也可能有一些“熟悉的陌生人”,即不互动但分享兴趣的博主,因此在结构上是等效的节点。蛋白质-蛋白质相互作用网络中蛋白质的生物学状态也表现出两种类型的等价性。例如,当蛋白质执行与相邻蛋白质互补的功能时,它们表现出结构等效性,而在其他时候,它们基于同质性组织以帮助相邻蛋白质执行相似功能。词共现网络相当密集,因为在 Wikipedia 语料库的 2length 窗口中共现的词之间存在边。因此,具有相同 POS 标签的单词不难找到,具有高度的同质性。同时,由于句法语法模式,我们期望词性标记中的一些结构等价,例如名词后面的限定词、标点符号后面的名词等。
    在这里插入图片描述
    实验结果。节点特征表示被输入到具有 L2 正则化的 one-vs-rest 逻辑回归分类器。训练数据和测试数据平均分成 10 个随机实例。我们使用 Macro-F1 分数来比较表 2 中的性能,并且相对性能增益超过了最接近的基准。 Micro-F1 和准确性的趋势相似,未显示。

    从结果中,很明显我们可以看到在探索邻域中增加的灵活性如何使 node2vec 优于其他基准算法。在 BlogCatalog 中,我们可以通过将参数 p 和 q 设置为较低的值来发现同质性和结构等价的正确组合,在 Macro-F1 分数中比 DeepWalk 提高 22.3%,比 LINE 提高 229.2%。 LINE 的性能比预期的要差,这可以用它无法重复使用样本来解释,而使用随机游走方法可以轻松完成这一壮举。即使在我们的其他两个网络中,存在混合等价的情况,node2vec 的半监督性质也可以帮助我们推断特征学习所需的适当探索程度。在 PPI 网络的情况下,最佳探索策略 (p = 4, q = 1) 与 DeepWalk 的统一 (p = 1, q = 1) 探索几乎无法区分,通过避免冗余,我们仅比 DeepWalk 略有优势在已经访问过的节点中通过高 p 值,但在 Macro-F1 分数中比 LINE 有令人信服的 23.8% 增益。然而,一般来说,均匀随机游走可能比 node2vec 学习的探索策略差得多。正如我们在维基百科词共现网络中看到的那样,统一游走不能引导搜索过程朝向最佳样本,因此,我们比 DeepWalk 获得了 21.8% 的增益,比 LINE 获得了 33.2% 的增益。
    在这里插入图片描述
    对于更细粒度的分析,我们还比较了性能,同时将训练测试拆分从 10% 更改为 90%,同时像以前一样在 10% 的数据上学习参数 p 和 q。为简洁起见,我们在图 4 中以图形方式总结了 Micro-F1 和 Macro-F1 分数的结果。在这里我们进行了类似的观察。所有方法都显着优于 Spectral 聚类,DeepWalk 优于 LINE,node2vec 始终优于 LINE,并且在跨领域的 DeepWalk 上取得了很大的改进。例如,在 70% 的标记数据下,我们在 BlogCatalog 上实现了比 DeepWalk 26.7% 的最大改进。在最坏的情况下,搜索阶段对学习表示几乎没有影响,在这种情况下 node2vec 相当于 DeepWalk。同样,与 LINE 相比,改进更为显着,除了在 BlogCatalog 上的显着增益(超过 200%)外,我们观察到在仅 10% 的标记数据上训练时,在 PPI 等其他数据集上的大幅改进高达 41.1%。

    4.4 Parameter sensitivity

    node2vec 算法涉及许多参数,在图 5a 中,我们使用标记数据和未标记数据之间的 50-50 分割来检查参数的不同选择如何影响 Node2vec 在 BlogCatalog 数据集上的性能。除被测参数外,所有其他参数均采用默认值。 p 和 q 的默认值设置为统一。

    我们将 Macro-F1 分数测量为参数 p 和 q 的函数。 node2vec 的性能随着输入输出参数 p 和返回参数 q 的减小而提高。这种性能的提高可以基于我们期望在 BlogCatalog 中看到的同质和结构等价。虽然低 q 鼓励向外探索,但它由低 p 来平衡,确保游走不会离起始节点太远。

    我们还检查了特征数量 d 和节点的邻域参数(游走次数 r、游走长度 l 和邻域大小 k)如何影响性能。我们观察到,一旦表示的维度达到 100 左右,性能就会趋于饱和。类似地,我们观察到增加每个源的游走次数和长度可以提高性能,这并不奇怪,因为我们有更大的总体采样预算 K 来学习表示。这两个参数对方法的性能都有相对较高的影响。有趣的是,上下文大小 k 也以增加优化时间为代价提高了性能。但是,在这种情况下,性能差异并不大。

    4.5 Perturbation Analysis

    在这里插入图片描述
    对于许多现实世界的网络,我们无法获得有关网络结构的准确信息。我们进行了扰动研究,分析了与 BlogCatalog 网络中的边缘结构相关的两个不完美信息场景的 node2vec 的性能。在第一种情况下,我们将性能测量为缺失边的比例(相对于整个网络)的函数。缺失的边是随机选择的,受限于网络中连接组件的数量保持固定的约束。正如我们在图 5b(顶部)中看到的,随着缺失边缘比例的增加,Macro-F1 分数的下降大致呈线性,且斜率很小。在图随时间演变的情况(例如,引文网络)或网络建设成本高昂(例如,生物网络)的情况下,网络中缺失边的鲁棒性尤其重要。

    在第二个扰动设置中,我们在网络中随机选择的节点对之间有噪声边缘。如图 5b(底部)所示,与缺失边的设置相比,node2vec 的性能最初下降的速度稍快,但是随着时间的推移,Macro-F1 分数的下降速度逐渐放缓。同样,node2vec 对错误边缘的鲁棒性在多种情况下很有用,例如用于构建网络的测量有噪声的传感器网络。

    4.6 Scalability

    在这里插入图片描述
    为了测试可扩展性,我们使用 node2vec 学习节点表示,其中 Erdos-Renyi 图的默认参数值从 100 增加到 1,000,000 个节点,平均度数为 10。在图 6 中,我们凭经验观察到 node2vec 随着数量的增加呈线性扩展的节点在不到 4 小时内为 100 万个节点生成表示。采样过程包括计算游走(可以忽略不计)的转移概率的预处理和随机游走的模拟。优化阶段使用负采样 [22] 和异步 SGD [26] 变得高效

    先前工作中的许多想法可作为使采样过程在计算上高效的有用指针。我们展示了在 DeepWalk [24] 中也使用的随机游走如何允许将采样节点重新用作出现在游走中的不同源节点的邻域。Alias sampling 允许我们的游走推广到加权网络,几乎没有预处理[28]。尽管我们可以根据基础任务和领域自由设置搜索参数,但学习搜索参数的最佳设置会增加开销。然而,正如我们的实验所证实的那样,这种开销是最小的,因为 node2vec 是半监督的,因此可以用很少的标记数据有效地学习这些参数

    4.7 Link prediction

    在链接预测中,给定一个网络,其中删除了一定比例的边缘,我们希望预测这些缺失的边缘。我们生成带标签的边数据集如下:为了获得正样本,我们从网络中随机抽取 50% 的边,同时确保边缘移除后得到的残差网络是连通的;为了生成负样本,我们随机抽取一个来自网络的相同数量的节点对,它们没有连接它们的边。
    在这里插入图片描述
    由于以前没有使用任何特征学习算法进行链接预测,我们还根据一些流行的启发式分数评估 node2vec,这些分数在链接预测中取得了良好的性能。我们考虑的分数是根据构成该对的节点的邻域集定义的(参见表 3)。我们在以下数据集上测试基准:

    • Facebook [14]:在 Facebook 网络中,节点代表用户,边代表任意两个用户之间的友谊关系。该网络有 4,039 个节点和 88,234 条边。
    • Protein-Protein Interactions (PPI) [5]:在智人的PPI 网络中,节点代表蛋白质,边表示一对蛋白质之间的生物相互作用。该网络有 19,706 个节点和 390,633 条边。
    • arXiv ASTRO-PH [14]:这是一个协作网络,由提交给电子版 arXiv 的论文生成,其中节点代表科学家,如果两位科学家在一篇论文中进行了合作,则他们之间存在优势。该网络有 18,722 个节点和 198,110 条边。
      在这里插入图片描述
      实验结果。我们在表 4 中总结了链路预测的结果。为便于演示,省略了每个 node2vec 条目的最佳 p 和 q 参数设置。我们可以从结果中得出的一般观察结果是,节点对的学习特征表示明显优于启发式基准分数,node2vec 在 arXiv 数据集上实现了最佳 AUC 改进,超过了最佳性能基线(Adamic-Adar [1] )。

    在特征学习算法中,node2vec 在所有网络中的表现都优于 DeepWalk 和 LINE,在 AUC 分数上分别获得高达 3.8% 和 6.5% 的增益,从而为每种算法提供最佳的二元算子选择。当我们单独查看算子时(表 1),node2vec 优于 DeepWalk 和 LINE,除非有一些涉及加权 L1 和加权 L2 算子的情况,其中 LINE 表现更好。总体而言,与 node2vec 一起使用的 Hadamard 算子非常稳定,并且在所有网络中平均提供了最佳性能。

    5. DISCUSSION AND CONCLUSION

    本文将网络中的特征学习作为一个基于搜索的优化问题来研究。这种观点给了我们多重优势。它可以解释基于探索-开发权衡的经典搜索策略。此外,它在应用于预测任务时为学习的表示提供了一定程度的可解释性。例如,我们观察到 BFS 只能探索有限的邻居(neighborhoods)。这使得 BFS 适用于表征网络中依赖于节点的直接局部结构的等价结构。另一方面,DFS 可以自由探索网络邻域,这对于发现同质社区(homophilous communities)很重要,但代价是高方差。

    DeepWalk 和 LINE 都可以看作是网络上的严格搜索(rigid search)策略

    • DeepWalk [24] 提出使用均匀随机游走进行搜索。这种策略的明显限制是无法控制已探索的邻居
    • LINE [28] 主要提出了一种广度优先策略,对节点进行采样并仅在 1 跳和 2 跳邻居上独立优化似然性。这种探索的效果更容易表征,但它具有限制性,并且在探索更深的节点时没有提供灵活性

    相比之下,node2vec 中的搜索策略既灵活又可控,通过参数 p 和 q 探索网络邻域。虽然这些搜索参数具有直观的解释,但当我们可以直接从数据中学习它们时,我们会在复杂网络上获得最佳结果。从实际的角度来看,node2vec 具有可扩展性并且对扰动具有鲁棒性

    我们展示了节点嵌入对链接预测的扩展如何胜过专门为此任务设计的流行启发式得分。我们的方法允许除了表 1 中列出的那些之外的其他二元算子。作为未来的工作,我们想探索 Hadamard 算子比其他算子成功的原因,并根据搜索参数为边建立可解释的等价概念。 node2vec 的未来扩展可能涉及具有特殊结构的网络,例如异构信息网络、具有显式域特征的节点和边缘网络以及有符号边缘网络。连续特征表示是许多深度学习算法的支柱,使用 node2vec 表示作为图上端到端深度学习的构建块会很有趣。

    展开全文
  • node2vec代码实现及详细解析

    千次阅读 2021-12-17 22:39:29
    node2vec代码实现及详细解析

    前言

    KDD 2016 | node2vec:Scalable Feature Learning for Networks
    中我们详细讨论了node2vec的机制,但并没有给出代码实现。本篇文章将从原文出发,逐步详细地讨论如何一步步实现node2vec。

    1.数据导入

    数据为《Les Misérables network》,也就是《悲惨世界》中的人物关系网络:该图是一个无向图,图中共77个节点、254条边。节点表示《悲惨世界》中的人物,两个节点之间的边表示这两个人物出现在书的同一章,边的权重表示两个人物(节点)出现在同一章中的频率。

    import networkx as nx
    G = nx.les_miserables_graph()
    

    原文中node2vec的算法描述如下:
    在这里插入图片描述
    其中node2vecWalk用于产生一个从节点 u u u开始的长为 l l l的游走序列,LearningFeatures利用所有节点产生的游走序列来进行word2vec,得到每个节点的向量表示。

    下面我将结合原文详细介绍这两个算法!!

    2.node2vecWalk

    2.1 归一化转移概率

    2.1.1 原理解析

    node2vecWalk算法的伪代码描述如下:

    1. 将初始节点 u u u加入到walk中
    2. 当前节点curr为walk中最后一个节点
    3. 根据curr和其对周围节点的转移概率选择下一个节点 s s s,并将其加入walk
    4. 当walk长度为 l l l时采集结束,返回walk

    描述比较模糊,我们再看看原文:

    当前节点是 v v v,下一个要采集的节点是 x x x,则我们有如下概率公式:
    在这里插入图片描述
    可以发现,我们只会采样跟当前节点 v v v间有边存在的节点,对于不与当前节点 v v v相连的节点,我们不会去采样。

    采样概率是一个归一化的转移概率: π v x Z \frac{\pi_{vx}} {Z} Zπvx,原文中 π v x \pi_{vx} πvx的描述为:
    在这里插入图片描述
    在这里插入图片描述
    观察上图:节点 t t t已经被采样了,紧接着我们采样了节点 v v v,现在需要做的是采样 v v v之后的下一次采样。根据前文所述,我们只会在节点 v v v的邻接节点中选择一个进行采样,也就是在三个 x x x中进行采样。这个时候 π v x = α p q ( t , x ) ⋅ w v x \pi_{vx}=\alpha_{pq}(t,x) \cdot w_{vx} πvx=αpq(t,x)wvx,其中 w v x w_{vx} wvx表示两个节点间的权重(如果是无权图,则权重为1)

    但是存在一个问题: 如果我们是进行第二次采样(第一次是初始结点 u u u),则有 v = u v=u v=u x x x表示与 u u u相连的节点。这个时候我们就会发现没法利用 π v x = α p q ( t , x ) ⋅ w v x \pi_{vx}=\alpha_{pq}(t,x) \cdot w_{vx} πvx=αpq(t,x)wvx来计算两个节点间的转移概率,因为不存在节点 t t t,也就没法计算 α p q ( t , x ) \alpha_{pq}(t, x) αpq(t,x)!!

    解决: 此时的 π v x \pi_{vx} πvx就是 w v x w_{vx} wvx

    因此,第一步的思路就很明确了:

    1. 如果当前要进行第二次采样,我们就算出第一个节点 u u u到其所有节点的归一化转移概率:非归一化转移概率 π v x \pi_{vx} πvx就是节点 u u u与其邻接节点相连边的权重(可能不在01间),归一化就是将所有概率变换到01之间:所有概率除以归一化常数 Z Z Z Z Z Z为这些权重之和。
    2. 否则,我们则根据当前节点 v v v和上一个被采样的节点 t t t,算出 v v v到其所有邻接节点 x x x的非归一化转移概率: π v x = α p q ( t , x ) ⋅ w v x \pi_{vx}=\alpha_{pq}(t,x) \cdot w_{vx} πvx=αpq(t,x)wvx,然后同样除以它们的和来进行归一化。

    2.1.2 Alias采样

    当我们有了当前节点对其所有邻接节点的转移概率后,我们应该怎么选择?是选择一个转移概率最大的节点进行采样吗?

    答案显而易见,肯定不是! 原文中算法描述如下:
    在这里插入图片描述
    可以看到作者采用了一种叫做AliasSample的采样方法,AliasSample,又名“别名采样”,是一种比较经典的采样算法。比如:游戏中经常遇到按一定的掉落概率来随机掉落指定物品的情况,例如掉落银币25%,金币20%, 钻石10%,装备5%,饰品40%。现在要求下一个掉落的物品类型,或者说一个掉落的随机序列,要求符合上述概率。

    在本文中可以描述为:我们已经有了待选节点集,也有了选择它们的概率,现在我们要进行下一次选择,要求该选择符合上述概率要求。

    在Alias Sample中,我们输入一个概率列表,最后会得到两个数组:Prob和Ailas
    在这里插入图片描述
    然后:随机取某一列 k k k(即[1,4]的随机整数),再随机产生一个[0-1]的小数 c c c,如果 P r o b [ k ] > c Prob[k] > c Prob[k]>c,那么采样结果就是 k k k,反之则为Alias[k]。

    关于Alias Sample的详细原理可以参考:Alias Sample,这里不再详细介绍。

    2.1.3 代码实现

    有了以上思路后我们就很容易编写代码了:

    1. 对于第一种情况:我们可以初始化一个字典nodes_info,nodes_info[node]表示与node有关的所有信息,其中nodes_info[node][0]和nodes_info[node][1]分别表示输入当前node与其邻接点的转移概率列表后得到的Alias数组和Prob数组。
    2. 对于第二种情况,我们可以初始化一个字典edges_info,其中edges_info[(t, v)][0]和edges_info[(t, v)][1]分别表示输入 v v v到所有 x x x的转移概率列表后得到的Alias数组和Prob数组。

    因此,代码实现如下:

    def init_transition_prob(self):
        """
        :return:归一化转移概率矩阵
        """
        g = self.G
        nodes_info, edges_info = {}, {}
        for node in g.nodes:
            nbs = sorted(g.neighbors(node)) # 当前节点的邻居节点
            probs = [g[node][n]['weight'] for n in nbs] # 概率就是权重
            # 归一化
            norm = sum(probs)  # 求和
            normalized_probs = [float(n) / norm for n in probs]  # 归一化
            nodes_info[node] = self.alias_setup(normalized_probs)  # 利用Alias采样得到Alias和Prob
    
        for edge in g.edges:
            # 有向图
            if g.is_directed():
                edges_info[edge] = self.get_alias_edge(edge[0], edge[1])
            # 无向图
            else:
                edges_info[edge] = self.get_alias_edge(edge[0], edge[1])
                edges_info[(edge[1], edge[0])] = self.get_alias_edge(edge[1], edge[0])
    
        self.nodes_info = nodes_info
        self.edges_info = edges_info
    

    其中alias_setup函数就是Alias Sample的具体实现,代码直接参考了网上现成的:

    def alias_setup(self, probs):
        """
        :probs: v到所有x的概率
        :return: Alias数组与Prob数组
        """
        K = len(probs)
        q = np.zeros(K)  # 对应Prob数组
        J = np.zeros(K, dtype=np.int)  # 对应Alias数组
        # Sort the data into the outcomes with probabilities
        # that are larger and smaller than 1/K.
        smaller = []  # 存储比1小的列
        larger = []  # 存储比1大的列
        for kk, prob in enumerate(probs):
            q[kk] = K * prob  # 概率
            if q[kk] < 1.0:
                smaller.append(kk)
            else:
                larger.append(kk)
    
        # Loop though and create little binary mixtures that
        # appropriately allocate the larger outcomes over the
        # overall uniform mixture.
    
        # 通过拼凑,将各个类别都凑为1
        while len(smaller) > 0 and len(larger) > 0:
            small = smaller.pop()
            large = larger.pop()
    
            J[small] = large  # 填充Alias数组
            q[large] = q[large] - (1.0 - q[small])  # 将大的分到小的上
    
            if q[large] < 1.0:
                smaller.append(large)
            else:
                larger.append(large)
    
        return J, q
    

    对于不是第二次采样的情况,需要利用get_alias_edge来得到一条边 ( t , v ) (t, v) (t,v) v v v到其邻居节点转移概率的Alias数组和Prob数组:

    def get_alias_edge(self, t, v):
        """
        Get the alias edge setup lists for a given edge.
        """
        g = self.G
        p = self.p
        q = self.q
        unnormalized_probs = []
        for v_nbr in sorted(g.neighbors(v)):
            if v_nbr == t:
                unnormalized_probs.append(g[v][v_nbr]['weight'] / p)
            elif g.has_edge(v_nbr, t):
                unnormalized_probs.append(g[v][v_nbr]['weight'])
            else:
                unnormalized_probs.append(g[v][v_nbr]['weight'] / q)
        norm_const = sum(unnormalized_probs)
        normalized_probs = [float(u_prob) / norm_const for u_prob in unnormalized_probs]
    
        return self.alias_setup(normalized_probs)
    

    在这里插入图片描述
    代码很容易理解:考虑v的邻居节点v_nbr:如果v_nbr就是t,则非归一化转移概率为 1 p × w \frac{1}{p} \times w p1×w;如果v_nbr与t间有边,也就是图中 x 1 x_1 x1,则 α p q ( t , x ) = 1 \alpha_{pq}(t, x)=1 αpq(t,x)=1,即非归一化转移概率为 1 × w 1 \times w 1×w;否则就是图中 x 2 , x 3 x_2,x_3 x2,x3这种情况,非归一化转移概率为 1 q × w \frac{1}{q} \times w q1×w w w w是两个节点间边的权重。

    有了非归一化转移概率后,我们再进行归一化(除以和),最后再利用alias_setup函数获得Alias数组和Prob数组。

    当我们有了各个节点间的转移概率时,我们在真正采样时需要做出决策,在这些相邻结点中选择一个作为下一个被采样的节点:随机取某一列 k k k(即[1,n]的随机整数,n为邻居节点的个数),再随机产生一个[0-1]的小数 c c c,如果 P r o b [ k ] > c Prob[k] > c Prob[k]>c,那么采样结果就是 k k k,反之则为Alias[k]。该采样函数实现较为简单:

    def alias_draw(self, J, q):
        """
        输入: Prob数组和Alias数组
        输出: 一次采样结果
        """
        K = len(J)
        # Draw from the overall uniform mixture.
        kk = int(np.floor(npr.rand() * K))  # 随机取一列
    
        # Draw from the binary mixture, either keeping the
        # small one, or choosing the associated larger one.
        if npr.rand() < q[kk]:  # 比较
            return kk
        else:
            return J[kk]
    

    其中kk或者J[kk]就是我们最终采样的结果。

    2.2 node2vecWalk的实现

    有了转移概率以及采样策略后,我们就能轻松实现node2vecWalk了:
    在这里插入图片描述
    实现代码如下:

    def node2vecWalk(self, u):
        walk = [u]
        g = self.G
        l = self.l
        nodes_info, edges_info = self.nodes_info, self.edges_info
        while len(walk) < l:
            curr = walk[-1]
            v_curr = sorted(g.neighbors(curr))
            if len(v_curr) > 0:
                if len(walk) == 1:
                    walk.append(v_curr[self.alias_draw(nodes_info[curr][0], nodes_info[curr][1])])
                else:
                    prev = walk[-2]
                    ne = v_curr[self.alias_draw(edges_info[(prev, curr)][0], edges_info[(prev, curr)][1])]
                    walk.append(ne)
            else:
                break
    
        return walk
    

    下面对重要代码进行解析:

    curr = walk[-1]
    v_curr = sorted(g.neighbors(curr))
    

    首先得到当前路径中的最后一个节点curr,并得到它的所有邻居节点v_curr。

    walk.append(v_curr[self.alias_draw(nodes_info[curr][0], nodes_info[curr][1])])
    

    如果curr的邻居节点不为空且当前walk的长度为1,即我们前面提到的第一种情况:进行第二次采样。那么这个时候我们就需要利用Alias Sample从其所有邻居节点中选择一个节点:nodes_info[curr][0]和nodes_info[curr][1]分别代表Alias数组和Prob数组。

    prev = walk[-2]
    ne = v_curr[self.alias_draw(edges_info[(prev, curr)][0], edges_info[(prev, curr)][1])]
    

    如果当前不是进行第二次采样,则分别找到 t t t v v v,也就是prev和curr,然后进行Alias Sample。

    最终返回的walk即为从 u u u开始的一条长为 l l l的随机游走路径。

    3.LearnFeatures

    在这里插入图片描述
    具体步骤:

    1. walks用来存储随机游走,先初始化为空
    2. 一共要进行 r r r次循环,每一次循环要为图中每个节点都生成一个长度为 l l l的游走序列
    3. 第iter次循环中对所有节点都利用node2vec算法生成一个随机游走序列walk,然后将其加入walks
    4. 得到所有节点的 r r r个随机游走序列后,利用SGD方法得到每一个节点的向量表示

    代码实现:

    def learning_features(self):
        g = self.G
        walks = []
        nodes = list(g.nodes())
        for iter in range(self.r):
            np.random.shuffle(nodes)
            for node in nodes:
                walk = self.node2vecWalk(node)
                walks.append(walk)
        # embedding
        walks = [list(map(str, walk)) for walk in walks]
        model = Word2Vec(sentences=walks, vector_size=self.d, window=self.k, min_count=0, sg=1, workers=3)
        f = model.wv
        return f
    

    walks中存储中每一个节点的 r r r条长为 l l l的随机游走路径,输出前两条:

    ['MmeBurgon', 'Gavroche', 'Mabeuf', 'Feuilly', 'Gavroche', 'MmeBurgon', 'Gavroche', 'Bossuet', 'Enjolras', 'Feuilly', 'Mabeuf', 'MotherPlutarch', 'Mabeuf', 'Courfeyrac', 'Bossuet', 'Combeferre', 'Courfeyrac', 'Combeferre', 'Bossuet', 'Enjolras', 'Feuilly', 'Enjolras', 'Claquesous', 'Montparnasse', 'Brujon', 'Babet', 'Valjean', 'Toussaint', 'Cosette', 'Valjean', 'Woman1', 'Valjean', 'Cosette', 'Marius', 'Bossuet', 'Combeferre', 'Bahorel', 'Courfeyrac', 'Combeferre', 'Gavroche', 'Bahorel', 'Feuilly', 'Bossuet', 'MmeHucheloup', 'Bossuet', 'Combeferre', 'Courfeyrac', 'Enjolras', 'Valjean', 'Marius', 'Eponine', 'Marius', 'Combeferre', 'Bahorel', 'Courfeyrac', 'Enjolras', 'Valjean', 'Marius', 'Gillenormand', 'MlleGillenormand', 'MmePontmercy', 'MlleGillenormand', 'Gillenormand', 'Cosette', 'Thenardier', 'Brujon', 'Gavroche', 'MmeHucheloup', 'Gavroche', 'Combeferre', 'Feuilly', 'Prouvaire', 'Bossuet', 'Enjolras', 'Valjean', 'Thenardier', 'MmeThenardier', 'Cosette', 'Valjean', 'MmeDeR']
    ['Feuilly', 'Bossuet', 'Bahorel', 'Prouvaire', 'Enjolras', 'Marius', 'Cosette', 'Javert', 'Valjean', 'Cosette', 'Valjean', 'Marguerite', 'Fantine', 'Dahlia', 'Favourite', 'Listolier', 'Blacheville', 'Fantine', 'Marguerite', 'Fantine', 'Zephine', 'Listolier', 'Tholomyes', 'Blacheville', 'Fameuil', 'Fantine', 'Marguerite', 'Fantine', 'Javert', 'Thenardier', 'Valjean', 'Enjolras', 'Claquesous', 'Thenardier', 'Marius', 'Cosette', 'MlleGillenormand', 'Gillenormand', 'Valjean', 'Thenardier', 'Boulatruelle', 'Thenardier', 'Cosette', 'Marius', 'Eponine', 'Claquesous', 'Javert', 'Valjean', 'Javert', 'Thenardier', 'Javert', 'Enjolras', 'Grantaire', 'Combeferre', 'Gavroche', 'Joly', 'Marius', 'Cosette', 'Valjean', 'Javert', 'Babet', 'Claquesous', 'Enjolras', 'Feuilly', 'Combeferre', 'Bahorel', 'Courfeyrac', 'Enjolras', 'Marius', 'Thenardier', 'Javert', 'Valjean', 'Isabeau', 'Valjean', 'Fauchelevent', 'Gribier', 'Fauchelevent', 'Javert', 'Enjolras', 'Marius']
    

    可以看到第一条随机游走路径是以节点MmeBurgon开始的,第二条是从节点Feuilly开始的,两条路径长度都为 l l l

    有了walks之后,我们利用gensim库中的Word2Vec进行训练,进而得到所有节点的向量表示:

    model = Word2Vec(sentences=walks, vector_size=self.d, window=self.k, min_count=0, sg=1, workers=3)
    

    其中:

    1. sentences是我们要分析的语料,在node2vec中就是随机游走路径的集合。
    2. vector_size是节点向量的维度,这里为 d d d
    3. window是词向量上下文最大距离,即Skip-Gram和CBOW中窗口的长度,默认值为5。
    4. min_cout:可以对字典做截断,词频少于min_count次数的单词会被丢弃掉,默认值为5,这里设置为0。
    5. sg:模型选择,sg=1表示采用Skip-Gram模型,sg=0表示采用CBOW模型,默认为0,这里选择Skip-Gram模型。
    6. workers:训练并行数,这里选择3。

    最终,f中存储着所有节点的长度为 d d d的向量表示,任意输出一个:

    print(f['MmeBurgon'])
    

    MmeBurgon节点的向量表示为:

    [-0.05092877 -0.02686426 -0.2292252   0.11856086  0.02136412  0.01406081
     -0.26274496 -0.15402426  0.1976506  -0.03906344 -0.1944654   0.0344015
      0.17913733  0.08412573  0.14779484 -0.00783093 -0.17162482 -0.28095236
     -0.32425568  0.2492605   0.14210573 -0.06607451  0.40488595 -0.15641351
     -0.01836408  0.0923218  -0.07496541  0.1163046   0.01180712  0.24809936
     -0.04660206 -0.36390662 -0.20256323 -0.07164664 -0.03223448  0.06946431
     -0.28120005 -0.14545655  0.2894095  -0.00597684 -0.2806793  -0.02517208
      0.21234442 -0.35515746  0.03860907  0.12777379  0.31198564 -0.04142399
     -0.06592249 -0.01730651  0.06897946 -0.26776454 -0.00844726 -0.13702574
      0.23738769 -0.23513325  0.05750211  0.01762778 -0.03779545 -0.29060882
      0.1997382   0.012223   -0.23850201 -0.16767174  0.0212742   0.11717773
      0.08926564  0.10213668 -0.07187556 -0.02068917  0.07960241 -0.15014939
      0.1681073   0.12445314  0.13363989 -0.23188415 -0.17411086  0.23457739
     -0.13661143  0.3249664  -0.07310021  0.24981983 -0.01397824  0.28996238
     -0.02117981 -0.12742186  0.33266178  0.07946197  0.29308477  0.05445471
     -0.00712562 -0.06370848  0.16291171 -0.04468412  0.33400518 -0.19028513
     -0.2808339   0.01152208 -0.13062981 -0.27341706 -0.20656888  0.22132947
     -0.20722346 -0.05620798 -0.33125588  0.05310262 -0.17866907  0.20349303
      0.09851206  0.03873271 -0.20351988  0.15531495 -0.09796275 -0.20567754
     -0.16734612  0.04089455  0.22214974  0.29019567 -0.0675301  -0.25800622
     -0.19473355  0.30337527 -0.3567541   0.11847463  0.00324172 -0.10936202
     -0.07167141 -0.01137679]
    

    4.参数选择

    参数为DeepWalk和LINE的典型值:
    在这里插入图片描述
    返回参数 p p p和出入参数 q q q的选择: p = 1 , q = 0.5 p=1,q=0.5 p=1,q=0.5

    if __name__ == '__main__':
        p, q = 1, 0.5
        d, r, l, k = 128, 10, 80, 10
        G = nx.les_miserables_graph()
        node2vec = node2vec(G, p, q, d, r, l, k)
        model = node2vec.learning_features()
    

    5.完整代码

    我把数据和代码放在了GitHub上:完整代码,原创不易,下载时请随手给个follow和star,感谢!

    展开全文
  • node2vec.pdf

    2020-05-05 10:07:39
    Prediction tasks over nodes and edges in networks require careful effort in engineering features used by learning algorithms. Recent research in the broader field of representation learning has led to...
  • 本文借鉴word2vec提出了node2vec,通过maximize the likelihood of preserving network neighborhoods of nodes in a d-dimensional feature space得到特征表示。利用二阶随机游走产生节点社区。
  • GraphEmbedding - Node2vec 图文详解

    千次阅读 2021-08-24 15:19:45
    二.Node2vec 算法 1.Node2vec 简介 说起 Node2vec 还是要提一下 DeepWalk,DeepWalk 基于图随机游走,默认各个边的权重为1,其更偏向于 DFS 即深度优先搜索,DFS 的好处是搜索的全局性好,但是对于较远的邻居的 ...
  • KDD 2016 | node2vec:Scalable Feature Learning for Networks
  • node2vec-master.zip

    2021-03-15 15:40:40
    node2vec-master.zip
  • 资源分类:Python库 所属语言:Python 使用前提:需要解压 资源全名:node2vec_fugue-0.2.12-py3-none-any.whl 资源来源:官方 安装方法:https://lanzao.blog.csdn.net/article/details/101784059
  • 论文阅读|node2vec: Scalable Feature Learning for Networks 文章目录论文阅读|node2vec: Scalable Feature Learning for NetworksAbstractIntroductionFeature Learning FrameworkClassic search strategiesnode2...
  • 基于Node2Vec的改进算法研究
  • node2vec的工作原理-word2vec无法做到的 (How node2vec works — and what it can do that word2vec can’t) 如何以不同的方式考虑您的数据 (How to think about your data differently) I...
  • 首先Node2vec和Deepwalk都是NLP中的word2vec在图中的拓展应用,其中Node2vec又是在Deepwalk基础上的拓展,主要有以下两个方面的改进: 在图中随机游走生成序列时,Node2vec从Deepwalk的无偏进阶到参数可控的有偏。 ...
  • 详解Node2vec以及优缺点

    千次阅读 2020-12-27 20:38:34
    根据以上两个假设条件,最终的目标函数公式1简化为公式4 3.2 路径采样策略 Node2vec依然延续了Deepwalk采用随机游走的方式获取顶点的近邻序列,Node2vec不同的是采用的是一种有偏的随机游走。 Node2vec引入两个超...
  • 从word2vecnode2vec

    千次阅读 2020-02-03 17:08:44
    word2vec 1. 什么是word2vec 在自然语言处理任务(NLP)中,最细粒度是词语,所以处理NLP问题,首先要处理好词语。 由于所有自然语言中的词语,都是人类的抽象总结,是符号形式的。而对于数学模型,如果要建立词语到...
  • node2vec简单总结

    2021-09-17 08:44:34
    node2vec 参考博客:https://zhuanlan.zhihu.com/p/56542707 伪代码 def node2vec_walk(G, u, walk_length): walk = [u] for l in range(walk_length): V = get_neighbors(G, walk[-1]) s = alias_sample(V, ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 21,148
精华内容 8,459
关键字:

node2vec