Generating Directed Graphs with Dual Attention and Asymmetric Encoding
Alba Carballo-Castro, Manuel Madeira, Yiming Qin, Dorina Thanou, Pascal Frossard · 2025
Read Generating Directed Graphs with Dual Attention and Asymmetric Encoding by Alba Carballo-Castro, Manuel Madeira, Yiming Qin, Dorina Thanou, Pascal Frossard (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-16404.txt.
Introduction
Alba Carballo-Castro, Manuel Madeira, Yiming Qin, Dorina Thanou, and Pascal Frossard build the first flow-based generator of directed graphs, in a 2025 paper. Directed graphs, where edges point one way, model transport, biology, and social ties. Making new ones is hard: direction doubles the dependency tangle, and no standard testbed existed. Their model, Directo, attacks both problems.
Position codes tailored to one-way relations and a dual attention that reads incoming and outgoing links separately give the model its directional sense. A new benchmark suite spans synthetic and real datasets. Directo performed strongly throughout, even rivaling specialists at acyclic graphs. The authors offer it as a foundation for a neglected corner of graph generation.
Catalog record
| CREATOR | Alba Carballo-Castro, Manuel Madeira, Yiming Qin, Dorina Thanou, Pascal Frossard |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 128 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-16404
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Generating Directed Graphs with Dual Attention and Asymmetric Encoding Alba Carballo-Castro, Manuel Madeira, Yiming Qin, Dorina Thanou, Pascal Frossard Abstract Directed graphs naturally model systems with asymmetric, ordered relationships, essential to applications in biology, transportation, social networks, and visual understanding. Generating such graphs enables tasks such as simulation, data augmentation and novel instance discovery; however, directed graph generation remains underexplored. We identify two key factors limiting progress in this direction: first, modeling edge directionality introduces a substantially larger dependency space, making the underlying distribution harder to learn; second, the absence of standardized benchmarks hinders rigorous evaluation. Addressing the former requires more expressive models that are sensitive to directional topologies. We propose Directo , the first generative model for directed graphs built upon the discrete flow matching framework. Our approach combines: (i) principled positional encodings tailored to asymmetric pairwise relations, (ii) a dual-attention mechanism capturing both incoming and outgoing dependencies, and (iii) a robust, discrete generative framework. To support evaluation, we introduce a benchmark suite covering synthetic and real-world datasets. It shows that our method performs strongly across diverse settings and even competes with specialized models for particular classes, such as directed acyclic graphs. Our results highlight the effectiveness and generality of our approach, establishing a solid foundation for future research in directed graph generation. 1 Introduction Directed graphs (digraphs) naturally model systems with asymmetric relationships, capturing essential structures such as flows, dependencies, and hierarchies that arise in many real-world applications. This makes digraphs particularly well-suited for problems in diverse domains including biology li2006directed ; takane2023directed ; wei2024inference , transportation concas2022chained , social dynamics schweimer2022generating , and, more recently, image and video understanding Chang23Scenegraphs ; rodin2023actionscenegraphslongform , where structured, directional representations are critical for interpretation and reasoning. Consequently, generating digraphs is central to tasks such as such as simulation, data augmentation and novel instance discovery in domains characterized by directional structure. (a) Comparison on # structures. (b) Overview of Directo . Figure 1 : (a) The learnable space increases drastically with the number of nodes for digraphs compared to undirected graphs harary1973enumeration , highlighting challenges in extending graph generative models to directed structures. (b) Overview of our generative model for directed graphs. During training, the dual attention transformer (denoising network) parameterized by \theta , and enhanced with asymmetric positional encodings , learns to reverse predictions using cross-entropy loss. During inference, we compute the rate matrix R_{t}^{\theta}(G_{t},G_{t+\Delta t}) based on the model prediction p^{\theta}(\cdot\mid G_{t}) , which governs the evolution of the generative process over finite intervals \Delta t . Graph generative models offer a data-driven approach to producing plausible and diverse samples, with applications in drug discovery mercado2020graph ; vignac2023midi , finance li2023moneylaundering , social network modeling tsai2023cdgraphdualconditionalsocial , and medicine nikolentzos2023synthetic . Despite their broad applicability and strong performance, the vast majority of existing generative models focus on undirected graphs liao2019gran ; martinkus2022SPECTRE ; vignac2023digress ; siraudin2024cometh ; xu2024disco ; Eijkelboom2024VariationalFM ; qin2025defog . Digraphs have received comparatively less attention, with recent work proposing auto-regressive models for DAGs zhang2019dvae ; li2024layerdag and, more recently, for general digraphs law2024directedheatkernels . We identify two main factors behind this limited progress. First, at the modeling level, the directed setting is inherently more challenging than its undirected counterpart, as edge directionality greatly enlarges the learnable space (see Fig. 1(a) : for graphs with 4 nodes, there are 218 possible digraphs, compared to only 11 undirected ones). This is further amplified in settings where domain-specific structural constraints must be respected, such as directed acyclic graphs (DAGs). Second, beyond these technical challenges, we identify the lack of standardized benchmarks for directed graph generation as an important barrier to rigorous evaluation and fair comparison across methods. Current methods li2024layerdag typically rely on proxy metrics derived from downstream task performance, without directly evaluating generated graph quality. To address the first challenge, we introduce Directo 1 1 1 Code available at: https://github.com/acarballocastro/DIRECTO , the first iterative refinement-based generative model for directed graphs. Our approach brings together three core components of expressive graph generative modeling: (i) informative input features, (ii) an expressive neural architecture, and (iii) a robust generative framework. For input features, we find that, upon comprehensive evaluation, positional encodings specifically designed for graphs with an asymmetric adjacency matrix, are more successful than directionality-agnostic baselines. For the architecture, we employ a dual attention mechanism that performs cross-attention between edge features and their reversed counterparts, capturing both source-to-target and target-to-source information flow. Finally, these components are integrated within a robust discrete-state flow matching framework that enables efficient generation with state-of-the-art performance. Figure 1(b) gives an overview of our method and its components. To tackle the second challenge, we propose a benchmarking framework for rigorous evaluation of directed graph generation. It spans both synthetic and real-world datasets and systematic evaluation metrics tailored to directed graphs. The synthetic benchmarks cover different distributions, including acyclic and community-based graphs, while real-world benchmarks include a DAG-focused dataset for Neural Architecture Search (NAS) google2023tpugraphs and a scene understanding dataset krishna2017visualgenome . We evaluate Directo on the proposed benchmarks, where it consistently achieves strong performance across all settings, underscoring its effectiveness across structurally diverse datasets. Extensive ablations further reveal that the proposed dual attention mechanism is critical for modeling directional dependencies, while positional encodings enhance overall generation quality. Our main contributions are summarized as follows: (i) We propose Directo , the first flow-based generative model specifically tailored for directed graphs, combining a direction-aware dual attention block with positional encoding tailored to capture directionally asymmetric structural properties. (ii) We address the lack of benchmarks for directed graph generation by releasing a unified evaluation pipeline that encompasses both synthetic graphs with important structural properties and real-world datasets with meaningful applications. (iii) We conduct an extensive empirical analysis demonstrating that Directo achieves state-of-the-art performance on structurally diverse synthetic and real-world graphs. Overall, by addressing the two main bottlenecks in directed graph generation, we aim to lay the groundwork for future research and practical deployment of directed graph generation. 2 Background: Discrete Flow Matching for Graph Generation Notation We denote by G=\left(x^{(1:n:N)},\,e^{(1:i\neq j:N)}\right) directed graphs with N nodes. The set of nodes is denoted by \{x^{(n)}\}_{n=1}^{N} , and the set of directed edges by \{e^{(i,j)}\}_{1\leq i\neq j\leq N} . Both nodes and edges are categorical variables, where x^{(n)}\in\{1,\ldots,X\} and e^{(i,j)}\in\{1,\ldots,E\} . Problem statement Graph generative models aim to learn the underlying probability distribution over graphs that produced a given dataset, enabling the generation of new samples that preserve the structural patterns and properties of the training graphs. Recently, Discrete Flow Matching (DFM)-based models gat2024discrete ; campbell2024generative have achieved state-of-the-art performance in undirected graph generation qin2025defog . DFM belongs to a broader class of discrete state-space methods that recover the original graph distribution \bm{p}_{1} by progressively denoising samples from a pre-specified noise distribution \bm{p}_{\text{noise}} vignac2023digress ; xu2024disco ; siraudin2024cometh . By operating directly in the discrete spaces, these methods naturally align with the discreteness of graphs and are well-suited to capturing complex dependencies through iterative refinement. DFM distinguishes itself from other methods in this class by decoupling sampling from training, allowing for post-training sampling optimization. This additional layer of expressivity is particularly valuable for digraphs, where edge directionality introduces combinatorial complexity and exponentially expands the search space. We now introduce the two