Bridging Maximum Likelihood and Optimal Transport for Efficient Inference and Model Selection in Stochastic Block Models

Technische Samenvatting: Het Overbruggen van Maximum Likelihood en Optimaal Transport voor Efficiënte Inference en Modelselectie in Stochastische Blokkenmodellen

Probleemstelling
Het artikel adresseert de uitdaging van inference en modelselectie in Stochastische Blokkenmodellen (SBM's), een generatief kader voor willekeurige grafen waarbij knopen zijn opgedeeld in verborgen clusters en de kansen op randen afhangen van het clusterlidmaatschap. Hoewel SBM's voordelen bieden ten opzichte van alternatieve clusteringmethoden (zoals modulariteitsmaximalisatie of spectrale clustering) door het herstellen van diverse structuren en het verschaffen van hulpmiddelen voor het schatten van het aantal clusters, vertrouwt standaard inference vaak op Variational Expectation-Maximization (VEM). Een kritieke beperking van VEM is de afhankelijkheid van entropische regularisatie om optimalisatiegladheid te waarborgen. Deze regularisatie verhindert dat transportplannen spaarzaam worden, waardoor "intrinsieke modelselectie" wordt gehinderd—het vermogen om onnodige clusters automatisch te deactiveren (hen nul massa toekennen) binnen één optimalisatieprobleem. Bijgevolg vereisen huidige benaderingen vaak computatief dure roosterzoekopdrachten of heuristische procedures om het optimale aantal clusters ($K$) te bepalen.

Methodologie
De auteurs stellen een nieuw kader voor dat Maximum Likelihood Variational Inference (MLVI) in SBM's interpreteert door de lens van Optimaal Transport (OT), met name gebruikmakend van de Semi-Relaxed Gromov-Wasserstein (srGW) divergentie.

1. Hervorming als srGW: Het artikel stelt vast dat de ELBO (Evidence Lower Bound) maximalisatie in SBM equivalent is aan het minimaliseren van een srGW-divergentie met een entropische regularisatieterm. De verliesfunctie komt overeen met de negatieve log-likelihood van het generatieve model.
2. Niet-geregulariseerde Schatters: Erkennend dat entropische regularisatie spaarzaamheid verhindert, onderzoeken de auteurs niet-geregulariseerde srGW-schatters. Zij definiëren schatters voor de connectiviteitsmatrix ($\Theta$) en het transportplan ($T$, dat clustertoewijzingen vertegenwoordigt) door de srGW-verliesfunctie te minimaliseren zonder de entropieterm.
3. Spaarzaamheidsbevorderende Regularisatie voor Modelselectie: Om automatische modelselectie (het schatten van $K$) mogelijk te maken zonder roosterzoekopdracht, introduceren de auteurs een $\ell_{1/2}$-pseudonormstraf op het transportplan. Deze straf moedigt de geschatte clusterproporties aan om spaarzaam te zijn, waardoor effectief de massa van niet-optimale clusters op nul wordt gesteld.
4. Optimalisatie: De parameters worden geschat met behulp van een Block Coordinate Descent-algoritme. Dit wisselt af tussen:
   • Het updaten van de connectiviteitsmatrix $\Theta$ met behulp van gesloten-vormoplossingen afgeleid uit de optimaliteitsvoorwaarden van de eerste orde.
   • Het updaten van het transportplan $T$ met behulp van een Majorization-Minimization (MM)-algoritme, dat de spaarzaamheidsstraf lineariseert en het resulterende kwadratische probleem oplost (bijvoorbeeld via Frank-Wolfe).

Belangrijkste Bijdragen

• Theoretisch Verband: Het artikel bewijst dat MLVI in SBM's kan worden geïnterpreteerd als een semi-gelaxeerde Gromov-Wasserstein-projectie met entropische regularisatie.
• Consistentieresultaten: De auteurs bewijzen dat de niet-geregulariseerde srGW-schatters consistent zowel de ware SBM-connectiviteitsmatrix als de latente clustertoewijzingen herstellen in het asymptotische regime ($N \to \infty$).
• Automatische Modelselectie: Door het opnemen van een spaarzaamheidsbevorderende straf, staat de methode toe om modelparameters en het aantal clusters gelijktijdig te herstellen in één optimalisatiestap. Dit vermijdt de noodzaak van kostbare roosterzoekopdrachten of hebberige heuristieken.
• Algoritmische Efficiëntie: De voorgestelde solver is ontworpen voor efficiëntie, met een theoretische complexiteit die wordt gedomineerd door gradientberekening ($O(N^2K + K^2N)$), en blijkt aanzienlijk sneller op CPU's te zijn dan state-of-the-art variational schatters.

Resultaten
De auteurs evalueren hun aanpak op synthetische data gegenereerd uit Bernoulli SBM's onder drie connectiviteitsregimes: Assortatief, Hub en Disassortatief.

• Clusteringprestaties: De voorgestelde srGW-schatter met een negatieve log-likelihood-verliesfunctie (srGW-NLL) presteert consistent beter dan of gelijk aan state-of-the-art baselines (waaronder Louvain, Infomap, Greed en Variational Estimators) wat betreft de Adjusted Rand Index (ARI), met name in Hub- en Disassortatieve regimes waar structurele aannames van andere methoden worden geschonden.
• Modelselectie: De methode herstelt succesvol het ware aantal clusters ($K^*$) over verschillende hyperparameterinstellingen heen, waarbij een plateau in prestaties wordt aangetoond wanneer de spaarzaamheidsparameter op de juiste wijze wordt afgestemd.
• Efficiëntie: De srGW-NLL-methode wordt gerapporteerd als 1 tot 2 ordes van grootte sneller op CPU dan de Variational Estimator- en Greed-methoden, voornamelijk omdat het de iteratieve modelselectielussen omzeilt die door die benaderingen vereist worden.

Betekenis en Claims
Het artikel claimt een unificerend theoretisch en praktisch brug te slaan tussen Optimaal Transport en Stochastische Blokkenmodellen. De primaire betekenis ligt in het aantonen dat OT-gebaseerde schatters niet alleen consistent zijn voor parameterherstel, maar ook intrinsieke modelselectie kunnen uitvoeren door spaarzaamheidsbevordering. Dit biedt een computatief efficiënt alternatief voor traditionele op likelihood gebaseerde methoden die worstelen met de combinatorische complexiteit van het selecteren van het aantal clusters. De auteurs positioneren hun werk als een stap naar robuustere en efficiëntere grafpartitie, met name in scenario's waarbij het aantal gemeenschappen onbekend is en de grafstructuur complex is (bijvoorbeeld met hubs of disassortatieve patronen). Zij merken op dat hoewel de asymptotische consistentie is bewezen, het afstemmen van de spaarzaamheidshyperparameter een gebied blijft voor toekomstig onderzoek, en de prestaties van de methode op real-world netwerken onderwerp is voor verder studie.