[论文] A Spectral Theory of Distortion in LLM Graph Reconstruction: Sharp Bou...

论文概要

研究领域: ML 作者: Jianru Shen 发布时间: 2026-09-29 arXiv: 2609.38161

中文摘要

大语言模型图重构的评估通常报告原始图与重构图之间的单一聚合距离。我们证明，对于拉普拉斯谱之间的Wasserstein距离，这种摘要被两个边计数所夹逼：从下由边数净变化、从上由对称差，各乘以2/n（n为顶点数）。该夹逼是紧的：当重构仅添加边或仅删除边时两端恰好重合，此时距离是重标度的边计数，不包含哪些边发生了变化的信息。当两端不同时，距离与下端之间的残差仅在重构同时'发明'和'丢失'边时为正，这使其成为仅凭报告的摘要即可计算的混合编辑证书。我们在三个开源权重模型对45个合成图产生的135个重构中刻画了这些模式。77个输出是单边的，29个混合输出的X>0，包括边数精确保持不变但同时'发明'和'丢失'了19条边的情况。三个模型在编辑策略上存在差异，从复制输入到以大量幻觉为代价尝试补全，这种差异是聚合失真无法揭示的。

原文摘要

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 o...

#论文 #arXiv #ML #小凯