非均匀随机图中的保距嵌入

# 超越最坏情况畸变：非齐次随机图中的距离保持嵌入 来源：https://arxiv.org/html/2607.10074 \\nameMy Le\\emailmle19@jh\.edu \\addr约翰霍普金斯大学应用数学与统计系 马里兰州巴尔的摩 21218, 美国\\nameLuana Ruiz\\emaillrubini1@jh\.edu \\addr约翰霍普金斯大学应用数学与统计系 马里兰州巴尔的摩 21218, 美国\\nameSouvik Dhara\\emailsdhara@gatech\.edu \\addr佐治亚理工学院工业与系统工程系 佐治亚州亚特兰大 30332, 美国 ###### 摘要 图机器学习为理解复杂网络和学习有意义的节点表示提供了强大工具。然而，一个核心挑战是设计嵌入时，需最小化*局部*和*全局*泛函（如最短路径长度）的畸变。现有的距离保持嵌入畸变保证本质上是基于最坏情况的，会产生过于悲观的上界，无法捕捉*典型*大规模网络的结构。为解决此问题，我们分析了非齐次随机图（IHG）上的基于地标的嵌入中的最短路径逼近问题。IHG是一种通用模型，具有依赖于类型的边概率。通过保留到一小部分称为地标的参考节点的最短路径，基于地标的方法有效地充当虚拟图稀疏化器，其中通过多类型分支过程建模的结构异质性和可控邻域扩展能够实现显著更紧的维度-畸变折中，即对于\(1-\varepsilon\)-畸变为\(\Omega\left(n^{1-\varepsilon}\log n\right)\)，对于\(1+\varepsilon\)-畸变为\(\Omega\left(n^{\frac{2}{2+\varepsilon}}\log n\right)\)，而经典最坏情况上界分别为\(\Omega\left(n^{\frac{2(1-\varepsilon)}{2-\varepsilon}}\log n\right)\)和\(\Omega\left(n^{\frac{2}{2+\varepsilon}}\log n\right)\)。我们将这些保证扩展到全局、组件范围内的平均值，并通过一种新颖的度量夹逼框架统一了有限类型和连续潜在空间的分析，建立了通用\(L^2\)核模型（包括重尾和幂律网络）的通用畸变界。最后，我们引入了一种图神经网络增强变体，用灵活、结构感知的神经代理替代了刚性、计算昂贵的精确最短路径查询。通过利用图神经消息传递与最短路径算法动态规划原理之间的内在对齐，我们的方法证明了在小型随机图上训练的模型能够学习提取通用的距离保持特征，从而实现对大规模、真实世界网络的鲁棒泛化，其保真度匹配或超越经典的、精确的基于地标嵌入。 关键词：最短路径，距离保持嵌入，地标，图稀疏化器，非齐次随机图，异质性，图神经网络，可迁移性 ## 1 引言 图学习中的一个核心挑战是以一种忠实捕捉其基本结构特征（包括局部连通模式、介观组织和全局拓扑）的形式来表示网络数据。一种常见策略是将节点映射到低维度量空间，使得嵌入点之间的距离反映图的原始结构。这些嵌入提供了网络的紧凑且数学上易于处理的表示，使得在一系列推理任务（包括节点分类、链接预测、聚类和路由）中能够进行大规模统计分析和高效计算 (Hamilton et al. 2017b, Grover and Leskovec 2016, Belkin and Niyogi 2003)。 尽管取得了显著进展，节点嵌入技术主要设计用于捕捉局部和介观尺度的结构，未能准确保留全局图泛函。特别地，一个常被忽视的关键全局泛函是最短路径距离，它在路由、导航和网络效率中至关重要。最短路径距离常常被低维嵌入扭曲，尤其是在大规模且结构异质的图中 (Goyal and Ferrara 2018, Tsitsulin et al. 2018, Brunner 2021)。这种未能保持图的度量结构的缺陷，需要一种更有原则性的距离感知嵌入方法。 *基于地标*的距离嵌入通过节点到一小部分称为地标的参考节点的距离来表示节点，自然地诱导出一个概率虚拟图稀疏化器 (Ahmed et al. 2020)。该方法植根于可扩展的最短路径逼近算法 (Sarma et al. 2010, Potamias et al. 2009, Tretyakov et al. 2011) 以及度量嵌入到希尔伯特空间的数学理论 (Bourgain 1985, Matoušek 1996, Linial et al. 1995)，在实践中被广泛使用，提供了传统边删除稀疏化器 (Peleg and Schäffer 1989, Althöfer et al. 1993) 的基于坐标的替代方案，同时享有可证明的\((1\pm\varepsilon)\)-畸变保证 (Bourgain 1985, Sarma et al. 2010)。 尽管取得了经验上的成功，现有的理论保证要求嵌入维度对于\((1-\varepsilon)\)-畸变为\(\Omega\left(n^{\frac{2(1-\varepsilon)}{2-\varepsilon}}\log n\right)\)，对于\((1+\varepsilon)\)-畸变为\(\Omega\left(n^{\frac{2}{2+\varepsilon}}\log n\right)\)，这随\(n\)多项式增长，在大规模时变得难以承受 (Matoušek 1996, Sarma et al. 2012, Loukas 2020)。这些界对任意图成立，在最坏情况下是紧的，但对于实践中出现的结构化、异质网络可能过于悲观。这提出了一个问题：在更现实的图结构假设下，是否可以实现更锐利的保证。 在本文中，我们在*非齐次随机图* (IHG) 上分析基于地标的距离嵌入。IHG是一个灵活模型，包含了随机块模型和Chung–Lu型模型的各种变体 (Chung and Lu 2002, Bollobás et al. 2007, van der Hofstad 2024a)，并捕捉了现实世界网络中观察到的结构异质性，如社区组织和度变异性。我们不是寻求对任意图都成立的最坏情况保证，而是采用基于随机图理论的“平均情况”视角，分析类型依赖的连通性如何支配邻域扩展，进而影响基于地标的距离保持嵌入的几何特性。 #### 理论贡献。 我们的主要贡献是证明，对于一大类具有离散或连续核的IHG，与经典最坏情况保证相比，基于地标的嵌入在畸变-维度折中上实现了多项式改进。我们通过多类型分支过程 (Athreya and Ney 2012, van der Hofstad 2024a) 的视角刻画局部邻域的精细扩展来建立这些结果。这个概率框架将局部的、异质的节点连通性与图的全局算子理论性质联系起来，使我们能够精确地映射IHG内部的结构方差如何控制距离传播。为此，我们的理论框架做出了三重贡献： - • **锐利逐点保证**（定理4.1和4.2）：在具有有限类型的IHG的超临界区域内（此时高概率存在唯一巨分支，即随着\(n\to\infty\)概率趋近于1），我们对于\((1\pm\varepsilon)\)-畸变获得嵌入维度\(\Omega\left(n^{1-\varepsilon}\log n\right)\)，这比最坏情况界更小。由于嵌入维度的增益为\(n^{O(\varepsilon)}\)，随着\(\varepsilon\to 0\)而减小。这一行为与Bourgain (1985) 关于Lipschitz嵌入的经典工作一致，该工作表明稠密随机图达到几乎最坏情况的畸变界。 - • **全局平均情况稳定性**（定理4.5）：我们将逐点保证扩展到整个拓扑结构，证明度量畸变的经验空间平均值——在全体有效连通的节点对\(U=\{(u_1,u_2): u_1\leftrightarrow u_2, u_1\neq u_2\}\)上归一化——高概率地紧致集中在\((1\pm\varepsilon)\)窗口内。通过解耦空间求和，我们证明病态配置的质量渐近可忽略，确保异常结构瓶颈无法破坏全局下游经验风险优化。 - • **通用连续扩展**（定理5.1和5.2）：我们通过严格概率空间耦合将有限类型结果推广到连续潜在空间，该耦合将任意\(L^2\)核\(\kappa\)夹逼在两个有限阶梯函数核\(\kappa_\delta^\pm\)之间。在超临界条件下，连续网络的全局度量结构表现为这些有限逼近在逼近分辨率\(\delta\to 0\)时的稳定泛函极限。这个夹逼论证使我们能够将多项式维度-畸变折中迁移到非参数、重尾网络架构，包括无界幂律Chung–Lu配置。 **方法贡献。** 在理论框架基础上，我们提出了一种基于GNN增强的变体，该变体直接从图结构学习逼近到地标的距离，替代了精确的最短路径计算。GNN非常适合此任务，因为它们与支撑最短路径算法的动态规划原理一致 (Xu et al. 2019b, Dudzik and Veličković 2022)。我们的实验表明，基于GNN的嵌入匹配或改进了精确的地标嵌入，特别是在强超临界区域，其中邻域扩展以图的谱半径决定的速率呈指数增长。更引人注目的是，在小型图上训练的GNN能够有效地泛化到更大的图以及真实世界网络，凸显了IHG框架作为可扩展、距离感知图表示训练场的实际价值。 ### 1.1 相关工作 距离保持图嵌入的基本极限已被广泛研究。Bourgain (1985) 证明了在任意图中，将所有成对距离保持到\((1\pm\varepsilon)\)因子内所需的维度至少为\(k_\varepsilon = \Omega\big((\log n)^2/(\log\log n)^2\big)\)。后续工作进一步优化了这些界。Linial et al. (1995) 证明了\(k_\varepsilon = \Omega((\log n)^2)\)，Matoušek (1996) 进一步精炼为对于某些图族有\(k_\varepsilon = \Omega\left(n^{c/(1+\varepsilon)}\right)\)。更近期，Naor (2016) 和Naor (2021) 证明了具有强扩展性质的图需要多项式维度的嵌入，强调了在最坏情况下距离保持的困难。 在算法方面，基于地标的方法作为实用替代方案已被广泛研究 (Goldberg and Harrelson 2005, Sarma et al. 2010, Potamias et al. 2009, Tretyakov et al. 2011, Akiba et al. 2013, Rizi et al. 2018, Qi et al. 2020)，Sommer (2014) 提供了全面综述。这些方法选择一小部分参考节点，并通过三角不等式近似成对距离，以精确性换取可扩展性。尽管经验上有效，它们的理论保证继承了最坏情况分析的悲观性，这激发了本文所采用的平均情况视角。 图表示学习领域中更广泛的研究关注结构性质（如局部连通性、高阶邻近性和谱几何）如何支配学习嵌入的质量。基于随机游走的方法如DeepWalk (Perozzi et al. 2014) 和Node2Vec (Grover and Leskovec 2016) 捕捉局部结构，而GraRep (Cao et al. 2015)、PRONE (Zhang et al. 2021) 和邻接搜索嵌入 (Chaitanya et al. 2025) 将其扩展到高阶邻近性。谱方法包括Laplacian Eigenmaps (Belkin and Niyogi 2003) 捕捉粗略的全局结构，但可能对度变异性和边异质性敏感 (Chung 1997, Von Luxburg 2007)。Cauchy嵌入 (Tang et al. 2019) 通过重尾相似性度量解决此问题，提高了异质网络中的鲁棒性。这些方法中没有一个被设计为显式保持图的度量结构，而这是本工作的重点。 我们的工作与理论计算机科学中关于*图稀疏化器*的广泛文献密切相关 (Ahmed et al. 2020, ht