A Spectral Theory of Distortion in LLM Graph Reconstruction: Sharp Bounds and Empirical Characterization

Jianru Shen

cs.LGSep 29, 2026

A Spectral Theory of Distortion in LLM Graph Reconstruction: Sharp Bounds and Empirical Characterization

Authors: Jianru Shen

Organizations: Columbia University New York, NY, USA

Abstract

Evaluations of graph reconstruction by language models typically report a single aggregate distance between the original and the reconstructed graph. We prove that for the Wasserstein distance between Laplacian spectra such a summary is bracketed by two edge counts, the net change in edge number from below and the symmetric difference from above, each scaled by $2/n$ where $n$ is the number of vertices. The bracket is sharp: its two ends coincide exactly when the reconstruction only adds edges or only deletes them, and on that class the distance is a rescaled edge count that says nothing about which edges changed. When the ends differ, the residual between the distance and the lower end is positive only if the reconstruction both invented and lost edges, which turns it into a certificate of mixed editing computable from the reported summaries alone. We characterize these regimes in 135 reconstructions produced by three open-weight models over 45 synthetic graphs. Seventy-seven outputs are one-sided and 29 mixed outputs have $X > 0$ , including cases where edge count is exactly preserved while nineteen edges were simultaneously invented and lost. The three models differ in editing policy, ranging from copying the input to attempting completion at the cost of large hallucination volume, a distinction that aggregate distortion does not reveal.

Figures & tables

Fig. 1: Two reconstructions of community instance g5 ( $n=28$ ); layout and node color are fixed from the original graph, so only the edge sets differ. (a) Original. (b) Preserves the edge count ( $\mathrm{ECR}=1$ ) while adding and deleting $19$ edges each, certified mixed from scalar summaries. (c) Verbatim return of the prompted sublist. EMD and edge-count summaries can thus obscure the edit mechanism; neither reconstruction is implied to be faithful.

Fig. 2: The mixed edit of Example 9 . (a)

G

. (b)

G^{\prime}=K_{4}

minus

\{1,2\}

; hallucinated edges solid red, deleted edge dotted gray. (c) Pointwise dominance without a crossing, attaining the lower bound of ( 3 ). (d) The perturbation spectrum is nonnegative although the edit is mixed.

Edit class	$N$	Lower attained	Upper attained
Sublist returned exactly	57	57	57
Other one-sided	20	20	20
Mixed, dominant	29	29	0
Mixed, certified	29	0	0
Total	135	106	77

TABLE I: Attainment of ( 3 ) by edit class at tolerance

10^{-6}

. The first two rows are one-sided; the last two are mixed.

Fig. 3: Sorted Laplacian spectra for one medium instance per family; crossings mark

X>0

(Proposition 12 ). The two crossing curves are the certified reconstructions of g5 and g22. In g35 the Mistral and Qwen curves coincide (identical edge lists) while the Llama curve is mixed yet spectrally dominated, the one corpus instance whose added and deleted edges are vertex disjoint.

Model	Classes	Recov.	Halluc.	Dropped	$z$
Llama 3.1	9/5/31	34	430	54	$+5.46$
Mistral 7B	12/7/26	46	686	109	$+1.17$
Qwen 2.5	36/8/1	1	3	40	—

TABLE II: Edit policy per model. Classes are exact sublist / other one sided / mixed; recovery is out of 805 withheld edges;

z

is the standardized recovery under the null model of Section III . Qwen’s score is not reported because it emitted only four non-prompt edges.

Model	Community	Scale-free	Grid
Llama 3.1	6/0/9	1/3/11	2/2/11
Mistral 7B	2/5/8	4/0/11	6/2/7
Qwen 2.5	11/3/1	13/2/0	12/3/0

TABLE III: Edit-class composition by model and graph family, as exact sublist / other one-sided / mixed.

Model	Family	Wthld	LLM	Rand	CN	AA	PA
Llama 3.1	Community	386	11	4.2	17.1	17.0	1.8
	Scale-free	225	9	6.9	7.9	10.1	14.8
	Grid	194	14	3.2	0.1	0.1	0.2
Mistral 7B	Community	386	12	8.1	19.4	20.4	6.7
	Scale-free	225	21	21.4	21.8	24.3	33.6
	Grid	194	13	11.1	6.2	6.2	4.1

TABLE IV: Withheld-edge recovery at matched emission volume, averaged over

1{,}000

tie permutations. CN: common neighbors; AA: Adamic–Adar; PA: preferential attachment; Rand: hypergeometric expectation. Bold marks the largest recovery in each row. Qwen is omitted (four non-prompt edges total).

Fig. 4: Mean

\mathrm{EMD}

and cell maximum over 15 outputs per model-family cell. The Qwen row largely tracks the benchmark density profile; the Mistral grid cell is driven by one instance.

Explore similar work

Formalizing and Mitigating Structural Distortion in LLM Attention for Graph Reasoning
Jun 14, 2026Donald Loveland, Puja Trivedi, Ari Weinstein +2LLM Reasoning with Graphs Transformer Attention
University of Michigan Ann Arbor, MI, USA · Amazon Palo Alto, CA, USA
PlanarBench: Evaluating LLM Spatial Reasoning via Planar Graph Drawing
Jun 1, 2026Oleksandr Nikitin, Anna KravchenkoSpatial Reasoning Benchmarks LLM Evaluation
When Graph Language Models Go Beyond Memorization
May 7, 2026Masatsugu Yamada, Mahito SugiyamaGraph Generation Memorization in Language Models
National Institute of Informatics Tokyo, Japan · National Institute of Informatics, Tokyo, Japan · SOKENDAI, Kanagawa, Japan

Jun 14, 2026, cs.LGJ/K move · Enter open · S save

Formalizing and Mitigating Structural Distortion in LLM Attention for Graph Reasoning

Donald Loveland, Puja Trivedi, Ari Weinstein, Edward W Huang+1

University of Michigan Ann Arbor, MI, USA · Amazon Palo Alto, CA, USA

LLM Reasoning with Graphs Transformer Attention Text-Attributed Graph Learning LLM Reasoning LLMs for Graph Learning

Open paper AskPDF arXiv

Large Language Models (LLMs) have shown promise for reasoning over Text-Attributed Graphs (TAGs). However, applying LLMs to graphs requires linearizing their structure into sequences, introducing distortion rooted in the graph bandwidth problem. While this distortion has been shown to degrade performance, it is often attributed to prompt design or model scale, leaving the underlying mechanism unclear. In this work, we show \textit{how} rotary positional embeddings turn graph linearization into bandwidth-dependent attention decay, suppressing attention between graph-adjacent nodes that are forced far apart in the serialized sequence. This shifts the focus of LLM-based graph reasoning from prompt engineering and scaling toward correcting attention misalignment. Motivated by this analysis, we propose \textbf{G}raph-\textbf{a}ligned \textbf{L}anguage \textbf{A}ttention (\textbf{GaLA}), a lightweight, inference-time modification for LLMs. GaLA biases attention toward graph-adjacent nodes while preserving the LLM's sequential inductive biases. Across TAG benchmarks, GaLA improves performance with negligible overhead, demonstrating that distortion is a correctable bottleneck in LLM-based graph reasoning.

Abstract

Explore similar work

Formalizing and Mitigating Structural Distortion in LLM Attention for Graph Reasoning

PlanarBench: Evaluating LLM Spatial Reasoning via Planar Graph Drawing

When Graph Language Models Go Beyond Memorization