Laurits Fredsgaard, Aaron Thomas, Michael Riis Andersen, Mikkel N. Schmidt, Mahito Sugiyama
5 min
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
Alex: So LU flags when the model's surprise score bounces around for the same graph under different paths. That makes sense—like faulty scales revealing the tool's problem, not the apple's.
Sam: Precisely. The paper tests this on models trained with different traversal strategies, like always starting from central hubs or low-degree spots. Biased strategies give low surprise on their own paths but much higher surprise under random orders.
Alex: Does that show up in the model's calibration—how well its predicted probabilities match reality?
Sam: Yes, measured by Expected Calibration Error on the QM9 dataset of small molecules. Biased models look good at first, but their calibration worsens sharply under random order. Native surprise scores fool us; the model memorized specific paths, not the graphs themselves.
Alex: So these models might spit out a molecule sequence that scores low surprise because it matches training paths, but swap the order and the surprise skyrockets. That explains why they generate plausible-looking but unstable molecules.
Sam: The study confirms that on QM9. When models generate molecules, their surprise scores on those outputs actually work backward for stability. But LU on those generated graphs does the opposite: low LU flags stable ones reliably—a clear improvement.
Alex: Oh—so LU acts like a better quality check. It catches when low surprise came from a lucky path, not true graph confidence. Why does random order training fix this?
Sam: Random order acts like data augmentation—each training round shows fresh linearizations of the same graphs, teaching the model to ignore paths and focus on structure. It keeps surprise scores and calibration stable under permutations, prevents overfitting, and sustains diversity in generations, even with limited data.
Alex: Interesting. Without something like LU, chemists might chase molecules that only look good from one angle. But this is just on SENT and QM9, right?
Sam: The paper notes limitations: it's specific to the SENT framework and QM9's small molecules. Larger, diverse benchmarks and bigger graphs would test if LU holds up.
Alex: That seems like a meaningful step for trustworthy molecular design—filtering candidates without heavy simulations. Thanks, Sam, for breaking it down so clearly.
Sam: It's a solid diagnostic. Helps ensure likelihoods reflect graphs, not artifacts. Thanks for the sharp questions, Alex.
Alex: Thanks for listening to ResearchPod.