Exact Graph Learning via Integer Programming

1. Problema e Contexto

O aprendizado de grafos (ou descoberta causal) visa inferir a estrutura de dependência entre variáveis de um sistema complexo a partir de dados observacionais. Essas estruturas são representadas por grafos, onde nós são variáveis e arestas indicam dependências.

O desafio central abordado no artigo é a limitação dos métodos existentes:

• Métodos Baseados em Restrições (ex: PC, FCI): Dependem de testes de independência condicional sequenciais. São sensíveis a erros de teste em amostras finitas e podem falhar em garantir a solução globalmente ótima, especialmente sob violações de "fidelidade" (near-faithfulness).
• Métodos Baseados em Pontuação (Score-based): Frequentemente utilizam algoritmos gananciosos (greedy) que não garantem o ótimo global ou exigem suposições distribucionais restritivas (ex: linearidade gaussiana).
• Métodos Exatos Atuais: Abordagens anteriores que garantem o ótimo global (como as baseadas em Answer Set Programming - ASP) tornam-se computacionalmente inviáveis para grafos com mais de 6 nós devido ao crescimento explosivo do espaço de busca.

O objetivo é desenvolver um método não paramétrico e exato que garanta a solução globalmente ótima para classes de grafos complexos (DAGs, ADMGs, Grafos de Cadeia) sem depender de suposições distribucionais rígidas, superando as limitações de escalabilidade dos métodos exatos anteriores.

2. Metodologia: GLIP (Graph Learning via Integer Programming)

Os autores propõem o GLIP, um framework que reformula o problema de aprendizado de grafos como um Programa Inteiro Misto (MIP). A abordagem combina a flexibilidade de métodos baseados em pontuação com a robustez de métodos baseados em restrições.

2.1 Formulação do Problema

O problema é definido como a minimização de uma função objetivo que mede a discrepância entre as separações gráficas implícitas em um candidato a grafo e os resultados de testes de independência condicional (valores-p) derivados dos dados.

• Entrada: Um conjunto de valores-p de testes de independência condicional entre variáveis $X_i$ e $X_j$ dado um conjunto de condicionamento $C$.
• Objetivo: Encontrar um grafo $G$ que minimize a soma ponderada das discrepâncias entre a separação gráfica (ex: d-separação, m-separação) e os valores-p observados (binarizados por um limiar $\alpha$).

2.2 Codificação de Comprimento Mínimo (Minimal-Length Encoding)

A contribuição técnica central do GLIP é uma nova codificação para as restrições de separação gráfica.

• Problema Anterior: Abordagens anteriores (ex: Eberhardt et al., 2025) codificavam cada caminho possível no grafo como uma variável, resultando em um número de variáveis que cresce fatorialmente ($O(d!)$), limitando a aplicação a grafos muito pequenos ($d \le 6$).
• Solução GLIP: Em vez de rastrear caminhos individuais, o GLIP codifica o comprimento do caminho de conexão mais curto entre dois nós dado um conjunto de condicionamento.
  • Introduz variáveis inteiras $l^C_{\{i,j\}}$ representando o comprimento do caminho mais curto que conecta $i$ e $j$ dado $C$.
  • Utiliza um conjunto de regras lógicas (restrições lineares) que relacionam as arestas do grafo com esses comprimentos mínimos.
  • Complexidade: O número de variáveis no programa inteiro cresce linearmente com o número de valores-p de entrada, permitindo a escalabilidade para grafos muito maiores.

2.3 Classes de Grafos Suportadas

O framework é modular e suporta diversas classes de grafos, adaptando as restrições de separação conforme necessário:

• DAGs (Grafos Acíclicos Direcionados) e DGs (Grafos Direcionados, permitindo ciclos).
• ADMGs (Grafos Direcionados Mistas Acíclicos) e DMGs (Grafos Direcionados Mistas).
• Grafos de Cadeia (Chain Graphs) com interpretação LWF.
• O método também suporta aprendizado fraco (weak graph learning), onde apenas independências condicionais com conjuntos de condicionamento de tamanho limitado ($k$) são consideradas, reduzindo ainda mais a complexidade.

3. Contribuições Principais

1. Algoritmo Exato e Não Paramétrico: O GLIP é o primeiro método baseado em programação inteira mista que oferece garantias de solução globalmente ótima para grafos direcionados mistos (com mais de 6 nós) e grafos de cadeia, sem assumir uma distribuição específica dos dados (apenas testes de independência condicional).
2. Codificação Escalável: A técnica de "codificação de comprimento mínimo" reduz drasticamente o número de variáveis necessárias em comparação com métodos anteriores, permitindo o aprendizado de grafos com até 14 nós (em cenários de aprendizado fraco) e 9 nós (aprendizado completo) dentro de limites de tempo computacional razoáveis.
3. Flexibilidade e Modularidade: O framework permite a inclusão de conhecimento de domínio (ex: "o nó $v$ é um sumidouro") e suporta qualquer função de perda que possa ser linearizada no programa inteiro.
4. Implementação de Código Aberto: Os autores lançaram o pacote R glip, que facilita a aplicação do método em dados reais e simulados.

4. Resultados Empíricos

Os autores realizaram extensas avaliações comparativas usando dados simulados e conjuntos de dados de benchmark (ALARM, ASIA, CHILD, HEPAR2, SACHS).

• Comparação com Métodos Exatos (ASP):

  • O GLIP foi comparado com abordagens baseadas em Answer Set Programming (ASP).
  • Desempenho: O GLIP é geralmente mais rápido para grafos pequenos e médios. Para grafos maiores (9 a 14 nós), o GLIP consegue resolver uma fração significativa das instâncias dentro do limite de tempo (600s), enquanto o ASP frequentemente falha ou atinge o limite de tempo sem encontrar solução.
  • Em cerca de 50% das instâncias, o GLIP é mais rápido; nos outros 50%, o ASP pode ser mais rápido, sugerindo que rodar ambos em paralelo pode ser uma estratégia viável.

• Comparação com Métodos Aproximados (PC, FCI, NOTEARS):

  • Qualidade da Solução: O GLIP frequentemente supera ou iguala o desempenho de métodos aproximados (como PC, FCI e NOTEARS) em métricas como Distância Hamming Estrutural (SHD) e F1-score.
  • Propriedade de Correção de Erros: Em experimentos com grandes tamanhos de amostra, o GLIP demonstrou capacidade de "corrigir" erros nos testes de independência condicional de entrada. Mesmo quando os valores-p iniciais são inconsistentes com um modelo válido, o GLIP encontra um grafo que é mais consistente com a verdade fundamental do que os testes brutos sugerem.
  • Robustez: O método mostrou-se robusto a violações de fidelidade (near-faithfulness), onde métodos gananciosos como o FCI falham ao remover arestas incorretamente devido a correlações altas.

5. Significado e Impacto

O trabalho representa um avanço significativo na área de descoberta causal e aprendizado de grafos:

• Viabilidade Prática: Torna viável a busca por soluções exatas em problemas que antes eram considerados computacionalmente intratáveis devido ao crescimento fatorial do espaço de busca.
• Confiança Teórica: Ao garantir o ótimo global, o GLIP elimina a incerteza de que o algoritmo tenha ficado preso em um ótimo local, um problema comum em métodos heurísticos.
• Generalidade: A capacidade de lidar com variáveis latentes (via ADMGs) e ciclos (via DGs/DMGs) sem suposições distribucionais torna o método aplicável a uma gama muito mais ampla de cenários do mundo real do que os métodos baseados em modelos lineares gaussianos.
• Ferramenta Acessível: A disponibilização do pacote glip em R democratiza o acesso a técnicas de otimização combinatória avançadas para pesquisadores e praticantes.

Em resumo, o GLIP preenche uma lacuna crítica entre a precisão teórica dos métodos exatos e a escalabilidade necessária para aplicações práticas, oferecendo um novo padrão para o aprendizado de estruturas de dependência complexas.