给公司怎么做官方网站,简单网站建设流程,wordpress 群站,南昌装修网站建设node2vec: Scalable Feature Learning for Networks
node2vec#xff1a;可扩展的网络特征学习
ABSTRACT
网络中节点和边缘的预测任务需要在学习算法使用的工程特征上付出仔细的努力。最近在更广泛的表示学习领域的研究通过学习特征本身在自动化预测方面取得了重大进展。然…node2vec: Scalable Feature Learning for Networks
node2vec可扩展的网络特征学习
ABSTRACT
网络中节点和边缘的预测任务需要在学习算法使用的工程特征上付出仔细的努力。最近在更广泛的表示学习领域的研究通过学习特征本身在自动化预测方面取得了重大进展。然而目前的特征学习方法的表现力不足以捕获网络中观察到的连接模式的多样性。
在这里我们提出了node2vec一种用于学习网络中节点的连续特征表示的算法框架。在node2vec中我们学习节点到低维特征空间的映射最大化保留节点网络邻域的可能性。我们定义了节点网络邻居的灵活概念并设计了一个有偏差的随机游走程序可以有效地探索不同的邻居。我们的算法概括了基于网络邻域的严格概念的先前工作并且我们认为探索邻域的灵活性是学习更丰富的表示的关键。
我们证明了 node2vec 相对于现有最先进技术在来自不同领域的几个现实世界网络中的多标签分类和链接预测方面的功效。总而言之我们的工作代表了一种在复杂网络中有效学习最先进的任务独立表示的新方法。
网络分析中的许多重要任务涉及节点和边的预测。在典型的节点分类任务中我们感兴趣的是预测网络中节点最可能的标签。例如在社交网络中我们可能对预测用户的兴趣感兴趣或者在蛋白质-蛋白质相互作用网络中我们可能对预测蛋白质的功能标签感兴趣。类似地在链接预测中我们希望预测网络中的一对节点是否应该有一条边连接它们。链接预测在很多领域都很有用。例如在基因组学中它可以帮助我们发现基因之间的新颖相互作用在社交网络中它可以识别现实世界的朋友 。
任何有监督的机器学习算法都需要一组信息丰富、具有区分性且独立的特征。在网络的预测问题中这意味着必须为节点和边构建特征向量表示。典型的解决方案涉及基于专家知识手工设计特定领域的功能。即使人们不考虑特征工程所需的繁琐工作这些特征通常是针对特定任务而设计的并且不能泛化到不同的预测任务。
另一种方法是通过解决优化问题来学习特征表示。特征学习的挑战是定义目标函数其中涉及平衡计算效率和预测准确性的权衡。一方面人们可以直接寻找一种能够优化下游预测任务性能的特征表示。虽然这种监督过程具有良好的准确性但由于需要估计的参数数量激增它的代价是训练时间复杂度很高。在另一个极端目标函数可以定义为独立于下游预测任务并且可以以纯粹无监督的方式学习表示。这使得优化的计算效率很高并且通过精心设计的目标它会产生与任务无关的特征这些特征在预测准确性方面与特定于任务的方法紧密匹配。
然而当前的技术无法令人满意地定义和优化网络中可扩展的无监督特征学习所需的合理目标。基于线性和非线性降维技术例如主成分分析、多维缩放及其扩展的经典方法优化了一个目标该目标转换网络的代表性数据矩阵使其最大化,数据表示的方差。因此这些方法总是涉及适当数据矩阵的特征分解这对于大型现实世界网络来说是昂贵的。此外由此产生的潜在表示在网络上的各种预测任务上表现不佳。
或者我们可以设计一个目标来保护节点的局部邻域。可以使用类似于单个隐藏层前馈神经网络上的反向传播的随机梯度下降 (SGD) 来有效优化目标。最近在这个方向上的尝试提出了有效的算法但依赖于网络邻居的严格概念这导致这些方法在很大程度上对网络特有的连接模式不敏感。具体来说网络中的节点可以根据它们所属的社区进行组织即同质性在其他情况下组织可以基于网络中节点的结构角色即结构等效性。例如在图 1 中我们观察到节点 u u u 和 s 1 s_1 s1 属于同一个紧密结合的节点社区而两个不同社区中的节点 u u u 和 s 6 s_6 s6 共享相同的中心节点结构角色。现实世界的网络通常表现出这些等价物的混合。因此必须允许一种灵活的算法来学习遵循两个原则的节点表示能够学习将来自同一网络社区的节点紧密嵌入在一起的表示以及学习共享相似角色的节点具有相似嵌入的表示。这将使特征学习算法能够泛化到各种领域和预测任务。 现在的工作。 我们提出了node2vec一种用于网络中可扩展特征学习的半监督算法。受先前自然语言处理工作的启发我们使用 SGD 优化了基于图形的自定义目标函数。直观上我们的方法返回的特征表示最大限度地保留了 d d d 维特征空间中节点的网络邻域的可能性。我们使用二阶随机游走方法来生成节点的样本网络邻域。
我们的主要贡献是定义了节点网络邻居的灵活概念。通过选择适当的邻域概念node2vec 可以学习根据节点的网络角色和/或所属社区来组织节点的表示。我们通过开发一系列有偏随机游走来实现这一目标这些游走可以有效地探索给定节点的不同邻域。由此产生的算法是灵活的使我们能够通过可调参数来控制搜索空间这与之前的工作中严格的搜索过程不同。因此我们的方法概括了先前的工作并且可以对网络中观察到的所有等价物进行建模。控制我们的搜索策略的参数具有直观的解释并使行走偏向不同的网络探索策略。这些参数也可以以半监督的方式使用一小部分标记数据直接学习。
我们还展示了如何将单个节点的特征表示扩展到节点对即边。为了生成边缘的特征表示我们使用简单的二元运算符组合各个节点的学习特征表示。这种组合性使 node2vec 能够完成涉及节点和边的预测任务。
我们的实验重点关注网络中的两个常见预测任务多标签分类任务其中每个节点都被分配一个或多个类标签以及链接预测任务我们在给定一对节点的情况下预测边缘的存在。我们将 node2vec 的性能与最先进的特征学习算法进行了对比。我们对来自不同领域的几个现实世界网络进行了实验例如社交网络、信息网络以及系统生物学网络。实验表明node2vec 在多标签分类方面优于最先进的方法高达 26.7%在链接预测方面优于最先进的方法高达 12.6%。即使使用 10% 的标记数据该算法也显示出具有竞争力的性能并且对于噪声或缺失边缘形式的扰动也具有鲁棒性。从计算角度来看node2vec 的主要阶段是可以并行化的并且可以在几个小时内扩展到具有数百万个节点的大型网络。
总的来说我们的论文做出了以下贡献
我们提出了node2vec一种用于网络中特征学习的高效可扩展算法它使用 SGD 有效地优化新颖的网络感知、邻域保留目标。我们展示了node2vec如何符合网络科学的既定原则为发现符合不同等价的表示提供了灵活性。我们基于邻域保留目标扩展了 node2vec 和其他特征学习方法从节点扩展到基于边缘的预测任务的节点对。我们根据经验评估了 node2vec 在多个真实数据集上的多标签分类和链接预测。
本文的其余部分的结构如下。在第2节中我们简要回顾了网络特征学习的相关工作。我们在第 3 节中介绍了使用 node2vec 进行特征学习的技术细节。在第 4 节中我们根据经验评估了 node2vec 在各种现实世界网络上的节点和边缘上的预测任务并评估了我们算法的参数敏感性、扰动分析和可扩展性方面。我们最后讨论了 node2vec 框架并在第 5 节中强调了未来工作的一些有前景的方向。node2vec 的数据集和参考实现可在项目页面上找到http://snap.stanford.edu/node2vec.
2. RELATED WORK
机器学习社区在不同的主题下对特征工程进行了广泛的研究。在网络中为节点生成特征的传统范例是基于特征提取技术该技术通常涉及一些基于网络属性的手工制作的种子特征。相反我们的目标是通过将特征提取作为表示学习问题来自动化整个过程在这种情况下我们不需要任何手工设计的特征。
无监督特征学习方法通常利用图的各种矩阵表示的谱特性特别是拉普拉斯矩阵和邻接矩阵。从线性代数的角度来看这些方法可以被视为降维技术。已经提出了几种线性例如PCA和非线性例如IsoMap降维技术。这些方法都存在计算和统计性能缺陷。就计算效率而言数据矩阵的特征分解是昂贵的除非解的质量受到近似的显着影响因此这些方法很难扩展到大型网络。其次这些方法针对对网络中观察到的不同模式例如同质性和结构等价性不稳健的目标进行优化并对底层网络结构和预测任务之间的关系做出假设。例如谱聚类做出了强同质性假设即图割对于分类很有用。这样的假设在许多情况下都是合理的但在跨不同网络的有效泛化方面却不能令人满意。
自然语言处理表征学习的最新进展为离散对象例如单词的特征学习开辟了新的方法。特别是Skip-gram 模型旨在通过优化邻域保留似然目标来学习单词的连续特征表示。该算法的流程如下它扫描文档的单词并针对每个单词嵌入它以便该单词的特征可以预测附近的单词即某个上下文窗口内的单词。单词特征表示是通过使用带有负采样的 SGD 优化似然目标来学习的。 Skip-gram 目标基于分布假设该假设指出相似上下文中的单词往往具有相似的含义。也就是说相似的词往往出现在相似的词邻域中。
受 Skip-gram 模型的启发最近的研究通过将网络表示为“文档”来建立网络的类比。与文档是有序的单词序列一样我们可以从底层网络中采样节点序列并将网络转换为有序的节点序列。然而节点有多种可能的采样策略从而导致不同的学习特征表示。事实上正如我们将要展示的不存在适用于所有网络和所有预测任务的明确的获胜采样策略。这是先前工作的一个主要缺点它无法提供从网络中采样节点的任何灵活性。我们的算法node2vec通过设计一个灵活的目标克服了这个限制该目标不依赖于特定的采样策略并提供参数来调整探索的搜索空间参见第3节。
最后对于基于节点和边缘的预测任务最近有大量基于现有和新颖的图特定深度网络架构的监督特征学习工作。这些架构使用多层非线性变换直接最小化下游预测任务的损失函数从而获得高精度但由于训练时间要求高而以可扩展性为代价。
3. FEATURE LEARNING FRAMEWORK
我们将网络中的特征学习表述为最大似然优化问题。令 G ( V , E ) G (V, E) G(V,E) 为给定网络。我们的分析是通用的适用于任何无定向、无加权网络。令 f : V → R d f:V\to\mathbb{R}^{d} f:V→Rd为从节点到我们旨在为下游预测任务学习的特征表示的映射函数。这里 d d d 是一个参数指定特征表示的维数。等价地 f f f 是大小为 ∣ V ∣ × d |V|\times d ∣V∣×d 的矩阵。对于每个源节点 u ∈ V u \in V u∈V我们将 N S ( u ) ⊂ V N_{S}(u)\subset V NS(u)⊂V定义为通过邻域采样策略 S S S 生成的节点 u u u 的网络邻域。
我们继续将 Skip-gram 架构扩展到网络。我们寻求优化以下目标函数该函数最大化观察节点 u u u 的网络邻域 N S ( u ) N_{S}(u) NS(u) 的对数概率该节点 u u u 以其特征表示为条件由 f f f 给出 max f ∑ u ∈ V log P r ( N S ( u ) ∣ f ( u ) ) . ( 1 ) \max_{f}\sum_{u\in V}\log Pr(N_{S}(u)|f(u)).\quad(1) fmaxu∈V∑logPr(NS(u)∣f(u)).(1)
为了使优化问题易于处理我们做出两个标准假设
有条件的独立。我们通过假设观察邻域节点的可能性独立于观察给定源的特征表示的任何其他邻域节点来分解可能性 P r ( N S ( u ) ∣ f ( u ) ) ∏ n i ∈ N S ( u ) P r ( n i ∣ f ( u ) ) . Pr(N_S(u)|f(u))\prod_{n_i\in N_S(u)}Pr(n_i|f(u)). Pr(NS(u)∣f(u))ni∈NS(u)∏Pr(ni∣f(u)).
特征空间的对称性。源节点和邻域节点在特征空间中彼此具有对称效应。因此我们将每个源邻域节点对的条件似然建模为由其特征的点积参数化的 softmax 单元 P r ( n i ∣ f ( u ) ) exp ( f ( n i ) ⋅ f ( u ) ) ∑ v ∈ V exp ( f ( 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))}. Pr(ni∣f(u))∑v∈Vexp(f(v)⋅f(u))exp(f(ni)⋅f(u)).
有了上述假设方程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}\bigg[-\log Z_u\sum_{n_i\in N_S(u)}f(n_i)\cdot f(u)\bigg].\quad(2) fmaxu∈V∑[−logZuni∈NS(u)∑f(ni)⋅f(u)].(2)
每个节点的划分函数 Z u ∑ v ∈ V exp ( f ( u ) ⋅ f ( v ) ) Z_{u}\sum_{v\in V}\exp(f(u)\cdot f(v)) Zu∑v∈Vexp(f(u)⋅f(v))对于大型网络来说计算起来很昂贵我们使用负采样来近似它。我们优化方程2在定义特征 f f f的模型参数上使用随机梯度上升。
基于 Skip-gram 架构的特征学习方法最初是在自然语言背景下开发的。考虑到文本的线性性质可以使用连续单词上的滑动窗口自然地定义邻域的概念。然而网络不是线性的因此需要更丰富的邻域概念。为了解决这个问题我们提出了一种随机过程对给定源节点 u u u 的许多不同邻域进行采样。邻域 N S ( u ) N_{S}(u) NS(u) 不仅限于直接邻居而且可以具有截然不同的结构具体取决于采样策略 S S S。
3.1 Classic search strategies
我们将源节点的邻域采样问题视为局部搜索的一种形式。图 1 显示了一个图其中给定源节点 u u 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 有两种极端采样策略
广度优先采样(BFS)邻域 N S N_S NS 仅限于与源直接相邻的节点。例如在图 1 中对于大小 k 3 k 3 k3 的邻域BFS 对节点 s 1 , s 2 , s 3 s_1,s_2,s_3 s1,s2,s3 进行采样。深度优先采样(DFS)邻域由以距源节点的距离逐渐增加的方式顺序采样的节点组成。在图 1 中DFS对 s 4 , s 5 , s 6 s_4,s_5,s_6 s4,s5,s6 进行采样。
广度优先和深度优先采样代表了他们探索的搜索空间方面的极端场景从而对学习的表示产生了有趣的影响。
特别是网络中节点的预测任务经常在两种相似性之间穿梭同质性和结构等价性。根据同质性假设 高度互连且属于相似网络集群或社区的节点应该紧密嵌入在一起例如图 1 中的节点 s 1 s_1 s1 和 u u u 属于同一网络社区。相反根据结构等价假设在网络中具有相似结构作用的节点应该紧密地嵌入在一起例如图1中的节点 u u u和 s 6 s_6 s6充当其相应社区的中心。重要的是与同质性不同结构等价并不强调连通性而是强调连通性。网络中的节点可以相距很远但仍然具有相同的结构作用。在现实世界中这些等价概念并不是排他性的网络通常表现出两种行为其中一些节点表现出同质性而另一些则反映结构等效性。
我们观察到 BFS 和 DFS 策略在生成反映上述任一等价性的表示方面发挥着关键作用。特别是BFS 采样的邻域导致与结构等价密切对应的嵌入。直观地我们注意到为了确定结构等效性准确地描述当地社区通常就足够了。例如基于网络角色例如桥梁和枢纽的结构等价性可以通过观察每个节点的直接邻居来推断。通过将搜索限制在附近的节点BFS 实现了这种表征并获得每个节点邻域的微观视图。此外在 BFS 中采样邻域中的节点往往会重复多次。这也很重要因为它减少了表征 1 跳节点相对于源节点的分布的方差。然而对于任何给定的 k k k只探索了该图的一小部分。
DFS则相反它可以探索网络的更大部分因为它可以进一步远离源节点 u u u样本大小 k k k是固定的。在DFS中采样的节点更准确地反映了一个宏观的观点这是必不可少的基于同质性的社区推断的邻居。然而DFS的问题是不仅要推断网络中存在哪些节点到节点的依赖关系而且要描述这些依赖关系的确切性质。这很难因为我们对样本大小有限制并且要探索的邻域很大导致方差很高。其次移动到更大的深度会导致复杂的依赖关系因为采样的节点可能远离源并且可能不太具有代表性。 3.2 node2vec
基于上述观察我们设计了一种灵活的邻域采样策略使我们能够在 BFS 和 DFS 之间平滑插值。我们通过开发一种灵活的有偏随机游走程序来实现这一目标该程序可以以 BFS 和 DFS 方式探索邻域。
3.2.1 Random Walks 随机游走
形式上给定源节点 u u u我们模拟固定长度 l l l 的随机游走。让 c i c_i ci 表示遍历中的第 i i i 个节点从 c 0 u c_0 u c0u 开始。节点 c i c_i ci 由以下分布生成 P ( c i x ∣ c i − 1 v ) { π v x Z if ( v , x ) ∈ E 0 otherwise P(c_ix\mid c_{i-1}v)\begin{cases}\frac{\pi_{vx}}{Z}\text{if} (v,x)\in E\\0\text{otherwise}\end{cases} P(cix∣ci−1v){Zπvx0if(v,x)∈Eotherwise
其中 π v x \pi_{vx} πvx 是节点 v v v 和 x x x 之间的非归一化转移概率 Z Z Z 是归一化常数。
3.2.2 Search bias α 搜索偏差 α \alpha α
偏置随机游走的最简单方法是根据静态边权重 w v x w_{vx} wvx 对下一个节点进行采样即 π v x w v x \pi_{vx}w_{vx} πvxwvx在未加权图 w v x 1 w_{vx} 1 wvx1 的情况下然而这不允许我们解释网络结构并指导我们的搜索过程来探索不同类型的网络邻居。此外与分别适合结构等价和同质性的极端采样范式 BFS 和 DFS 不同我们的随机游走应该适应这样一个事实这些等价概念不是竞争性的或排他性的并且现实世界的网络通常表现出两者的混合。
我们使用两个参数 p p p 和 q q q 来定义二阶随机游走这两个参数 p p p 和 q q q 引导游走考虑一个刚刚穿过边 ( t , v ) (t, v) (t,v) 且现在位于节点 v v v 的随机游走图 2。现在步行需要决定下一步以便评估从 v v v 开始的边 ( v , x ) (v, x) (v,x) 上的转移概率 π v x π_{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_{pq}(t,x)\begin{cases}\frac{1}{p}\text{if}d_{tx}0\\1\text{if}d_{tx}1\\\frac{1}{q}\text{if}d_{tx}2\end{cases} αpq(t,x)⎩ ⎨ ⎧p11q1ifdtx0ifdtx1ifdtx2 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 之间进行插值从而反映不同节点等价概念的亲和力。
返回参数 p p p。 参数 p p p 控制立即重新访问步行中的节点的可能性。将其设置为较高的值 ( m a x ( q , 1 ) max(q, 1) max(q,1)) 可确保我们不太可能在接下来的两个步骤中对已访问过的节点进行采样除非遍历中的下一个节点没有其他邻居。该策略鼓励适度探索并避免采样中的 2 跳冗余。另一方面如果 p 较低 ( m i n ( q , 1 ) min(q, 1) min(q,1))则会导致步行回溯一步图 2这将使步行保持“本地”靠近起始节点 u u u。 输入输出参数, q q q。 参数 q q q 允许搜索区分“向内”和“向外”节点。回到图 2如果 q 1 q 1 q1则随机游走偏向靠近节点 t t t 的节点。这样的游走获得了相对于游走中的起始节点的底层图的局部视图并在我们的样本由小局部区域内的节点组成的意义上近似 BFS 行为。
相反如果 q 1 q 1 q1则步行更倾向于访问距离节点 t t t 较远的节点。这种行为反映了DFS鼓励向外探索的精神。然而这里的一个本质区别是我们在随机游走框架内实现了类似 DFS 的探索。因此采样节点与给定源节点 u u u 的距离并不是严格增加的但反过来我们受益于易于处理的预处理和随机游走的卓越采样效率。请注意通过将 π v , x π_{v,x} πv,x 设置为游走 t t t 中前一个节点的函数随机游走是二阶马尔可夫。
随机游走的好处。 与纯 BFS/DFS 方法相比随机游走有几个好处。就空间和时间要求而言随机游走在计算上是高效的。存储图中每个节点的直接邻居的空间复杂度为 O ( ∣ E ∣ ) O(|E|) O(∣E∣)。对于二阶随机游走存储每个节点的邻居之间的互连是有帮助的这会导致 O ( a 2 ∣ V ∣ ) O(a^2|V|) O(a2∣V∣) 的空间复杂度其中 a a a 是图的平均度对于现实世界的网络来说通常很小。与经典的基于搜索的采样策略相比随机游走的另一个关键优势是其时间复杂度。特别是通过在样本生成过程中施加图连接性随机游走提供了一种方便的机制可以通过在不同源节点之间重用样本来提高有效采样率。
通过模拟长度 l k l k lk 的随机游走由于随机游走的马尔可夫性质我们可以立即为 l − k l − k l−k 个节点生成 k k k 个样本。因此每个样本的有效复杂度为 O ( l k ( l − k ) ) O(\frac l{k(l-k)}) O(k(l−k)l)。例如在图 1 中我们对长度 l 6 l 6 l6 的随机游走 { 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 ( s 4 ) { s 5 , s 6 , s 8 } N_{S}(u)\{s_{4},s_{5},s_{6}\}, N_{S}(s_{4}) \{s_{5},s_{6},s_{8}\} NS(u){s4,s5,s6},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}。请注意样本重复使用可能会在整个过程中引入一些偏差。但我们发现它大大提高了效率。 3.2.3 The node2vec algorithm
算法 1 中给出了 node2vec 的伪代码。在任何随机游走中由于起始节点 u u u 的选择都会存在隐式偏差。由于我们学习所有节点的表示因此我们通过从每个节点开始模拟 r r r 个固定长度 l l l 的随机游走来抵消这种偏差。在行走的每一步采样都是基于转移概率 π v x π_{vx} πvx 进行的。可以预先计算二阶马尔可夫链的转移概率 π v x π_{vx} πvx因此可以使用别名采样在 O ( 1 ) O(1) O(1) 时间内有效地在模拟随机游走时完成节点采样。 node2vec 的三个阶段即计算转移概率的预处理、随机游走模拟和使用 SGD 的优化是按顺序执行的。每个阶段都是可并行的并异步执行有助于提高node2vec的整体可扩展性。
node2vec可以在http://snap.stanford.edu/node2vec获取。 3.3 Learning edge features 学习边缘特征
node2vec 算法提供了一种半监督方法来学习网络中节点的丰富特征表示。然而我们通常对涉及节点对而不是单个节点的预测任务感兴趣。例如在链接预测中我们预测网络中两个节点之间是否存在链接。由于我们的随机游走自然地基于底层网络中节点之间的连接结构因此我们使用对各个节点的特征表示的引导方法将它们扩展到节点对。
给定两个节点 u u u 和 v v v我们在相应的特征向量 f ( u ) f(u) f(u) 和 f ( v ) f(v) f(v) 上定义一个二元运算符 o \text{o} o以生成表示 g ( u , v ) g(u, v) g(u,v)使得 g : V × V → R d ′ g: V\times V \to \mathbb{R}^{d^{\prime}} g:V×V→Rd′ 其中 d ′ d\prime d′ 是 ( u , v ) (u, v) (u,v) 对的表示大小。我们希望我们的运算符通常为任何一对节点定义即使该对之间不存在边因为这样做使得表示对于链接预测有用其中我们的测试集包含真边和假边即不存在。我们考虑了算子 o \text{o} o 的几种选择使得 d ′ d d\prime d d′d如表 1 所示。 4. EXPERIMENTS
公式2中的目标独立于任何下游任务node2vec 提供的探索灵活性将学习到的特征表示提供给下面讨论的各种网络分析设置。
4.1 Case Study: Les Misérables network 案例研究《悲惨世界》网络
在第 3.1 节中我们观察到 BFS 和 DFS 策略代表了基于同质性即网络社区和结构等效即节点的结构角色原则的嵌入节点范围的极端。我们现在的目标是凭经验证明这一事实并证明 node2vec 实际上可以发现遵循这两个原则的嵌入。
我们使用一个网络其中节点对应于小说《悲惨世界》中的角色边连接共同出现的角色。该网络有 77 个节点和 254 个边。我们设置 d 16 d 16 d16 并运行 node2vec 来学习网络中每个节点的特征表示。特征表示使用 kmeans 进行聚类。然后我们在二维中可视化原始网络节点现在根据其集群分配颜色。
图 3上显示了当我们设置 p 1 , q 0.5 p 1, q 0.5 p1,q0.5 时的示例。请注意网络区域即网络社区如何使用相同的颜色进行着色。在这种情况下node2vec 发现在小说的主要次要情节中经常相互互动的人物集群/社区。由于字符之间的边缘是基于共现性的因此我们可以得出结论这种表征与同质性密切相关。 为了发现哪些节点具有相同的结构角色我们使用相同的网络但设置 p 1 , q 2 p 1, q 2 p1,q2使用 node2vec 获取节点特征然后根据获得的特征对节点进行聚类。这里node2vec 获得了节点到簇的互补分配使得颜色对应于结构等价如图 3底部所示。例如node2vec 将蓝色节点紧密地嵌入在一起。这些节点代表充当小说不同子情节之间桥梁的角色。同样黄色节点主要代表处于外围且交互有限的角色。人们可以为这些节点簇分配替代的语义解释但关键的一点是node2vec 并不依赖于特定的等价概念。正如我们通过实验表明的那样这些等价概念通常出现在大多数现实世界的网络中并对预测任务的学习表示的性能产生重大影响。
4.2 Experimental setup
我们的实验评估了通过 node2vec 在标准监督学习任务上获得的特征表示节点的多标签分类和边缘的链接预测。对于这两个任务我们根据以下特征学习算法评估了 node2vec 的性能
谱聚类(Spectral clustering)这是一种矩阵分解方法其中我们将图 G 的归一化拉普拉斯矩阵的顶部特征向量作为节点的特征向量表示。DeepWalk该方法通过模拟均匀随机游走来学习 d d d 维特征表示。DeepWalk中的采样策略可以看作是 p 1 p 1 p1且 q 1 q 1 q1的node2vec的特例。LINE该方法在两个单独的阶段学习 d d d 维特征表示。在第一阶段它通过对节点的直接邻居进行 BFS 式模拟来学习 d / 2 d/2 d/2 维。在第二阶段它通过严格在距源节点 2 跳距离处采样节点来学习下一个 d / 2 d/2 d/2 维度。
我们排除了其他已被证明不如 DeepWalk的矩阵分解方法。我们还排除了最近的方法 GraRep该方法概括了 LINE 以合并来自超过 2 跳的网络邻居的信息但无法有效地扩展到大型网络。
与之前用于评估基于采样的特征学习算法的设置相比我们为每种方法生成相同数量的样本然后评估在预测任务中获得的特征的质量。在此过程中我们纯粹因为实现语言 (C/C/Python) 而观察到性能提升因为它对于算法来说是次要的。因此在采样阶段设置 DeepWalk、LINE 和 node2vec 的参数以便它们在运行时生成相同数量的样本。例如如果 K \mathcal K K是总体采样预算则node2vec参数满足 K r ⋅ l ⋅ ∣ V ∣ \mathcal{K}r\cdot l\cdot|V| Kr⋅l⋅∣V∣。在优化阶段所有这些基准测试都使用 SGD 进行优化但我们纠正了两个关键差异。首先DeepWalk 使用分层采样来近似 softmax 概率其目标类似于 node2vec 使用的目标。然而与负采样相比分层 softmax 效率较低。因此在保持其他一切不变的情况下我们在 DeepWalk 中切换到负采样这也是 node2vec 和 LINE 中事实上的近似。其次node2vec 和 DeepWalk 都有一个用于优化的上下文邻域节点数量的参数数量越大需要的优化轮次就越多。对于 LINE此参数设置为 unity但由于 LINE 比其他方法更快地完成一个 epoch因此我们让它运行 k k k 个 epoch。
node2vec 使用的参数设置与 DeepWalk 和 LINE 使用的典型值一致。具体来说我们设置 d 128 , r 10 , l 80 , k 10 d 128, r 10, l 80, k 10 d128,r10,l80,k10并且优化针对单个 epoch 运行。我们对 10 个随机种子初始化重复实验我们的结果具有统计显着性 p p p 值小于 0.01。最好的输入输出和返回超参数是通过对 10% 标记数据进行 10 倍交叉验证来学习的,对 p , q ∈ { 0.25 , 0.50 , 1 , 2 , 4 } p, q \in \{0.25, 0.50, 1, 2, 4\} p,q∈{0.25,0.50,1,2,4} 进行网格搜索。
4.3 Multi-label classification
在多标签分类设置中每个节点都被分配有限集 L \mathcal L L 中的一个或多个标签。在训练阶段我们观察节点的某一部分及其所有标签。任务是预测剩余节点的标签。这是一项具有挑战性的任务尤其是当 L \mathcal L L 很大时。我们利用以下数据集
BlogCatalog这是 BlogCatalog 网站上列出的博客作者的社交关系网络。这些标签代表通过博主提供的元数据推断出的博主兴趣。该网络有 10312个节点、333983个边和 39 个不同的标签。Protein-Protein Interactions (PPI)我们使用智人 PPI 网络的子图。子图对应于由节点诱导的图我们可以从标志基因集中获得标签并代表生物状态。该网络有 3890 个节点、76584 个边和 50 个不同的标签。Wikipedia这是出现在维基百科转储的前百万字节中的单词共现网络。这些标签代表使用斯坦福 POS-Tagger 推断的词性 (POS) 标签。该网络有 4777 个节点、184812 个边和 40 个不同的标签。
所有这些网络都表现出同质性和结构等价性的合理组合。例如我们期望博客作者的社交网络表现出强烈的基于同质性的关系然而也可能存在一些“熟悉的陌生人”即不互动但有共同兴趣的博主因此在结构上是等效的节点。蛋白质-蛋白质相互作用网络中蛋白质的生物学状态也表现出两种类型的等价性。例如当蛋白质执行与邻近蛋白质互补的功能时它们表现出结构等效性而在其他时候它们基于同质性进行组织以协助邻近蛋白质执行相似的功能。单词共现网络相当密集因为维基百科语料库中 2 长度窗口中同时出现的单词之间存在边缘。因此具有相同词性标签的单词并不难找到同质性很高。同时由于句法语法模式例如限定词后面的名词、名词后面的标点符号等我们期望词性标签中存在一些结构等效性。
实验结果。 节点特征表示被输入到具有 L 2 L2 L2 正则化的一对一逻辑回归分类器。训练数据和测试数据在 10 个随机实例中平均分配。我们使用 M a c r o − F 1 Macro-F_1 Macro−F1 分数来比较表 2 中的性能相对性能增益超过了最接近的基准。 M i c r o − F 1 Micro-F_1 Micro−F1 和准确度的趋势相似但未显示。 从结果中我们很明显可以看到探索邻域时所增加的灵活性如何使 node2vec 的性能优于其他基准算法。在BlogCatalog中我们可以通过将参数 p p p 和 q q q 设置为较低值来发现同质性和结构等价性的正确组合使我们在 M a c r o − F 1 Macro-F_1 Macro−F1 分数上比 DeepWalk 提高 22.3%比 LINE 提高 229.2%。LINE 显示出比预期更差的性能这可以通过其无法重用样本来解释而使用随机游走方法可以轻松完成这一壮举。即使在我们的其他两个网络中我们存在等价物的混合node2vec 的半监督性质也可以帮助我们推断特征学习所需的适当探索程度。在 PPI 网络的情况下最佳探索策略 p 4 , q 1 p 4, q 1 p4,q1与 DeepWalk 的均匀 p 1 , q 1 p 1,q 1 p1,q1探索几乎没有区别通过避免冗余我们仅比 DeepWalk 略有优势,在已经访问过的节点中 p p p 值很高但在 M a c r o − F 1 Macro-F_1 Macro−F1 分数方面比 LINE 提高了 23.8%令人信服。然而一般来说均匀随机游走可能比node2vec学习的探索策略差很多。正如我们在维基百科单词共现网络中所看到的均匀行走无法引导搜索过程走向最佳样本因此我们比 DeepWalk 获得了 21.8% 的增益比 LINE 获得了 33.2% 的增益。
为了进行更细粒度的分析我们还比较了将训练测试分割从 10% 更改为 90% 时的性能同时像以前一样在 10% 的数据上学习参数 p p p 和 q q q。为简洁起见我们在图 4 中以图形方式总结了 M i c r o − F 1 Micro-F_1 Micro−F1 和 M a c r o − F 1 Macro-F_1 Macro−F1 分数的结果。在这里我们进行了类似的观察。所有方法都显着优于 Spectral 聚类DeepWalk 优于 LINEnode2vec 始终优于 LINE并在跨领域实现了较 DeepWalk 的巨大改进。例如我们在 BlogCatalog 上以 70% 标记数据实现了相对 DeepWalk 的最大改进达到 26.7%。在最坏的情况下搜索阶段对学习到的表示几乎没有影响在这种情况下node2vec 相当于 DeepWalk。同样与 LINE 相比这些改进更加引人注目除了 BlogCatalog 上的大幅提升超过 200%之外我们还观察到 PPI 等其他数据集上的大幅改进高达 41.1%而仅使用 10% 标记数据进行训练。 4.4 Parameter sensitivity 参数灵敏度
node2vec 算法涉及许多参数在图 5a 中我们使用标记数据和未标记数据之间的 50-50 分割来检查参数的不同选择如何影响 BlogCatalog 数据集上的 node2vec 性能。除所测试的参数外其他参数均采用默认值。 p p p 和 q q q 的默认值设置为 unity。 我们将 M a c r o − F 1 Macro-F_1 Macro−F1 分数测量为参数 p p p 和 q q q 的函数。随着输入输出参数 p p p 和返回参数 q q q 的减小node2vec 的性能会提高。这种性能的提高可以基于我们期望在 BlogCatalog 中看到的同质和结构等效性。虽然低 q q q 鼓励向外探索但它通过低 p p p 来平衡确保行走不会离起始节点太远。
我们还研究了特征数量 d d d 和节点的邻域参数行走次数 r r r、行走长度 l l l 和邻域大小 k k k如何影响性能。我们观察到一旦表示的维度达到 100 左右性能就会趋于饱和。同样我们观察到增加每个源的行走次数和长度可以提高性能这并不奇怪因为我们有更大的总体采样预算 K \mathcal K K 来学习表示。这两个参数对该方法的性能都有相对较大的影响。有趣的是上下文大小 k k k 也提高了性能但代价是增加了优化时间。然而在这种情况下性能差异并不那么大。
4.5 Perturbation Analysis 扰动分析
对于许多现实世界的网络我们无法获得有关网络结构的准确信息。我们进行了一项扰动研究分析了与 BlogCatalog 网络中的边缘结构相关的两个不完美信息场景下的 node2vec 的性能。在第一种情况下我们将性能作为缺失边缘比例的函数相对于整个网络来衡量。缺失的边是随机选择的但受到网络中连接组件数量保持固定的约束。正如我们在图 5b顶部中看到的随着缺失边缘比例的增加 M a c r o − F 1 Macro-F_1 Macro−F1 分数的下降大致呈线性且斜率较小。在图随时间演变的情况下例如引文网络或者网络构建成本高昂的情况下例如生物网络网络中缺失边的鲁棒性尤其重要。
在第二个扰动设置中我们在网络中随机选择的节点对之间存在噪声边缘。如图5b下所示与缺失边的设置相比node2vec的性能最初下降得稍快但随着时间的推移 M a c r o − F 1 Macro-F_1 Macro−F1分数下降的速度逐渐减慢。同样node2vec 对错误边缘的鲁棒性在多种情况下非常有用例如用于构建网络的测量有噪声的传感器网络。
4.6 Scalability 可扩展性
为了测试可扩展性我们使用 node2vec 学习节点表示Erdos-Renyi 图的默认参数值从 100 个节点增加到 1000000 个节点平均度数恒定为 10。在图 6 中我们凭经验观察到node2vec 随着数量的增加呈线性缩放。在不到四小时内生成一百万个节点的表示的节点数。采样过程包括计算行走的转移概率小到可以忽略不计的预处理和随机行走的模拟。使用负采样和异步 SGD使优化阶段变得高效。 先前工作中的许多想法可以为提高采样过程的计算效率提供有用的指导。我们展示了 DeepWalk中也使用的随机游走如何允许将采样节点重新用作游走中出现的不同源节点的邻域。别名采样允许我们的游走推广到加权网络几乎不需要预处理。尽管我们可以根据基础任务和领域自由设置搜索参数无需额外成本但学习搜索参数的最佳设置会增加开销。然而正如我们的实验所证实的这种开销是最小的因为 node2vec 是半监督的因此可以用很少的标记数据有效地学习这些参数。
4.7 Link prediction 链路预测
在链接预测中我们得到一个删除了一定比例边缘的网络我们希望预测这些缺失的边缘。我们生成边的标记数据集如下为了获得正例我们从网络中删除随机选择的50的边同时确保删除边后获得的残差网络是连接的为了生成负例我们随机采样,网络中没有边连接的相同数量的节点对。
由于之前没有任何特征学习算法用于链接预测因此我们另外根据一些流行的启发式分数评估了 node2vec这些分数在链接预测中取得了良好的性能。我们考虑的分数是根据构成该对的节点的邻域集来定义的参见表 3。我们在以下数据集上测试我们的基准
Facebook在Facebook网络中节点代表用户边代表任意两个用户之间的好友关系。该网络有 4039 个节点和 88234 个边。Protein-Protein Interactions(PPI)在智人的 PPI 网络中节点代表蛋白质边表示一对蛋白质之间的生物相互作用。该网络有 19706 个节点和 390633 个边。arXiv ASTRO-PH这是一个由提交到电子打印 arXiv 的论文生成的协作网络其中节点代表科学家如果两位科学家在论文中进行过合作则他们之间存在一条边。该网络有 18722 个节点和 198110 个边。 实验结果。我们在表 4 中总结了链路预测的结果。为了便于演示省略了每个 node2vec 条目的最佳 p p p 和 q q q 参数设置。我们可以从结果中得出的一般观察结果是节点对的学习特征表示显着优于启发式基准分数其中 node2vec 在 arXiv 数据集上实现了最佳 AUC 改进比最佳性能基线提高了 12.6%(Adamic-Adar)。 在特征学习算法中node2vec 在所有网络中都优于 DeepWalk 和 LINE对于每种算法的二元运算符的最佳选择AUC 分数分别提高了 3.8% 和 6.5%。当我们单独查看运算符时(表 1)node2vec 的性能优于 DeepWalk 和 LINE除非在涉及加权 L1 和加权 L2 运算符的情况下 LINE 表现更好。总体而言Hadamard 算子与 node2vec 一起使用时高度稳定并且在所有网络中平均提供最佳性能。 5. DISCUSSION AND CONCLUSION
在本文中我们研究了网络中的特征学习作为基于搜索的优化问题。这种观点给我们带来了多种优势。它可以解释基于探索-利用权衡的经典搜索策略。此外当应用于预测任务时它为学习到的表示提供了一定程度的可解释性。例如我们观察到 BFS 只能探索有限的邻域。这使得 BFS 适合表征网络中依赖于节点的直接局部结构的结构等价性。另一方面DFS 可以自由地探索网络邻居这对于以高方差为代价发现同质社区非常重要。
DeepWalk 和 LINE 都可以看作是网络上的刚性搜索策略。 DeepWalk 提出使用均匀随机游走进行搜索。这种策略的明显局限性是它使我们无法控制所探索的社区。 LINE 主要提出了一种广度优先策略对节点进行采样并仅在 1 跳和 2 跳邻居上独立优化似然度。这种探索的效果更容易表征但它具有限制性并且在探索更深度的节点时不提供灵活性。相比之下node2vec 中的搜索策略是灵活可控的通过参数 p p p 和 q q q 探索网络邻域。虽然这些搜索参数具有直观的解释但当我们可以直接从数据中学习它们时我们会在复杂网络上获得最佳结果。从实际的角度来看node2vec 具有可扩展性并且对扰动具有鲁棒性。
我们展示了节点嵌入对链接预测的扩展如何优于专门为此任务设计的流行启发式分数。我们的方法允许使用表 1 中列出的其他二元运算符。作为未来的工作我们希望探索 Hadamard 运算符相对于其他运算符成功的原因并根据搜索参数为边建立可解释的等价概念。 Node2vec 的未来扩展可能涉及具有特殊结构的网络例如异构信息网络、具有节点和边的显式域特征的网络以及带符号边网络。连续特征表示是许多深度学习算法的支柱使用 node2vec 表示作为图上端到端深度学习的构建块会很有趣。
论文链接
https://arxiv.org/pdf/1607.00653.pdf
