Maximum entropy based testing in network models: ERGMs and constrained optimization

Resumo Técnico: Testes Baseados em Máxima Entropia em Modelos de Redes

1. Problema e Contexto

O artigo aborda o problema fundamental de inferência estatística em dados de redes, especificamente focado em testes de aderência (goodness-of-fit) e testes de duas amostras (two-sample tests).

• Contexto: Modelos de redes estocásticas são ubíquos em diversas disciplinas (redes sociais, biológicas, cerebrais). A inferência estatística nessas redes geralmente envolve estimar parâmetros ou testar se os dados observados seguem um modelo específico.
• Desafio: Métodos tradicionais de teste de hipóteses muitas vezes dependem de estatísticas de resumo específicas ou de aproximações assintóticas que podem não ser robustas em regimes de rede complexos (esparsos ou densos). Além disso, muitos modelos de redes, como os Modelos de Grafos Aleatórios Exponenciais (ERGMs), não são facilmente identificáveis através de contagens simples de subgrafos, dificultando a formulação de testes diretos de parâmetros.
• Objetivo: Desenvolver um quadro unificado de inferência baseado no Princípio de Máxima Entropia (MaxEnt), onde a estrutura da rede é restringida por contagens esperadas de motivos (subgrafos), e utilizar os multiplicadores de Lagrange resultantes como estatísticas de teste.

2. Metodologia

A abordagem central do artigo inverte a lógica tradicional: em vez de maximizar a verossimilhança (MLE), os autores maximizam a entropia da distribuição empírica dos contagens de motivos, sujeita a restrições impostas pela hipótese nula.

• Formulação de Otimização:
  Dada uma amostra de $n$ grafos $G_1, \dots, G_n$, define-se um vetor de pesos $w = (w_1, \dots, w_n)$ para maximizar a entropia empírica:
  $$\max_{w} -\sum_{i=1}^n w_i \log w_i$$
  Sujeito a:
  $$\sum_{i=1}^n w_i h(G_i) = 0 \quad \text{e} \quad \sum w_i = 1, \quad w_i \ge 0$$
  Onde $h(G_i) = T(H, G_i) - \mathbb{E}_{H_0}[T(H, G)]$ representa a contagem centrada do motivo $H$ (subgrafo) no grafo $G_i$, subtraindo a expectativa sob a hipótese nula.

• Estatística de Teste (Multiplicador de Lagrange):
  A solução deste problema de otimização concava estrita é encontrada via multiplicadores de Lagrange. O artigo demonstra que o multiplicador de Lagrange ótimo ($\hat{\lambda}_n$) associado à restrição de entropia possui propriedades assintóticas robustas.

  • Sob a hipótese nula, $\hat{\lambda}_n$ converge para zero (ou uma constante conhecida).
  • O teste é construído analisando a distribuição assintótica de $\hat{\lambda}_n$ (ou sua versão escalonada).

• Ferramentas Teóricas:
  O trabalho integra três áreas avançadas:

  1. Teoria de Limites de Grafos (Graph Limits/Graphons): Essencial para o regime denso, permitindo tratar sequências de grafos como funções contínuas (grafons).
  2. Desvios Grandes Não-Lineares (Non-linear Large Deviations): Utiliza resultados recentes (ex: Chatterjee & Dembo) para analisar a energia livre e o comportamento de grafos aleatórios densos, fornecendo limites de erro quantitativos.
  3. Teoria de Estimadores Z (Z-estimators): Utilizada para estabelecer a normalidade assintótica do multiplicador de Lagrange como a raiz de uma equação de estimativa.

3. Principais Contribuições

O artigo apresenta contribuições teóricas e metodológicas significativas:

1. Novo Paradigma de Teste: Propõe o uso do multiplicador de Lagrange derivado da maximização de entropia empírica como estatística de teste para redes, uma abordagem inédita na literatura de redes estatísticas (diferente dos testes baseados em verossimilhança ou Stein).
2. Unificação de Regimes: Desenvolve a teoria para três regimes distintos de crescimento da rede:
   • Tamanho Fixo: O número de vértices é constante.
   • Regime Espesso (Dense): O número de vértices cresce, mas a densidade de arestas permanece constante ($p = \Theta(1)$). Aplica-se a ERGMs ferromagnéticos subcríticos e modelos Erdös-Rényi densos.
   • Regime Esparso (Sparse): O número de vértices cresce e a densidade tende a zero. Foca-se em modelos Erdös-Rényi esparsos onde contagens de motivos convergem para distribuições de Poisson.
3. Conexão com Econometria: Estabelece uma ponte teórica entre testes de redes e os clássicos Testes de Multiplicador de Lagrange (LM) ou testes de Score usados em econometria para dados reais, generalizando-os para o espaço de grafos.
4. Resultados de Consistência e Normalidade: Prova a consistência e a normalidade assintótica do multiplicador de Lagrange em todos os regimes considerados, permitindo a construção de testes com nível de significância controlado.

4. Resultados Chave

• Regime de Tamanho Fixo:

  • O multiplicador de Lagrange $\hat{\lambda}_n$ converge quase certamente para uma raiz única $\lambda^\circ$.
  • Sob $H_0$, $\sqrt{n}(\hat{\lambda}_n - \lambda^\circ)$ converge em distribuição para uma Normal. Isso permite testes de aderência baseados em estatísticas $Z$.

• Regime Espesso (Dense):

  • Para ERGMs no regime subcrítico ferromagnético, o problema de otimização converge para um problema variacional sobre o espaço de grafons.
  • O multiplicador de Lagrange é caracterizado como a raiz de uma função derivada da energia livre do modelo.
  • Estabelecem-se taxas de convergência precisas ($m_n^2(\hat{\lambda}_n - \lambda^\circ)$) que distinguem as hipóteses nula e alternativa, permitindo testes consistentes mesmo quando a distribuição assintótica exata é difícil de derivar.

• Regime Esparso (Sparse):

  • Para grafos Erdös-Rényi esparsos, a contagem de motivos segue uma distribuição de Poisson.
  • O artigo prova que a contagem empírica "tilted" (exponencialmente distorcida) satisfaz um Teorema do Limite Central.
  • O multiplicador de Lagrange escalonado e centrado é assintoticamente normal, permitindo testes de aderência e testes de duas amostras para a probabilidade de aresta $p$.

• Testes de Duas Amostras:

  • O método é estendido para comparar duas amostras de redes. A estatística de teste baseia-se na diferença entre os multiplicadores de Lagrange calculados independentemente para cada amostra ($\hat{\lambda}_{n1} - \hat{\lambda}_{n2}$), que converge para uma distribuição normal sob a hipótese de que as redes provêm do mesmo modelo.

5. Significância e Impacto

• Generalidade: A abordagem não depende de um modelo específico de rede, mas sim do princípio de máxima entropia, tornando-a aplicável a uma vasta gama de modelos, desde ERGMs até grafos aleatórios simples.
• Robustez: Ao utilizar técnicas de desvios grandes não-lineares, o método lida com a complexidade analítica de redes densas onde métodos clássicos falham devido a degenerescências ou falta de normalidade.
• Interpretabilidade: O uso do multiplicador de Lagrange conecta a inferência de redes a uma vasta literatura estatística estabelecida, oferecendo uma intuição clara: o teste verifica se a "força" necessária para impor as restrições de estrutura (motivos) é estatisticamente significativa.
• Aplicações Práticas: O framework oferece ferramentas para validar modelos em neurociência (comparação de redes cerebrais), biologia (redes de interação proteína-proteína) e ciência social, especialmente em cenários onde o tamanho da rede cresce com a amostra.

Em suma, o artigo fornece um quadro inferencial unificado baseado em entropia que supera limitações de métodos anteriores, utilizando a teoria moderna de limites de grafos e grandes desvios para estabelecer testes estatísticos rigorosos e consistentes para redes em diversas escalas.