Résumé Technique : Coarsement de Modèles Causaux Linéaires Non-Gaussiens avec Cycles

Énoncé du Problème

La découverte causale à partir de données observationnelles s'est historiquement concentrée sur les Graphes Acycliques Dirigés (DAG). Cependant, de nombreux systèmes scientifiques, tels que les réseaux de régulation génique et les systèmes dynamiques, contiennent intrinsèquement des boucles de rétroaction (cycles dirigés). Bien que des méthodes existantes permettent d'apprendre des modèles causaux cycliques, elles rencontrent souvent des limitations significatives :

1. Ambiguïté d'Identifiabilité : Dans le cadre Linéaire Non-Gaussien (LiNG), les Modèles Causaux Structurels (SCM) cycliques sont identifiables uniquement jusqu'à une classe d'équivalence distributionnelle. Les membres de cette classe diffèrent par l'inversion de cycles dirigés, rendant la structure exacte du graphe microscopique non identifiable à partir de données observationnelles seules, sans hypothèses fortes (par exemple, stabilité ou cycles disjoints).
2. Complexité Computationsnelle : Les approches existantes pour apprendre des résumés de structures causales, telles que l'algorithme GroupLiNGAM, souffrent souvent d'une complexité temporelle exponentielle en fonction du nombre de variables.
3. Applicabilité : De nombreux modèles de haute dimension avec cycles sont exclus des cadres standards d'abstraction causale car ces cadres supposent l'acyclicité.

Ce papier aborde le défi de résumer des structures causales cycliques de haute dimension en représentations de basse dimension qui sont à la fois identifiables et calculables, sans nécessiter les hypothèses restrictives de cycles disjoints ou de stabilité.

Méthodologie

Les auteurs étendent le cadre du coarsement causal—qui regroupe des variables en clusters pour former un graphe quotient—aux graphes dirigés contenant des cycles.

1. Cadre Théorique : Le Sol des Composantes Fortement Connexes (CFC)

L'idée théorique centrale est que tout coarsement DAG valide d'un graphe cyclique doit respecter ses Composantes Fortement Connexes (CFC).

• Proposition 1 : Les nœuds au sein d'une même CFC doivent être regroupés dans le même cluster dans tout coarsement DAG. S'ils étaient séparés, le graphe quotient contiendrait nécessairement un cycle, violant ainsi l'exigence DAG.
• Sol Structurel : La partition des variables en CFC forme le « sol structurel » du treillis de coarsement. C'est le plus fin des coarsements DAG valides. Le graphe quotient résultant est la condensation ($G_{sc}$) du graphe original, qui est un DAG par définition.

2. Identifiabilité via l'ICA

Le papier exploite les propriétés des SCM cycliques Linéaires Non-Gaussiens (LiNG) :

• Modèle : $X = BX + \varepsilon$, où $\varepsilon$ possède des composantes mutuellement indépendantes et non gaussiennes.
• Équivalence Observationnelle : Suivant [19], la matrice de mélange $A = (I-B)^{-1}$ peut être récupérée via l'Analyse en Composantes Indépendantes (ICA) à une permutation de lignes et un étirement près. Différentes permutations produisent différents membres de la classe d'équivalence distributionnelle (différant par des inversions de cycles).
• Théorème 1 (Identifiabilité de la Condensation) : Les auteurs prouvent que si le graphe microscopique $G$ n'est identifiable qu'à la classe d'équivalence près, la condensation $G_{sc}$ est invariante à travers tous les membres de cette classe.
  • Raisonnement : Les inversions de cycles se produisent strictement au sein des CFC et n'altèrent pas la partition des CFC elle-même. De plus, les arêtes entre différentes CFC (arêtes inter-cluster) ne peuvent pas se trouver sur un cycle dirigé ; ainsi, les inversions de cycles ne peuvent ni ajouter, ni supprimer, ni rediriger ces arêtes. Par conséquent, le DAG au niveau des clusters est entièrement identifiable à partir de données observationnelles seules.

3. Algorithme : Récupération de la Condensation

La procédure proposée (Algorithme 1) récupère la condensation en temps polynomial :

1. Estimation : Appliquer FastICA aux données observationnelles pour estimer la matrice de démélange $\hat{W}$.
2. Permutation : Sélectionner une seule permutation de lignes admissible $P$ (par exemple, via l'algorithme hongrois) telle que la diagonale de $P\hat{W}$ soit non nulle.
3. Construction de Candidat : Calculer une matrice d'adjacence candidate $\hat{B} = I - \text{diag}(P\hat{W})^{-1}P\hat{W}$.
4. Seuillage : Appliquer un seuil $\tau$ à $\hat{B}$ pour déterminer le support (les arêtes).
5. Extraction des CFC : Appliquer l'algorithme de Tarjan au support de $\hat{B}$ pour identifier les CFC.
6. Construction de la Condensation : Former le graphe quotient où les nœuds sont les CFC et où des arêtes existent s'il y a une arête quelconque entre les clusters correspondants dans $\hat{B}$.

Complexité : L'algorithme s'exécute dans le pire des cas en $O(k \cdot n \cdot d^2 + d^3)$, où $n$ est la taille de l'échantillon, $d$ le nombre de variables, et $k$ le nombre d'itérations ICA. Cela évite la complexité $O(d!)$ de l'énumération de tous les membres de la classe d'équivalence.

Résultats Clés

Le papier fournit des garanties théoriques et une validation empirique sur des données synthétiques :

• Garanties Théoriques :

  • Identifiabilité : La condensation $G_{sc}$ est identifiable à partir de données observationnelles sans invoquer d'hypothèses de stabilité ni de contraintes de cycles disjoints.
  • Complexité Échantillonnale : Le papier dérive des bornes montrant que la récupération de la vraie condensation avec une probabilité $1-\delta$ nécessite une taille d'échantillon $n = \Theta(d / (\beta_{min}^2 \sqrt{\delta}))$, où $\beta_{min}$ est le poids d'arête non nul minimum.
  • Modes d'Échec : Les auteurs caractérisent deux modes d'échec du seuillage : (a) la division d'une vraie CFC due à des arêtes omises (raffinement), et (b) la fusion de CFC distinctes due à des arêtes spurieuses (coarsement).

• Performance Empirique :

  • Cohérence : Les expériences sur des SCM cycliques LiNG synthétiques ($d=10$) montrent que l'Indice Rand Ajusté (ARI) de la partition de CFC récupérée et le score F1 du DAG de clusters convergent vers 1 à mesure que la taille de l'échantillon augmente, indépendamment du fait que le système soit dans un régime stable ($\rho(B) < 1$) ou instable ($\rho(B) > 1$).
  • Évolutivité : Comparé à la référence de l'état de l'art sur les cycles disjoints [9], la méthode proposée s'adapte beaucoup mieux. Alors que le temps d'ajustement de la référence croît de manière exponentielle et que les performances plafonnent pour $d \ge 50$, la méthode proposée maintient une haute précision et des temps d'ajustement inférieurs à 10 secondes, même pour $d=100$.
  • Robustesse : La méthode récupère avec succès la structure au niveau des clusters même lorsque la structure au niveau des variables est non identifiable (par exemple, dans le régime instable où le filtre « premier-stable » échoue à récupérer le vrai $B$).

Importance et Revendications

Le papier prétend combler le fossé entre la modélisation causale cyclique et l'abstraction causale :

1. Résolution de l'Ambiguïté : Il fournit un représentant naturel pour la classe d'équivalence distributionnelle des modèles LiNG cycliques. Si le graphe microscopique exact est ambigu, la condensation est un objet unique et identifiable qui capture le flux causal entre les clusters de variables.
2. Permettre l'Inférence Causale en Aval : En identifiant $G_{sc}$ à partir de données observationnelles, le papier fournit le prérequis nécessaire pour appliquer les théorèmes d'identification des C-DAG (DAG de clusters) (de [2]). Cela permet aux chercheurs de réaliser l'identification des effets causaux au niveau des clusters dans des systèmes cycliques en utilisant des mécanismes acycliques standards, une tâche précédemment limitée aux systèmes acycliques ou nécessitant des données d'intervention.
3. Efficacité Computationsnelle : L'approche offre une alternative en temps polynomial aux méthodes en temps exponentiel pour apprendre des résumés causaux, la rendant applicable à des problèmes de plus haute dimension.
4. Hypothèses Assouplies : Contrairement aux travaux précédents exigeant des cycles disjoints ou des skewness de bruit spécifiques, cette approche repose uniquement sur la non-gaussianité générale et l'ICA standard, applicable aux cycles chevauchants.

Les auteurs notent des limitations, spécifiquement que la méthode suppose l'absence de confondants latents (ou nécessite des extensions ICA sur-complètes) et qu'au plus une composante de bruit peut être gaussienne pour éviter qu'une ambiguïté rotationnelle ne fusionne des CFC distinctes. Ils positionnent ce travail comme une étape fondamentale vers la découverte causale pratique dans des systèmes complexes et cycliques.