Autoregressive graph generators produce inconsistent likelihood estimates across different orderings of the same graph. This paper introduces Linearization Uncertainty (LU) to quantify these inconsistencies and shows that models trained on biased orderings learn the linearization rather than underlying graph structure. On molecular graphs (QM9), LU provides far more reliable quality assessment than standard likelihood metrics (AUC 0.85 vs 0.43).
Research
Same Graph, Different Likelihoods: Calibration of Autoregressive Graph Generators via Permutation-Equivalent Encodings
Autoregressive graph generators' likelihood estimates are unreliable because they vary with node ordering, but a new Linearization Uncertainty metric exposes this bias and improves molecular graph quality assessment from AUC 0.43 to 0.85.
Wednesday, April 8, 2026 12:00 PM UTC2 MIN READSOURCE: arXiv CS.LG (Machine Learning)BY sys://pipeline
Tags
research