Same Graph, Different Likelihoods: Calibration of Autoregressive Graph Generators via Permutation-Equivalent Encodings

Laurits Fredsgaard; Aaron Thomas; Michael Riis Andersen; Mikkel N. Schmidt; Mahito Sugiyama

cs.LGApr 7, 2026

Same Graph, Different Likelihoods: Calibration of Autoregressive Graph Generators via Permutation-Equivalent Encodings

Authors: Laurits Fredsgaard, Aaron Thomas, Michael Riis Andersen, Mikkel N. Schmidt, Mahito Sugiyama

Organizations: Technical University of Denmark · University of Birmingham · National Institute of Informatics

Abstract

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

Figures & tables

		NLL/token ↓		Linearization Uncertainty ↓		ECE ↓
Strategy	Tok/graph	Native	Random	Native	Random	Native	Random
Random	$88.9$	$0.336_{\pm 0.001}$	$0.336_{\pm 0.001}$	$0.083_{\pm 0.000}$	$0.083_{\pm 0.000}$	$0.000_{\pm 0.000}$	$0.000_{\pm 0.000}$
Min-Degree	$79.0$	$0.250_{\pm 0.000}$	$1.564_{\pm 0.028}$	$0.049_{\pm 0.000}$	$0.383_{\pm 0.007}$	$0.001_{\pm 0.000}$	$0.171_{\pm 0.000}$
Max-Degree	$98.7$	$0.244_{\pm 0.000}$	$2.240_{\pm 0.057}$	$0.039_{\pm 0.000}$	$0.277_{\pm 0.006}$	$0.002_{\pm 0.000}$	$0.205_{\pm 0.006}$
Anchor	$95.6$	$0.222_{\pm 0.000}$	$2.246_{\pm 0.033}$	$0.027_{\pm 0.000}$	$0.217_{\pm 0.005}$	$0.001_{\pm 0.000}$	$0.245_{\pm 0.004}$

Table 1: Test-set robustness on QM9 (

K{=}32

permutations, full test set, 3 seeds). Native = model’s own training strategy; Random = evaluated under the Random Order strategy.

Strategy	(Gen.)	(Resamp.)	(Gen.)	(Resamp.)	Lin. Unc. ↓
	Tok/graph		NLL ↓
Random	$127.1_{\pm 0.4}$	$89.3_{\pm 0.2}$	$29.383_{\pm 0.007}$	$30.361_{\pm 0.049}$	$0.085_{\pm 0.000}$
Min-Degree	$112.9_{\pm 0.5}$	$79.2_{\pm 0.2}$	$19.162_{\pm 0.035}$	$19.781_{\pm 0.026}$	$0.055_{\pm 0.000}$
Max-Degree	$140.9_{\pm 0.3}$	$98.7_{\pm 0.2}$	$23.458_{\pm 0.042}$	$23.839_{\pm 0.052}$	$0.041_{\pm 0.000}$
Anchor	$136.2_{\pm 0.3}$	$95.4_{\pm 0.2}$	$20.682_{\pm 0.055}$	$21.166_{\pm 0.037}$	$0.031_{\pm 0.000}$

Table 2: Model self-assessment of generated sequences on QM9 (3-seed mean

{}_{\pm\text{std}}

, valid molecules only). Gen. = model’s own generated trajectory; Resamp. = same molecule re-linearized via the native strategy (

K{=}32

Figure 1: LU AUC vs. number of permutations $K$ (QM9). ROC-AUC for predicting molecular stability from LU, per linearization strategy (mean $\pm$ std across 3 seeds). Even at $K{=}2$ the signal far exceeds the Generation NLL baseline (AUC $=0.43$ ).

Appendix figures & tables9 assets

Supplementary material from the paper’s appendix.

Appendix

Strategy	Validity ↑	Unique ↑	Novelty ↑*	Atm. Stable ↑	Mol. Stable ↑	FCD ↓	PGD ↓
Random	$98.6_{\pm 0.1}$	$97.3_{\pm 0.2}$	$46.0_{\pm 1.2}$	$98.6_{\pm 0.0}$	$87.2_{\pm 0.3}$	$0.067_{\pm 0.002}$	$0.515_{\pm 0.007}$
Min-Degree	$98.6_{\pm 0.0}$	$96.9_{\pm 0.2}$	$37.0_{\pm 0.9}$	$98.5_{\pm 0.0}$	$87.2_{\pm 0.1}$	$0.042_{\pm 0.002}$	$0.513_{\pm 0.002}$
Max-Degree	$98.8_{\pm 0.0}$	$96.7_{\pm 0.1}$	$29.9_{\pm 1.0}$	$98.5_{\pm 0.0}$	$87.0_{\pm 0.2}$	$0.040_{\pm 0.001}$	$0.505_{\pm 0.002}$
Anchor	$98.7_{\pm 0.2}$	$96.8_{\pm 0.2}$	$36.9_{\pm 0.6}$	$98.5_{\pm 0.0}$	$86.8_{\pm 0.3}$	$0.049_{\pm 0.002}$	$0.506_{\pm 0.010}$

Appendix

Table 3: Generative quality on QM9 (3-seed mean

{}_{\pm\text{std}}

; 10,000 generated molecules per model). Metric definitions in Appendix A .

Figure 2: Overfitting vs. Generative Quality in Data-Scarce Regimes. Dual-axis plot showing validation NLL/token (solid, left axis) and VUN (dashed, right axis) for Planar ( $N{=}128$ , seed 0). For all biased strategies, NLL rises after $\sim$ 5k steps (memorization) while VUN continues to climb, driven by Validity alone. Only Random Order achieves sustained improvement in both axes. See Appendix D.2 for the decomposition of VUN into Validity, Uniqueness, and Novelty.

Figure 3: QM9 subset-size sweep (mean $\pm$ std, 3 seeds). Generative quality across $N_{\mathrm{train}}\in\{128,1000,10000\}$ . Uniqueness collapses for biased strategies at small $N$ , recovering only at $N{=}10{,}000$ . Novelty remains consistently lower for biased strategies at all sizes.

Figure 4: Decomposition of VUN into Validity, Uniqueness, and Novelty (Planar, $N{=}128$ , seed 0). Each panel shares the NLL curve (faded solid lines, left axis) with the main figure. Validity (left): Min-Degree First is the only strategy where Validity visibly suffers, indicating incomplete grammar acquisition. Uniqueness (center): all biased strategies generate repeated outputs over time, with Anchor Expansion degrading most. Novelty (right): biased strategies reproduce training examples, with Anchor Expansion collapsing to $\sim$ 60%. Random Order sustains 100% across all three components throughout training.

Figure 5: Full Diversity Saturation Grid. Diversity metrics across Planar (top), QM9 Subset (middle), and QM9 Full (bottom). Random Order maintains higher sequence diversity across all scales; biased strategies saturate early.

Figure 6: Full cross-evaluation breakdown (QM9, $K{=}32$ , 3-seed mean $\pm$ std). Rows = training strategy; columns = evaluation strategy. Diagonal cells (native evaluation) are well-calibrated and low-NLL for all strategies. Off-diagonal cells expose the “specialist” brittleness of biased strategies: NLL/tok, linearization uncertainty, and ECE all increase substantially when the evaluation ordering differs from the training ordering. Random order (top row/column) is the most robust across all metrics. Among ECE token types, Revisit tokens show the largest absolute calibration failure for biased strategies evaluated off-diagonal, confirming that these models exploit topological sorting cues to resolve cycle-closing decisions.

Figure 7: Per-molecule stability prediction from permutation-based metrics (QM9). Each bar shows mean $\pm$ std across 4 strategies $\times$ 3 seeds. Top : Spearman correlation with molecular stability. Bottom : ROC-AUC for binary stability prediction. Generation NLL is negatively correlated with stability; LU achieves AUC $=0.85$ .

Figure 8: QM9: Sequence Length Distribution (Test Set vs. Generated). Distribution of sequence lengths for algorithmically-linearized QM9 test graphs and model-generated sequences. Generated sequences are systematically longer across all strategies.

Figure 9: Mechanistic Analysis of Sequence Length. Top: Distribution of chordal back-references per molecule for test graphs and model-generated sequences (across 3 seeds). Despite similar node and edge counts, model-generated sequences incur

\approx 2\times

more back-references, explaining the length gap in Table 2 . Bottom: Mean trail-length profile as a function of relative sequence position. Solid lines = algorithmically-resampled test sequences per strategy; dashed lines = generated sequences. Generated sequences consistently front-load large trails compared to algorithmically sampled linearizations.

Autoregressive Generation

Autoregressive generation creates structured outputs step by step, conditioning each prediction on what has already been generated.

See all 109 papers

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models
Jun 2, 2026Alessio Barboni, Massimiliano Lupo Pasini, Bishal Lakha +1Graph Generation Generative Modeling
Boise State University Boise, Idaho, USA · Oak Ridge National Laboratory Oak Ridge, Tennessee, USA
GraphVQ: Structure-Aware Autoregressive Decoding over Context-Quantized Graph Tokens
Sep 29, 2026Yuxiang Yao, Zijun ZhaoAutoregressive Generation Graph Foundation Models
Research Center, China Life Insurance Company Ltd. · School of Computer Science and Technology Beijing Institute of Technology
GraViti: Graph-Level Variational Autoencoders with Relaxed Permutation Invariance
May 15, 2026Roman Bresson, Konstantinos Divriotis, Johannes F. Lutzeyer +2Molecular Generation Molecular Representation Learning
Mohamed bin Zayed University of Artificial Intelligence · LIX, CNRS, École Polytechnique, IP Paris

Jun 2, 2026J/K move · Enter open · S save

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models

Alessio Barboni, Massimiliano Lupo Pasini, Bishal Lakha, Edoardo Serra

Boise State University Boise, Idaho, USA · Oak Ridge National Laboratory Oak Ridge, Tennessee, USA

Graph Generation Generative Modeling Autoregressive Generation

Open paper AskPDF arXiv

Generating realistic and diverse graphs is a key problem in machine learning, with applications in molecular discovery, circuit design, cybersecurity, and beyond. However, current graph generative models remain limited by scalability and novelty. Diffusion-based methods often require costly full-adjacency operations and long denoising chains, while many autoregressive and hybrid models have at least quadratic complexity. In addition, these models often imitate training graphs rather than generalize beyond them. We propose a lightweight autoregressive framework to address these issues. It uses a structure-guided topological ordering to serialize graphs into regular edge sequences, enabling near log-linear generation, and a two-phase training strategy that combines exploration-oriented augmentation with iterative refinement to reduce overfitting and promote controlled novelty. Experiments on molecular and non-molecular benchmarks show that our approach improves novelty while preserving high validity and uniqueness. The framework also supports both LSTM and Mamba-style causal sequence backbones, with large-memory accelerators enabling longer graph-sequence experiments beyond typical GPU limits.

Abstract

Autoregressive Generation

Explore similar work

Scaling Novel Graph Generation via Lightweight Structure-Guided Autoregressive Models

GraphVQ: Structure-Aware Autoregressive Decoding over Context-Quantized Graph Tokens

GraViti: Graph-Level Variational Autoencoders with Relaxed Permutation Invariance