论文标题
与地标的应变最小化双曲线网络嵌入
Strain-Minimizing Hyperbolic Network Embeddings with Landmarks
论文作者
论文摘要
我们引入L-Hydra（地标性双曲线距离恢复和近似），这是将网络或基于距离的数据嵌入双曲线空间中的方法，这仅需要距离测量到几个“地标节点”。这种具有里程碑意义的启发式使L-Hydra适用于大规模图，并根据先前引入的方法改进。作为数学上的理由，我们表明，从距离测量到D+1个地标，可以完美地恢复D维双曲线空间中的点配置（直至等轴测图）。我们还表明，L-Hydra解决了一个两阶段的应变最小化问题，类似于我们以前的（未地标记）方法“ Hydra”。在实际网络数据上测试，我们表明L-Hydra比现有的双曲线嵌入方法更快，并且在节点数量中线性缩放。尽管L-Hydra的嵌入错误高于现有方法的误差，但我们引入了扩展名L-Hydra+，该扩展名在运行时和嵌入质量中都胜过现有方法。
We introduce L-hydra (landmarked hyperbolic distance recovery and approximation), a method for embedding network- or distance-based data into hyperbolic space, which requires only the distance measurements to a few 'landmark nodes'. This landmark heuristic makes L-hydra applicable to large-scale graphs and improves upon previously introduced methods. As a mathematical justification, we show that a point configuration in d-dimensional hyperbolic space can be perfectly recovered (up to isometry) from distance measurements to just d+1 landmarks. We also show that L-hydra solves a two-stage strain-minimization problem, similar to our previous (unlandmarked) method 'hydra'. Testing on real network data, we show that L-hydra is an order of magnitude faster than existing hyperbolic embedding methods and scales linearly in the number of nodes. While the embedding error of L-hydra is higher than the error of existing methods, we introduce an extension, L-hydra+, which outperforms existing methods in both runtime and embedding quality.
