Multi-Resolution Graph Diffusion

Recent graph denoising diffusion models achieved high fidelity in modeling small to medium sized graphs, however they often struggle from a complexity-expressivity tradeoff due the most high quality methods requiring architectures or features which scale quadratic in the number of nodes. This work proposes hierarchical diffusion, a novel approach that leverages the inherent hierarchical community structure found in real-world datasets in order to alleviate this issue. Our method decomposes the diffusion process into a sequence of conditional diffusion processes, where a parent graph representing community structure and edge distribution guides the generation of individual communities and their cross-connections. This process recursively refines the graph from coarse to fine resolutions until the final graph is generated. Importantly, our method preserves permutation equivariance by construction, and we further design our method to allow the diffusion process to take into account the global edge distribution when connecting partitions explicitly during the diffusion process, while retaining the ability to distribute training and inference across machines to scale horizontally.