Récemment, le test d'isomorphisme de graphes de Weisfeiler-Lehman (WL) a été utilisé pour mesurer la puissance expressive des réseaux neuronaux de graphes (GNN). Il a été démontré que les GNN populaires basés sur le passage de messages ne peuvent pas distinguer entre des graphes qui sont indiscernables par le test 1-WL (Morris et al. 2018 ; Xu et al. 2019). Malheureusement, de nombreux exemples simples de graphes sont indiscernables par le test 1-WL.Dans notre recherche de modèles d'apprentissage de graphes plus expressifs, nous nous appuyons sur les récents réseaux neuronaux de graphes invariants et équivariants d'ordre k (Maron et al. 2019a,b) et présentons deux résultats :Premièrement, nous montrons que ces réseaux d'ordre k peuvent distinguer entre des graphes non isomorphes aussi bien que les tests k-WL, qui sont prouvés être plus puissants que le test 1-WL pour k > 2. Cela rend ces modèles strictement plus forts que les modèles basés sur le passage de messages. Malheureusement, l'expressivité accrue de ces modèles est accompagnée d'un coût computationnel lié au traitement de tenseurs d'ordre élevé.Deuxièmement, en visant la construction d'un modèle simple, pratique et évolutif avec une puissance expressive garantie supérieure, nous démontrons qu'un réseau réduit d'ordre 2 contenant uniquement un opérateur identité scalaire, augmenté d'une seule opération quadratique (multiplication matricielle), possède une puissance expressive garantie équivalente à celle du test 3-WL. Autrement dit, nous proposons un modèle simple qui alterne des applications d'un perceptron multicouche standard (MLP) sur la dimension des caractéristiques et des multiplications matricielles. Nous validons ce modèle en présentant des résultats à l'état de l'art sur des tâches populaires de classification et de régression de graphes. À notre connaissance, c'est le premier modèle invariant/équivariant pratique doté d'une puissance expressive garantie équivalente à celle du test 3-WL, strictement supérieure aux modèles basés sur le passage de messages.