Was ist ein gerichteter azyklischer Graph (DAG)?

Ein gerichteter azyklischer Graph (Directed Acyclic Graph, DAG) ist ein Diagrammtyp, in dem Knoten durch unidirektionale Verbindungen verbunden sind, die keine Zyklen bilden. DAGs werden verwendet, um Abhängigkeiten und Kausalzusammenhänge darzustellen.

Wie alle Diagramme können auch DAGs hilfreich sein, um Beziehungen zwischen Knoten zu visualisieren, die Daten, Aufgaben oder Ereignisse darstellen. DAGs sind jedoch nützlich, wenn es darum geht, Systeme darzustellen, in denen Ereignisse in einer bestimmten Reihenfolge ablaufen, wie z. B. ein Zeitplan von Aufgaben, die erledigt werden müssen, um ein Ziel zu erreichen.

DAGs sind auch für die Erstellung von Kausaldiagrammen wichtig: DAGs können Systeme darstellen, bei denen einige Knoten andere Knoten beeinflussen, aber die kausalen Effekte funktionieren nicht in umgekehrter Richtung. Ein grundlegendes Beispiel für solche einseitigen Beziehungen finden sich in Stammbäumen, da die DAGs aufeinanderfolgende Generationen von Eltern und Kindern abbilden.

Die Anwendung von DAGs ist in der Informatik weit verbreitet. Entwickler und Ingenieure verwenden DAGS für Datenpipelines und Datenverarbeitung, neuronale Netzwerkarchitektur, Robotertechnik und mehr.

Um besser zu verstehen, was ein gerichteter azyklischer Graph ist, lassen Sie uns seine Komponenten aufschlüsseln:

Knoten: Knoten, auch Scheitelpunkte genannt, stellen Entitäten, Objekte oder Variablen in einem Diagramm dar. Sie werden in der Regel als Punkte oder Kreise dargestellt.

Kanten: Kanten stellen Verbindungen zwischen Entitäten dar. Sie werden als Linien dargestellt.

Gerichtete Kanten: Gerichtete Kanten stellen Verbindungen dar, die nur in eine Richtung durchlaufen werden können. Pfeile an solchen Kanten zeigen ihre Richtung an.

Gerichtete Graphen: Graphen, die ausschließlich aus gerichteten Kanten bestehen, nennt man gerichtete Graphen oder „Digraphen“. Im Gegensatz dazu handelt es sich bei Graphen ohne gerichtete Kanten um ungerichtete Graphen.

Collider: Collider sind Knoten, auf die 2 gerichtete Kanten zeigen.

Pfade: Pfade sind eine Abfolge von Kanten, die einen bestimmten Knoten mit einem anderen verbinden. Pfade, die vollständig aus gerichteten Kanten bestehen, werden als gerichtete Pfade bezeichnet. Gerichtete Pfade, die auf Kausalzusammenhänge hinweisen, werden als Kausalpfade bezeichnet.

Baum: In der Informatik ist ein Baum ein gerichteter azyklischer Graph, in dem jeder Knoten nur eine gerichtete Kante hat, die auf ihn zeigt, mit Ausnahme des Startknotens (des „Wurzelknotens“). Während die Kanten vom Wurzelknoten ausgehen, zeigen keine Kanten auf den Wurzelknoten.

Neben dem Verständnis der Teile einer DAG ist es auch wichtig, eine Komponente zu erkennen, die ihr fehlt: ein Zyklus. Das „azyklisch“ in gerichteten azyklischen Graphen bezieht sich darauf, dass es in diesen Graphen keine Zyklen oder geschlossenen Kreisläufe gibt. Mit anderen Worten: Wenn Sie bei einem Knoten in einer DAG beginnen und die nachfolgenden Knoten und Kanten durchlaufen, ist es unmöglich, zum Startknoten zurückzukehren.

In der Graphentheorie (der Lehre von den Graphen) werden bei der Arbeit mit gerichteten azyklischen Graphen häufig mehrere Konzepte oder Verfahren angewendet. Dazu gehören:

• Topologische Sortierung
• Transitiver Abschluss
• Transitive Reduktion

Eine topologische Sortierung, die auch als topologische Ordnung bezeichnet wird, ist eine Möglichkeit, die Knoten eines DAG linear zu ordnen, sodass die Knoten, die auf andere Knoten zeigen, zuerst erscheinen und Nachfolger nicht vor ihren Vorgängern angezeigt werden. Topologische Sortieralgorithmen können solche Sequenzen auf der Grundlage von DAGs erzeugen.¹

In komplizierten Graphen kann es schwierig sein, zu erkennen, welche Knoten über gerichtete Pfade von anderen Knoten aus „erreichbar“ sind. Bei der transitiven Schließung werden solche indirekten Verbindungen zwischen Knoten identifiziert und grafisch dargestellt.

Wenn ein Graph beispielsweise eine gerichtete Kante hat, die die Knoten A und B verbindet, und eine weitere gerichtete Kante, die die Knoten B und C verbindet, so würde dies darauf hinweisen, dass A und C indirekt miteinander verbunden sind. Ein transitiver Abschluss würde zu einer neuen gerichteten Kante führen, die A mit C verbindet - jetzt der kürzeste Weg zwischen diesen beiden Knoten - zusätzlich zu den ursprünglichen gerichteten Kanten zwischen A und B und B und C. Wie bei der topologischen Sortierung können Algorithmen für die Berechnung des transitiven Abschlusses verwendet werden.

Die transitive Reduktion kann als das Gegenteil des transitiven Abschlusses betrachtet werden. Im Zusammenhang mit einem gerichteten Graphen hat die transitive Reduktion des Graphen die gleiche Anzahl von Knoten wie der ursprüngliche Graph und die Paare von Knoten, die erreichbar sind, sind die gleichen. Allerdings wird die Anzahl der Kanten in der transitiven Reduktion des Graphen minimiert.

Betrachten Sie zum Beispiel einen ursprünglichen Graphen, der eine gerichtete Kante enthält, die den Knoten A mit dem Knoten C verbindet, sowie eine Folge von gerichteten Kanten, die den Knoten A mit dem Knoten B und den Knoten B mit dem Knoten C verbinden. Eine transitive Reduktion dieses Graphen würde die Kante zwischen A und C ausschließen, während die Kanten zwischen der größeren Menge von Variablen erhalten bleiben: A und B und B und C.

Mit anderen Worten: Der längste Pfad zwischen A und C im ursprünglichen Graphen wird in den neuen Graphen aufgenommen, während der Pfad mit nur 1 Kante eliminiert wird. 

Gerichtet azyklische Graphen spielen in der Informatik in einer Vielzahl von Anwendungsfällen eine wichtige Rolle:

• Datenverarbeitung
• Neuronale Netze
• Kausale Inferenz beim maschinellen Lernen
• Robotertechnik
• Compiler-Design
• Blockchain

DAGs helfen Dateningenieuren, Datenstrukturen zu definieren und Datenflüsse zu optimieren. Plattformen zur Datenorchestrierung wie Apache Airflow verwenden beispielsweise DAGs (definiert in Python-Skripten), um Datenverarbeitungsaufgaben zu definieren und ihre Ausführungsreihenfolge in Datenpipelines und Workflows festzulegen.

In Fällen, in denen mehrere DAGs voneinander abhängen, können Orchestrierungstools Abhängigkeitsgraphen erstellen, um diese Beziehungen zu verdeutlichen.² Plattformen zur Daten-Observability können in Verbindung mit Plattformen zur Datenorchestrierung verwendet werden, um Probleme in der Datenpipeline zu erkennen und zu lösen.

Die beschleunigte Einführung von Anwendungen der generativen künstlichen Intelligenz, die auf Datenzugriff angewiesen sind, hat die Bedeutung von Datenpipelines und DAGs in der modernen Technologielandschaft verstärkt.

Ein neuronales Netzwerk ist ein Maschinenlernprogramm, das ähnlich wie das menschliche Gehirn entscheidet, indem es Prozesse verwendet, die die Art und Weise nachahmen, wie biologische Neuronen zusammenarbeiten, um Beobachtungen zu machen und Schlussfolgerungen zu ziehen. DAGs werden verwendet, um neuronale Netzwerke abzubilden und können besonders hilfreich bei der Visualisierung von tiefen neuronalen Netzwerken mit mehreren Schichten sein.

DAGs können eine Rolle bei den Bemühungen spielen, KI-Modellen beizubringen, kausale Beziehungen durch kausale Inferenz zu erkennen. Die kausale Inferenz ist ein Paradigma zur Bestimmung kausaler Effekte und verwendet oft DAGs. DAGs können zum Beispiel dabei helfen, „Confounder“ zu erkennen, also Variablen, die die tatsächliche Kausalität verzerren oder verschleiern. Insbesondere in der Epidemiologie entwickelt sich die mit kausalen Inferenzen angereicherte KI zu einem Instrument, das Forschern bei der Untersuchung von Krankheitsfaktoren helfen kann.³

Forscher haben vorgeschlagen, ein DAG- und großes Sprachmodell-basiertes Strukturplanungsverfahren zu verwenden, um die Leistung von zweiarmigen Robotern zu verbessern. Im vorgeschlagenen Framework erzeugt ein LLM ein DAG, das komplexe Aufgaben als Teilaufgaben darstellt, wobei die Kanten die Abhängigkeiten zwischen den Aufgaben anzeigen. Im Framework werden diese Informationen verwendet, um die Bewegungsplanung und die Koordination zwischen den 2 Armen für die Aufgabenausführung zu bestimmen.⁴

DAGs werden verwendet, um das Design von Compilern zu optimieren. Das sind Programme, die Programmiersprachen (Quellcode) in Anweisungen für Computer (Maschinencode) umwandeln. Ein DAG kann zum Beispiel dabei helfen, gemeinsame Unterausdrücke zu identifizieren, die zur Verbesserung der Effizienz eliminiert werden können.

Eine Blockchain, die auf einer DAG basiert, zeigt eine bessere Leistung als herkömmliche Blockchains, so die Forscher. Eine DAG-basierte Blockchain kann die parallele Verarbeitung von Transaktionen ermöglichen, wodurch sich die Rate der in einem bestimmten Zeitraum verarbeiteten Transaktionen erhöht und mehr Flexibilität und Skalierbarkeit ermöglicht wird. Solche Verbesserungen können in Bereichen wie dem Lieferkettenmanagement und der Zugangskontrolle für Internet-der-Dinge-Netzwerke Anwendung finden.^{5, 6}