Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph

Technische Samenvatting: Dimensiereductie Ontmoet Netwerkwetenschap

Probleemstelling

Hoewel UMAP een dominante tool is voor het visualiseren van hoogdimensionale data, behandelen standaard analytische workflows de resulterende 2D-spreidingsdiagram (scatter plot) doorgaans als het enige object van belang. Deze aanpak negeert de rijke, intermediaire k-nearest-neighbor (kNN) graaf die UMAP intern construeert vóór de projectie. De auteurs stellen dat deze graaf de lokale geometrie en connectiviteit van de datamanifold in de oorspronkelijke hoogdimensionale ruimte getrouwer weergeeft dan de 2D-lay-out, die onvermijdelijk vervorming introduceert. Door deze graaf te negeren, missen analisten kansen om sensemaking-taken uit te voeren — zoals het identificeren van representatieve punten, het analyseren van dichtheids-hiërarchieën en het detecteren van lokale cohesie — die in de 2D-projectie verborgen blijven.

Methodologie

Het artikel stelt voor om de interne kNN-graaf van UMAP te verheffen tot een "first-class analytical resource" door standaard netwerkwetenschappelijke algoritmen direct op deze graaf toe te passen, in plaats van op de 2D-embedding. De methodologie maakt gebruik van de specifieke structurele eigenschappen van de graaf: een vaste uitgaande graad $k$, een variabele inkomende graad en dichtheid-adaptieve randgewichten. Drie specifieke algoritmen worden toegepast:

1. PageRank voor Selectie van Representatie:

   • Mechanisme: In plaats van exemplaren te selecteren op basis van geometrische zwaartepunten in de vertekende 2D-ruimte (die zich in niet-representatieve regio's kunnen bevinden), passen de auteurs PageRank toe op de kNN-graaf.
   • Logica: Een knoopscore wordt transitief versterkt; een punt scoort hoog niet alleen omdat veel knopen naar het wijzen (hoge in-degree), maar omdat de knopen die ernaar wijzen zelf ook hoog scoren. Dit identificeert globaal representatieve punten die dienen als "autoriteiten" in de manifold.
   • Implementatie: Randgewichten worden afgeleid van de dichtheid-adaptieve lidmaatschapssterktes van UMAP.

2. k-Core Decompositie voor Dichtheids-hiërarchie:

   • Mechanisme: De auteurs passen k-core decompositie toe op de graaf om dichte kernregio's te onderscheiden van ijle periferieën.
   • Logica: In tegenstelling tot standaard graad-gebaseerde decompositie, die beperkt wordt door de vaste uitgaande graad $k$, dekomponeert deze methode uitsluitend op basis van de inkomende graad (in-degree). Dit produceert een "coreness"-score (0, 1, 2...) die aangeeft hoe diep een knoop is ingebed in progressief dichtere, meer onderling verbonden subgrafen.
   • Doel: Het onthullen van gegradeerde subgraaf-hiërarchieën en subcategorieën binnen clusters die discrete clustering-labels (bijv. van HDBSCAN) niet kunnen vangen.

3. Clustering Coëfficiënt voor Lokale Cohesie:

   • Mechanisme: De clustering coëfficiënt (CC) wordt berekend voor elke knoop om de fractie van zijn buren te meten die ook met elkaar verbonden zijn.
   • Logica: Een hoge CC duidt op "hecht verbonden" micro-buurten waar punten elkaar wederzijds als dichtstbijzijnde buren beschouwen.
   • Doel: Het detecteren van semantisch coherente micro-clusters (bijv. specifieke handschrijfstijlen) die er in een 2D-projectie mogelijk uitzien als een monolithische massa.

Belangrijkste Bijdragen

Het artikel levert twee primaire bijdragen:

1. Conceptuele Verschuiving: Het overbrugt dimensiereductie en netwerkwetenschap door de weggegooide kNN-graaf van UMAP als een primaire bron te behandelen. Dit maakt sensemaking mogelijk die complementair is aan 2D-spreidingsdiagrammen, specifiek gericht op representativiteit, dichtheidsstructuur en lokale cohesie.
2. Empirische Validatie: Door middel van kwantitatieve en kwalitatieve evaluaties op MNIST en Fashion MNIST demonstreren de auteurs dat deze graaf-gebaseerde methoden competitief zijn met, of superieur aan, doelgerichte methoden:
   • PageRank vs. k-medoids: Door PageRank geselecteerde punten bereiken een superieure klassebalans (lagere Jensen-Shannon divergentie) vergeleken met k-medoids, die de neiging heeft om overmatig te selecteren uit variabelie-rijke klassen. Hoewel k-medoids licht presteert op het gebied van representativiteit bij zeer kleine budgetten, haalt PageRank snel in en blijft het competitief. Cruciaal is dat PageRank slechts één globale rangschikking vereist, terwijl k-medoids voor elk budgetformaat opnieuw moet worden uitgevoerd.
   • k-Core vs. HDBSCAN: Terwijl HDBSCAN discrete clusterlabels toekent, onthult k-core decompositie een gegradeerde hiërarchie van centraliteit binnen clusters. De lidmaatschaps-kansen van HDBSCAN vertoonden een bijna nul-correlatie met coreness, wat bevestigt dat ze verschillende vragen beantwoorden (groepslidmaatschap versus positie binnen de groep).
   • Clustering Coëfficiënt: CC identificeert onderscheidende micro-buurten (bijv. specifieke stijlen van het cijfer "6") die topologisch coherent zijn maar visueel ononderscheidbaar kunnen zijn in 2D.

Resultaten

• Stabiliteit: PageRank-rangschikkingen zijn zeer stabiel over een bereik van 20x in buurnommaten ($k=5$ tot $100$), met gemiddelde Spearman-rangcorrelaties van ~0,95, wat aangeeft dat de geselecteerde representanten geen artefacten zijn van een specifieke $k$-waarde.
• Prestaties:
  • Representativiteit: PageRank is competitief met k-medoids wat betreft de gemiddelde cosinusafstand tot de dichtstbijzijnde representanten, vooral naarmate het selectiebudget toeneemt.
  • Klassebalans: PageRank presteert significant beter dan k-medoids in het behouden van de globale klassenverdeling (lagere JSD), met name bij budgetten $s \ge 200$.
  • Downstream Nut: SVM-classifiers getraind op door PageRank geselecteerde exemplaren bereiken een nauwkeurigheid die binnen 2–3 procentpunten ligt van k-medoids op Fashion MNIST en is vergelijkbaar op MNIST.
  • Structureel Inzicht: k-core decompositie isoleert succesvol subcategorieën (bijv. rugzakken versus heuptasjes binnen de "tas"-klasse) door te filteren op specifieke coreness-drempelwaarden. Hoge CC-waarden isoleren consistente handschrijfstijlen binnen de "6"-cluster.

Betekenis en Claims

De auteurs claimen dat hun werk de onbenutte potentie van de interne representatie van UMAP aantoont. Door de kNN-graaf te behouden en te analyseren, kunnen analisten toegang krijgen tot structurele informatie (centraliteit, connectiviteitshiërarchie, lokale cohesie) die verloren gaat of vervormd wordt in de 2D-projectie.

Het artikel positioneert deze graaf-algoritmen niet als vervangingen voor bestaande tools, maar als complementaire methoden die specifieke voordelen bieden:

• Ze bieden een parameter-vrije (of stabiele) manier om representanten te selecteren zonder een afstandsobjectief te optimaliseren.
• Ze bieden een continue hiërarchie van dichtheid (via k-core) in plaats van discrete cluster-toewijzingen.
• Ze zijn computationeel efficiënt en draaien in minder dan 1 seconde op 60.000 punten door gebruik te maken van de vooraf berekende buren-arrays van UMAP.

De auteurs concluderen dat dit perspectief de gemeenschap aanmoedigt om "verder te kijken dan het spreidingsdiagram en in de graaf te kijken die het heeft gemaakt", wat suggereert dat deze aanpak zich natuurlijk uitstrekt naar andere dimensiereductiemethoden die kNN-grafen construeren (zoals TriMap, PaCMAP).