Information-Theoretic Limits of Node Localization under Hybrid Graph Positional Encodings
This addresses the problem of understanding when positional encodings can uniquely identify nodes in graphs, which is crucial for graph learning models, though it is incremental in providing theoretical limits rather than a new method.
The paper tackled the fundamental identifiability of node localization under hybrid positional encodings combining anchor-distance profiles and quantized spectral features, establishing an information-theoretic impossibility regime and showing empirical crossover on random 3-regular graphs and graph-dependent identifiability on real-world DDI graphs.
Positional encoding has become a standard component in graph learning, especially for graph Transformers and other models that must distinguish structurally similar nodes, yet its fundamental identifiability remains poorly understood. In this work, we study node localization under a hybrid positional encoding that combines anchor-distance profiles with quantized low-frequency spectral features. We cast localization as an observation-map problem whose difficulty is controlled by the number of distinct codes induced by the encoding and establish an information-theoretic converse identifying an impossibility regime jointly governed by the anchor number, spectral dimension, and quantization level. Experiments further support this picture: on random $3$-regular graphs, the empirical crossover is well organized by the predicted scaling, while on two real-world DDI graphs identifiability is strongly graph-dependent, with DrugBank remaining highly redundant under the tested encodings and the Decagon-derived graph becoming nearly injective under sufficiently rich spectral information. Overall, these results suggest that positional encoding should be understood not merely as a heuristic architectural component, but as a graph-dependent structural resolution mechanism.