Topological Message Passing, Computation Graphs, and Relational Structures: A Case Study on Oversquashing

Topological neural networks (TNNs) extend graph neural networks (GNNs) to simplicial complexes, cellular complexes, and other higher-order structures, to model topological features and higher-order interactions. As TNNs become more widely adopted, developing a better theoretical understanding of their properties becomes crucial. One phenomenon of interest is oversquashing, which is the compression of exponentially many features into fixed-width representations, which often degrades GNN performance on tasks. Even though oversquashing has been well studied in GNNs, it has remained largely unexamined for TNNs. In this talk, we present a first step toward a rigorous treatment of oversquashing in TNNs: We axiomatically model the computation graphs corresponding to TNNs as finite relational structures, and using this formulation we extend the results on oversquashing in GNNs to TNNs. In particular, we introduce "influence graphs" that model aggregate information flow in higher-order networks, and leverage these graphs to carry out higher-order sensitivity analysis, introduce new relevant higher-order discrete curvatures, establish bounds on the impact of local geometry and network depth, and quantify how hidden dimensions affect oversquashing. Lastly, we present a relational rewiring heuristic that adapts graph-rewiring techniques to higher-order networks, and demonstrably improves TNN performance in a manner consistent with graph rewiring. This talk is based on joint work with James Chapman, Marzieh Eidi, Karel Devriendt, and Guido Montúfar.