Resumo Técnico: Aproximação de Modelos Causais Lineares Não-Gaussianos com Ciclos

Declaração do Problema

A descoberta causal a partir de dados observacionais historicamente concentrou-se em Grafos Acíclicos Direcionados (DAGs). No entanto, muitos sistemas científicos, como redes de regulação gênica e sistemas dinâmicos, contêm inerentemente loops de feedback (ciclos direcionados). Embora existam métodos existentes para aprender modelos causais cíclicos, eles frequentemente enfrentam limitações significativas:

1. Ambiguidade de Identificabilidade: No cenário Linear Não-Gaussiano (LiNG), Modelos Causais Estruturais (SCMs) cíclicos são identificáveis apenas até uma classe de equivalência distribucional. Os membros desta classe diferem pela reversão de ciclos direcionados, tornando a estrutura exata do grafo em nível micro não identificável a partir de dados observacionais isolados, sem suposições fortes (por exemplo, estabilidade ou ciclos disjuntos).
2. Complexidade Computacional: Abordagens existentes para aprender resumos de estruturas causais, como o algoritmo GroupLiNGAM, frequentemente sofrem de complexidade de tempo exponencial no número de variáveis.
3. Aplicabilidade: Muitos modelos de alta dimensão com ciclos são excluídos de frameworks padrão de abstração causal porque esses frameworks assumem aciclicidade.

Este artigo aborda o desafio de resumir estruturas causais cíclicas de alta dimensão em representações de baixa dimensão que sejam tanto identificáveis quanto computacionalmente tratáveis, sem exigir as suposições restritivas de ciclos disjuntos ou estabilidade.

Metodologia

Os autores estendem o framework de aproximação causal — que agrupa variáveis em clusters para formar um grafo quociente — a grafos direcionados contendo ciclos.

1. Framework Teórico: O Piso SCC

A principal insight teórica é que qualquer DAG-aproximação válida de um grafo cíclico deve respeitar seus Componentes Fortemente Conectados (SCCs).

• Proposição 1: Nós dentro do mesmo SCC devem ser agrupados no mesmo cluster em qualquer DAG-aproximação. Se fossem divididos, o grafo quociente conteria necessariamente um ciclo, violando o requisito de DAG.
• Piso Estrutural: A partição de variáveis em SCCs forma o "piso estrutural" do reticulado de aproximação. É a DAG-aproximação válida mais fina. O grafo quociente resultante é a condensação ($G_{sc}$) do grafo original, que é um DAG por definição.

2. Identificabilidade via ICA

O artigo aproveita as propriedades de SCMs cíclicos Lineares Não-Gaussianos (LiNG):

• Modelo: $X = BX + \varepsilon$, onde $\varepsilon$ possui componentes mutuamente independentes e não-Gaussianos.
• Equivalência Observacional: Seguindo [19], a matriz de mistura $A = (I-B)^{-1}$ pode ser recuperada via Análise de Componentes Independentes (ICA) até permutação de linhas e escalonamento. Diferentes permutações produzem diferentes membros da classe de equivalência distribucional (diferindo por reversões de ciclos).
• Teorema 1 (Identificabilidade da Condensação): Os autores provam que, embora o grafo em nível micro $G$ seja identificável apenas até a classe de equivalência, a condensação $G_{sc}$ é invariante em todos os membros desta classe.
  • Raciocínio: Reversões de ciclos ocorrem estritamente dentro de SCCs e não alteram a própria partição SCC. Além disso, arestas entre diferentes SCCs (arestas inter-cluster) não podem estar em um ciclo direcionado; assim, reversões de ciclos não podem adicionar, remover ou redirecionar essas arestas. Consequentemente, o DAG em nível de cluster é totalmente identificável a partir de dados observacionais isolados.

3. Algoritmo: Recuperação da Condensação

O procedimento proposto (Algoritmo 1) recupera a condensação em tempo polinomial:

1. Estimação: Aplicar FastICA aos dados observacionais para estimar a matriz de desmistura $\hat{W}$.
2. Permutação: Selecionar uma única permutação de linhas admissível $P$ (por exemplo, via o algoritmo húngaro) tal que a diagonal de $P\hat{W}$ seja não nula.
3. Construção de Candidato: Calcular uma matriz de adjacência candidata $\hat{B} = I - \text{diag}(P\hat{W})^{-1}P\hat{W}$.
4. Limiarização: Aplicar um limiar $\tau$ a $\hat{B}$ para determinar o suporte (arestas).
5. Extração de SCC: Aplicar o algoritmo de Tarjan ao suporte de $\hat{B}$ para identificar SCCs.
6. Construção da Condensação: Formar o grafo quociente onde os nós são os SCCs e as arestas existem se houver qualquer aresta entre os clusters correspondentes em $\hat{B}$.

Complexidade: O algoritmo executa no pior caso em tempo $O(k \cdot n \cdot d^2 + d^3)$, onde $n$ é o tamanho da amostra, $d$ são as variáveis e $k$ são as iterações da ICA. Isso evita a complexidade $O(d!)$ de enumerar todos os membros da classe de equivalência.

Resultados Chave

O artigo fornece garantias teóricas e validação empírica em dados sintéticos:

• Garantias Teóricas:

  • Identificabilidade: A condensação $G_{sc}$ é identificável a partir de dados observacionais sem invocar suposições de estabilidade ou restrições de ciclos disjuntos.
  • Complexidade de Amostra: O artigo deriva limites mostrando que recuperar a condensação verdadeira com probabilidade $1-\delta$ requer um tamanho de amostra $n = \Theta(d / (\beta_{min}^2 \sqrt{\delta}))$, onde $\beta_{min}$ é o peso de aresta não nulo mínimo.
  • Modos de Falha: Os autores caracterizam dois modos de falha da limiarização: (a) dividir um SCC verdadeiro devido a arestas descartadas (refinamento) e (b) fundir SCCs distintos devido a arestas espúrias (aproximação).

• Desempenho Empírico:

  • Consistência: Experimentos em SCMs cíclicos LiNG sintéticos ($d=10$) mostram que o Índice Rand Ajustado (ARI) da partição SCC recuperada e a pontuação F1 do DAG de cluster convergem para 1 à medida que o tamanho da amostra aumenta, independentemente de o sistema estar em um regime estável ($\rho(B) < 1$) ou instável ($\rho(B) > 1$).
  • Escalabilidade: Comparado à linha de base de ciclos disjuntos mais avançada [9], o método proposto escala significativamente melhor. Enquanto o tempo de ajuste da linha de base cresce exponencialmente e o desempenho estagna para $d \ge 50$, o método proposto mantém alta precisão e tempos de ajuste abaixo de 10 segundos mesmo para $d=100$.
  • Robustez: O método recupera com sucesso a estrutura em nível de cluster mesmo quando a estrutura em nível de variável não é identificável (por exemplo, no regime instável onde o filtro "primeiro-estável" falha em recuperar o verdadeiro $B$).

Significado e Alegações

O artigo afirma preencher a lacuna entre modelagem causal cíclica e abstração causal:

1. Resolução de Ambiguidade: Fornece um representante natural para a classe de equivalência distribucional de modelos LiNG cíclicos. Embora o micro-grafo exato seja ambíguo, a condensação é um objeto único e identificável que captura o fluxo causal entre clusters de variáveis.
2. Habilitação de Inferência Causal a Montante: Ao identificar $G_{sc}$ a partir de dados observacionais, o artigo fornece o pré-requisito necessário para aplicar teoremas de identificação de C-DAG (Cluster DAG) (de [2]). Isso permite que pesquisadores realizem identificação de efeitos causais em nível de cluster em sistemas cíclicos usando maquinaria acíclica padrão, uma tarefa anteriormente limitada a sistemas acíclicos ou exigindo dados intervencionais.
3. Eficiência Computacional: A abordagem oferece uma alternativa de tempo polinomial a métodos de tempo exponencial para aprender resumos causais, tornando-a aplicável a problemas de dimensão mais elevada.
4. Suposições Relaxadas: Ao contrário de trabalhos anteriores que exigiam ciclos disjuntos ou assimetria específica de ruído, esta abordagem depende apenas de não-Gaussianidade geral e ICA padrão, aplicável a ciclos sobrepostos.

Os autores notam limitações, especificamente que o método assume a ausência de confundidores latentes (ou requer extensões de ICA supercompletas) e que no máximo um componente de ruído pode ser Gaussiano para evitar ambiguidade rotacional que fundiria SCCs distintos. Eles posicionam o trabalho como um passo fundamental em direção à descoberta causal prática em sistemas complexos e cíclicos.