Les Transformers généralisent les DeepSets et peuvent être étendus aux graphes et hypergraphes.

Nous présentons une généralisation des Transformers aux données invariantes par permutation d'ordre quelconque (ensembles, graphes et hypergraphes). Nous commençons par observer que les Transformers généralisent les DeepSets, ou MLPs invariantes par permutation de premier ordre (entrée en ensemble). Ensuite, en nous appuyant sur les caractérisations récentes des MLPs invariantes d'ordre supérieur, nous étendons le concept d'auto-attention à des ordres supérieurs et proposons des Transformers d'ordre supérieur pour les données d'ordre $k$ ($k=2$ pour les graphes et $k>2$ pour les hypergraphes). Malheureusement, ces Transformers d'ordre supérieur se révèlent avoir une complexité prohibitivement élevée $\mathcal{O}(n^{2k})$ en fonction du nombre de nœuds d'entrée $n$. Pour résoudre ce problème, nous présentons des Transformers d'ordre supérieur éparse dont la complexité est quadratique en fonction du nombre d'hyperarêtes d'entrée, et nous adoptons l'approche de l'attention à noyau pour réduire encore cette complexité à une linéaire. En particulier, nous montrons que les Transformers du deuxième ordre éparse avec attention à noyau sont théoriquement plus expressifs que les opérations de passage de messages tout en ayant une complexité asymptotiquement identique. Nos modèles obtiennent une amélioration significative des performances par rapport aux MLPs invariantes et aux réseaux neuronaux graphiques basés sur le passage de messages dans les tâches de régression sur grands graphes et de prédiction set-to-(hyper)graph. Notre implémentation est disponible à l'adresse https://github.com/jw9730/hot.