Converse and Collision-Based Achievability for Node Localization with Hybrid Distance-Spectral Graph Positional Encodings
TL;DR
A hybrid distance-spectral encoding that combines anchor-distance profiles with quantized low-frequency Laplacian-energy coordinates is studied, showing that hybrid encodings better recover syntactic-tree geometry than distance-only or spectral-only baselines.
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 \(\kappa_H=\kappa_D\kappa_{S|D}\), and the collision information \(I_H=-\log\kappa_D-\log\kappa_{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.
