Abstract
Higher-order graph neural networks (HOGNNs) are an important class of GNNmodels that harness polyadic relations between vertices beyond plain edges.They have been used to eliminate issues such as over-smoothing orover-squashing, to significantly enhance the accuracy of GNN predictions, toimprove the expressiveness of GNN architectures, and for numerous other goals.A plethora of HOGNN models have been introduced, and they come with diverseneural architectures, and even with different notions of what the"higher-order" means. This richness makes it very challenging to appropriatelyanalyze and compare HOGNN models, and to decide in what scenario to usespecific ones. To alleviate this, we first design an in-depth taxonomy and ablueprint for HOGNNs. This facilitates designing models that maximizeperformance. Then, we use our taxonomy to analyze and compare the availableHOGNN models. The outcomes of our analysis are synthesized in a set of insightsthat help to select the most beneficial GNN model in a given scenario, and acomprehensive list of challenges and opportunities for further research intomore powerful HOGNNs.