Conditional graph generation tasks involve training a model to generate a
graph given a set of input conditions. Many previous studies employ
autoregressive models to incrementally generate graph components such as nodes
and edges. However, as graphs typically lack a natural ordering among their
components, converting a graph into a sequence of tokens is not
straightforward. While prior works mostly rely on conventional heuristics or
graph traversal methods like breadth-first search (BFS) or depth-first search
(DFS) to convert graphs to sequences, the impact of ordering on graph
generation has largely been unexplored. This paper contributes to this problem
by: (1) highlighting the crucial role of ordering in autoregressive graph
generation models, (2) proposing a novel theoretical framework that perceives
ordering as a dimensionality reduction problem, thereby facilitating a deeper
understanding of the relationship between orderings and generated graph
accuracy, and (3) introducing "latent sort," a learning-based ordering scheme
to perform dimensionality reduction of graph tokens. Our experimental results
showcase the effectiveness of latent sort across a wide range of graph
generation tasks, encouraging future works to further explore and develop
learning-based ordering schemes for autoregressive graph generation.

本文提出了基于学习的排序方案来解决自回归模型中的图生成和排序问题，并通过实验证明该方案在各种图生成任务上的有效性，鼓舞未来工作进一步探索和发展学习排序方案。