Learning From Simplicial Data Based on Random Walks and 1D Convolutions

Triggered by limitations of graph-based deep learning methods in terms of computational expressivity and model flexibility, recent years have seen a surge of interest in computational models that operate on higher-order topological domains such as hypergraphs and simplicial complexes. While the increased expressivity of these models can indeed lead to a better classification performance and a more faithful representation of the underlying system, the computational cost of these higherorder models can increase dramatically. To this end, we here explore a simplicial complex neural network learning architecture based on random walks and fast 1D convolutions (SCRaWl), in which we can adjust the increase in computational cost by varying the length and number of random walks considered while accounting for higher-order relationships. Importantly, due to the random walk-based design, the expressivity of the proposed architecture is provably incomparable to that of existing message-passing simplicial neural networks. We empirically evaluate SCRaWl on real-world datasets and show that it outperforms other simplicial neural networks. In recent years, there has been a strong interest in extending graph-based learning methods, in particular graph neural networks, to higher-order domains such as hypergraphs and simplicial complexes. These higher-order abstractions offer a more comprehensive representation of relationships among entities than traditional graph-based approaches, which are based on pairwise interactions. Accordingly, it has been shown that we can achieve performance gains in various learning and prediction tasks for complex systems by employing such higher-order models (Benson et al., 2018; Schaub et al., 2021; Battiston & Petri, 2022). For instance, in the context of graph classification, it is well known that standard message-passing graph neural networks with anonymous inputs are limited in their expressiveness by the one-dimensional Weisfeiler-Leman graph isomorphism test (Morris et al., 2019; Xu et al., 2019; Morris et al., 2023) and thus cannot distinguish certain non-isomorphic graphs.