用关键点嵌入法高效近似随机图的最短路径距离
Landmark-Based Node Representations for Shortest Path Distance Approximations in Random Graphs
- 通过选取少量参考节点（地标）计算路径距离，实现局部距离保持
- 随机图中所需嵌入维度低于最坏情况图，理论优势明显
- 基于GNN的地标距离近似在真实网络上表现良好，可迁移性强
图机器学习中的节点表示学习是基础问题。现有嵌入方法虽能有效保留局部相似性，却难以捕捉全局函数如图距离。受Bourgain（1985）关于度量空间到希尔伯特空间嵌入的开创性工作启发，我们研究了基于地标（landmark-based）的局部距离保持嵌入方法。这类方法通过计算节点到少量参考节点（地标）的最短路径来近似任意两点间距离。我们的主要理论贡献表明，对于埃拉托斯特尼-随机图（Erdos-Renyi random graphs）等随机图，所需嵌入维度显著低于最坏情况下的图。实验证明，基于图神经网络（GNN）对地标距离的近似在更大规模的真实世界网络中具有良好泛化能力，为图表示学习提供了一种可扩展且可迁移的替代方案。
原文摘要 · Abstract (English)
Learning node representations is a fundamental problem in graph machine learning. While existing embedding methods effectively preserve local similarity measures, they often fail to capture global functions like graph distances. Inspired by Bourgain's seminal work on Hilbert space embeddings of metric spaces (1985), we study the performance of local distance-preserving node embeddings. Known as landmark-based algorithms, these embeddings approximate pairwise distances by computing shortest paths from a small subset of reference nodes called landmarks. Our main theoretical contribution shows that random graphs, such as Erdos-Renyi random graphs, require lower dimensions in landmark-based embeddings compared to worst-case graphs. Empirically, we demonstrate that the GNN-based approximations for the distances to landmarks generalize well to larger real-world networks, offering a scalable and transferable alternative for graph representation learning.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。