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

Resumo Técnico: Ponte entre Máxima Verossimilhança e Transporte Ótimo para Inferência Eficiente e Seleção de Modelos em Modelos de Blocos Estocásticos

Declaração do Problema
O artigo aborda o desafio da inferência e seleção de modelos em Modelos de Blocos Estocásticos (SBMs), um framework generativo para grafos aleatórios onde os nós são particionados em clusters ocultos e as probabilidades de arestas dependem da pertença ao cluster. Embora os SBMs ofereçam vantagens sobre métodos alternativos de agrupamento (como maximização de modularidade ou agrupamento espectral) ao recuperar estruturas diversas e fornecer ferramentas para estimar o número de clusters, a inferência padrão frequentemente depende do Máximo da Expectativa Variacional (VEM). Uma limitação crítica do VEM é sua dependência de regularização entrópica para garantir suavidade na otimização. Essa regularização impede que os planos de transporte se tornem esparsos, dificultando assim a "seleção de modelo intrínseca"—a capacidade de desativar automaticamente clusters desnecessários (atribuindo-lhes massa zero) dentro de um único problema de otimização. Consequentemente, as abordagens atuais frequentemente exigem buscas em grade computacionalmente caras ou procedimentos heurísticos para determinar o número ótimo de clusters ($K$).

Metodologia
Os autores propõem um novo framework que interpreta a Inferência Variacional de Máxima Verossimilhança (MLVI) em SBMs através da lente do Transporte Ótimo (OT), utilizando especificamente a divergência Gromov-Wasserstein Semi-Relaxada (srGW).

1. Reformulação como srGW: O artigo estabelece que a maximização do ELBO (Limite Inferior de Evidência) em SBM é equivalente à minimização de uma divergência srGW com um termo de regularização entrópica. A função de perda corresponde ao log-verossimilhança negativa do modelo generativo.
2. Estimadores Não Regularizados: Reconhecendo que a regularização entrópica impede a esparsidade, os autores investigam estimadores srGW não regularizados. Eles definem estimadores para a matriz de conectividade ($\Theta$) e o plano de transporte ($T$, representando atribuições de cluster) minimizando a perda srGW sem o termo de entropia.
3. Regularização Promovendo Esparsidade para Seleção de Modelo: Para permitir a seleção automática de modelos (estimando $K$) sem busca em grade, os autores introduzem uma penalidade de pseudo-norma $\ell_{1/2}$ no plano de transporte. Essa penalidade incentiva que as proporções de clusters estimadas sejam esparsas, efetivamente definindo a massa de clusters não ótimos como zero.
4. Otimização: Os parâmetros são estimados usando um algoritmo de Descida de Coordenadas em Blocos. Isso alterna entre:
   • Atualizar a matriz de conectividade $\Theta$ usando soluções de forma fechada derivadas das condições de otimalidade de primeira ordem.
   • Atualizar o plano de transporte $T$ usando um algoritmo de Majorização-Minimização (MM), que lineariza a penalidade de esparsidade e resolve o problema quadrático resultante (por exemplo, via Frank-Wolfe).

Principais Contribuições

• Vínculo Teórico: O artigo prova que a MLVI em SBMs pode ser interpretada como uma projeção Gromov-Wasserstein semi-relaxada com regularização entrópica.
• Resultados de Consistência: Os autores provam que os estimadores srGW não regularizados recuperam consistentemente tanto a verdadeira matriz de conectividade do SBM quanto as atribuições de clusters latentes no regime assintótico ($N \to \infty$).
• Seleção Automática de Modelo: Ao incorporar uma penalidade que promove esparsidade, o método permite a recuperação simultânea dos parâmetros do modelo e a seleção do número de clusters em uma única etapa de otimização. Isso evita a necessidade de buscas em grade custosas ou heurísticas gananciosas.
• Eficiência Algorítmica: O solucionador proposto é projetado para eficiência, com complexidade teórica dominada pelo cálculo do gradiente ($O(N^2K + K^2N)$), e demonstrou ser significativamente mais rápido em CPUs em comparação com estimadores variacionais do estado da arte.

Resultados
Os autores avaliam sua abordagem em dados sintéticos gerados a partir de SBMs Bernoulli sob três regimes de conectividade: Associativo, Hub e Desassociativo.

• Desempenho de Agrupamento: O estimador srGW proposto usando uma perda de log-verossimilhança negativa (srGW-NLL) consistentemente supera ou iguala as bases de referência do estado da arte (incluindo Louvain, Infomap, Greed e Estimadores Variacionais) em termos de Índice Rand Ajustado (ARI), particularmente nos regimes Hub e Desassociativo onde as suposições estruturais de outros métodos são violadas.
• Seleção de Modelo: O método recupera com sucesso o número verdadeiro de clusters ($K^*$) através de várias configurações de hiperparâmetros, demonstrando um platô no desempenho quando o parâmetro de esparsidade é ajustado adequadamente.
• Eficiência: O método srGW-NLL é relatado como sendo 1 a 2 ordens de magnitude mais rápido em CPU do que os métodos Estimador Variacional e Greed, principalmente porque contorna os loops iterativos de seleção de modelo exigidos por essas abordagens.

Significado e Afirmações
O artigo afirma fornecer uma ponte teórica e prática unificada entre Transporte Ótimo e Modelos de Blocos Estocásticos. Seu significado principal reside em demonstrar que estimadores baseados em OT não são apenas consistentes para recuperação de parâmetros, mas também podem realizar seleção de modelo intrínseca através da promoção de esparsidade. Isso oferece uma alternativa computacionalmente eficiente aos métodos tradicionais baseados em verossimilhança que lutam com a complexidade combinatória de selecionar o número de clusters. Os autores posicionam seu trabalho como um passo rumo a uma particionamento de grafos mais robusto e eficiente, particularmente em cenários onde o número de comunidades é desconhecido e a estrutura do grafo é complexa (por exemplo, contendo hubs ou padrões desassociativos). Eles observam que, embora a consistência assintótica seja provada, o ajuste do hiperparâmetro de esparsidade permanece uma área para investigação futura, e o desempenho do método em redes do mundo real é um assunto para estudos adicionais.