通过排列等价编码，揭示自回归图生成器的似然不一致问题。
Same Graph, Different Likelihoods: Calibration of Autoregressive Graph Generators via Permutation-Equivalent Encodings
- 用排列等价序列统一图的线性化方式，提升生成一致性
- 模型在特定顺序下似然更低，但随机排列时校准误差高200倍
- 基于排列的评估比分子稳定性更可靠，适合分子生成质量检验
自回归图生成器通过顺序构建定义似然，但只有在所有图的线性化中保持一致才有意义。近期提出的分段欧拉邻域路径（SENT）将图转化为可被语言模型高效处理的序列，但同一图存在多个等价线性化。本文用等价线性化间负对数似然（NLL）的变异系数衡量似然不一致，称为线性化不确定性（LU）。在两个数据集上对比四种线性化策略训练的Transformer，发现偏好特定顺序的模型在本机顺序下NLL更低，但在随机排列下预期校准误差（ECE）高出两个数量级，表明其学习的是训练顺序而非图本身。在分子图基准QM9上，生成图的NLL与分子稳定性负相关（AUC=0.43），而LU的AUC达0.85，说明基于排列的评估更能可靠判断生成分子质量。
原文摘要 · Abstract (English)
Autoregressive graph generators define likelihoods via a sequential construction process, but these likelihoods are only meaningful if they are consistent across all linearizations of the same graph. Segmented Eulerian Neighborhood Trails (SENT), a recent linearization method, converts graphs into sequences that can be perfectly decoded and efficiently processed by language models, but admit multiple equivalent linearizations of the same graph. We quantify violations in assigned negative log-likelihood (NLL) using the coefficient of variation across equivalent linearizations, which we call Linearization Uncertainty (LU). Training transformers under four linearization strategies on two datasets, we show that biased orderings achieve lower NLL on their native order but exhibit expected calibration error (ECE) two orders of magnitude higher under random permutation, indicating that these models have learned their training linearization rather than the underlying graph. On the molecular graph benchmark QM9, NLL for generated graphs is negatively correlated with molecular stability (AUC $=0.43$), while LU achieves AUC $=0.85$, suggesting that permutation-based evaluation provides a more reliable quality check for generated molecules. Code is available at https://github.com/lauritsf/linearization-uncertainty
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。