Ordering Stochastic Block Models via prior transitivity

Résumé Technique : Ordonnancement des Modèles Stochastiques de Blocs par Transitivité de Priorité

Énoncé du Problème
Les réseaux dirigés présentent souvent deux caractéristiques structurelles simultanées : une structure de communauté (les nœuds formant des groupes avec des schémas d'interaction similaires) et une structure hiérarchique (les groupes interagissant de manière ordonnée, où les liens circulent principalement des groupes de rang supérieur vers les groupes de rang inférieur). Les méthodologies existantes traitent généralement ces caractéristiques de manière isolée. Les modèles stochastiques de blocs (SBM) standards récupèrent les groupes mais n'imposent pas un ordre de bloc cohérent, tandis que les modèles de classement ordonnent les nœuds individuels mais échouent à identifier des groupes structurellement équivalents. Cette séparation risque d'imposer des ordonnancements de nœuds stricts là où seuls des hiérarchies de groupe existent, ou de ne pas détecter les motifs hiérarchiques au sein de données regroupées. L'article répond au besoin d'un cadre unifié qui infère conjointement des blocs ordonnés et évalue si une structure de blocs transitive est soutenue par les données.

Méthodologie : Le Modèle Stochastique de Blocs Transitif (TSBM)
Les auteurs introduisent le Modèle Stochastique de Blocs Transitif (TSBM), un modèle bayésien pour les réseaux dirigés pondérés. La méthodologie repose sur cinq piliers clés :

1. Décomposition Volume/Direction : Le modèle décompose les comptes d'arêtes dirigées en deux composantes :

   • Volume : Le volume total d'interactions non dirigées entre les nœuds, modélisé via une matrice d'intensité symétrique et des propensions de degré spécifiques aux nœuds (suivant le cadre du DC-SBM - Modèle Stochastique de Blocs Corrigé selon le Degré).
   • Direction : La probabilité de la direction de l'interaction conditionnellement à une interaction survenant. Cette séparation permet au modèle d'imposer une hiérarchie sur le déséquilibre directionnel plutôt que sur la fréquence d'interaction.

2. Priors Induisant la Transitivité : Le modèle impose un ordre sur les blocs par des priors sur les log-odds directionnels ($\psi$). Deux spécifications sont proposées :

   • Transitivité Stochastique Faible (WST) : Un prior flexible qui exclut les schémas de dominance cycliques (par exemple, $A \succ B \succ C \succ A$) en garantissant que si le bloc $k$ domine $\ell$ et $\ell$ domine $m$, alors $k$ domine $m$. Ceci est réalisé via des priors gaussiens tronqués indépendants sur les log-odds de la partie supérieure de la matrice.
   • Transitivité Stochastique Forte (SST) : Un prior plus restrictif, spécifiquement une version SST de Toeplitz. Elle suppose que l'avantage directionnel augmente avec la séparation des rangs (c'est-à-dire que l'avantage d'un bloc de rang élevé sur un bloc de rang bas est supérieur à son avantage sur un bloc de rang moyen). Ceci est modélisé en supposant que les log-odds dépendent uniquement de la distance entre les blocs, avec des incréments monotones imposés via une somme cumulée d'incréments positifs.

3. Prior de Partition Ordonnée : Puisque les étiquettes de blocs ordonnées ne sont pas échangeables (permuter les étiquettes change la hiérarchie et donc la vraisemblance), les priors de partition échangeables standards ne sont pas appropriés. Les auteurs emploient un prior de partition ordonné par l'âge (Donnelly et Tavaré, 1986 ; Donnelly et Joyce, 1991). Ce prior, issu de la génétique des populations, traite les blocs comme apparaissant séquentiellement dans le temps (ou l'âge), permettant l'inférence conjointe du nombre de blocs et de l'allocation des nœuds sans nécessiter de MCMC de type saut réversible (reversible-jump).

4. Inférence Postérieure : L'inférence est réalisée via un échantillonneur de Gibbs partiellement réduit. Pour gérer la non-conjugaison entre la vraisemblance logistique des probabilités directionnelles et les priors gausiens, les auteurs utilisent l'augmentation de données de Pólya-Gamma. Cela permet des mises à jour conditionnelles tractables pour les paramètres directionnels, les paramètres de volume et les allocations de nœuds.

5. Sélection de Modèle : Le cadre utilise la validation croisée "Leave-One-Out" (LOO-CV) via l'échantillonnage d'importance lissé par Pareto pour comparer les variantes du TSBM au DC-SBM standard.

Contributions Clés

• Nouvelle Formulation de Modèle : Le TSBM est le premier modèle bayésien qui infère conjointement l'équivalence stochastique et l'ordonnancement stochastique dans les réseaux dirigés en utilisant des contraintes de transitivité sur les probabilités de bloc.
• Tractabilité Computationnelle : En combinant l'augmentation de Pólya-Gamma avec des priors de partition ordonnés par l'âge, les auteurs dérivent un échantillonneur de Gibbs complet qui évite les méthodes trans-dimensionnelles coûteuses (comme le reversible-jump) pour estimer le nombre de blocs ordonnés.
• Transitivité Flexible : L'introduction de la WST et de la SST de Toeplitz permet au modèle de s'adapter à différents niveaux de rigueur hiérarchique, de la simple acyclicité à la dominance dépendante du rang.
• Capacité Diagnostique : Le cadre identifie explicitement les scénarios où imposer un ordre est préjudiciable (par exemple, les réseaux de citations non transitifs), fournissant un mécanisme probabiliste pour évaluer la validité de l'hypothèse de transitivité.

Résultats

• Études de Simulation : Dans les réseaux creux avec des signaux directionnels faibles, le TSBM (versions WST et SST) surpasse significativement le DC-SBM standard tant en précision prédictive (LOOIC) qu'en récupération de partition (Variation de l'Information). Dans les réseaux denses avec des signaux forts, tous les modèles se comportent de manière similaire. Crucialement, dans les scénarios mal spécifiés contenant des cycles (non-transitifs), le DC-SBM surpasse le TSBM, démontrant la capacité du modèle à détecter quand l'hypothèse de transitivité est inappropriée.
• Applications Empiriques : Le modèle a été appliqué à six réseaux dirigés pondérés (dominance animale, citations de revues et amitiés scolaires) :
  • Dominance Animale : Dans les réseaux de mouflons, de chèvres de montagne et de hyènes tachetées, le TSBM améliore généralement la performance prédictive et produit des partitions avec des structures hiérarchiques plus claires et plus cohérentes (moins d'arêtes de retour) par rapport au DC-SBM.
  • Citations : Dans le réseau de citations de revues de statistiques, le DC-SBM a été plus performant. Les auteurs notent que bien que des gradients de prestige existent, les schémas de citation ne sont pas strictement transitifs ; ainsi, le prior ordonné a contraint le modèle inutilement.
  • Macaques : Dans le réseau de dominance des macaques, la hiérarchie était déjà presque parfaite (presque un ordonnancement strict au niveau du nœud). Ici, le DC-SBM a légèrement mieux performé que le TSBM, car la régularisation du prior offrait peu de bénéfice par rapport au signal fort déjà présent dans les données.
  • Amitiés : Dans le réseau d'amitié au lycée, le TSBM a récupéré un ordonnancement par bloc cohérent avec une hiérarchie globale, tandis que le DC-SBM a produit une partition reflétant une structure de communauté plutôt qu'une hiérarchie.

Signification et Revendications
L'article affirme que le TSBM fournit un cadre probabiliste pour estimer des groupes ordonnés et, surtout, pour évaluer si une structure de blocs transitive est soutenue par les données. Les auteurs soulignent que la valeur du modèle réside non seulement dans l'imposition de l'ordre, mais aussi dans la modélisation conjointe du regroupement et de la hiérarchie, ce qui peut améliorer l'inférence et la prédiction spécifiquement lorsque le signal directionnel est faible ou que le réseau est creux. Ce travail contribue également aux statistiques bayésiennes non paramétriques en démontrant l'utilité des priors de partition ordonnés par l'âge dans les modèles de blocs latents, une combinaison qui n'avait pas été utilisée auparavant dans ce contexte. Les auteurs notent modestement que la performance de leur modèle est contingente sur les données ; dans les cas où la structure sous-jacente est non-transitive ou si la hiérarchie est déjà extrêmement nette, le DC-SBM non contraint peut rester préférable.