Technische Samenvatting: Chordloze Cyclusfiltraties voor Dimensiedetectie in Complexe Netwerken via Topologische Data-analyse

1. Probleemstelling

Complexe netwerken uit diverse domeinen (biologisch, sociaal, technologisch) vertonen vaak structurele patronen die consistent zijn met een onderliggende latente hyperbolische geometrie. Het bepalen van de effectieve dimensie ($D$) van deze latente ruimte is cruciaal voor het begrijpen van structurele complexiteit, gemeenschapsorganisatie, netwerknavigatie en systeemdynamica. Hoewel er verschillende definities van netwerkdimensie bestaan (bijvoorbeeld fractaal, spectraal, metrisch), en modelgestuurde benaderingen (zoals het $S^D/H^{D+1}$-model) succesvol dimensie hebben geschat door cyclusfrequenties te projecteren op configuratieruimtes, vereisen deze methoden vaak het genereren van grote ensemble's van synthetische surrogaatnetwerken voor elk nieuw doelnetwerk. Dit proces is rekenintensief en mist een unificerend, datagedreven kader dat Topologische Data-analyse (TDA) integreert met machine learning om surrogaatgeneratie te omzeilen.

Bovendien zijn standaard TDA-toepassingen in de netwerkwetenschap beperkt gebleven. Gewone persistente homologie is ongeschikt voor grafen omdat cycli (1-dimensionale kenmerken) oneindige persistentie hebben bij afwezigheid van hogerdimensionale simplexen om ze op te vullen. Bovendien kunnen bestaande filtratieschema's (bijvoorbeeld gebaseerd op knooppuntgraad of Ricci-kromming) de specifieke geometrische handtekeningen die nodig zijn voor dimensieschatting, niet vastleggen.

2. Methodologie

De auteurs stellen een tweeledige aanpak voor die algebraïsche topologie en machine learning combineert om netwerkdimensie te schatten.

A. Chordloze Cyclusfiltraties en Uitgebreide Persistentie

De kern-topologische innovatie is een wegingsschema gebaseerd op chordloze cycli (cycli zonder interne koorden).

1. Weging: Voor een gegeven netwerk worden drie grafgewogen grafen geconstrueerd. Het gewicht van een rand wordt gedefinieerd door de lokale dichtheid van chordloze cycli van specifieke lengtes: driehoeken ($C_t$), vierkanten ($C_s$) en vijfhoeken ($C_p$).
2. Uitgebreide Persistentie: Omdat cycli in grafen niet sterven in standaardfiltraties, berekenen de auteurs uitgebreide persistentie. Dit omvat een techniek om de grafgewogen graaf om te zetten in een topologisch equivalente knooppuntgewogen graaf via "graad-splitsende subdieling". Dit maakt het gebruik van standaard TDA-software (Gudhi) mogelijk om de uitgebreide persistentie van cycli te berekenen, gedefinieerd als het verschil tussen de geboortewaarde in de subniveaufiltratie en de geboortewaarde in de superniveaufiltratie.
3. Beschrijvers: De Totale Uitgebreide Persistentie (de som van persistentiewaarden voor alle onafhankelijke cycli) wordt berekend voor elk van de drie filtraties, wat een kenmerkvector oplevert $(TP_t, TP_s, TP_p)$.

B. Benaderingen voor Dimensieschatting

Het artikel presenteert twee methoden voor het schatten van $D$:

1. Surrogaatgebaseerde k-Nearest Neighbors (kNN):

   • Voor een doelnetwerk wordt een ensemble van synthetische surrogaatnetwerken gegenereerd met behulp van de $D$-GR (Geometrische Randomisatie) procedure. Deze methode herschikt het netwerk om de waarschijnlijkheid van het $S^D/H^{D+1}$-model te maximaliseren, terwijl de exacte graadsequentie van het doelnetwerk behouden blijft.
   • Het doelnetwerk en zijn surrogaatnetwerken worden in kaart gebracht naar een configuratieruimte gedefinieerd door $(TP_t, TP_s, TP_p)$.
   • Een kNN-classificator identificeert de dimensie $D$ van de surrogaatnetwerken die het dichtst bij het doelnetwerk liggen.

2. Neuraal Netwerk (DimNN):

   • Om het genereren van surrogaatnetwerken voor elk nieuw netwerk te vermijden, trainen de auteurs een Residual Multilayer Perceptron (DimNN).
   • Trainingsdata: Een database van 792.000 synthetische netwerken (SynNet) gegenereerd vanuit het $S^D/H^{D+1}$-model met bekende dimensies ($D \in [1, 10]$) en variërende parameters (graadheterogeniteit $\gamma$, inverse temperatuur $\beta$).
   • Invoerkenmerken: Het model gebruikt een 12-dimensionale kenmerkvector die omvat:
     • Grafstatistieken: Aantal knooppunten ($N$), gemiddelde graad ($\langle k \rangle$), genormaliseerd tweede moment van de graadverdeling ($\langle k^2 \rangle / \langle k \rangle^2$), min/max graden, en gemiddelde buurgraad ($\langle k_{nn} \rangle$).
     • Cyclusdichtheden: Gemiddelde chordloze driehoek-, vierkant- en vijfhoekdichtheden ($C_t, C_s, C_p$).
     • Topologische beschrijvers: Totale uitgebreide persistenties ($TP_t, TP_s, TP_p$).
   • Architectuur: Een diep MLP met 21 verborgen lagen, ReLU-activaties, dropout (50%) en residuale verbindingen, getraind met AdamW.
   • Validatie: Een secundair regressiemodel (met MSE-verlies) werd getraind om robuustheid te verifiëren, waarbij hoge overeenkomst met het classificatiemodel werd aangetoond.

3. Belangrijkste Bijdragen

• Nieuw Filtratieschema: Introductie van een op chordloze cyclusdichtheid gebaseerd filtratieschema voor grafen, specifiek afgestemd op het vastleggen van geometrische eigenschappen die relevant zijn voor dimensie.
• Uitgebreide Persistentie voor Grafen: Aanpassing van uitgebreide persistentie aan grafgewogen grafen via graad-splitsende subdieling, waardoor de berekening van eindige cycluslevensduren mogelijk wordt in netwerkontexten waar standaard persistentie faalt.
• Datagedreven Dimensieschatting: Ontwikkeling van DimNN, een neuraal netwerk getraind op een enorme synthetische database dat netwerkdimensie direct kan schatten vanuit een enkel real-world netwerk zonder surrogaatgeneratie.
• Integratie van TDA en ML: Demonstratie dat TDA-kenmerken (totale persistentie) de nauwkeurigheid van machine learning-modellen voor dimensieschatting significant verbeteren, en modellen die alleen cyclusdichtheden of graadstatistieken gebruiken, overtreffen.

4. Resultaten

• Correlatie: Er werd een negatieve correlatie waargenomen tussen netwerkdimensie en totale uitgebreide persistentiewaarden, met name voor vierkanten en vijfhoeken (Pearson-coëfficiënten $\rho_s \approx -0,31$, $\rho_p \approx -0,24$).
• Synthetische Validatie:
  • De kNN-surrogaatmethode bereikte redelijke nauwkeurigheid op synthetische doelen, met verwarringsmatrices die hoge fideliteit toonden voor de meeste dimensies, hoewel er enige verwarring optrad tussen aangrenzende dimensies in sterk heterogene netwerken.
  • DimNN bereikte een classificienauwkeurigheid van 83,00% op de validatieset met behulp van de volledige kenmerkvector.
  • Ablatiestudies bevestigden dat het combineren van totale persistentie met gemiddelde cyclusdichtheden en graadgerelateerde kenmerken de prestaties maximaliseert. Het verwijderen van TDA-kenmerken resulteerde in een significante daling van de nauwkeurigheid.
• Toepassing op Real-World Netwerken:
  • De methode werd toegepast op 10 bekende real-world netwerken (bijvoorbeeld Human Connectome, Jazz-samenwerking, E-mailnetwerken). De afgeleide dimensies waren consistent met eerdere literatuur (bijvoorbeeld hersenconnectomen rond $D=3$, sociale netwerken die iets hogere dimensies vereisen).
  • Bij toepassing op een grotere dataset van 53 real-world netwerken voorspelde het model dimensies variërend van 1 (Software, Web-grafen) tot 10 (sommige sociale netwerken).
  • Robuustheid: Twee onafhankelijk getrainde modellen (classificatie en regressie) toonden hoge overeenkomst (tot 88,86% op synthetische data), wat suggereert dat de modellen onderliggende relaties vastleggen in plaats van overfitten.
  • Validatie: Surrogaatnetwerken gegenereerd met de voorspelde dimensies en D-Mercator-inbeddingen reproduceerden succesvol belangrijke topologische eigenschappen van de originele netwerken, waaronder graadverdeling, clustering-spectrum en percolatiedrempels.

5. Betekenis en Beweringen

Het artikel beweert dat dit werk de kloof tussen complexe netwerkteorie en Topologische Data-analyse overbrugt door een robuste en effectieve methode te bieden voor het blootleggen van de verborgen geometrie van complexe netwerken.

• Efficiëntie: De neuraal-netwerkbenadering biedt een aanzienlijk rekenkundig voordeel ten opzichte van eerdere surrogaatgebaseerde methoden, omdat er geen hertraining of surrogaatgeneratie nodig is voor nieuwe netwerken.
• Expressiviteit: De studie toont aan dat cyclusbewuste filtraties en uitgebreide persistentie-beschrijvers zeer expressieve kenmerken zijn voor dimensiedetectie, die traditionele geometrische beschrijvers aanvullen.
• Generalisatie: Het model transferreert succesvol van synthetische trainingsdata naar real-world netwerken, wat suggereert dat de latente geometrische structuren van real-world netwerken goed worden weergegeven door het $S^D/H^{D+1}$-model binnen de geteste parameterregimes.

De auteurs merken bescheiden op dat het kader voornamelijk gericht is op geometrische netwerken ($\beta > D$) en dat het uitbreiden van de aanpak naar zwak-geometrische regimes of het optimaliseren van de neurale architectuur voor bredere distributieveranderingen een richting blijft voor toekomstig werk. Het artikel positioneert zichzelf als een bewijs van concept voor de bruikbaarheid van op cycli gebaseerde filtraties in TDA en de haalbaarheid van diep-lering-ondersteunde dimensieschatting.