Network Cross-Validation and Model Selection via Subsampling

Deze paper introduceert NETCROP, een efficiënte en nauwkeurige methode voor cross-validatie en modelselectie in complexe netwerken door het gebruik van overlappende subnetwerken.

De kern

Samenvatting van het papier: NETCROP – De Slimme Netwerk-Test

Stel je voor dat je een enorme, ingewikkelde stad hebt met miljoenen mensen (de punten of nodes) en duizenden wegen die hen verbinden (de lijnen of edges). Dit noemen we een netwerk. Wetenschappers gebruiken dit om alles te modelleren: van vriendschappen op sociale media tot hoe een virus zich verspreidt.

Om deze steden te begrijpen, gebruiken we wiskundige modellen. Maar hier zit een probleem: Hoe weet je welk model het beste werkt?

In de gewone wereld (zoals bij het voorspellen van weer of huisprijzen) gebruiken we een trucje genaamd Cross-Validation. Je neemt je data, verdeelt het in twee delen: één deel om te leren (trainen) en één deel om te testen. Als je model de test goed doet, is het goed.

Het probleem met netwerken:
Bij netwerken werkt deze truc niet zomaar. Je hebt maar één stad. Als je een deel van de wegen weghaalt om te testen, verandert de hele structuur van de stad. Het is alsof je een puzzel probeert op te lossen, maar je mag alleen kijken naar de randen en niet naar het midden. Bestaande methoden zijn vaak traag, onnauwkeurig of vereisen dat je de hele stad in je hoofd moet houden, wat onmogelijk is bij grote netwerken.

De oplossing: NETCROP
De auteurs van dit papier hebben een nieuwe, slimme methode bedacht genaamd NETCROP. Laten we het uitleggen met een analogie.

De "Deel-Steden" Analogie

Stel je voor dat je een gigantische stad hebt en je wilt weten of je een goede kaart (een model) hebt om de straten te beschrijven.

1. De Oude Manier (NCV & ECV):

   • NCV is alsof je de stad in grote stukken snijdt, maar je moet steeds de hele stad bekijken om te zien hoe de stukken passen. Dit is extreem traag en zwaar voor je computer.
   • ECV is alsof je een paar willekeurige straten weghaalt en probeert ze later weer in te vullen met giswerk. Dit werkt vaak niet goed als de stad te complex is, en het kan leiden tot fouten (overfitting).

2. De Nieuwe Manier (NETCROP):
   NETCROP werkt als een slimme delegatie van onderzoekers.

   • Stap 1: De Overlap (De Gemeenschappelijke Basis). Je kiest een groep mensen (bijvoorbeeld de inwoners van het centrum) die in alle groepen zitten. Laten we dit de "Overlap" noemen.
   • Stap 2: De Subnetwerken (De Deel-Steden). Je deelt de rest van de stad in kleinere stukken op. Elke groep onderzoekers krijgt nu een "Deel-Stad" mee. Elke Deel-Stad bestaat uit:
     • De Overlap (het centrum).
     • Één uniek stuk van de stad (een wijk).
   • Stap 3: Leren en Afbreken. Elke groep onderzoekers leert hun eigen Deel-Stad kennen en maakt een kaartje. Omdat ze allemaal het centrum (de Overlap) hebben, kunnen ze hun kaartjes met elkaar vergelijken en op elkaar afstemmen. Ze zeggen: "Jullie noemen deze straat 'Hoofdstraat', wij noemen hem 'Centrumstraat'. Laten we het eens maken!"
   • Stap 4: De Test. Nu hebben ze een gecombineerde kaart van de hele stad. Maar ze testen deze kaart niet op de stukken die ze al hebben gezien. Ze testen hem op de verbindingen tussen de verschillende wijken (de wegen die de Deel-Steden met elkaar verbinden). Deze wegen hebben ze nooit eerder gezien tijdens het leren.

Waarom is dit zo slim?

• Snelheid: In plaats van de hele gigantische stad in één keer te analyseren, werken de onderzoekers met kleine, snelle Deel-Steden. Het is veel lichter voor de computer.
• Nauwkeurigheid: Omdat ze allemaal het centrum (Overlap) delen, weten ze precies hoe ze hun resultaten moeten "stikken" (samenvoegen) zonder dat ze in de war raken.
• Stabiliteit: Ze hoeven niet 20 keer te herhalen om een goed resultaat te krijgen (zoals de oude methoden), omdat de methode van nature al heel stabiel is.

Wat hebben ze bewezen?

De auteurs hebben wiskundig bewezen dat deze methode werkt voor verschillende soorten netwerken:

• Het vinden van gemeenschappen (bijv. welke mensen bij welke club horen).
• Het bepalen van de complexiteit van het netwerk (hoeveel "dimensies" of lagen er nodig zijn).
• Het kiezen van de beste instellingen voor algoritmen.

In hun tests (simulaties en echte data, zoals het DBLP-netwerk van onderzoekers en het Twitch-gamernetwerk) was NETCROP:

1. Veel sneller: Soms wel 10 tot 100 keer sneller dan de oude methoden.
2. Nauwkeuriger: Het vond de juiste antwoorden vaker, vooral bij grote en complexe netwerken.
3. Minder geheugen nodig: Het hoeft niet alles tegelijk in het geheugen te laden.

Conclusie

NETCROP is als het hebben van een team van slimme detectives die elk een klein deel van een mysterie oplossen, maar die allemaal een gemeenschappelijke sleutel (de Overlap) hebben om hun bevindingen samen te voegen. Ze testen hun theorie op de delen van het mysterie die ze nog niet hebben gezien.

Voor wetenschappers die werken met enorme netwerken (van sociale media tot biologische systemen) is dit een game-changer: het maakt het mogelijk om modellen te kiezen en te testen die voorheen te duur of te traag waren om te berekenen.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Network Cross-Validation and Model Selection via Subsampling" in het Nederlands.

Titel: Netwerk Cross-Validatie en Modelselectie via Subsampling

Auteurs: Sayan Chakrabarty, Srijan Sengupta, en Yuguo Chen.

---

1. Het Probleem

Complexere en grotere netwerken worden steeds vaker gebruikt in wetenschappelijke toepassingen (bijv. sociale netwerken, biomedische netwerken, epidemiologie). Hoewel er veel modellen bestaan voor deze netwerken (zoals Stochastic Blockmodels, Random Dot Product Graphs), blijft het selecteren van het juiste model en het afstemmen van parameters (zoals het aantal gemeenschappen of de dimensie van de latente ruimte) een uitdaging.

De traditionele methode voor modelselectie, cross-validatie, is moeilijk toe te passen op netwerkgdata vanwege de unieke structuur:

• Er is meestal slechts één instantie van het netwerk beschikbaar.
• De data-punten (koppels van knopen) zijn niet onafhankelijk.
• Bestaande methoden zoals NCV (Network Cross-Validation) en ECV (Edge Cross-Validation) hebben ernstige nadelen:
  • NCV: Vereist het werken met grote rechthoekige matrices, wat leidt tot zeer trage trainingstijden. Het is specifiek ontworpen voor het schatten van het aantal gemeenschappen in Blockmodels.
  • ECV: Gebruikt matrixcompletie om ontbrekende waarden in te vullen. Dit werkt goed voor spectrale methoden, maar faalt voor methoden die een binaire burenmatrix vereisen (zoals Bernoulli-likelihood methoden). Bovendien vereist ECV vaak een zeer groot deel van de data (bijv. 90%) voor training, wat leidt tot overfitting en hoge rekentijd. Beide methoden vereisen vaak 20 herhalingen voor stabiliteit, wat de rekentijd verder vergroot.

2. Methodologie: NETCROP

De auteurs introduceren NETCROP (NETwork CRoss-Validation using Overlapping Partitions), een computerefficiënte cross-validatieprocedure gebaseerd op subsampling.

Kernidee:
In plaats van het hele netwerk te splitsen in onafhankelijke train- en testsets, verdeelt NETCROP het netwerk in meerdere subnetwerken die een gedeeld overlap-gedeelte hebben.

Het algoritme (stappen):

1. Verdeling (Division):
   • Er wordt een set van $o$ knopen willekeurig geselecteerd als het overlap-gedeelte ($S_0$).
   • De resterende knopen worden verdeeld in $s$ niet-overlappende delen ($S_1, ..., S_s$).
   • Er worden $s$ subsets gevormd: $S_{0q} = S_0 \cup S_q$.
   • De trainingssets zijn de subnetwerken geïnduceerd door deze subsets ($S_{0q}$).
   • De testset bestaat uit de koppelingskansen tussen de knopen in de verschillende niet-overlappende delen ($S_p \times S_q$ voor $p \neq q$).
2. Modelpassing (Model Fitting):
   • Elk kandidaatmodel wordt getraind op elk van de $s$ subnetwerken.
   • Omdat parameters in netwerkmomenten vaak niet uniek identificeerbaar zijn (bijv. permutatie van labels bij gemeenschappen, rotatie bij latente ruimtes), worden de schattingen van de subnetwerken op elkaar afgestemd (stitched) met behulp van het overlap-gedeelte ($S_0$).
3. Loss Berekening:
   • De samengevoegde parameters worden gebruikt om de kansen van de randen in de testset te voorspellen.
   • De voorspellingsfout (loss) wordt berekend tussen de voorspelde kansen en de waargenomen burenmatrix in de testset.
4. Selectie:
   • Het model met de laagste testset-loss wordt geselecteerd.
   • Het proces kan $R$ keer worden herhaald met verschillende willekeurige splitsingen; het meest voorkomende resultaat (meerderheidsstemming) wordt als einduitkomst gekozen.

Computationele Voordelen:

• Schaalbaarheid: De training gebeurt op veel kleinere subnetwerken ($o+m$) in plaats van het volledige netwerk ($n$).
• Parallelisatie: De training op de verschillende subnetwerken kan parallel worden uitgevoerd.
• Stabiliteit: Door het overlap-gedeelte worden de parameters consistent gemaakt, waardoor veel minder herhalingen nodig zijn (vaak $R=1$ of $5$) vergeleken met de 20 herhalingen die NCV/ECV vereisen.

3. Belangrijkste Bijdragen

1. Algemene Procedure: NETCROP is een universele methode die toepasbaar is op een breed scala aan netwerkmodellen en probleemstellingen (modelselectie en parameter-tuning).
2. Theoretische Consistentie:
   • Bewezen consistentie voor het selecteren van het aantal gemeenschappen in Stochastic Blockmodels (SBM) en Degree-Corrected Blockmodels (DCBM).
   • Bewezen consistentie voor het selecteren van de dimensie van de latente ruimte in Random Dot Product Graphs (RDPG).
   • De theorie toont aan dat de kans dat NETCROP het aantal gemeenschappen onderschat, naar nul gaat naarmate de netwerkgrootte toeneemt.
   • De theoretische grenzen voor de fout zijn vergelijkbaar met of beter dan bestaande methoden, maar onder mildere aannames.
3. Efficiëntie: De methode is aanzienlijk sneller en verbruikt minder geheugen dan NCV en ECV, vooral bij grote netwerken.
4. Implementatie: De auteurs hebben de code en scripts openbaar gemaakt via een GitHub-repository.

4. Resultaten

De prestaties van NETCROP zijn getest op zowel gesimuleerde als echte netwerken, vergeleken met NCV en ECV.

• Gesimuleerde Netwerken (SBM/DCBM):
  • NETCROP bereikte 100% nauwkeurigheid bij het detecteren van het aantal gemeenschappen en het onderscheid tussen SBM en DCBM in scenario's waar NCV en ECV faalden (0% nauwkeurigheid) of zeer onnauwkeurig waren.
  • Snelheid: NETCROP was 7 tot 100 keer sneller dan de concurrenten. Waar NCV/ECV duizenden seconden nodig hadden, deed NETCROP het in enkele seconden.
  • Stabiliteit: Met slechts 5 herhalingen was NETCROP al stabiel, terwijl NCV/ECV 20 herhalingen nodig hadden.
• RDPG en Latente Ruimte Modellen:
  • NETCROP overtrof ECV aanzienlijk in nauwkeurigheid bij het schatten van de dimensie van de latente ruimte, vooral bij dunnere netwerken (hoge sparsiteit).
• Real Data (DBLP en Twitch):
  • Op het DBLP-netwerk (onderzoekers) en Twitch-netwerk (gamers) selecteerde NETCROP correct het aantal gemeenschappen (4 en 20 respectievelijk) en het juiste modeltype (DCBM).
  • NCV en ECV neigden naar een verkeerd model (SBM) en overschatte het aantal gemeenschappen.
  • NETCROP was opnieuw 5-10 keer sneller en leverde een hogere AUC (Area Under Curve) op.
• Geheugengebruik: NETCROP gebruikt aanzienlijk minder RAM-geheugen omdat het slechts een deel van het netwerk tegelijk in het geheugen hoeft te laden.

5. Betekenis en Conclusie

NETCROP vult een cruciale lacune in de literatuur over netwerkanalyse op. Het biedt een computationeel efficiënte, theoretisch onderbouwde en veelzijdige oplossing voor modelselectie en parameter-tuning in grote netwerken.

De belangrijkste implicaties zijn:

• Het maakt cross-validatie haalbaar voor zeer grote netwerken waar eerdere methoden te traag of te geheugenintensief waren.
• Het lost het probleem van niet-identificeerbare parameters op door gebruik te maken van overlap-knopen, wat leidt tot robuustere resultaten.
• Het is een verbetering ten opzichte van de huidige state-of-the-art (NCV en ECV) op het gebied van snelheid, nauwkeurigheid en geheugenefficiëntie, zonder in te leveren op theoretische garanties.

De auteurs suggereren dat toekomstig onderzoek zich kan richten op het uitbreiden van NETCROP naar dynamische netwerken, multilayer-netwerken en hypergrafieken.