Wir präsentieren eine Verallgemeinerung von Transformers auf permutationsinvariante Daten beliebiger Ordnung (Mengen, Graphen und Hypergraphen). Zunächst beobachten wir, dass Transformers DeepSets verallgemeinern, also perkussionsinvariante MLPs erster Ordnung (mit Mengeneingaben). Anschließend erweitern wir den Begriff der Selbst-Attention auf höhere Ordnungen basierend auf kürzlich charakterisierten perkussionsinvarianten MLPs höherer Ordnung und schlagen höhere-Ordnungs-Transformers für Daten der Ordnung $k$k vor ($k=2$k=2 für Graphen und $k>2$k>2 für Hypergraphen). Leider haben höhere-Ordnungs-Transformers eine verbotene Komplexität von $\mathcal{O}(n^{2k})$O(n2k) in Abhängigkeit von der Anzahl der Eingabeknoten $n$n. Um dieses Problem zu lösen, präsentieren wir dünnbesetzte höhere-Ordnungs-Transformers, die eine quadratische Komplexität in Bezug auf die Anzahl der Eingabe-Hyperkanten haben, und verwenden ferner den Kernel-Attention-Ansatz, um die Komplexität auf lineare zu reduzieren. Insbesondere zeigen wir, dass dünnbesetzte Transformern zweiter Ordnung mit Kernel Attention theoretisch ausdrucksstärker sind als Message-Passing-Operationen, während sie asymptotisch dieselbe Komplexität besitzen. Unsere Modelle erzielen signifikante Leistungsverbesserungen gegenüber perkutionsinvarianten MLPs und Message-Passing-GNNs in Aufgaben des großen Graphenregressionsproblems und der Mengen-zu-(Hyper-)Graph-Vorhersage. Unsere Implementierung ist unter https://github.com/jw9730/hot verfügbar.