📊 statistics

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

Dit artikel implementeert $k$ -nearest neighbors-classificatie met behulp van Gromov--Wasserstein en fused Gromov--Wasserstein-afstanden om grafen en met knoopkenmerken voorzien van grafen respectievelijk te vergelijken, en bewijst de universele consistentie van deze classificaties much terwijl het hun sterke empirische prestaties over meerdere datasets demonstreert.

Oorspronkelijke auteurs: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Gepubliceerd 2026-06-10

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een enorme stapel verschillende objecten probeert te sorteren. Sommige zijn eenvoudige vormen, andere zijn complexe netwerken zoals metrokaarten of sociale kringen. Je doel is om te achterhalen bij welke categorie een nieuw, onbekend object hoort door te kijken naar de objecten die je al kent. Dit is de taak van een $k$ -Nearest Neighbors ( $k$ -NN) classifier.

Denk aan $k$ -NN als een "populariteitswedstrijd" onder je buren. Als je een nieuw object in een kamer met bekende objecten laat vallen, kijk je naar de $k$ dichtstbijzijnde buren. Als de meeste van die buren "katten" zijn, gok je dat het nieuwe object ook een kat is.

Het probleem is: Hoe meet je "nabijheid" wanneer de objecten complexe netwerken (grafen) zijn zonder standaard grootte of vorm? Je kunt niet simpelweg de afstand tussen twee punten op een kaart meten.

Dit artikel introduceert een slimme nieuwe manier om die afstand te meten met behulp van iets dat Gromov–Wasserstein (GW) en Fused Gromov–Wasserstein (fGW) wordt genoemd. Hier is de uitleg in eenvoudige termen:

1. Het Probleel: Appels met Appels Vergelijken (en Oranges met Airplanes)

Normaal gesproken, om twee dingen te vergelijken, moeten ze dezelfde grootte hebben. Als je twee grafen (netwerken van stippen en lijnen) wilt vergelijken, dwingen traditionele methoden hen vaak om dezelfde grootte te hebben of transformeren ze ze naar een enkele lijst met getallen (een "embedding"). Dit is alsof je probeert een kleine stamboom te vergelijken met een enorme bedrijfsstructuur door ze allebei in hetzelfde kleine doosje te proppen. Je verliest informatie.

2. De Oplossing: Het "Vormveranderende" Liniaal

De auteurs gebruiken een wiskundig hulpmiddel genaamd de Gromov–Wasserstein afstand.

De Analogie: Stel je voor dat je twee verschillende steden hebt. De ene is een raster (zoals Manhattan), en de andere is een web van kronkelende wegen (zoals San Francisco). Ze zien er totaal anders uit.
De GW Magie: In plaats van de straten direct te vergelijken, vraagt GW: "Als ik de mensen in Stad A magisch zou kunnen herverdelen om te passen bij de bevolkingsdichtheid van Stad B, hoeveel zou de 'relatieafstand' tussen buren dan veranderen?"
Het geeft niet om of de steden 100 mensen of 1.000 mensen hebben. Het geeft alleen om het patroon van relaties. Als Stad A een "hub" heeft met veel verbindingen en Stad B een vergelijkbare "hub" heeft, zegt GW: "Deze twee steden zijn structureel vergelijkbaar," zelfs als ze er op een kaart anders uitzien.

3. "Kenmerken" Toevoegen: De Gefuseerde Versie

Soms hebben de stippen in je netwerk extra informatie. Bijvoorbeeld, in een molecuul-grafiek heeft elk atoom een specifiek type (Koolstof, Zuurstof). In een sociale grafiek heeft elke persoon een functietitel.

De Analogie: Stel je weer voor dat je twee steden vergelijkt. GW kijkt naar de wegpatronen. Maar wat als je ook de typen gebouwen wilt vergelijken?
De fGW Magie: De Fused Gromov–Wasserstein (fGW) afstand doet beide tegelijk. Het controleert of de wegpatronen overeenkomen en of de gebouwen op vergelijkbare plekken hetzelfde type zijn. Het is als een liniaal die zowel de vorm van de stad als de kleur van de huizen meet.

4. De Grote Claim: "Het Werkt Altijd" (Universele Consistentie)

De auteurs hebben niet alleen een nieuwe liniaal gebouwd; ze hebben bewezen dat het gebruik van deze liniaal met de $k$ -NN methode op de lange termijn altijd werkt.

De Garantie: Ze bewezen dat als je steeds meer trainingsdata toevoegt (meer voorbeelden van grafen), je $k$ -NN classifier met deze nieuwe afstanden uiteindelijk net zo nauwkeurig wordt als theoretisch mogelijk is.
De Kanttekening: Dit bewijs geldt voor grafen van elke grootte, zolang je bepaalde regels volgt over hoe je het "aantal buren" ( $k$ ) kiest naarmate je data groeit. Ze hebben aangetoond dat de ruimte van alle mogelijke grafen goed genoeg werkt zodat deze wiskunde standhoudt.

5. Het Experiment: Helpt het echt?

De auteurs hebben hun methode getest op echte gegevens:

Moleculen: Het sorteren van chemicaliën op basis van hun structuur en atoomtypen.
Sociale Netwerken: Het sorteren van film-samenwerkingsnetwerken (bijv. "Actie" films versus "Romantiek" films).
Synthetische Data: Bepaald door mensen gemaakte netwerken om de grenzen van de methode te testen.

De Resultaten:

Hun methode (GW- $k$ -NN en fGW- $k$ -NN) presteerde erg goed, en versloeg of evenaarde vaak populaire methoden zoals Graph Neural Networks (GCNs) en complexe graph kernels.
Belangrijkste Bevinding: Voor moleculen met extra data (atoomtypen), was de "Fused" versie (fGW) de duidelijke winnaar. Het toonde aan dat het kijken naar zowel de structuur als de kenmerken samen beter is dan kijken naar slechts één van beide.
Efficiëntie: Hoewel de wiskunde zwaar is, was de methode verrassend snel en efficiënt vergeleken met sommige andere complexe methoden, vooral voor niet-geattribueerde grafen.

Samenvatting

Het artikel zegt: "We hebben een manier gevonden om te meten hoe vergelijkbaar twee complexe netwerken zijn, ongeacht hun grootte of vorm. We hebben bewezen dat als je deze meting gebruikt om nieuwe netwerken te sorteren op basis van hun dichtstbijzijnde buren, de methode wiskundig gegarandeerd beter en beter wordt naarmate je er meer data in voert. Onze tests laten zien dat het geweldig werkt voor echte problemen zoals het identificeren van moleculen en filmgenres."

Wat ze NIET hebben geclaimd:

Ze claimden niet dat dit voor elke denkbare soort data werkt (alleen voor grafen en gestructureerde objecten).
Ze claimden niet dat dit de snelste methode ter wereld is (ze merkten op dat het computationeel zwaar kan zijn, hoewel ze lieten zien dat het competitief is).
Ze hebben dit niet toegepast op medische diagnoses of klinisch gebruik; ze bleven strikt bij taken van grafenclassificatie.

Technische Samenvatting: $k$ -Nearest Neighbors in de Gromov–Wasserstein-ruimte

Probleemstelling
Het artikel behandelt de uitdaging van het classificeren van graafgestructureerde data, inclusief zowel niet-geattributueerde grafen als grafen met knoop-attributen, binnen een rigoureus metrijs leerraamwerk. Traditionele $k$ -nearest neighbors ( $k$ -NN) classificatiesystemen vertrouwen op afstandsfuncties die gedefinieerd zijn in Euclidische of standaard metriële ruimtes. Grafen bezitten echter vaak complexe structuren waarbij directe vergelijking moeilijk is, vooral wanneer grafen een verschillend aantal knopen hebben of geen canonieke inbedding bezitten. Hoewel de Gromov–Wasserstein (GW) afstand een raamwerk biedt voor het vergelijken van metriële metrische ruimtes (mm-ruimtes) en de fused Gromov–Wasserstein (fGW) afstand dit uitbreidt naar knoopkenmerken, waren de theoretische eigenschappen van $k$ -NN classificatiesystemen die opereren binnen deze specifieke metriële ruimtes voorheen onbekend. Specifiek was onduidelijk of $k$ -NN universeel consistent is (convergeert naar de optimale Bayes-risico) wanneer de onderliggende ruimte de ruimte van grafen is, uitgerust met GW- of fGW-afstanden.

Methodologie
De auteurs implementeren $k$ -NN classificatie met behulp van GW- en fGW-afstanden en onderzoeken de theoretische consistentie hiervan. De kern van hun methodologie bestaat uit het vaststellen van de topologische eigenschappen van de metriële ruimtes in kwestie om te voldoen aan de voorwaarden die vereist zijn voor universele consistentie.

Definities van de Metriële Ruimtes:
- GW-ruimte ( $\mathbb{X}$ ): De ruimte van equivalentieklassen van mm-ruimtes met eindige ondersteuning en een uniforme waarschijnlijkheidsmaat, uitgerust met de $p=2$ Gromov–Wasserstein afstand. Dit modelleert niet-geattributueerde grafen.
- fGW-ruimte ( $\mathbb{Y}^f$ ): De ruimte van zwakke isomorfieklassen van gestructureerde objecten (mm-ruimtes met feature-kaarten naar $\mathbb{R}^d$ ), uitgerust met de fused Gromov–Wasserstein afstand ( $p=1, q=2$ ). Dit modelleert grafen met knoop-attributen.
Theoretisch Raamwerk:
De auteurs steunen op gevestigde resultaten in de leertheorie (specifiek Chaudhuri en Dasgupta [9]) die stellen dat $k$ -NN universeel consistent is op een scheidbare metriële ruimte als de ruimte beschikt over een $\sigma$ -eindige metriële dimensie (een eigenschap gerelateerd aan de Lebesgue-differentiatievoorwaarde). Om dit voor GW- en fGW-ruimtes te bewijzen, doen de auteurs het volgende:
- Construeren einddimensionale modellen voor $n$ -puntsruimtes binnen deze raamwerken.
- Demonstreren het bestaan van bi-Lipschitz afbeeldingen tussen de ruimte van $n$ -puntsgrafen en specifieke quotientruimtes van Euclidische matrices (voor GW) en productruimtes van matrices en feature-vectoren (voor fGW).
- Bewijzen dat deze quotientruimtes een eindige Assouad-Nagata dimensie hebben.
- Gebruiken Lemma 2.4 om aan te tonen dat het bestaan van bi-Lipschitz afbeeldingen naar ruimtes met een eindige dimensie impliceert dat de doelruimtes ( $\mathbb{X}$ en $\mathbb{Y}^f$ ) een $\sigma$ -eindige metriële dimensie hebben.
Numerieke Experimenten:
De auteurs evalueren de prestaties van GW- $k_n$ -NN en fGW- $k_n$ -NN op zeven benchmark-datasets:
- Geattributueerde Grafen: BZR, COX-2 en PROTEINS (moleculaire datasets).
- Niet-geattributueerde Grafen: IMDb-B, IMDb-M (sociale netwerken), en twee synthetische datasets (ERSBM1, ERSBM2).
- Baselines: Vergelijkingen met Graph Convolutional Networks (GCN), diverse graaf-kernelmethoden (Shortest Path, Graphlet, HOPPER, Propagation) en SVM's met GW/fGW-kernels.

Belangrijkste Bijdragen
De primaire bijdrage van dit werk is het bewijs van universele consistentie voor $k$ -NN classificatiesystemen in de context van graafclassificatie met behulp van GW- en fGW-afstanden.

Theoretische Resultaten:
- Theorem 1.8: Bewijst dat de GW- $k_n$ -NN classifier universeel zwak consistent is op de ruimte van grafen $(\mathbb{X}, GW_2)$ onder de voorwaarden $k \to \infty$ en $k/n \to 0$ . Het is universeel sterk consistent indien $k/\log(n) \to \infty$ .
- Theorem 1.9: Bewijst dezelfde consistentie-resultaten voor de fGW- $k_n$ -NN classifier op de ruimte van grafen met knoop-attributen $(\mathbb{Y}^f, fGW_{\alpha,1,2})$ .
- Deze resultaten worden vastgesteld door aan te tonen dat beide ruimtes scheidbaar zijn en beschikken over een $\sigma$ -eindige metriële dimensie, een eigenschap die is afgeleid via bi-Lipschitz inbeddingen in quotientruimtes van Euclidische ruimtes.
Empirische Resultaten:
- Op geattributueerde graaf-datasets (BZR, COX-2, PROTEINS) behaalde fGW- $k_n$ -NN consistent de hoogste gemiddelde nauwkeurigheid, waarmee het GCN's en andere kernel-gebaseerde methoden overtrof. GW- $k_n$ -NN presteerde ook competitief.
- Op niet-geattributueerde datasets behaalde GW- $k_n$ -NN een perfecte nauwkeurigheid (100%) op de synthetische dataset ERSBM2 en sterke prestaties op IMDb-B, waarbij het vaak graaf-kernels en GCN's overtrof.
- De auteurs merken op dat hoewel GW/fGW-methoden interpreteerbaar zijn (kleine afstanden impliceren structurele gelijkenis), ze computationeel intensiever kunnen zijn dan sommige kernel-methoden, hoewel ze efficiëntieverbeteringen bieden ten opzichte van SVM's met GW-kernels in bepaalde contexten.

Betekenis en Claims
Het artikel beweert een theoretische fundering te hebben gelegd voor het gebruik van metriële classificatiesystemen zoals $k$ -NN binnen het Gromov–Wasserstein-raamwerk. Door universele consistentie te bewijzen, argumenteren de auteurs dat deze methoden niet louter heuristisch zijn, maar theoretisch solide voor graafclassificatietaken.

De betekenis ligt in het overbruggen van de kloof tussen de optimale transporttheorie en statistische leertheorie voor gestructureerde data. De auteurs benadrukken dat hun aanpak een "zeer interpreteerbaar raamwerk" biedt waarbij de afstand tussen grafen direct de structurele gelijkenis meet (isomorfie impliceert een afstand van nul). Zij stellen expliciet dat, naar hun weten, dit de eerste toepassing van GW- $k$ -NN op graafclassificatie is en het eerste theoretische bewijs van de consistentie ervan.

Het artikel blijft bescheiden wat betreft toekomstige generalisaties. Er wordt erkend dat hoewel consistentie is bewezen voor specifieke parameters ( $p=2$ voor GW, $p=1, q=2$ voor fGW), het een open vraag blijft of deze resultaten standhouden voor andere parameterkeuzes of in de meest algemene Z-Gromov–Wasserstein settings. De auteurs vermoeden dat, vergelijkbaar met de Wasserstein-ruimte, universele consistentie mogelijk niet in volledige algemeenheid standhoudt zonder specifieke restricties op de ruimtes van belang.