Graph-based NLP and symbolic reasoning models often rely on positional encodings to distinguish tokens, entities, or reasoning states, but the identifiability provided by these encodings remains poorly understood. We analyze a hybrid graph encoding that combines anchor distances with quantized low-frequency spectral energy. Treating the encoding as a deterministic observation map gives an exact image-preimage identity for localization ambiguity and a one-sided information-theoretic converse: if the joint anchor, spectral, and quantization budget is too small, distinct nodes must share the same code, which also lower-bounds task-label ambiguity observable from that code. Experiments on random 3-regular graphs, CLUTRR relation graphs, and Universal Dependencies trees support the predicted scaling. Under matched normalized budgets, Hybrid is best or tied at 74 of 87 attained thresholds, while PE-only UD probes show improved recovery of syntactic-tree geometry. The results therefore position positional encoding as a pre-model, encoding-level necessary-condition diagnostic rather than an achievability guarantee or an end-to-end model claim.

Molecular graph learning benefits from positional signals that capture both local neighborhoods and global topology. Two widely used families are spectral encodings derived from Laplacian or diffusion operators and anchor-based distance encodings built from shortest-path information, but the relationship between them is still not well understood. In this paper, we study when anchor-based distance encodings can approximate diffusion geometry. Under a random r-regular graph model, we derive an explicit trilateration map that reconstructs truncated diffusion coordinates from transformed anchor distances and anchor spectral positions, together with pointwise and Frobenius-gap guarantees. On DrugBank with a shared GNP-based DDI backbone, anchor-distance Nyström accurately recovers diffusion geometry, and both DE and LapPE outperform models without positional encodings, with LapPE showing slightly more consistent performance.