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

Resumen Técnico: Pruebas de Máxima Entropía en Modelos de Redes

1. Planteamiento del Problema

El artículo aborda problemas fundamentales de inferencia estadística en redes aleatorias, específicamente:

• Pruebas de Bondad de Ajuste (Goodness-of-Fit): Determinar si una red observada (o una colección de ellas) proviene de un modelo de red aleatoria específico con parámetros predefinidos.
• Pruebas de Muestra Doble (Two-Sample Testing): Evaluar si dos muestras independientes de redes provienen del mismo modelo subyacente.

El desafío central reside en la naturaleza de los datos de red, donde el tamaño de la red (número de vértices) puede crecer con el tamaño de la muestra, y las estructuras dependen de conteos de subgrafos (motivos) que no siempre son identificables de manera única en modelos complejos como los Modelos de Grafos Aleatorios Exponenciales (ERGM).

2. Metodología Propuesta

La propuesta de los autores se basa en el Principio de Máxima Entropía (MaxEnt) y la optimización con restricciones, alejándose de los enfoques tradicionales basados directamente en la verosimilitud (likelihood) o en conteos crudos de subgrafos.

• Formulación de Optimización:
  Dado un conjunto de $n$ grafos observados $G_1, \dots, G_n$, se define un problema de maximización de entropía empírica sujeto a restricciones estructurales (basadas en los conteos de motivos centrados).
  Se busca maximizar la entropía de una distribución de pesos $w = (w_1, \dots, w_n)$ asignada a los grafos:
  $$\max_{w} -\sum_{i=1}^n w_i \log w_i$$
  sujeto a:
  $$\sum_{i=1}^n w_i h(G_i) = 0, \quad \sum w_i = 1, \quad w_i \ge 0$$
  donde $h(G_i)$ representa el conteo centrado de un motivo $H$ en el grafo $G_i$ (es decir, $T(H, G_i) - \mathbb{E}[T(H, G)]$).

• Estadístico de Prueba (Multiplicador de Lagrange):
  La solución a este problema de optimización convexa conduce a un multiplicador de Lagrange óptimo, denotado como $\hat{\lambda}_n$.

  • La hipótesis nula ($H_0$) implica que las restricciones se satisfacen con la distribución verdadera, lo que teóricamente lleva a $\lambda^\circ = 0$.
  • La desviación de $\hat{\lambda}_n$ de cero bajo $H_0$ sirve como estadístico de prueba.
  • El método conecta conceptualmente con las pruebas de puntuación (Score tests) en econometría, pero adaptadas a espacios de grafos de alta dimensión.

• Análisis Asintótico:
  Los autores analizan el comportamiento asintótico de $\hat{\lambda}_n$ en tres regímenes distintos:

  1. Tamaño Fijo: El número de vértices $m$ es constante.
  2. Régimen Disperso (Sparse): El número de vértices $m_n \to \infty$ y la probabilidad de arista $p_n \to 0$ (modelos Erdös-Rényi).
  3. Régimen Denso (Dense): $m_n \to \infty$ y $p_n = \Theta(1)$ (incluyendo ERGMs ferromagnéticos subcríticos y Erdös-Rényi densos).

3. Contribuciones Clave

1. Novedad en la Literatura de Redes: Es la primera vez que se utilizan los multiplicadores de Lagrange derivados de la maximización de entropía empírica como estadísticos de prueba para modelos de redes, en lugar de usarlos meramente como herramientas computacionales.
2. Marco Unificado: Proporciona un marco inferencial basado en la entropía que cubre desde grafos de tamaño fijo hasta redes masivas en regímenes dispersos y densos.
3. Conexión con Grandes Desviaciones No Lineales: Para el régimen denso, el análisis se apoya fuertemente en la teoría de grandes desviaciones no lineales (Chatterjee-Dembo) y la teoría de límites de grafos (graphons), permitiendo caracterizar el comportamiento del multiplicador de Lagrange mediante problemas variacionales sobre el espacio de grafones.
4. Pruebas de Muestra Doble: Desarrollan procedimientos robustos para comparar dos distribuciones de redes utilizando la diferencia de sus multiplicadores de Lagrange estimados independientemente.

4. Resultados Principales

• Consistencia y Normalidad Asintótica:

  • Tamaño Fijo: Se demuestra que $\hat{\lambda}_n$ es consistente y asintóticamente normal bajo $H_0$.
  • Régimen Disperso: Para grafos Erdös-Rényi, los conteos de motivos convergen a una distribución Poisson. Los autores prueban que el multiplicador de Lagrange centrado y escalado sigue una distribución normal, permitiendo construir pruebas de bondad de ajuste y de dos muestras para la probabilidad de arista $p$.
  • Régimen Denso: Para ERGMs en régimen subcrítico, se demuestra que el logaritmo de la función objetivo converge a un funcional convexo definido sobre grafones. Se establecen tasas de convergencia precisas (del orden de $m_n^{-2}$) para $\hat{\lambda}_n$.

• Construcción de Pruebas:

  • Bondad de Ajuste: Se propone rechazar $H_0$ si $\hat{\lambda}_n$ excede un umbral crítico basado en la distribución normal (para pruebas unilaterales, que son las técnicamente viables en sus marcos).
  • Dos Muestras: Se utiliza la estadística $(\hat{\lambda}_{n1} - \hat{\lambda}_{n2})$ estandarizada por su varianza estimada. Bajo $H_0$ (mismos parámetros), esta diferencia converge a una normal estándar.

• Limitaciones Técnicas:

  • Las pruebas se formulan principalmente como unilaterales debido a dificultades técnicas en la caracterización de la distribución asintótica cuando el multiplicador de Lagrange es negativo en ciertos regímenes (especialmente en el régimen denso donde el supremo variacional puede no ser alcanzado por un grafón constante).

5. Significado e Impacto

• Generalización de Métodos Clásicos: El trabajo extiende la lógica de las pruebas de Lagrange (muy comunes en econometría para datos vectoriales) al dominio complejo de las redes, donde la dimensionalidad crece con la muestra.
• Robustez: Al basarse en el principio de máxima entropía, el método es natural para modelos de redes y ofrece una alternativa a los métodos basados en verosimilitud, que a menudo son computacionalmente intratables en ERGMs debido a la constante de normalización.
• Herramienta para Modelos Complejos: Proporciona una vía para realizar inferencia en modelos ERGMs densos en régimen subcrítico, un área donde las pruebas estadísticas han sido escasas.
• Futuro: Abre la puerta a futuras investigaciones para extender estos resultados a regímenes supercríticos, modelos dispersos más generales (más allá de Erdös-Rényi) y pruebas de dos colas.

En conclusión, el artículo establece un nuevo paradigma para la inferencia en redes, transformando problemas de ajuste de modelos en problemas de optimización convexa y explotando la teoría avanzada de grandes desviaciones para derivar propiedades estadísticas rigurosas de los multiplicadores de Lagrange resultantes.