Weisfeiler et Leman s’affinent : Vers des plongements de graphes d’ordre supérieur plus scalables

Les noyaux de graphes basés sur l'algorithme de Weisfeiler-Leman unidimensionnel ($1$-dimensionnel) et les architectures neuronales correspondantes sont récemment apparus comme des outils puissants pour l'apprentissage supervisé avec des graphes. Cependant, en raison de leur nature purement locale, ces algorithmes peuvent manquer des motifs essentiels dans les données fournies et ne peuvent traiter que des relations binaires. L'algorithme de Weisfeiler-Leman $k$-dimensionnel remédie à cela en considérant des $k$-uplets définis sur l'ensemble des sommets et en établissant une notion appropriée d'adjacence entre ces uplets de sommets. Ainsi, il prend en compte les interactions d'ordre supérieur entre les sommets. Cependant, cet algorithme ne se généralise pas bien et peut souffrir de surapprentissage lorsqu'il est utilisé dans un contexte d'apprentissage automatique. Il reste donc un problème important et ouvert de concevoir des méthodes d'apprentissage de graphes basées sur le WL qui soient simultanément expressives, évolutives et résistantes au surapprentissage. Dans ce travail, nous proposons des variantes locales et les architectures neuronales correspondantes, qui considèrent un sous-ensemble du voisinage original, ce qui les rend plus évolutives et moins sujettes au surapprentissage. La puissance expressive (de l'un) de nos algorithmes est strictement supérieure à celle de l'algorithme original en termes de capacité à distinguer des graphes non isomorphes. Notre étude expérimentale confirme que les algorithmes locaux, tant les noyaux que les architectures neuronales, conduisent à des temps de calcul considérablement réduits et préviennent le surapprentissage. La version noyau établit un nouveau niveau d'état de l'art pour la classification de graphes sur une large gamme de jeux de données基准数据集 (benchmark datasets), tandis que la version neuronale montre des performances prometteuses pour les tâches de régression moléculaire à grande échelle.Note: "基准数据集" a été conservé en chinois car il s'agit d'un terme spécifique qui n'a pas d'équivalent direct en français dans ce contexte. Si vous préférez une traduction plus générale, vous pouvez utiliser "jeux de données standards" ou "jeux de données références".