Converse and Collision-Based Achievability for Node Localization with Hybrid Distance-Spectral Graph Positional Encodings

arXiv:2608.30152v1 Announce Type: new 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_Dkappa_{S|D}), and the collision information (I_H=-logkappa_D-logkappa_{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.

Related

• Full-Spectrum Graph Neural Networks: Expressive and Scalable
• GIST: Gauge-Invariant Spectral Transformers for Scalable Graph Neural Operators
• Enhancing Distance-Based Graph Autoencoders with Structural Penalties for Dynamic Graph Embedding

Source: arXiv cs.LG | 2026-09-01