Élargir l'espace de conception des réseaux neuronaux graphiques en repensant le Weisfeiler-Lehman folklorique

Les réseaux neuronaux à passage de messages (MPNNs) sont apparus ces dernières années comme le cadre le plus populaire des réseaux neuronaux sur graphes (GNNs). Cependant, leur puissance expressive est limitée par le test de Weisfeiler-Lehman en dimension 1 (1-WL). Certains travaux s'inspirent du $k$-WL/FWL (Weisfeiler-Lehman Folklore) pour concevoir les versions neuronales correspondantes. Malgré leur forte puissance expressive, ces recherches présentent des limitations importantes. En particulier : (1) le $k$-WL/FWL nécessite une complexité spatiale d'au moins $O(n^k)$, ce qui est impraticable pour les grands graphes même lorsque $k=3$ ; (2) l'espace de conception du $k$-WL/FWL est rigide, avec le seul hyperparamètre ajustable étant $k$. Pour résoudre la première limitation, nous proposons une extension, $(k,t)$-FWL. Nous démontrons théoriquement que même si nous fixons la complexité spatiale à $O(n^k)$ (pour tout $k\geq 2$) dans $(k,t)$-FWL, nous pouvons construire une hiérarchie d'expressivité jusqu'à résoudre le problème d'isomorphisme de graphes. Pour aborder la deuxième problématique, nous proposons $k$-FWL+, qui considère tout ensemble équivariant comme voisin au lieu de tous les nœuds, ce qui élargit considérablement l'espace de conception du $k$-FWL. La combinaison de ces deux modifications aboutit à un cadre flexible et puissant, $(k,t)$-FWL+. Nous montrons que $(k,t)$-FWL+ peut implémenter la plupart des modèles existants avec une expressivité équivalente. Nous introduisons ensuite une instance de $(k,t)$-FWL+ appelée Neighborhood$^2$-FWL (N$^2$-FWL), qui est solide tant sur le plan pratique que théorique. Nous prouvons que N$^2$-FWL est au moins aussi puissant que 3-WL et peut encoder de nombreuses sous-structures tout en ne nécessitant qu'une complexité spatiale de $O(n^2)$. Enfin, nous concevons sa version neuronale nommée N$^2$-GNN et évaluons ses performances sur diverses tâches. N$^2$-GNN obtient des résultats historiques sur ZINC-Subset (0,059), surpassant les résultats SOTA précédents de 10,6 %. De plus, N$^2$-GNN atteint de nouveaux résultats SOTA sur l'ensemble de données BREC (71,8 %) parmi toutes les méthodes GNN existantes à haute expressivité.