Equivariance is central to graph generative models, as it ensures the model respects the permutation symmetry of graphs. However, strict equivariance can increase computational cost due to added architectural constraints, and can slow down convergence because the model must be consistent across a large space of possible node permutations. We study this trade-off for graph generative models. Specifically, we start from an equivariant discrete flow-matching model, and relax its equivariance during training via a controllable symmetry modulation scheme based on sinusoidal positional encodings and node permutations. Experiments first show that symmetry-breaking can accelerate early training by providing an easier learning signal, but at the expense of encouraging shortcut solutions that can cause overfitting, where the model repeatedly generates graphs that are duplicates of the training set. On the contrary, properly modulating the symmetry signal can delay overfitting while accelerating convergence, allowing the model to reach stronger performance with 19% of the baseline training epochs.
Figures & tables
Figure 1: Symmetry breaking restoring cycle. Starting from the initial point, equivariant paths converge slowly but preserve symmetry, non equivariant paths converge faster with a generalization gap, and the breaking restoring path achieves fast progress while recovering structural validity.
Figure 2: Comparison of the baseline setting and symmetry breaking sinusoidal positional encodings in (A), and with different invariance scalings λ using (B) χ=∞ and (C) χ=10 . Panels show (a) Validity, (b) Novelty, (c) Uniqueness, and (d) VUN on the SBM dataset.
Figure 3: Comparison of DeFoG’s baseline setting, with RRWP encodings and symmetry breaking sinusoidal PE with different invariance scaling λ and time dependent permutation rates.
Appendix figures & tables9 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 4: (A) Inverse of the time-dependent rate functions used in Figure 3 . (B) Phase space diagram of the aggregated metric UN, evaluated in the first 10000 training steps.
Figure 5: Comparison of positional encodings with and without data augmentation (a) Validity (b) Novelty (c) Uniqueness (d) VUN, on the SBM dataset.
Figure 6: Comparison of DeFoG’s baseline setting, with RRWP encodings and normalized symmetry breaking sinusoidal PE (Equation 16 with different invariance scaling λ and no permutations, χ=∞ for (a) Validity (b) Novelty (c) Uniqueness (d) VUN, on the SBM dataset.
Figure 7: Comparison of the different methods introduced in Section 2.1 for a fixed value of λ=3 .
Dataset
Min Nodes
Max Nodes
Graphs Sampled
Planar
64
64
40
Tree
64
64
40
Erdös-Rényi
20
80
40
Barábasi-Albert
64
64
40
Appendix
Table 2: Training and sampling parameters for the datasets used in Appendix H .
Figure 8: Comparison of DeFoG’s baseline setting, with RRWP encodings and symmetry breaking sinusoidal PE (a) Validity (b) Novelty (c) Uniqueness (d) VUN, on the planar dataset.
Figure 9: Comparison of DeFoG’s baseline setting, with RRWP encodings and symmetry breaking sinusoidal PE (a) Validity (b) Novelty (c) Uniqueness (d) VUN, on the tree dataset.
Figure 10: Comparison of DeFoG’s baseline setting, with RRWP encodings and symmetry breaking sinusoidal PE (a) Validity (b) Novelty (c) Uniqueness (d) VUN, on the Erdös-Rényi model.
Figure 11: Comparison of DeFoG’s baseline setting, with RRWP encodings and symmetry breaking sinusoidal PE (a) Validity (b) Novelty (c) Uniqueness (d) VUN, on the Barábasi-Albert model.
Graphs are invariant under node permutations, motivating permutation-equivariant architectures in generative models. In flow matching, however, symmetry also affects the source-target coupling: one must choose both which graphs to pair and which node representatives to align. We study these two forms of alignment, termed outer and inner alignment, and their effect on equivariant graph flow matching. We connect inner alignment to transport on the graph quotient space, whose Euclidean quotient metric coincides with Gromov-Monge distance, and show that quotient couplings admit aligned representative lifts while symmetrization yields equivariant flow-matching minimizers, including for categorical endpoints. In practice, we compare random augmentation, permutation-blind minibatch optimal transport, approximate Gromov-Wasserstein alignment, and combinations of inner and outer alignment. Across continuous graph and molecular generation, alignment can substantially simplify trajectories and improve few-step generation, while its benefits depend on the alignment and computational budget. Our results highlight that effective graph flow matching benefits from alignment both inside and across graph pairs.
Moritz Piening, Christian Wald
Institute of Computer Science University of Göttingen Göttingen, Germany · Institut Camille Jordan INSA Lyon Villeurbanne, France
Denoising-based models, including diffusion and flow matching, have led to substantial advances in graph generation. Despite this progress, such models remain constrained by two fundamental limitations: a computational cost that scales quadratically with the number of nodes and a large number of function evaluations required during generation. In this work, we introduce a novel hierarchical generative framework that reduces the number of node pairs that must be evaluated and adopts discrete flow matching to significantly decrease the number of denoising iterations. We empirically demonstrate that our approach more effectively captures graph distributions while substantially reducing generation time.
Yoann Boget, Pablo Strasser, Alexandros Kalousis
Department of Computer Science, University of Geneva, Switzerland · DMML Group, Geneva School for Business administration HES-SO, Switzerland
We study generative modeling of graphs with recurring subgraph motifs. We propose Flowette, a continuous flow matching framework that employs a graph neural network-based transformer to learn a velocity field over graph representations with node and edge attributes. Our model promotes topology-aware alignment through optimal transport-based coupling and preserves structural fidelity through endpoint- and chemistry-aware regularisation. To incorporate domain-driven structural priors, we introduce graphettes, a new probabilistic family of graph structure models that generalize graphons via controlled structural edits for motifs such as rings, stars, and trees. We theoretically analyze the coupling, invariance, and structural properties of the framework, evaluate it on synthetic and molecular benchmarks, and isolate the contributions of the structural prior, the optimal-transport coupling, and the regularisation terms through controlled ablations. Flowette achieves competitive performance overall, attaining state-of-the-art results on several metrics across multiple benchmarks, highlighting the effectiveness of combining structural priors with flow-based training for modeling complex graph distributions.
Asiri Wijesinghe, Sevvandi Kandanaarachchi, Daniel M. Steinberg +1