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

• URL: http://arxiv.org/abs/2608.30152v1
• Date: Mon, 31 Aug 2026 02:08:39 GMT
• Title: Converse and Collision-Based Achievability for Node Localization with Hybrid Distance-Spectral Graph Positional Encodings
• Abstract summary: We study a hybrid distance-spectral encoding that combines anchor-distance profiles with quantized low-frequency Laplacian-energy coordinates.<n>Treating the encoding as an observation map yields a simplex-refined converse.<n>Experiments show that hybrid encodings better recover syntactic-tree geometry than distance-only or spectral-only baselines.
• Score: 14.222038987314649
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• GLASS: Graph-Language Alignment with Spherical Scoring for Transferable Graph-Level Anomaly Detection [37.05370485421858]
  GLASS builds a unified representation space by aligning a structure-aware graph encoder with an instruction-aware text embedding.<n>Our framework serializes local, global, and semantic graph properties into a compact Graph Descriptor Prompt (GraphDP)<n>For scoring, we formulate anomaly detection as density estimation on the aligned hypersphere.
  arXiv  Detail & Related papers  (2026-09-04T15:16:16Z)
• Tropical Algebraic Geometry for Neuronal Representations: An Arakelov-Green Measure Based Descriptor for Graph Learning [14.563432689352084]
  We propose a training-free geometric prior based on tropical algebraic geometry.<n>We convert spatial trees into cyclic metric graphs suitable for embedding into the Tropical Jacobian.<n>We show that the discrete Arakelov-Green measure, computed in closed form via the graph Laplacian's generalized inverse, decomposes exactly into the intrinsic path metric minus the unquantized polarization distance on this cover.
  arXiv  Detail & Related papers  (2026-08-05T05:34:50Z)
• Scalable Graph Coreset Selection via Greedy Sampling [48.91894218306487]
  We propose a simple and effective column-selective graph sampling algorithm based on a minimum inner product greedy selection rule.<n>We analyze the algorithm under the block model and show that, when the degree distribution is balanced across nodes, the algorithm achieves proportional sampling to cluster size.
  arXiv  Detail & Related papers  (2026-07-30T02:45:31Z)
• Bridging Distance and Spectral Positional Encodings via Anchor-Based Diffusion Geometry Approximation [7.270459013324939]
  Two widely used families are spectral encodings derived from Laplacian or diffusion operators and anchor-based distance encodings built from shortest-path information.<n>We derive an explicit trilateration map that reconstructs truncated diffusion coordinates from transformed anchor distances and anchor spectral positions.<n>On DrugBank molecular graphs using a shared GNP-based DDI prediction backbone, a distance-driven Nystrm scheme closely recovers diffusion geometry.
  arXiv  Detail & Related papers  (2026-01-08T02:31:03Z)
• Resolving Node Identifiability in Graph Neural Processes via Laplacian Spectral Encodings [9.343292907600913]
  We provide theory for a Laplacian positional encoding that is invariant to eigenvector sign flips and to basis rotations within eigenspaces.<n>We prove that this encoding yields node identifiability from a constant number of observations and establish a sample-complexity separation from architectures constrained by the Weisfeiler-Lehman test.
  arXiv  Detail & Related papers  (2025-11-24T12:20:36Z)
• A Spectral Interpretation of Redundancy in a Graph Reservoir [51.40366905583043]
  This work revisits the definition of the reservoir in the Multiresolution Reservoir Graph Neural Network (MRGNN)<n>It proposes a variant based on a Fairing algorithm originally introduced in the field of surface design in computer graphics.<n>The core contribution of the paper lies in the theoretical analysis of the algorithm from a random walks perspective.
  arXiv  Detail & Related papers  (2025-07-17T10:02:57Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• ADA-GAD: Anomaly-Denoised Autoencoders for Graph Anomaly Detection [84.0718034981805]
  We introduce a novel framework called Anomaly-Denoised Autoencoders for Graph Anomaly Detection (ADA-GAD) In the first stage, we design a learning-free anomaly-denoised augmentation method to generate graphs with reduced anomaly levels. In the next stage, the decoders are retrained for detection on the original graph.
  arXiv  Detail & Related papers  (2023-12-22T09:02:01Z)
• Recurrent Distance Filtering for Graph Representation Learning [34.761926988427284]
  Graph neural networks based on iterative one-hop message passing have been shown to struggle in harnessing the information from distant nodes effectively. We propose a new architecture to reconcile these challenges. Our model aggregates other nodes by their shortest distances to the target and uses a linear RNN to encode the sequence of hop representations.
  arXiv  Detail & Related papers  (2023-12-03T23:36:16Z)
• SIGMA: A Structural Inconsistency Reducing Graph Matching Algorithm [21.1095092767297]
  We propose a novel criterion to measure the graph matching accuracy, structural inconsistency (SI) Specifically, SI incorporates the heat diffusion wavelet to accommodate the multi-hop structure of the graphs. We show that SIGMA can be derived by using a mirror descent method to solve the Gromov-Wasserstein distance with a novel K-hop-structure-based matching costs.
  arXiv  Detail & Related papers  (2022-02-06T15:18:37Z)
• Dist2Cycle: A Simplicial Neural Network for Homology Localization [66.15805004725809]
  Simplicial complexes can be viewed as high dimensional generalizations of graphs that explicitly encode multi-way ordered relations. We propose a graph convolutional model for learning functions parametrized by the $k$-homological features of simplicial complexes.
  arXiv  Detail & Related papers  (2021-10-28T14:59:41Z)
• Spectral-Spatial Global Graph Reasoning for Hyperspectral Image Classification [50.899576891296235]
  Convolutional neural networks have been widely applied to hyperspectral image classification. Recent methods attempt to address this issue by performing graph convolutions on spatial topologies.
  arXiv  Detail & Related papers  (2021-06-26T06:24:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.