mlsanityData to 7 Oct 2026

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

arXiv 2608.30152 ↗First posted 31 Aug 2026cs.LGcited by 0

Not on the map. Why?

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.

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

Builds on

30 of 41 references.

References · 30

  1. 2018How Powerful are Graph Neural Networks?cited by 4,355
  2. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  3. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 702
  4. 2020Benchmarking Graph Neural Networkscited by 672
  5. 2021Rethinking Graph Transformers with Spectral Attentioncited by 468
  6. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 326
  7. 2017struc2vec: Learning Node Representations from Structural Identitycited by 214
  8. 2019Position-aware Graph Neural Networkscited by 203
  9. 2022Structure-Aware Transformer for Graph Representation Learningcited by 191
  10. 2022Pure Transformers are Powerful Graph Learnerscited by 188
  11. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  12. 2023Exphormer: Sparse Transformers for Graphscited by 166
18 more
  1. 2019CLUTRR: A Diagnostic Benchmark for Inductive Reasoning from Textcited by 155
  2. 2023Graph Inductive Biases in Transformers without Message Passingcited by 150
  3. 2017Encoding Sentences with Graph Convolutional Networks for Semantic Role Labelingcited by 137
  4. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  5. 2017Learning Structural Node Embeddings Via Diffusion Waveletscited by 97
  6. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  7. 2022GRPE: Relative Positional Encoding for Graph Transformercited by 67
  8. 2023Transformers Meet Directed Graphscited by 39
  9. 2022Rewiring with Positional Encodings for Graph Neural Networkscited by 35
  10. 2023Graph Positional and Structural Encodercited by 31
  11. 2023On the Stability of Expressive Positional Encodings for Graphscited by 31
  12. 2023Graph Positional Encoding via Random Feature Propagationcited by 30
  13. 2023Laplacian Canonization: A Minimalist Approach to Sign and Basis Invariant Spectral Embeddingcited by 21
  14. 2024Comparing Graph Transformers via Positional Encodingscited by 20
  15. 2024What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encodingcited by 14
  16. 2023What functions can Graph Neural Networks compute on random graphs? The role of Positional Encodingcited by 11
  17. 2023Cycle Invariant Positional Encoding for Graph Representation Learningcited by 8
  18. 2021A Simple Algorithm for Graph Reconstructioncited by 3

Built on by

Not cited yet.