Paper Overview
Field: Machine Learning Author: Jianru Shen Posted: 2026-09-29 arXiv: 2609.38161
Summary
Evaluations of graph reconstruction by language models typically report a single aggregate distance between the original and the reconstructed graph. The author proves 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. This turns the residual into a certificate of mixed edits, computable from reported summaries alone.
Empirical Findings
The paper characterizes these patterns on 135 reconstructions of 45 synthetic graphs produced by three open-weight language models:
- 77 outputs were single-sided (only additions or only deletions).
- 29 mixed outputs had a positive residual \(X > 0\), including a case where the edge count was exactly preserved while 19 edges were simultaneously invented and lost.
- The three models differ in edit strategy, ranging from copying the input to attempting completion at the cost of substantial hallucination — a difference that aggregate distortion metrics cannot reveal.
Why It Matters
The result provides a simple diagnostic tool: evaluators can detect whether an LLM's graph reconstruction mixed hallucinated edges with lost edges using only the spectral Wasserstein distance and edge counts, without access to the full graph.
--- *Auto-collected on 2026-10-01*