Beyond Flat Walks: Compositional Abstraction for Autoregressive Graph Generation

Kaiwen Bian, Andrew H. Yang, Yusu Wang, Ali Parviz, Gal MishnearXiv 2026 · arXiv

TL;DR

This paper introduces a hierarchical framework for autoregressive graph generation that moves beyond "flat" node-by-node walks. By coarsening graphs into a hierarchy of communities and serializing them into a coarse-to-fine token sequence, the authors achieve significant improvements in structural and distributional fidelity across molecular and synthetic benchmarks.

What Problem Does This Paper Address?

Autoregressive graph generation typically relies on linearization: turning a graph into a sequence of nodes and edges (often via BFS or DFS traversals) so a Transformer can process it. However, these "flat walks" often obscure higher-order structures like rings in molecules or communities in social networks.

While the model might learn local connectivity, it struggles to capture global topology and long-range dependencies in large, complex graphs. The challenge is to create a sequence representation that explicitly exposes this hierarchical structure while remaining lossless (allowing perfect reconstruction) and compatible with standard causal Transformers.

Methods

The authors propose a three-stage pipeline: Coarsening, Tokenization, and Decoding.

  1. Coarsening: The graph is partitioned into a hierarchy ($H$). They explore two main strategies:
  2. Domain-Agnostic: Hierarchical Agglomerative Clustering (HAC) based on edge affinities.
  3. Chemistry-Aware: "Motif Community" (MC) detection, which identifies ring systems and functional groups.
  4. Tokenization (Hierarchical Depth Traversal - HDT): This is the core contribution. HDT performs a depth-first traversal of the hierarchy tree. It uses [ENTER] and [EXIT] tokens to delimit community boundaries. Connectivity is represented through "back-edges"—brackets that connect the current node to previously emitted neighbors, whether they are in the same community or a different one.
  5. Order Randomization: To help the model generalize, they resample traversal choices during training. They found that Full Hierarchy-Wide Randomization (-FR)—which randomizes the order of communities at every level—is essential for maintaining high novelty and uniqueness in generated graphs.
  6. Decoding: A deterministic parser that reads the token sequence and perfectly reconstructs the graph's nodes, edges, and attributes.
Figure 1: Encoding pipeline, illustrated on camptothecin. Motif coarsening gives two non- singleton communities (C6, C7) and six singleton communities (C0–C5), defining H. HDT serializes the hierarchy depth-first: [ENTER]/[EXIT] delimit communities, and back-edge brackets connect each atom to previously emitted neighbors within or across communities (orange arcs). The sequence is abridged, retains original atom indices, and omits atom- and bond-type tokens.

Datasets

The authors evaluated their method across ten benchmarks:

  • Molecular: GuacaMol, MOSES, COCONUT 2.0, GEOM-Drugs, and Macrocycle.
  • Non-Molecular: Proteins (D&D) and Planar graphs.
  • Synthetic: Three families of Stochastic Block Models (SBM, SSBM, and Recursive SBM) designed to test how well the model captures planted community structures.

Key Insights and Ideas

  • Coarse-before-Fine is Key: By presenting global community structure early in the sequence, later local decisions (like adding a specific atom) are made within the correct global context.
  • The Randomization Trade-off: Restricting the model to a fixed community order (Within-community randomization) leads to a "V.U.N. deficit"—a drop in Validity, Uniqueness, and Novelty. Expanding randomization to the full hierarchy tree largely fixes this, allowing the model to explore the graph space more effectively.
  • Hierarchy Alignment: The benefits of this approach depend heavily on how well the chosen coarsening strategy aligns with the data's natural structure. If the hierarchy is "meaningless" for the domain (as seen in the Planar graph results), the added complexity can actually hinder performance.
  • Architecture Agnostic: The gains come entirely from the serialization strategy, not a new model architecture. They used a standard GPT2-XS (~11M parameters) for all main experiments.

Key Results

  • Distributional Gains: On molecular benchmarks, the hierarchical HDT-HAC-R configuration reduced the Fréchet ChemNet Distance (FCD) by 51.6% to 64.6% compared to the flat baseline (SENT).
  • Structural Fidelity: It significantly improved MoleculePGD (a metric for graph discrepancy) by 34.3% to 86.6% across all five molecular datasets.
  • Scalability to Large Graphs: On the Proteins dataset (the largest tested), hierarchical serialization improved the V.U.N. score by 62.8% over the flat walk baseline.
  • Efficiency: While hierarchical sequences are longer, the authors showed that their model (GPT2-XS) with hierarchical tokens could outperform a larger model (GPT2-S) using flat tokens on several key metrics.
The decoding pipeline: a Transformer generates the HDT sequence, which is then parsed to reconstruct the molecule.

Limitations and Future Work

  • Sequence Length: Hierarchical tokenization roughly doubles the sequence length compared to flat walks. Because Transformer attention is quadratic, this increases the computational cost and memory requirements.
  • Coarsening Sensitivity: The framework relies on an external coarsening step. Finding the "optimal" hierarchy for a new, unknown domain remains an open challenge.
  • Conditional Generation: The paper primarily focuses on unconditional generation. The authors noted that their zero-shot results for motif-conditioned generation were less consistent, suggesting that conditional fine-tuning is a necessary next step for practical applications like drug discovery.

Summary updated

Abstract

Autoregressive graph generators typically linearize graphs through flat node-edge walks, which can obscure higher-order structure in large and complex graphs. We introduce a hierarchical graph abstraction and coarse-to-fine generation pipeline that separates coarsening, tokenization, and decoding. This exposes three design axes: community coarsening, hierarchical tokenization, and order randomization. Across these axes, traversal-based hierarchy consistently improves distributional and structural fidelity, while its V.U.N.\ cost depends strongly on the coarsening and randomization policy. In particular, the fidelity--V.U.N.\ trade-off observed under within-community randomization is substantially reduced when traversal order is randomized across the full hierarchy. With a fixed backbone, training protocol, and matched training time across five molecular and five non-molecular benchmarks, hierarchical serialization yields consistent distributional and structural gains on all molecular datasets, while the non-molecular results further show that these gains depend on how well the supplied hierarchy aligns with structure in the target distribution. Together, these results characterize when and how hierarchical serialization benefits autoregressive graph generation.
BibTeX
@misc{bian2026beyond,
  author = {Kaiwen Bian and Andrew H. Yang and Yusu Wang and Ali Parviz and Gal Mishne},
  title = {{Beyond Flat Walks: Compositional Abstraction for Autoregressive Graph Generation}},
  year = {2026},
  eprint = {2611.12160},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.12160},
}
Figure