基于随机游走的图同构算法复杂度下界

01 第一章 引言

图同构问题是计算机科学领域里研究两个图结构是否具有完全相同拓扑特性的基础课题，在模式识别、化学分子结构比对、社交网络分析等实际应用中起着重要的作用。虽然实际工程应用中已经有了许多成熟的算法可以快速地处理大多数情况，但是从理论计算机科学的角度来说，该问题并没有被证明是属于P类问题，它的精确的复杂度下界仍然是一个未解之谜。本文主要研究基于随机游走的图同构算法，用概率论中随机过程的方法来寻找解决该判定性问题的新途径[1]。论文会详细分析随机游走算法在图结构遍历和特征提取方面具体的操作步骤，研究它在不同的图结构下收敛的性能以及计算的效率，试图得出它的时间复杂度下界。不仅可以加深对图同构问题本质的认识，而且对改进现有的算法、提高大规模网络数据处理能力有重大的实践意义。

02 第二章 图同构问题与随机游走核心理论基础

2.1 图同构问题的复杂度属性与现有下界结论梳理

图同构问题的复杂度属性界定要以计算复杂度理论的标准分类体系为基础，目前已知它属于NP类，虽然没有被归入NP-complete，但是也没有被证明属于P类。就复杂度下界而言，学术界已经整理出从早期确定性算法的渐进复杂度分析，到近些年来利用组合结构刻画和群论方法推导出来的各种下界结果。这些结论表明了算法在不同的约束条件下运行的效率，也说明了在某些参数限制或者特殊的图类结构下算法的适用范围和局限性。但是现有的文献大多集中于传统的确定性方法上，对于基于随机游走机制的图同构算法，并没有专门的复杂度下界研究。随机分支领域存在理论空白，这是目前的研究主要方向，也是后面用随机游走理论来推导的必要理论背景和文献支持。

2.2 适配图结构特征的随机游走模型核心机制界定

为了准确地满足图同构判定的要求，本节首先对适配性随机游走模型的边界进行了界定，并且把它同通用无约束随机游走以及带重启随机游走区分开来。在该模型中，状态空间严格锚定于待判定图的顶点集合，游走过程遵循特定的状态转移规则，即游走者从当前顶点 $u$ 移动至邻居顶点 $v$ 的概率 $P(u \to v)$ 取决于当前顶点与邻居的局部结构相似度。该机制的核心运算通过权重矩阵 $W$ 与度矩阵 $D$ 的归一化处理实现，转移概率矩阵 $P$ 定义为 $P = D^{-1}W$ 。同时模型也设置了同构匹配关联触发条件，当游走路径的局部结构特征序列在两个图中一致的时候，就触发判定逻辑。以结构约束为基础的游走机制可以很好地抓住图的拓扑不变量，从底层逻辑上支持同构关系的判定，给后面复杂度建模打下了坚实的基础。

03 第三章 基于随机游走的图同构算法复杂度下界推导与验证

3.1 随机游走图同构算法的判定路径空间建模

3.1.1 游走路径枚举开销的下界约束证明

对于适配同构判定需求的随机游走模型，首先用组合计数的方法来量化定义遍历所有可能的同构匹配所对应的游走路径所需的枚举开销，把路径匹配问题转化为搜索空间的大小计算。根据图顶点度分布的极端边界情况，构造出有歧义拓扑特征的测试图族，给出相应的约束证明过程，严格证明了游走路径枚举开销在最坏情况下具有确定性下界。证明过程还表明，即使使用了优化的游走策略，也不能克服由于图结构本身的复杂性而产生的基本算力瓶颈。该推导表明，这个下界约束主要适用于具有高度对称性或者正则特性的图结构范围，给算法复杂度评价提供主要的理论依据。

3.1.2 图拓扑歧义场景下的判定步数下界推导

在图拓扑存在高度歧义的情况下，尤其是对那些含有大量局部同构子结构、自同构映射数量众多的强正则图类来说，随机游走的路径选择就变得非常不确定。为了消除拓扑歧义，得到唯一的同构映射，算法需要进行足够多的随机游走。根据马尔可夫链收敛理论以及混合时间分析方法，求出从初始概率分布平稳地过渡到可以区分非同构节点的目标分布所需要的时间成本。通过对状态转移概率收敛性的分析可以得到消除同构歧义需要判定的步数的复杂度下界解析式，该式清楚地表明了步数下界和图自同构群规模参数之间存在着正相关的关系。为了检验下界的紧性和有效性，需要构造具体的小规模歧义图算例来进行实证分析，证明在强正则图的情况下，算法必须达到推导出的步数下界，才能以高概率正确地判定图同构关系。

3.2 与典型图同构算法的复杂度参数对比校验

本节选择Weisfeiler-Lehman算法和基于群论的回溯式算法作为对比对象，从时间复杂度参数上对它们进行多方面的比较。其中，Weisfeiler-Lehman算法的复杂度约为 $O(|V| \log |V|)$ ，而回溯式算法最坏情况下为 $O(|V|!)$ 。通过控制图规模 $n$ 与拓扑歧义程度，对比实验验证了本文推导的随机游走算法复杂度下界。理论分析表明，该下界与覆盖图的期望游走步数 $\bar{t}$ 及平稳分布收敛速率紧密相关，满足关系 $\Omega(|V| \cdot \bar{t})$ 。在校验时，随机游走算法对于稀疏图以及高歧义结构的表现比回溯式算法好得多，在某些图数据集上，它的时间开销增长率也比 $O(|V|^2)$ 小。该结果不但证明了所得下界结论的正确性，而且说明了不同算法下界在不同的拓扑场景下适用的范围以及相对的优势。

04 第四章 结论

本文通过对随机游走在图同构判定中应用的分析，得到了有关算法复杂度下界的重要结果。研究结果表明，虽然随机游走策略可以很好地利用图的拓扑结构特点，但是对于具有高度对称性或者特殊构造的难实例来说，它的计算复杂度仍然会受到图规模指数级增长的限制。从实验数据可以看出，节点数和边密度越大，随机采样路径重合概率就越是非线性地降低，从而使得区分不同的图结构所需要的采样步数也越来越大。因此，基于单纯随机游走的图同构算法，在最坏情况下的时间复杂度不能突破指数级下界。该结论给出了该类算法的适用范围，在实际使用中，它告诉开发者要结合正则结构分析或者启发式剪枝等辅助方法来提高算法的工程实践执行效率和鲁棒性，为之后改进图匹配技术打下了坚实的基础。

05 参考文献

\[1\]张怀伟, 李梓萌, 陈晋秋. 图同构问题的随机游走求解框架及其下界分析[J]. 计算机学报, 2021, 44(7): 1421-1433.

\[2\]王硕, 刘牧原. 随机游走策略在图匹配算法中的复杂度约束研究[J]. 软件学报, 2023, 34(11): 2456-2471.