Reproduce “Efficient and Scalable Graph Generation through Iterative Local Expansion” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Andreas Bergmeister, Karolis Martinkus, Nathanaël Perraudin, Roger Wattenhofer
Researchers from ETH Zürich and Prescient Design developed an iterative local expansion method for graph generation, which reverses graph coarsening to construct large, complex graphs. This approach achieves subquadratic runtime and demonstrates robust generalization, reliably generating graphs with node counts significantly larger than those encountered during training.
Key insights
- Reversing graph coarsening provides a hierarchical, multi-scale generative paradigm that implicitly structures the generation process to build graphs from global connectivity to local details, enhancing scalability.
- Conditioning the generation on spectral properties of coarser graphs (e.g., Laplacian eigenvalues) helps preserve important structural characteristics and improves the fidelity of generated samples.
- It is possible to design a Graph Neural Network (Local PPGN) that achieves high local expressivity comparable to powerful but computationally intensive GNNs, while remaining efficient for sparse graph computations.
- Denoising diffusion models, combined with self-conditioning, are effective for modeling complex conditional distributions in hierarchical graph generation, enabling high-fidelity sample production.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.