双曲图嵌入能否用一种度量嵌入、用另一种度量优化?

嵌入保持曲率-1,两阶段预条件子在真实树上把应力比最佳单一曲率降低46-74%。

直接答案

可以。论文表明,用于走梯度步的度量可以被当作独立于嵌入几何的预条件子:损失始终在曲率-1下计算,而优化器的扭曲从平坦(c 趋于 0)一直延伸到精确双曲度量(c = 1)。在热启动把节点铺展到很宽半径范围的图上,两个端点都不是最优;两阶段方案(先平坦、再取中间曲率)在真实树上把应力比最佳单一曲率降低 46-74%。

1篇文献引用

本文由 WisPaper 驱动的搜索和论文分析生成。

大半径下角向运动被冻结

层次图嵌入双曲空间时,由于负曲率,其失真低于欧氏空间;但基于梯度的学习在大半径处受阻,而层次图恰恰把大多数节点放在那里。庞加莱球和洛伦兹双曲面都会因灾难性相消而损失精度:洛伦兹模型从两个量级为 e^(2r) 的近乎相等数的闵可夫斯基积中恢复距离,当 r 约为 16 时,这种相消已使距离为 1 的两个节点的距离产生 1% 的误差,到 r 约为 19 时变为零。球的点以 1 - tanh(r/2) 约等于 2e^(-r) 趋近边界,也遭受同类相消。

极坐标避免了这一失效,在 r 约达 350 时仍保持准确,但引入了另一个问题。在极坐标中,一个点被存为双曲半径与单位方向,x = (r, v),而双曲度量把角向分量按 sinh^2(r) 缩放。在自然梯度下降下,角向步长为 delta theta = -eta * d_theta f / sinh^2(r),因此实际移动的弧长为 delta s = eta * |d_theta f| / sinh(r),随半径指数衰减。在层次嵌入可能达到的半径(约 20 或 30)处,无论角向导数多大,角坐标都被冻结。

步长度量是一种选择而非约束

核心观察是:用于走梯度步的度量不必是嵌入所生活的度量。损失始终用曲率-1 下的双曲距离计算,因此优化器的度量只起预条件子作用:它改变优化器走过的路径,而不改变所求解的问题。现有实现默默固定了这一选择。黎曼方法用精确双曲度量走步,而欧氏切参数化把每个嵌入存为单个无约束向量 z = rv 并施加普通欧氏梯度下降,这隐含地把角向分量按半径本身缩放。

把 sinh^2(r) 替换为任意正扭曲 w(r)^2,就得到一个预条件子族,而上述两种现有选择是该单参数族 w_c(r) = sinh(sqrt(c) r) / sqrt(c) 的两个端点。这里 c = 1 恢复精确双曲度量,c 趋于 0 给出平坦扭曲 w_0(r) = r。每个 w_c 都是常曲率 -c 度量的扭曲,但它在这里只作为预条件子起作用:损失不变,嵌入之间的距离对每个 c 都保持曲率-1,扭曲只在移动坐标时进入。这与混合曲率方法不同,后者改变的是嵌入空间本身。

两个端点为何在宽半径跨度下都失效

论文把半径的分散程度认定为预条件子起作用的必要条件。采用平坦预条件子时冻结被消除,但如果嵌入从很小的 r_min 跨到很大的 r_max,外层与内层节点移动量之比会按 e^(r_max - r_min) 缩放,除非角向导数随 r 指数下降,而对应力目标而言恰恰相反。因此单一学习率在 c 趋于 0 时无法有效移动所有节点:它要么只移动外层节点,要么发散。

精确双曲度量则以相反方式失效。它冻结角向运动,因此要纠正一个布局整体错误的热启动,需要在大半径处做相对大角度的旋转,而这只有较小的 c 才能提供。中间取值的 c 缩小了外层与内层节点移动量的差异,该比值变为约 e^((1 - sqrt(c))(r_max - r_min))。极端情形 c = 1 看似抵消了半径跨度,却会把冻结带回来。

两阶段方案分离粗调与精调

作者运行两个阶段:c 趋于 0 的粗调阶段、坐标交接,以及在内部 c 处、带全新优化器状态和各自学习率的精调阶段。预条件子不改变损失的临界点,因为 G_c^(-1) grad f 恰在 grad f 为零处为零;但损失非凸,路径决定到达哪个临界点。因此粗调阶段不只是让同一次下降更快起步:它可以交接出一个配置,使精调阶段收敛到精调单独绝不会找到的位置。

调度与曲率同样重要。仅从初始化出发运行时,中间曲率往往比平坦度量更差。它最大的优势出现在平坦第一阶段完成大尺度重排之后,让弯曲度量去精修一个大致正确的配置。

实验是如何进行的

所有实验都用闭式 HYDRA 解初始化嵌入,该解来自 cosh(D) 的特征分解,再用黎曼 Adam 精修。整个流程不含随机性:热启动是确定性特征分解,应力按全批量评估。学习率在每个图中按预条件子曲率搜索,网格取 1/3/10 阶梯,每个报告结果都对应损失意义上被夹住的最佳学习率,即两侧都有严格更差或发散邻居;若某网格的胜出者落在端点,则扩展网格直到满足该条件。报告值是最后 10% 迭代的平均应力。

应力目标是嵌入在固定曲率-1 下的双曲距离与图中对应最短路径距离之差的平方。所用图包括五棵树,其中四棵是来自 Open Tree of Life 合成树(release 16.1)的真实系统发育树:Marsupialia、Cichlidae 和 Falconiformes 支系的诱导子树,以及 Fabaceae 的一棵有根子树。第五棵是合成毛毛虫图,一条 40 个节点的路径,每个节点附 4 个叶节点。还包括两个小直径、枢纽主导的图:用 NetworkX 的 powerlaw cluster graph 生成的 Holme-Kim 无标度图,以及欧洲航空交通网络。

单一曲率下精确度量表现最差

在单一曲率消融中,c = 1 的精确度量在应力确实下降的少数迭代之后便实际冻结,更大的学习率只会发散。从 HYDRA 初始化出发,它最终比最佳单一曲率高出 2 到 20 倍。中间取值的 c 可以给出总体最佳结果,而 c 趋于 0 系统性地处于最佳单一曲率之列,这正是它被用作两阶段方案初始化的原因。

半径跨度把受益的图与不受益的图分开。在两个枢纽主导的图以及跨度为 13.2 的 Falconiformes 上,所有曲率、学习率和调度都收敛到相差 1% 以内的相同应力。半径跨度更大的图对预条件子曲率更敏感。

两阶段增益及其消失之处

两阶段方案产生了显著改善的结果。在合成毛毛虫图上,应力几乎下降两个数量级。在真实图上增益较温和但仍显著:与单纯重启 Adam 相比,大半径跨度的图下降 25% 到 50%。与在整个迭代数中选用单一曲率相比,调度增益更大:最佳两阶段运行在真实树上把应力比最佳单一曲率降低 46-74%,在合成毛毛虫图上降低 98.0%。

曲率增益比较第 2 阶段中 c 取 {0.2, 0.3} 的最佳值与 c = 10^-6:毛毛虫图 -98.7%,Marsupialia -53.2%,Fabaceae -26.5%,Cichlidae -23.1%,Falconiformes -0.8%。调度增益在同样这些图上依次为 -98.0%、-74.1%、-60.0%、-45.8%、+0.4%、+0.4% 和 +0.1%。在半径跨度较小的图上,两阶段方案的增益为零:预条件子曲率在那里没有影响,这在单阶段方案中已经可见,第二阶段也不会改变这一点。

半径跨度阈值对实践意味着什么

论文自身的优先判据是热启动的半径跨度 s = r_max - r_min。由于 r_min 约为 0.5、r_max 约为 diam/2,直径大、节点分布在很宽深度范围上的深而不平衡的树,正是预条件子选择应当起作用的图类型;而对小世界图则不应起作用。跨度起的是阈值而非预测器的作用:它把受益的图与不受益的图分开,但不决定增益的大小。

两项限制界定了这一结论的可迁移范围。最佳曲率和学习率是对每个图分别用网格搜索找到的,因此一个能从图本身设定它们、或在优化过程中自适应调整它们的规则会让方法更实用。此外,研究只覆盖单一目标(应力);同样的预条件视角能否迁移到其他双曲嵌入损失以及更大的图,仍是未决问题。对想从这篇论文中取用的读者而言,可操作的划分依据是半径跨度:在热启动把节点铺展到很宽半径范围的图上,精确双曲度量是所测选项中最差的,先平坦后中间曲率的两阶段调度是优先选择;在小跨度图上,曲率与调度选择都收敛到相差 1% 以内的相同应力,因此选择无关紧要。

本文引用的文献

1

Hyperbolic Graph Representation Learning: Embed in One Metric, Optimize with Another

把优化器的度量当作独立于曲率-1 嵌入的预条件子后,两阶段调度(先平坦、再取中间曲率)在真实树上把应力比最佳单一曲率降低 46-74%,而在半径跨度大的图上,精确双曲度量是表现最差的单一曲率选项。