Converse and Collision-Based Achievability for Node Localization with Hybrid Distance-Spectral Graph Positional Encodings
Zimo Yan, Yifan Li, Hao Li, Zheng Xie, Chang Liu, Zheming Tu, Yuan Wang
Abstract
Graph positional encodings are widely used in graph neural networks and graph Transformers, yet it remains unclear when the code itself can identify nodes. We study a hybrid distance-spectral encoding that combines anchor-distance profiles with quantized low-frequency Laplacian-energy coordinates. Treating the encoding as an observation map yields a simplex-refined converse, an exact collision factorization \(κ_H=κ_Dκ_{S|D}\), and the collision information \(I_H=-\logκ_D-\logκ_{S|D}\). On random regular graphs, the criterion is made explicit through a bounded-correlation Gaussian-wave surrogate; for actual Laplacian-energy coordinates, we give the distance-conditioned spectral collision condition sufficient for conditional actual-coordinate achievability. Experiments show that \(I_H/\log n\) calibrates localization success, and PE-only structural task probes on Universal Dependencies trees show that hybrid encodings better recover syntactic-tree geometry than distance-only or spectral-only baselines.