Resumo Técnico: Falsificação de Grafos Causais com Eventos Atípicos (Outliers)

Declaração do Problema

As verdadeiras relações causais raramente são conhecidas a priori, e inferir grafos causais a partir de dados continua sendo uma tarefa desafiadora. Uma dificuldade fundamental reside em avaliar a validade de um determinado grafo causal candidato na ausência de uma verdade fundamental (ground truth). Embora métodos anteriores tenham utilizado dados intervencionais ou verificações de consistência entre subconjuntos de variáveis, estes frequentemente exigem múltiplas amostras, acesso a oráculos de independência condicional ou assumem formas paramétricas específicas. Em cenários práticos, como monitoramento de nuvem ou manufatura, pode ser proibitivamente caro ou impossível reunir múltiplas amostras de eventos anômalos raros. Além disso, os métodos existentes para falsificar modelos causais usando dados observacionais carecem de testes estatísticos válidos com taxas de falsos positivos controladas.

Este trabalho aborda o problema de falsificar um grafo causal candidato utilizando uma única amostra atípica (outlier). O objetivo é testar a hipótese nula $H_0: \hat{G} = G$, onde $\hat{G}$ é um grafo causal estimado e $G$ é o verdadeiro grafo causal, aproveitando as características de propagação de eventos atípicos.

Metodologia

A abordagem proposta fundamenta-se no princípio de que outliers fracos raramente causam outliers fortes. Este princípio, anteriormente utilizado na análise de causa raiz para identificar causas sem conhecimento prévio do grafo, é invertido aqui para falsificar grafos: se um grafo candidato implica um padrão de propagação de outliers inconsistente com este princípio, o grafo é rejeitado.

Conceitos Centrais

1. Modelagem de Outliers: Os outliers são modelados como o resultado de uma "intervenção suave" (soft-intervention) em um subconjunto de variáveis de causa raiz $R$. A distribuição de uma amostra atípica é uma versão "corrompida" da distribuição verdadeira, onde os mecanismos para as variáveis em $R$ são alterados.
2. Scores de Outlier de Teoria da Informação (IT): O método utiliza scores de outlier IT definidos como $S(x) = -\log P(\text{evento})$.
   • Scores Marginais: $S(x_i) = -\log P(\tau_i(X_i) \geq \tau_i(x_i))$.
   • Scores Condicionais: $S(x_i | pa_i) = -\log P(\tau_i(X_i) \geq \tau_i(x_i) | PA_i = pa_i)$.
     Sob a hipótese nula de que o grafo está correto e a amostra é extraída do mecanismo ordinário (excluindo as causas raiz), esses scores seguem uma distribuição exponencial padrão independente, $\text{Exp}(1)$.

Testes Estatísticos

Os autores propõem quatro testes estatísticos baseados nesses scores para rejeitar $H_0$. Os testes são projetados para ter controle de falsos positivos (p-valores válidos) e garantias de poder contra classes específicas de grafos incorretos.

1. Testes de Score Condicional (Assumindo Causas Raiz Conhecidas)

Quando as causas raiz $R$ são conhecidas e o grafo é um Grafo Acíclico Dirigido (DAG), os scores condicionais das variáveis não-raiz são variáveis independentes $\text{Exp}(1)$ sob $H_0$. O artigo propõe:

• Teste baseado em Fisher: Soma os scores condicionais ($S_{sum}$). O p-valor é derivado da distribuição de Erlang (soma de exponenciais).
• Teste baseado em Tippett: Utiliza o valor máximo do score condicional ($S_{max}$). O p-valor é derivado da distribuição do máximo de exponenciais.
• Teste Binomial: Conta o número de scores que excedem um limiar $t$ ($N_t$). O p-valor segue uma distribuição Binomial.
• Teste Kolmogorov-Smirnov (KS): Compara a CDF empírica dos scores contra a CDF teórica $\text{Exp}(1)$ ($D_L$).

2. Testes de Score Marginal (Assunção de Polytree)

Inferir distribuições condicionais é estatisticamente mal posto com dados limitados. Os autores adaptam os três primeiros testes para usar apenas scores marginais, desde que o grafo verdadeiro seja um polytree (um DAG sem ciclos não direcionados).

• Tipicidade de Score: O método baseia-se na condição $S(y|x) \geq |S(y) - S(x)|_+$. Quando satisfeita, implica que um outlier fraco raramente causa um forte.
• Estatísticas de Teste: Os testes marginais utilizam o "salto" (jump) nos scores: $|S(x_i) - S(PA_i)|_+$.
• Validade: Sob a assunção de polytree e tipicidade de score, estas estatísticas marginais são estocasticamente dominadas por suas contrapartes condicionais, garantindo p-valores válidos.

3. Causas Raiz Desconhecidas

Se as causas raiz forem desconhecidas, mas um limite superior $k$ sobre o seu número for conhecido, os autores propõem um procedimento de máximo leave-$k$-out. A estatística de teste é computada para cada subconjunto de $k$ variáveis tratadas como potenciais causas raiz, e o valor máximo de p-valor é tomado. Isso controla a taxa de falsos positivos sem introduzir viés de seleção.

Garantias Teóricas

• Controle de Falsos Positivos: Os testes fornecem p-valores rigorosos, garantindo que $P(\text{rejeitar } H_0 | H_0 \text{ é verdadeira}) \leq \alpha$.
• Garantias de Poder: O artigo deriva limites inferiores para a taxa de decaimento dos scores de outliers ao longo dos caminhos causais usando a Desigualdade de Processamento de Dados Forte (SDPI).
  • Se um descendente verdadeiro de uma causa raiz recebe pais incorretos (por exemplo, não-descendentes ou pais mais distantes da raiz), o resultante "salto de score" é limitado inferiormente.
  • O poder dos testes aumenta com a força do outlier ($\lambda$) e com a proporção de arestas incorretas ($\pi$).
  • Resultados específicos de otimalidade (Uniformemente Mais Poderosos) são mostrados para o teste de soma (Fisher) contra mudanças globais nos parâmetros de taxa e o teste de máximo (Tippett) contra outliers dominantes únicos.

Resultados Experimentais

Os autores avaliaram seus métodos em conjuntos de dados sintéticos e do mundo real, comparando-os com baselines que incluem um teste baseado em permutação (Eulig et al., 2025) e um algoritmo de descoberta causal (GRaSP).

Dados Sintéticos

• Configuração: DAGs aleatórios com 20 nós. Outliers foram injetados em uma causa raiz aleatória e propagados. O "ground truth" foi parcialmente corrompido para criar grafos de teste com frações variadas de arestas corretas ($|K|/|N|$).
• Descobertas:
  • Os testes propostos mostraram taxas de rejeição crescentes conforme a fração de arestas incorretas aumentava.
  • Testes de score condicional geralmente superaram os testes de score marginal, como esperado.
  • O baseline GRaSP foi excessivamente sensível, rejeitando quase todos os grafos (incluindo o ground truth) devido a discrepâncias de amostra finita.
  • O baseline de permutação comportou-se como esperado, rejeitando grafos apenas quando eram piores que o acaso.
  • O poder aumentou com a força dos anomalias injetadas e quando múltiplas amostras de outliers estavam disponíveis.

Dados do Mundo Real

1. Dataset PetShop (Computação em Nuvem): O estudo testou um "mapa de dependência de serviço" (com arestas invertidas) como um proxy para o grafo causal.
   • Resultado: Os testes propostos rejeitaram este grafo a uma taxa significativamente maior que o nível de significância, particularmente em cenários de alto tráfego. Isso sugere que o mapa de serviço, embora melhor que o acaso, não é o verdadeiro grafo causal.
2. Dataset Causal Chambers: Um banco de testes físico com uma estrutura causal conhecida e precisa.
   • Resultado: Os testes rejeitaram o grafo a uma taxa consistente com o nível de significância (ou seja, não rejeitaram falsamente o grafo correto), validando o controle de falsos positivos.

Significância e Alegações

O artigo afirma apresentar os primeiros testes estatísticos para a hipótese nula de que um determinado grafo causal é o grafo verdadeiro que satisfazem três critérios específicos:

1. Controle de Falsos Positivos: Fornecem p-valores válidos, garantindo que a taxa de falsas rejeições seja limitada.
2. Garantias de Poder: Possuem poder provado contra uma ampla classe de grafos causais incorretos, especificamente onde a propagação de outliers viola o princípio "fraco-para-forte".
3. Operação com Amostra Única: Podem operar efetivamente com apenas uma única amostra de outlier, uma característica crítica para domínios onde eventos anômalos são raros e caros.

Os autores enfatizam que este trabalho preenche a lacuna entre a literatura de análise de causa raiz e a avaliação de grafos causais, transformando o princípio da propagação de outliers em uma ferramenta rigorosa de falsificação. O método não requer dados intervencionais ou múltiplas amostras do regime anômalo, tornando-o aplicável a cenários onde os métodos tradicionais de descoberta ou falsificação causal falham.