📊 statistics

$k$ -Nearest Neighbors in Gromov--Wasserstein Space

Diese Arbeit implementiert die $k$ -nächste-Nachbarn-Klassifizierung unter Verwendung von Gromov–Wasserstein- und Fused-Gromov–Wasserstein-Distanzen zum Vergleich von Graphen bzw. knotenattributierten Graphen und beweist die universelle Konsistenz dieser Klassifikatoren, während sie deren starke empirische Leistung über mehrere Datensätze hinweg demonstriert.

Ursprüngliche Autoren: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Veröffentlicht 2026-06-10

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie versuchen, einen riesigen Haufen verschiedener Objekte zu sortieren. Einige sind einfache Formen, andere sind komplexe Netzwerke wie U-Bahnpläne oder soziale Kreise. Ihr Ziel ist es, herauszufzufinden, zu welcher Kategorie ein neues, unbekanntes Objekt gehört, indem Sie die Objekte betrachten, die Sie bereits kennen. Das ist die Aufgabe eines $k$ -Nearest Neighbors ( $k$ -NN)-Klassifizierers.

Denken Sie an $k$ -NN wie an einen „Popularitätswettbewerb“ unter Ihren Nachbarn. Wenn Sie ein neues Objekt in einen Raum mit bekannten Objekten fallen lassen, schauen Sie sich die $k$ nächstgelegenen Nachbarn an. Wenn die meisten dieser Nachbarn „Katzen“ sind, raten Sie, dass das neue Objekt ebenfalls eine Katze ist.

Das Problem ist: Wie misst man die „Nähe“, wenn die Objekte komplexe Netzwerke (Graphen) sind, die keine Standardgröße oder -form haben? Man kann den Abstand zwischen zwei Punkten auf einer Karte nicht einfach messen.

Dieses Paper stellt eine clevere neue Methode vor, um diesen Abstand mithilfe von etwas namens Gromov–Wasserstein (GW) und Fused Gromov–Wasserstein (fGW) zu messen. Hier ist die Aufschlüsselung in einfachen Worten:

1. Das Problem: Äpfel mit Birnen vergleichen (und Orangen mit Flugzeugen)

Normalerweise müssen Dinge, die man vergleichen möchte, die gleiche Größe haben. Wenn Sie zwei Graphen (Netzwerke aus Punkten und Linien) vergleichen wollen, zwingen herkömmliche Methoden diese oft dazu, die gleiche Größe zu haben oder sie in eine einzige Liste von Zahlen (ein „Embedding“) umzuwandeln. Das ist so, als würde man versuchen, einen kleinen Stammbaum mit einem riesigen Konzernorganigramm zu vergleichen, indem man beide in dieselbe winzige Box quetscht. Dabei gehen Informationen verloren.

2. Die Lösung: Das „gestaltwandelnde“ Lineal

Die Autoren verwenden ein mathematisches Werkzeug namens Gromov–Wasserstein-Distanz.

Die Analogie: Stellen Sie sich vor, Sie haben zwei verschiedene Städte. Die eine ist ein Raster (wie Manhattan), die andere ist ein Geflecht aus gewundenen Straßen (wie San Francisco). Sie sehen völlig unterschiedlich aus.
Die GW-Magie: GW fragt nicht direkt nach den Straßen, sondern: „Wenn ich die Menschen in Stadt A magisch so umverteilen könnte, dass sie der Bevölkerungsdichte von Stadt B entsprechen, wie sehr würde sich der ‚Beziehungsabstand‘ zwischen den Nachbarn ändern?“
Es ist egal, ob die Städte 100 oder 1.000 Einwohner haben. Es geht nur um das Muster der Beziehungen. Wenn Stadt A einen „Hub“ mit vielen Verbindungen hat und Stadt B einen ähnlichen „Hub“, sagt GW: „Diese beiden Städte sind strukturell ähnlich“, selbst wenn sie auf einer Karte völlig anders aussehen.

3. Das Hinzufügen von „Merkmalen“: Die fusionierte Version

Manchmal besitzen die Punkte in Ihrem Netzwerk zusätzliche Informationen. Zum Beispiel hat jedes Atom in einem Molekülgraphen einen bestimmten Typ (Kohlenstoff, Sauerstoff). In einem sozialen Graphen hat jede Person einen Jobtitel.

Die Analogie: Stellen Sie sich erneut vor, Sie vergleichen zwei Städte. GW betrachtet die Straßenmuster. Aber was, wenn Sie auch die Arten der Gebäude vergleichen möchten?
Die fGW-Magie: Die Fused Gromov–Wasserstein (fGW)-Distanz macht beides gleichzeitig. Sie prüft, ob die Straßenmuster übereinstimmen und ob die Gebäude an ähnlichen Stellen denselben Typ haben. Es ist wie ein Lineal, das sowohl die Form der Stadt als auch die Farbe der Häuser misst.

4. Der große Anspruch: „Es funktioniert immer“ (Universelle Konsistenz)

Die Autoren haben nicht nur ein neues Lineal gebaut; sie haben mathematisch bewiesen, dass die Verwendung dieses Lineals mit der $k$ -NN-Methode langfristig immer funktioniert.

Die Garantie: Sie haben bewiesen, dass Ihr $k$ -NN-Klassifizierer unter Verwendung dieser neuen Distanzen schließlich so genau wird, wie es theoretisch möglich ist, wenn Sie immer mehr Trainingsdaten (mehr Beispiele von Graphen) hinzufügen.
Die Einschränkung: Dieser Beweis gilt für Graphen jeglicher Größe, solange Sie bestimmte Regeln befolgen, wie Sie die „Nachbaranzahl“ ( $k$ ) im Zuge Ihres Datenwachstums wählen. Sie haben gezeigt, dass der Raum aller möglichen Graphen gut genug strukturiert ist, damit diese Mathematik Bestand hat.

5. Das Experiment: Hilft es tatsächlich?

Die Autoren haben ihre Methode an realen Daten getestet:

Moleküle: Sortierung von Chemikalien basierend auf ihrer Struktur und ihren Atomtypen.
Soziale Netzwerke: Sortierung von Kollaborationsnetzwerken von Filmen (z. B. „Action“-Filme vs. „Romanze“-Filme).
Synthetische Daten: Künstlich erzeugte Netzwerke, um die Grenzen der Methode zu testen.

Die Ergebnisse:

Ihre Methode (GW- $k$ -NN und fGW- $k$ -NN) schnitt sehr gut ab und übertraf oft oder erreichte das Niveau populärer Methoden wie Graph Neural Networks (GCNs) und komplexer Graph-Kernel.
Wichtigste Erkenntnis: Bei Molekülen mit Zusatzdaten (Atomtypen) war die „fusionierte“ Version (fGW) der klare Gewinner. Sie zeigte, dass es besser ist, sowohl die Struktur als auch die Merkmale gemeinsam zu betrachten, als nur eines von beiden.
Effizienz: Obwohl die Mathematik schwerfällig ist, war die Methode überraschend schnell und effizient im Vergleich zu anderen komplexen Methoden, insbesondere bei Graphen ohne Attributwerte.

Zusammenfassung

Das Paper besagt: „Wir haben einen Weg gefunden, wie man misst, wie ähnlich sich zwei komplexe Netzwerke sind, unabhängig von ihrer Größe oder Form. Wir haben bewiesen, dass Ihr Klassifizierer, wenn Sie dieses Maß verwenden, um neue Netzwerke basierend auf ihren nächsten Nachbarn zu sortieren, mathematisch garantiert immer besser wird, je mehr Daten Sie ihm zufüttern. Unsere Tests zeigen, dass dies bei realen Problemen wie der Identifizierung von Molekülen oder Filmgenres hervorragend funktioniert.“

Was sie NICHT behauptet haben:

Sie haben nicht behauptet, dass dies für jede Art von Daten funktioniert (nur für Graphen und strukturierte Objekte).
Sie haben nicht behauptet, dass dies die schnellste Methode der Welt ist (sie merkten an, dass sie rechenintensiv sein kann, zeigten aber, dass sie konkurrenzfähig ist).
Sie haben dies nicht auf medizinische Diagnosen oder klinische Anwendungen angewendet; sie blieben strikt bei Aufgaben der Graph-Klassifizierung.

Technische Zusammenfassung: $k$ -Nächste-Nachbarn in der Gromov–Wasserstein-Räume

Problemstellung
Die Arbeit adressiert die Herausforderung der Klassifizierung von graphenstrukturierten Daten, einschließlich nicht-attributierter Graphen und knotenattributierter Graphen, innerhalb eines rigorosen Metriatlern-Frameworks. Traditionelle $k$ -Nächste-Nachbarn ( $k$ -NN)-Klassifikatoren stützen sich auf Distanzfunktionen, die in euklidischen oder Standard-Metrikräumen definiert sind. Graphen besitzen jedoch oft komplexe Strukturen, in denen ein direkter Vergleich schwierig ist, insbesondere wenn Graphen unterschiedliche Knotenzahlen aufweisen oder keine kanonische Einbettung besitzen. Während die Gromov–Wasserstein (GW)-Distanz einen Rahmen für den Vergleich von metrischen Maßräumen (mm-Räumen) bietet und die fusionierte Gromov–Wasserstein (fGW)-Distanz dies zur Einbeziehung von Knotenmerkmalen erweitert, waren die theoretischen Eigenschaften von $k$ -NN-Klassifikatoren, die in diesen spezifischen Metrikräumen operieren, zuvor unbekannt. Insbesondere war unklar, ob $k$ -NN universell konsistent ist (gegen das optimale Bayes-Risiko konvergiert), wenn der zugrunde liegende Raum der Raum der Graphen ist, der mit GW- oder fGW-Distanzen ausgestattet ist.

Methodik
Die Autoren implementieren die $k$ -NN-Klassifizierung unter Verwendung von GW- und fGW-Distanzen und untersuchen deren theoretische Konsistenz. Der Kern ihrer Methodik besteht darin, die topologischen Eigenschaften der betrachteten Metrikräume zu etablieren, um die für eine universelle Konsistenz erforderlichen Bedingungen zu erfüllen.

Definitionen der Metrikräume:
- GW-Raum ( $\mathbb{X}$ ): Der Raum der Äquivalenzklassen von mm-Räumen mit endlicher Unterstützung und gleichmäßiger Wahrscheinlichkeitsmaße, ausgestattet mit der $p=2$ Gromov–Wasserstein-Distanz. Dies modelliert nicht-attributierte Graphen.
- fGW-Raum ( $\mathbb{Y}^f$ ): Der Raum der schwachen Isomorphieklassen strukturierter Objekte (mm-Räume mit Feature-Maps in $\mathbb{R}^d$ ), ausgestattet mit der fusionierten Gromov–Wasserstein-Distanz ( $p=1, q=2$ ). Dies modelliert knotenattributierte Graphen.
Theoretischer Rahmen:
Die Autoren stützen sich auf etablierte Ergebnisse der Lerntheorie (speziell Chaudhuri und Dasgupta [9]), die besagen, dass $k$ -NN auf einem separablen Metrikraum universell konsistent ist, wenn der Raum eine $\sigma$ -endliche metrische Dimension besitzt (eine Eigenschaft, die mit der Lebesgue-Differenzierbarkeitbedingung zusammenhängt). Um dies für GW- und fGW-Räume zu beweisen, konstruieren die Autoren:
- Finite-dimensionale Modelle für $n$ -Punkt-Räume innerhalb dieser Frameworks.
- Den Nachweis der Existenz von Bi-Lipschitz-Abbildungen zwischen dem Raum der $n$ -Punkt-Graphen und spezifischen Quotientenräumen euklidischer Matrizen (für GW) sowie Produkträumen von Matrizen und Feature-Vektoren (für fGW).
- Den Beweis, dass diese Quotientenräume eine endliche Assouad-Nagata-Dimension besitzen.
- Die Nutzung von Lemma 2.4, um zu zeigen, dass die Existenz von Bi-Lipschitz-Abbildungen auf Räume mit endlicher Dimension impliziert, dass die Zielräume ( $\mathbb{X}$ und $\mathbb{Y}^f$ ) eine $\sigma$ -endliche metrische Dimension besitzen.
Numerische Experimente:
Die Autoren evaluieren die Leistungsfähigkeit von GW- $k_n$ -NN und fGW- $k_n$ -NN auf sieben Benchmark-Datensätzen:
- Attributierte Graphen: BZR, COX-2 und PROTEINS (molekulare Datensätze).
- Nicht-attributierte Graphen: IMDb-B, IMDb-M (soziale Netzwerke) und zwei synthetische Datensätze (ERSBM1, ERSBM2).
- Baselines: Vergleiche mit Graph Convolutional Networks (GCN), verschiedenen Graph-Kernel-Methoden (Shortest Path, Graphlet, HOPPER, Propagation) und SVMs unter Verwendung von GW/fGW-Kerneln.

Wesentliche Beiträge
Der primäre Beitrag dieser Arbeit ist der Beweis der universellen Konsistenz für $k$ -NN-Klassifikatoren im Kontext der Graph-Klassifizierung unter Verwendung von GW- und fGW-Distanzen.

Theoretische Ergebnisse:
- Theorem 1.8: Beweist, dass der GW- $k_n$ -NN-Klassifikator universell schwach konsistent auf dem Raum der Graphen $(\mathbb{X}, GW_2)$ unter den Bedingungen $k \to \infty$ und $k/n \to 0$ ist. Er ist universell stark konsistent, falls $k/\log(n) \to \infty$ .
- Theorem 1.9: Beweist dieselben Konsistenzresultate für den fGW- $k_n$ -NN-Klassifikator auf dem Raum der knotenattributierten Graphen $(\mathbb{Y}^f, fGW_{\alpha,1,2})$ .
- Diese Ergebnisse werden dadurch etabliert, dass sowohl die GW- als auch die fGW-Räume als separabel nachgewiesen werden und eine $\sigma$ -endliche metrische Dimension besitzen, eine Eigenschaft, die über Bi-Lipschitz-Einbettungen in Quotientenräume euklidischer Räume abgeleitet wurde.
Empirische Ergebnisse:
- Auf attributierten Graph-Datensätzen (BZR, COX-2, PROTEINS) erreichte fGW- $k_n$ -NN konsistent die höchste durchschnittliche Genauigkeit und übertraf damit GCNs und andere kernelbasierte Methoden. GW- $k_n$ -NN zeigte ebenfalls eine wettbewerbsfähige Leistung.
- Auf nicht-attributierten Datensätzen erreichte GW- $k_n$ -NN eine perfekte Genauigkeit (100 %) auf dem synthetischen Datensatz ERSBM2 und eine starke Leistung auf IMDb-B, wobei es oft Graph-Kernel und GCNs übertraf.
- Die Autoren merken an, dass GW/fGW-Methoden zwar interpretierbar sind (kleine Distanzen implizieren strukturelle Ähnlichkeit), aber im Vergleich zu einigen Kernel-Methoden rechenintensiv sein können, obwohl sie in bestimmten Kontexten Effizienzverbesserungen gegenüber SVMs mit GW-Kerneln bieten.

Bedeutung und Behauptungen
Das Paper behauptet, ein theoretisches Fundament für die Verwendung von metrischen Klassifikatoren wie $k$ -NN innerhalb des Gromov–Wasserstein-Frameworks geschaffen zu haben. Durch den Beweis der universellen Konsistenz argumentieren die Autoren, dass diese Methoden nicht bloß heuristisch, sondern theoretisch fundiert für Graph-Klassifizierungsaufgaben sind.

Die Bedeutung liegt in der Überbrückung der Lücke zwischen der Optimalen Transporttheorie und der statistischen Lerntheorie für strukturierte Daten. Die Autoren betonen, dass ihr Ansatz einen „hochgradig interpretierbaren Rahmen“ bietet, in dem die Distanz zwischen Graphen direkt die strukturelle Ähnlichkeit misst (Isomorphie impliziert eine Distanz von Null). Sie stellen explizit fest, dass dies nach ihrem Wissen die erste Anwendung von GW- $k$ -NN auf die Graph-Klassifizierung und der erste theoretische Beweis seiner Konsistenz ist.

Das Paper bleibt hinsichtlich zukünftiger Verallgemeinerungen bescheiden. Es räumt ein, dass während die Konsistenz für spezifische Parameter ( $p=2$ für GW, $p=1, q=2$ für fGW) bewiesen wurde, es ein offenes Problem bleibt, ob diese Ergebnisse für andere Parameterwahl oder im allgemeinsten Z-Gromov–Wasserstein-Setting gelten. Die Autoren vermuten, dass – ähnlich wie beim Wasserstein-Raum – die universelle Konsistenz ohne spezifische Einschränkungen der betrachteten Räume nicht in voller Allgemeingültigkeit bestehen könnte.