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

• URL: http://arxiv.org/abs/2604.05613v1
• Date: Tue, 07 Apr 2026 09:03:06 GMT
• Title: Same Graph, Different Likelihoods: Calibration of Autoregressive Graph Generators via Permutation-Equivalent Encodings
• Abstract summary: We quantify violations in assigned negative log-likelihood (NLL) using the coefficient of variation across equivalent linearizations.<n>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.
• Score: 13.71581355372561
• License: http://creativecommons.org/licenses/by/4.0/
• 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

Related papers

• Signed Graph Learning: Algorithms and Theory [17.374356596021936]
  Real-world data is often represented through the relationships between data samples, forming a graph structure.<n>Current graph learning research has primarily focused on unsigned graphs.<n>We develop a method for capturing a set of smooth signed graph signals.
  arXiv  Detail & Related papers  (2025-07-13T17:33:26Z)
• Efficient Learning of Balanced Signed Graphs via Sparse Linear Programming [26.334739062500674]
  A balanced signed graph has eigenvectors that map via a simple linear transform to ones in a corresponding positive graph.<n>We propose an efficient method to learn a balanced signed graph Laplacian directly from data.
  arXiv  Detail & Related papers  (2025-06-02T16:09:51Z)
• Learning-Order Autoregressive Models with Application to Molecular Graph Generation [52.44913282062524]
  We introduce a variant of ARM that generates high-dimensional data using a probabilistic ordering that is sequentially inferred from data.<n>We demonstrate experimentally that our method can learn meaningful autoregressive orderings in image and graph generation.
  arXiv  Detail & Related papers  (2025-03-07T23:24:24Z)
• Graph Linearization Methods for Reasoning on Graphs with Large Language Models [25.3545522174459]
  Graphs should be linearized to reflect certain properties of natural language text, such as local dependency and global alignment.<n>We develop several graph linearization methods based on graph centrality and degeneracy.<n>Our work introduces novel graph representations suitable for LLMs, contributing to the potential integration of graph machine learning with the trend of multimodal processing.
  arXiv  Detail & Related papers  (2024-10-25T11:51:37Z)
• Scalable Graph Compressed Convolutions [68.85227170390864]
  We propose a differentiable method that applies permutations to calibrate input graphs for Euclidean convolution. Based on the graph calibration, we propose the Compressed Convolution Network (CoCN) for hierarchical graph representation learning.
  arXiv  Detail & Related papers  (2024-07-26T03:14:13Z)
• Similarity-aware Positive Instance Sampling for Graph Contrastive Pre-training [82.68805025636165]
  We propose to select positive graph instances directly from existing graphs in the training set. Our selection is based on certain domain-specific pair-wise similarity measurements. Besides, we develop an adaptive node-level pre-training method to dynamically mask nodes to distribute them evenly in the graph.
  arXiv  Detail & Related papers  (2022-06-23T20:12:51Z)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Learning Graphon Autoencoders for Generative Graph Modeling [91.32624399902755]
  Graphon is a nonparametric model that generates graphs with arbitrary sizes and can be induced from graphs easily. We propose a novel framework called textitgraphon autoencoder to build an interpretable and scalable graph generative model. A linear graphon factorization model works as a decoder, leveraging the latent representations to reconstruct the induced graphons.
  arXiv  Detail & Related papers  (2021-05-29T08:11:40Z)
• Permutation Invariant Graph Generation via Score-Based Generative Modeling [114.12935776726606]
  We propose a permutation invariant approach to modeling graphs, using the recent framework of score-based generative modeling. In particular, we design a permutation equivariant, multi-channel graph neural network to model the gradient of the data distribution at the input graph. For graph generation, we find that our learning approach achieves better or comparable results to existing models on benchmark datasets.
  arXiv  Detail & Related papers  (2020-03-02T03:06:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.