1 引言

受到自然语言处理领域的word2vec算法启发，图学习领域出现了基于随机游走的图表示学习算法，比如DeepWalk和Node2Vec等算法。这些算法将节点视为单词，将随机游走序列看作句子，通过分析邻居节点在上下文中出现的概率，来学习图中节点的嵌入表示。这些算法的核心在于确保随机游走采样生成的序列能够准确地捕捉图中的信息。然而，随着图的规模增大，随机游走序列的采样面临着消耗时间过多和收敛速度较慢等挑战。因此，如何设计更加高效的随机游走算子，引起了人们的关注。在本文中，将介绍一些最新的研究论文，带领读者了解目前可用的随机游走采样算子。

2 论文简介

[EuroSys 2023] TEA: A General-Purpose Temporal Graph Random Walk Engine

论文链接：https://madsys.cs.tsinghua.edu.cn/publications/eurosys23-huan.pdf

由于以往的采样策略主要针对静态图，未能有效地解决时序图上的随机游走采样问题。这篇工作提出了一种针对时序图的高效通用随机游走算子，通过引入一种新的混合采样方法，将两种蒙特卡洛采样方法结合在一起，从而显著减少了空间复杂度，并实现了高效的采样速度。

文章中首先介绍了随机游走采样中常用的三种采样方法：

• inverse transform sampling(ITS)：对于每一个顶点 ，ITS通过计算当前节点 边集的权重前缀和，将顶点 的累积分布函数存储在数组 中， 假设边 的权值为 ，则 。在采样过程中，生成一个在范围 [0, ] 内的随机数 ， 其中 为所有边的权值之和。然后 ITS 会找到满足 的最小值，从而选择采样的边。ITS算法的时间复杂度为 ， 其中 为采样空间的大小。详细情况如上图（b）所示。

• Alias method：Alias方法将每条边的权重分成几个部分，并将它们组合起来形成n个区段。需要满足两个条件：（1）每个区段最多由两部分组成，（2）每个区段的总权重必须是整体的平均权重。在采样过程中首先均匀采样一个区段，然后在区段内采样一个部分。从直观上来说，边被采样的概率与其对应的权值成正比。记录这些区段及其内容的数据结构称为Alias表。生成Alias表和在其上进行采样时间的复杂度分别为 和 。详细情况如上图（c）所示。

• Rejection sampling：该方法通过生成一个随机数来选择侯选边，然后再生成另外一个随机数来决定是否接受这个采样边。如果采样边被拒绝，则需要重新进行采样，直到得到一个有效的边。详细情况如上图（d）所示。

本文所提出的HPAT方法在随机游走采样过程中巧妙地结合了ITS和Alias两种采样方法。在HPAT方法的运行流程中，首先将边集划分为多个小的区段，每个区段都充当了一个Alias表的主干。在采样过程中，先使用ITS采样方法来选择感兴趣的主干，然后在每个主干内部使用Alias方法进行采样。如果选择的主干是完整的，那么可以直接使用Alias采样方法进行采样；但如果所选择的主干是不完整的，则需要使用ITS方法重新构建数组，然后进行采样。通过这种独特的组合方式，HPAT方法可以兼顾Alias和ITS方法的各自优点，既减少了存储空间复杂度，又降低了搜索时间复杂度。

如上图所示，TEA模型的整体运行流程提供了更直观的图示。

[TKDE 2023] Common Neighbors Matter: Fast Random Walk Sampling With Common Neighbor Awareness

论文链接：https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=9712235

本文提出了一种具有共同邻居意识的快速随机游走采样方法，称为CNARW。随机游走通常在大规模图中进行采样，但是其收敛速度较慢而且计算成本高。CNARW方法通过在每次节点选择的过程中整合先前访问过的节点和下一跳候选节点之间的公共邻居，从而加快收敛速度。

上图的左半部分所示为进行简单随机游走采样，即以相同的概率随机选择当前节点 的下一节点，这一采样方法很容易陷入局部循环。上图的右半部分所示为CNARW方法的随机游走采样，如果当前节点为 ，对任意节点 ，如果节点 的节点度较高或者与节点 拥有更少的共同邻居，那么采样节点 的概率则更高，这种选择方式更容易探索更多未访问过的节点。下面解释一下CNARW方法有效的原因，因为如果一个候选节点有更高的节点度的话，则有更大的机会去探索未访问过的节点；那么如果它与之前访问过的节点有更多的共同邻居的话，则也有很高的概率重新走回访问过的节点。因此，CNARW方法有更高的概率采样之前未访问过的节点，并且降低在未来随机游走采样中重新采样之前采样过的节点的概率。

节点采样的概率矩阵 表示如下：

其中 计算方法为：

其中 表示节点 的节点度， 表示节点 和 节点 的共同邻居数。

整个CNARW方法的伪代码表示为：

3 总结

本文介绍了TEA和CNARW两篇论文，其中TEA提出了使用混合采样的方法，减小采样的时间复杂度。CNARW提出了一种可以帮助在随机游走采样过程中，更有利于探索之前所未访问过的节点的方法。对于大规模的图，当前的随机游走方法可能仍然需要较长的时间来收敛，未来可以考虑如何利用分布式计算的方法加快采样过程。