# Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation

arXiv: https://arxiv.org/abs/2106.06189 · HTML: https://mlsanity.com/paper/2106.06189/

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 40 references that are in the map.
- First posted on arXiv 11 Jun 2021.

## Builds on (most cited first, 17 of 17)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Variational Inference: A Review for Statisticians](https://mlsanity.com/paper/1601.00670/) (2016)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Models](https://mlsanity.com/paper/1802.08773/) (2018)
- [Black Box Variational Inference](https://mlsanity.com/paper/1401.0118/) (2013)
- [GraphAF: a Flow-based Autoregressive Model for Molecular Graph Generation](https://mlsanity.com/paper/2001.09382/) (2020)
- [Monte Carlo Gradient Estimation in Machine Learning](https://mlsanity.com/paper/1906.10652/) (2019)
- [Efficient Graph Generation with Graph Recurrent Attention Networks](https://mlsanity.com/paper/1910.00760/) (2019)
- [Learning Deep Generative Models of Graphs](https://mlsanity.com/paper/1803.03324/) (2018)
- [XGNN: Towards Model-Level Explanations of Graph Neural Networks](https://mlsanity.com/paper/2006.02587/) (2020)
- [A Systematic Survey on Deep Generative Models for Graph Generation](https://mlsanity.com/paper/2007.06686/) (2020)
- [GraphGen: A Scalable Approach to Domain-agnostic Labeled Graph Generation](https://mlsanity.com/paper/2001.08184/) (2020)
- [Scalable Deep Generative Modeling for Sparse Graphs](https://mlsanity.com/paper/2006.15502/) (2020)
- [The Class of Random Graphs Arising from Exchangeable Random Measures](https://mlsanity.com/paper/1512.03099/) (2015)
- [Edge-exchangeable graphs and sparsity](https://mlsanity.com/paper/1603.06898/) (2016)

## Built on by (most cited first, 30 of 33)

- [Predicting Physics in Mesh-reduced Space with Temporal Attention](https://mlsanity.com/paper/2201.09113/) (2022)
- [Autoregressive Diffusion Model for Graph Generation](https://mlsanity.com/paper/2307.08849/) (2023)
- [Efficient and Degree-Guided Graph Generation via Discrete Diffusion Modeling](https://mlsanity.com/paper/2305.04111/) (2023)
- [On Evaluation Metrics for Graph Generative Models](https://mlsanity.com/paper/2201.09871/) (2022)
- [GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generation](https://mlsanity.com/paper/2212.01842/) (2022)
- [A Survey on Graph Diffusion Models: Generative AI in Science for Molecule, Protein and Material](https://mlsanity.com/paper/2304.01565/) (2023)
- [Learning-Order Autoregressive Models with Application to Molecular Graph Generation](https://mlsanity.com/paper/2503.05979/) (2025)
- [Pard: Permutation-Invariant Autoregressive Diffusion for Graph Generation](https://mlsanity.com/paper/2402.03687/) (2024)
- [NVDiff: Graph Generation through the Diffusion of Node Vectors](https://mlsanity.com/paper/2211.10794/) (2022)
- [Graph Generative Pre-trained Transformer](https://mlsanity.com/paper/2501.01073/) (2025)
- [Improving Graph Generation by Restricting Graph Bandwidth](https://mlsanity.com/paper/2301.10857/) (2023)
- [Flatten Graphs as Sequences: Transformers are Scalable Graph Generators](https://mlsanity.com/paper/2502.02216/) (2025)
- [FairGen: Towards Fair Graph Generation](https://mlsanity.com/paper/2303.17743/) (2023)
- [Conditional set generation using Seq2seq models](https://mlsanity.com/paper/2205.12485/) (2022)
- [Let There Be Order: Rethinking Ordering in Autoregressive Graph Generation](https://mlsanity.com/paper/2305.15562/) (2023)
- [Symmetry-Aware GFlowNets](https://mlsanity.com/paper/2506.02685/) (2025)
- [HiGen: Hierarchical Graph Generative Networks](https://mlsanity.com/paper/2305.19337/) (2023)
- [TD-GEN: Graph Generation With Tree Decomposition](https://mlsanity.com/paper/2106.10656/) (2021)
- [Interpretable Node Representation with Attribute Decoding](https://mlsanity.com/paper/2212.01682/) (2022)
- [EDGE++: Improved Training and Sampling of EDGE](https://mlsanity.com/paper/2310.14441/) (2023)
- [Overcoming Order in Autoregressive Graph Generation](https://mlsanity.com/paper/2402.03387/) (2024)
- [Entropy Coding of Unordered Data Structures](https://mlsanity.com/paper/2408.08837/) (2024)
- [Diffusion-Free Graph Generation with Next-Scale Prediction](https://mlsanity.com/paper/2503.23612/) (2025)
- [Random Edge Coding: One-Shot Bits-Back Coding of Large Labeled Graphs](https://mlsanity.com/paper/2305.09705/) (2023)
- [IFH: a Diffusion Framework for Flexible Design of Graph Generative Models](https://mlsanity.com/paper/2408.13194/) (2024)
- [Quality Measures for Dynamic Graph Generative Models](https://mlsanity.com/paper/2503.01720/) (2025)
- [Probabilistic Graph Circuits: Deep Generative Models for Tractable Probabilistic Inference over Graphs](https://mlsanity.com/paper/2503.12162/) (2025)
- [FLAGG: Flexible Autoregressive Graph Generation](https://mlsanity.com/paper/2606.05067/) (2026)
- [On Hierarchical Multi-Resolution Graph Generative Models](https://mlsanity.com/paper/2303.03293/) (2023)
- [A Semi-Autoregressive Graph Generative Model for Dependency Graph Parsing](https://mlsanity.com/paper/2306.12018/) (2023)

## Abstract (arXiv)

A graph generative model defines a distribution over graphs. One type of generative model is constructed by autoregressive neural networks, which sequentially add nodes and edges to generate a graph. However, the likelihood of a graph under the autoregressive model is intractable, as there are numerous sequences leading to the given graph; this makes maximum likelihood estimation challenging. Instead, in this work we derive the exact joint probability over the graph and the node ordering of the sequential process. From the joint, we approximately marginalize out the node orderings and compute a lower bound on the log-likelihood using variational inference. We train graph generative models by maximizing this bound, without using the ad-hoc node orderings of previous methods. Our experiments show that the log-likelihood bound is significantly tighter than the bound of previous schemes. Moreover, the models fitted with the proposed algorithm can generate high-quality graphs that match the structures of target graphs not seen during training. We have made our code publicly available at hyperref[https://github.com/tufts-ml/graph-generation-vi]https://github.com/tufts-ml/graph-generation-vi.