Ordering Stochastic Block Models via prior transitivity

Resumen Técnico: Ordenamiento de Modelos Estocásticos de Bloques mediante Transitividad de Prioris

Planteamiento del Problema
Las redes dirigidas suelen exhibir dos características estructurales simultáneas: estructura de comunidades (nodos que forman grupos con patrones de interacción similares) y estructura jerárquica (los grupos interactúan de manera ordenada, donde los bordes fluyen predominantemente de grupos de mayor rango a grupos de menor rango). Las metodologías existentes suelen abordar estas características de forma aislada. Los Modelos Estocásticos de Bloques (SBM) estándar recuperan grupos, pero no imponen un orden de bloques coherente, mientras que los modelos de clasificación ordenan nodos individuales pero no logran identificar grupos estructuralmente equivalentes. Esta separación conlleva el riesgo de imponer ordenamientos estrictos a nivel de nodo cuando solo existen jerarquías a nivel de grupo, o de no detectar patrones jerárquicos dentro de datos agrupados. El artículo aborda la necesidad de un marco unificado que infiera conjuntamente bloques ordenados y evalúe si una estructura de bloques transitiva está respaldada por los datos.

Metodología: El Modelo Estocástico de Bloques Transitivo (TSBM)
Los autores introducen el Modelo Estocástico de Bloques Transitivo (TSBM), un modelo bayesiano para redes dirigidas ponderadas. La metodología se basa en cinco pilares clave:

1. Descomposición de Volumen/Dirección: El modelo descompone los conteos de bordes dirigidos en dos componentes:

   • Volumen: El volumen total de interacción no dirigida entre nodos, modelado mediante una matriz de intensidad simétrica y propensiones de grado específicas de cada nodo (siguiendo el marco del SBM corregido por grado).
   • Dirección: La probabilidad de dirección de la interacción condicional a que ocurra una interacción. Esta separación permite al modelo imponer jerarquía sobre el desequilibrio direccional en lugar de la frecuencia de interacción.

2. Priors de Inducción de Transitividad: El modelo impone orden en los bloques mediante priors en los log-odds direccionales ($\psi$). Se proponen dos especificaciones:

   • Transitividad Estocástica Débil (WST): Un prior flexible que excluye patrones de dominancia cíclica (por ejemplo, $A \succ B \succ C \succ A$) asegurando que si el bloque $k$ domina a $\ell$ y $\ell$ domina a $m$, entonces $k$ domina a $m$. Esto se logra mediante priors gaussianos truncados independientes sobre los log-odds del triángulo superior.
   • Transitividad Estocástica Fuerte (SST): Un prior más restrictivo, específicamente una versión Toeplitz SST. Asume que la ventaja direccional aumenta con la separación de rango (es decir, la ventaja de un bloque de alto rango sobre uno de bajo rango es mayor que su ventaja sobre uno de rango medio). Esto se modela asumiendo que los log-odds dependen solo de la distancia entre bloques, con incrementos monótonos impuestos mediante una suma acumulativa de incrementos positivos.

3. Prior de Partición Ordenada: Dado que las etiquetas de bloques ordenadas no son intercambiables (permutar las etiquetas cambia la jerarquía y, por tanto, la verosimilitud), los priors de partición intercambiables estándar no son adecuados. Los autores emplean un prior de partición ordenada por edad (Donnelly y Tavaré, 1986; Donnelly y Joyce, 1991). Este prior, originario de la genética de poblaciones, trata los bloques como si aparecieran secuencialmente en el tiempo (o edad), permitiendo la inferencia conjunta del número de bloques y la asignación de nodos sin requerir MCMC de salto reversible (reversible-jump MCMC).

4. Inferencia Posterior: La inferencia se realiza mediante un muestreador de Gibbs parcialmente colapsado. Para manejar la no conjugación entre la verosimilitud logística de las probabilidades direccionales y los priors gaussianos, los autores utilizan la aumentación de datos de Pólya-Gamma. Esto permite actualizaciones condicionales tratables para los parámetros direccionales, los parámetros de volumen y las asignaciones de nodos.

5. Selección de Modelos: El marco utiliza la Validación Cruzada de Dejar Uno Fuera (LOO-CV) mediante el muestreo de importancia suavizado por Pareto para comparar las variantes del TSBM contra el DC-SBM (SBM corregido por grado) estándar.

Contribuciones Clave

• Formulación de Modelo Novedosa: El TSBM es el primer modelo bayesiano que infiere conjuntamente equivalencia estocástica y ordenamiento estocástico en redes dirigidas utilizando restricciones de transitividad en las probabilidades de bloque.
• Tractabilidad Computacional: Al combinar la aumentación de Pólya-Gamma con los priors de partición ordenados por edad, los autores derivan un muestreador de Gibbs completo que evita métodos trans-dimensionales costosos (como el salto reversible) para estimar el número de bloques ordenados.
• Transitividad Flexible: La introducción de tanto WST como Toeplitz SST permite al modelo adaptarse a diferentes niveles de rigurosidad jerárquica, desde la simple aciclicidad hasta la dominancia dependiente del rango.
• Capacidad Diagnóstica: El marco identifica explícitamente escenarios donde imponer orden es perjudicial (por ejemplo, redes de citas no transitivas), proporcionando un mecanismo probabilístico para evaluar la validez del supuesto de transitividad.

Resultados

• Estudios de Simulación: En redes dispersas con señales direccionales débiles, el TSBM (tanto las variantes WST como SST) supera significativamente al DC-SBM estándar tanto en precisión predictiva (LOOIC) como en recuperación de la partición (Variación de Información). En redes densas con señales fuertes, todos los modelos se comportan de manera similar. Crucialmente, en escenarios mal especificados donde los datos contienen ciclos (no transitivos), el DC-SBM supera al TSBM, demostrando la capacidad del modelo para detectar cuándo el supuesto de transitividad es inapropiado.
• Aplicaciones Empíricas: El modelo se aplicó a seis redes dirigidas ponderadas (dominancia animal, citas de revistas y amistades escolares):
  • Dominancia Animal: En las redes de bighorn sheep, mountain goats y spotted hyenas, el TSBM generalmente mejoró el rendimiento predictivo y produjo particiones con estructuras jerárquicas más claras y coherentes (menos bordes hacia atrás) en comparación con el DC-SBM.
  • Citas: En la red de citas de la revista de estadística, el DC-SBM funcionó mejor. Los autores señalan que, aunque existen gradientes de prestigio, los patrones de citación no son estrictamente transitivos; por lo tanto, el prior ordenado constriñó el modelo innecesariamente.
  • Macaque: En la red de dominancia de los macacos, la jerarquía ya era casi perfecta (casi un ordenamiento estricto a nivel de nodo). Aquí, el DC-SBM superó ligeramente al TSBM, ya que la regularización del prior ofreció poco beneficio sobre la señal fuerte ya presente en los datos.
  • Amistades: En la red de amistades de una escuela secundaria, el TSBM recuperó un ordenamiento de bloque consistente con una jerarquía global, mientras que el DC-SBM produjo una partición que reflejaba la estructura de comunidad en lugar de la jerarquía.

Significancia y Reivindicaciones
El artículo afirma que el TSBM proporciona un marco probabilístico para estimar grupos ordenados y, lo que es más importante, para evaluar cuándo un esquema de bloques transitivo está respaldado por los datos. Los autores enfatizan que el valor del modelo reside no solo en imponer orden, sino en el modelado conjunto de agrupación y jerarquía, lo que puede mejorar la inferencia y la predicción específicamente cuando la señal direccional es débil o la red es dispersa. El trabajo también contribuye a la estadística bayesiana no paramétrica al demostrar la utilidad de los priors de partición ordenados por edad en modelos de bloques latentes con etiquetas no intercambiables, una combinación que no se había utilizado previamente en este contexto. Los autores señalan modestamente que el rendimiento del modelo depende de los datos; en casos donde la estructura subyacente es no transitiva o la jerarquía es ya extremadamente nítida, el DC-SBM no restringido puede seguir siendo preferible.