Graph generation has been dominated by autoregressive models due to their
simplicity and effectiveness, despite their sensitivity to ordering. Yet
diffusion models have garnered increasing attention, as they offer comparable
performance while being permutation-invariant. Current graph diffusion models
generate graphs in a one-shot fashion, but they require extra features and
thousands of denoising steps to achieve optimal performance. We introduce PARD,
a Permutation-invariant Auto Regressive Diffusion model that integrates
diffusion models with autoregressive methods. PARD harnesses the effectiveness
and efficiency of the autoregressive model while maintaining permutation
invariance without ordering sensitivity. Specifically, we show that contrary to
sets, elements in a graph are not entirely unordered and there is a unique
partial order for nodes and edges. With this partial order, PARD generates a
graph in a block-by-block, autoregressive fashion, where each block's
probability is conditionally modeled by a shared diffusion model with an
equivariant network. To ensure efficiency while being expressive, we further
propose a higher-order graph transformer, which integrates transformer with
PPGN. Like GPT, we extend the higher-order graph transformer to support
parallel training of all blocks. Without any extra features, PARD achieves
state-of-the-art performance on molecular and non-molecular datasets, and
scales to large datasets like MOSES containing 1.9M molecules.

PARD 是一个将扩散模型与自回归方法结合的置换不变自回归扩散模型，通过使用特定的局部顺序，以块状的自回归方式生成图。它在没有额外特征的情况下，在分子和非分子数据集上取得了最新水平的性能，且可以扩展到包含 1.9M 个分子的大型数据集。