Nonparametric undirected graphical model selection using diffusion models

Resumo Técnico: Seleção de Modelos Gráficos Não Orientados Não Paramétricos Usando Modelos de Difusão

Definição do Problema
Modelos gráficos não orientados fornecem um arcabouço para representar estruturas de independência condicional entre variáveis aleatórias de alta dimensão. Embora a seleção de modelos seja um problema central na estatística de alta dimensão, com aplicações em genômica, neurociência e finanças, a maioria dos métodos existentes baseia-se em suposições paramétricas (por exemplo, modelos gráficos gaussianos ou modelos de Ising). Esses métodos frequentemente falham quando a distribuição verdadeira desvia da forma paramétrica assumida. Abordagens não paramétricas existem, mas são estatisticamente desafiadoras devido à "maldição da dimensionalidade" na estimativa de densidade e à complexidade adicional de estimar derivadas de segunda ordem (o Hessiano do log-densidade), que são necessárias para identificar a estrutura do grafo via equivalência $(i, j) \notin E_0 \iff \frac{\partial^2 \log p_0}{\partial x_i \partial x_j} = 0$.

Metodologia
Os autores propõem uma nova abordagem não paramétrica para a seleção de modelos gráficos não orientados baseada em modelos de difusão. O método aproveita o fato de que os modelos de difusão podem estimar funções de pontuação (score functions — gradientes do log-densidade) e se adaptar a estruturas de baixa dimensão sem sofrer com a maldição total da dimensionalidade.

O procedimento proposto, resumido no Algoritmo 1, consiste nas seguintes etapas:

1. Estimativa da Função de Pontuação: Utilizando um arcabouço padrão de modelagem de difusão (especificamente, o Modelo Probabilístico de Difusão de Denoising, DDPM), os autores estimam uma família de funções de pontuação $f_0(x, t) = \nabla \log p_t(x)$, onde $p_t$ é a densidade marginal do processo de difusão direta em um tempo $t$. Isso é alcançado via score matching nos dados observados.
2. Estimativa do Hessiano via Fórmula de Tweedie: Em vez de diferenciar diretamente a função de pontuação estimada (o que é numericamente instável), o método utiliza a fórmula de Tweedie de segunda ordem. Esta fórmula relaciona o Hessiano do log-densidade $\nabla^2 \log p_t(x)$ à covariância condicional dos dados originais $X_0$ dado a observação ruidosa $X_t = x$:
   $$\nabla^2 \log p_t(x) = \sigma_t^{-4} \mu_t^2 \text{Cov}[X_0 | X_t = x] - \sigma_t^{-2} I_D$$
   onde $\mu_t$ e $\sigma_t$ são parâmetros do processo de Ornstein-Uhlenbeck direto.
3. Recuperação do Grafo: O método estima a covariância condicional $\text{Cov}[X_0 | X_t = x]$ usando amostragem de Monte Carlo a partir do processo de difusão reversa. Especificamente, para um tempo $t$ fixo e um vetor aleatório $U_t$, os autores computam a expectativa empírica dos valores absolutos das entradas do Hessiano estimado, $E_n[|\hat{H}_{ij}(U_t, t)|]$.
4. Limiarização e Agrupamento: Uma aresta $(i, j)$ é incluída no grafo estimado se a magnitude média da entrada do Hessiano exceder um limiar $\tau$. Para lidar com o ajuste prático, os autores propõem agregar informações através de múltiplos pequenos passos de tempo $t_1, \dots, t_M$ e aplicar o agrupamento K-means aos valores padronizados do Hessiano para separar arestas de não-arestas.

Principais Contribuições Teóricas
O artigo estabelece garantias teóricas rigorosas para o método proposto sob condições de regularidade brandas (especificamente, que $\log p_0$ pertence a uma classe de Hölder $\mathcal{H}_{\beta, K}$):

• Taxas de Decaimento: Os autores provam que a covariância condicional $\text{Cov}[X_{0,i}, X_{0,j} | X_t = x]$ decai a taxas diferentes dependendo da distância do grafo $d(i, j)$ entre os nós. Para arestas ($d(i, j)=1$), a covariância decai como $O(t^2)$, enquanto para não-arestas ($d(i, j) \ge 2$), ela decai mais rapidamente, como $O(t^{(\beta+2)\wedge 5/2})$.
• Consistência de Seleção: Sob a suposição de que o estimador da função de pontuação converge para a verdadeira função de pontuação a uma taxa $\epsilon_n$, os autores derivam um limite superior não assintótico para a probabilidade de seleção incorreta do grafo. Eles mostram que, com escolhas apropriadas do parâmetro de tempo $t$ e do limiar $\tau$, o estimador é consistente (ou seja, $P(\hat{G}_{t, \tau} \neq G_0) = o(1)$) em um regime de dimensão fixa.
• Evasão da Estimativa Direta do Hessiano: Ao utilizar o processo de difusão e a fórmula de Tweedie, o método evita a necessidade de estimar diretamente o Hessiano da log-densidade da distribuição original $p_0$, que é estatisticamente mais exigente.

Resultados Empíricos
Os autores avaliam o método por meio de simulações extensas e duas análises de dados reais:

• Simulações: O método foi testado em quatro distribuições: duas Gaussianas e duas não Gaussianas (distribuição Butterfly e copula Gaussiana). O método baseado em difusão proposto (DDPM) apresentou desempenho competitivo com modelos paramétricos corretamente especificados (ex: Graphical Lasso para dados Gaussianos) e superou significativamente as bases não paramétricas existentes (SING e L-SING) em todas as distribuições. Notavelmente, alcançou a recuperação perfeita do grafo em configurações não Gaussianas onde os métodos paramétricos falharam.
• Análise de Imagem (MNIST): Aplicado ao conjunto de dados MNIST ($D=784$), o método recuperou um grafo de independência condicional esparso consistente com o princípio de localidade das imagens (pixels conectados principalmente a vizinhos imediatos). Também identificou uma assimetria específica nas arestas diagonais, refletindo a inclinação para a direita dos dígitos manuscritos no conjunto de dados.
• Dados Financeiros (Preços de Ações): Aplicado aos retornos diários de 28 empresas industriais, o método recuperou um grafo esparso de dependências condicionais. As arestas estimadas mostraram relações econômicas significativas, incluindo algumas não explicitamente rotuladas como concorrentes em bases de dados externas, mas sustentadas por parcerias de cadeia de suprimentos ou tecnologia.

Significância e Alegações
O artigo afirma preencher a lacuna entre a adaptabilidade teórica dos modelos de difusão a estruturas de grafos desconhecidas e sua aplicação prática para estimativa explícita de grafos. Os autores enfatizam que seu método oferece uma alternativa não paramétrica unificada para as abordagens existentes, capaz de lidar com distribuições complexas e não Gaussianas sem exigir a especificação correta do modelo. Eles observam que, embora a consistência teórica seja estabelecida para dimensões fixas, os resultados empíricos sugerem que o método escala efetivamente para configurações de alta dimensão ($D \gg n$), aproveitando a estrutura intrínseca de baixa dimensão dos dados. O trabalho conclui identificando a extensão para assintóticas de alta dimensão e distribuições discretas como direções naturais para pesquisas futuras.