Rompre les goulets d’étranglement expressifs des réseaux neuronaux graphiques

Récemment, le test d'isomorphisme de graphes de Weisfeiler-Lehman (WL) a été utilisé pour mesurer l'expressivité des réseaux neuronaux de graphes (GNNs), montrant que les GNNs basés sur l'agrégation de voisinage étaient au maximum aussi puissants que le test 1-WL pour distinguer les structures de graphes. Des améliorations ont également été proposées en analogie avec le test $k$-WL ($k>1$). Cependant, les agrégateurs dans ces GNNs sont loin d'être injectifs comme requis par le test WL, et souffrent d'une faible capacité à distinguer, ce qui en fait des goulets d'étranglement en termes d'expressivité. Dans cet article, nous améliorons l'expressivité en explorant des agrégateurs puissants. Nous reformulons l'agrégation avec la matrice de coefficients d'agrégation correspondante, puis analysons systématiquement les exigences de cette matrice pour construire des agrégateurs plus puissants et même injectifs. Cette approche peut également être considérée comme une stratégie pour préserver le rang des caractéristiques cachées, et suggère que les agrégateurs de base correspondent à un cas particulier de transformations de rang faible. Nous démontrons également la nécessité d'appliquer des unités non linéaires avant l'agrégation, ce qui diffère de la plupart des GNNs basés sur l'agrégation. Sur la base de notre analyse théorique, nous avons développé deux couches GNN, ExpandingConv et CombConv. Les résultats expérimentaux montrent que nos modèles améliorent considérablement les performances, en particulier pour les grands graphes densément connectés.