Converse and Collision-Based Achievability for Node Localization with Hybrid Distance-Spectral Graph Positional Encodings
2026-08-31 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study a special way to label nodes in a graph that mixes distance-based and spectral information to help graph neural networks understand node positions better. They develop a mathematical formula to measure how well this combined labeling can uniquely identify nodes without confusion. Using random graphs and real data, they show their method predicts success in locating nodes accurately. Their experiments suggest that combining both types of information works better for understanding structures like syntactic trees compared to using just one type alone.
graph positional encodinggraph neural networksLaplacian eigenvectorsspectral graph theoryanchor distancecollision factorizationrandom regular graphssyntactic treeslocalizationUniversal Dependencies
Authors
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.