LEAP: Local ECT-Based Learnable Positional Encodings for Graphs

Ce papier propose LEAP, une nouvelle méthode d'encodage positionnel local et apprenable pour les graphes, qui combine l'approximation différentiable de la transformée d'Euler (DECT) et sa variante locale ($\ell$-ECT) afin de surmonter les limites des réseaux de neurones sur graphes standards en intégrant des caractéristiques topologiques efficaces.

L'essentiel

🌟 Le Titre : LEAP (Le Saut)

Imaginez que vous essayez de comprendre la forme d'un objet complexe, comme un château de cartes ou un réseau de métro, simplement en regardant les points individuels (les nœuds) et les liens entre eux (les arêtes).

Le papier présente LEAP (Local ECT-Based Learnable Positional Encodings for Graphs), une nouvelle méthode pour aider les intelligences artificielles à "voir" la forme et la structure des graphes, pas seulement les données qui y sont attachées.

---

🧩 Le Problème : L'IA qui a la "vue en tunnel"

Aujourd'hui, la plupart des réseaux de neurones graphiques (les IA qui analysent des réseaux sociaux, des molécules, etc.) fonctionnent comme des messagers locaux.

• L'analogie : Imaginez un groupe de personnes dans une pièce sombre. Chaque personne ne peut parler qu'à ses voisins immédiats. Elles échangent des messages ("J'ai un chapeau rouge", "Je suis triste").
• Le souci : Si la pièce est très grande, l'information met trop de temps à circuler. De plus, si deux personnes ont exactement les mêmes voisins et les mêmes messages, l'IA les confond, même si elles sont dans des pièces de formes totalement différentes (l'une ronde, l'autre carrée). L'IA perd la "forme globale" du réseau.

💡 La Solution : LEAP, le "GPS Topologique"

Pour résoudre ce problème, les auteurs ont créé LEAP. C'est comme donner à chaque personne un GPS spécial qui ne se contente pas de dire "où je suis", mais qui décrit la forme du terrain autour d'elle.

Ce GPS utilise une idée mathématique appelée Transformée de Caractéristique d'Euler (ECT).

• L'analogie de la "Silhouette" : Imaginez que vous tenez une lampe torche (une direction) et que vous projetez l'ombre de votre voisinage sur un mur. L'ECT compte combien de fois l'ombre se sépare ou se reconnecte.
• En tournant la lampe torche dans toutes les directions possibles, vous obtenez une "signature" unique de la forme du voisinage. C'est comme si l'IA pouvait sentir la topologie (les trous, les boucles, les connexions) sans avoir besoin de voir les détails exacts.

🎨 La Grande Innovation : Apprendre à regarder

Avant, cette méthode (ECT) était rigide, comme une règle en plastique que l'on ne pouvait pas changer.

• L'innovation de LEAP : Les auteurs ont rendu cette règle apprenable.
• L'analogie : Au lieu d'avoir une lampe torche fixe, l'IA apprend elle-même où pointer la lumière pour voir le mieux possible. Si elle remarque que pointer vers le nord-est aide à distinguer deux molécules différentes, elle va "apprendre" à privilégier cette direction. C'est comme si l'IA apprenait à faire ses propres "photos" du réseau pour mieux le comprendre.

🧪 Ce qu'ils ont découvert (Les Résultats)

Les chercheurs ont testé LEAP sur plusieurs terrains de jeu :

1. Le test des formes pures : Ils ont créé des graphes où les points n'avaient aucune information (pas de couleur, pas de nom), juste des liens. Les IA classiques échouaient (elles ne voyaient rien). LEAP, lui, a obtenu 100 % de réussite. Il a compris la structure purement par la forme.
2. Les vrais mondes : Sur des données réelles (comme des molécules chimiques ou des réseaux de lettres), LEAP a souvent battu les meilleures méthodes existantes, surtout quand il était combiné à des architectures modernes.
3. La flexibilité : Même si on change la taille du voisinage regardé (1 voisin, 2 voisins...), LEAP reste très performant, prouvant qu'il est robuste.

🚀 Pourquoi c'est important ?

Imaginez que vous essayez de reconnaître un ami dans une foule.

• Les anciennes méthodes : Elles regardent juste la couleur de son t-shirt et ce que disent ses voisins immédiats.
• Avec LEAP : L'IA regarde aussi la forme de la foule autour de lui. Est-ce qu'il est au centre d'un cercle ? Est-ce qu'il est coincé dans un couloir ? Est-ce qu'il est sur une île ?

Cela permet aux IA de comprendre des structures complexes (comme des protéines pour la médecine ou des réseaux financiers) beaucoup mieux qu'auparavant, en capturant la "géométrie" cachée des données.

En résumé

LEAP est un nouveau super-pouvoir pour les IA graphiques. Il leur donne la capacité de sentir la forme de leur environnement et d'apprendre à regarder sous les angles les plus pertinents pour résoudre des problèmes complexes, là où les méthodes précédentes étaient souvent aveugles à la structure globale.

Résumé technique

1. Problématique et Contexte

Les réseaux de neurones à graphes (GNN), et plus spécifiquement les réseaux de neurones à passage de messages (MPNN), sont la norme pour l'apprentissage sur les graphes. Cependant, ils souffrent de limitations théoriques et pratiques bien documentées :

• Perte d'information : Ils ont tendance à perdre les signaux dans les graphes de grand diamètre (problème d'oversquashing) et peinent à exploiter efficacement les informations de sous-structures.
• Manque de représentation canonique : Les graphes varient en cardinalité et combinent des informations géométriques (features des nœuds) et topologiques (connectivité).
• Limites des encodages positionnels existants : Les méthodes actuelles (comme RWPE ou LaPE) se basent soit sur des aspects purement géométriques, soit topologiques, mais manquent souvent de flexibilité ou d'expressivité pour capturer des structures complexes, en particulier sur des graphes non attribués (sans features de nœuds informatives).

L'objectif est de développer un encodage positionnel (PE) localement apprenable, end-to-end, capable de capturer à la fois la géométrie et la topologie d'un graphe pour améliorer les performances des GNN.

2. Méthodologie : LEAP

Les auteurs proposent LEAP (Local ECT-Based Learnable Positional Encodings), un nouvel encodage positionnel structurel local basé sur une approximation différentiable de la Transformée de Caractéristique d'Euler (ECT).

Concepts Fondamentaux

• ECT (Euler Characteristic Transform) : Un invariant géométrique-topologique qui caractérise la forme d'un objet en suivant l'évolution de sa caractéristique d'Euler (nœuds - arêtes) le long de différentes directions de projection.
• DECT (Differentiable ECT) : Une version de l'ECT où la fonction indicatrice est approximée par une fonction sigmoïde, rendant le calcul différentiable et compatible avec le deep learning.
• $\ell$-ECT (Local ECT) : Une variante calculée non pas sur le graphe entier, mais sur le voisinage local (m-hop) d'un nœud spécifique.

Architecture de LEAP

Le processus de calcul pour un nœud $v$ se déroule en quatre étapes :

1. Sélection du voisinage : Extraction du sous-graphe $N_m(v, G)$ (voisinage à $m$ sauts) autour du nœud.
2. Normalisation : Centrage et normalisation des features des nœuds du voisinage pour les ramener sur la sphère unité $S^{d-1}$.
3. Calcul de la DECT : Calcul de la matrice de la transformée de caractéristique d'Euler différentiable pour ce voisinage, en utilisant un ensemble fini de directions $\Theta$ et de seuils $T$.
4. Projection Apprenable : Une couche apprenable $\phi$ projette la matrice de la DECT ($|\Theta| \times |T|$) en un vecteur d'encodage positionnel de dimension $k$.

Stratégies de Projection

Pour garantir l'invariance aux rotations et aux permutations des directions, les auteurs proposent cinq stratégies de projection :

• Projection linéaire (non invariante).
• Convolutions 1D.
• DeepSets (invariant par permutation des directions).
• Attention (invariant par permutation, sans PE).
• Attention avec PE (intègre l'information des directions).

Une caractéristique clé de LEAP est que les directions $\Theta$ peuvent être initialisées aléatoirement et apprises durant l'entraînement (LEAP-L), contrairement aux méthodes statiques.

3. Contributions Clés

1. Nouvel Encodage End-to-End : Première intégration de l'ECT local ($\ell$-ECT) dans des architectures de deep learning de manière entièrement apprenable.
2. Capture de la Topologie Pure : La méthode est capable de distinguer des structures de graphes même lorsque les features des nœuds sont non informatives (ou purement aléatoires), prouvant sa nature structurelle.
3. Performance Supérieure : Démonstration empirique que LEAP surpasse les encodages positionnels existants (RWPE, LaPE) lorsqu'il est combiné à divers GNN (GCN, GAT, GIN) et architectures sans passage de messages (NoMP).
4. Flexibilité et Expressivité : Le cadre permet de capturer des informations topologiques locales complexes, dépassant les limites théoriques des MPNN classiques pour le comptage de sous-graphes.

4. Résultats Expérimentaux

Les expériences ont été menées sur des jeux de données synthétiques et réels (benchmarks TU, Alchemy, HIV).

• Jeu de données synthétique : Sur un ensemble de 40 000 graphes où la tâche de classification dépend uniquement du nombre d'arêtes (features de nœuds aléatoires), les modèles GCN/GAT standards ont échoué (précision ~70%), tandis que LEAP a atteint 100% de précision, prouvant sa capacité à extraire la structure pure.
• Benchmarks TU (Classification de graphes) :
  • LEAP a obtenu les meilleurs résultats sur la majorité des combinaisons architecture/dataset.
  • Sur les datasets Letter-H, Letter-M et Fingerprint, l'amélioration par rapport aux pires baselines est massive (jusqu'à +96% de gain relatif sur Letter-H).
  • L'apprentissage des directions (LEAP-L) améliore généralement les performances par rapport aux directions fixes (LEAP-F), surtout avec les architectures GCN et NoMP.
• Datasets à grande échelle (Alchemy & HIV) :
  • Sur Alchemy (régression rotation-invariante), LEAP avec directions apprises surpasse nettement toutes les baselines.
  • Sur HIV, bien que LaPE (encodage global) soit très performant, la combinaison LaPE + LEAP donne les meilleurs résultats, suggérant que les informations locales (LEAP) et globales (LaPE) sont complémentaires.
• Robustesse : Des études d'ablation montrent que LEAP est robuste aux variations de la dimension d'embedding, du nombre de sauts ($m=1$ étant souvent optimal) et des hyperparamètres de la DECT.

5. Signification et Perspectives

Signification :
Ce travail établit un pont crucial entre la topologie computationnelle (via l'ECT) et l'apprentissage profond sur les graphes. Il démontre que les invariants topologiques locaux, lorsqu'ils sont rendus apprenables, offrent une expressivité supérieure aux méthodes de passage de messages traditionnelles et aux encodages positionnels statiques. LEAP est particulièrement pertinent pour les architectures basées sur l'attention globale (comme les Transformers sur graphes) qui manquent d'induction de biais structurels locaux.

Limitations et Futur :

• LEAP nécessite des features de nœuds (même si elles peuvent être apprises), ce qui le distingue des PE purement structurels.
• L'approximation différentiable de l'ECT peut ne pas conserver toutes les garanties théoriques d'injectivité de l'ECT exact.
• Le nombre d'hyperparamètres (directions, seuils, lissage) est plus élevé que pour d'autres PE.

Futur : Les auteurs envisagent de formaliser la théorie de l'expressivité de LEAP, de rendre l'étape de seuillage entièrement apprenable, et d'étendre la méthode aux complexes simpliciaux et cellulaire pour l'apprentissage topologique de haut niveau.

En résumé, LEAP représente une avancée majeure pour l'apprentissage de représentations de graphes, offrant un outil puissant pour capturer la structure topologique locale de manière flexible et performante.