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.

Reasoning based on chains of thought (CoTs) enables large language models (LLMs) to solve problems by thinking step by step and becomes the mainstream solution for Question-Answering (QA) tasks. Knowledge graph (KG)-enhanced CoT technology helps correct factual errors or predict reasoning direction. Existing KG-enhanced methods find relevant information in KGs “within” each reasoning step of CoTs. However, in some cases, logical connections “between” reasoning steps may be missing or wrong, leading to broken reasoning chains and wrong reasoning direction. To solve the above problem, we argue that the errors between reasoning steps require collaborative verification and mining of multiple triplets and multiple paths in KG. So we propose the DCMKC (Dual Consistency Matching for KG and CoT) method, aiming to maintain semantic and structural consistency between KG and CoT. The main idea is to convert CoTs and KGs into two granularity-aligned graphs, transforming multi-hop reasoning and KG matching into iterative matching and modification of two graphs. In each iteration, DCMKC matches the KG reasoning chains with CoTs based on semantic similarity and judges the structural consistency between them. Then it modifies CoTs using the matched chains. After iterations, the CoTs and KG reasoning chains reach high semantic and structural consistency, which is theoretically and experimentally demonstrated by kernel and spectral methods. The two kinds of chains are then used to generate the final answers. Experimental results show that our method outperforms baselines on multiple datasets, especially on multi-answer questions, with up to 5.1% improvement over the baseline.