Skip to content
返回搜索结果

网络嵌入 — Node2Vec、DeepWalk、LINE

年份
2014 (DeepWalk); 2016 (Node2Vec)
类型
Representation learning / unsupervised network method

本文为机器翻译,尚未经过审校。 阅读英文原文

字号

它有什么作用?

网络嵌入是一类表征学习方法,它将图的每个节点映射到密集、低维的向量中,同时保留网络的结构属性。Perozzi、Al-Rfou 和 Skiena 在 DeepWalk (2014) 中首次将该方法形式化应用于社交网络数据,该方法将 Word2Vec 的 skip-gram 模型应用于图上的随机游走。Grover 和 Leskovec 在 Node2Vec (2016) 中对其进行了扩展,引入了一种有偏随机游走,平衡了广度优先和深度优先探索。这些嵌入将关系数据转换为特征向量,可供标准机器学习分类器和聚类算法直接使用。

方法背后的直觉

图由节点和边构成,但大多数机器学习算法需要表格形式的数字。网络嵌入解决了这一转换问题。正如 Word2Vec 通过观察句子中哪些词出现在彼此附近来学习词义一样,DeepWalk 通过观察图上随机游走中哪些节点出现在彼此附近来学习节点含义。结果是向量空间中的一个坐标——结构相似或频繁共同访问的节点最终会彼此靠近。一旦每个节点都有一个向量,就可以将这些向量输入分类器,使用 k-means 对它们进行聚类,或使用 UMAP 进行可视化,而无需编写任何特定于图的代码。

历史学

将 Word2Vec 应用于图结构数据的想法由 Perozzi、Al-Rfou 和 Skiena 在 DeepWalk (KDD 2014) 中提出,该研究表明社交图上的随机游走可以取代手工特征进行节点分类。Grover 和 Leskovec 在 Node2Vec (KDD 2016) 中对此进行了扩展,引入了由 p 和 q 参数化的二阶有偏随机游走,明确控制了基于同质性和基于结构等价性的邻域探索之间的权衡。大约在同一时期,Tang 等人提出了 LINE (WWW 2015),它通过直接优化一阶和二阶接近度目标而不是通过随机游走来学习嵌入,使其适用于非常大的图。这三种方法共同建立了网络表征学习领域,并启发了后续的图神经网络架构。

何时使用

当您拥有至少 50 个节点的图并且需要连续向量特征用于下游任务(例如节点分类、链接预测或节点聚类)时,网络嵌入是合适的。该方法适用于无权图和加权图,并处理有向或无向结构。当简单的、均匀的随机游走基线足够时,选择 DeepWalk。当您希望通过 p 和 q 参数调整同质性和结构等价性之间的平衡时,选择 Node2Vec。如果您需要在推理时嵌入新的、以前未见的节点而无需重新训练,请优先选择 GraphSAGE 等归纳方法;标准形式的网络嵌入是转导的。该方法不需要正态分布的节点属性。

局限与注意事项

  • 转导性:模型无法嵌入训练期间不存在的节点,除非进行完全重新训练。
  • 超参数敏感性:嵌入维度、游走长度、游走次数、窗口大小、p 和 q 都会影响嵌入质量,需要进行调整。
  • 随机游走无法捕获更高阶的图结构(例如,超边或多关系边),除非进行扩展。
  • 在非常小的图(少于 50 个节点)上性能会下降,因为游走语料库过于稀疏,无法学习可靠的统计数据。

来源中的条件不能替代独立的科学审查或分析引擎的验证。

优势

  • 将关系图数据转换为固定长度的向量,与任何标准机器学习流程兼容。
  • Node2Vec 的 p 和 q 参数允许分析师调整社区敏感和角色敏感嵌入之间的平衡。
  • 边权重可以纳入游走概率中,无需额外的建模步骤即可捕获关系强度。
  • 通过高效的随机游走采样和 skip-gram 训练过程,可扩展到大型图。

应用

  • 引文网络、社交平台或生物交互图中的节点分类。
  • 链接预测——通过比较节点嵌入相似性来识别缺失或未来的边。
  • 通过使用 k-means 或层次方法对节点向量进行聚类来检测社区。
  • 异常检测——向量空间中嵌入为异常值的节点可能代表不寻常的结构角色。
  • 推荐系统,其中用户和项目是二分图或多重交互图中的节点。

使用方式

使用方式

1

该过程始于一个图 G,其中节点是实体,边代表关系。边可以是有向的或无向的,并且可以带有权重,这些权重将影响后续遍历的概率。如果存在边权重,它们将包含在游走概率中;如果不存在,所有边都将获得相同的权重。在此阶段,分析师还会选择算法变体——DeepWalk 用于均匀随机游走,Node2Vec 用于由参数 p(返回)和 q(进出)控制的有偏游走,或 LINE 用于分别学习一阶和二阶邻域接近度。Node2Vec 参数方案的选择由预期的网络属性指导:同质性(相似节点连接,因此偏好广度优先探索,q < 1)或结构等价性(具有相似角色的节点可能相距很远,因此偏好深度优先探索,p < 1)。

2

从每个节点开始,算法模拟一系列固定长度(通常为 30 步)的随机游走,并重复多次(通常每个节点 200 次游走)。每次游走都会生成一个节点标识符序列,类似于一个词语的句子。在 DeepWalk 中,下一个节点是从邻居中均匀选择的。在 Node2Vec 中,下一个节点是根据受 p 和 q 偏置的转移概率选择的:返回到前一个节点会受到 1/p 的惩罚,保持相同距离的概率为 1,向外移动的概率由 1/q 控制。所有游走的集合形成一个节点序列语料库,编码了图的拓扑结构。

3

节点序列语料库被输入到 skip-gram 模型(与 Word2Vec 相同的架构)中。对于游走中的每个节点,模型预测窗口内(通常为 10 步)的周围上下文节点。通过随机梯度下降,模型学习每个节点的固定维度(通常为 64 或 128)的密集向量表示,使得在游走中共同出现的节点具有相似的向量。维度是一个超参数:更大的维度捕获更多的结构,但会增加计算量并增加在小图上过拟合的风险。

4

训练完成后,模型为每个节点提供一个嵌入向量。这些向量用作节点分类(将它们输入逻辑回归或神经网络分类器)、链接预测(比较候选节点对的向量)或社区检测(对向量进行聚类)的特征。这些嵌入是转导的:它们对于训练期间看到的节点是固定的。如果在训练后必须嵌入新节点,则应使用 GraphSAGE 等归纳方法,因为标准的 Node2Vec 或 DeepWalk 模型无法在不重新训练的情况下泛化到未见节点。

常见陷阱

  • 将 Node2Vec 模型应用于训练图中不存在的新节点——模型将不会为它们提供向量;当转导嵌入不可接受时,请使用归纳方法(例如 GraphSAGE)。
  • 使用默认 p=1, q=1(等同于 DeepWalk)而未检查网络是否遵循同质性或结构等价性模式——根据预期模式调整 p 和 q 可以显著提高下游任务性能。
  • 将嵌入维度视为固定常数:在小图上,64 或 128 的维度可能会过拟合;从较低维度开始,并在下游任务上进行验证。
  • 忽略最小样本要求:节点少于 50 个的图会产生过于稀疏的游走语料库,无法训练可靠的嵌入。

常见问题

DeepWalk、Node2Vec 和 LINE 之间有什么区别?

DeepWalk 使用均匀随机游走和 Word2Vec skip-gram 模型——它是最简单的基线。Node2Vec 添加了由 p 和 q 控制的有偏随机游走,允许分析师调整游走是像广度优先搜索(同质性)还是深度优先搜索(结构等价性)那样进行探索。LINE 完全不使用随机游走;它直接在边列表上优化一阶和二阶接近度目标,这对于非常大的图更具可扩展性,但牺牲了基于游走的邻域信号。

如何在 Node2Vec 中选择 p 和 q 参数?

p 控制返回到前一个节点的可能性(p 值低 = 回溯少),q 控制探索半径(q < 1 有利于向外探索,q > 1 使游走保持在源附近)。如果您期望同一社区中的节点相似(同质性),请设置 q < 1 以允许游走向外漫游。如果您期望具有相同结构角色的节点相似,即使它们相距很远,请设置 p < 1 以鼓励深度优先探索。在下游任务上验证这两种方案。

训练后是否可以在不重新训练整个模型的情况下嵌入新节点?

标准的 Node2Vec 和 DeepWalk 是转导的:嵌入矩阵仅覆盖训练期间看到的节点。为了对新的、以前未见的节点进行归纳泛化,请使用归纳图神经网络方法,例如 GraphSAGE,它学习一个节点邻域上的聚合函数,可以在推理时应用于任何节点。

嵌入应该使用多少维度?

最常见的选择是 64 和 128,这些对于中大型图效果很好。对于小型图(50-200 个节点),从较低维度(16 或 32)开始,以避免过拟合,并通过衡量下游任务性能(例如,节点分类准确性)而不是单独的重建误差来评估嵌入质量。

相关方法

参考文献

  1. Grover, A. & Leskovec, J. (2016). Node2Vec: Scalable Feature Learning for Networks. Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 855-864.

    打开 DOI 文献
    已复制。
  2. Perozzi, B., Al-Rfou, R., & Skiena, S. (2014). DeepWalk: Online Learning of Social Representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 701-710.

    打开 DOI 文献
    已复制。