Loading... [node2vec: Scalable Feature Learning for Networks](https://dl.acm.org/doi/abs/10.1145/2939672.2939754) ## 1 算法原理 Node2Vec是对DeepWalk的改进，在DeepWalk完全随机游走的基础上，Node2Vec增加了p、q参数，从而实现了有偏随机游走。不同的p、q组合，对应了不同的搜索范围，具有很大的灵活性。Node2Vec与DeepWalk均使用SkipGram模型获取节点的向量表示，但与DeepWalk不同的是，Node2Vec使用负采样对模型进行优化，从而具有更高的效率。 Node2Vec的算法流程如图1所示，可概括为三个步骤： (1)构建随机游走采样策略表； (2)根据随机游走采样策略表进行有偏随机游走，得到有偏随机游走序列； (3) 将节点类比成单词，随机游走序列类比成句子，使用SkipGram算法，获得节点的向量表示。  ### 1.1 有偏随机游走 获取给定节点的邻域节点集有两种方法：BFS（广度优先采样）和DFS（深度优先采样）。BFS能够捕获到节点的结构等价性信息，如图2中的节点u和节点S6具有相似的结构作用；DFS能够捕获到节点的同质性信息，如图2中的节点u和节点S1属于同一网络社群。Node2Vec通过综合考虑这两种采样方法，制定了有偏随机游走的节点转移策略。  给定当前节点v，则访问下一个节点x的概率可通过下式得到。其中$\pi_{vx}$是节点v和节点x之间的未归一化转移概率，Z是归一化常数。 $$ P(c_i=x \mid c_{i-1}=v) = \begin{cases} \frac{\pi_{vx}}{Z} & if(v, x)\in E \\ 0 & otherwise \\ \end{cases} $$ 为了能够指导随机游走探索不同类型的网络邻居，Node2Vec引入了两个超参数p和q来控制随机游走的策略。 若当前随机游走经过边(t, v)到达节点v，则未归一化的转移概率$\pi_{vx} = \alpha_{pq}(t, x) \cdot w_{vx}$，其中$w_{vx}$是节点v和x之间的边权，$\alpha_{pq}(t,x)$的定义如下式所示，式中$d_{tx}$表示节点t和节点x间的最短距离，Node2Vec只考虑$d_{tx}$取值为{0, 1, 2}的情况。 $$ \alpha_{pq}(t,x) = \begin{cases} \frac{1}{p} & if \ d_{tx} = 0 \\ 1 & if \ d_{tx} = 1 \\ \frac{1}{q} & if \ d_{tx} = 2 \\ \end{cases} $$ 参数p控制重复访问刚刚访问过的节点的概率（见图3）。如果p的值很大，则刚刚被访问过的节点再次被访问的概率会很低，这种策略可以避免程序在两个节点间来回跳跃的情况，并指导程序适度地向外探索；如果p的值很小，则程序会倾向于探索局部信息。 参数q控制随机游走探索的方向（见图3）。如果q的值很大，则程序倾向于访问和节点t接近的节点，类似BFS。如果q的值很小，则程序更倾向于探索距离t较远的节点，类似DFS。  ### 1.2 Alias Sample 有偏随机游走过程中的每一次转移都是对离散非均匀概率分布的一次采样，别名采样(Alias Sample)可以经过时间复杂度为O(n)的预处理过程，将其转化为均匀分布与二项分布的组合，从而实现时间复杂度为O(1)的采样。 假设一个离散随机分布包含n个相互独立的事件$A_1, A_2, ...,A_n$，其中$\sum_{i=1}^{n}{P(A_i)=1}$，别名采样算法预处理流程如下： (1) 将所有概率乘以n，得到n个值； (2) 将值大于1的事件拆分成两个或多个值小于等于1的事件，使得其能通过与值小于1的事件两两组合，形成n组值为1的新事件$B_1, B_2, ...,B_n$，其中$P(B_i)=\frac{1}{n}$，且每个新事件最多包含两个原事件。于是，组与组之间服从均匀分布，而组内服从二项分布。 进行采样时，只需按照均匀分布随机选择其中一组，然后在组内按照二项分布进行采样即可。 ## 2 代码实现 根据概率分布构造采样表：smaller用于存放值小于1的事件编号，larger用于存放值大于1的事件编号。每次分别从smaller和larger取出一个事件，将值大于1的事件拆分为两部分，其中一部分与值小于1的事件组合成值等于1的新事件，剩下一部分根据值的大小放到smaller或larger中，如此循环，直到消除所有值不为1的事件。最终返回的采样表有两项，accept[i]表示组i中事件i发生的概率，而alias[i]是组i中i事件的对立事件编号，具体代码如下： ```Python def get_alias_table(probs): k = len(probs) # accept[i]是组i中事件i发生的概率（二项分布） accept = np.zeros(k, dtype=np.float) # alias[i]是组i中i事件的对立事件编号 alias = np.zeros(k, dtype=np.int) smaller = [] # 小于1的事件 larger = [] # 大于1的事件 for idx, prob in enumerate(probs): accept[idx] = k * prob if accept[idx] < 1.0: smaller.append(idx) else: larger.append(idx) # 用大于1的事件填小于1的事件，直到所有组的值都为1 while smaller and larger: small = smaller.pop() large = larger.pop() accept[large] -= 1 - accept[small] alias[small] = large if accept[large] < 1.0: smaller.append(large) else: larger.append(large) return alias, accept ``` 根据采样表进行采样：首先生成一个[0, k)之间均匀分布的伪随机数用于选择组，然后再生成一个[0, 1) 之间均匀分布的伪随机数，当该随机数小于当前组内原事件idx的概率时，认为原事件idx发生，反之则认为其对立事件alias[idx]发生。因为只需要产生两个随机数就能完成采样过程，所以采样的时间复杂度为O(1)。具体代码如下： ```Python def alias_sample(alias, accept): k = len(alias) # 随机选择一组 idx = int(np.floor(np.random.rand() * k)) if np.random.rand() < accept[idx]: return idx else: return alias[idx] ``` 根据参数p、q和边权计算转移概率，返回该节点的采样表：按照**1.1 有偏随机游走** 中的公式计算转移概率。对于当前节点cur，遍历其所有邻居节点，若邻居节点nbr是刚刚访问过的节点prev，则转移概率为边权除以p；若nbr是prev的一阶邻居节点，则转移的概率为边权乘以1；若nbr是prev的二阶邻居节点，则转移的概率为边权除以q。最后，将该节点的转移概率进行归一化，调用get_alias_table函数生成采样表。具体代码如下： ```Python def get_alias_edge(self, prev, cur): unnormalized_probs = [] for nbr in sorted(self.G.neighbors(cur)): # 回到上一个节点的概率 = 边权 * 1/p if nbr == prev: unnormalized_probs.append(self.G[cur][nbr]['weight'] / self.p) # 到上一个节点的一阶邻居的概率 = 边权 * 1 elif self.G.has_edge(nbr, prev): unnormalized_probs.append(self.G[cur][nbr]['weight']) # 到上一个节点的二阶邻居的概率 = 边权 * 1/q else: unnormalized_probs.append(self.G[cur][nbr]['weight'] / self.q) # 归一化各条边的转移权重 norm_const = sum(unnormalized_probs) normalized_probs = [float(u_prob) / norm_const for u_prob in unnormalized_probs] return get_alias_table(normalized_probs) ``` 初始化所有节点的采样表：对于无向图中每一条边，分别调用get_alias_edge方法生成其转移概率采样表，由于是无向图，所以每条边的两个方向都要进行处理。除此之外，还需要考虑一种特殊情况，即随机游走的起始节点不存在上一个节点，因此不能通过**1.1 有偏随机游走** 中的公式计算其转移概率，这种情况可不考虑p、q的值，直接使用边权计算转移概率。具体代码如下： ```Python def init_alias_table(self): print("Init alias table...") for edge in tqdm(self.G.edges()): self.alias_edges[edge] = self.get_alias_edge(edge[0], edge[1]) self.alias_edges[(edge[1], edge[0])] = self.get_alias_edge(edge[1], edge[0]) # 只根据边权信息计算转移概率，生成采样表（用于起始节点的转移） for node in tqdm(self.G.nodes()): # 取出node边的权重并进行归一化 unnormalized_probs = [self.G[node][nbr]['weight'] for nbr in sorted(self.G.neighbors(node))] norm_const = sum(unnormalized_probs) normalized_probs = [float(u_prob) / norm_const for u_prob in unnormalized_probs] # 仅依据边权进行转移 self.alias_nodes[node] = get_alias_table(normalized_probs) ``` 生成单个有偏随机游走序列：对于当前节点cur，如果其有邻居节点，且其是该随机游走过程中的第一个节点，则仅根据由边权信息确定的采样策略进行别名采样，确定下一个访问的节点；如果其不是随机游走过程中的第一个节点，则根据由p、q参数和边权信息确定的采样策略进行别名采样，确定下一个访问的节点。循环上述过程，直到随机游走序列满足最大长度要求。具体代码如下： ```Python def biased_random_walk(self, start_node, walk_length): walk = [start_node] cur = start_node prev = None while len(walk) < walk_length: nbrs = sorted(self.G.neighbors(cur)) if len(nbrs) > 0: if prev is None: # 起始节点依据边的权重进行随机游走 walk.append(nbrs[alias_sample(self.alias_nodes[cur][0], self.alias_nodes[cur][1])]) else: walk.append(nbrs[alias_sample(self.alias_edges[(prev, cur)][0], self.alias_edges[(prev, cur)][1])]) prev = cur cur = walk[-1] else: break return walk ``` 生成所有节点的随机游走序列：遍历图中的所有节点num_walks次，对每个节点调用biased_random_walk方法生成长度最大为walk_length的随机游走序列，最后将所有的随机游走序列转成字符串类型，以便后续处理。具体代码如下所示： ```Python def simulate_walks(self, num_walks=args.num_walks, walk_length=args.walk_length): walks = [] nodes = list(self.G.nodes()) print("Walking...") for _ in tqdm(range(num_walks)): random.shuffle(nodes) for cur in nodes: walks.append(self.biased_random_walk(cur, walk_length)) # 转成字符串格式 for walk in walks: self.walks_str.append([str(x) for x in walk]) ``` 学习节点的向量表示：同DeepWalk，这里使用Word2Vec中的SkipGram，与DeepWalk唯一的不同的是，这里的参数hs=0，表示使用负采样优化模型。具体代码如下所示： ```Python def learn_embeddings(self): print("Learning...") model = Word2Vec(sentences=self.walks_str, vector_size=args.dimensions, window=args.window_size, min_count=0, sg=1, hs=0, workers=args.workers) self.wv = model.wv # 保存 filename, suf = os.path.splitext(self.dataset_name) filename += f"({self.p},{self.q}).embeddings" path = os.path.join(args.save_dir, filename) model.wv.save_word2vec_format(path) ``` ## 3 实验分析 以下使用Node2Vec算法分别在Cora和BlogCatalog数据集上进行了实验，两个数据集分别采用的参数如表所示。 | 参数 | Cora | BlogCatalog | | ----------- | ------- | ----------- | | dimensions | 128 | 128 | | walk_length | 80 | 80 | | num_walks | 10 | 10 | | window_size | 10 | 10 | | workers | 10 | 10 | | p | 0.25、4 | 1 | | q | 0.25、4 | 1 | ### 3.1 Cora数据集测试结果 使用Node2Vec算法对Cora数据集进行处理，将每个节点都映射为128维向量，然后用t-NSE将嵌入向量映射到二维空间中。可视化结果如图4所示，图中根据节点的真实类别为节点分配颜色。当p=4，q=0.25时，可以得到图4(a)，当p=0.25，q=4时，可以得到图4(b)。 对比图4(a)与图4(b)，可以发现图4(a)中相同类别的节点分布更加聚集，而图4(b)中相同类别的节点分布更加分散。这是因为左图中p比较大，而q比较小，此时随机游走更倾向于采用DFS策略进行探索，更易于发现节点的同质性信息，即属于同一社群的节点编码成低维向量后，在低维空间中仍然相近。右图中的p比较小，而q比较大，此时随机游走更倾向于采用BFS策略进行探索，更易于发现节点的结构相似性信息；虽然节点类别相同，但节点在网络中的功能重要性程度不同，具有相似结构的节点编码成低维向量后，在低维空间中相近，因而右图中同一类别的节点更为分散。  ### 3.2 BlogCatalog数据集测试结果 使用Node2Vec的默认参数(p=1, q=1)对BlogCatalog数据集进行处理，将节点嵌入成128维的向量，然后从标记的节点中随机抽取一部分(TR, 10%~90%)作为训练集，其余部分作为测试集，使用one-vs-rest逻辑回归进行多标签分类，并计算macro-F1和micro-F1分数，实验结果如表所示。 | | 10% | 20% | 30% | 40% | 50% | 60% | 70% | 80% | 90% | | ----------- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | ----- | | Micro-F1(%) | 33.76 | 36.61 | 38.24 | 39.11 | 39.93 | 40.53 | 41.06 | 41.29 | 41.85 | | Macro-F1(%) | 19.75 | 22.60 | 24.20 | 25.08 | 26.03 | 26.54 | 27.14 | 27.07 | 27.38 | 根据表中数据绘制的折线图如图5所示，其中蓝色折线是Micro-F1分数，绿色折线是Macro-F1分数。与Node2Vec论文中的测试数据进行对比（图6），在训练集占比为10%~40%时，本次测试得到Micro-F1分数略低于论文中的Micro-F1分数，其余情况基本与其一致。 ![图5 Micro-F1和Macro-F1分数]  ## 4 总结 本章简述了Node2Vec的算法原理，完成了代码复现，并分别在Cora和BlogCatalog数据集上进行了测试，测试结果与预期相符，即Node2Vec能够通过控制超参数p和q的大小来选择更加关注节点的同质性信息还是结构相似性信息，相比DeepWalk，Node2Vec具有更大的灵活性。 Node2Vec使用Alias Sample采样算法，可以在O(1)的时间复杂度内完成对离散非均匀随机变量的采样。除了进行多标签分类，Node2Vec也可用于链接预测。同DeepWalk，Node2Vec也具有良好的并行性。 最后，需要说明的是，作者在论文中给出了如下示意图(图7)，很好地反映了node2vec的两种策略。 > 但我花了很长时间尝试复现该图，却始终得不到这种效果，目前也没找到他人的复现结果  © 允许规范转载 赞 0 如果觉得我的文章对你有用，请随意赞赏