🤖 machine learning

Dimensionality Reduction Meets Network Science: Sensemaking on UMAP's kNN Graph

Cet article démontre que l'application d'algorithmes de graphes standards, tels que PageRank, la décomposition en k-cœurs et l'analyse du coefficient de regroupement, au graphe k-plus proches voisins interne construit par UMAP offre une approche puissante et complémentaire pour la compréhension de données de haute dimension qui égale ou surpasse souvent les méthodes conçues à cet effet.

Auteurs originaux : Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz

Publié 2026-07-10

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Duen Horng Chau, Donghao Ren, Fred Hohman, Dominik Moritz

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 ayez une boîte géante et désordonnée de 60 000 photos — certaines sont des chiffres écrits à la main, d'autres sont des images de vêtements comme des sacs, des chemises et des chaussures. Vous voulez voir les motifs, alors vous utilisez un outil super intelligent appelé UMAP pour écraser ce chaos 3D (ou même de dimension supérieure) sur une feuille de papier 2D plate.

Habituellement, les gens s'arrêtent là ; ils regardent le joli nuage de points en 2D, plissent les yeux devant les points et disent : « D'accord, je vois un groupe de sacs ici. » Mais cet article soutient que l'UMAP jette en réalité sa meilleure arme secrète au moment précis où il dessine cette image.

Avant que l'UMAP n'écrase les données sur le papier, il construit un graphe kNN caché. Pensez à ce graphe comme à un immense réseau invisible d'amitiés. Dans ce réseau, chaque photo a exactement 15 amis (ses « k-plus proches voisins ») qu'elle considère comme les plus similaires. Mais voici le twist : si chaque photo choisit 15 amis, toutes les photos ne sont pas choisies par 15 autres. Certaines photos sont si bizarres ou uniques que presque personne ne les choisit comme ami. D'autres sont si « moyennes » ou « prototypiques » que des centaines d'autres photos les nomment comme leur correspondance idéale.

Les auteurs disent : « Ne jetez pas ce réseau ! Il est en fait plus honnête que l'image en 2D. » Ils ont testé trois façons géniales de jouer avec ce réseau pour mieux comprendre les données que le graphique 2D ne permettrait jamais de comprendre.

1. Le « Élève le plus populaire » (PageRank)

La Question : Quels sont les véritables « représentants » d'un groupe ?
L'Ancienne Méthode : Les gens choisissent généralement la photo la plus proche du centre d'un amas sur la carte 2D. Mais la carte 2D est déformée ! Un amas étiré pourrait avoir un « centre » qui ne ressemble pas réellement à une vraie photo.
La Nouvelle Méthode : Les auteurs ont utilisé un algorithme appelé PageRank (le même que Google a utilisé pour classer les sites web). Dans ce réseau, une photo obtient un score élevé non seulement parce que beaucoup de personnes l'ont choisie, mais aussi parce que d'autres photos populaires l'ont choisie.
Le Résultat :

Les photos ayant les scores les plus élevés ressemblaient aux exemples parfaits et classiques d'une classe (comme un « 6 » classique ou un sac à bandoulière standard).
Les photos ayant les scores les plus bas étaient les plus bizarres ou atypiques.
La Preuve : Lorsqu'ils ont choisi 200 photos de tête pour représenter l'ensemble du jeu de données, ces sélections par PageRank étaient bien meilleures pour équilibrer les classes que l'ancienne méthode (k-medoids) ; l'ancienne méthode continuait de choisir trop de photos provenant des groupes désordonnés et étalés, tandis que PageRank a choisi un mélange équitable.
À quel point sont-ils sûrs ? Très sûrs. Ils ont testé cela sur 60 000 images et ont constaté que les résultats étaient stables même en changeant le nombre d'amis de 5 à 100. Les classements restaient presque identiques (corrélation d'environ 0,95).

2. Le « Cœur vs la Périphérie » (Décomposition k-Core)

La Question : Quelles photos sont le « cœur » d'un groupe, et lesquelles ne font que traîner en périphérie ?
L'Ancienne Méthode : Des outils comme HDBSCAN vous donnent une étiquette simple : « C'est un sac. » Mais cela ne vous dit pas si ce sac est un sac classique ou un sac bizarre et flou qui correspond à peine à la définition.
La Nouvelle Méthode : Les auteurs ont utilisé la décomposition k-core. Imaginez que vous épluchez un oignon. Vous retirez continuellement les photos qui ont le moins de nominations entrantes (les moins populaires). Celles qui restent au centre même sont le « cœur ».
Le Résultat :

Ils ont découvert que les photos du « cœur » étaient les plus auto-similaires et cohérentes. Par exemple, dans la catégorie « 1 » des chiffres écrits à la main, le cœur ne contenait que des « 1 » parfaits.
Dans la catégorie « sac », le cœur a révélé des sous-groupes distincts : sacs à bandoulière, sacs bananes et textures lourdes. La carte 2D ne montrait qu'un gros amas flou de « sacs », mais le graphe l'a ouvert pour révéler les couches.
La Preuve : Ils ont comparé cela à HDBSCAN. HDBSCAN était excellent pour dire « Est-ce un sac ? », mais incapable de dire « À quel point ce sac est-il central ? ». La méthode du graphe a fourni une échelle graduée de « centralité » que les anciens outils avaient manquée.

3. Le « Club Secret » (Coefficient de Clustering)

La Question : Existe-t-il de petits groupes très serrés de photos qui se ressemblent exactement ?
L'Ancienne Méthode : En regardant la carte 2D, un groupe de « 6 » peut ressembler à une seule grande masse solide.
La Nouvelle Méthude : Le Coefficient de Clustering cherche des « triangles » dans le réseau. Si la Photo A considère la Photo B comme une amie, et que la Photo B considère la Photo C comme une amie, est-ce que la Photo A considère aussi la Photo C comme une amie ? Si oui, c'est un groupe très soudé.
Le Résultat :

Cette méthode a trouvé des « micro-quartiers » de photos partageant des styles très spécifiques. Pour le chiffre « 6 », elle a isolé des groupes basés sur de minuscules détails : certains avaient une grande boucle, d'autres étaient inclinés, d'autres avaient une courbe spécifique.
La Preuve : Les 5 % de photos ayant les coefficients de « cohésion » les plus élevés présentaient un taux de pureté de 98 % (ce qui signifie que presque tous leurs voisins étaient du même type). C'est bien plus élevé que de choisir des photos au hasard.

L'Essentiel

L'article ne dit pas que l'image 2D est inutile. Il dit simplement qu'elle est incomplète. En conservant le réseau caché d'amitiés (le graphe kNN) et en appliant ces algorithmes de graphes standards dessus, on obtient une vue beaucoup plus claire et plus honnête de ses données.

À quel point sont-ils confiants ?
Ils ont testé cela sur deux jeux de données massifs et standards (MNIST et Fashion MNIST) avec 60 000 images chacun. Les résultats sont rapides (s'exécutant en moins d'une seconde sur un ordinateur portable) et les mathématiques tiennent la route face aux meilleurs outils existants. Ils suggèrent que cette approche fonctionne pour d'autres outils similaires, mais ils ne l'ont prouvée que sur ces ensembles d'images spécifiques. Ils ne prétendent pas résoudre chaque problème de données, mais ils sont assez convaincus que c'est une bien meilleure façon de « donner du sens » que de simplement fixer des points en 2D.

Résumé technique : La réduction de dimension rencontre la science des réseaux

Problématique

Bien que l'UMAP soit un outil dominant pour la visualisation de données de haute dimension, les flux de travail analytiques standards traitent généralement le diagramme de dispersion 2D résultant comme le seul artefact d'intérêt. Cette approche délaisse le riche graphe des k-plus proches voisins (kNN) intermédiaire que l'UMAP construit en interne avant la projection. Les auteurs soutiennent que ce graphe encode la géométrie locale et la connectivité du manifold des données dans l'espace de haute dimension de manière plus fidèle que la disposition 2D, laquelle introduit inévitablement des distorsions. En ignorant ce graphe, les analystes manquent des opportunités de tâches de sens-construction — telles que l'identification de points représentatifs, l'analyse des hiérarchies de densité et la détection de la cohésion locale — qui sont occultées dans la projection 2D.

Méthodologie

L'article propose d'élever le graphe kNN interne de l'UMAP au rang de « ressource analytique de premier rang » en appliquant directement des algorithmes de science des réseaux standard à celui-ci, plutôt qu'à l'incorporation 2D. La méthodologie tire parti des propriétés structurelles spécifiques du graphe : un degré sortant $k$ fixe, un degré entrant variable et des poids d'arêtes adaptatifs à la densité. Trois algorithmes spécifiques sont appliqués :

PageRank pour la sélection de représentants :
- Mécanisme : Au lieu de sélectionner des exemplaires basés sur des centroïdes géométriques dans l'espace 2D distordu (qui peuvent tomber dans des régions non représentatives), les auteurs appliquent le PageRank au graphe kNN.
- Logique : Le score d'un nœud est amplifié de manière transitive ; un point est hautement classé non seulement parce que de nombreux nœuds pointent vers lui (degré entrant élevé), mais parce que les nœuds qui pointent vers lui sont eux-mêmes hautement classés. Cela identifie des points globalement représentatifs qui servent d'« autorités » dans le manifold.
- Implémentation : Les poids des arêtes sont dérivés des forces d'appartenance adaptatives à la densité de l'UMAP.
Décomposition k-core pour la hiérarchie de densité :
- Mécanisme : Les auteurs appliquent la décomposition k-core au graphe pour distinguer les régions de cœurs denses des périphéries éparses.
- Logique : Contrairement à la décomposition standard basée sur le degré, qui est limitée par le degré sortant fixe $k$ , cette méthode se base uniquement sur le degré entrant. Cela produit un score de « centralité de cœur » (0, 1, 2...) indiquant à quel point un nœud est profondément ancré dans des sous-graphes de plus en plus denses et interconnectés.
- Objectif : Révéler des hiérarchies de sous-graphes graduées et des sous-catégories au sein des clusters que les étiquettes de clustering discrètes (ex: de HDBSCAN) ne peuvent capturer.
Coefficient de regroupement (Clustering Coefficient) pour la cohésion locale :
- Mécanisme : Le coefficient de regroupement (CC) est calculé pour chaque nœud afin de mesurer la fraction de ses voisins qui sont également connectés entre eux.
- Logique : Un CC élevé indique des micro-voisinages « serrés » où les points se considèrent mutuellement comme des plus proches voisins.
- Objectif : Détecter des micro-clusters sémantiquement cohérents (ex: des styles d'écriture spécifiques) qui peuvent apparaître comme une masse monolithique dans une projection 2D.

Contributions clés

L'article apporte deux contributions primaires :

Changement conceptuel : Il jette un pont entre la réduction de dimension et la science des réseaux en traitant le graphe kNN de l'UMAP, souvent délaissé, comme une ressource primaire. Cela permet une construction de sens complémentaire aux diagrammes de dispersion 2D, répondant spécifiquement aux enjeux de représentativité, de structure de densité et de cohésion locale.
Validation empirique : À travers des évaluations quantitatives et qualitatives sur MNIST et Fashion MNIST, les auteurs démontrent que ces méthodes basées sur les graphes sont compétitives ou supérieures aux méthodes dédiées :
- PageRank vs k-medoids : Les points sélectionnés par PageRank atteignent une balance de classes supérieure (divergence de Jensen-Shannon plus faible) par rapport aux k-medoids, qui ont tendance à sur-sélectionner des classes à haute variance. Bien que les k-medoids surpassent légèrement PageRank en termes de représentativité pour de très petits budgets, PageRank rattrape rapidement son retard et reste compétitif en précision de classification SVM en aval. Crucialement, PageRank ne nécessite qu'un seul calcul de classement global, tandis que les k-medoids doivent être réexécutés pour chaque taille de budget.
- k-Core vs HDBSCAN : Alors que HDBSCAN assigne des étiquettes de clusters discrètes, la décomposition k-core révèle une hiérarchie graduée de centralité au sein des clusters. Les probabilités d'appartenance à HDBSCAN ont montré une corrélation proche de zéro avec la centralité de cœur (coreness), confirmant qu'elles répondent à des questions différentes (appartenance au groupe vs position au sein du groupe).
- Coefficient de regroupement : Le CC identifie des micro-voisinages distincts (ex: des styles spécifiques du chiffre « 6 ») qui sont topologiquement cohérents mais peuvent être visuellement indiscernables en 2D.

Résultats

Stabilité : Les classements PageRank sont hautement stables sur une plage de taille de voisinage de 20x ( $k=5$ à $100$), avec des corrélations de rang de Spearman moyennes d'environ 0,95, indiquant que les représentants sélectionnés ne sont pas des artefacts d'une valeur de $k$ spécifique.
Performance :
- Représentativité : PageRank rivalise avec les k-medoids en distance cosinus moyenne aux représentants les plus proches, surtout à mesure que le budget de sélection augmente.
- Balance de classes : PageRank surpasse significativement les k-medoids pour maintenir la distribution globale des classes (JSD plus faible), particulièrement pour des budgets $s \ge 200$ .
- Utilité en aval : Les classificateurs SVM entraînés sur les exemplaires sélectionnés par PageRank atteignent une précision à 2–3 points percentaux près de celle des k-medoids sur Fashion MNIST et sont comparables sur MNIST.
- Aperçu structurel : La décomposition k-core isole avec succès des sous-catégories (ex: sacs à bandoulière vs sacs à taille au sein de la classe « sac ») en filtrant pour des seuils de centralité spécifiques. Les valeurs élevées de CC isolent des styles d'écriture constants au sein du cluster du chiffre « 6 ».

Signification et affirmations

Les auteurs affirment que leur travail démontre le potentiel inexploité de la représentation interne de l'UMAP. En conservant et en analysant le graphe kNN, les analystes peuvent accéder à des informations structurelles (centralité, hiérarchie de connectivité, cohésion locale) qui sont perdues ou déformées dans la projection 2D.

L'article positionne ces algorithmes de graphes non pas comme des remplacements des outils existants, mais comme des méthodes complémentaires offrant des avantages distincts :

Ils fournissent un moyen sans paramètre (ou stable) de sélectionner des représentants sans optimiser un objectif de distance.
Ils offrent une hiérarchie continue de densité (via le k-core) plutôt que des assignations de clusters discrètes.
Ils sont efficaces sur le plan computationnel, s'exécutant en moins d'une seconde sur 60 000 points en réutilisant les tableaux de voisins précalculés de l'UMAP.

Les auteurs concluent que cette perspective encourage la communauté à « regarder au-delà du diagramme de dispersion et dans le graphe qui l'a créé », suggérant que cette approche s'étend naturellement à d'autres méthodes de réduction de dimension qui construisent des graphes kNN (ex: TriMap, PaCMAP).