Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing

Diaaeldin Taha, James Chapman, Marzieh Eidi, Karel Devriendt, Guido Montúfar, [6pt] Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany · 2025

Read Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing by Diaaeldin Taha, James Chapman, Marzieh Eidi, Karel Devriendt, Guido Montúfar, [6pt] Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06582.txt.

Introduction

Diaaeldin Taha, James Chapman, Marzieh Eidi, Karel Devriendt, and Guido Montúfar reframed topological message passing in 2025. Topological deep learning models data with higher-order links, not just pairwise edges. One flaw, oversquashing, squeezes long-range news through narrow bottlenecks, and it was little studied in this setting.

The authors build a unifying framework that views both graphs and higher-order complexes as relational structures. That lens lets graph results and algorithms extend to simplicial and cellular message passing. They use it to analyze oversquashing and to suggest ways to ease it. Theory plus tests on simplicial networks, they argue, show the frame's promise for the field.

Catalog record

CREATORDiaaeldin Taha, James Chapman, Marzieh Eidi, Karel Devriendt, Guido Montúfar, [6pt] Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE134 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-06582

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing Diaaeldin Taha, James Chapman, Marzieh Eidi, Karel Devriendt, Guido Montúfar, [6pt] Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany Abstract Topological deep learning (TDL) has emerged as a powerful tool for modeling higher-order interactions in relational data. However, phenomena such as oversquashing in topological message-passing remain understudied and lack theoretical analysis. We propose a unifying axiomatic framework that bridges graph and topological message-passing by viewing simplicial and cellular complexes and their message-passing schemes through the lens of relational structures. This approach extends graph-theoretic results and algorithms to higher-order structures, facilitating the analysis and mitigation of oversquashing in topological message-passing networks. Through theoretical analysis and empirical studies on simplicial networks, we demonstrate the potential of this framework to advance TDL. 1 Introduction Recent years have witnessed a growing recognition that traditional machine learning, rooted in Euclidean spaces, often fails to capture the complex structure and relationships present in real-world data. This shortcoming has driven the development of geometric deep learning (GDL) ( Bronstein et al. 2021 ) and, more recently, topological deep learning (TDL) ( Hajij et al. 2023 ) , for handling non-Euclidean and relational data. TDL, in particular, has emerged as a promising frontier for relational learning, that extends beyond graph neural networks (GNNs). TDL offers tools to capture and analyze higher-order interactions and topological features in complex data and higher-order structures, such as simplicial complexes, cell complexes, and sheaves ( Hajij et al. 2023 ) . However, the TDL field is young, and the TDL community has yet many open theoretical and practical questions relating to, e.g., oversquashing and rewiring (research directions 2 and 9 of Papamarkou et al. 2024 ). Oversquashing is a challenging failure mode in GNNs, where information struggles to propagate across long paths due to the compression of an exponentially growing number of messages into fixed-size vectors ( Alon & Yahav 2021 ) . This phenomenon has been examined through various perspectives, including curvature ( Topping et al. 2022 ) , graph expansion ( Banerjee et al. 2022 ) , effective resistance ( Black et al. 2023 ) , and spectral properties ( Karhadkar et al. 2023 ) . Despite the potential of higher-order message passing architectures—such as simplicial neural networks ( Ebli et al. 2020 ) , message passing simplicial networks ( Bodnar et al. 2021b ) , and CW networks ( Bodnar et al. 2021a ) —there remains a lack of unified frameworks for analyzing and mitigating oversquashing in these settings. In this paper, we take a first step toward studying oversquashing in TDL by showing that simplicial complexes and their message passing schemes can be interpreted as relational structures, making it possible to extend key GNN insights and tools to higher-order message passing architectures. The conceptual framework and theoretical results developed in this paper address pressing questions in the TDL community (e.g., research directions 2 and 9 of Papamarkou et al. 2024 ). Contributions. Our contributions are threefold: • Axiomatic : We provide a unifying view of simplicial complexes and their message passing schemes through the lens of relational structures. • Theoretical : We introduce influence graphs which enable novel extensions of prior graph analyses to higher-order structures, where existing methods for analysis do not apply. We extend graph-theoretic concepts and results on oversquashing to relational structures, analyzing network sensitivity (Lemma 3.2 ), local geometry (Proposition 3.4 ), and the impact of network depth (Theorem 3.5 ) and hidden dimensions (Section 3.4 ). • Practical : We propose a heuristic to extend oversquashing-mitigation techniques from graph-based models to relational structures. Related Work. Our work sits at the intersection of graph neural networks, topological deep learning, relational learning, and the study of oversquashing and graph rewiring in graph neural networks. We review related work in Appendix A . The rest of this paper is organized as follows: Section 2 provides the axiomatic groundwork for relating simplicial and relational message passing. Section 3 presents our theoretical analysis of oversquashing in this context. Section 4 introduces a heuristic rewiring strategy to mitigate oversquashing in relational message passing. Section 5 presents our experimental results, followed by a discussion and conclusions in Section 6 . 2 Simplicial Complexes are Relational Structures In this section, we reinterpret simplicial complexes and message passing through the lens of relational structures . We begin by recalling simplicial complexes and a representative simplicial message passing scheme, then reframe these notions within a relational framework. We illustrate the definitions in this section with a small worked example in Appendx H . We note that the connection we establish here extends to other higher-order structures, such as cellular complexes ( Hansen & Ghrist 2019 ; Bodnar et al. 2021a ; Giusti et al. 2024 ) . 2.1 Simplicial Complexes and Message Passing Simplicial complexes are mathematical structures that generalize graphs to higher dimensions, capturing relationships among vertices, edges, triangles, and higher-dimensional objects. Definition 2.1 (Simplicial Complex, Nanda 2021 ) . Let V be a non-empty set. A simplicial complex \mathcal{K} is a collection of non-empty subsets of V that contains all the singleton subsets of V and is closed under the operation of taking non-empty subsets. A member \sigma=\{v_{0},v_{1},\ldots,v_{d}\}\in\mathcal{K} with cardinality |\sigma|=d+1 is called a d -simplex . Geometrically, 0 -simplices are vertices, 1 -simplices are edges, 2 -simplices are triangles, and so on. Definition 2.2 (Boundary Incidence Relation) . We say that \tau covers \sigma , written \sigma\prec\tau , iff \sigma\subsetneq\tau and there is no \delta\in\mathcal{K} such that \sigma\subsetneq\delta\subsetneq\tau . The incidence relations from Definition 2.2 can be used to construct four types of (local) adjacencies. Definition 2.3 . Consider a simplex \sigma\in\mathcal{K} . Four types of adjacent simplices can be defined: 1. Boundary adjacency : \mathcal{B}(\sigma)=\{\tau\colon\tau\prec\sigma\} ; 2. Co-boundary adjacency : \mathcal{C}(\sigma)=\{\tau\colon\sigma\prec\tau\} ; 3. Lower adjacency : \mathcal{N}_{\downarrow}(\sigma)=\{\tau\colon\exists\delta\text{ such that }\delta\prec\tau\text{ and }\delta\prec\sigma\} ; 4. Upper adjacency : \mathcal{N}_{\uparrow}(\sigma)=\{\tau\colon\exists\delta\text{ such that }\tau\prec\delta\text{ and }\sigma\prec\delta\} . In Figure 1 , we illustrate an example of a simplicial complex and its adjacency relations. 0 1 2 3 4 (a) Simplicial Complex \mathcal{K} \{2,3,4\} \{0,1\} \{1,2\} \{2,3\} \{2,4\} \{3,4\} \{0\} \{1\} \{2\} \{3\} \{4\} \rightarrow Boundary \rightarrow Co-boundary \rightarrow Lower \rightarrow Upper (b) Adjacency Relations on \mathcal{K} Figure 1: The left panel shows a simplicial complex \mathcal{K} consisting of five vertices, five edges, and one triangle. The right panel shows the corresponding adjacency relations depicted as arrows to each simplex \sigma\in\mathcal{K} emanating from each of its adjacent simplices in \mathcal{B}(\sigma) , \mathcal{C}(\sigma) , \mathcal{N}_{\downarrow}(\sigma) , \mathcal{N}_{\uparrow}(\sigma) . We now, following Bodnar et al. 2021b , review a general scheme for message passing on simplicial complexes. In Appendix A , we provide references for topological message passing architectures that fit this scheme. We refer readers to Appendix F.5 for specific instantiations of this scheme in our graph and topological message passing models. Simplicial message passing extends graph message passing from pairwise node connections to higher-dimensional adjacency connections between simplices. Message passing schemes on simplicial complexes iteratively update feature vectors assigned to simplices by exchanging messages between adjacent simplices. For a simplicial complex \mathcal{K} , we denote the feature vector of a simplex \sigma\in\mathcal{K} as \mathbf{h}_{\sigma}\in\mathbb{R}^{p} . At each iteration

Read the complete text