DeFoG: Discrete Flow Matching for Graph Generation

DeFoG: Discrete Flow Matching for Graph Generation

Speakers: Yiming Qin, Manuel Madeira, Dorina Thanou, Pascal Frossard

Conference: ICML 2025

YouTube: https://slideslive.com/39043999

Overview

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.

DeFoG addresses these challenges by extending the Discrete Flow Matching (DFM) framework to the graph domain. DFM, a generalization of discrete diffusion, offers a more adaptable formulation that has previously demonstrated superior generative performance in other data modalities like text and images. The core innovation of DeFoG lies in leveraging this inherent flexibility to overcome the limitations of traditional diffusion models, achieving state-of-the-art results across various graph generative settings while significantly enhancing inference efficiency.

This work is particularly important for the machine learning and systems community as it paves the way for more efficient, adaptable, and performant graph generative AI. By enabling model configurations to be tailored to the specific nature of each graph dataset, DeFoG promises to unlock new possibilities in areas requiring high-fidelity and diverse graph synthesis, such as drug discovery, material science, and circuit optimization, where the ability to generate valid, unique, and novel structures is paramount.

Background

▶ Watch: Introduction to graph generation and diffusion model limitations (0:00)

The problem of graph generation is fundamental to many scientific and engineering disciplines. It involves learning the underlying probability distribution of a given set of graphs and then generating new graphs that resemble the training data, exhibiting similar structural and statistical properties. The diversity of real-world graphs is immense; a graph representing a molecule, with atoms as nodes and chemical bonds as edges, has fundamentally different characteristics from a graph representing an electronic circuit or a social network. This inherent diversity presents a significant challenge for generative models, which ideally should be adaptable to these varying data modalities.

A prominent family of generative models in this space are graph discrete diffusion models. These models operate on a two-phase principle: a noising process and a denoising process. During noising, a clean graph is progressively perturbed by sampling node and edge classes from a categorical distribution, eventually transforming into a fully noisy version. The denoising process, conversely, involves training a neural network to reverse this perturbation, step by step, from noise back to a clean graph. At inference time, the model generates new samples by iteratively applying this learned denoising chain. While powerful, these models are not without their drawbacks. A major limitation is their inflexibility and high computational cost during fine-tuning. Hyperparameters, such as noise schedules, are often tightly coupled with the training stage, meaning that any adjustment requires a full model retraining—a computationally intensive endeavor. This often forces researchers to adopt a "one-size-fits-all" training recipe, which is suboptimal for the highly varied nature of graph datasets. Such rigidity limits their ability to achieve peak performance across the diverse applications of graph generation.

To address these limitations, the authors drew inspiration from Discrete Flow Matching (DFM). DFM is a more general framework than discrete diffusion, offering increased flexibility in its formulation. Previous research has demonstrated DFM's superior generative performance over discrete diffusion in other data modalities, such as text and images, suggesting its potential for graph-structured data. The core motivation behind DeFoG was to extend this promising framework to the unique challenges of graph generation, aiming to develop a more adaptable and efficient generative model that can overcome the bottlenecks inherent in traditional graph diffusion approaches. The problem, therefore, is not just generating graphs, but generating them flexibly and efficiently across a spectrum of topological complexities and data characteristics.

Key Findings

▶ Watch: DeFoG's noising process: linear interpolation formulation (2:40)

DeFoG's introduction to the graph generation landscape brings several pivotal findings that significantly advance the state of the art:

1. Initial DFM Performance: A crucial insight was that a vanilla DFM model, when directly applied to graphs, does not inherently outperform existing graph diffusion models like DiGress. This underscored the necessity of tailoring the DFM framework specifically for graph structures and leveraging its inherent flexibility.
2. Leveraging DFM Flexibility: The core contribution of DeFoG lies in identifying and exploiting the modifiable components within the DFM framework—specifically, the rate matrix (R_theta_t) and the step size (delta_t)—to enhance graph generation performance. This adaptability is key to surpassing diffusion models.
3. Target Guidance for Accelerated Denoising: The introduction of target guidance (an extra term, R_star, added to the rate matrix) proved highly effective. This technique actively steers the denoising trajectory towards the predicted clean data distribution, causing "useful denoising work" to occur much earlier in the process. This results in a more uniformly effective and faster convergence to valid graphs, as evidenced by earlier increases in graph validity during the denoising chain.
4. Adaptive Denoising Time Steps: Adjusting the denoising time steps (delta_t) was found to be crucial for accommodating the distinct characteristics of different graph datasets. This allows for a customized denoising schedule that is more suited to specific graph topologies and properties.
5. Cumulative Performance Optimization: The progressive incorporation of these techniques (target guidance, adaptive delta_t, etc.) leads to a cumulative optimization of the sampling stage. This results in significantly improved generative performance, particularly when the number of denoising steps is limited.
6. Drastically Improved Inference Efficiency: DeFoG achieves high generative performance with a remarkably reduced number of denoising steps. The talk highlighted achieving comparable or superior performance with only 50 denoising steps, a stark contrast to the 1000 steps typically required by traditional diffusion models. This represents a substantial improvement in sampling efficiency.
7. Faster Training: Beyond inference, the paper also discusses that DeFoG achieves faster training by exploiting similar optimization techniques, further reducing the computational burden of developing and fine-tuning graph generative models.
8. Enhanced Graph Representation through RWPs: To overcome the known limitations of Graph Neural Networks (GNNs) in capturing complex graph structures, DeFoG augments standard graph transformers with Relative Random Walk Properties (RWPs) as additional node and edge features. These features significantly enhance the model's understanding of graph topology and are shown to be more efficient to compute than existing alternatives.
9. Principled Permutation Invariance: DeFoG inherently ensures permutation invariance, meaning the probability of sampling a graph is independent of its node ordering, a fundamental requirement for any robust graph generative model.
10. State-of-the-Art Performance Across Domains: DeFoG demonstrates state-of-the-art (SOTA) performance across a diverse range of graph generation tasks, including synthetic graphs (demonstrating learning of varied topologies), molecular graph generation (achieving SOTA validity (VAL) and generating unique and novel (VUN) molecules), and conditional graph generation in biomedically motivated settings.

These findings collectively establish DeFoG as a highly flexible, efficient, and performant framework for graph generation, addressing long-standing issues in the field and opening new avenues for application.

Technical Deep Dive

▶ Watch: DeFoG's denoising process and probability updates (4:00)

DeFoG builds upon the Discrete Flow Matching (DFM) framework, adapting its core principles of noising and denoising to the unique challenges of graph-structured data. The framework is designed to be more flexible than traditional discrete diffusion models, particularly in how it constructs the noising trajectory and how it allows for modifications during the denoising inference.

DFM Framework for Graphs

At its core, DeFoG, like discrete diffusion, is composed of two main processes: a noising process and a denoising process.

1. Noising Process Formulation:

DeFoG formulates the noising process as a linear interpolation between two distributions:

• P1 (Clean Data Distribution): This represents the target clean graph data. For each node and edge, its class (e.g., atom type, bond type) is represented as a one-hot encoding.
• P0 (Predefined Initial Distribution): This is a predefined categorical distribution, often set as a uniform distribution across all possible node and edge classes. However, the flexibility of DFM allows for any other categorical distribution to be used.

At any given time step t (between 0 and 1), the noising trajectory is constructed by sampling independently each of the graph variables (i.e., for each node and each edge) from the distributions induced by this interpolation. This process progressively transforms a clean graph into a noisy graph Gt. Conceptually, as t approaches 0, the graph approaches the fully noisy state defined by P0; as t approaches 1, it approaches the clean state defined by P1.

1. Denoising Neural Network:

A crucial component is the denoising neural network. This network takes the noisy graph Gt (for any t between 0 and 1) as its input. Its primary objective during training is to predict the corresponding clean graph (G1). This prediction capability is fundamental for guiding the reverse, denoising process.

1. Denoising Process (Inference):

The inference stage begins with a fully noisy graph, sampled from the predefined initial distribution P0 for all nodes and edges. The model then progressively denoises this graph, jumping from a state at time t to a slightly cleaner state at time t + delta_t. Each denoising step involves updating the probability distribution for each node and edge:

• Probability Update Vector: For a selected node or edge, its probability distribution for the next step is updated by adding a vector to its current state. This update vector is calculated as the product of two terms:
• Step Size (delta_t): A scalar representing the size of the time step.
• Rate Matrix (R_theta_t): This matrix encodes the transition rates between different node/edge classes at time t. Crucially, this rate matrix is dynamically computed based on the predictions of the trained denoising neural network (indicated by the theta superscript, R_theta_t). It essentially tells us the probabilities of a node transitioning from its current class to any other class, guided by the neural network's understanding of the clean data.
• Sampling: After computing the updated probability distribution, a new class for the node or edge is sampled from this distribution. This process is repeated for every node and edge in the graph, defining one complete denoising step. By applying this update over successive time steps, noise is incrementally removed, and the graph progressively converges to a clean, fully denoised graph at the end of the chain.

DeFoG's Enhancements for Graph Generation Performance

The vanilla DFM, as noted, does not directly outperform existing graph diffusion models. DeFoG's innovation lies in leveraging DFM's flexibility to introduce specific enhancements:

1. Optimizing the Rate Matrix (R_theta_t) with Target Guidance:

The rate matrix is a key control point. DeFoG introduces target guidance to amplify the neural network's predictions more effectively along the denoising trajectory.

• Problem: In vanilla DFM, early denoising steps might not be very effective, with most "useful" denoising postponed to the final stages (e.g., validity only rapidly improves after t > 0.8).
• Solution: An extra term, denoted as R_star, is added to the default rate matrix. This R_star term actively steers the denoising trajectory towards the clean data distribution as predicted by the trained neural network.
• Effect: With target guidance, validity rises much earlier in the denoising trajectory, indicating that the denoising process becomes more uniformly effective and efficient throughout. This means the model makes more meaningful progress towards a clean graph from the very beginning.

1. Adjusting the Step Size (delta_t):

The step size delta_t also offers a knob for optimization. DeFoG explores adjusting different types of denoising time steps to better accommodate the varied nature of different graph types. While specific schedules were not detailed in the talk, the principle is to tailor the progression of denoising to the specific characteristics of the dataset, rather than using a generic, fixed schedule. This allows for more precise control over the denoising speed and trajectory, optimizing for different graph topologies and feature complexities.

1. Graph-Specific Features and Architecture:

• GNN Augmentation with Relative Random Walk Properties (RWPs): Graph Neural Networks (GNNs) are known to have limitations in their representational power, particularly for complex or long-range dependencies in graphs. To address this, DeFoG augments the standard graph transformer architecture. It incorporates Relative Random Walk Properties (RWPs) as additional node and edge features. These RWPs provide the GNN with enhanced information about the structural context and connectivity patterns within the graph, improving its understanding of graph topology. The authors highlight that RWPs are not only expressive for graph generation but also more efficient to compute than many existing alternatives.
• Permutation Invariance: A fundamental requirement for graph generative models is permutation invariance, meaning that the generated graph should be independent of the arbitrary ordering of its nodes. DeFoG ensures this by designing the model such that the probability of sampling a graph represented by its adjacency matrix A is equal to the probability of sampling any of its permuted versions. This principled design guarantees that the model learns the intrinsic structure of graphs, not just artifacts of their representation.

These technical innovations, particularly the flexible control over the rate matrix and step size, combined with graph-specific architectural enhancements, enable DeFoG to transcend the limitations of previous graph diffusion models and achieve superior performance and efficiency.

Experimental Setup & Results

▶ Watch: Deep dive into target guidance for effective denoising (7:00)

To provide a comprehensive evaluation of DeFoG, the researchers considered three distinct types of graph generation tasks, showcasing its versatility and robust performance across various domains.

Evaluation Tasks

1. Synthetic Graphs: This task aimed to demonstrate DeFoG's ability to accurately learn and reproduce the underlying distributions of graphs with diverse topologies. This is crucial for validating the model's fundamental generative capabilities.
2. Molecular Graph Generation: This is a high-stakes application where graphs represent molecules (atoms as nodes, chemical bonds as edges). This task involves generating graphs with rich node and edge classes and is critical for applications like drug discovery. The talk highlighted DeFoG's progressive denoising of a noisy graph into a realistic molecule as an example.
3. Conditional Graph Generation: This involved a biomedically motivated setting, where graphs are generated conditioned on specific properties or inputs. This demonstrates DeFoG's capability for targeted and controlled graph synthesis.

Metrics and Baselines

For molecular graph generation, key metrics were:

• Validity (VAL): The percentage of generated molecules that are chemically valid according to standard rules.
• Unique and Novel (VUN): The percentage of generated molecules that are both unique (not duplicates) and novel (not present in the training dataset), indicating true generative capacity.

The primary baseline for comparison was DiGress, a prominent existing graph discrete diffusion model.

Headline Results and Ablations

The experimental results powerfully illustrate the impact of DeFoG's proposed techniques:

1. Vanilla DFM vs. Baselines: A critical initial finding was that the vanilla DFM (without DeFoG's specific enhancements) did not directly outperform existing graph diffusion models like DiGress. This established the necessity of the subsequent methodological contributions.
2. Cumulative Optimization: A key plot presented showed generative performance (y-axis, higher is better) against the number of denoising steps (x-axis).

• The vanilla DFM (light blue line) consistently performed below DiGress (orange line) across all numbers of denoising steps.
• However, by progressively incorporating DeFoG's techniques (e.g., target guidance, adaptive delta_t), a cumulative optimization of the sampling stage was observed. Each added technique led to a significant and noticeable improvement in generative performance.

1. Dramatic Inference Efficiency: The benefits of DeFoG's optimizations were particularly pronounced when using fewer denoising steps. The model achieved high performance with only 50 denoising steps, a stark contrast to the 1000 steps typically used by conventional graph diffusion models. This represents an approximate 20x reduction in inference computation for comparable or superior performance. This significant speedup is a major practical advantage.
2. State-of-the-Art Molecular Generation: For molecular graph generation, DeFoG demonstrated state-of-the-art validity (VAL) across several molecular datasets. Furthermore, it proved capable of generating a high proportion of unique and novel (VUN) molecules, a crucial indicator of a model's ability to explore chemical space effectively and discover new compounds.
3. Faster Training: While not detailed with specific numbers in the talk, the authors also mentioned that DeFoG achieves faster training by leveraging similar optimization techniques, further improving the overall development and deployment cycle.

In summary, the experimental results rigorously validate DeFoG's technical innovations. They clearly demonstrate that by strategically leveraging the flexibility of the DFM framework and incorporating graph-specific features, DeFoG not only surpasses the performance of existing graph diffusion models but also does so with unprecedented efficiency during inference and training, making it a highly compelling solution for real-world graph generation tasks.

Practical Implications

▶ Watch: Demonstrating cumulative performance gains with DeFoG techniques (8:00)

DeFoG introduces significant practical implications for various stakeholders in the AI/ML ecosystem, from model builders to infrastructure teams and those deploying generative AI solutions.

For practitioners and model builders, DeFoG offers a much-needed increase in flexibility and adaptability. Unlike traditional graph diffusion models that often constrain choices during training, requiring costly retraining for hyperparameter tuning, DeFoG's framework is inherently more configurable. This means that instead of relying on a single, suboptimal training recipe for all graph datasets, practitioners can now tailor model configurations to the specific nature of each dataset—be it molecular structures, electronic circuits, or social networks. This adaptability is critical for achieving optimal generative performance across the highly diverse graph modalities encountered in real-world applications. The ability to fine-tune aspects like the rate matrix and denoising step sizes without full retraining allows for more agile experimentation and better-performing models. For instance, in drug discovery, this flexibility could lead to more effective generation of molecules with desired properties by adapting the generative process to specific chemical spaces.

For infrastructure teams and deployers, the most impactful implication is the dramatic improvement in inference efficiency. DeFoG's ability to achieve high-quality graph generation with only 50 denoising steps, compared to the typical 1000 steps of diffusion models, translates directly into substantial reductions in computational cost and inference latency. This 20x speedup means:

• Lower operational costs: Fewer GPU/TPU hours are needed for generating samples at scale.
• Faster turnaround times: Applications requiring on-demand graph generation (e.g., real-time molecular design queries) can respond much quicker.
• Reduced carbon footprint: Less computation inherently means lower energy consumption.
• Scalability: Deploying generative models at scale becomes more feasible and cost-effective.

Furthermore, the mention of faster training also benefits infrastructure teams by reducing the compute resources and time required for model development and iterative improvements. This accelerates the research-to-deployment cycle.

Tradeoffs and Limitations: While DeFoG offers significant advantages, it's important to acknowledge that achieving these benefits requires a more nuanced approach than simply applying vanilla DFM. The talk explicitly stated that direct application of DFM to graphs does not outperform existing diffusion models. This implies that the effectiveness of DeFoG hinges on the careful implementation and tuning of its specific enhancements, such as target guidance and adaptive step sizes, as well as the integration of graph-specific features like RWPs. The increased complexity of managing these flexible components might present a steeper learning curve compared to a black-box diffusion model. However, the demonstrated gains in performance and efficiency strongly suggest that the investment in understanding and leveraging DeFoG's flexibility is well worth the effort. The primary "limitation" of DFM itself (its non-superiority in vanilla form) is precisely what DeFoG transforms into an opportunity through targeted innovation.

Overall, DeFoG represents a substantial leap forward for practical graph generation, offering a powerful combination of flexibility, efficiency, and state-of-the-art performance that can drive innovation across various scientific and engineering domains.

Key Takeaways

• DeFoG introduces a novel graph generative framework based on Discrete Flow Matching (DFM), addressing the inflexibility and computational cost of traditional graph discrete diffusion models.
• The core innovation lies in leveraging DFM's inherent flexibility through techniques like target guidance for the rate matrix and adaptive denoising time steps (delta_t), which are crucial for achieving state-of-the-art performance.
• DeFoG drastically improves inference efficiency, achieving high generative quality with only 50 denoising steps compared to the typical 1000 steps required by existing graph diffusion models, leading to significant computational savings.
• The framework incorporates Relative Random Walk Properties (RWPs) as additional features for graph transformers, enhancing the GNN's ability to understand complex graph structures and ensuring principled permutation invariance.
• DeFoG demonstrates state-of-the-art performance across diverse graph generation tasks, including synthetic graphs, molecular graph generation (achieving high validity (VAL) and generating unique and novel (VUN) molecules), and conditional graph generation.
• This work provides a more adaptable, efficient, and performant solution for practitioners and infrastructure teams, enabling customized generative models for highly diverse graph datasets and reducing the computational burden of deployment.

About the Speaker(s)

The work "DeFoG: Discrete Flow Matching for Graph Generation" was presented by Manuel Madeira and Yiming Qin, who collaborated with Dorina Thanou and Pascal Frossard. All speakers are affiliated with EPFL (École Polytechnique Fédérale de Lausanne), a renowned research institution, indicating a strong academic backing for this technical contribution to the field of AI/ML. Their presentation highlighted their expertise in graph generative models and the Discrete Flow Matching framework.