2025-11-18T15:28:13.400087

Local Causal Discovery for Statistically Efficient Causal Inference

Schubert, Claassen, Magliacane
Causal discovery methods can identify valid adjustment sets for causal effect estimation for a pair of target variables, even when the underlying causal graph is unknown. Global causal discovery methods focus on learning the whole causal graph and therefore enable the recovery of optimal adjustment sets, i.e., sets with the lowest asymptotic variance, but they quickly become computationally prohibitive as the number of variables grows. Local causal discovery methods offer a more scalable alternative by focusing on the local neighborhood of the target variables, but are restricted to statistically suboptimal adjustment sets. In this work, we propose Local Optimal Adjustments Discovery (LOAD), a sound and complete causal discovery approach that combines the computational efficiency of local methods with the statistical optimality of global methods. First, LOAD identifies the causal relation between the targets and tests if the causal effect is identifiable by using only local information. If it is identifiable, it then finds the optimal adjustment set by leveraging local causal discovery to infer the mediators and their parents. Otherwise, it returns the locally valid parent adjustment sets based on the learned local structure. In our experiments on synthetic and realistic data LOAD outperforms global methods in scalability, while providing more accurate effect estimation than local methods.
academic

Lokale Kausale Entdeckung für statistisch effiziente kausale Inferenz

Grundinformationen

  • Paper-ID: 2510.14582
  • Titel: Local Causal Discovery for Statistically Efficient Causal Inference
  • Autoren: Mátyás Schubert (Universität Amsterdam), Tom Claassen (Radboud-Universität Nijmegen), Sara Magliacane (Universität Amsterdam)
  • Klassifizierung: stat.ML cs.AI cs.LG
  • Veröffentlichungsdatum: 16. Oktober 2025 (arXiv-Preprint)
  • Paper-Link: https://arxiv.org/abs/2510.14582v1

Zusammenfassung

Methoden der kausalen Entdeckung können für die Schätzung des kausalen Effekts zwischen einem Paar von Zielvariablen gültige Anpassungsmengen identifizieren, selbst wenn der zugrunde liegende kausale Graph unbekannt ist. Globale Methoden der kausalen Entdeckung konzentrieren sich auf das Erlernen des gesamten kausalen Graphen und können daher optimale Anpassungsmengen (d.h. solche mit der niedrigsten asymptotischen Varianz) wiederherstellen, werden aber mit zunehmender Anzahl von Variablen schnell rechnerisch unhandlich. Lokale Methoden der kausalen Entdeckung bieten durch die Konzentration auf die lokale Nachbarschaft der Zielvariablen eine skalierbarere Alternative, sind aber auf statistisch suboptimale Anpassungsmengen beschränkt. In dieser Arbeit präsentieren die Autoren LOAD (Local Optimal Adjustment Discovery), eine zuverlässige und vollständige Methode der kausalen Entdeckung, die die Recheneffizienz lokaler Methoden mit der statistischen Optimalität globaler Methoden verbindet.

Forschungshintergrund und Motivation

Problemdefinition

In der kausalen Inferenz ist die Schätzung des kausalen Effekts zwischen zwei Variablen eine Kernaufgabe. Wenn der zugrunde liegende kausale Graph unbekannt ist, müssen Methoden der kausalen Entdeckung verwendet werden, um gültige Anpassungsmengen für die Schätzung des kausalen Effekts zu identifizieren. Bestehende Methoden stehen vor einem grundlegenden Kompromiss:

  1. Das Dilemma globaler Methoden: Globale Methoden der kausalen Entdeckung (wie der PC-Algorithmus) können den vollständigen kausalen Graphen erlernen und optimale Anpassungsmengen wiederherstellen, aber ihre Rechenkomplexität wächst exponentiell mit der Anzahl der Variablen, was sie bei großen Problemen unmöglich macht.
  2. Die Einschränkungen lokaler Methoden: Lokale Methoden der kausalen Entdeckung (wie MB-by-MB, LDECC) sind rechnerisch effizient, können aber nur suboptimale Anpassungsmengen wiederherstellen, was zu einer höheren asymptotischen Varianz bei der Schätzung des kausalen Effekts führt.

Forschungsmotivation

Die Autoren identifizieren folgende Probleme bei bestehenden lokalen Methoden:

  • Der LocalPC-Algorithmus ist bei der Identifizierung von Nachbarvariablen nicht zuverlässig genug und kann fälschlicherweise nicht-benachbarte Ehepartner als benachbart identifizieren
  • Der LDECC-Algorithmus ist unvollständig und kann in bestimmten Fällen nicht alle orientierbaren Kanten orientieren
  • Der LDP-Algorithmus kann fälschlicherweise berichten, dass Effekte nicht identifizierbar sind, wenn sie tatsächlich null sind

Daher ist eine neue Methode erforderlich, die die Recheneffizienz lokaler Methoden beibehält und gleichzeitig die statistische Optimalität globaler Methoden erreicht.

Kernbeiträge

  1. Entwicklung von Methoden zur Bestimmung der Identifizierbarkeit kausaler Effekte basierend auf lokalen Informationen: Präsentation von notwendigen und hinreichenden Bedingungen, um allein mit lokalen Informationen zu bestimmen, ob ein kausaler Effekt identifizierbar ist.
  2. Vorstellung des LOAD-Algorithmus: Eine zuverlässige und vollständige Methode, die optimale Anpassungsmengen nur unter Verwendung lokaler Informationen um die Variablen herum identifiziert.
  3. Umfassende experimentelle Bewertung: Bewertung von LOAD auf synthetischen und realen Daten, die zeigt, dass es hochwertige Anpassungsmengen mit niedrigen Rechenkosten wiederherstellen kann.
  4. Theoretische Garantien: Nachweis der Zuverlässigkeit und Vollständigkeit von LOAD bei der Bestimmung der Identifizierbarkeit kausaler Effekte und beim Auffinden optimaler Anpassungsmengen.

Methodische Details

Aufgabendefinition

Gegeben ein Paar von Zielvariablen X und Y besteht das Ziel darin:

  1. Die kausale Beziehung zwischen X und Y zu bestimmen (expliziter Vorfahr, möglicher Vorfahr oder bestimmter Nicht-Vorfahr)
  2. Zu bestimmen, ob der kausale Effekt identifizierbar ist
  3. Falls identifizierbar, die optimale Anpassungsmenge zu finden; andernfalls eine lokal gültige Eltern-Anpassungsmenge zurückzugeben

LOAD-Algorithmus-Architektur

Der LOAD-Algorithmus besteht aus 5 Hauptschritten:

Schritt 1: Bestimmung der kausalen Beziehung zwischen Zielvariablen

Verwendung des LocalRelate-Algorithmus (Algorithmus 1) durch folgende Theoreme:

  • Explizite Vorfahr-Beziehung (Theorem 4.1): Für zwei verschiedene Knoten X und Y in CPDAG G gilt X ∈ ExplAn_G(Y) genau dann, wenn X ⊥̸⊥ Y | Pa_G(X) ∪ Sib_G(X)
  • Bestimmte Nicht-Vorfahr-Beziehung (Theorem 4.2): X ist ein bestimmter Nicht-Vorfahr von Y genau dann, wenn X ⊥⊥ Y | Pa_G(X)

Schritt 2: Prüfung der Identifizierbarkeit des kausalen Effekts

Vorstellung eines adaptiven Tests basierend auf lokalen Informationen:

Lemma 4.3: Für X ∈ PossAn_G(Y) in CPDAG G ist G relativ zu (X,Y) anpassungsfähig genau dann, wenn:

∀V ∈ Sib_G(X) : V ⊥⊥ Y | Pa_G(V) ∪ {X}

Diese Bedingung kann effizient durch den LocalAmenTest-Algorithmus (Algorithmus 2) erkannt werden.

Schritte 3-5: Konstruktion der optimalen Anpassungsmenge

Falls der kausale Effekt identifizierbar ist, konstruiert LOAD die optimale Anpassungsmenge durch folgende Schritte:

  1. Auffinden expliziter Nachkommen: Identifizierung aller expliziten Nachkommen von T
  2. Identifizierung von Vermittlungsknoten: Auffinden von Knoten, die sowohl explizite Nachkommen von T als auch explizite Vorfahren von O sind
  3. Konstruktion der optimalen Anpassungsmenge: 
    Oset_G(T,O) = Pa_G(Cn_G(T,O)) \ (Cn_G(T,O) ∪ {T})

Technische Innovationen

  1. Lokaler Anpassungstest: Erstmalige Präsentation von notwendigen und hinreichenden Bedingungen für die Prüfung der Anpassungsfähigkeit nur mit lokalen Informationen, wodurch die Notwendigkeit entfällt, alle möglichen gerichteten Pfade zu überprüfen.
  2. Caching-Mechanismus: Der verbesserte MB-by-MB-Algorithmus nutzt Caching zur Wiederverwendung von in früheren Läufen identifizierten Markov-Decken und lokalen Strukturen, was die Recheneffizienz erheblich verbessert.
  3. Theoretische Vollständigkeit: Nachweis, dass LOAD bei der Bestimmung kausaler Beziehungen, Identifizierbarkeit und optimaler Anpassungsmengen zuverlässig und vollständig ist.

Experimentelle Einrichtung

Datensätze

  1. Synthetische Daten:
    • Verwendung von zufällig generierten Erdős–Rényi-Graphen
    • Anzahl der Variablen: 100-1000
    • Erwarteter Grad: d=2, maximaler Grad: dmax=10
    • Stichprobengröße: nD=10000
  2. Reale Netzwerke:
    • MAGIC-NIAB-Netzwerk: 44 Knoten, durchschnittlicher Grad 3
    • ANDES-Netzwerk: 223 Knoten, durchschnittlicher Grad 3,03

Bewertungsmetriken

  1. Recheneffizienz: Anzahl der Tests auf bedingte Unabhängigkeit
  2. Qualität der Anpassungsmenge: F1-Score der optimalen Anpassungsmenge
  3. Qualität der Schätzung des kausalen Effekts: Interventionsdistanz

Vergleichsmethoden

  • Globale Methoden: PC, MARVEL, SNAP(∞)
  • Lokale Methoden: MB-by-MB+, LDECC+, LDP+ (erweiterte Versionen)

Implementierungsdetails

  • Signifikanzniveau: α = 0,01
  • Drei Arten von Tests auf bedingte Unabhängigkeit: Oracle d-Separation, Fisher-Z-Test, G²-Test
  • 100 Durchläufe pro Einstellung, wobei die besten und schlechtesten 5 Ergebnisse entfernt werden

Experimentelle Ergebnisse

Hauptergebnisse

Recheneffizienz

Die Anzahl der Tests auf bedingte Unabhängigkeit von LOAD ist in allen Einstellungen durchweg niedriger als bei globalen Methoden und etwas höher als bei lokalen Methoden:

  • Bei 1000 Knoten benötigt LOAD 9,43×10³ Tests, während PC 542,52×10³ Tests benötigt
  • Im Vergleich zu den 5,64×10³ Tests von MB-by-MB+ ist der zusätzliche Aufwand von LOAD angemessen

Qualität der Anpassungsmenge (F1-Score)

  • Oracle-Einstellung: LOAD erreicht einen perfekten F1=1,0, vergleichbar mit globalen Methoden
  • Fisher-Z-Test: LOAD übertrifft alle Baseline-Methoden bei allen Knotenzahlen mit F1-Scores von etwa 0,91-0,95
  • G²-Test: LOAD zeigt suboptimale Leistung, ist aber immer noch die zweitbeste Methode

Interventionsdistanz

LOAD erreicht in den meisten Einstellungen die niedrigste Interventionsdistanz:

  • Oracle-Einstellung: 0,003 (vergleichbar mit PC, SNAP)
  • Fisher-Z-Test: 0,014-0,026 (optimal)
  • G²-Test: 0,022-0,036 (zweitbest, nur hinter PC)

Ergebnisse auf realen Daten

Im MAGIC-NIAB-Netzwerk:

  • LOAD erreicht den besten F1-Score (0,62)
  • Erreicht die niedrigste Interventionsdistanz (0,007)
  • Anzahl der Tests auf bedingte Unabhängigkeit (4,35×10³) liegt zwischen lokalen und globalen Methoden

Ablationsstudien

  1. Bekannte Behandlungs-Ergebnis-Beziehung: Wenn Hintergrundwissen bereitgestellt wird, übertrifft LOAD* PC bei binären Daten
  2. Identifizierbare Zielpaare: In Einstellungen, die sicherstellen, dass der kausale Effekt identifizierbar ist, bleiben die Ergebnismuster konsistent
  3. Parameterempfindlichkeit: LOAD zeigt Robustheit gegenüber verschiedenen Stichprobengrößen und erwarteten Graden

Verwandte Arbeiten

Globale Methoden der kausalen Entdeckung

  • PC-Algorithmus: Klassische constraint-basierte Methode, aber hohe Rechenkomplexität
  • MARVEL: Rekursive Methode, aber immer noch schwer auf Hunderte von Variablen skalierbar
  • SNAP: Progressive Identifizierung und Entfernung bestimmter Nicht-Vorfahren, aber erfordert immer noch kausale Entdeckung auf allen möglichen Vorfahren

Lokale Methoden der kausalen Entdeckung

  • MB-by-MB: Sequenzielle Markov-Decken-Entdeckung, aber beschränkt auf suboptimale Anpassungsmengen
  • LDECC: Effiziente Collider-Prüfung, aber mit Zuverlässigkeits- und Vollständigkeitsproblemen
  • LDP: Erlernen von Anpassungsmengen durch Partitionierung, aber möglicherweise immer noch suboptimal mit Annahmebeschränkungen

Vorteile dieses Papiers

LOAD ist die erste Methode, die gleichzeitig folgende Ziele erreicht:

  1. Verwendung nur lokaler Informationen
  2. Wiederherstellung optimaler Anpassungsmengen
  3. Bereitstellung theoretischer Garantien (Zuverlässigkeit und Vollständigkeit)

Schlussfolgerung und Diskussion

Hauptschlussfolgerungen

  1. LOAD verbindet erfolgreich die Recheneffizienz lokaler Methoden mit der statistischen Optimalität globaler Methoden
  2. Der vorgeschlagene lokale Anpassungstest bietet eine effiziente Methode zur Bestimmung der Identifizierbarkeit kausaler Effekte
  3. Bei verschiedenen Datentypen und Netzwerkstrukturen zeigt LOAD überlegene Leistung

Einschränkungen

  1. Annahme kausaler Suffizienz: Die aktuelle Version setzt voraus, dass es keine latenten Verwirrvariablen oder Selektionsverzerrungen gibt
  2. Rechnerische Engpässe bei großen Netzwerken: Bei extrem großen Graphen kann die Markov-Decken-Suche immer noch ein Rechnerengpass sein
  3. Leistung bei binären Daten: Begrenzte Leistung bei Verwendung des G²-Tests auf binären Daten

Zukünftige Richtungen

  1. Erweiterung auf kausale Insuffizienz-Einstellungen: Umgang mit latenten Verwirrvariablen
  2. Optimierung der Markov-Decken-Entdeckung: Weitere Verbesserung der Recheneffizienz bei großen Netzwerken
  3. Verbesserung der Leistung bei endlichen Stichproben: Besonders bei binären Daten

Tiefgreifende Bewertung

Stärken

  1. Bedeutende theoretische Beiträge: Erstmalige Präsentation eines Anpassungstests basierend nur auf lokalen Informationen mit wichtigem theoretischen Wert
  2. Hohe Praktikabilität: Erreicht statistische Optimalität bei Beibehaltung der Recheneffizienz und löst damit ein Schlüsselproblem in praktischen Anwendungen
  3. Umfassende Experimente: Abdeckung verschiedener Datentypen, Netzwerkgrößen und Bewertungsmetriken mit überzeugenden Ergebnissen
  4. Algorithmische Vollständigkeit: Bereitstellung theoretischer Garantien für Zuverlässigkeit und Vollständigkeit mit strenger Algorithmus-Gestaltung

Mängel

  1. Annahmebeschränkungen: Die Annahme kausaler Suffizienz ist in praktischen Anwendungen möglicherweise nicht erfüllt
  2. Skalierungsprobleme: Obwohl besser als globale Methoden, gibt es immer noch rechnerische Herausforderungen bei extrem großen Netzwerken
  3. Leistung bei endlichen Stichproben: In bestimmten Einstellungen mit endlichen Stichproben ist die Leistung nicht stabil genug

Auswirkungen

  1. Akademischer Wert: Bietet neue theoretische Rahmen und Algorithmus-Designideen für das Feld der kausalen Entdeckung
  2. Praktischer Wert: Von großer Bedeutung für praktische Anwendungen, die Schätzung kausaler Effekte erfordern
  3. Reproduzierbarkeit: Detaillierte Algorithmus-Beschreibungen und experimentelle Einrichtungen ermöglichen einfache Reproduktion und Erweiterung

Anwendungsszenarien

  1. Kausale Inferenz mittlerer Größe: Schätzung kausaler Effekte mit Hunderten bis Tausenden von Variablen
  2. Rechnerisch begrenzte Ressourcen: Anwendungsszenarien, die ein Gleichgewicht zwischen Recheneffizienz und statistischer Leistung erfordern
  3. Kausale Suffizienz-Umgebung: Beobachtungsstudien ohne wichtige latente Verwirrvariablen

Referenzen

Das Papier zitiert wichtige Literatur im Bereich der kausalen Inferenz, einschließlich:

  • Pearl (2009): Causality - Klassisches Lehrbuch der kausalen Inferenz
  • Spirtes et al. (2000): Grundlegende Arbeiten zur constraint-basierten kausalen Entdeckung
  • Henckel et al. (2022): Graphische Kriterien für optimale Anpassungsmengen
  • Perković et al. (2015): Definition und Eigenschaften der Anpassungsfähigkeit

Gesamtbewertung: Dies ist ein hochqualitatives Papier zur kausalen Inferenz mit wichtigen Beiträgen auf theoretischer und praktischer Ebene. Der LOAD-Algorithmus löst elegant das Kompromiss-Problem zwischen Recheneffizienz und statistischer Optimalität in der kausalen Entdeckung und hat bedeutende akademische Werte und Anwendungsperspektiven.