Low-Complexity and Consistent Graphon Estimation from Multiple Networks

Probleemstelling

Het artikel adresseert de uitdaging om een graphon (een niet-parametrisch model dat de generatieve structuur van willekeurige grafen beschrijft) te schatten op basis van een collectie van meerdere netwerken. De specifieke moeilijkheid ligt in het feit dat deze netwerken:

1. Geen gemeenschappelijke knopen hebben (disjoint node sets).
2. Verschillende maten hebben (variabele grootte $n^{(m)}$).

Bestaande methoden voor graphon-schatting zijn vaak beperkt tot één enkel netwerk. Wanneer men meerdere netwerken analyseert, worden methoden die de schattingen per netwerk apart berekenen en vervolgens middelen, geconfronteerd met ernstige tekortkomingen:

• Identificeerbaarheid: Graphons zijn niet uniek identificeerbaar; verschillende graphons kunnen dezelfde verdeling van grafen genereren.
• Bias: Schattingen op kleine netwerken zijn sterk vertekend en hebben een disproportioneel grote invloed op het gemiddelde.
• Heterogeniteit: Bestaande methoden negeren vaak de schaalverschillen tussen netwerken.
• Complexiteit: Geavanceerde methoden (zoals die gebaseerd op Gromov-Wasserstein afstanden of neurale netwerken) zijn computatief zeer intensief en niet schaalbaar voor grote collecties.

Methodologie: Joint Graph Sorting (JGS)

De auteurs introduceren de Joint Graph Sorting (JGS) schatter, een nieuw framework dat de knopen van alle netwerken in één collectie simultaan sorteert om een uniek, globaal histogram te construeren.

Kernstappen van het algoritme:

1. Gecombineerde Sortering: In plaats van netwerken één voor één te behandelen, worden alle knopen uit alle $M$ netwerken verzameld. De rangschikking gebeurt op basis van de genormaliseerde empirische graad ($\hat{d}^{norm}$) van elke knoop.
   • De genormaliseerde graad voor knoop $i$ in netwerk $m$ is: $\hat{d}^{norm}_{i,(m)} = \frac{1}{n^{(m)}-1} \sum_{j} A^{(m)}_{i,j}$.
2. Latente Posities: De knopen worden gesorteerd van laag naar hoog op basis van deze graden. De geschatte latente positie $\hat{U}^{JGS}_{i,(m)}$ wordt vervolgens toegewezen als de genormaliseerde rang in de totale collectie van $N = \sum n^{(m)}$ knopen. Dit creëert een uniforme verdeling op het interval $[0, 1]$ met een hogere resolutie dan bij individuele netwerken.
3. Gecombineerd Histogram: De gesorteerde knopen worden gebruikt om een enkele adjacency-matrix te construeren (met ontbrekende waarden voor kanten tussen verschillende netwerken). Het graphon wordt geschat als een stapfunctie (histogram) over een $k \times k$ rooster, waarbij de kantdichtheid in elke cel wordt berekend op basis van de waargenomen kanten binnen de gesorteerde blokken.
4. Selectie van $k$: Het aantal blokken $k$ wordt gekozen via een regel die de bias-variatie balans optimaliseert en lege blokken voorkomt:
   $$k \asymp \min \left\{ S^{1/4}, \frac{N}{c(M + \log N)} \right\}$$
   waarbij $S$ het totale aantal waargenomen kanten en niet-kanten is.

Complexiteit:
Het algoritme heeft een lage computationele complexiteit van $O(N \log N + S)$, waarbij $N$ het totale aantal knopen en $S$ het totale aantal waarnemingen is. Dit is aanzienlijk sneller dan iteratieve methoden zoals SIGL of SGWB.

Belangrijkste Bijdragen

1. Deterministisch, niet-iteratief algoritme: JGS schat de latente posities en het graphon in één doorloop zonder zware optimalisatie of training.
2. Theoretische consistentie: De auteurs bewijzen dat de schatter consistent is onder milde regulariteitsvoorwaarden (strikt monotonie van de genormaliseerde graadfunctie). De schatter convergeert naar de waarheid wanneer de grootte van de netwerken toeneemt (met een vast aantal netwerken $M$).
3. Prestaties: Numerieke experimenten tonen aan dat JGS superieur is aan state-of-the-art methoden (zoals SBA, SAS, USVT, SGWB, SIGL) in termen van nauwkeurigheid (MISE), vooral bij kleine en heterogene netwerken.
4. Efficiëntie: De rekentijd is meerdere ordes van grootte korter dan die van consistente methoden zoals SIGL en SGWB.
5. Toepassing: JGS verbetert de prestaties van Graph Neural Networks (GNN) voor classificatietaken wanneer het wordt gebruikt voor data-augmentatie (via G-Mixup).

Resultaten

• Nauwkeurigheid: Op synthetische data (13 verschillende graphon-functies) behaalde JGS de laagste Mean Integrated Squared Error (MISE) voor bijna alle gevallen, inclusief niet-monotone graphons waar andere methoden faalden. Alleen bij zeer schaarse netwerken (graphon 9) presteerde SIGL iets beter, maar JGS bleef de op één na beste.
• Schaalbaarheid: De uitvoeringstijd van JGS blijft laag zelfs bij grote aantallen netwerken of grote netwerkgroottes, terwijl methoden zoals SIGL en SGWB exponentieel langzamer worden.
• Asymptotisch gedrag:
  • Wanneer de grootte van de netwerken ($n^{(m)}$) toeneemt, convergeert de schatter naar 0 fout.
  • Wanneer het aantal netwerken ($M$) toeneemt maar de netwerkgrootte bounded blijft, convergeert de schatter niet naar 0. Dit is een fundamentele limiet van het gebruik van genormaliseerde graden als indicator bij vaste netwerkgroottes, maar dit is een inherente beperking van het asymptotische kader, niet specifiek van JGS.
• Real-world toepassing: Bij classificatie op de IMDB-BINARY en IMDB-MULTI datasets leidde het gebruik van JGS voor data-augmentatie tot de hoogste testnauwkeurigheid vergeleken met andere augmentatiemethoden.

Betekenis en Conclusie

Dit werk toont aan dat het middelen van individuele graphon-schattingen geen optimale strategie is voor collecties van netwerken. Door gezamenlijke sortering van knopen over alle netwerken heen, kan informatie efficiënter worden gebundeld.

De belangrijkste doorbraak is dat statistische consistentie en hoge nauwkeurigheid niet ten koste hoeven te gaan van computationele complexiteit. JGS biedt een praktische, schaalbare oplossing voor het analyseren van heterogene netwerkcollections, wat essentieel is voor toepassingen in neurowetenschappen, ecologie en sociologie waar data vaak uit vele kleine, niet-overlappende netwerken bestaat. De open-source implementatie maakt de methode direct toepasbaar voor onderzoekers.