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

Die Arbeit stellt die Multiscale Clustering Bifiltration (MCbiF) vor, ein Werkzeug der topologischen Datenanalyse, das mittels 2-Parameter-Persistenter Homologie die topologische Autokorrelation nicht-hierarchischer Multiskalen-Clusterings quantifiziert und als interpretierbare Merkmalskarte für überlegene maschinelle Lernergebnisse auf Regressions- und Klassifikationsaufgaben dient.

Das Wesentliche

Das große Bild: Warum Gruppen sich ändern, ist wichtiger als die Gruppen selbst

Stell dir vor, du beobachtest eine Gruppe von Menschen in einem großen Raum.

• Morgen: Sie stehen alle einzeln herum.
• Mittag: Sie bilden drei große Gruppen.
• Abend: Zwei dieser Gruppen verschmelzen zu einer riesigen, aber eine dritte Gruppe spaltet sich wieder auf.
• Nacht: Alle mischen sich neu.

In der klassischen Datenanalyse (wie bei einem Stammbaum) würde man erwarten, dass sich Gruppen nur zusammenfügen (wie beim Schmelzen von Wachs) oder nur teilen (wie beim Zerschneiden eines Kuchens). Das nennt man hierarchisch.

Aber in der echten Welt ist das Leben chaotischer! Gruppen vermischen sich, spalten sich wieder auf und bilden neue Konstellationen. Das nennt man nicht-hierarchisch. Die Herausforderung für Computer ist: Wie vergleicht man diese chaotischen Abläufe? Wie misst man, wie "verwirrt" oder "konsistent" eine solche Geschichte ist?

Die Autoren haben dafür ein neues Werkzeug namens MCbiF (Multiscale Clustering Bifiltration) entwickelt.

---

Die Analogie: Der Sankey-Diagramm-Verkehrsstau

Stell dir vor, du willst den Datenfluss einer solchen Gruppe visualisieren. Ein klassisches Werkzeug dafür ist das Sankey-Diagramm.

• Wie es aussieht: Linke Seite sind die Gruppen zu Zeit A, rechte Seite zu Zeit B. Pfeile zeigen, wer zu wem gewechselt ist.
• Das Problem: Wenn die Gruppen sich wild vermischen, kreuzen sich die Pfeile. Das Diagramm sieht aus wie ein durcheinandergeratenes Spaghetti-Gericht. Je mehr Kreuzungen, desto "unordentlicher" ist die Geschichte.

Das Problem bisher: Computer können diese Kreuzungen schwer zählen und noch schwerer verstehen, warum sie da sind.

Die Lösung: MCbiF als "Topologischer Detektiv"

Die Autoren sagen: "Vergiss die Linien. Wir schauen uns die Form der Geschichte an."

Sie bauen eine Art 3D-Modell aus den Daten. Stell dir vor, du nimmst alle Gruppen zu jedem Zeitpunkt und klebst sie wie einen riesigen, sich verändernden Knetmasse-Klumpen zusammen.

• Wenn sich Gruppen einfach nur verbinden, bleibt der Klumpen glatt.
• Wenn sich Gruppen kreuzen und wieder trennen (z.B. Person A ist mit B vereint, dann mit C, aber B und C waren nie direkt verbunden), entstehen im Knetmasse-Modell Löcher oder Schlaufen.

Diese Löcher sind der Schlüssel!

Die zwei Arten von "Löchern" (Konflikten)

Das MCbiF-System zählt zwei Arten von Unstimmigkeiten, die es in der Geschichte gibt:

1. Die "Verwirrten" (Dimension 0):

   • Analogie: Stell dir vor, du bist in einer Warteschlange. Plötzlich sagt jemand: "Du bist jetzt vorne!" Aber eine Sekunde später sagt ein anderer: "Nein, du bist hinten!"
   • Das System erkennt: "Hey, es gibt keine klare Reihenfolge!" Es gibt keinen "König" der Gruppe, der alle anderen überdeckt. Das ist ein 0-Konflikt.
   • Was es misst: Wie sehr die Hierarchie zusammenbricht.

2. Die "Dreiecks-Lügen" (Dimension 1):

   • Analogie: Das ist wie ein klassisches Dreiecks-Drama.
     • Anna sagt: "Ich kenne Bob."
     • Bob sagt: "Ich kenne Carl."
     • Aber Anna sagt: "Ich kenne Carl gar nicht!"
   • In einer perfekten Welt (hierarchisch) würde das nicht passieren. Wenn Anna Bob kennt und Bob Carl, müsste Anna Carl auch kennen (Transitivität).
   • Wenn das nicht stimmt, entsteht im 3D-Modell ein Loch (ein Ring). Das ist ein 1-Konflikt.
   • Was es misst: Komplexe Widersprüche, die einfache Vergleiche übersehen.

Warum ist das genial?

Bisherige Methoden waren wie ein Lineal: Sie maßen nur den Abstand zwischen zwei Punkten (z.B. "Wie ähnlich sind Gruppe A und Gruppe B?").
Das neue MCbiF ist wie ein Architekt, der das ganze Gebäude betrachtet. Es sieht nicht nur, ob zwei Wände schief sind, sondern ob das ganze Dach einstürzen könnte, weil die Balken nicht zusammenpassen.

Der Clou:
Die Autoren haben gezeigt, dass diese "Löcher" (die mathematisch als Hilbert-Funktionen bezeichnet werden) so informativ sind, dass man sie direkt in Künstliche Intelligenz (KI) stecken kann.

Die Experimente: Der Beweis

Die Forscher haben ihre Methode an zwei Aufgaben getestet:

1. Der Sankey-Optimierer:

   • Aufgabe: Ein Computer soll vorhersagen, wie viele Kreuzungen ein Sankey-Diagramm haben wird (eine sehr schwierige Aufgabe).
   • Ergebnis: Die KI, die mit den neuen "Loch-Zählern" (MCbiF) fütterte, war viel besser als alle anderen Methoden. Sie verstand die globale Struktur der Daten besser als Modelle, die nur die rohen Daten oder einfache Graphen sahen.

2. Der Ordnungs-Tester:

   • Aufgabe: Ist eine Geschichte logisch geordnet oder chaotisch? (z.B. bei sozialen Gruppen von Mäusen).
   • Ergebnis: Die Methode konnte mit 97% Genauigkeit sagen, ob die Gruppen sich logisch verhalten oder ob sie wild durcheinandergeraten sind. Andere Methoden lagen bei Zufallstreffer.

Das echte Beispiel: Die Mäuse-Partys

Die Autoren haben echte Daten von Wildmäusen analysiert. Über 9 Wochen beobachteten sie, wie sich die Mäuse in Gruppen zusammenfanden.

• Bei manchen Zeitintervallen (z.B. jede Sekunde) sahen die Gruppen chaotisch aus (viele Kreuzungen, viele "Lügen").
• Bei anderen Intervallen (z.B. alle 24 Stunden) waren die Gruppen stabil und geordnet.
• Das MCbiF-System konnte genau diese Unterschiede messen und sogar vorhersagen, welche Zeitintervalle die "wahren" sozialen Strukturen der Mäuse am besten zeigen.

Fazit in einem Satz

Das MCbiF ist wie ein topologischer Röntgenblick, der durch das Chaos von sich ständig ändernden Gruppen schaut, um die verborgenen "Löcher" und Widersprüche zu finden, die andere Methoden übersehen – und macht diese Informationen nutzbar für bessere KI-Modelle.

Es verwandelt das Chaos von sich vermischenden Gruppen in eine klare, messbare Landkarte der Unordnung.

Technische Zusammenfassung

1. Problemstellung

Viele Datensätze in der realen Welt besitzen eine intrinsische multiskalige Struktur, die sich nicht durch eine einzelne Clusterung, sondern durch eine Sequenz von Partitionen über verschiedene Auflösungsstufen (Skalen $t$) beschreiben lässt. Beispiele hierfür sind zeitliche soziale Netzwerke, Themenmodelle in Dokumenten oder Diffusionsprozesse auf Daten.

Das zentrale Problem besteht darin, solche Sequenzen von Partitionen $\theta(t)$ zu analysieren und zu vergleichen, insbesondere wenn sie nicht-hierarchisch sind.

• Herausforderung: Traditionelle Methoden wie hierarchisches Clustering (Dendrogramme) oder Ultrametrik setzen eine strikte Verschachtelung (Refinement-Ordnung) voraus. In nicht-hierarchischen Sequenzen können Cluster sich teilen, wieder zusammenführen oder überlappen, was die Baumstruktur bricht.
• Limitationen bestehender Ansätze:
  • Ultrametrik: Versagt bei nicht-hierarchischen Daten, da die Dreiecksungleichung verletzt wird.
  • Paarweise Vergleichsmaße (ARI, VI, MOD): Diese vergleichen nur zwei Partitionen gleichzeitig und können keine höheren Ordnungs-Inkonsistenzen (Higher-Order Inconsistencies) über die gesamte Sequenz hinweg erfassen. Sie ignorieren oft die zeitliche Reihenfolge und „Gedächtniseffekte".

Ziel ist es, ein Werkzeug zu entwickeln, das die topologische Autokorrelation einer Sequenz von Partitionen erfasst, unabhängig davon, ob diese hierarchisch ist oder nicht.

2. Methodik: Multiscale Clustering Bifiltration (MCbiF)

Die Autoren führen die Multiscale Clustering Bifiltration (MCbiF) ein, ein neues Objekt aus dem Bereich der Topologischen Datenanalyse (TDA).

• Definition: Die MCbiF ist eine 2-Parameter-Filtration abstrakter simplizialer Komplexe $K_{s,t}$, parametrisiert durch einen Startpunkt $s$ und einen Endpunkt $t$ ($s \le t$).
  • Ein Simplex $\sigma = [x_1, \dots, x_k]$ gehört zu $K_{s,t}$, wenn alle Elemente $x_i$ in mindestens einer Partition $\theta(r)$ für $r \in [s, t]$ derselben Cluster zugeordnet waren.
  • Dies kodiert die Schnittmuster von Clustern über den gesamten Zeit- oder Skalenspanne $[s, t]$.
• Mathematische Eigenschaften:
  • Die MCbiF ist ein vollständiges Invariant der Sequenz $\theta$.
  • Die Anwendung der Multi-Parameter Persistent Homology (MPH) auf die MCbiF führt zu einem endlich präsentierten, block-dekomponierbaren Persistenzmodul.
  • Als stabile Invarianten werden die Hilbert-Funktionen $HF_k(s, t)$ verwendet, die den Rang der Homologiegruppen $H_k(K_{s,t})$ angeben.

Interpretation der Dimensionen:

• Dimension $k=0$ (Verbundene Komponenten): $HF_0(s, t)$ zählt die Anzahl der verbundenen Komponenten. Ein Wert, der kleiner ist als das Minimum der Clusteranzahlen in $[s, t]$, deutet auf einen 0-Konflikt hin. Dies bedeutet, dass es im Intervall $[s, t]$ keine maximale Partition bezüglich der Verfeinerungsordnung gibt (Verletzung der Hierarchie).
• Dimension $k=1$ (Löcher/Zyklen): $HF_1(s, t)$ zählt die 1-dimensionalen Löcher. Ein Wert $>0$ deutet auf einen 1-Konflikt hin. Dies repräsentiert höhere Ordnungs-Inkonsistenzen, bei denen Cluster-Zuordnungen über mehrere Skalen hinweg einen nicht-überdeckbaren Zykel bilden (z. B. $A$ ist mit $B$ verbunden, $B$ mit $C$, $C$ mit $A$, aber es gibt keine gemeinsame Partition, die alle drei vereint).

Alternative Konstruktion:
Die Autoren stellen eine äquivalente, auf dem Nerv basierende Konstruktion vor, die als höherordentliche Erweiterung des Sankey-Diagramms interpretiert werden kann. Während ein Sankey-Diagramm nur paarweise Überlappungen zwischen aufeinanderfolgenden Schichten zeigt, erfasst die nerv-basierte MCbiF auch höhere Überlappungen über mehrere Schichten hinweg.

3. Wichtige Beiträge

1. Neues mathematisches Framework: Einführung der MCbiF als 2-Parameter-Filtration, die nicht-hierarchische Clustersequenzen vollständig charakterisiert.
2. Theoretische Charakterisierung von Konflikten:
   • Definition und Quantifizierung von 0-Konflikten (Fehlen einer maximalen Partition) und 1-Konflikten (höhere Ordnungs-Inkonsistenzen).
   • Beweis, dass 1-Konflikte zu Verletzungen der starken Dreiecksungleichung in Ultrametrik-Matrizen führen.
   • Herleitung globaler, normalisierter Maße: Average 0-Conflict ($\bar{c}_0$) und Average 1-Conflict ($\bar{c}_1$), die den Grad der Nicht-Hierarchie quantifizieren.
3. Maschinelles Lernen als Feature-Map: Die Hilbert-Funktionen $HF_k(s, t)$ werden als interpretierbare topologische Feature-Maps für Downstream-Machine-Learning-Aufgaben vorgeschlagen.
4. Anwendung auf reale Daten: Demonstration der Methode an einer realen Datensatz von sozialen Gruppenmustern wilder Mäuse über die Zeit.

4. Ergebnisse und Experimente

Die Autoren testen die MCbiF in drei Szenarien:

• Regressionsaufgabe (Minimierung von Kreuzungen in Sankey-Diagrammen):

  • Ziel: Vorhersage der minimalen Anzahl von Kreuzungen ($\kappa_\theta$) beim Layout eines Sankey-Diagramms (ein NP-vollständiges Problem).
  • Ergebnis: Modelle, die auf MCbiF-Features ($HF_0, HF_1$) trainiert wurden, übertrafen signifikant Baseline-Features (ARI, VI, MOD) und Representation-Learning-Methoden (Raw Labels, GCN auf Sankey-Graphen).
  • Bedeutung: Die Kombination aus $HF_0$ und $HF_1$ erreichte die höchsten $R^2$-Werte, was zeigt, dass die topologischen Invarianten globale Eigenschaften der Sequenz besser erfassen als lokale paarweise Vergleiche.

• Klassifikationsaufgabe (Erkennung ordnungserhaltender Sequenzen):

  • Ziel: Unterscheidung zwischen Sequenzen, die mit einer totalen Ordnung auf den Daten kompatibel sind (order-preserving), und solchen, die es nicht sind.
  • Ergebnis: Ein logistisches Regressionsmodell, das nur auf $HF_1$ trainiert wurde, erreichte eine Genauigkeit von 97%. Baseline-Methoden und Rohdaten-Encodings lagen nahe am Zufallsniveau (ca. 50-56%).
  • Bedeutung: $HF_1$ ist extrem sensitiv für das Fehlen einer konsistenten Ordnung (1-Konflikte).

• Anwendung auf reale Daten (Mäuse-Sozialverhalten):

  • Analyse von Kontakt-Daten von Hausmäusen über 9 Wochen.
  • Die MCbiF-Features identifizierten drei verschiedene zeitliche Regime basierend auf dem Grad der Nicht-Hierarchie.
  • Es wurde gezeigt, dass eine mittlere zeitliche Auflösung ($\tau = 60s$) die hierarchischste und stabilste Struktur aufweist, während hohe und niedrige Auflösungen stärkere 0- und 1-Konflikte aufweisen. Zudem wurde die Zeitreversibilität der sozialen Gruppen durch den Vergleich von Vorwärts- und Rückwärts-Sequenzen mittels Hilbert-Distanz quantifiziert.

5. Bedeutung und Fazit

Das Papier stellt einen signifikanten Fortschritt in der Analyse komplexer, nicht-hierarchischer Datenstrukturen dar.

• Erweiterung bestehender TDA: Die MCbiF erweitert die 1-Parameter-Persistenzhomologie (die oft auf hierarchische Daten beschränkt ist) auf 2 Parameter, was eine reichhaltigere algebraische Invariante für dynamische Clustersequenzen liefert.
• Interpretierbarkeit: Im Gegensatz zu „Black-Box"-Representation-Learning-Methoden bieten die Hilbert-Funktionen und die daraus abgeleiteten Konfliktmaße ($\bar{c}_0, \bar{c}_1$) direkte, mathematisch fundierte Einblicke in die Struktur der Daten (z. B. „Wie stark bricht die Hierarchie?").
• Leistungsfähigkeit: Die experimentellen Ergebnisse belegen, dass diese topologischen Features für maschinelles Lernen überlegen sind, insbesondere bei Aufgaben, die das Verständnis globaler, sequenzieller Abhängigkeiten erfordern.
• Zukunftsausblick: Die Autoren schlagen vor, die Methode auf höhere Homologie-Dimensionen ($k \ge 2$) und komplexere Invarianten (wie Persistence Landscapes) zu erweitern und sie zur Bewertung von Konsistenz in Consensus-Clustering zu nutzen.

Zusammenfassend bietet die MCbiF ein robustes, mathematisch fundiertes Werkzeug, um die „topologische Autokorrelation" in multiskaligen Daten zu messen und dabei Phänomene zu erfassen, die für traditionelle statistische oder informationstheoretische Methoden unsichtbar bleiben.