Nonlinear Causal Discovery through a Sequential Edge Orientation Approach

Resumo Técnico: Descoberta Causal por Orientação Sequencial de Arestas

1. Problema e Motivação

A descoberta causal visa inferir a estrutura de um Grafo Acíclico Direcionado (DAG) a partir de dados observacionais. Embora métodos existentes possam identificar a classe de equivalência de Markov (representada por um CPDAG - Completed Partially Directed Acyclic Graph), determinar a direção exata das arestas não direcionadas em cenários não lineares permanece um desafio.

Os métodos atuais enfrentam várias limitações:

• Suposições restritivas: Muitos assumem linearidade ou ruído gaussiano, o que não reflete a complexidade de dados reais.
• Custo Computacional: Métodos baseados em testes de independência condicional (como testes baseados em kernels) têm complexidade quadrática ou cúbica em relação ao tamanho da amostra, tornando-os inviáveis para grandes grafos.
• Dependência de Modelos: Abordagens baseadas em pontuação (score-based) frequentemente dependem de otimização global intensiva e podem falhar em encontrar o ótimo global ou serem sensíveis à padronização dos dados.
• Ineficiência em Orientação: Métodos que tentam inferir a ordem topológica global muitas vezes falham em identificar a direção correta de arestas específicas sem reavaliar todo o grafo.

O objetivo deste trabalho é desenvolver um método eficiente, robusto e consistente para orientar arestas não direcionadas em um CPDAG, recuperando o DAG causal verdadeiro sob modelos de ruído aditivo não lineares.

2. Metodologia Proposta: SNOE

Os autores propõem o algoritmo SNOE (Sequential Nonlinear Orientation of Edges), que opera em duas etapas principais: aprendizado inicial da estrutura e orientação sequencial das arestas.

A. Modelo de Ruído Aditivo Par (PANM)
O cerne da metodologia é o Modelo de Ruído Aditivo Par (Pairwise Additive Noise Model - PANM). Diferente de verificar a independência global, o PANM foca em pares de nós conectados por uma aresta não direcionada ($X - Y$) e seus pais identificados no grafo parcial ($PA_X, PA_Y$).

• Se a relação causal for $X \to Y$, o modelo assume $Y = f(X, PA_Y) + \epsilon_Y$, onde $\epsilon_Y$ é independente de $\{X, PA_Y\}$.
• O algoritmo verifica se a independência entre o resíduo e os pais/variáveis causais se mantém apenas sob a direção correta.

B. Procedimento de Orientação Sequencial
Ao invés de tentar ordenar todos os nós de uma vez, o SNOE orienta arestas sequencialmente:

1. Classificação (Ranking) de Arestas: As arestas não direcionadas são classificadas com base em uma medida de dependência (Informação Mútua Normalizada) entre os resíduos e as variáveis parentais. Arestas que satisfazem o critério PANM (onde a dependência é zero ou mínima) são priorizadas.
2. Teste de Razão de Verossimilhança (Likelihood Ratio Test): Para a aresta selecionada, o algoritmo compara dois modelos condicionais:
   • $H_f$: $X \to Y$ (Modelo $F$)
   • $H_g$: $Y \to X$ (Modelo $G$)
     O teste utiliza uma divisão de amostra (train-test split) para estimar os parâmetros e calcular a estatística de razão de verossimilhança. Isso evita viés de sobreajuste e permite derivar uma distribuição assintótica (Normal) para o teste, fornecendo uma decisão estatística definitiva sobre a direção.
3. Aplicação de Regras de Meek: Após orientar uma aresta, o algoritmo aplica as regras de Meek e identifica filhos comuns para orientar novas arestas, criando um efeito cascata que reduz o número de arestas a serem testadas.

C. Fluxo do Algoritmo (SNOE)

1. Aprendizado Inicial: Usa uma versão modificada do algoritmo PC para aprender um CPDAG inicial e um conjunto de arestas candidatas (usando níveis de significância diferentes para evitar a remoção prematura de arestas verdadeiras).
2. Orientação: Aplica o procedimento de classificação e teste de razão de verossimilhança iterativamente até que todas as arestas sejam orientadas ou não haja mais arestas que satisfaçam o PANM.
3. Poda (Pruning): Remove arestas espúrias através de testes de significância em modelos de Regressão Aditiva Generalizada (GAM).

3. Contribuições Principais

• Critério PANM: Uma nova condição derivada do modelo de ruído aditivo que garante a identificabilidade da direção de uma aresta localmente, sem necessidade de conhecer a ordem topológica global.
• Algoritmo Sequencial com Consistência: Prova teórica de que, no limite de grandes amostras, o algoritmo recupera o DAG verdadeiro a partir do CPDAG, desde que o modelo de ruído aditivo restrito seja válido.
• Teste de Razão de Verossimilhança Robusto: Desenvolvimento de um teste estatístico que compara diretamente a verossimilhança de direções opostas, superando a ambiguidade de testes de independência separados e sendo computacionalmente mais eficiente que testes baseados em kernels.
• Eficiência Computacional: O método evita a otimização global sobre todo o espaço de grafos, focando em subgrafos locais, resultando em tempos de execução significativamente menores.

4. Resultados Experimentais

Os autores realizaram extensas simulações e aplicações em dados reais:

• Desempenho em Dados Sintéticos:

  • O SNOE superou consistentemente métodos concorrentes (CAM, NOTEARS, DAGMA, SCORE) em termos de pontuação F1 e Distância Hamming Estrutural (SHD).
  • Foi particularmente eficaz em DAGs não lineares com funções invertíveis, um cenário onde outros métodos falham frequentemente.
  • Demonstrou robustez contra má especificação do modelo (ex: ruído não gaussiano, funções não puramente aditivas).
  • Velocidade: O SNOE foi até 10 vezes mais rápido que os concorrentes em redes maiores, devido à sua abordagem local e evitação de otimização global.

• Aplicações em Dados Reais:

  • Dados de Citometria de Fluxo (Rede Sachs): O SNOE alcançou a maior pontuação F1 (>0.50), superando todos os outros métodos, com menos falsos positivos e uma estrutura mais próxima da verdade.
  • Pares Causa-Efeito (Tübingen): No conjunto de dados de pares causa-efeito, a versão com validação cruzada (SNOE-CV) alcançou 66,3% de precisão global, superando a maioria dos métodos baseados em entropia existentes.

5. Significado e Impacto

Este trabalho representa um avanço significativo na descoberta causal não linear ao:

1. Resolver o Problema de Escalabilidade: Oferece uma alternativa viável a métodos baseados em kernels, que se tornam proibitivos em grandes conjuntos de dados.
2. Ponte entre Teoria e Prática: Conecta a teoria de identificabilidade (ANM) a um algoritmo prático que não requer conhecimento de domínio profundo para seleção de modelos complexos.
3. Robustez: Demonstra que a descoberta causal pode ser realizada com alta precisão mesmo quando os dados não seguem distribuições estritamente gaussianas ou funções lineares, que são as suposições padrão em muitas ferramentas industriais.

Em suma, o SNOE estabelece um novo padrão para a descoberta de DAGs não lineares, combinando rigor teórico, eficiência computacional e robustez empírica.