Technisches Resümee: Falsifizierung kausaler Graphen mittels Ausreißer-Ereignissen

Problemstellung

Wahre kausale Beziehungen sind im Voraus selten bekannt, und die Ableitung kausaler Graphen aus Daten bleibt eine anspruchsvolle Aufgabe. Eine grundlegende Schwierigkeit liegt in der Bewertung der Gültigkeit eines gegebenen Kandidaten-Kausalgraphen in Abwesenheit von Ground Truth. Während frühere Methoden interventionalen Daten oder Konsistenzprüfungen über Variablen-Teilmengen nutzten, erfordern diese oft mehrere Stichproben, den Zugriff auf bedingte Unabhängigkeits-Orakel oder setzen spezifische parametrische Formen voraus. In praktischen Umgebungen wie der Cloud-Überwachung oder der Fertigung ist es oft prohibitiv teuer oder unmöglich, mehrere Stichproben seltener anomaler Ereignisse zu sammeln. Zudem mangelt es bestehenden Methoden zur Falsifizierung kausaler Modelle mittels Beobachtungsdaten oft an validen statistischen Tests mit kontrollierten Falsch-Positiv-Raten.

Diese Arbeit adresset das Problem der Falsifizierung eines Kandidaten-Kausalgraphen unter Verwendung einer einzelnen Ausreißer-Stichprobe. Das Ziel ist die Prüfung der Nullhypothese $H_0: \hat{G} = G$, wobei $\hat{G}$ ein geschätzter kausaler Graph und $G$ der wahre kausale Graph ist, indem die Propagationscharakteristika von Ausreißer-Ereignissen genutzt werden.

Methodik

Der vorgeschlagene Ansatz basiert auf dem Prinzip, dass schwache Ausreißer selten starke Ausreißer verursachen. Dieses Prinzip, das zuvor in der Ursachenanalyse (Root Cause Analysis) zur Identifizierung von Ursachen ohne vorheriges Graphwissen genutzt wurde, wird hier invertiert, um Graphen zu falsifizieren: Wenn ein Kandidatengraph ein Ausreißer-Propagationsmuster impliziert, das inkonsistent mit diesem Prinzip ist, wird der Graph abgelehnt.

Kernkonzepte

1. Ausreißer-Modellierung: Ausreißer werden als Ergebnis einer „Soft-Intervention“ auf eine Teilmenge von Wurzelursachen-Variablen $R$ modelliert. Die Verteilung einer Ausreßer-Stichprobe ist eine „korrumpierte“ Version der wahren Verteilung, bei der die Mechanismen für die Variablen in $R$ verändert wurden.
2. Informationstheoretische (IT) Ausreißer-Scores: Die Methode nutzt IT-Ausreißer-Scores, definiert als $S(x) = -\log P(\text{event})$.
   • Marginale Scores: $S(x_i) = -\log P(\tau_i(X_i) \geq \tau_i(x_i))$.
   • Bedingte Scores: $S(x_i | pa_i) = -\log P(\tau_i(X_i) \geq \tau_i(x_i) | PA_i = pa_i)$.
     Unter der Nullhypothese, dass der Graph korrekt ist und die Stichprobe aus dem regulären Mechanismus (unter Ausschluss der Wurzelursachen) gezogen wurde, folgen diese Scores einer unabhängigen Standard-Exponentialverteilung, $\text{Exp}(1)$.

Statistische Tests

Die Autoren schlagen vier statistische Tests vor, die auf diesen Scores basieren, um $H_0$ abzulehnen. Die Tests sind darauf ausgelegt, eine Kontrolle der Falsch-Positiv-Rate (valide p-Werte) und Power-Garantien gegen spezifische Klassen falscher Graphen zu bieten.

1. Bedingte Score-Tests (unter Annahme bekannter Wurzelursachen)

Wenn die Wurzelursachen $R$ bekannt sind und der Graph ein gerichteter azyklischer Graph (DAG) ist, sind die bedingten Scores der Nicht-Wurzelvariablen unter $H_0$ unabhängige $\text{Exp}(1)$-Variablen. Das Paper schlägt vor:

• Fisher-basierter Test: Summiert die bedingten Scores ($S_{sum}$). Der p-Wert wird aus der Erlang-Verteilung (Summe von Exponentialverteilungen) abgeleitet.
• Tippett-basierter Test: Verwendet den maximalen bedingten Score ($S_{max}$). Der p-Wert wird aus der Verteilung des Maximums von Exponentialverteilungen abgeleitet.
• Binomial-Test: Zählt die Anzahl der Scores, die einen Schwellenwert $t$ überschreiten ($N_t$). Der p-Wert folgt einer Binomialverteilung.
• Kolmogorov-Smirnov (KS) Test: Vergleicht die empirische CDF der Scores mit der theoretischen $\text{Exp}(1)$ CDF ($D_L$).

2. Marginale Score-Tests (Polytree-Annahme)

Die Inferenz bedingter Verteilungen ist mit begrenzten Daten statistisch schlecht gestellt. Die Autoren passen die ersten drei Tests an, um nur marginale Scores zu verwenden, unter der Voraussetzung, dass der wahre Graph ein Polytree (ein DAG ohne ungerichtete Zyklen) ist.

• Score-Typicalität: Die Methode stützt sich auf die Bedingung $S(y|x) \geq |S(y) - S(x)|_+$. Wenn diese erfüllt ist, impliziert dies, dass ein schwacher Ausreißer selten einen starken verursacht.
• Teststatistiken: Die marginalen Tests nutzen den „Sprung“ in den Scores: $|S(x_i) - S(PA_i)|_+$.
• Validität: Unter der Polytree-Annahme und Score-Typicalität werden diese marginalen Statistiken durch ihre bedingten Gegenstücke stochastisch dominiert, was valide p-Werte sicherstellt.

3. Unbekannte Wurzelursachen

Falls die Wurzelursachen unbekannt sind, aber eine obere Schranke $k$ für deren Anzahl bekannt ist, schlagen die Autoren ein Maximum Leave-$k$-out-Verfahren vor. Der Teststatistik wird für jede Teilmenge von $k$ Variablen berechnet, die als potenzielle Wurzelursachen behandelt werden, und das maximale p-Verhalten wird genommen. Dies kontrolliert die Falsch-Positiv-Rate, ohne Selektionsbias einzuführen.

Theoretische Garantien

• Kontrolle der Falsch-Positiv-Rate: Die Tests liefern rigorose p-Werte und stellen sicher, dass $P(\text{reject } H_0 | H_0 \text{ ist wahr}) \leq \alpha$.
• Power-Garantien: Das Paper leitet untergrenzige Raten für den Zerfall der Ausreißer-Scores entlang kausaler Pfade unter Verwendung der Strong Data Processing Inequality (SDPI) ab.
  • Wenn einem wahren Nachfahren einer Wurzelursache falsche Eltern zugewiesen werden (z. B. Nicht-Nachfahren oder Eltern, die weiter von der Wurzel entfernt sind), ist der resultierende „Score-Sprung“ nach unten begrenzt.
  • Die Power der Tests steigt mit der Stärke des Ausreißers ($\lambda$) und dem Anteil der falschen Kanten ($\pi$).
  • Spezifische Optimalitätsresultate (Uniformly Most Powerful) werden für den Summen-Test (Fisher) gegen globale Verschiebungen der Ratenparameter und den Max-Test (Tippett) gegen einzelne dominante Ausreißer gezeigt.

Experimentelle Ergebnisse

Die Autoren evaluierten ihre Methoden sowohl auf synthetischen als auch auf realen Datensätzen und verglichen sie mit Baselines, einschließlich eines Permutations-basierten Tests (Eulig et al., 2025) und einem kausalen Discovery-Algorithmus (GRaSP).

Synthetische Daten

• Setup: Zufällige DAGs mit 20 Knoten. Ausreißer wurden in eine zufällige Wurzelursache injiziert und propagiert. Die „Ground Truth“ wurde teilweise korrumpiert, um Testgraphen mit variierenden Anteilen korrekter Kanten ($|K|/|N|$) zu erzeugen.
• Ergebnisse:
  • Die vorgeschlagenen Tests zeigten steigende Ablehnungsraten, wenn der Anteil falscher Kanten zunahm.
  • Bedingte Score-Tests waren generell leistungsfähiger als marginale Score-Tests, was zu erwarten war.
  • Die GRaSP-Baseline war überempfindlich und lehnte fast alle Graphen ab (einschließlich der Ground Truth) aufgrund von endlichen Stichproben-Diskrepanzen.
  • Die Permutations-Baseline verhielt sich erwartungsgemäß und lehnte Graphen nur ab, wenn diese schlechter als zufällig waren.
  • Die Power stieg mit stärkeren injizierten Anomalien und wenn mehrere Ausreißer-Stichproben verfügbar waren.

Reale Daten

1. PetShop Datensatz (Cloud Computing): Die Studie testete eine „Service-Abhängigkeitskarte“ (mit umgekehrten Kanten) als Proxy für den kausalen Graphen.
   • Ergebnis: Die vorgeschlagenen Tests lehnten diesen Graphen mit einer Rate ab, die signifikant höher als das Signifikanzniveau war, insbesondere in Szenarien mit hohem Traffic. Dies deutet darauf hin, dass die Service-Map zwar besser als zufällig ist, aber nicht der wahre kausale Graph ist.
2. Causal Chambers Datensatz: Ein physisches Testbed mit einer bekannten, genauen kausalen Struktur.
   • Ergebnis: Die Tests lehnten den Graphen mit einer Rate ab, die konsistent mit dem Signifikanzniveau war (d. h. sie lehnten den korrekten Graphen nicht fälschlicherweise ab), was die Kontrolle der Falsch-Positiv-Rate validiert.

Bedeutung und Ansprüche

Das Paper beansprucht, die ersten statistischen Tests für die Nullhypothese zu präsentieren, dass ein gegebener kausaler Graph der wahre kausale Graph ist und dabei drei spezifische Kriterien erfüllt:

1. Kontrolle der Falsch-Positiv-Rate: Sie liefern valide p-Werte, die sicherstellen, dass die Rate der Fehlablehnungen begrenzt ist.
2. Power-Garantien: Sie besitzen nachgewiesene Power gegen eine breite Klasse falscher kausaler Graphen, speziell dort, wo die Propagation von Ausreißern das „Weak-to-Strong“-Prinzip verletzt.
3. Ein-Stichproben-Betrieb: Sie können effektiv mit nur einer einzelnen Ausreißer-Stichprobe operieren, ein kritisches Merkmal für Domänen, in denen anomale Ereignisse selten und teuer zu beobachten sind.

Die Autoren betonen, dass diese Arbeit die Lücke zwischen der Literatur zur Ursachenanalyse (Root Cause Analysis) und der kausalen Graph-Evaluierung schließt, indem sie das Prinzip der Ausreißer-Propagation in ein rigoroses Falsifizierungswerkzeug verwandelt. Die Methode erfordert keine interventionalen Daten oder mehrere Stichproben aus dem anomalen Regime, was sie anwendbar macht, wenn traditionelle kausale Discovery- oder Falsifizierungsmethoden scheitern.