Hierarchical methods improve accuracy in autoregressive graph generation
Beyond Flat Walks: Compositional Abstraction for Autoregressive Graph Generation
Machine Learning
Summary
Generating graphs by listing their parts one by one can miss how parts fit together on a bigger scale. The authors found that grouping nodes into communities and creating a hierarchy before generating graphs can better capture these larger structures. This approach improves how closely generated graphs resemble real ones, especially when the hierarchy matches the graph’s natural organization. These improvements were shown consistently on chemical molecules and other graph datasets.
What this means in practice
- •For pharmaceutical data scientists: Generate molecular graphs that more accurately reflect chemical structures using hierarchical grouping to improve drug discovery simulations.
- •For network analysis teams: Create synthetic network graphs preserving community structures better for testing analysis algorithms and modeling large real-world systems.
Authors
Kaiwen Bian, Andrew H. Yang, Yusu Wang, Ali Parviz, Gal Mishne
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.