Simultaneous global and local clustering in multiplex networks with covariate information

Technische Samenvatting: Gelijktijdige Globale en Lokale Clustering in Multiplex Netwerken met Covariaat-informatie

Probleemstelling
Moderne netwerkdata bevatten vaak meerdere typen interacties tussen dezelfde set entiteiten, vertegenwoordigd als multiplex netwerken. Een kritieke uitdaging bij het analyseren van dergelijke data is de gelijktijdige detectie van twee verschillende soorten gemeenschapsstructuren:

1. Lokale (laagspecifieke) Clustering: Het identificeren van groepen knooppunten die dicht met elkaar interageren binnen een specifieke laag (interactietype).
2. Globale Clustering: Het identificeren van een verenigde groepering van knooppunten die standhoudt over alle lagen heen, wat een overkoepelende structurele rol weerspiegelt.

Bestaande literatuur heeft zich grotendeels gericht op ofwel laag-clustering ofwel globale clustering in isolatie, of heeft een bekend, eindig aantal gemeenschappen verondersteld. Weinig methoden integreren nodale covariaat-informatie (metadata) om het clusteringproces te sturen, terwijl ze tegelijkertijd een onbekend en potentieel oneindig aantal gemeenschappen mogelijk maken. Dit artikel adresseert de methodologische kloof in het vermogen om hiërarchische clustering (globaal en lokaal) in multiplex netwerken uit te voeren, terwijl covariaten worden geïntegreerd en een onbekend aantal groepen wordt afgehandeld.

Methodologie: Het Hiërarchische Multiplex Stochastic Blockmodel (HMPSBM)
De auteurs stellen het Hierarchical Multiplex Stochastic Blockmodel (HMPSBM) voor, een Bayesiaans non-parametrisch model dat zowel globale knoop-lidmaatschappen als laagspecifieke lidmaatschappen gelijktijdig afleidt.

• Modelstructuur:

  • Globale Toewijzing: Elk knooppunt $i$ wordt toegewezen aan een globale groep $w_i$. De waarschijnlijkheid van deze toewijzing, $\tau_i$, wordt geconstrueerd met behulp van een probit stick-breaking proces dat wordt gedreven door nodale covariaten $x_i$. Dit maakt het model in staat om te leren hoe kenmerken de globale groepslidmaatschap beïnvloeden.
  • Lokale Toewijzing: Voorwaardelijk op de globale groep $w_i$, wordt elk knooppunt toegewezen aan een laagspecifieke groep $z_{\ell i}$ voor elke laag $\ell$. Deze toewijzingen worden beheerst door knooppuntspecifieke mengverhoudingen afgeleid van gedeelde Griffiths-Engen-McCloskey (GEM) distributies.
  • Connectiviteit: Binnen elke laag volgen verbindingen een Stochastic Blockmodel (SBM). De waarschijnlijkheid van een verbinding tussen knooppunten $i$ en $j$ in laag $\ell$ hangt af van hun laagspecifieke groepslidmaatschappen.
  • Non-parametrische Priors: Het model maakt gebruik van een non-parametrisch framework (specifiek gebruikmakend van GEM-distributies en stick-breaking representaties) om een onbekend (effectief oneindig) aantal globale en laag-niveau gemeenschappen toe te staan, waarbij de geschikte complexiteit automatisch wordt geselecteerd in plaats van vooraf vast te leggen.

• Inference Procedure:

  • Vanwege de complexiteit van de posterieure distributie stellen de auteurs een Variational Bayesian (VB) inference procedure voor met behulp van Coordinate Ascent Variational Inference (CAVI).
  • De aanpak maakt gebruik van een mean-field benadering waarbij de posterieure verdeling is gefactoriseerd over modelparameters.
  • Om de oneindig-dimensionale aard van het probleem te behandelen, introduceren de auteurs truncatieparameters ($M_w$ voor globale groepen en $M_z$ voor laag-groepen).
  • Het algoritme bevat specifieke updates voor de stick-breaking variabelen en gebruikt gradiënt-ascent (het Adam-algoritme) voor parameters die geen gesloten vorm hebben voor hun conditionele distributies (specifiek de regressiecoëfficiënten die de link leggen tussen covariaten en globale groepswaarrscheinlichheden).
  • Initialisatie: De methode maakt gebruik van een geïnformeerd initialisatieschema met behulp van spectrale embedding (SVD) en HDBSCAN om de laag-niveau groepen te zaaien, gevolgd door een her-enumeratiestap om consistentie tussen de lagen te waarborgen.

Belangrijkste Bijdragen

1. Gelijktijdige Hiërarchische Clustering: Het artikel introduceert de eerste methodologie die gelijktijdig een globale clustering van knooppunten en laagspecifieke clusteringen binnen een multiplex netwerk afleidt, waarbij heterogene clusteringpatronen over lagen heen mogelijk zijn.
2. Integratie van Covariaten: Het model integreert nodale covariaat-informatie direct in het globale clusteringmechanisme via een probit stick-breaking proces, waardoor de vorming van globale groepen wordt gestuurd door knooppuntskenmerken.
3. Non-parametrische Flexibiliteit: In tegen tegenstelling tot veel bestaande multiplex SBM's die een vooraf gespecificeerd aantal gemeenschappen vereisen, staat HMPSBM een onbekend (effectief oneindig) aantal globale en laag-niveau groepen toe, waarbij de geschikte complexiteit automatisch wordt gekozen.
4. Schaalbare Inference: De auteurs ontwikkelen een schaalbaar variational inference algoritme met paralleliseerbare updates, waardoor de aanpak toepasbaar is op grote netwerken waar Markov Chain Monte Carlo (MCMC) methoden computationeel te kostbaar zouden zijn.

Resultaten
De prestaties van de HMPSBM werden geëvalueerd via uitgebreide simulatiestudies en een real-world toepassing:

• Simulatiestudies:

  • Herstel van Groepsaantallen: Het model slaagde erin het ware aantal globale en laag-niveau groepen te herstellen wanneer de truncatieparameters voldoende groot waren.
  • Covariaat vs. Netwerkstructuur: In scenario's waar nodale covariaten minder informatief werden (afnemende scheiding), herstelde het model nog steeds accuraat de globale groepen, wat aantoont dat de netwerkstructuur de primaire drijfveer is voor clustering, waarbij covariaten dienen als een aanvullend signaal.
  • Robuustheid tegenover Initialisatie: Hoewel geïnformeerde initialisatie een iets betere convergentie opleverde, toonde het model robuustheid door in de meeste gevallen te convergeren naar vergelijkbare oplossingen, zelfs met willekeurige initialisatie.
  • Schaalbaarheid: De prestaties (gemeten via Normalized Mutual Information, NMI) verbeterden met een toenemend aantal lagen en netwerkomvang, vooral in settings met een zwakke connectiviteits-scheiding.

• Real-World Applicatie (FAO Handelsnetwerk):

  • Het model werd toegepast op een multiplex netwerk van wereldwijde voedselhandel (214 landen, 314 voedseltypen), gereduceerd tot 177 knooppunten en 20 lagen.
  • Met behulp van covariaten zoals BBP en landoppervlak identificeerde het model 11 globale groepen en 6 laag-niveau groepen.
  • Interpretabiliteit: De afgeleide globale groepen kwamen overeen met economische intuïtie. Zo bestond één groep uit grote wereldwijde handelsmachten (VS, China, VK, Duitsland, etc.), terwijl een andere groep opkomende economieën en regionale machten groepeerde. Een duidelijke cluster van Syrië en Iran werd geïdentificeerd, wat hun specifieke handelsrelaties reflecteerde vóór de Syrische Revolutie van 2011.
  • Impact van Covariaten: Het toevoegen van verdere covariaten (stedelijk landoppervlak, kustlengte) verfijnde de periferie van de clusters (bijv. het verplaatsen van kust-/eilandstaten), maar liet de kernstructuur van de grote economieën ongewijzigd, wat de bevinding bevestigt dat de netwerkstructuur de dominante factor is.

Betekenis en Claims
Het artikel claimt dat de HMPSBM een kritieke methodologische kloof vult door een verenigd framework te bieden voor hiërarchische clustering in multiplex netwerken dat zowel onbekende gemeenschapsgroottes als nodale covariaten accommodeert. De auteurs stellen dat hun variational inference aanpak een computationeel efficiënt alternatief biedt voor MCMC voor grootschalige netwerken.

De betekenis van het werk ligt in het vermogen om latente structuren te onthullen die niet zichtbaar zijn bij het analyseren van lagen in isolatie of het negeren van metadata. De toepassing op het FAO-handelsnetwerk toont aan dat het model economisch betekenisvolle groeperingen kan onthullen die zowel handelspatronen als geopolitieke/economische kenmerken weerspiegelen. De auteurs merken bescheiden op dat hoewel het model ervan uitgaat dat knooppunten in alle lagen aanwezig zijn en covariaten volledig geobserveerd zijn, het huidige framework er succesvol in slaagt om structurele en kenmerkgebaseerde informatie te balanceren om interpreteerbare en accurate clusteringresultaten te produceren.