盐城网站平台建设,泉州网站建设公司首选公司,漏惹网站做,广东哪有做网赌网站图神经网络实战#xff08;4#xff09;——基于Node2Vec改进嵌入质量 0. 前言1. Node2Vec 架构1.2 定义邻居1.2 在随机游走中引入偏向性1.3 实现有偏随机游走 2. 实现 Node2Vec小结系列链接 0. 前言
Node2Vec 是一种基于 DeepWalk 的架构#xff0c;DeepWalk 主要由随机游… 图神经网络实战4——基于Node2Vec改进嵌入质量 0. 前言1. Node2Vec 架构1.2 定义邻居1.2 在随机游走中引入偏向性1.3 实现有偏随机游走 2. 实现 Node2Vec小结系列链接 0. 前言
Node2Vec 是一种基于 DeepWalk 的架构DeepWalk 主要由随机游走和 Word2Vec 两个组件构成Node2Vec 通过改进随机游走的生成方式改进嵌入质量。 在本节中我们将学习这些改进以及如何为给定的图找到最佳参数实现 Node2Vec 架构并将其与在 Zacharys Karate Club 数据集上使用的 DeepWalk 进行比较以理解两种架构之间的差异。
1. Node2Vec 架构
Node2Vec 由 Grover 和 Leskovec 于 2016 年提出它保留了 DeepWalk 的两个主要组件随机游走和 Word2Vec。不同之处在于 Node2Vec 中的随机游走不是使用均匀分布生成节点序列而是进行了有偏处理。接下来我们将了解为什么这些有偏随机游走表现更好以及如何实现它们
定义邻居在随机游走中引入偏向性
1.2 定义邻居
Node2Vec 引入的关键概念是灵活的邻居概念。直观地说我们认为邻居是与初始节点接近的节点但在图中应该如何定义“接近”呢以下图为例 我们希望探索节点 A 相邻的三个节点该探索过程也称为采样策略 (sampling strategy)
一种解是考虑在连接关系方面最接近的三个节点。在这种情况下A 的邻居为 N ( A ) { B , C , D } N(A) \{B,C,D\} N(A){B,C,D}另一种采用策略是首先选择与前一个节点不相邻的节点。在这种情况下A 的邻居为 N ( A ) { D , E , F } N(A) \{D, E, F\} N(A){D,E,F}
换句话说在第一种情况下需要执行广度优先搜索 (Breadth-First Search, BFS)而在第二种情况下需要执行深度优先搜索 (Depth-First Search, DFS)。BFS 侧重于节点周围的局部网络而 DFS 则建立了更宏观的图视图。 考虑到我们对邻居的直观定义首先会想到舍弃 DFS。然而Node2Vec 则认为这是种错误认知其认为每种方法都捕捉到了网络的不同但有价值的表示。 将这些算法与以下两种网络属性联系起来
结构等价性 (Structural equivalence)这意味着如果节点共享许多相同的邻居则它们在结构上是等效的。因此如果它们共享许多邻居则它们的结构等价性就更高同质性 (Homophily)表示相似的节点更有可能相互连接
Node2Vec 认为 BFS 是突出结构等效性的理想策略因为该策略仅查看相邻节点。在这些随机游走序列中节点经常重复出现并保持彼此接近。而 DFS 则通过创建远距离节点序列来强调非同质性。这些随机游走序列会采样距离源节点很远的节点因此降低了代表性。因此我们需要在这两种属性之间进行权衡同质性可能更有助于理解某些图反之亦然。 通常认为结合同质性和结构等价性的图是理想的解决方案因此我们希望使用这两种采样策略来创建数据集。接下来我们使用它们来生成随机游走序列。
1.2 在随机游走中引入偏向性
我们已经知道随机游走是在图中随机选择的节点序列通过使用一个给定起点(也可以是随机的)和一个预定义的长度创建。在这些图中经常出现在一起的节点就像句子中经常出现在一起的单词一样根据同质性假设它们具有相似的含义因此也具有相似的表示。
在 Node2Vec 中我们的目标是将这些随机游走的随机性偏向以下两者之一
提升与前一个节点没有连接的节点(类似于 DFS)提升与前一个节点相近的节点(类似于 BFS)
以下图为例当前节点为 j j j前一节点为 i i i特征节点为 k k k。从节点 j j j 到节点 k k k 的非归一化转移概率 π j k \pi_{jk} πjk该概率可以分解为 π j k a ( i , k ) ⋅ w j k \pi_jk a( i, k)\cdot w_{jk} πjka(i,k)⋅wjk, 其中 a ( i , k ) a(i , k) a(i,k) 是节点 j j j 和 k k k 之间的搜索偏置 (search bias) w j k w_{jk} wjk 是 j j j 到 k k k 的边的权重。 在 DeepWalk 中对于任意一对节点 a a a 和 b b b它们之间的边权重 a ( a , b ) 1 a(a,b)1 a(a,b)1。在 Node2Vec 中 a ( a , b ) a( a, b) a(a,b) 的值是根据节点间的距离和两个附加参数定义的回退参数 p 和进出参数 q分别用于近似 DFS 和 BFS。 a ( a , b ) a(a, b) a(a,b) 值的定义如下 a ( a , b ) { 1 p d a b 0 1 d a b 1 1 q d a b 2 a(a, b)\begin{cases} \frac 1 p d_{ab}0\\ 1 d_{ab}1\\ \frac 1 q d_{ab}2\\ \end{cases} a(a,b)⎩ ⎨ ⎧p11q1dab0dab1dab2 其中 d a b d_{ab} dab 是节点 a a a 和 b b b 之间的最短路径距离可以按如下方式更新上图中的非归一化转移概率 在非归一化转移概率中
回到前一个节点 i i i 的概率由参数 p p p 控制参数 p p p 越大随机游走就会越趋向于探索新的节点而不是重复相同的节点看起来就像 DFS前往 k 1 k_1 k1 的非归一化概率为 1因为该节点是前一个节点 i i i 的直接邻居到达节点 k 2 k_2 k2 的概率由参数 q q q 控制参数 q q q 越大随机游走就越集中在与前一个节点相近的节点上看起来就像 BFS
为了理解这些概念最好的办法就是实际实现这一架构并对参数进行调整。接下来我们在 Zachary’s Karate Club 数据集上实现此架构。需要注意的是该图是一个非加权网络因此转移概率仅由搜索偏置决定。
1.3 实现有偏随机游走
首先需要创建一个函数根据前一个节点、当前节点以及参数 p p p 和 q q q 随机选择图中的下一个节点。
(1) 导入所需的库并创建图
import networkx as nx
import matplotlib.pyplot as plt
import numpy as np
# Create graph
G nx.erdos_renyi_graph(10, 0.3, seed1, directedFalse)# Plot graph
plt.axis(off)
nx.draw_networkx(G, posnx.spring_layout(G, seed0))
plt.show()(2) 用参数列表定义 next_node() 函数
def next_node(previous, current, p, q):(3) 检索当前节点的邻居节点列表并初始化 alpha 值列表 alphas []# Get the neighboring nodesneighbors list(G.neighbors(current))(4) 对于每个邻居都要计算出相应的 alpha 值如果该邻居是前一个节点则为 1 p \frac1 p p1如果该邻居与前一个节点相连则为 1 1 1否则为 1 q \frac 1 q q1 # Calculate the appropriate alpha value for each neighborfor neighbor in neighbors:# Distance 0: probability to return to the previous nodeif neighbor previous:alpha 1/p# Distance 1: probability of visiting a local nodeelif G.has_edge(neighbor, previous):alpha 1# Distance 2: probability to explore an unknown nodeelse:alpha 1/qalphas.append(alpha)(5) 对这些值进行归一化处理得出概率 probs [alpha / sum(alphas) for alpha in alphas](6) 根据上一步计算出的转换概率使用 np.random.choice() 随机选择下一个节点并返回 next np.random.choice(neighbors, size1, pprobs)[0]return next在测试该函数之前需要编写整个随机游走的代码。随机游走的代码与我们在 DeepWalk 一节中实现的代码类似。不同的是下一个节点由 next_node() 函数选择该函数需要额外的参数p 和 q以及上一个节点和当前节点。这些节点可以通过查看添加到 walk 变量中的最后两个元素轻松获得出于兼容性考虑函数返回字符串而不是整数。 改进后的 random_walk() 函数如下
def random_walk(start, length, p, q):walk [start]for i in range(length):current walk[-1]previous walk[-2] if len(walk) 1 else Nonenext next_node(previous, current, p, q)walk.append(next)return walk调用 random_walk()函数生成长度为 5、p1和q1 的随机游走序列
print(random_walk(0, 8, p1, q1))函数返回序列如下所示
[0, 9, 1, 0, 1, 0, 4, 3, 6]该序列是随机的因为每个相邻节点都有相同的转换概率。
接下来令算法偏向于回到前一个节点即 q10
print(random_walk(0, 8, p1, q10))函数返回序列如下所示
[0, 9, 1, 0, 1, 9, 0, 1, 2]可以看到随机游走探索了图中更多的节点。接下来使用 p10 调用函数由于其概率很低所以不会返回到之前的节点
print(random_walk(0, 8, p10, q1))函数返回序列如下所示
[0, 9, 4, 6, 5, 4, 9, 0, 1]接下来我们在实际应用中使用这些属性并将其与 DeepWalk 进行比较。
2. 实现 Node2Vec
现在我们已经实现了生成有偏随机游走的函数Node2Vec 的实现与 DeepWalk 相似我们可以重复使用相同的代码并使用 p 1 和 q 1 将 DeepWalk 作为 Node2Vec 的一个特例我们重用 Zachary’s Karate Club 数据集实现 Node2Vec 架构。 我们的目标是将俱乐部的每位成员归类为正确的类别 (“Mr. Hi” 和 “Officer”)使用 Node2Vec 输出的节点嵌入作为机器学习分类器(本节中使用随机森林)的输入。
(1) 首先在 shell 中使用 pip 命令安装 gensim 库以使用 Word2Vec
pip install gensim(2) 导入所需的库
from gensim.models.word2vec import Word2Vec
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score(3) 加载 Zachary’s Karate Club 数据集
G nx.karate_club_graph()(4) 将节点标签转换为数值 (0 和 1)
# Process labels (Mr. Hi 0, Officer 1)
labels []
for node in G.nodes:label G.nodes[node][club]labels.append(1 if label Officer else 0)(5) 指定参数 p3、q2 调用 random_walk() 函数为图中的每个节点生成 80 个随机游走列表
walks []
for node in G.nodes:for _ in range(80):walks.append(random_walk(node, 10, 3, 2))(6) 使用分层 softmax 函数创建一个 Word2Vec (skip-gram 模型)实例
node2vec Word2Vec(walks,hs1, # Hierarchical softmaxsg1, # Skip-gramvector_size100,window10,workers2,min_count1)(7) 在生成的序列上对 skip-gram 模型进行 30 次训练
node2vec.train(walks, total_examplesnode2vec.corpus_count, epochs30, report_delay1)(8) 创建掩码训练并测试分类器
train_mask [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24]
test_mask [0, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33]
labels np.array(labels)(9) 在训练数据上训练随机森林分类器
clf RandomForestClassifier(random_state0)
clf.fit(node2vec.wv[train_mask], labels[train_mask])(10) 在测试数据集上使用准确率作为评估模型性能的度量标准
y_pred clf.predict(node2vec.wv[test_mask])
acc accuracy_score(y_pred, labels[test_mask])
print(fNode2Vec accuracy {acc*100:.2f}%)
# Node2Vec accuracy 95.45%要实现 DeepWalk我们可以在 p 1 和 q 1 的情况下重复完全相同的过程。但是为了进行公平的比较我们不能使用单次实验的准确率因为这其中涉及很多随机过程可能会出现从最差的模型中得到更好的结果。 为了限制结果的随机性我们可以重复此过程 100 次然后取平均值。这样的结果会稳定得多也可以使用标准差 (np.std()) 来测量准确率的变化。 我们已经知道Zachary’s Karate Club 是一个具有同质性的网络。这种特性通过 DFS 得到了强调而增加参数 p 可以鼓励 DFS。假如这一说法和 DFS 与同质性之间的联系是正确的那么 p 值越大就能够获得更好的结果。 对参数 p 和q在 1 到 7 之间重复进行同样的实验。在实际的机器学习项目中我们会使用验证数据进行参数搜索在本例中我们将模型直接作为最终应用因此直接使用测试数据。结果总结如下表所示 从上表中可以看出
DeepWalk(p 1q 1) 的性能比表中其他 p 和 q 组合都要差。这证明了有偏随机游走对于该数据集而言的有效性但情况并非总是如此在其他数据集上无偏随机游走也可能表现得更好p 值越高性能越好这也与我们的假设完全吻合。在社交网络中通常可以将随机游走偏向于同质性。
我们可以通过调整参数观察使用不同参数时的结果。例如我们可以探索 p 值较高 ( 7) 时的情况或者 p 值和 q 值较低(介于 0 和 1 之间)时的情况。
小结
在本节中我们了解了 Node2Vec这是一种基于 Word2Vec 的架构。我们实现了有偏随机游走并解释了其参数与两个网络属性(同质性和结构等价性)之间的联系。通过比较 Node2Vec 与 DeepWalk 在 Zacharys Karate Club 数据集上的性能表现验证了有偏随机游走的有效性。
系列链接
图神经网络实战1——图神经网络(Graph Neural Networks, GNN)基础 图神经网络实战2——图论基础 图神经网络实战3——基于DeepWalk创建节点表示
