Neuer Algorithmus BUILD rekonstruiert lineare DAGs exakt

In der Kausalitätsforschung ist die Rekonstruktion von gerichteten azyklischen Graphen (DAGs) aus Beobachtungsdaten ein zentrales Ziel. Unter dem Modell linearer Gaußscher Strukturgleichungen mit gleichen Rauschvarianten lässt sich die Struktur eindeutig bestimmen. Forscher haben gezeigt, dass die Ensemble-Genauigkeitsmatrix der Beobachtungen ein charakteristisches Muster aufweist, das die Wiederherstellung des DAGs erleichtert.

Auf dieser Erkenntnis basiert der neue Algorithmus BUILD (Bottom‑Up Inference of Linear DAGs). BUILD arbeitet deterministisch in Schritten: Zunächst werden Blattknoten und deren Eltern identifiziert, anschließend werden die Blätter entfernt, indem die zugehörigen Kanten abgeschnitten werden. Dieser Prozess wiederholt sich, bis der gesamte Graph exakt aus der wahren Präzisionsmatrix rekonstruiert ist.

In der Praxis muss die Präzisionsmatrix aus endlich vielen Datenpunkten geschätzt werden, was zu numerischen Problemen führen kann. BUILD begegnet diesem Problem, indem es periodisch die Präzisionsmatrix neu berechnet – dabei reduziert sich die Dimensionalität, sobald Blätter entfernt werden. Dieser Ansatz erhöht die Robustheit, auch wenn er die Laufzeit etwas verlängert.

Reproduzierbare Tests an anspruchsvollen synthetischen Benchmarks zeigen, dass BUILD im Vergleich zu führenden DAG‑Lernalgorithmen sehr gute Ergebnisse liefert und gleichzeitig die Komplexität explizit steuert.