📊 statistics

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

Cet article implémente la classification des $k$ plus proches voisins en utilisant les distances de Gromov--Wasserstein et de Gromov--Wasserstein fusionné pour comparer respectivement des graphes et des graphes à attributs de nœuds, et prouve la cohérence universelle de ces classifieurs tout en démontrant leur forte performance empirique sur de multiples jeux de données.

Auteurs originaux : Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Publié 2026-06-10

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Kaitlyn Hohmeier, Nicolas Fraiman, Caroline Moosmueller

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de trier un immense tas d'objets différents. Certains sont des formes simples, d'autres sont des réseaux complexes comme des plans de métro ou des cercles sociaux. Votre objectif est de déterminer à quelle catégorie appartient un nouvel objet, encore inconnu, en observant les objets que vous connaissez déjà. C'est le travail d'un classificateur $k$ -plus proches voisins ( $k$ -NN).

Considérez le $k$ -NN comme un « concours de popularité » entre vos voisins. Si vous déposez un nouvel objet dans une pièce remplie d'objets connus, vous regardez les $k$ plus proches d'entre eux. Si la plupart de ces voisins sont des « chats », vous devinez que le nouvel objet est aussi un chat.

Le problème est le suivant : Comment mesurer la « proximité » lorsque les objets sont des réseaux complexes (graphes) sans taille ni forme standard ? Vous ne pouvez pas simplement mesurer la distance entre deux points sur une carte.

Ce document présente une nouvelle façon ingénieuse de mesurer cette distance en utilisant ce qu'on appelle le Gromov–Wasserstein (GW) et le Gromov–Wasserstein fusionné (fGW). Voici la décomposition en termes simples :

1. Le problème : Comparer des pommes avec des oranges (et des oranges avec des avions)

Habituellement, pour comparer deux choses, elles doivent avoir la même taille. Si vous voulez comparer deux graphes (réseaux de points et de lignes), les méthodes traditionnelles les forcent souvent à avoir la même taille ou les transforment en une liste unique de nombres (un « embedding »). C'est comme essayer de comparer un petit arbre généalogique à un immense organigramme d'entreprise en les faisant tous deux entrer dans la même petite boîte. Vous perdez de l'information.

2. La solution : La règle « changeuse de forme »

Les auteurs utilisent un outil mathématique appelé distance de Gromov–Wasserstein.

L'analogie : Imaginez que vous avez deux villes différentes. L'une est une grille (comme Manhattan), et l'autre est un réseau de routes sinueuses (comme San Francisco). Elles ont l'air totalement différentes.
La magie du GW : Au lieu de comparer les rues directement, le GW demande : « Si je pouvais magiquement réorganiser les habitants de la Ville A pour correspondre à la densité de population de la Ville B, à quel point la "distance de relation" entre les voisins changerait-elle ? »
Il ne se soucie pas de savoir si les villes comptent 100 personnes ou 1 000 personnes. Il ne s'intéresse qu'au schéma des relations. Si la Ville A possède un « hub » avec de nombreuses connexions et que la Ville B possède un « hub » similaire, le GW dit : « Ces deux villes sont structurellement similaires », même si elles ne se ressemblent pas sur une carte.

3. Ajouter des « caractéristiques » : La version fusionnée

Parfois, les points de votre réseau possèdent des informations supplémentaires. Par exemple, dans un graphe de molécule, chaque atome a un type spécifique (Carbone, Oxygène). Dans un grapque social, chaque personne a un titre de poste.

L'analogie : Imaginons à nouveau la comparaison de deux villes. Le GW examine les schémas routiers. Mais et si vous vouliez aussi comparer les types de bâtiments ?
La magie du fGW : La distance Gromov–Wasserstein fusionnée (fGW) fait les deux à la fois. Elle vérifie si les schémas routiers correspondent et si les bâtiments situés dans des endroits similaires sont du même type. C'est comme une règle qui mesure à la fois la forme de la ville et la couleur des maisons.

4. La grande affirmation : « Cela fonctionne toujours » (Cohérence universelle)

Les auteurs n'ont pas seulement construit une nouvelle règle ; ils ont prouvé mathématiquement que l'utilisation de cette règle avec la méthode $k$ -NN fonctionne toujours sur le long terme.

La garantie : Ils ont prouvé que si vous ajoutez de plus en plus de données d'entraînement (plus d'exemples de graphes), votre classificateur $k$ -NN utilisant ces nouvelles distances deviendra aussi précis que cela est théoriquement possible.
Le bémol : Cette preuve est vraie pour des graphes de n'importe quelle taille, tant que vous suivez des règles spécifiques sur la façon de choisir votre « nombre de voisins » ( $k$ ) à mesure que vos données augmentent. Ils ont montré que l'espace de tous les graphes possibles se comporte suffisamment bien pour que ce calcul tienne la route.

5. L'expérience : Est-ce que cela aide réellement ?

Les auteurs ont testé leur méthode sur des données réelles :

Molécules : Trier des produits chimiques basés sur leur structure et leurs types d'atomes.
Réseaux sociaux : Trier des réseaux de collaboration cinématographique (par exemple, les films d'« Action » par rapport aux films de « Romance »).
Données synthétiques : Des réseaux fabriqués de toutes pièces pour tester les limites.

Les résultats :

Leur méthode (GW- $k$ -NN et fGW- $k$ -NN) a très bien performé, égalant ou dépassant souvent d'autres méthodes populaires comme les réseaux de neurones sur graphes (GCN) et les noyaux de graphes complexes.
Résultat clé : Pour les molécules avec des données supplémentaires (types d'atomes), la version « fusionnée » (fGW) était la grande gagnante. Elle a montré que regarder à la fois la structure et les caractéristiques ensemble est préférable à l'examen d'une seule de ces composantes.
Efficacité : Bien que les mathématiques soient lourdes, la méthode est étonnamment rapide et efficace par rapport à certaines autres méthodes complexes, surtout pour les graphes non attribués.

Résumé

Le papier dit : « Nous avons trouvé un moyen de mesurer à quel point deux réseaux complexes sont similaires, indépendamment de leur taille ou de leur forme. Nous avons prouvé que si vous utilisez cette mesure pour trier de nouveaux réseaux en fonction de leurs plus proches voisins, la méthode est mathématiquement garantie de s'améliorer de plus en plus à mesure que vous lui fournissez plus de données. Nos tests montrent que cela fonctionne très bien sur des problèmes du monde réel comme l'identification de molécules ou de genres cinématographiques. »

Ce qu'ils n'ont PAS affirmé :

Ils n'ont pas affirmé que cela fonctionne pour chaque type de données possible (uniquement pour les graphes et les objets structurés).
Ils n'ont pas affirmé que c'est la méthode la plus rapide au monde (ils ont noté qu'elle peut être coûteuse en termes de calcul, bien qu'ils aient montré qu'elle est compétitive).
Ils ne l'ont pas appliqué aux diagnostics médicaux ou aux utilisations cliniques ; ils se sont strictement concentrés sur les tâches de classification de graphes.

Résumé Technique : $k$ -plus proches voisins dans l'espace de Gromov–Wasserstein

Énoncé du Problème
Le papier traite du défi de la classification de données structurées sous forme de graphes, incluant les graphes sans attributs et les graphes avec attributs de nœuds, dans un cadre rigoureux d'apprentissage métrique. Les classifieurs traditionnels des $k$ -plus proches voisins ( $k$ -NN) reposent sur des fonctions de distance définies dans des espaces euclidiens ou des espaces métriques standards. Cependant, les graphes possèdent souvent des structures complexes où la comparaison directe est difficile, particulièrement lorsque les graphes ont des nombres de nœuds différents ou manquent d'un plongement canonique. Bien que la distance de Gromov–Wasserstein (GW) fournisse un cadre pour comparer les espaces de mesures métriques (mm-spaces) et que la distance de Gromov–Wasserstein fusionnée (fGW) étende cela pour inclure les caractéristiques des nœuds, les propriétés théoriques des classifieurs $k$ -NN opérant dans ces espaces métriques spécifiques étaient auparavant inconnues. Plus précisément, il n'était pas clair si le $k$ -NN est universellement consistant (convergeant vers le risque de Bayes optimal) lorsque l'espace sous-jacent est l'espace des graphes équipé des distances GW ou fGW.

Méthodologie
Les auteurs implémentent la classification $k$ -NN en utilisant les distances GW et fGW et étudient leur cohérence théorique. Le cœur de leur méthodologie consiste à établir les propriétés topologiques des espaces métriques en question afin de satisfaire les conditions requises pour la cohérence universelle.

Définitions des Espaces Métriques :
- Espace GW ( $\mathbb{X}$ ) : L'espace des classes d'équivalence d'mm-spaces avec support fini et mesure de probabilité uniforme, équipé de la distance de Gromov–Wasserstein $p=2$ . Cela modélise les graphes sans attributs.
- Espace fGW ( $\mathbb{Y}^f$ ) : L'espace des classes d'isomorphisme faible d'objets structurés (mm-spaces avec des applications de caractéristiques dans $\mathbb{R}^d$ ), équipé de la distance de Gromov–Wasserstein fusionnée ( $p=1, q=2$ ). Cela modélise les graphes avec attributs de nœuds.
Cadre Théorique :
Les auteurs s'appuient sur des résultats établis en théorie de l'apprentissage (spécifiquement Chaudhuri et Dasgupta [9]) qui stipulent que le $k$ -NN est universellement consistant sur un espace métrique séparable si l'espace possède une dimension métrique $\sigma$ -finie (une propriété liée à la condition de différenciation de Lebesgue). Pour prouver cela pour les espaces GW et fGW, les auteurs :
- Construisent des modèles de dimension finie pour des espaces à $n$ points au sein de ces cadres.
- Démontrent l'existence de applications bi-Lipschitziennes entre l'espace des graphes à $n$ points et des espaces quotients spécifiques de matrices euclidiennes (pour GW) et d'espaces produits de matrices et de vecteurs de caractéristiques (pour fGW).
- Prouvent que ces espaces quotients possèdent une dimension Assouad-Nagata finie.
- Utilisent le Lemme 2.4 pour montrer que l'existence d'applications bi-Lipschitziennes vers des espaces de dimension finie implique que les espaces cibles ( $\mathbb{X}$ et $\mathbb{Y}^f$ ) possèdent une dimension métrique $\sigma$ -finie.
Expériences Numériques :
Les auteurs évaluent les performances de GW- $k_n$ -NN et fGW- $k_n$ -NN sur sept jeux de données de référence :
- Graphes avec attributs : BZR, COX-2 et PROTEINS (jeux de données moléculaires).
- Graphes sans attributs : IMDb-B, IMDb-M (réseaux sociaux) et deux jeux de données synthétiques (ERSBM1, ERSBM2).
- Lignes de base (Baselines) : Comparaisons avec des réseaux de neurones convolutifs sur graphes (GCN), diverses méthodes de noyaux de graphes (Shortest Path, Graphlet, HOPPER, Propagation) et des SVM utilisant des noyaux GW/fGW.

Contributions Clés
La contribution principale de ce travail est la preuve de la cohérence universelle pour les classifieurs $k$ -NN dans le contexte de la classification de graphes en utilisant les distances GW et fGW.

Résultats Théoriques :
- Théorème 1.8 : Prouve que le classifieur GW- $k_n$ -NN est universellement faiblement consistant sur l'espace des graphes $(\mathbb{X}, GW_2)$ sous les conditions $k \to \infty$ et $k/n \to 0$ . Il est universellement fortement consistant si $k/\log(n) \to \infty$ .
- Théorème 1.9 : Prouve les mêmes résultats de cohérence pour le classifieur fGW- $k_n$ -NN sur l'espace des graphes avec attributs de nœuds $(\mathbb{Y}^f, fGW_{\alpha,1,2})$ .
- Ces résultats sont établis en montrant que les deux espaces sont séparables et possèdent une dimension métrique $\sigma$ -finie, une propriété dérivée via des plongements bi-Lipschiens dans des espaces quotients d'espaces euclidiens.
Résultats Empiriques :
- Sur les jeux de données de graphes avec attributs (BZR, COX-2, PROTEINS), fGW- $k_n$ -NN a systématiquement atteint la précision moyenne la plus élevée, surpassant les GCN et les autres méthodes basées sur les noyaux. GW- $k_n$ -NN a également obtenu des performances compétitives.
- Sur les jeux de données sans attributs, GW- $k_n$ -NN a atteint une précision parfaite (100 %) sur le jeu de données synthétique ERSBM2 et une forte performance sur IMDb-B, surpassant souvent les noyaux de graphes et les GCN.
- Les auteurs notent que bien que les méthodes GW/fGW soient interprétables (les petites distances impliquent une similitude structurelle), elles peuvent être coûteuses en calcul par rapport à certaines méthodes de noyaux, bien qu'elles offrent des améliorations d'efficacité par rapport aux SVM utilisant des noyaux GW dans certains contextes.

Signification et Revendications
Le papier prétend établir un fondement théorique pour l'utilisation de classifieurs métriques comme $k$ -NN dans le cadre de Gromov–Wasserstein. En prouvant la cohérence universelle, les auteurs soutiennent que ces méthodes ne sont pas simplement heuristiques mais sont théoriquement solides pour les tâches de classification de graphes.

La signification réside dans le pont jeté entre la théorie du transport optimal et la théorie de l'apprentissage statistique pour les données structurées. Les auteurs soulignent que leur approche offre un « cadre hautement interprétable » où la distance entre les graphes mesure directement la similitude structurelle (l'isomorphisme implique une distance nulle). Ils déclarent explicitement que, à leur connaissance, il s'agit de la première application de GW- $k$ -NN à la classification de graphes et de la première preuve théorique de sa cohérence.

Le papier reste modeste concernant les généralisations futures. Il reconnaît que, bien que la cohérence soit prouvée pour des paramètres spécifiques ( $p=2$ pour GW, $p=1, q=2$ pour fGW), il reste un problème ouvert de savoir si ces résultats tiennent pour d'autres choix de paramètres ou dans les contextes de Z-Gromov–Wasserstein les plus généraux. Les auteurs conjecturent que, de manière similaire à l'espace de Wasserstein, la cohérence universelle peut ne pas tenir dans la pleine généralité sans restrictions spécifiques sur les espaces d'intérêt.