Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models

Resumen Técnico: Uniendo la Máxima Verosimilitud y el Transporte Óptimo para una Inferencia Eficiente y Selección de Modelos en Modelos de Bloques Estocásticos

Planteamiento del Problema
El artículo aborda el desafío de la inferencia y la selección de modelos en Modelos de Bloques Estocásticos (SBM), un marco generativo para grafos aleatorios donde los nodos se dividen en grupos ocultos y las probabilidades de las aristas dependen de la pertenencia al grupo. Aunque los SBM ofrecen ventajas sobre otros métodos de agrupamiento (como la maximización de la modularidad o el agrupamiento espectral) al recuperar estructuras diversas y proporcionar herramientas para estimar el número de grupos, la inferencia estándar suele depender del Método de Maximización de Expectación Variacional (VEM). Una limitación crítica del VEM es su dependencia de la regularización entrópica para garantizar la suavidad de la optimización. Esta regularización impide que los planes de transporte sean dispersos, obstaculizando así la "selección de modelos intrínseca": la capacidad de desactivar automáticamente grupos innecesarios (asignándoles masa cero) dentro de un único problema de optimización. En consecuencia, los enfoques actuales a menudo requieren búsquedas en cuadrícula computacionalmente costosas o procedimientos heurísticos para determinar el número óptimo de grupos ($K$).

Metodología
Los autores proponen un marco novedoso que interpreta la Inferencia Variacional de Máxima Verosimilitud (MLVI) en SBM a través de la lente del Transporte Óptimo (OT), utilizando específicamente la divergencia Gromov-Wasserstein Semi-Relajada (srGW).

1. Reformulación como srGW: El artículo establece que la maximización del límite inferior de evidencia (ELBO) en SBM es equivalente a minimizar una divergencia srGW con un término de regularización entrópica. La función de pérdida corresponde al logaritmo negativo de la verosimilitud del modelo generativo.
2. Estimadores sin regularizar: Reconociendo que la regularización entrópica impide la dispersión, los autores investigan estimadores srGW sin regularizar. Definen estimadores para la matriz de conectividad ($\Theta$) y el plan de transporte ($T$, que representa las asignaciones de grupos) minimizando la pérdida srGW sin el término de entropía.
3. Regularización que promueve la dispersión para la selección de modelos: Para permitir la selección automática de modelos (estimación de $K$) sin búsqueda en cuadrícula, los autores introducen una penalización de pseudo-norma $\ell_{1/2}$ sobre el plan de transporte. Esta penalización fomenta que las proporciones de grupos estimadas sean dispersas, estableciendo efectivamente la masa de los grupos no óptimos en cero.
4. Optimización: Los parámetros se estiman utilizando un algoritmo de Descenso de Coordenadas por Bloques. Esto alterna entre:
   • Actualizar la matriz de conectividad $\Theta$ utilizando soluciones de forma cerrada derivadas de las condiciones de optimalidad de primer orden.
   • Actualizar el plan de transporte $T$ utilizando un algoritmo de Mayorización-Minimización (MM), que linealiza la penalización de dispersión y resuelve el problema cuadrático resultante (por ejemplo, mediante Frank-Wolfe).

Contribuciones Clave

• Vínculo Teórico: El artículo demuestra que la MLVI en SBM puede interpretarse como una proyección Gromov-Wasserstein semi-relajada con regularización entrópica.
• Resultados de Consistencia: Los autores demuestran que los estimadores srGW sin regularizar recuperan consistentemente tanto la verdadera matriz de conectividad del SBM como las asignaciones de grupos latentes en el régimen asintótico ($N \to \infty$).
• Selección Automática de Modelos: Al incorporar una penalización que promueve la dispersión, el método permite la recuperación simultánea de los parámetros del modelo y la selección del número de grupos en un único paso de optimización. Esto evita la necesidad de búsquedas en cuadrícula costosas o heurísticas codiciosas.
• Eficiencia Algorítmica: El solucionador propuesto está diseñado para la eficiencia, con una complejidad teórica dominada por el cálculo del gradiente ($O(N^2K + K^2N)$), y se muestra significativamente más rápido en CPUs en comparación con los estimadores variacionales más avanzados.

Resultados
Los autores evalúan su enfoque en datos sintéticos generados a partir de SBM Bernoulli bajo tres regímenes de conectividad: Agrupativo, de Hub y Desagrupativo.

• Rendimiento de Agrupamiento: El estimador srGW propuesto que utiliza una pérdida de logaritmo negativo de la verosimilitud (srGW-NLL) supera o iguala consistentemente a las líneas base más avanzadas (incluyendo Louvain, Infomap, Greed y Estimadores Variacionales) en términos del Índice Rand Ajustado (ARI), particularmente en los regímenes de Hub y Desagrupativo donde se violan las suposiciones estructurales de otros métodos.
• Selección de Modelos: El método recupera con éxito el número verdadero de grupos ($K^*$) en diversos ajustes de hiperparámetros, demostrando una meseta en el rendimiento cuando el parámetro de dispersión se ajusta adecuadamente.
• Eficiencia: Se informa que el método srGW-NLL es de 1 a 2 órdenes de magnitud más rápido en CPU que el Estimador Variacional y los métodos Greed, principalmente porque elude los bucles iterativos de selección de modelos requeridos por esos enfoques.

Significado y Afirmaciones
El artículo afirma proporcionar un puente teórico y práctico unificado entre el Transporte Óptimo y los Modelos de Bloques Estocásticos. Su principal significado radica en demostrar que los estimadores basados en OT no solo son consistentes para la recuperación de parámetros, sino que también pueden realizar una selección de modelos intrínseca mediante la promoción de la dispersión. Esto ofrece una alternativa computacionalmente eficiente a los métodos tradicionales basados en verosimilitud que luchan con la complejidad combinatoria de seleccionar el número de grupos. Los autores posicionan su trabajo como un paso hacia una partición de grafos más robusta y eficiente, particularmente en escenarios donde el número de comunidades es desconocido y la estructura del grafo es compleja (por ejemplo, conteniendo hubs o patrones desagrupativos). Señalan que, aunque se ha demostrado la consistencia asintótica, el ajuste del hiperparámetro de dispersión sigue siendo un área para futura investigación, y el rendimiento del método en redes del mundo real es un tema para un estudio posterior.