PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zimo Yan, Yifan Li, Hao Li, Zheng Xie, Chang Liu, Zheming Tu, Yuan Wang

arXiv:2608.30152v1cs.LG

TL;DR

The paper addresses when a positional code, rather than a downstream model, can identify graph nodes. It analyzes a hybrid distance-spectral observation map with converse and collision-based criteria, finding that normalized collision information calibrates localization and that hybrid codes better recover syntactic-tree geometry. The actual-Laplacian achievability result remains conditional, and the empirical structural probes are restricted to unlabeled undirected dependency-tree skeletons.

  • Problem

    The paper asks when positional encodings themselves can identify nodes, since downstream performance mixes positional information with architectures, features, optimization, and task correlations.

  • Method

    It treats a hybrid code combining anchor-distance profiles and quantized low-frequency Laplacian-energy coordinates as an observation map.

  • Results

    Hybrid encodings reduce localization error on most graph families, while IH/log n calibrates localization success and hybrid codes better recover syntactic-tree geometry than distance-only or spectral-only baselines.

  • Takeaways & Limitations

    Intrinsic localization information in the positional code aligns with recovery of syntactic-tree geometry in PE-only structural probes.

  • Takeaways & Limitations

    Actual-Laplacian achievability is conditional on a distance-conditioned spectral collision bound, and UD probes use unlabeled undirected dependency-tree skeletons rather than full parsing or language-model fine-tuning.

Abstract

from arXiv · show

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.

I. INTRODUCTION

The paper asks when positional encodings themselves can distinguish graph nodes, and proposes a hybrid distance-spectral framework to analyze and test that question. Its experiments indicate that collision information calibrates localization and that hybrid codes recover syntactic-tree geometry better than single-component baselines.

  • Motivation: Graph positional encodings support relational learning, but their intrinsic ability to distinguish nodes is obscured by architectures, features, and task-specific effects.Spectral encodings also face sign, basis, and stability issues, while distance profiles can collide.
  • Motivation: The central question is when a hybrid graph positional encoding contains enough information to localize nodes.
  • Framework: The hybrid code is treated as an observation map whose fibers contain nodes indistinguishable from positional information alone.This separates intrinsic positional identifiability from downstream architectures, attributes, labels, and optimization effects.
  • Theory: The theory combines a simplex-refined converse with collision-based achievability, including spectral collision bounds conditioned on distance collisions.The converse rules out localization below the log n code-budget scale, while the collision analysis yields κH = κDκS|D and collision information IH.
  • Empirical findings: IH/log n tracks localization success across graph families.The error drops as IH/log n crosses the unit-scale boundary.
  • Empirical findings: Hybrid encodings recover dependency-tree geometry better than distance-only or spectral-only baselines in PE-only probes on Universal Dependencies treebanks.

D. Positional Identifiability and Graph Localization

The localization problem is formulated using only graph structure and a hybrid observation map built from anchor-distance profiles and low-frequency Laplacian-energy coordinates. Counting image size gives a converse, while pairwise collision control supplies the complementary achievability perspective.

  • Problem formulation: The encoding-level problem removes node attributes, edge labels, directions, lexical information, and task-specific features, so equal positional codes are indistinguishable to a code-only decoder.
  • Distance component: Anchor-distance profiles partition vertices into buckets, whose number is D(G, A), the cardinality of the realized profile set.
  • Spectral component: Low-frequency Laplacian-energy coordinates refine distance buckets, with squared coordinates removing sign ambiguity.A fixed eigenbasis convention is used, while repeated eigenspaces can use blockwise projector energy.
  • Observation map: The hybrid positional observation map is analyzed through the optimal conditional localization error for a uniformly sampled source vertex.
  • Two-sided criterion: Small image size implies unavoidable ambiguity, whereas small pairwise collision probability implies successful localization.These are the converse and achievability views of the same observation map.
  • Converse: The simplex-refined converse bounds the number of distance-spectral cells after trimming vertices with excessive spectral energy.It yields a subcritical principle: localization is impossible when the joint anchor, spectral-dimension, and quantization budget remains below the log n scale.

B. Collision-Based Achievability

The hybrid encoding’s achievability is governed by pairwise collisions: distance collisions must be resolved by spectral refinement, with explicit criteria for surrogate and actual Laplacian-energy coordinates.

  • For the hybrid map, a collision requires both an anchor-distance collision and a spectral collision within the same distance bucket.
  • The exact factorization κH = κDκS|D separates distance-collision frequency from conditional spectral resolution.When κD = 0, the distance code already separates all distinct vertex pairs, so κH = 0 under the stated convention.
  • The collision-information condition IH(G, A, m, η) ≥ (1+ε) log n, up to lower-order terms, gives vanishing-error achievability.Collision information is defined with −log 0 = +∞.
  • Random-regular achievability: On random regular graphs, a distance-collision decay bound and bounded-correlation Gaussian-wave anti-concentration yield a closed hybrid achievability theorem.The surrogate models normalized Laplacian coordinates.
  • Conditional actual-coordinate achievability: For actual Laplacian-energy coordinates, achievability instead requires a spectral collision bound conditioned on distance-collision buckets.This avoids requiring a full distributional transfer from the Gaussian-wave surrogate to actual eigenvectors.

D. Two-Sided Localization Criterion

The theory gives a graph-dependent two-sided localization criterion: a simplex-refined code-budget converse rules out localization below the log n scale, while collision information above that scale supports achievability.

  • The simplex-refined converse code budget counts the number of hybrid codes after distance partitioning and spectral quantization.The conservative box budget B2_conv is kept separate from the simplex-counting budget B∆_conv.
  • The graph-dependent design principle identifies two regimes for sequences of hybrid encodings.
  • Localization is impossible when the simplex-refined code budget is below the log n scale.
  • Localization is achievable when total distance-spectral collision information exceeds the log n scale.

V. EMPIRICAL EVALUATION

The empirical evaluation tests the hybrid observation map on synthetic graph families and Universal Dependencies trees, using localization, collision, budget, surrogate, and PE-only structural-probe metrics.

  • Synthetic graph diagnostics: Synthetic diagnostics cover random regular, Erdős–Rényi, stochastic block, grid, and barbell graphs, comparing distance-only, spectral-only, and hybrid encodings.Spectral coordinates include Laplacian and Gaussian-wave variants.
  • Collision diagnostics: Distance-saturated rows with κD = 0 are treated as successful distance-level saturation, with κS|D = 0, κH = 0, and IH = +∞.
  • Universal Dependencies structural task probes: Universal Dependencies probes exclude lexical and edge-side information while evaluating surface position, dependency depth, and pairwise dependency distance from positional encodings.The study uses English-EWT, Chinese-GSD, Spanish-GSD, French-GSD, and German-GSD trees with 6 ≤ n ≤ 80.
  • Metrics: The experiments report image-size success rate, induced localization error, normalized collision information IH/log n, budget diagnostics, and Gaussian-wave discrepancies.

B. Mathematical Localization and Surrogate-Discrepancy Diagnostics

The diagnostics evaluate localization through collision information and a conservative converse budget across graph families, with validation spanning held-out graph instances. Hybrid Laplacian-energy encodings generally improve localization, while bottleneck graphs expose surrogate-transfer and subcritical-information limitations.

  • Family-level localization: Hybrid Laplacian-energy encodings reduce average error relative to distance-only encoding by 63.9% to 80.6% on random regular, ER, SBM, and grid graphs.Barbell graphs remain a contrasting failure case, with hybrid error close to distance-only error and subcritical information.
  • Collision decomposition: Mean localization error drops from 0.515 in the low-information regime to 0.003 in the high-information regime.The regime split is defined by the information ratio I_H/log n.
  • Surrogate-discrepancy diagnostics: Surrogate discrepancy is smallest on expander-like graphs and larger on bottleneck graphs, reaching 1.240 for energy coordinates and 1.520 for signed coordinates on barbells.These discrepancies do not by themselves establish the conditional spectral-collision assumption for actual coordinates.
  • Unified design diagnostics: The achievability-side rule I_H/log n ≥ 1 predicts localization success with precision 0.930 and recall 0.9998 for Err∗(F) ≤ 0.1.Across 25,256 configurations, the relaxed Err∗(F) ≤ 0.2 threshold yields precision 0.990 and recall 0.991.
  • Unified design diagnostics: The converse-side rule B2_conv/log n < 1 identifies Err∗(F) ≥ 0.9 configurations with recall 0.975 but precision 0.340.The joint region B2_conv/log n < 1 and I_H/log n < 1 has mean error 0.829 and median error 0.850.
  • Held-out validation: I_H/log n remains a stable success-side diagnostic under graph-clustered validation and threshold transfer across unseen graph families, settings, and sizes.The expanded sweep contains 129,360 configurations from 210 graph-instance clusters.

C. Real-graph structural task probes on Universal Dependencies

The UD experiments use PE-only probes to test whether positional codes recover syntactic-tree geometry, while controls isolate node-code alignment from marginal PE statistics. Hybrid encodings show their clearest advantages on depth and pairwise-distance recovery.

  • Protocol: The benchmark uses five UD treebanks and compares NoPE, distance-only anchor codes, Laplacian-energy codes, and hybrid distance-energy codes.Inputs exclude lexical forms, dependency labels, edge directions, and token attributes, so probes use positional codes alone.
  • Protocol: The three probes predict normalized token order, dependency depth, and clipped pairwise dependency distance from positional codes.Position and depth use NMAE, while pairwise distance uses macro-F1.
  • Main results: HybridEnergy reduces surface-position average NMAE from 0.262 to 0.257, a modest gain because undirected dependency skeletons only partially determine word order.The surface-position configuration is reused without new hyperparameter search for the additional probes.
  • Main results: HybridEnergy achieves the best depth NMAE and pairwise-distance macro-F1, outperforming both distance-only and spectral-energy encodings.The result supports complementary contributions from anchor distances and Laplacian-energy coordinates.
  • Controls: HybridEnergy has the larger alignment-specific margin across all three probes after PE-row derangement removes token-code alignment while preserving marginal PE statistics.The control preserves sentence-level statistics, feature dimension, and code budget.
  • Ablations: Farthest anchors give the best localization and surface-position recovery, while coarser quantization lowers IH/log n and slightly increases collision error.Probe performance remains stable for η ≤0.5 and weakens mildly at η = 1.0.

APPENDIX A THEORETICAL DERIVATIONS

The appendix derives the deterministic image-size and collision results underlying the localization theory. It specializes the converse to random regular graphs and establishes an exact distance–spectral collision factorization without independence assumptions.

  • Simplex-refined converse: The appendix first proves a deterministic image-size bound for hybrid observation maps, then specializes it using logarithmic diameter control for random regular graphs.The proof counts trimmed vertices and quantized spectral codes, while bounding the distance component by the graph diameter.
  • Random-regular specialization: The random-regular corollary uses the standard diameter estimate to derive a subcritical code-budget condition below the log n scale.The remaining O(k_n) + O(m_n) terms are absorbed under the stated slack and m_n = o(log log n) assumptions.
  • Collision factorization: Hybrid collisions decompose exactly into distance collisions and residual spectral collisions within distance buckets.The factorization is obtained by partitioning vertices according to their anchor-distance profiles.
  • Localization criterion: The collision bound converts the factorization into a two-sided localization criterion based on the hybrid collision information.The converse rules out localization under insufficient code budget, while collision decay supplies achievability conditions.

2) Equal-distance representation for random anchors:

For random anchors, equal-distance vertices are characterized through the set of graph vertices that distinguish a pair. Random-regular graph distinguisher bounds provide the high-probability control needed for distance-collision analysis.

  • Equal-distance representation: For a uniformly sampled anchor set, the probability of an equal-distance anchor profile is governed by the number of vertices in Eq_G(u,v).The representation converts random-anchor collisions into a sampling problem over equal-distance vertices.
  • Equal-distance representation: The equal-distance representation defines Eq_G(u,v) as vertices equidistant from u and v.This set identifies anchors that fail to distinguish the pair.
  • Random-regular distinguisher bound: Random regular graphs have, with high probability, at least 3n/log n strong distinguishers for every non-adjacent vertex pair.A union bound transfers the fixed-pair estimate to all relevant pairs.
  • Random-regular distinguisher bound: The distinguisher estimate is transferred from the configuration model to uniform simple random regular graphs by conditioning on simplicity.For fixed r ≥3, the configuration model is simple with probability bounded away from zero.

2) Equal-distance moment decay:

The equal-distance moment analysis combines non-adjacent-pair distinguisher bounds with separate control of adjacent pairs. This yields high-probability decay of distance collisions for random anchors.

  • Moment decomposition: The moment calculation separates adjacent from non-adjacent ordered vertex pairs because the distinguisher bound applies directly to non-adjacent pairs.Adjacent pairs are controlled through their sampling probability and contribution to the overall moment.
  • Moment decay: For non-adjacent pairs, every strong distinguisher lies outside the equal-distance set, producing decay in the equal-distance moment.The argument conditions on the high-probability random-regular event established earlier.
  • Moment decay: Combining adjacent-pair control with the non-adjacent two-source estimate gives the required moment bound for sufficiently large n.The proof uses the relation between distinguishers, equal-distance vertices, and random-anchor sampling.
  • Distance-collision corollary: Markov’s inequality converts the moment estimate into a high-probability decay statement for distance collisions under random anchors.The resulting corollary holds with probability tending to one as n →∞.

4) Gaussian-wave surrogate model:

The Gaussian-wave surrogate models spectral energy coordinates with independent, bounded-correlation Gaussian fields. Its anti-concentration analysis supplies high-probability spectral collision bounds that yield hybrid localization achievability on random regular graphs.

  • Surrogate definition: The surrogate uses centered Gaussian fields with bounded correlation, independent across spectral coordinates, then forms squared-energy and quantized spectral codes.These assumptions support coordinate-wise collision control for the hybrid observation map.
  • Anti-concentration: A one-dimensional small-ball estimate for squared correlated Gaussians is the main ingredient in the spectral anti-concentration proof.The density analysis controls the probability that quantized squared coordinates collide.
  • Anti-concentration: The Gaussian-wave spectral anti-concentration theorem converts bounded correlation and quantization into a conditional bound on within-distance-bucket spectral collisions.The resulting statement holds with conditional probability at least 1 −e^−ωs,n.
  • Achievability: Combining distance and spectral collision events with the exact hybrid factorization yields a high-probability collision-achievability criterion for Gaussian-wave observation maps.The criterion is applied conditionally on the graph and anchor set, with constants depending on the graph degree and correlation bound.

9) Laplacian achievability under an actual spectral collision bound:

For actual Laplacian-energy coordinates, achievability is obtained by imposing a spectral collision bound conditional on distance collisions rather than transferring the full Gaussian-wave distribution. The resulting criterion is graph-dependent and is supported by synthetic localization diagnostics across several graph families.

  • Actual-coordinate criterion: Actual-coordinate achievability requires a spectral collision bound conditioned on distance collisions, without requiring full distributional transfer from the Gaussian-wave surrogate.This separates the surrogate theorem from the condition needed for actual Laplacian-energy coordinates.
  • Actual-coordinate criterion: The hybrid collision factorization combines the distance collision term with the conditional actual-spectral collision term to obtain the achievability bound.The appendix derives the bound from the simplex-refined converse and the collision factorization.
  • Experimental setting: The synthetic experiment evaluates random regular, Erdős-Rényi, stochastic block model, grid, and barbell graphs across multiple spectral variants and anchor configurations.Non-grid settings use n ∈{500, 1000, 2000}, grids use n ∈{529, 1024, 2025}, and each configuration uses 10 graph trials.

C. UD probe protocol

The UD protocol tests whether PE codes alone recover surface position, dependency depth, and pairwise dependency distance from unlabeled dependency-tree skeletons. HybridEnergy generally improves structural recovery, while cross-tree coordinate stability and graph-dependent collision geometry remain important.

  • Probe tasks: PE-only probes predict normalized surface position, normalized dependency-root depth, and clipped pairwise dependency distance from the encoding representation.HybridEnergy concatenates normalized anchor-distance features with quantized Laplacian-energy bins; NoPE uses a constant feature.
  • Surface-position results: The selected HybridEnergy surface-position probe improves over NoPE by 0.0055 NMAE on average, a 2.08% relative reduction, and improves Kendall-τ by 0.118.Its average NMAE improvements over Distance-only and SpectralEnergy are 1.27% and 0.33%, respectively.
  • Cross-probe results: HybridEnergy has the larger alignment-specific margin on all three probes, indicating advantages beyond sentence-level PE marginal statistics.Configuration-level diagnostics associate higher IH/ log n with larger gains over NoPE and low-collision, higher-rank-recovery regimes.
  • Ablations: Signed coordinates reduce within-tree collisions and increase IH/ log n but do not improve probe accuracy, suggesting cross-sentence coordinate stability is also required.Exact within-tree separability alone is therefore not sufficient for cross-sentence structural prediction.
  • Ablations: Coarser quantization reduces IH/ log n and mildly increases Err∗(F), while probe performance remains stable for η ≤0.5 and weakens mildly at η = 1.0.This indicates limited sensitivity to small quantization changes once the code remains sufficiently resolved.
Loading 2608.30152v1…