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.
- Coarsening: The graph is partitioned into a hierarchy ($H$). They explore two main strategies:
- Domain-Agnostic: Hierarchical Agglomerative Clustering (HAC) based on edge affinities.
- Chemistry-Aware: "Motif Community" (MC) detection, which identifies ring systems and functional groups.
- 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. - 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.
- Decoding: A deterministic parser that reads the token sequence and perfectly reconstructs the graph's nodes, edges, and attributes.
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.
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