Technische Samenvatting: Het falsificeren van causale grafen met uitschietergebeurtenissen

Probleemstelling

Ware causale relaties zijn zelden a priori bekend, en het afleiden van causale grafen uit data blijft een uitdagende taak. Een fundamentele moeilijkheid ligt in het beoordelen van de geldigheid van een gegeven kandidaat-causale graaf bij afwezigheid van de grondwaarheid. Hoewel eerdere methoden gebruik hebben gemaakt van interventionele data of consistentiecontroles over variabelensubsets, vereisen deze vaak meerdere monsters, toegang tot conditionele onafhankelijkheidsorakels, of gaan zij uit van specifieke parametrische vormen. In praktische omgevingen zoals cloudmonitoring of productie is het vaak prohibitief duur of onmogelijk om meerdere monsters van zeldzame anomalieën te verzamelen. Bovsamen missen bestaande methoden voor het falsificeren van causale modellen met observationele data vaak geldige statistische tests met gecontroleerde fout-positieve ratio's.

Dit werk adresseert het probleem van het falsificeren van een kandidaat-causale graaf met behulp van een enkelvoudig uitschieler-monster. Het doel is om de nulhypothese $H_0: \hat{G} = G$ te testen, waarbij $\hat{G}$ een geschatte causale graaf is en $G$ de ware causale graaf, door gebruik te maken van de propagatiekenmerken van uitschietergebeurtenissen.

Methodologie

De voorgestelde aanpak is gebaseerd op het principe dat zwakke uitschieters zelden sterke uitschieters veroorzaken. Dit principe, dat eerder werd toegepast in root cause analysis om oorzaken te identificeren zonder voorafgaande kennis van de graaf, wordt hier omgekeerd om grafen te falsificeren: als een kandidaat-graaf een uitschieter-propagatiepatroon impliceert dat inconsistent is met dit principe, wordt de graaf verworpen.

Kernconcepten

1. Uitschieter-modellering: Uitschieters worden gemodelleerd als het resultaat van een "soft-intervention" op een subset van root cause variabelen $R$. De distributie van een uitschieler-monster is een "gecorrumpeerde" versie van de ware distributie waarbij de mechanismen voor variabelen in $R$ zijn gewijzigd.
2. Informatie-theoretische (IT) uitschieler-scores: De methode maakt gebruik van IT uitschieler-scores gedefinieerd als $S(x) = -\log P(\text{event})$.
   • Marginale scores: $S(x_i) = -\log P(\tau_i(X_i) \geq \tau_i(x_i))$.
   • Conditionele scores: $S(x_i | pa_i) = -\log P(\tau_i(X_i) \geq \tau_i(x_i) | PA_i = pa_i)$.
     Onder de nulhypothese dat de graaf correct is en het monster is getrokken uit het normale mechanisme (exclusief de root causes), volgen deze scores een onafhankelijke standaard exponentiële distributie, $\text{Exp}(1)$.

Statistische Tests

De auteurs stellen vier statistische tests voor op basis van deze scores om $H_0$ te verwerpen. De tests zijn ontworpen om fout-positieve controle te hebben (geldige p-waarden) en power-garanties tegen specifieke klassen van incorrecte grafen.

1. Conditionele score-tests (uitgaande van bekende root causes)

Wanneer de root causes $R$ bekend zijn en de graaf een Directed Acyclic Graph (DAG) is, zijn de conditionele scores van niet-root variabelen onafhankelijke $\text{Exp}(1)$ variabelen onder $H_0$. Het artikel stelt voor:

• Fisher-gebaseerde test: Sommeert de conditionele scores ($S_{sum}$). De p-waarde wordt afgeleid van de Erlang-distributie (som van exponentialen).
• Tippett-gebaseerde test: Gebruikt de maximale conditionele score ($S_{max}$). De p-waarde wordt afgeleid van de distributie van het maximum van exponentialen.
• Binomiale test: Telt het aantal scores dat een drempelwaarde $t$ overschrijdt ($N_t$). De p-waarde volgt een Binomiale distributie.
• Kolmogorov-Smirnov (KS) test: Vergelijkt de empirische CDF van de scores met de theoretische $\text{Exp}(1)$ CDF ($D_L$).

2. Marginale score-tests (Polytree aanname)

Het afleiden van conditionele distributies is statistisch slecht gesteld met beperkte data. De auteurs passen de eerste drie tests aan om alleen marginale scores te gebruiken, mits de ware graaf een polytree is (een DAG zonder ongerichte cycli).

• Score Typicality: De methode steunt op de conditie $S(y|x) \geq |S(y) - S(x)|_+$. Wanneer dit wordt voldaan, impliceert dit dat een zwakke uitschieter zelden een sterke uitschieter veroorzaakt.
• Teststatistieken: De marginale tests gebruiken de "jump" in scores: $|S(x_i) - S(PA_i)|_+$.
• Geldigheid: Onder de polytree-aanname en score typicality worden deze marginale statistieken stochastisch gedomineerd door hun conditionele tegenhangers, wat geldige p-waarden garandeert.

3. Onbekende root causes

Als de root causes onbekend zijn maar een bovengrens $k$ op hun aantal bekend is, stellen de auteurs een maximum leave-$k$-out procedure voor. De teststatistiek wordt berekend voor elke subset van $k$ variabelen die als potentiële root causes worden behandeld, en het maximale p-waarde wordt genomen. Dit controleert de fout-positieve ratio zonder selectiebias te introduceren.

Theoretische Garanties

• Fout-positieve Controle: De tests bieden rigoureuze p-waarden, waardoor $P(\text{verwerp } H_0 | H_0 \text{ is waar}) \leq \alpha$.
• Power-garanties: Het artikel leidt ondergrenzen af voor de afname van de uitschieler-scores langs causale paden met behulp van de Strong Data Processing Inequality (SDPI).
  • Als een ware afstammeling van een root cause onjuiste ouders krijgt toegewezen (bijv. niet-afstammelingen of ouders die verder van de root liggen), is de resulterende "score jump" ondergrens bepaald.
  • De power van de tests neemt toe met de sterkte van de anomalie ($\lambda$) en de proportie incorrecte randen ($\pi$).
  • Specifieke optimaliteitsresultaten (Uniformly Most Powerful) worden getoond voor de som-test (Fisher) tegen globale verschuivingen in de rate parameters en de max-test (Tippett) tegen enkelvoudige dominante uitschieters.

Experimentele Resultaten

De auteurs evalueerden hun methoden op zowel synthetische als real-world datasets, waarbij ze hun methoden vergeleken met baselines, waaronder een permutatie-gebaseerde test (Eulig et al., 2025) en een causale discovery algoritme (GRaSP).

Synthetische Data

• Setup: Willekeurige DAGs met 20 knopen. Uitschieters werden geïnjecteerd in een willekeurige root cause en gepropageerd. De "grondwaarheid" graaf werd gedeeltelijk gecorrumpeerd om testgrafen te creëren met variërende fracties correcte randen ($|K|/|N|$).
• Bevindingen:
  • De voorgestelde tests vertoonden een toenemende afwijzingsratio naarmate de fractie incorrecte randen toenam.
  • Conditionele score-tests presteerden over het algemeen beter dan marginale score-tests, zoals verwacht.
  • De GRaSP baseline was overgevoelig en verwierp bijna alle grafen (inclusclusief de grondwaarheid) vanwege finite-sample discrepanties.
  • De permutatie baseline gedroeg zich zoals verwacht, waarbij grafen pas werden verworpen als ze slechter waren dan willekeurig.
  • De power nam toe met sterkere geïnjecteerde anomalieën en wanneer meerdere uitschieler-monsters beschikbaar waren.

Real-World Data

1. PetShop Dataset (Cloud Computing): De studie testte een "service dependency map" (met omgedraaide randen) als een proxy voor de causale graaf.
   • Resultaat: De voorgestelde tests verwierpen deze graaf met een rate die aanzienlijk hoger lag dan het significantieniveau, vooral in scenario's met veel verkeer. Dit suggereert dat de service map, hoewel beter dan willekeurig, niet de ware causale graaf is.
2. Causal Chambers Dataset: Een fysieke testopstelling met een bekende, accurate causale structuur.
   • Resultaat: De tests verwierpen de graaf met een rate die consistent was met het significantieniveau (dat wil zeggen, ze verwierpen de correcte graaf niet onterecht), wat de fout-positieve controle valideert.

Betekenis en Claims

Het artikel claimt de eerste statistische tests te presenteren voor de nulhypothese dat een gegeven causale graaf de ware causale graaf is, die voldoen aan drie specifieke criteria:

1. Fout-positieve Controle: Ze bieden geldige p-waarden, waardoor de rate van foutieve verwerpen begrensd is.
2. Power-garanties: Ze hebben bewezen power tegen een brede klasse van incorrecte causale grafen, speciferlijk waar de propagatie van uitschieters de "weak-to-strong" principes schendt.
3. Single Sample Operatie: Ze kunnen effectief opereren met slechts één uitschieler-monster, een cruciaal kenmerk voor domeinen waar anomalieën zeldzaam en kostbaar zijn om te observeren.

De auteurs benadrukken dat dit werk de kloof tussen de root cause analysis literatuur en causale graaf-evaluatie overbrugt, door het principe van uitschieter-propagatie om te zetten in een rigoureus falsificatie-instrument. De methode vereist geen interventionele data of meerdere monsters uit het anomalie-regime, waardoor het toepasbaar is in scenario's waar traditionele causale discovery of falsificatiemethoden falen.