Simultaneous global and local clustering in multiplex networks with covariate information

Resumo Técnico: Agrupamento Global e Local Simultâneo em Redes Multiplex com Informação de Covariáveis

Definição do Problema
Dados de redes modernas frequentemente envolvem múltiplos tipos de interações entre o mesmo conjunto de entidades, representados como redes multiplex. Um desafio crítico na análise de tais dados é a detecção simultânea de dois tipos distintos de estruturas de comunidades:

1. Agrupamento Local (específico por camada): Identificar grupos de nós que interagem densamente dentro de uma camada específica (tipo de interação).
2. Agrupamento Global: Identificar um agrupamento unificado de nós que persiste em todas as camadas, refletindo um papel estrutural abrangente.

A literatura existente tem abordado majoritariamente o agrupamento de camadas ou o agrupamento global de forma isolada, ou assumiu um número conhecido e finito de comunidades. Além disso, poucos métodos integram informações de covariáveis nodais (metadados) para guiar o processo de agrupamento enquanto permitem, simultaneamente, um número desconhecido e potencialmente infinito de comunidades. Este artigo aborda a lacuna metodológica que pode realizar o agrupamento hierárquico (global e local) em redes multiplex enquanto incorpora covariáveis e lida com um número desconhecido de grupos.

Metodologia: O Modelo de Bloco Estocástico Multiplex Hierárquico (HMPSBM)
Os autores propõem o Modelo de Bloco Estocástico Multiplex Hierárquico (HMPSBM), um modelo bayesiano não paramétrico projetado para inferir tanto os agrupamentos globais de nós quanto os agrupamentos específicos de cada camada simultaneamente.

• Estrutura do Modelo:

  • Atribuição Global: Cada nó $i$ é atribuído a um grupo global $w_i$. A probabilidade desta atribuição, $\tau_i$, é construída usando um processo de quebra de bastão probit impulsionado por covariáveis nodais $x_i$. Isso permite que o modelo aprenda como as características influenciam a pertinência ao grupo global.
  • Atribuição Local: Condicional ao grupo global $w_i$, cada nó é atribuído a um grupo específico da camada $z_{\ell i}$ para cada camada $\ell$. Essas atribuições são governadas por proporções de mistura específicas do nó derivadas de distribuições compartilhadas de Griffiths-Engen-McCloskey (GEM).
  • Conectividade: Dentro de cada camada, as conexões seguem um Modelo de Bloco Estocástico (SBM). A probabilidade de uma conexão entre os nós $i$ e $j$ na camada $\ell$ depende de suas atribuições de grupo específicas da camada.
  • Priores Não Paramétricos: O modelo emprega um framework não paramétrico (especificamente usando distribuições GEM e representações de quebra de bastão) para permitir que o número de comunidades globais e de nível de camada seja desconhecido e inferido a partir dos dados, em vez de fixo a priori.

• Procedimento de Inferência:

  • Devido à complexidade da distribuição posterior, os autores propõem um procedimento de inferência Bayesiana Variacional (VB) utilizando Inferência Variacional de Ascensão de Coordenadas (CAVI).
  • A abordagem utiliza uma aproximação de campo médio onde a posterior é fatorada sobre os parâmetros do modelo.
  • Para lidar com a natureza de dimensão infinita do problema, os autores introduzem parâmetros de truncamento ($M_w$ para grupos globais e $M_z$ para grupos de camada).
  • O algoritmo inclui atualizações específicas para as variáveis de quebra de bastão e usa ascensão de gradiente (algoritmo Adam) para parâmetros que não possuem distribuições condicionais de forma fechada (especificamente os coeficientes de regressão que ligam as covariáveis às probabilidades de grupo global).
  • Inicialização: O método emprega um esquema de inicialização informada usando incorporação espectral (SVD) e HDBSCAN para semear os grupos de nível de camada, seguido por um passo de reenumeração para garantir consistência entre as camadas.

Principais Contribuições

1. Agrupamento Hierárquico Simultâneo: O artigo introduz a primeira metodologia para inferir simultaneamente um agrupamento global de nós e agrupamentos específicos de camada dentro de uma rede multiplex, permitindo padrões de agrupamento heterogêneos entre as camadas.
2. Integração de Covariáveis: O modelo incorpora informações de covariáveis nodais diretamente no mecanismo de agrupamento global via um processo de quebra de bastão probit, guiando a formação de grupos globais com base nas características dos nós.
3. Flexibilidade Não Paramétrica: Ao contrário de muitos SBMs multiplex existentes que exigem um número pré-especificado de comunidades, o HMPSBM permite um número desconhecido (efetivamente infinito) de grupos globais e de nível de camada, selecionando a complexidade apropriada automaticamente.
4. Inferência Escalável: Os autores desenvolvem um algoritmo de inferência variacional escalável com atualizações paralelizáveis, tornando a abordagem aplicável a grandes redes onde métodos de Cadeia de Markov Monte Carlo (MCMC) poderiam ser computacionalmente proibitivos.

Resultados
O desempenho do HMPSBM foi avaliado através de extensos estudos de simulação e uma aplicação no mundo real:

• Estudos de Simulação:

  • Recuperação de Contagens de Grupos: O modelo recuperou com sucesso o número real de grupos globais e de nível de camada quando os parâmetros de truncamento eram suficientemente grandes.
  • Covariável vs. Estrutura de Rede: Em configurações onde as covariáveis nodais tornaram-se pouco informativas (diminuindo a separação), o modelo ainda recuperou com precisão os grupos globais, demonstrando que a estrutura da rede é o principal motor do agrupamento, com as covariáveis servindo como um sinal auxiliar.
  • Robustez à Inicialização: Embora a inicialização informada tenha gerado uma convergência ligeiramente melhor, o modelo demonstrou robustez, convergindo para soluções semelhantes mesmo com inicialização aleatória na maioria dos casos.
  • Escalabilidade: O desempenho (medido pela Informação Mútua Normalizada, NMI) melhorou com o aumento do número de camadas e do tamanho da rede, particularmente em configurações de separação de conectividade fraca.

• Aplicação no Mundo Real (Rede de Comércio da FAO):

  • O modelo foi aplicado a uma rede multiplex de comércio global de alimentos (214 países, 314 tipos de alimentos), reduzida a 177 nós e 20 camadas.
  • Usando covariáveis como PIB e área terrestre, o modelo identificou 11 grupos globais e 6 grupos de nível de camada.
  • Interpretabilidade: Os grupos globais inferidos alinharam-se com a intuição econômica. Por exemplo, um grupo compreendia as grandes potências comerciais globais (EUA, China, Reino Unido, Alemanha, etc.), enquanto outro agrupava economias emergentes e potências regionais. Um cluster distinto de Síria e Irã foi identificado, refletindo seus relacionamentos comerciais específicos antes da Revolução Síria de 2011.
  • Impacto das Covariáveis: A adição de mais covariáveis (área de terra urbana, comprimento da linha costeira) refinou a periferia dos clusters (por exemplo, movendo estados costeiros/ilhas), mas deixou a estrutura central das principais economias inalterada, reforçando a descoberta de que a estrutura da rede é o fator dominante.

Significância e Alegações
O artigo afirma que o HMPSBM preenche uma lacuna metodológica crítica ao fornecer um framework unificado para o agrupamento hierárquico em redes multiplex que acomoda tanto tamanhos de comunidade desconhecidos quanto covariáveis nodais. Os autores sustentam que sua abordagem de inferência variacional oferece uma alternativa computacionalmente eficiente ao MCMC para redes de grande escala.

A significância do trabalho reside em sua capacidade de descobrir estruturas latentes que não são aparentes ao analisar as camadas isoladamente ou ignorar metadados. A aplicação à rede de comércio da FAO demonstra que o modelo pode revelar agrupamentos economicamente significativos que refletem tanto padrões comerciais quanto características geopolíticas/econômicas. Os autores observam modestamente que, embora o modelo assuma que os nós estão presentes em todas as camadas e que as covariáveis sejam totalmente observadas, o framework atual equilibra com sucesso as informações estruturais e baseadas em características para produzir resultados de agrupamento interpretáveis e precisos.