Ordering Stochastic Block Models via prior transitivity

Resumo Técnico: Ordenação de Modelos de Blocos Estocásticos via Transitividade de Priori

Definição do Problema
Redes direcionadas frequentemente exibem duas características estruturais simultâneas: estrutura de comunidade (nós formando grupos com padrões de interação semelhantes) e estrutura hierárquica (grupos interagindo de maneira ordenada, onde as arestas fluem predominantemente de grupos de ranking superior para grupos de ranking inferior). As metodologias existentes geralmente abordam essas características isoladamente. Os Modelos de Blocos Estocásticos (SBMs) padrão recuperam grupos, mas não impõem uma ordem de bloco coerente, enquanto modelos de ranking ordenam nós individuais, mas falham em identificar grupos estruturalmente equivalentes. Essa separação corre o risco de impor ordenações estritas ao nível do nó onde existem apenas hierarquias ao nível de grupo, ou de falhar em detectar padrões hierárquicos dentro de dados agrupados. O artigo aborda a necessidade de um framework unificado que infira conjuntamente blocos ordenados e avalie se uma estrutura de bloco transitiva é sustentada pelos dados.

Metodologia: O Modelo de Blocos Estocásticos Transitivo (TSBM)
Os autores introduzem o Modelo de Blocos Estocásticos Transitivo (TSBM), um modelo bayesiano para redes direcionadas ponderadas. A metodologia baseia-se em cinco pilares fundamentais:

1. Decomposição de Volume/Direção: O modelo decompõe contagens de arestas direcionadas em dois componentes:

   • Volume: O volume total de interação não direcionada entre nós, modelado via uma matriz de intensidade simétrica e propensões de grau específicas por nó (seguindo o framework do SBM Corrigido pelo Grau).
   • Direção: A probabilidade de direção de interação condicional ao ocorrimento de uma interação. Essa separação permite que o modelo imponha hierarquia sobre o desequilíbrio direcional em vez da frequência de interação.

2. Priors Indutoras de Transitividade: O modelo impõe ordem sobre os blocos através de priors nas log-odds direcionais ($\psi$). Duas especificações são propostas:

   • Transitividade Estocástica Fraca (WST): Uma prior flexível que exclui padrões de dominância cíclica (ex: $A \succ B \succ C \succ A$) ao garantir que, se o bloco $k$ domina $\ell$ e $\ell$ domina $m$, então $k$ domina $m$. Isso é alcançado via priors gaussianas truncadas independentes nas log-odds do triângulo superior.
   • Transitividade Estocástica Forte (SST): Uma prior mais restritiva, especificamente uma versão SST de Toeplitz. Ela assume que a vantagem direcional aumenta com a separação de ranking (ou seja, a vantagem de um bloco de alto ranking sobre um de baixo ranking é maior do que sua vantagem sobre um de ranking médio). Isso é modelado assumindo que as log-odds dependem apenas da distância entre os blocos, com incrementos monótons impostos via uma soma cumulativa de incrementos positivos.

3. Prior de Partição Ordenada: Como os rótulos de blocos ordenados não são permutáveis (permutar rótulos altera a hierarquia e, portanto, a verossimilhança), as priors de partição permutáveis padrão não são adequadas. Os autores empregam uma prior de partição ordenada por idade (Donnelly e Tavaré, 1986; Donnelly e Joyce, 1991). Esta prior, originária da genética de populações, trata os blocos como surgindo sequencialmente no tempo (ou idade), permitindo a inferência conjunta do número de blocos e da alocação de nós sem a necessidade de MCMC de salto reversível (reversible-jump MCMC).

4. Inferência Posterior: A inferência é realizada via um amostrador de Gibbs parcialmente colapsado. Para lidar com a não-conjugação entre a verossimilhança logística das probabilidades direcionais e as priors gaussianas, os autores utilizam aumento de dados de Pólya-Gamma. Isso permite atualizações condicionais tratáveis para os parâmetros direcionais, parâmetros de volume e alocações de nós.

5. Seleção de Modelo: O framework utiliza Validação Cruzada Leave-One-Out (LOO-CV) via amostragem de importância suavizada por Pareto para comparar as variantes do TSBM contra o DC-SBM (SBM Corrigido pelo Grau) padrão.

Principais Contribuições

• Nova Formulação de Modelo: O TSBM é o primeiro modelo bayesiano a inferir conjuntamente equivalência estocástica e ordenação estocástica em redes direcionadas usando restrições de transitividade nas probabilidades de nível de bloco.
• Tractabilidade Computacional: Ao combinar o aumento de Pólya-Gamma com priors de partição ordenada por idade, os autores derivam um amostrador de Gibbs completo que evita métodos trans-dimensionais computacionalmente caros (como o reversible-jump) para estimar o número de blocos ordenados.
• Transitividade Flexível: A introdução de tanto WST quanto SST de Toeplitz permite que o modelo se adapte a diferentes níveis de rigor hierárquico, desde a simples aciclicidade até a dominância dependente de ranking.
• Capacidade Diagnóstica: O framework identifica explicitamente cenários onde impor ordem é prejudicial (ex: redes de citação não-transitivas), fornecendo um mecanismo probabilístico para avaliar a validade da suposição de transitividade.

Resultados

• Estudos de Simulação: Em redes esparsas com sinais direcionais fracos, o TSBM (tanto as variantes WST quanto SST) supera significativamente o DC-SBM padrão tanto em precisão preditiva (LOOIC) quanto em recuperação de partição (Variação de Informação). Em redes densas com sinais fortes, todos os modelos performam de forma semelhante. Crucialmente, em cenários de erro de especificação onde os dados contêm ciclos (não-transitivos), o DC-SBM supera o TSBM, demonstrando a capacidade do modelo de detectar quando a suposição de transitividade é inapropriada.
• Aplicações Empíricas: O modelo foi aplicado a seis redes direcionadas ponderadas (dominância animal, citações de periódicos e amizades escolares):
  • Dominância Animal: Nas redes de bighorn sheep, mountain goats e spotted hyenas, o TSBM geralmente melhorou o desempenho preditivo e gerou partições com estruturas hierárquicas mais claras e coerentes (menos arestas de retorno) comparadas ao DC-SBM.
  • Citações: Na rede de citações de periódicos de estatística, o DC-SBM performou melhor. Os autores observam que, embora existam gradientes de prestígio, os padrões de citação não são estritamente transitivos; assim, a prior ordenada restringiu o modelo desnecessariamente.
  • Macaques: Na rede de dominância de macacos, a hierarquia já era quase perfeita (quase uma ordenação estrita ao nível do nó). Aqui, o DC-SBM superou ligeiramente o TSBM, pois a regularização da prior ofereceu pouco benefício sobre o sinal forte já presente nos dados.
  • Amizades: Na rede de amizades de ensino médio, o TSBM recuperou uma ordenação de nível de bloco consistente com uma hierarquia global, enquanto o DC-SBM produziu uma partição refletindo estrutura de comunidade em vez de hierarquia.

Significância e Alegações
O artigo afirma que o TSBM fornece um framework probabilístico para estimar grupos ordenados e, importante, para avaliar quando uma estrutura de bloco transitiva é sustentada pelos dados. Os autores enfatizam que o valor do modelo reside não apenas em impor ordem, mas na modelagem conjunta de agrupamento e hierarquia, o que pode melhorar a inferência e a predição especificamente quando o sinal direcional é fraco ou a rede é esparsa. O trabalho também contribui para a estatística não-paramétrica bayesiana ao demonstrar a utilidade de priors de partição ordenada por idade em modelos de blocos latentes com rótulos não-permutáveis, uma combinação não utilizada anteriormente neste contexto. Os autores notam modestamente que o desempenho do modelo é contingente aos dados; em casos onde a estrutura subjacente é não-transitiva ou a hierarquia já é extremamente nítida, o DC-SBM não restringido pode continuar sendo preferível.