LEED: Local Embedding Evolution Distance for over-smoothing estimation and virtual node selection in GNN

Imaginez que vous essayez d'apprendre à un groupe d'amis comment résoudre un mystère en leur faisant chuchoter des indices les uns aux autres. C'est essentiellement ainsi que fonctionnent les réseaux de neurones sur graphes (GNN). Dans le monde de l'informatique, un « graphe » est simplement une carte de connexions — comme un réseau social où les personnes sont des points et les amitiés sont des lignes. Les GNN sont des programmes intelligents qui apprennent en faisant circuler l'information le long de ces lignes, couche par couche, pour comprendre l'ensemble du tableau.

Cependant, ce jeu de chuchotements présente deux bugs délicats. Premièrement, il y a le « sur-lissage » (over-smoothing). Si vous faites circuler un secret autour d'un grand cercle trop de fois, tout le monde finit par entendre exactement la même chose, et les détails uniques sont délavés jusqu'à ce que plus personne ne puisse distinguer qui a dit quoi. Deuxièmement, il y a l'« écrasement excessif » (over-squashing). Imaginez essayer de faire passer une histoire vaste et complexe dans un couloir étroit et minuscule pour qu'elle arrive de l'autre côté ; l'information est écrasée, déformée ou perdue entièrement parce que le chemin est trop encombré ou trop long. Les scientifiques essaient de corriger ces bugs depuis des années, souvent en ajoutant des « nœuds virtuels » — des super-amis imaginaires qui peuvent connecter instantanément des parties distantes du groupe pour accélérer les choses. Mais la grande question a toujours été : quels amis devraient recevoir ces super-pouvoirs ? Généralement, les chercheurs se contentaient de deviner ou d'essayer un tas de règles différentes pour voir ce qui fonctionnait le mieux.

Ce papier introduit un outil ingénieux appelé LEED (Local Embedding Evolution Distance) pour résoudre ce jeu de devinettes. Voyez le LEED comme un micro ultra-sensible qui écoute précisément comment la « voix » (la représentation des données) de chaque ami change à mesure que le message circule dans le groupe. Au lieu de simplement regarder l'ensemble de la foule pour voir si tout le monde sonne pareil, le LEED zoome sur chaque personne pour voir qui se perd dans le bruit ou qui est coincé dans un goulot d'étranglement. Les auteurs ont découvert qu'en utilisant le LEED pour choisir les « nœuds critiques » les plus importants pour devenir des super-amis virtuels, ils pouvaient corriger le problème d'écrasement sans provoquer accidentellement le problème de lissage. Leurs expériences sur six ensembles de données différents ont montré que cette nouvelle méthode aide l'ordinateur à apprendre mieux et plus vite que les anciens jeux de devinettes, prouvant que l'écoute attentive des détails de la conversation est la clé pour réparer tout le système.

L'histoire du réseau de chuchotements

Plongeons plus profondément dans la magie de ces réseaux numériques. Vous pouvez considérer un réseau de neurones sur graphe comme une immense partie de « Téléphone Arabe », mais au lieu d'une chanson ridicule, les joueurs font circuler des données complexes sur une molécule, une citation ou une connexion sociale. Dans une partie standard, si vous faites passer un message à travers trop de personnes, il finit par être déformé. Dans un GNN, si vous faites passer l'information à travers trop de couches, les caractéristiques uniques de chaque nœud (les points) commencent à se brouiller jusqu'à ce qu'ils se ressemblent tous. C'est le sur-lissage. C'est comme si tous les élèves de votre classe commençaient à porter exactement le même uniforme et à dire exactement la même phrase d'accroche ; vous ne pourriez plus distinguer votre meilleur ami d'un étranger.

Il y a ensuite le problème opposé : l'écrasement excessif. Cela se produit lorsqu'un message doit voyager d'un côté d'un immense graphe vers l'autre, mais que le chemin est étroit. Imaginez essayer d'envoyer une lettre de 50 pages par une petite fente de boîte aux lettres qui ne peut contenir qu'une carte postale. L'information est compressée, écrasée et déformée. En termes de graphe, cela se produit lors de « goulots d'étranglement » — des endroits où un nœud ou quelques arêtes doivent supporter trop de trafic provenant de parties distantes du réseau.

Pour corriger ces problèmes, les scientifiques ont essayé d'ajouter des nœuds virtuels. Considérez-les comme des « super-connecteurs » ou des « téléporteurs ». Si vous ajoutez un ami magique qui est connecté à tout le monde, le message n'a pas besoin de voyager via le long chemin sinueux du groupe original ; il peut simplement sauter vers le téléporteur et bondir vers la destination. Cela corrige le problème d'écrasement en raccourcissant la distance. Mais attention : si vous choisissez la mauvaise personne pour être le téléporteur, ou si vous en ajoutez trop, vous pourriez accidentellement aggraver le problème de « sur-lissage ». Vous pourriez faire en sorte que tout le monde sonne pareil trop rapidement.

Pendant longtemps, les chercheurs choisissaient ces nœuds spéciaux en utilisant de vieilles règles, comme « qui a le plus d'amis ? » (Degré) ou « qui se trouve sur le plus grand nombre de chemins les plus courts ? » (Intermédiarité). Ils testaient un tas de ces règles, lançaient l'expérience, et voyaient laquelle donnait le meilleur score. C'était un peu comme chercher la meilleure clé pour une serrure en testant chaque clé d'un énorme trousseau sans savoir laquelle convient réellement.

Entrée en scène du LEED : La loupe du détective

Les auteurs de ce papier, Killian Cressant et Pedro B. Velloso, ont décidé d'arrêter de deviner. Ils ont construit une nouvelle métrique appelée LEED (Local Embedding Evolution Distance). Au lieu de regarder l'ensemble du graphe pour voir si les choses deviennent floues, le LEED agit comme une loupe pour chaque nœud. Il suit précisément comment l'« embedding » d'un nœud (sa représentation interne de lui-même) évolue à travers chaque couche du réseau.

Voici la partie ingénieuse : le LEED ne mesure pas seulement la distance entre un nœud et ses voisins ; il mesure la distance minimale vers ses voisins après une transformation qui imite la façon dont le réseau traite l'information. C'est comme vérifier si la réponse d'un élève devient trop similaire à celle de son voisin, mais en regardant spécifiquement la correspondance la plus proche pour voir s'ils commencent à trop se copier.

En faisant cela, le LEED peut repérer deux choses à la fois :

1. Qui se perd ? (Les nœuds qui deviennent trop similaires à tous les autres, indiquant un sur-lissage).
2. Qui est le goulot d'étranglement ? (Les nœuds qui peinent à transmettre l'information, indiquant un écrasement excessif).

Le papier soutient que ces deux problèmes sont en fait les deux faces d'une même pièce. On ne peut pas simplement en corriger un sans penser à l'autre. Si vous ajoutez trop de connexions pour corriger l'écrasement, vous risquez de lisser tout le système trop vite. Le LEED aide à trouver les « nœuds critiques » — les personnes spécifiques qui doivent devenir des nœuds virtuels pour améliorer le flux sans briser l'unicité du groupe.

L'expérience : Tester la nouvelle stratégie

Pour voir si leur nouvel outil de détective fonctionnait réellement, les auteurs ont mené une série d'expériences. Ils ont pris six ensembles de données différents (comme MUTAG, ENZYMES et PROTEINS, qui sont des collections de structures chimiques et de données biologiques) et ont testé leur méthode contre les anciennes méthodes de sélection de nœuds.

Ils ont comparé leur approche, qui utilise le LEED pour choisir les nœuds critiques, à deux méthodes existantes populaires :

• LVN (Local Virtual Nodes) : Une méthode qui ajoute de petits groupes de nœuds virtuels au graphe.
• PANDA : Une méthode qui agrandit la taille de certains nœuds pour qu'ils puissent contenir plus d'informations.

Autrefois, ces méthodes devaient tester différentes règles de « centralité » (comme le Degré, PageRank, l'Intermédiarité) pour voir laquelle fonctionnait le mieux pour chaque ensemble de données. C'était un processus de tâtonnements. Les auteurs ont remplacé toutes ces vieilles règles par le seul LEED.

Les résultats étaient prometteurs. Dans leurs tests, la combinaison LVN-LEED a obtenu la meilleure performance moyenne sur les ensembles de données. Par exemple, sur l'ensemble de données MUTAG, le GCN standard (le modèle de base) a obtenu une précision d'environ 74,75 %, tandis que le modèle LVN-LEED a atteint 83,33 %. Sur ENZYMES, l'amélioration était encore plus notable, passant de 29,08 % à 31,09 % (et même plus haut dans certains tests spécifiques).

Les auteurs ont noté que si les anciennes méthodes fonctionnaient parfois bien, elles nécessitaient beaucoup de réglages. Le LEED, en revanche, fonctionnait de manière constante sans avoir besoin de tester une douzaine de règles différentes. Cela suggère qu'en se concentrant sur l'évolution locale des données, ils pouvaient trouver les bons nœuds pour aider le réseau à mieux « respirer ».

Ce que le papier dit (et ne dit pas)

Il est important de comprendre ce que ce papier prouve réellement. Les auteurs démontrent que le LEED est un outil de diagnostic plus informatif que les anciennes mesures d'énergie globale (comme l'énergie de Dirichlet) car il peut voir les détails locaux. Ils démontrent également que l'utilisation du LEED pour choisir les nœuds conduit à de meilleures performances dans leurs expériences spécifiques par rapport à une sélection aléatoire ou aux mesures de centralité standard.

Cependant, le papier prend soin de ne pas prétendre qu'il s'agit d'une solution miracle pour chaque problème. Ils précisent explicitement que leurs résultats sont basés sur des simulations et des expériences sur des ensembles de données spécifiques. Ils ont constaté que pour certains ensembles de données sans caractéristiques de nœuds claires (comme COLLAB), l'amélioration n'était pas aussi spectaculaire, et dans un cas avec le cadre PANDA, la performance a légèrement chuté, bien que non de manière significative. Cela suggère que si le LEED est un nouvel outil puissant, il peut nécessiter des ajustements selon le type de données que l'on observe.

Les auteurs soulignent également qu'ils se sont concentrés sur un type spécifique d'architecture de réseau (GCN) et qu'il reste beaucoup à explorer. Ils suggèrent que les travaux futurs pourraient examiner comment le LEED fonctionne avec d'autres types de réseaux ou comment il pourrait être utilisé pour concevoir des manières encore plus intelligentes de recâbler les graphes. Ils ne prétendent pas avoir résolu le problème du sur-lissage pour toujours ; ils ont plutôt offert un nouveau prisme plus précis pour le voir et une meilleure façon de le corriger.

Ce qu'il faut retenir

En fin de compte, ce papier traite de l'art de mieux écouter. Pendant des années, les scientifiques ont essayé de réparer le jeu du « Téléphone Arabe » des réseaux de neurones sur graphes en devinant quels amis avaient besoin de super-pouvoirs. Les auteurs de ce papier ont construit un nouvel outil, le LEED, qui écoute chaque chuchotement pour voir exactement où le message se perd ou où tout le monde commence à se ressembler. En utilisant cet outil pour choisir les bons « nœuds virtuels », ils ont montré que le réseau peut apprendre plus vite et plus précisément. C'est un rappel que parfois, pour résoudre un gros problème, on n'a pas besoin d'un marteau plus gros ; on a juste besoin d'une meilleure façon d'observer les détails.