基于地标节点的随机图最短路径距离近似表示 (Landmark-Based Node Representations for Shortest Path Distance Approximations in Random Graphs)

from arxiv, Landmark-based embeddings preserve global distances in graphs more efficiently; on Erdos-Renyi random graphs they need lower dimensions, and GNNs generalize these embeddings to large real-world networks

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.

翻译：学习节点表示是图机器学习中的一个基本问题。现有的嵌入方法虽然能有效保持局部相似性度量，但往往难以捕捉图距离等全局函数。受Bourgin关于度量空间希尔伯特空间嵌入的开创性工作（1985）启发，我们研究了局部距离保持节点嵌入的性能。这类被称为基于地标算法的嵌入方法，通过计算从少量参考节点（称为地标）出发的最短路径来近似成对距离。我们的主要理论贡献表明，与最坏情况图相比，随机图（如Erdos-Renyi随机图）在基于地标的嵌入中需要更低的维度。实证研究表明，基于GNN的地标距离近似方法能够很好地推广到更大的现实世界网络，为图表示学习提供了可扩展且可迁移的替代方案。