Estimate Collapsibility of Causal Effects in Completed Partial DAGs via Strong d-Convex Hulls

Resumo Técnico: Estimativa da Colapsabilidade de Efeitos Causais em CPDAGs Completos via Cascos d-Convexos Fortes

Definição do Problema
A estimativa de efeitos causais a partir de dados observacionais depende tipicamente de modelos gráficos causais. Embora o critério de back-door e o cálculo do-calculus permitam a estimativa precisa em Grafos Acíclicos Dirigidos (DAGs), a descoberta causal a partir de dados frequentemente resulta apenas em uma classe de equivalência de Markov de DAGs, representada por um Grafo Parcialmente Dirigido Acíclico Completado (CPDAG). Estimar efeitos causais em CPDAGs, como via o algoritmo IDA (Cálculo de Intervenção quando o DAG está Ausente), requer a enumeração de possíveis conjuntos de pais ou conjuntos de ajuste válidos em todos os DAGs consistentes. Este processo torna-se computacionalmente proibitivo em cenários de alta dimensionalidade. Além disso, métodos existentes para redução de conjuntos de ajuste dependem frequentemente de poda local ou conhecimento prévio adicional, deixando variáveis redundantes no grafo que deveriam ser removidas para simplificar o modelo. Um desafio crítico é identificar um subconjunto mínimo de variáveis que preserve as estimativas de efeito causal após a marginalização sobre variáveis irrelevantes, uma propriedade conhecida como colapsabilidade. Embora a colapsabilidade tenha sido estudada em grafos não direcionados e para propriedades distributivas, sua aplicação para a estimativa de efeito causal em CPDAGs permanece pouco explorada.

Metodologia
O artigo propõe um framework para estimar efeitos causais em CPDAGs através da identificação de "conjuntos colapsáveis mínimos" por meio de um novo conceito teórico-gráfico: o Casco d-Convexo Forte.

1. Estimativa da Colapsabilidade em CBNs: Os autores definem colapsabilidade de estimativa para Redes Bayesianas Causais (CBNs). Um conjunto $R$ é colapsável de estimativa se as Estimativas de Máxima Verossimilhança (MLEs) da distribuição marginal sobre $R$ permanecerem consistentes, quer sejam computadas no grafo completo ou no subgrafo induzido.
2. Cascos d-Convexos Fortes: Para caracterizar conjuntos colapsáveis mínimos, o artigo introduz o Casco d-Convexo Forte. Um subconjunto $R$ é fortemente d-convexo se:
   • Não houver caminhos indutores para $R$ dentro do subgrafo induzido.
   • O conjunto de filhos do complemento de $R$ que também são ancestrais de $R$ for linearmente ordenado em relação a $R$.
     O artigo prova (Teorema 1) que um conjunto é um conjunto colapsável mínimo se, e somente se, for o casco d-convexo forte das variáveis alvo.
3. Algoritmos (ISCHA): Os autores desenvolvem o Algoritmo de Identificação de Casco d-Convexo Forte (ISCHA). Este algoritmo opera em duas fases:
   • Primeiro, computa o casco d-convexo absorvendo iterativamente vértices em caminhos indutores mais curtos entre nós não adjacentes no conjunto alvo.
   • Em seguida, impõe a condição de ordenação linear absorvendo pais de nós que violam a restrição de ordenação.
     O algoritmo roda em tempo polinomial ($O(k^2 \times |V|^4)$, onde $k$ é o tamanho do conjunto alvo e $|V|$ é o total de variáveis).
4. Integração com IDA para CPDAGs: O método estende-se para CPDAGs aproveitando o fato de que o casco d-convexo forte é invariante em todos os DAGs de uma classe de equivalência de Markov (Teorema 5). O proposto Algoritmo Subgraph IDA:
   • Seleciona um DAG arbitrário da classe de equivalência do CPDAG.
   • Computa o casco d-convexo forte para as variáveis de tratamento e desfecho.
   • Realiza a estimativa de efeito causal (usando ajuste de back-door) neste subgrafo local reduzido.
   • Isso reduz o espaço de enumeração de DAGs e o tamanho dos conjuntos de ajuste necessários para a estimativa.

Principais Contribuições

• Caracterização Teórica: O artigo introduz o conceito de colapsabilidade de estimativa para efeitos causais em CPDAGs e estabelece que conjuntos colapsáveis mínimos correspondem exatamente a cascos d-convexos fortes.
• Inovação Algorítmica: Propõe o algoritmo ISCHA para identificar eficientemente esses conjuntos mínimos em DAGs e generaliza a abordagem para CPDAGs.
• Eficiência em Estimativa Causal: Ao combinar a redução de grafo com o framework IDA, o método reduz significativamente a carga computacional de enumeração de DAGs e conjuntos de ajuste sem sacrificar a precisão da estimativa.

Resultados Experimentais
Os autores avaliaram o método através de simulações numéricas e análise empírica em redes bayesianas do mundo real (ex: Hailfinder, Pathfinder, Munin1) e grafos aleatórios sintéticos.

• Raciocínio Probabilístico: A abordagem de subgrafo local preservou a distribuição de probabilidade do grafo completo com divergência de Kullback-Leibzer negligenciável (ordem de $10^{-17}$ a $10^{-18}$). Alcançou taxas de redução de nós substanciais (até 96%) e acelerações significativas no tempo de consulta.
• Estimativa de Efeito Causal: Comparações entre o Subgraph IDA e o IDA padrão mostraram:
  • Precisão: Recall e Precisão perfeitos ou quase perfeitos (frequentemente 1.0) através de variados tamanhos de rede (20 a 100 nós) e densidades. As estimativas de efeito causal foram idênticas ao método do grafo completo.
  • Eficiência: O método demonstrou fatores de aceleração consistentes, variando de ~1.1x em redes pequenas a mais de 30x em redes grandes (ex: Munin1). A aceleração aumentou com o tamanho e a densidade da rede.

Significância e Alegações
O artigo afirma que seu método fornece uma solução rigorosa e eficiente para a estimativa de efeito causal em CPDAGs de alta dimensionalidade. Ao reduzir o problema a um subgrafo local definido pelo casco d-convexo forte, a abordagem mantém a consistência dos estimadores antes e depois da marginalização. Isso permite que pesquisadores realizem inferência causal precisa enquanto reduzem significativamente os custos computacionais e a complexidade do espaço do modelo. Os autores observam que o método é particularmente eficaz para pares tratamento-desfecho não adjacentes e atualmente assume dados totalmente observados, deixando grafos com variáveis latentes como uma direção para trabalhos futuros.