MCbiF: Measuring Topological Autocorrelation in Multiscale Clusterings via 2-Parameter Persistent Homology

Dit paper introduceert MCbiF, een methode gebaseerd op 2-parameter persistente homologie die de topologische autocorrelatie van niet-hiërarchische multischaalclusteringen kwantificeert en bewezen superieure prestaties levert op machine learning-taken vergeleken met bestaande methoden.

De kern

Stel je voor dat je een enorme hoeveelheid data hebt, zoals de bewegingen van mensen in een stad, de vriendschappen in een sociale netwerk, of hoe muizen in het wild met elkaar omgaan. Vaak kun je deze data op verschillende manieren "groeperen" of "clusteren".

Soms is die groepering heel logisch en hiërarchisch: je begint met individuen, die groeperen in kleine groepjes, die weer in grote clans, en zo verder, net als een stamboom. Dit is makkelijk te begrijpen.

Maar in de echte wereld is het vaak rommeliger. Groepen kunnen samensmelten, weer uit elkaar vallen, en soms vormen ze nieuwe combinaties die niet in een strakke boom passen. Denk aan een groep vrienden die op maandag samen koffie drinken, op dinsdag met een andere groep gaat sporten, en op woensdag weer een heel andere mix vormt. Er is geen enkele "bovenste" groep die alles omvat; het is een dynamisch, verwarrend web.

Deze paper introduceert een nieuwe manier om die rommelige, niet-hiërarchische groeperingen te analyseren. De auteurs noemen hun methode MCBIF.

Hier is een eenvoudige uitleg, vol met metaforen:

1. Het Probleem: De Verwarde Sankey-diagram

Stel je voor dat je een Sankey-diagram tekent. Dat is een soort stroomdiagram waar lijnen van links naar rechts lopen en aangeven hoe mensen of dingen van de ene groep naar de andere gaan.

• Als de groepen perfect hiërarchisch zijn (zoals een stamboom), zien de lijnen eruit als een strakke boom: ze komen samen en splitsen nooit weer op.
• Maar in de echte wereld (zoals bij de muizen in het experiment) kruisen de lijnen elkaar over en weer. Groep A splitst zich, en de stukken gaan naar B en C. Later komen B en C weer samen, maar niet precies zoals voorheen.

Het probleem is: hoe meet je hoe "verward" of "chaotisch" zo'n diagram is? Hoe vergelijk je twee van deze rommelige stroomdiagrammen met elkaar? Bestaande methoden kijken vaak alleen naar twee momenten in de tijd en missen het grote plaatje.

2. De Oplossing: De "Topologische Autocorrelatie" (MCBIF)

De auteurs hebben een wiskundig gereedschap bedacht (gebaseerd op Topological Data Analysis) dat ze MCBIF noemen.

De Metafoor: De 3D-Netwerkkaart
Stel je voor dat je niet alleen naar de lijnen kijkt, maar dat je het hele diagram in een 3D-ruimte bouwt.

• De X-as is de tijd (wanneer gebeurtenissen plaatsvinden).
• De Y-as is de "starttijd" van je observatie.
• De Z-as is de "eindtijd".

In dit 3D-gebouw bouwen ze een structuur van simpliciale complexen. Klinkt ingewikkeld? Denk er gewoon aan als een bouwpakket van LEGO-blokken.

• Als drie muizen (A, B en C) op een bepaald moment allemaal in dezelfde groep zitten, bouwen ze een driehoek (een blokje) in hun structuur.
• Als die groep later uit elkaar valt, maar de muizen komen later weer samen in een andere combinatie, dan ontstaat er een gat of een lus in de structuur.

Deze structuur is een compleet bewijs van hoe de groepen zich gedragen. Het onthult patronen die met het blote oog (of met simpele lijntekeningen) onzichtbaar zijn.

3. Wat Meet Het Eigenlijk? (De "Gaten" en "Knooppunten")

De methode kijkt naar twee soorten "fouten" of "inconsistenties" in de data:

• Dimensie 0 (De "Verkeerde Aansluiting"):
  Stel je voor dat je denkt dat A en B vrienden zijn, en B en C zijn vrienden, maar A en C zijn het nooit eens. In een perfecte hiërarchie zou dit niet kunnen. De methode telt hoeveel van deze "driehoekige verwarringen" er zijn. Dit noemen ze 0-conflicten. Het vertelt je: "Haha, hier klopt de logica niet; er is geen duidelijke 'baas' die iedereen omvat."

• Dimensie 1 (De "Lus" of "Gat"):
  Dit is nog interessanter. Stel je voor dat A en B samengaan, B en C, en C en A, maar ze vormen nooit één grote groep. In je 3D-structuur ontstaat er een gat of een lus. Je kunt eromheen lopen, maar je kunt er niet doorheen. Dit noemen ze 1-conflicten.

  • Voorbeeld: In het muizenexperiment zagen ze dat muizen soms in overlappende groepen zaten, maar nooit allemaal tegelijk in één nest. Dat creëert zo'n "gat" in de data. Bestaande methoden zagen dit niet, maar MCBIF wel.

4. Waarom Is Dit Geweldig voor AI?

De auteurs hebben getoond dat je deze "gatentellers" (de Hilbert-functies) kunt gebruiken als kenmerken voor machine learning.

• Het Experiment 1 (Sankey-diagrammen): Ze wilden voorspellen hoe moeilijk het is om een Sankey-diagram netjes te tekenen zonder dat lijnen elkaar kruisen (een lastig wiskundig probleem).

  • Resultaat: De AI die gebruikmaakte van de MCBIF-metingen (het tellen van gaten en verwarringen) was veel slimmer dan AI die gewoon naar de ruwe data keek of naar simpele statistieken. Het kon de "chaos" in het diagram direct "voelen".

• Het Experiment 2 (Muizen): Ze keken naar echte data van wilde muizen. Ze ontdekten dat bij bepaalde tijdsintervallen (bijvoorbeeld elke 60 seconden) de sociale groepen het meest stabiel en logisch waren (weinig gaten). Bij andere intervallen (bijvoorbeeld elke seconde) was het een chaos van groepjes die constant veranderden.

  • De methode kon precies aangeven waar en wanneer de sociale structuur het meest "hiërarchisch" was en wanneer hij "rommelig" was.

Samenvatting in Eén Zin

Deze paper introduceert een slimme wiskundige "lens" (MCBIF) die rommelige, niet-hiërarchische groeperingen in data omzet in een 3D-structuur van gaten en lussen, waardoor computers veel beter kunnen begrijpen en voorspellen hoe complexe systemen (zoals sociale netwerken of muizengroepen) zich gedragen over de tijd.

Het is alsof je van een platte, verwarde tekening van een stroomdiagram een 3D-sculptuur maakt, zodat je de "gaten" in de logica van de groepen kunt zien en tellen.

Technische samenvatting

1. Probleemdefinitie

Veel datasets vertonen een intrinsieke multischaalstructuur, waarbij betekenisvolle beschrijvingen bestaan op verschillende niveaus van grofheid (resolutie). Traditionele methoden voor het analyseren van dergelijke data, zoals hiërarchisch clusteren (dendrogrammen), gaan ervan uit dat de data een hiërarchische structuur heeft (waarbij clusters alleen samensmelten of splitsen in een strikte volgorde).

In veel real-world toepassingen (zoals tijdsgebonden clustering, topic modeling, of diffusie op data-geometrie) is de structuur echter multischaal maar niet-hiërarchisch. In deze scenario's kunnen clusters samensmelten en later weer splitsen, of overlappende patronen vertonen die niet in een boomstructuur passen.

• De uitdaging: Hoe analyseer en vergelijk je sequenties van partities (clusteringen) die niet-hiërarchisch zijn, rekening houdend met "geheugeneffecten" over de schaalparameter $t$?
• Beperkingen van bestaande methoden: Bestaande maatstaven zoals de Adjusted Rand Index (ARI), Variation of Information (VI) of ultrametrics zijn beperkt tot paarsgewijze vergelijkingen tussen clusters of partities. Ze kunnen geen hogere-orde inconsistenties (interacties tussen meer dan twee clusters over verschillende schalen) detecteren en zijn vaak ongevoelig voor de volgorde van de sequentie.

2. Methodologie: De Multiscale Clustering Bifiltration (MCbiF)

De auteurs introduceren de Multiscale Clustering Bifiltration (MCbiF), een nieuw wiskundig object gebaseerd op Topological Data Analysis (TDA).

• Definitie: Gegeven een sequentie van partities $\theta: [t_1, \infty) \to \Pi_X$, definieert de MCbiF een 2-parameter filtratie van abstracte simpliciale complexen $K_{s,t}$.
  • De parameters zijn het startpunt $s$ en het eindpunt $t$ in de sequentie.
  • Een simplex in $K_{s,t}$ bestaat uit elementen die in het interval $[s, t]$ ten minste één keer in dezelfde cluster hebben gezeten.
  • Dit creëert een driehoekig diagram van inclusies dat zowel grof- als fijnkorreling (coarse- en fine-graining) vastlegt.
• Wiskundige Eigenschappen:
  • De MCbiF is een compleet invariant van de sequentie van partities (inclusief niet-hiërarchische).
  • Toepassing van Multiparameter Persistent Homology (MPH) op de MCbiF resulteert in een module die puntsgewijs eindig-dimensionaal, eindig gepresenteerd en blok-decomposeerbaar is. Dit garandeert algebraïsche stabiliteit.
• Hilbert Functies: De auteurs gebruiken de stabiele Hilbert-functies $HF_k(s, t)$ als invariante maatstaven.
  • $HF_0(s, t)$: Telt het aantal samenhangende componenten. Het detecteert 0-conflicten (afwezigheid van een maximale partitie in een subposet ten opzichte van verfijning).
  • $HF_1(s, t)$: Telt het aantal 1-gaten (cycli). Het detecteert 1-conflicten, wat correspondeert met hogere-orde inconsistenties in cluster-toewijzingen over schalen (bijv. een cyclus van overlappende clusters die niet gesloten kan worden door een gemeenschappelijke cluster).

3. Kernbijdragen

1. MCbiF Constructie: Een nieuwe 2-parameter filtratie die de intersectiepatronen van clusters over schalen encodeert. Het is een hogere-orde uitbreiding van Sankey-diagrammen (die voor hiërarchische data reduceren tot dendrogrammen).
2. Theoretische Karakterisering: Bewijs dat de MCbiF leidt tot een stabiele, blok-decomposeerbare persistence module. De auteurs definiëren 0-conflicten en 1-conflicten en tonen aan hoe deze respectievelijk hiërarchie en genestheid schenden.
3. Nerve-based Constructie: Een computatie-efficiënte alternatieve definitie van de MCbiF gebaseerd op de "nerve" van de clusters. Dit is wiskundig equivalent aan de originele constructie maar computatie-efficiënter wanneer het aantal schalen kleiner is dan de grootte van de grootste cluster.
4. Interpreteerbare Feature Maps: De Hilbert-functies worden gepresenteerd als interpreteerbare topologische features voor machine learning, die de "topologische autocorrelatie" van de data kwantificeren.

4. Resultaten en Experimenten

De auteurs testen hun methode op synthetische en real-world data:

• Regressie Taak (Sankey Crossing Number):

  • Doel: Voorspellen van het minimale aantal kruisingen in een Sankey-diagram (een NP-complete probleem).
  • Resultaat: Modellen getraind op MCbiF features ($HF_0$ en $HF_1$) presteerden significant beter ($R^2 \approx 0.54$) dan baselines (ARI, VI, MOD) en representation learning methoden (GCN op Sankey-graaf, CNN op ruwe labels).
  • Inzicht: De $HF_1$ feature correleert sterk met het aantal kruisingen, wat bevestigt dat topologische gaten direct corresponderen met visuele complexiteit in de visualisatie.

• Classificatie Taak (Order-Preserving Sequences):

  • Doel: Classificeren of een sequentie van partities "order-preserving" is (compatibel met een totale ordening van de data).
  • Resultaat: Een logistische regressie op $HF_1$ bereikte 97% nauwkeurigheid. Baseline methoden (CE, ARI, MOD) presteerden niet beter dan een willekeurige classifier.
  • Inzicht: Niet-order-preserving sequenties introduceren specifieke 1-conflicten die door $HF_1$ worden opgepikt, maar door traditionele maatstaven worden gemist.

• Real-World Applicatie (Muizen Sociale Groepering):

  • Data: Tijdsreeksen van sociale interacties van wilde muizen (Bovet et al., 2022).
  • Analyse: De auteurs vergeleken verschillende temporele resoluties ($\tau$).
  • Vindst: Ze identificeerden drie verschillende regimes. Een specifieke resolutie ($\tau_4$) bleek de meest hiërarchische en stabiele structuur te hebben (laagste $\bar{c}_0$ en $\bar{c}_1$), terwijl andere resoluties meer "non-hiërarchische" breuken vertoonden. De MCbiF kon deze subtiele verschillen in stabiliteit en "time reversibility" kwantificeren waar andere methoden tekortschoten.

5. Significantie en Conclusie

• Voorbij Hiërarchie: De paper biedt een wiskundig robuust raamwerk om complexe, niet-hiërarchische multischaaldata te analyseren, een gebied waar traditionele TDA en clustering methoden tekortschoten.
• Interpretabiliteit: In tegenstelling tot "black-box" deep learning modellen, bieden de Hilbert-functies directe fysieke interpretaties (aantal conflicten, consistentie van clusters). Dit is cruciaal voor Explainable AI (XAI).
• Superieure Prestaties: De methode overtreft zowel traditionele statistische maatstaven als geavanceerde representation learning methoden in taken die afhankelijk zijn van de globale, hogere-orde structuur van de data.
• Toekomstperspectief: De auteurs suggereren dat de methode nuttig kan zijn voor consensus clustering (het evalueren van consistentie tussen verschillende clustering-algoritmen) en het lokaliseren van specifieke conflicten in tijdsgebonden data.

Kortom, MCBIF introduceert een krachtige, theoretisch onderbouwde manier om de "topologische autocorrelatie" in complexe data-sequenties te meten, waardoor het mogelijk wordt om structurele inconsistenties te detecteren die voorheen onzichtbaar waren.