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

arXiv: https://arxiv.org/abs/2608.30152 · HTML: https://mlsanity.com/paper/2608.30152/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 41 references that are in the map.
- First posted on arXiv 31 Aug 2026.

## Builds on (most cited first, 30 of 30)

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [struc2vec: Learning Node Representations from Structural Identity](https://mlsanity.com/paper/1704.03165/) (2017)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [Structure-Aware Transformer for Graph Representation Learning](https://mlsanity.com/paper/2202.03036/) (2022)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Exphormer: Sparse Transformers for Graphs](https://mlsanity.com/paper/2303.06147/) (2023)
- [CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Text](https://mlsanity.com/paper/1908.06177/) (2019)
- [Graph Inductive Biases in Transformers without Message Passing](https://mlsanity.com/paper/2305.17589/) (2023)
- [Encoding Sentences with Graph Convolutional Networks for Semantic Role Labeling](https://mlsanity.com/paper/1703.04826/) (2017)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Learning Structural Node Embeddings Via Diffusion Wavelets](https://mlsanity.com/paper/1710.10321/) (2017)
- [Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks](https://mlsanity.com/paper/2203.00199/) (2022)
- [GRPE: Relative Positional Encoding for Graph Transformer](https://mlsanity.com/paper/2201.12787/) (2022)
- [Transformers Meet Directed Graphs](https://mlsanity.com/paper/2302.00049/) (2023)
- [Rewiring with Positional Encodings for Graph Neural Networks](https://mlsanity.com/paper/2201.12674/) (2022)
- [Graph Positional and Structural Encoder](https://mlsanity.com/paper/2307.07107/) (2023)
- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Graph Positional Encoding via Random Feature Propagation](https://mlsanity.com/paper/2303.02918/) (2023)
- [Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embedding](https://mlsanity.com/paper/2310.18716/) (2023)
- [Comparing Graph Transformers via Positional Encodings](https://mlsanity.com/paper/2402.14202/) (2024)
- [What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding](https://mlsanity.com/paper/2406.01977/) (2024)
- [What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding](https://mlsanity.com/paper/2305.14814/) (2023)
- [Cycle Invariant Positional Encoding for Graph Representation Learning](https://mlsanity.com/paper/2311.14333/) (2023)
- [A Simple Algorithm for Graph Reconstruction](https://mlsanity.com/paper/2112.04549/) (2021)

## Abstract (arXiv)

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 (kappaH=kappaDkappaS|D), and the collision information (IH=-logkappaD-logkappaS|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 (IH/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.