Résumé Technique : Falsification de Graphes Causaux avec des Événements Aberrants

Énoncé du Problème

Les relations causales réelles sont rarement connues a priori, et l'inférence de graphes causaux à partir de données demeure une tâche complexe. Une difficulté fondamentale réside dans l'évaluation de la validité d'un graphe causal candidat en l'absence de vérité terrain. Bien que des méthodes précédentes aient utilisé des données interventionnelles ou des vérifications de cohérence sur des sous-ensembles de variables, celles-ci nécessitent souvent de multiples échantillons, l'accès à des oracles d'indépendance conditionnelle, ou supposent des formes paramétriques spécifiques. Dans des contextions pratiques telles que la surveillance du cloud ou la fabrication, il est souvent prohibitif ou impossible de collecter de multiples échantillons d'événements anormaux rares. De plus, les méthodes existantes pour falsifier les modèles causaux à l'aide de données observationnelles manquent souvent de tests statistiques valides avec des taux de faux positifs contrôlés.

Ce travail aborde le problème de la falsification d'un graphe causal candidat en utilisant un échantillon aberrant unique. L'objectif est de tester l'hypothèse nulle $H_0: \hat{G} = G$, où $\hat{G}$ est un graphe causal estimé et $G$ est le véritable graphe causal, en exploitant les caractéristiques de propagation des événements aberrants.

Méthodologie

L'approche proposée est fondée sur le principe selon lequel les outliers faibles causent rarement des outliers forts. Ce principe, précédemment utilisé dans l'analyse des causes racines pour identifier les causes sans connaissance préalable du graphe, est ici inversé pour falsifier les graphes : si un graphe candidat implique un motif de propagation d'anomalies incompatible avec ce principe, le graphe est rejeté.

Concepts Fondamentaux

1. Modélisation des Outliers : Les outliers sont modélisés comme le résultat d'une « intervention douce » sur un sous-ensemble de variables causes racines $R$. La distribution d'un échantillon aberrant est une version « corrompue » de la distribution réelle où les mécanismes pour les variables dans $R$ sont altérés.
2. Scores d'Outliers Information-Théoriques (IT) : La méthode utilise des scores d'outliers IT définis par $S(x) = -\log P(\text{événement})$.
   • Scores Marginaux : $S(x_i) = -\log P(\tau_i(X_i) \geq \tau_i(x_i))$.
   • Scores Conditionnels : $S(x_i | pa_i) = -\log P(\tau_i(X_i) \geq \tau_i(x_i) | PA_i = pa_i)$.
     Sous l'hypothèse nulle que le graphe est correct et que l'échantillon est tiré du mécanisme ordinaire (en excluant les causes racines), ces scores suivent une distribution exponentielle standard indépendante, $\text{Exp}(1)$.

Tests Statistiques

Les auteurs proposent quatre tests statistiques basés sur ces scores pour rejeter $H_0$. Les tests sont conçus pour avoir un contrôle des faux positifs (p-valeurs valides) et des garanties de puissance contre des classes spécifiques de graphes incorrects.

1. Tests de Scores Conditionnels (En supposant les causes racines connues)

Lorsque les causes racines $R$ sont connues et que le graphe est un DAG (Graphe Acyclique Dirigé), les scores conditionnels des variables non-racines sont des variables $\text{Exp}(1)$ indépendantes sous $H_0$. Le papier propose :

• Test basé sur Fisher : Somme les scores conditionnels ($S_{sum}$). La p-valeur est dérivée de la distribution d'Erlang (somme d'exponentielles).
• Test basé sur Tippett : Utilise le score conditionnel maximum ($S_{max}$). La p-valeur est dérivée de la distribution du maximum d'exponentielles.
• Test Binomial : Compte le nombre de scores dépassant un seuil $t$ ($N_t$). La p-valeur suit une distribution binomiale.
• Test de Kolmogorov-Smirnov (KS) : Compare la fonction de répartition empirique des scores contre la fonction de répartition théorique de $\text{Exp}(1)$ ($D_L$).

2. Tests de Scores Marginaux (Hypothèse de Polytree)

L'inférence des distributions conditionnelles est statistiquement mal posée avec des données limitées. Les auteurs adaptent les trois premiers tests pour utiliser uniquement des scores marginaux, à condition que le vrai graphe soit un polytree (un DAG sans cycles non orientés).

• Typicité des Scores : La méthode repose sur la condition $S(y|x) \geq |S(y) - S(x)|_+$. Lorsqu'elle est satisfaite, elle implique qu'un outlier faible cause rarement un outlier fort.
• Statistiques de Test : Les tests marginaux utilisent le « saut » des scores : $|S(x_i) - S(PA_i)|_+$.
• Validité : Sous l'hypothèse du polytree et la typicité des scores, ces statistiques marginales sont stochastiquement dominées par leurs homologues conditionnels, garantissant des p-valeurs valides.

3. Causes Racines Inconnues

Si les causes racines sont inconnues mais qu'une borne supérieure $k$ sur leur nombre est connue, les auteurs proposent une procédure de maximum leave-$k$-out. La statistique de test est calculée pour chaque sous-ensemble de $k$ variables traitées comme des causes racines potentielles, et le p-valeur maximum est pris. Cela contrôle le taux de faux positifs sans introduire de biais de sélection.

Garanties Théoriques

• Contrôle des Faux Positifs : Les tests fournissent des p-valeurs rigoureuses, garantissant que $P(\text{rejeter } H_0 | H_0 \text{ est vraie}) \leq \alpha$.
• Garanties de Puissance : Le papier dérive des bornes inférieures sur le taux de décroissance des scores d'outliers le long des chemins causaux en utilisant la Forte Inégalité de Traitement des Données (SDPI).
  • Si un descendant réel d'une cause racine se voit attribuer des parents incorrects (par exemple, des non-descendants ou des parents plus éloignés de la racine), le « saut de score » résultant est inférieur à une certaine borne.
  • La puissance des tests augmente avec la force de l'anomalie injectée ($\lambda$) et la proportion d'arêtes incorrectes ($\pi$).
  • Des résultats d'optimalité spécifiques (Uniformément Plus Puissants) sont démontrés pour le test de somme (Fisher) contre les décalages globaux des paramètres de taux et le test de max (Tippett) contre les outliers dominants uniques.

Résultats Expérimentaux

Les auteurs ont évalué leurs méthodes sur des ensembles de données synthétiques et réels, comparant leurs performances aux bases de référence incluant un test par permutation (Eulig et al., 2025) et un algorithme de découverte causale (GRaSP).

Données Synthétiques

• Configuration : DAGs aléatoires avec 20 nœuds. Des outliers ont été injectés dans une cause racine aléatoire et propagés. Le « véritable graphe » a été partiellement corrompu pour créer des graphes de test avec des fractions variables d'arêtes correctes ($|K|/|N|$).
• Constats :
  • Les tests proposés ont montré des taux de rejet croissants à mesure que la fraction d'arêtes incorrectes augmentait.
  • Les tests de scores conditionnels sont généralement plus performants que les tests de scores marginaux, comme prévu.
  • La base de référence GRaSP est excessivement sensible, rejetant presque tous les graphes (y compris le vrai graphe) en raison des écarts d'échantillonnage fini.
  • La base de référence par permutation se comporte comme attendu, ne rejetant les graphes que lorsqu'ils sont moins bons que l'aléatoire.
  • La puissance augmente avec des anomalies injectées plus fortes et lorsque plusieurs échantillons d'outliers sont disponibles.

Données du Monde Réel

1. Jeu de données PetShop (Cloud Computing) : L'étude a testé une « carte de dépendance de service » (avec des arêtes inversées) comme proxy du graphe causal.
   • Résultat : Les tests proposés ont rejeté ce graphe à un taux significativement plus élevé que le niveau de signification, particulièrement dans les scénés à fort trafic. Cela suggère que la carte de service, bien que meilleure que l'aléatoire, n'est pas le véritable graphe causal.
2. Jeu de données Causal Chambers : Un banc d'essai physique avec une structure causale connue et précise.
   • Résultat : Les tests ont rejeté le graphe à un taux cohérent avec le niveau de signification (c'est-à-dire qu'ils n'ont pas rejeté à tort le graphe correct), validant ainsi le contrôle des faux positifs.

Signification et Revendications

Le papier affirme présenter les premiers tests statistiques pour l'hypothèse nulle selon laquelle un graphe causal donné est le véritable graphe causal, satisfaisant trois critères spécifiques :

1. Contrôle des Faux Positifs : Ils fournissent des p-valeurs valides, assurant que le taux de faux rejets est borné.
2. Garanties de Puissance : Ils ont une puissance prouvée contre une large classe de graphes causaux incorrects, spécifiquement là où la propagation des outliers viole le principe « faible-vers-fort ».
3. Fonctionnement sur Échantillon Unique : Ils peuvent opérer efficacement avec un seul échantillon d'outlier, une caractéristique critique pour les domaines où les événements anormaux sont rares et coûteux.

Les auteurs soulignent que ce travail comble le fossé entre la littérature sur l'analyse des causes racines et l'évaluation des graphes causaux, transformant le principe de propagation des outliers en un outil de falsification rigoureux. La méthode ne nécessite ni données interventionnelles ni multiples échantillons de la régime anormal, ce qui la rend applicable à des scénarios où les méthodes traditionnelles de découverte ou de falsification causale échouent.