DeFoG: Discrete Flow Matching for Graph Generation

Yiming Qin, Manuel Madeira, Dorina Thanou, Pascal Frossard

International Conference on Machine Learning 2025 · Oral

The talk "DeFoG: Discrete Flow Matching for Graph Generation," presented by Manuel Madeira and Yiming Qin from EPFL, introduces a novel and highly flexible framework for generating graphs that accurately capture complex data distributions. Graph generation is a critical task with wide-ranging applications, from designing new molecules and electronic circuits to modeling complex networks. Existing graph generative models, particularly **graph discrete diffusion models**, have shown remarkable performance in capturing diverse graph topologies. However, they suffer from significant limitations, primarily their computational cost and inflexibility in fine-tuning, often necessitating a single training recipe across vastly different graph datasets.

AI review

DeFoG is a competent and honest engineering contribution that adapts the Discrete Flow Matching framework to graph generation, introducing target guidance on the rate matrix and adaptive step sizes to improve over a vanilla DFM baseline. The work is well-motivated, the ablations are structured, and the efficiency gains (50 vs. 1000 steps) are practically meaningful. However, the theoretical depth is limited: the core techniques are adaptations of existing DFM machinery rather than new mathematical objects, the claims about permutation invariance are architectural rather than proven at the…