0. 前言

Node2Vec 是一种基于 DeepWalk 的架构，DeepWalk 主要由随机游走和 Word2Vec 两个组件构成，Node2Vec 通过改进随机游走的生成方式改进嵌入质量。
在本节中，我们将学习这些改进以及如何为给定的图找到最佳参数，实现 Node2Vec 架构，并将其与在 Zachary's 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$，前一节点为 $i$，特征节点为 $k$。从节点 $j$ 到节点 $k$ 的非归一化转移概率 ${\pi }_{jk}$，该概率可以分解为 ${\pi }_{j}k=a(i,k)\cdot w_{jk}$, 其中 $a(i,k)$ 是节点 $j$ 和 $k$ 之间的搜索偏置 (search bias)，$w_{jk}$ 是 $j$ 到 $k$ 的边的权重。

在 DeepWalk 中，对于任意一对节点 $a$ 和 $b$，它们之间的边权重 $a(a,b)=1$。在 Node2Vec 中，$a(a,b)$ 的值是根据节点间的距离和两个附加参数定义的：回退参数 p 和进出参数 q，分别用于近似 DFS 和 BFS。$a(a,b)$ 值的定义如下：
$$a(a,b)=\{\begin{array}{ll}\frac{1}{p}& d_{ab}=0\\ 1& d_{ab}=1\\ \frac{1}{q}& d_{ab}=2\end{array}$$
其中，$d_{ab}$ 是节点 $a$ 和 $b$ 之间的最短路径距离，可以按如下方式更新上图中的非归一化转移概率：

在非归一化转移概率中：

• 回到前一个节点 $i$ 的概率由参数 $p$ 控制，参数 $p$ 越大，随机游走就会越趋向于探索新的节点，而不是重复相同的节点，看起来就像 DFS
• 前往 $k_1$ 的非归一化概率为 1，因为该节点是前一个节点 $i$ 的直接邻居
• 到达节点 $k_2$ 的概率由参数 $q$ 控制，参数 $q$ 越大，随机游走就越集中在与前一个节点相近的节点上，看起来就像 BFS

为了理解这些概念，最好的办法就是实际实现这一架构，并对参数进行调整。接下来，我们在 Zachary’s Karate Club 数据集上实现此架构。需要注意的是，该图是一个非加权网络，因此转移概率仅由搜索偏置决定。

1.3 实现有偏随机游走

首先，需要创建一个函数，根据前一个节点、当前节点以及参数 $p$ 和 $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, seed=1, directed=False)# Plot graph
plt.axis('off')
nx.draw_networkx(G, pos=nx.spring_layout(G, seed=0))
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 值：如果该邻居是前一个节点，则为 $\frac{1}{p}$；如果该邻居与前一个节点相连，则为 $1$；否则为 $\frac{1}{q}$：

    # 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, size=1, p=probs)[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、p=1和q=1` 的随机游走序列：

print(random_walk(0, 8, p=1, q=1))

函数返回序列如下所示：

[0, 9, 1, 0, 1, 0, 4, 3, 6]

该序列是随机的，因为每个相邻节点都有相同的转换概率。

接下来，令算法偏向于回到前一个节点，即 q=10：

print(random_walk(0, 8, p=1, q=10))

函数返回序列如下所示：

[0, 9, 1, 0, 1, 9, 0, 1, 2]

可以看到，随机游走探索了图中更多的节点。接下来，使用 p=10 调用函数，由于其概率很低，所以不会返回到之前的节点：

print(random_walk(0, 8, p=10, q=1))

函数返回序列如下所示：

[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) 指定参数 p=3、q=2 调用 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,hs=1,   # Hierarchical softmaxsg=1,   # Skip-gramvector_size=100,window=10,workers=2,min_count=1)

(7) 在生成的序列上对 skip-gram 模型进行 30 次训练：

node2vec.train(walks, total_examples=node2vec.corpus_count, epochs=30, report_delay=1)

(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_state=0)
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(f'Node2Vec 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 = 1，q = 1) 的性能比表中其他 p 和 q 组合都要差。这证明了有偏随机游走对于该数据集而言的有效性，但情况并非总是如此，在其他数据集上，无偏随机游走也可能表现得更好
• p 值越高，性能越好，这也与我们的假设完全吻合。在社交网络中，通常可以将随机游走偏向于同质性。

我们可以通过调整参数观察使用不同参数时的结果。例如，我们可以探索 p 值较高 (> 7) 时的情况，或者 p 值和 q 值较低(介于 0 和 1 之间)时的情况。

小结

在本节中，我们了解了 Node2Vec，这是一种基于 Word2Vec 的架构。我们实现了有偏随机游走，并解释了其参数与两个网络属性(同质性和结构等价性)之间的联系。通过比较 Node2Vec 与 DeepWalk 在 Zachary's Karate Club 数据集上的性能表现，验证了有偏随机游走的有效性。

系列链接

图神经网络实战（1）——图神经网络(Graph Neural Networks, GNN)基础
图神经网络实战（2）——图论基础
图神经网络实战（3）——基于DeepWalk创建节点表示