🤖 machine learning

Understanding Truncated Positional Encodings for Graph Neural Networks

Cet article étudie les implications théoriques et empiriques de l'utilisation d'encodages positionnels tronqués dans les réseaux de neurones sur graphes, révélant qu'une telle troncature modifie fondamentalement le pouvoir expressif des différentes familles d'encodage — rendant les variantes spectrales non plus plus fortes que le test 1-WL — et démontrant que la combinaison de plusieurs encodages tronqués surpasse l'utilisation de n'importe quelle famille unique sur des jeux de données réels.

Auteurs originaux : James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

Publié 2026-06-12

📖 6 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : James Flora, Mitchell Black, Weng-Keen Wong, Amir Nayyeri

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 d'apprendre à un robot à comprendre le tracé d'une ville. Le robot est un Réseau de Neurones sur Graphes (GNN) et la ville est un graphe composé d'intersections (nœuds) et de rues (arêtes).

Pour faire du bon travail, le robot a besoin de plus qu'une simple liste de quelles rues sont connectées à lesquelles. Il a besoin de Codages Positionnels (PEs). Considérez les PEs comme une « carte » ou une « boussole » qui indique au robot où se trouve chaque intersection par rapport aux autres. Sans cette carte, le robot est comme une personne marchant dans une ville les yeux fermés, sachant seulement qui se trouve juste à côté d'elle, mais n'ayant aucune idée si elle est proche du centre-ville ou coincée dans une impasse.

Le Problème : La Carte « Parfaite » est Trop Lourde

Il existe deux manières principales de créer cette carte parfaite :

La Carte Spectrale : Elle utilise des mathématiques complexes (valeurs propres et vecteurs propres) pour observer les « vibrations » ou la forme globale de la ville.
La Carte de Marche : Elle compte le nombre de façons de marcher d'un point à un autre en 1 étape, 2 étapes, 3 étapes, et ainsi de suite.

Mathématiquement, si vous utilisez la carte entière (toutes les étapes, toutes les vibrations), ces deux méthodes sont également puissantes. Elles peuvent distinguer presque n'importe quels deux tracés de ville différents.

Cependant, il y a un piège : Créer cette carte « complète » pour une grande ville demande une puissance de calcul et une mémoire (spécifiquement, cela devient exponentiellement plus difficile) massives à mesure que la ville s'agrandit. C'est comme essayer de porter un sac à dos contenant la bibliothèque de tous les plans possibles du monde. C'est trop lourd pour être utilisé dans la vie réelle.

C'est pourquoi les ingénieurs utilisent des Codages Positionnels Tronqués. Au lieu de la bibliothèque entière, ils ne prennent que les premiers chapitres.

Spectral Tronqué : Juste les premières « vibrations » (vecteurs propres).
Marche Tronquée : Juste les premières étapes de marche (puissances de la matrice d'adjacence).

La grande question posée par l'article est la suivante : Si nous coupons la fin de ces cartes, fonctionnent-elles toujours de la même manière ?

La Grande Découverte : « Couper » Change Tout

Les auteurs ont découvert une réponse surprenante : Non, elles ne fonctionnent plus de la même manière.

Lorsque vous avez la carte complète, les méthodes Spectrales et de Marche sont des jumeaux. Mais quand vous les tronquez (les coupez), elles deviennent des frères et sœurs très différents avec des forces et des faiblesses distinctes.

Le Piège du « Spectral Tronqué » : Parfois, utiliser seulement les premières vibrations peut rendre le robot moins performant pour comprendre la ville que s'il n'avait aucune carte du tout ! Dans certains cas, une carte spectrale tronquée est si faible qu'elle ne peut même pas faire la différence entre deux villes qu'un test de vérification de voisinage très simple (appelé test 1-WL) peut facilement identifier.
Le Piège de la « Marche Tronquée » : Inversement, il existe des configurations de villes que une carte de marche tronquée (comptant seulement quelques étapes) rate complètement, mais qu'une carte spectrale tronquée détecte immédiatement.

L'Analogie : Imaginez essayer d'identifier une personne.

La Carte Spectrale Complète est comme connaître son ADN entier et son histoire de vie.
La Carte Spectrale Tronquée est comme ne connaître que sa taille.
La Carte de Marche Tronquée est comme savoir combien de pas il faut pour marcher de sa maison à l'épicerie.

Si vous ne connaissez que la taille (Spectral Tronqué), vous pourriez confondre deux personnes de même taille. Si vous ne connaissez que la distance de marche (Marche Tronquée), vous pourriez confondre deux personnes qui habitent à la même distance de l'épicerie. Mais si vous utilisez les deux, vous obtenez une bien meilleure image.

Le Nouveau Héros : Les « Distances Harmoniques »

L'article introduit une nouvelle famille de cartes appelées distances k-harmoniques.

Considérez la Résistance Effective (un type de distance 1-harmonique) comme mesurant à quel point deux points sont « connectés », comme la quantité d'électricité qui circule entre eux.
L'article montre que la Distance Biharmonique (2-harmonique) mesure quelque chose de différent : comment une rue est « centrale » ou importante pour l'ensemble de la ville.

Les auteurs prouvent que bien que ces nouvelles cartes soient puissantes, elles ont aussi des limites. Si vous n'utilisez que la carte de « résistance », vous pourriez manquer des détails que la carte « biharmonique » saisit, et vice versa. Cependant, si vous utilisez assez de ces cartes harmoniques, vous pouvez recréer la puissance des cartes complètes et lourdes.

Le Conseil Pratique : « Mélanger et Associer »

Puisqu'aucune carte de type « coupée » unique n'est parfaite, les auteurs suggèrent une règle simple pour les ingénieurs : Ne vous reposez pas sur un seul type de carte tronquée.

Au lieu de cela, mélangez-les ensemble.

Combinez quelques étapes de la carte de « Marche ».
Combinez quelques « vibrations » de la carte « Spectrale ».
Ajoutez une ou deux distances « Harmoniques ».

L'Expérience :
Les auteurs ont testé cela sur des jeux de données réels (comme la prédiction des propriétés chimiques de molécules).

Utiliser un seul type de carte tronquée était correct.
Utiliser un mélange de différents types de cartes tronquées était nettement meilleur.

C'est comme naviguer dans une ville : avoir une boussole (Spectral), un podomètre (Marche) et une mesure du flux de trafic (Harmonique) à la fois est bien mieux que de ne compter que sur un seul d'entre eux.

Résumé

Les cartes complètes sont trop lourdes pour une utilisation réelle, c'est pourquoi nous utilisons des versions « tronquées » (coupées).
La coupe brise l'égalité : Les cartes Spectrales Tronquées et de Marche Tronquées ne sont plus égales ; elles ont des angles morts différents.
Certaines coupes sont pires que l'absence de carte : Dans certains cas, une carte spectrale tronquée est plus faible qu'un test très basique.
La Solution : Ne choisissez pas un seul type. Mélangez différents types de cartes tronquées pour obtenir la meilleure performance sans le coût de calcul massif.

Résumé technique : Comprendre les encodages positionnels tronqués pour les réseaux de neurones sur graphes

Énoncé du problème

Les réseaux de neurones sur graphes (GNN), en particulier les réseaux de passage de messages (MPNN), sont fondamentalement limités dans leur capacité à capturer l'information structurelle globale, une contrainte formalisée par leur équivalence au test 1-WL (Weisfeiler-Lehman). Pour surmonter cela, les Graph Transformers (GT) et les GNN améliorés utilisent des encodages positionnels (PE) pour injecter de l'information structurelle. Deux familles dominantes de PE sont les encodages spectraux (dérivés des espaces propres du Laplacien) et les encodages basés sur les marches (dérivés des puissances de la matrice d'adjacence).

Théoriquement, les versions complètes de ces encodages (utilisant $\Omega(n)$ vecteurs propres ou puissances de matrices) sont équivalentes en termes de puissance expressive, se situant entre les tests 1-WL et 3-WL. Cependant, le calcul de ces encodages complets nécessite une complexité de temps et d'espace de $O(n^3)$ , ce qui est prohibitif pour les applications du monde réel. Par conséquent, les praticiens s'appuient sur des variantes tronquées (par exemple, les $k$ premiers vecteurs propres ou les $k$ premières puissances de la matrice d'adjacence). Les propriétés théoriques, la puissance expressive et les forces comparatives de ces PE tronqués restent largement inexplorées, créant un fossé entre les garanties théoriques et la mise en œuvre pratique.

Méthodologie

Les auteurs initient une étude systématique des PE tronqués à travers une analyse théorique et une validation empirique.

Cadre théorique

Le papier utilise la hiérarchie WL et ses variantes pour caractériser la puissance expressive de différents PE :

Test $\psi$ -WL : Une variante du test WL où les couleurs des nœuds sont mises à jour à l'aide d'un encodage positionnel relatif (RPE) $\psi$ .
Test Sparse- $\psi$ -WL : Une extension pour les MPNN où $\psi$ est utilisé comme caractéristique d'arête.
Familles clés analysées :
1. Projections d'espace propre tronquées ( $k$ -EP-WL) : Utilisation des $k$ premières projections d'espace propre du Laplacien.
2. Encodages de marche tronqués ( $k$ -Walk-WL) : Utilisation des $k$ premières puissances de la matrice d'adjacence.
3. Résistance effective (Resistance-WL) : Une distance spectrale spécifique (distance 1-harmonique).
4. Distances $k$ -harmoniques : Une généralisation de la résistance effective définie comme $H_k(u, v) = \sqrt{(1_u - 1_v)^T (L^+)^k (1_u - 1_v)}$ .

Les auteurs construisent des paires de graphes spécifiques (par exemple, des produits de graphes chemins et de graphes complets, ou des cycles vs des unions disjointes de cycles) pour prouver la séparabilité ou l'indistinguabilité sous différents PE tronqués et tests WL.

Évaluation empirique

Des expériences ont été menées sur trois benchmarks :

BREC : Un jeu de données conçu pour mesurer la « puissance expressive réalisée » des GNN en testant leur capacité à distinguer des graphes non isomorphes allant de 1-WL à 3-WL indistinguables.
ZINC-12k : Un benchmark de régression de graphes pour la solubilité moléculaire, utilisé pour tester l'hypothèse selon laquelle le mélange de PE tronqués améliore les performances.
ogbg-molhiv : Un benchmark de classification binaire pour l'inhibition de l'HIV.

Les auteurs ont évalué des architectures Graphormer-GD et des MPNN (GINE) en utilisant diverses combinaisons de PE tronqués, incluant des familles uniques et des mélanges de codages spectraux, de marches et de $k$ -harmoniques.

Contributions clés et résultats

1. Divergence de la puissance expressive dans les formes tronquées

Le papier prouve que si les encodages spectraux et de marche complets sont équivalents, leurs formes tronquées sont fondamentalement différentes :

Spectral tronqué vs 1-WL : Les auteurs montrent que les projections d'espace propre tronquées ( $k$ -EP-WL) peuvent être plus faibles que le test 1-WL. Plus précisément, il existe des paires de graphes distinguables par 1-WL mais indistinguables par $k$ -EP-WL pour $k \in \Omega(n)$ (Théorème 4.1).
Marche tronquée vs Spectral : Inversement, il existe des paires de graphes distinguables par une seule projection d'espace propre (1-EP-WL) mais indistinguables par des encodages de marche de taille $\Omega(n)$ (Théorème 4.2).
Implication : Aucune famille de PE tronqués n'est strictement supérieure ; elles capturent différents aspects structurels et peuvent être incomparables à la hiérarchie WL standard.

2. Limitations de la résistance effective

Le papier analyse la résistance effective (distance 1-harmonique) et constate qu'elle est un PE plus faible que les projections d'espace propre complètes ou les encodages de marche sur les graphes pondérés.

Théorème 4.3 : Il existe des graphes pondérés indistinguables par Resistance-WL mais distinguables par Adjacency-WL (et donc 1-WL sur des graphes non pondérés).
Corollaire 4.1 : Resistance-WL n'encode pas l'intégralité du spectre du graphe, infirmant une conjecture précédente.

3. Les distances $k$ -harmoniques comme un pont

Les auteurs introduisent les distances $k$ -harmoniques comme un pont naturel entre les encodages polynomiaux et spectraux.

Complétude : La concaténation de $\Theta(n)$ distances $k$ -harmoniques produit un encodage équivalent en puissance aux encodages spectraux ou de marche complets (Théorème 4.6).
Puissance différentielle : Même au sein de la famille $k$ -harmonique, les encodages de taille fixe diffèrent. Par exemple, la distance biharnonique (2-harmonique) peut distinguer certaines paires d'arbres en un nombre constant d'itérations, alors que la résistance effective (1-harmonique) nécessite $O(n)$ itérations (Théorème 4.7).
Robustesse : Cependant, si une distance $k$ -harmonique distingue une paire de graphes, la plupart des autres distances $k$ -harmoniques les distingueront également (Théorème 4.8).

4. Résultats empiriques : Le pouvoir du mélange

Résultats BREC : Les distances $k$ -harmoniques ont obtenu des résultats compétitifs avec des encodages à canal unique et à faible surcharge, égalant souvent le plafond théorique pour les graphes situés entre 1-WL et 3-WL.
Résultats ZINC : La découverte la plus significative est que mélanger des PE de différentes familles (par exemple, combiner des marches tronquées et des $k$ -harmoniques) surpasse toute famille unique. Un mélange de marches tronquées et de $k$ -harmoniques a atteint l'erreur absolue moyenne (MAE) la plus basse sur ZINC-12k, surpassant les bases de référence à famille unique.
Efficacité : Le papier note que les distances $k$ -harmoniques peuvent être approximées en $O(mk \cdot \text{poly}(\log n))$ temps en utilisant des solveurs de Laplacien rapides et des projections de Johnson-Lindenstrauss, évitant ainsi le coût de $O(n^3)$ d'un calcul exact.

Signification et affirmations

Le papier affirme initier l'étude théorique des encodages positionnels tronqués, déplaçant la perspective de voir ces derniers simplement comme des approximations d'encodages complets vers une vision de espace de conception distinct possédant des propriétés expressives uniques.

Aperçu théorique : Ce travail démontre que la troncature modifie fondamentalement l'information capturée par les PE, les rendant incomparables à la hiérarchie WL standard dans certains cas spécifiques.
Conseil pratique : Les auteurs proposent une règle empirique : mélangez les PE de différentes familles lorsque vous utilisez des encodages tronqués. Cette approche capture des indices structurels complémentaires tout en contrôlant les coûts de calcul.
Portée modeste : Les auteurs reconnaissent que si l'isomorphisme de graphe est un proxy principled, les tâches du monde réel impliquent des signaux en aval (centralité, motifs) qui peuvent ne pas s'aligner strictement sur les tests d'isomorphisme. Ainsi, la contribution principale est d'établir un fondement théorique et un point de départ pour une étude empirique systématique, plutôt que de revendiquer une solution universelle pour toutes les tâches d'apprentissage sur graphes.