Ordering Stochastic Block Models via prior transitivity

Technische Samenvatting: Ordenen van Stochastic Block Models via Prior Transitiviteit

Probleemstelling
Gerichte netwerken vertonen vaak twee gelijktijdige structurele kenmerken: gemeenschapsstructuur (knopen die groepen vormen met vergelijkbare interactiepatronen) en hiërarchische structuur (groepen die op een geordende manier interageren, waarbij randen voornamelijk van hoger geplaatste naar lager geplaatste groepen stromen). Bestaande methodologieën behandelen deze kenmerken doorgaans in isolatie. Standaard Stochastic Block Models (SBMs) herstellen groepen, maar dwingen geen coherente blokordening af, terwijl ordeningsmodellen individuele knopen ordenen, maar er niet in slagen om structureel equivalente groepen te identificeren. Deze scheiding brengt het risico met zich mee dat er strikte knoop-niveau ordeningen worden afgedwongen waar alleen groep-niveau hiërarchieën bestaan, of dat het niet lukt om hiërarchische patronen binnen geclusterde data te detecteren. Dit artikel adresseert de behoefte aan een verenigd framework dat zowel geordende blokken afleidt als beoordeelt of een transitieve blokstructuur door de data wordt ondersteund.

Methodologie: Het Transitive Stochastic Block Model (TSBM)
De auteurs introduceren het Transitive Stochastic Block Model (TSBM), een Bayesiaans model voor gerichte gewogen netwerken. De methodologie rust op vijf kernzuilen:

1. Volume/Richting Decompositie: Het model deelt gerichte rand-aantallen op in twee componenten:

   • Volume: Het totale ongerichte interactievolume tussen knopen, gemodelleerd via een symmetrische intensiteitsmatrix en knoop-specifieke graad-propensiteiten (volgens het Degree-Corrected SBM-framework).
   • Richting: De waarschijnlijkheid van de interactierichting voorwaardelijk op het plaatsvinden van een interactie. Deze scheiding maakt het mogelijk om hiërarchie op te leggen aan directionele onbalans in plaats van aan de frequentie van interactie.

2. Transitiviteit-inducerende Priors: Het model legt orde op aan blokken via priors op de directionele log-odds ($\psi$). Twee specificaties worden voorgesteld:

   • Weak Stochastic Transitivity (WST): Een flexibele prior die cyclische dominantiepatronen (bijv. $A \succ B \succ C \succ A$) uitsluit door te garanderen dat als blok $k$ domineert over $\ell$ en $\ell$ domineert over $m$, dan ook $k$ domineert over $m$. Dit wordt bereikt via onafhankelijke afgekappende Gaussische priors op de bovendriehoekige log-odds.
   • Strong Stochastic Transitivity (SST): Een restrictievere prior, specifiek een Toeplitz SST versie. Deze gaat ervan uit dat het directionele voordeel toeneemt met de rangafstand (dat wil zeggen, het voordeel van een hooggeplaatste blok over een laaggeplaatste blok is groter dan zijn voordeel over een middengeplaatste blok). Dit wordt gemodelleerd door aan te nemen dat de log-odds enkel afhangen van de afstand tussen blokken, waarbij monotone incrementen worden afgedwongen via een cumulatieve som van positieve incrementen.

3. Geordende Partitie Prior: Omdat geordende bloklabels niet uitwisselbaar zijn (het permuteren van labels verandert de hiërarchie en daarmee de likelihood), zijn standaard uitwisselbare partitie-priors ongeschikt. De auteurs gebruiken een leeftijd-geordende partitie prior (Donnelly en Tavaré, 1986; Donnelly en Joyce, 1991). Deze prior, oorspronkelijk afkomstig uit de populatiegenetica, behandelt blokken alsof ze sequentieel in de tijd (of leeftijd) verschijnen, wat de gezamenlijke inferentie van het aantal blokken en de knoop-allocatie mogelijk maakt zonder dat een reversible-jump MCMC vereist is.

4. Posterior Inferentie: Inferentie wordt uitgevoerd via een gedeeltelijk gecollapseerde Gibbs sampler. Om de niet-conjugaliteit tussen de logistische likelihood van directionele waarschijnlijkheden en Gaussische priors te behandelen, maken de auteurs gebruik van Pólya-Gamma data-augmentatie. Dit maakt tractabele conditionele updates mogelijk voor de directionele parameters, volume-parameters en knoop-allocaties.

5. Modelselectie: Het framework gebruikt Leave-One-Out Cross-Validation (LOO-CV) via Pareto-smoothed importance sampling om de TSBM-varianten te vergelijken met de standaard Degree-Corrected SBM (DC-SBM).

Belangrijkste Bijdragen

• Nieuwe Modelformulering: De TSBM is het eerste Bayesiaanse model dat gezamenlijk stochastische equivalentie en stochastische ordening in gerichte netwerken afleidt door middel van transitiviteitsrestricties op blok-niveau waarschijnlijkheden.
• Computationele Tractabiliteit: Door de combinatie van Pólya-Gamma augmentatie met leeftijd-geordende partitie-priors leiden de auteurs een volledige Gibbs sampler af die trans-dimensionale methoden (zoals reversible-jump) vermijdt voor het schatten van het aantal geordende blokken.
• Flexibele Transitiviteit: De introductie van zowel WST als Toeplitz SST stelt het model in staat om zich aan te passen aan verschillende niveaus van hiërarchische striktheid, van eenvoudige acycliciteit tot rang-afhankelijke dominantie.
• Diagnostische Capaciteit: Het framework identificeert expliciet scenario's waarin het opleggen van orde nadelig is (bijv. niet-transitieve citatienetwerken), en biedt een probabilistisch mechanisme om de geldigheid van de transitiviteitsveronderstelling te beoordelen.

Resultaten

• Simulatiestudies: In ijle netwerken met zwakke directionele signalen presteert de TSBM (zowel de WST als de SST varianten) significant beter dan de standaard DC-SBM in zowel voorspellende nauwkeurigheid (LOOIC) als partitie-herstel (Variation of Information). In dichte netwerken met sterke signalen presteren alle modellen vergelijkbaar. Cruciaal is dat in gespecificeerde scenario's waar de data cycli bevat (niet-transitief), de DC-SBM beter presteert dan de TSBM, wat de capaciteit van het model aantoont om te detecteren wanneer de transitiviteitsveronderstelling ongepast is.
• Empirische Toepassingen: Het model werd toegepast op zes gerichte gewogen netwerken (dierlijke dominantie, tijdschriftcitaties en schoolvriendschappen):
  • Dierlijke Dominantie: In netwerken van bighorn schapen, berggoeien en gevlekte hyena's verbeterde de TSBM over het algemeen de voorspellende prestaties en leverde het partities op met duidelijkere, meer coherente hiërarchische structuren (minder achterwaartse randen) vergeleken met de DC-SBM.
  • Citatie: In het citatienetwerk van statistiek-tijdschriften presteerde de DC-SBM beter. De auteurs merken op dat hoewel er prestige-gradiënten bestaan, de citatiepatronen niet strikt transitief zijn; de geordende prior beperkte het model hierdoor onnodig.
  • Macaques: In het dominantienetwerk van macroques was de hiërarchie al bijna perfect (bijna een strikte knoop-niveau ordening). Hier presteerde de DC-SBM licht beter dan de TSBM, omdat de regularisatie van de prior weinig voordeel bood boven het sterke signaal dat al in de data aanwezig was.
  • Vriendschap: In het netwerk van hoge schoolvriendschappen herstelde de TSBM een blok-niveau ordening die consistent was met een globale hiërarchie, terwijl de DC-Sism een partitie produceerde die de gemeenschapsstructuur weerspiegelde in plaats van de hiërarchie.

Betekenis en Claims
Het artikel claimt dat de TSBM een probabilistisch framework biedt voor het schatten van geordende groepen en, belangrijker nog, voor het beoordelen wanneer een transitieve blokstructuur door de data wordt ondersteund. De auteurs benadrukken dat de waarde van het model niet alleen ligt in het afdwingen van orde, maar in de gezamenlijke modellering van groepering en hiërarchie, wat de inferentie en voorspelling kan verbeteren, specif