Résumé technique : Le test de Weisfeiler–Leman est incomplet sur les graphes à spectre simple, il faut donc les canoniser

Énoncé du problème

Les réseaux de neurones à graphes (GNN) sont largement utilisés pour l'apprentissage sur des données structurées en graphes, mais leur puissance expressive est souvent limitée par la hiérarchie de Weisfeiler–Leman (WL). Il est établi que le test WL de dimension $k$ ($k$-WL) ne peut pas distinguer tous les graphes non isomorphes. Cependant, une classe spécifique de graphes — ceux ayant un spectre simple (où la matrice d'adjacence possède des valeurs propres distinctes) — admet un test d'isomorphisme en temps cubique. Malgré cette tractabilité théorique, il restait une question ouverte de savoir si la hiérarchie WL, qui borne supérieurement l'expressivité de nombreux GNN, pouvait distinguer tous les graphes à spectre simple.

De plus, bien que les encodages de position spectraux (par exemple, les vecteurs propres du Laplacien) soient couramment intégrés aux GNN pour améliorer l'expressivité, ils souffrent d'ambiguïtés inhérentes : ambiguïté de signe pour les spectres simples et ambiguïté de base pour les valeurs propres répétées. Les méthodes existantes pour résoudre ces ambiguïtés (telles que SignNet, MAP et OAP) sont prouvées comme étant incomplètes sur les graphes à spectre simple, échouant à distinguer certaines paires non isomorphes. Cette incomplétude limite la capacité des GNN spectraux à atteindre l'approximation universelle sur cette classe de graphes.

Méthodologie

1. Preuve de l'incomplétude de WL sur les spectres simples

Les auteurs établissent d'abord que l'ensemble de la hiérarchie WL est incomplet sur les graphes à spectre simple.

• Construction : Ils utilisent la construction de Cai–Fürer–Immerman (CFI), qui génère des paires de graphes non isomorphes indistinguables par le test $k$-WL.
• Encodage : Puisque les graphes CFI standards ne possèdent pas de spectre simple, les auteurs introduisent un nouveau mécanisme d'encodage entier. Ils transposent les motifs d'adjacence CFI dans une matrice orthogonale $\tilde{X}$ composée d'entrées entières.
• Formation de multigraphes : En utilisant cette matrice orthogonale et une matrice diagonale de valeurs propres entières distinctes, ils construisent une paire de multigraphes symétriques ($A_{G,0}$ et $A_{G,1}$) à spectres simples.
• Résultat : Ils prouvent que ces multigraphes à spectre simple construits restent indistinguables par le test $k$-WL, démontrant qu'aucun niveau de la hiérarchie WL ne peut résoudre le problème d'isomorphisme pour cette classe, malgré le fait que le problème soit soluble en temps cubique.

2. PRiSM : Une canonisation complète

Pour remédier aux limites des méthodes spectrales existantes, les auteurs proposent PRiSM (Partition, Refine, Solve, Match), une procédure de canonisation prouvée complète pour les décompositions spectrales des graphes à spectre simple.

• Entrée : Une matrice orthonormée par colonnes $U$ de vecteurs propres.
• Groupe d'ambiguïté : La procédure gère le groupe d'ambiguïté $S_n \times \{-1, 1\}^k$ (permutations et inversions de signe).
• Quatre étapes :
  1. Partition : Les sommets sont regroupés en fonction de leurs signatures invariantes par signe (valeurs absolues des entrées des vecteurs propres).
  2. Raffinement : Une variante spectrale de la procédure de raffinement de couleurs WL est appliquée à la partition. Cela affine itérativement les classes de sommets en utilisant le multi-ensemble des caractéristiques d'arêtes définies par les produits élément par élément des entrées des vecteurs propres ($U_v \odot U_u$) jusqu'à ce que la partition se stabilise.
  3. Résolution : La partition stable définit un système d'équations linéaires sur le corps $\mathbb{Z}_2$. Le système impose que chaque classe de partition contienne au moins une ligne avec des entrées non négatives. La résolution de ce système détermine les signes canoniques uniques pour les vecteurs propres (à automorphismes de graphe près).
  4. Appariement : Une fois les signes fixés, les lignes sont triées lexicographiquement pour résoudre l'ambiguïté de permutation, produisant une matrice canonique unique.
• Extension : Pour les graphes avec des valeurs propres répétées (spectre non simple), PRiSM est étendu de manière heuristique. Il applique la procédure de base au bloc à spectre simple ($m=1$) et utilise la décomposition QR et la sélection de pivots pour résoudre les espaces propres d'ordre supérieur ($m > 1$).

3. Garanties théoriques

• Complétude : PRiSM est prouvé comme étant une canonisation valide, ce qui signifie qu'il produit la même sortie pour des graphes isomorphes et des sorties différentes pour des graphes à spectre simple non isomorphes.
• Approximation universelle : En composant PRiSM avec un réseau d'ensembles universel (par exemple, DeepSets ou Transformers), le modèle résultant atteint l'approximation universelle pour toute fonction invariante par isomorphisme sur les graphes à spectre simple. Cela résout le problème ouvert de l'atteinte de la complétude pour les GNN spectraux sur cette classe.

Résultats clés

Résultats théoriques

• Théorème 1 : Pour tout nombre naturel $k$, il existe des multigraphes à spectre simple non isomorphes avec $\Theta(k)$ nœuds qui ne sont pas distingués par l'algorithme $k$-WL. Cela implique que toutes les familles de GNN alignées sur $k$-WL (y compris PPGN, $k$-GNNs et Graph Transformers) sont incomplètes sur les graphes à spectre simple.
• Théorème 2 : PRiSM fournit une canonisation valide pour les décompositions spectrales à spectre simple.
• Théorème 3 : Les modèles composés de PRiSM et de réseaux d'ensembles universels atteignent l'approximation universelle sur les graphes à spectre simple.

Performance empirique

Les auteurs ont évalué PRiSM sur trois benchmarks :

1. Benchmark d'expressivité BREC : PRiSM a surpassé les canonisations concurrentes (MAP, OAP) dans la distinction de paires de graphes non isomorphes, en particulier sur les catégories Regular et Extension. Il a correctement distingué 212/360 paires contre 199/360 pour MAP/OAP.
2. Prédiction de propriétés moléculaires (ZINC, OGB-Mol) : PRiSM a atteint des performances de pointe ou égales aux meilleures sur les tâches de régression moléculaire (ZINC) et de classification (MOLTOX21, MOLPCBA) en utilisant à la fois les architectures GatedGCN et PNA.
3. Architectures Transformer (OGB, Alchemy) : Lorsqu'il est utilisé comme encodage de position pour les Graph Transformers, PRiSM a surpassé toutes les lignes de base (LPE, MAP, OAP) sur les quatre jeux de données (MOLHIV, MOLCLINTOX, MOLBBBP, ALCHEMY). Les auteurs attribuent cela au fait que PRiSM fournit un ordre déterministe des sommets en plus des vecteurs propres corrigés de signe, ce qui est crucial pour les mécanismes d'attention des Transformers.

Importance et revendications

L'article revendique la résolution d'un écart fondamental dans la compréhension théorique de l'expressivité des GNN et des méthodes spectrales :

1. Incomplétude de WL : Il prouve définitivement que la hiérarchie WL, malgré sa puissance croissante, ne peut pas distinguer tous les graphes à spectre simple, une classe où l'isomorphisme est théoriquement facile.
2. Première canonisation complète : PRiSM est présenté comme la première canonisation de signe prouvée complète pour les décompositions spectrales à spectre simple, surmontant les limites des méthodes précédentes comme MAP et OAP qui sont incomplètes sur cette classe.
3. Approximation universelle : Le travail établit que les GNN spectraux peuvent atteindre l'approximation universelle sur les graphes à spectre simple s'ils sont associés à une canonisation complète comme PRiSM, justifiant ainsi l'utilisation d'encodages de position canonisés du Laplacien.
4. Utilité pratique : Empiriquement, la méthode démontre que la résolution complète des ambiguïtés spectrales conduit à des améliorations tangibles dans les tâches en aval, surpassant les approches existantes invariantes par signe et de canonisation.

Les auteurs notent des limitations, spécifiquement que la garantie de complétude s'applique strictement aux graphes à spectre simple (ou aux multigraphes construits dans la preuve) et que la procédure de canonisation est discontinue, une propriété qu'ils soutiennent être mathématiquement inévitable pour les canonisations de signe complètes. Ils laissent également l'extension de la preuve d'incomplétude aux graphes combinatoires simples (sans arêtes multiples) comme travail futur.