Qu’est-ce qu’un graphe acyclique dirigé (DAG) ?

Un graphe acyclique dirigé (DAG) est un type de graphe dans lequel les nœuds sont reliés par des connexions à sens unique qui ne forment aucun cycle. Les DAG sont utilisés pour illustrer les dépendances et les relations de cause à effet.

Comme tous les graphiques, les DAG peuvent être utiles pour visualiser les relations entre les nœuds représentant des données, des tâches ou des événements. Cependant, les DAG permettent de représenter des systèmes dans lesquels les événements se produisent dans un ordre spécifique, comme un calendrier de tâches à accomplir pour atteindre un objectif.

Les DAG sont également importants pour créer des diagrammes de causalité : les DAG peuvent représenter des systèmes où certains nœuds ont un impact sur d’autres nœuds, mais les effets causaux ne fonctionnent pas dans l’autre sens. Un exemple de base de telles relations à sens unique peut être trouvé dans les arbres généalogiques, car les DAG cartographient les générations successives de parents et d’enfants.

L’utilisation des DAG est courante en informatique. Les développeurs et les ingénieurs utilisant les DAG pour les pipelines et le traitement de données, l’architecture des réseaux neuronaux, la robotique, etc.

Pour mieux comprendre le principe du graphe acyclique dirigé, détaillons ses composants :

Nœuds : les nœuds, également appelés vertices, représentent des entités, des objets ou des variables sur un graphique. Ils sont généralement représentés sous forme de points ou de cercles.

Arêtes : les arêtes symbolisent les connexions entre les entités. Elles sont représentées par des lignes.

Arêtes dirigées : les arêtes dirigées représentent des connexions qui peuvent être parcourues dans une seule direction. Les flèches sur ces arêtes indiquent leur direction.

Graphes dirigés : les graphes composés entièrement d’arêtes dirigées sont des graphes dirigés ou digraphes. En revanche, les graphes sans arêtes dirigées sont des graphiques non dirigés.

Collisionneurs : les collisionneurs sont des nœuds vers lesquels deux arêtes dirigées pointent.

Chemins : les chemins sont une séquence d’arêtes reliant un nœud donné à un autre. Les chemins composés entièrement d’arêtes dirigées sont appelés chemins dirigés. Les chemins dirigés qui indiquent des relations causales sont appelés chemins causaux.

Arbre : en informatique, un arbre est un graphe acyclique dirigé où chaque nœud n’a qu’une seule arête dirigée vers lui, à l’exception du nœud de départ (le nœud « racine »). Alors que les arêtes s’étendent à partir du nœud racine, aucune arête ne pointe vers le nœud racine.

En plus de comprendre les éléments d’un DAG, il est également important de reconnaître un composant qui lui manque : un cycle. Dans un graphe acyclique dirigé, le terme « acyclique » fait référence à l’absence de cycles ou de boucles fermées sur ce type de graphes. En d’autres termes, lorsque vous partez d’un nœud dans un DAG et que vous traversez les nœuds et les arêtes successifs, il est impossible de revenir au nœud de départ.

Dans la théorie des graphes (l’étude des graphes), plusieurs concepts ou processus sont souvent appliqués lorsque l’on travaille avec des graphes acycliques dirigés. En voici quelques exemples :

• Tri topologique
• Clôture transitive
• Réduction transitive

Un tri topologique, également connu sous le nom d’ordre topologique, est une manière d’organiser les nœuds d’un DAG de manière linéaire afin que les nœuds qui pointent vers d’autres nœuds apparaissent en premier et que les successeurs n’apparaissent pas avant leurs prédécesseurs. Les algorithmes de tri topologique peuvent produire de telles séquences basées sur des DAG.¹

Dans les graphes complexes, il peut être difficile de reconnaître les nœuds qui peuvent être « accessibles » par des chemins dirigés à partir d’autres nœuds. Dans la clôture transitive, ces liens indirects entre les nœuds sont identifiés et schématisés.

Par exemple, si un graphique comporte une arête dirigée reliant le nœud A et le nœud B et une autre arête dirigée reliant le nœud B et le nœud C, cela indiquera que A et C sont liés indirectement. Un résultat de fermeture transitive donnerait une nouvelle arête reliant A à C (qui est désormais le chemin le plus court entre ces deux nœuds) en plus des arêtes dirigées originales entre A et B et B et C. Comme pour le tri topologique, les algorithmes peuvent être utilisés pour les calculs de clôture transitive.

La réduction transitive peut être considérée comme l’inverse de la clôture transitive. Dans le contexte d’un graphe orienté, la réduction transitive du graphe a le même nombre de nœuds que le graphe original et les paires de nœuds atteignables sont les mêmes. Cependant, le nombre d’arêtes dans la réduction transitive du graphe est réduit au minimum.

Considérons, par exemple, un graphe original qui comprend une arête dirigée reliant le nœud A au nœud C, et une séquence d’arêtes dirigées reliant le nœud A au nœud B et le nœud B au nœud C. Une réduction transitive de ce graphique exclurait l’arête entre A et C tout en conservant les arêtes entre l’ensemble plus large de variables : A et B et B et C.

En d’autres termes, le chemin le plus long entre A et C dans le graphique original est inclus dans le nouveau graphe, tandis que le chemin avec une seule arête est éliminé. 

Les graphiques acycliques dirigés occupent une place prépondérante dans l’informatique à travers une multitude de cas d’utilisation :

• Traitement de données
• Réseaux neuronaux
• Inférence causale dans le machine learning
• Robotique
• Conception du compilateur
• Blockchain

Les DAG aident les ingénieurs de données à définir des structures de données et à optimiser les flux de données. Les plateformes d’harmonisation des données, comme par exemple Apache Airflow, utilisent des DAG (définis dans les scripts Python) pour définir les tâches de traitement des données et spécifier leur ordre d’exécution dans les pipelines de données et les workflows.

Dans les cas où plusieurs DAG dépendent les uns des autres, les outils d’orchestration peuvent créer des graphiques de dépendance pour clarifier ces relations.² Les plateformes d’observabilité des données peuvent être utilisées avec les plateformes d’harmonisation des données pour identifier et résoudre les problèmes liés au pipeline de données.

L’accélération de l’adoption d’applications d’intelligence artificielle générative, qui reposent sur l’accès aux données, a amplifié l’importance des pipelines de données et des DAG dans l’environnement technologique moderne.

Un réseau neuronal est un programme de machine learning qui prend des décisions comme le ferait un cerveau humain en utilisant des processus qui imitent la façon dont les neurones biologiques collaborent via des observations, puis des conclusions. Les DAG sont utilisés pour cartographier les réseaux neuronaux et peuvent être particulièrement utiles pour la visualisation des réseaux neuronaux profonds à couches multiples.

Les DAG peuvent jouer un rôle dans les efforts visant à « apprendre » aux modèles IA à reconnaître les relations causales par le biais de l’inférence causale. L’inférence causale est un paradigme permettant de déterminer les effets de causalité et utilise souvent des DAG. Par exemple, les DAG peuvent aider à détecter les « facteurs de confusion », qui sont des variables qui déforment ou obscurcissent la causalité réelle. L’IA améliorée par l’inférence causale est en train de devenir un outil en particulier pour l’épidémiologie. Elle pourra aider les chercheurs dans leurs études sur la recherche des déterminants de la maladie.³

Des chercheurs ont proposé d’utiliser une méthode de planification structurelle basée sur un DAG et un grand modèle de langage (LLM) pour améliorer la performance des robots à deux bras. Dans le cadre des exigences proposé, un LLM génère un DAG qui représente des tâches complexes sous forme de sous-tâches, avec des arêtes indiquant les interdépendances. Dans le framework, ces informations sont utilisées pour déterminer la planification des mouvements et la coordination entre les 2 bras pour l’exécution des tâches.⁴

Les DAG sont utilisés pour optimiser la conception des compilateurs, qui sont des programmes qui convertissent les langages de programmation (code source) en instructions pour les ordinateurs (code machine). Par exemple, un DAG peut aider à identifier les sous-expressions courantes qui peuvent être éliminées pour améliorer l’efficacité.

Selon les chercheurs, une blockchain basée sur un DAG présente de meilleures performances que les blockchains conventionnelles. Une blockchain basée sur DAG peut permettre le traitement parallèle des transactions, augmentant ainsi le taux de transactions traitées sur une certaine période et permettant plus de flexibilité et d’évolutivité. De telles améliorations peuvent avoir des applications dans des domaines tels que la gestion de la chaîne d’approvisionnement et les contrôles d’accès aux réseaux de l’Internet des objets .^{5, 6}