Demystifying Topological Message-Passing with Relational Structures: A Case Study on Oversquashing in Simplicial Message-Passing
Authors: Diaaeldin Taha
James Chapman
Marzieh Eidi
Karel Devriendt
Guido Montufar
Venue: ICLR 2025 Poster (2025)
Keywords: topological deep learning
oversquashing
rewiring
relational graph neural networks
simplicial complexes
relational structures
Primary area: learning on graphs and other geometries & topologies
TL;DR: We propose a framework that unifies graph and higher-order message passing schemes using relational structures to analyze oversquashing in simplicial message-passing, and propose a higher-order generalization of rewiring.

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.

Published as a conference paper at ICLR 2025
DEMYSTIFYING TOPOLOGICAL MESSAGE-PASSING WITH RELATIONAL STRUCTURES: A CASE STUDY ON OVERSQUASHING IN SIMPLICIAL MESSAGE-PASSING
DDiaaeldin Taha', "James Chapman?, Marzieh Eidi Karel Devriendt', Guido Montúfar1.2
Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany UCLA, CA, USA
Center for Scalable Data Analyties and Artificial Intelligence, Leipzig, Germany 'University of Oxford, Oxford, UK
taha@mis www..ppg........ de, chapman20 j /tteee.uaaaa......eeaaaaaaaeaala wcl.cclaaaoo. edu, meidi@mis mpg. de, karel. devrieviieee iendt @maths..... ox. ac. uk, montufar@math.ucl edd
ABSTRACT
Topological deep learning (TDL) has emerged as a powerful tool for modeling higher-order interactions relational data. However, phenomena such over- squashing in topological message-passing remain understudied and lack theoreti- cal 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 ap- proach 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 advance TDI.
INTRODUCTION
Recent years have witnessed a growing recognition that traditional machine learning, rooted in Eu- clidean spaces, often fails capture the complex structure and relationships present in real-world data. This shortcoming has driven the development of geometric deep learning (GDL) (Bronstein al. 2021) and, more recently, topological deep learning (TDL) (Haji) et 2023), for handling non non-Euclidean and relational data. TDL. in particular, has emerged as a promising frontier for rela- tional 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 struc- tures, 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 and 9 of Papamarkou et al. 2024).
Oversquashing is 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 (Tpppigg et al., 2022), graph expansion (Banerjee et al. 2022), effective resistance (Black et al.] 2023), and spectral properties (Karhadkar al.) (023). 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. (022b)) and CW networks Bodnar et al. (2021a) there remains lack of unified frameworks for analyzing and mitigating oversquashing in these settings.
In this paper, we take first step toward studying oversquashing in TDL by showing that simplicial complexes and their message passing schemes can be interpreted as relational structures, making
"Equal contribution.
Equul contribution.

---

Published as a conference paper at ICLR 2025
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 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 oversquashing relational structures, lyzing 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 wversuushinngmmiiigene 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 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 introduces a heuristic rewiring strategy to mitigate over- squashing in relational message passing. Section 3 presents our experimental results, followed by discussion and conclusions in Section
SIMPLICIAL COMPLEXES ARE RELATIONAL STRUCTURES
In this section, reinterpret simplicial complexes and message passing through the lens of rela- tional structures. We begin by recalling simplicial complexes and a representative simplicial mes- sage passing scheme, then reframe these notions within relational framework. We illustrate the definitions in this section with a small worked example in Appendx H We note that the connection establish here extends other higher-order structures, such 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 higher dimensions, cap- turing relationships among vertices, edges, triangles, and higher-dimensional objects.
Definition 2.1 (Simplicial Complex, Nanda [021). Let V be non-empty set. A simplicial complex is a collection of non-empty subsets of V that contains all the singleton subsets of and closed under the operation of laking non-empty subsets.
member a = {No, U1...., va) E with cardinality | d is called a d-simplex. Geometri- cally, 0- 0-simplices are vertices, 1-simplices edges, 2-simplices are triangles, and Definition 2.2 (Boundary Incidence Relation). We say that covers a, written - T, iff Ç T and there is no E K. such that a Ç T.
The incidence relations from Definition 2.2 2 can be used construct four types of (local) adjacencies.
Definition 2.3. Consider a simplex o E Four types of adjacent simplices can defined:
1. Boundary adjacency: B(a) {r: a.);
2. Co-boundary adjacency: C(a) = [
3. Lower adjacency: Ni(a) [T: 38 such that d < and 5 - a):
4. Upper adjacency: Nf(a) = {T: 38 such that t - and σ - 6).
In Figure I we illustrate example of simplicial complex and its adjacency relations.
We now, following Bodnar et al. 20021 Section 4), review a general scheme for message passing simplicial complexes. In Appendix
provide references for topological message passing architectures that fit this scheme. We refer readers to appendix[F53 [F55] for specific instantiations of this scheme in graph and topological message passing models.
2

---

Published as a conference paper at ICLR 2025
(2
3
0
1
(0. 1
1,
12 3
(2
33 4
4
(0)
1
(2)
3
(4)
Boundary
Co- Co-boundary
Lower
Upper
(a) Simplicial Complex I
(b) Adjacency Relations on K.
Figure 1: The left panel shows simplicial complex consisting of five vertices, five edges, and one triangle. The right panel shows the corresponding adjacency relations depicted as arrows each simplex emanating from each of adjacent simplices B(a), (())
Simplicial message passing extends graph message passing from pairwise node connections to nigher-dimensional adjacency connections between simplices. Message passing schemes on sim- plicial complexes iteratively update feature vectors assigned to simplices by exchanging messages between adjacent simplices. For simplicial complex K., we denote the feature vector of simplex
IC as h, Rº. At each iteration (layer) t, the feature vectors h of simplices E K. are up- dated by aggregating messages from adjacent simplices. For a simplex from adjacent simplices are defined as follows:
K, the messages passed
mg (t (o) AGG+eB(r) (Ma(h, (9) h, (9))
m (1 + (o) = AGGrec(o) (Mc (9) h, (9))
m. (t (o) AGG,eN1()) (M, h honr (())
m (o) = AGGGEN)()) (M, (0, 1,,,, (9, hour (0)).
Here AGG an aggregation function (e.g., sum or mean), and MB, Mc, My, M, are message func- tions (e.g., linear or MLP), Then, an update operation UPDATE (e.g., MLP) incorporates these four different types of incoming messages:
h (+++) I) UPDATE (h(), mg (a), m
(++1)
(o),
(++1) (o), m (++1)
(a), m ())
(o))
(2)
Finally, after the last iteration, read-out function is applied process the features to perform desired task, such as classification or regression.
2.2 RELATIONAL STRUCTURES AND MESSAGE PASSING
We model simplicial complexes and the above message passing scheme using relational structures. Definition 2.4 (Relational Structure, Hodges 1993). A relational structure R (S. Ri.... R²)
consists of finite set S of entities, and relations R C Smh where n, is the arity of R.
We note that modeling simplicial complexes relational structures generalizes powerful perspec- tive in which simplicial complexes and similar constructs are treated as augmented Hasse diagrams as demonstrated, for example, by Hajij et al. 2023). Ditan et al. (2024), and Papillon et al. (2024).
We now introduce general scheme for message passing on relational structures which encom- passes the simplicial message passing scheme from Section 2.1 This scheme is an extension of the relational graph convolution model from [Schlichtrrull et al. (2018) which allows for relations of different arities, not just binary relations.
Definition 2.5 (Relational Message Passing Model), relational message passing model on rela- tional structure R (8, Ri...., R&)) consists of:
Feature vectors: (!t E RR for each a S at layer t 2 0, initialized as h!S = x, (inpur features). Here, pt denotes the dimensionality of the feature vectors layer t.
3

---

Published as a conference paper at ICLR 2025
Message functions 3/ IR .... X R. RR (with ne arguments) for each relation Ra where i == 1.....,
......... .. Each message function lakes n, input feature vectors (corresponding to the target simplex and its n4 related simplices) and outputs a message vector of dimension Pia- The parameter n, represents the arity of the relation R4.
funstioon
Update function Φ0 R.m. x x.. TR - Rp The output dimension p+t1 specifies the dimensionality of the feature vectors at layer 1.
Shift operators A., E TRlgo" associated with each relation R4 for 1,...,k. For each
E S and & (EI....,EE.-1)) E - with (a,E) E R3 the element A represents the strength of the signal passed from to More specifically, for any combination of entities (SI, (,....,,mm) E S where the relation R₁ does not hold among the entities Çı, .2..... Sn. (i.e., (S1, S2.... ,......,,)))) Suz) & Rih. the tensor A R. satisfies A RR, Ka..a... 0.
The update rule is given by:
h((+1)
=61))
m
(f)
m
o.k
(t)
(3)
where for each i 1,...,,, k, the message m (1) received by over R2 is computed as:
Σ
Rg A
(1) o
h h (4)
h 1
(4)
$ES"4-1
Remark 2.6. The shift operators Definition 2.5 extend the definition of graph shift operators Mateos et al. [2019] Gama et al. 20200 Dasoulas et al. (202)) from graphs relational structures. Whereas relations indicate whether entities are connected, shift operators numerically encode these connections with weights.
In the context of message passing, a simplicial complex K. can be viewed as a relational structure R(K.) (S, R....., Rs), where S = K. are the entities, and R2 are relations defined follows: R {(o) : XC} (identity), R2 = {(aTT): : K, B(o)) (boundary), R3 = ((, e Kr E C(a)) (co-boundary), R4 ((0,T,8) : K, (o),
A (lower adjacency), Rs = ((a,T, T, : K,, E ( = UT} (upper adjacency). The message functions vb(() correspond to MB, Mc,Mp, My. the update function (t to UPDATE, and aggregation uses shift operators A R. This establishes an equivalence between message passing on the simplicial complex K. and the relational structure R(K).
Remark 2.7. The relational message passing scheme in Definition 2.5 encompasses relational graph neural networks (Schlichtkrull et al.) 2018), simplicial neural networks (Bodnar et al. 2027b), higher-onder graph neural networks (Morris et al. 2019 and cellular complex neural net- works (Bodnar al. 2021a). We demonstrate how higher-order graphs fit the relational framework in Appendix G
Takeaway Message (Axiomatic)
Simplicial complexes can be represented relational structures, where the entities sim- plices, and the relations capture the adjacency among simplices of different dimensions. Sim- plicial message passing an instance of relational message passing on these structures.
3 OVERSQUASHING IN RELATIONAL MESSAGE-PASSING
The existing literature oversquashing in GNNs does not directly address relational message pass- ing. this section, we address that gap by deriving new extensions of key results on oversquashing in GNNs to relational message passing. We illustrate the definitions in this section with small worked example in Appendx
In our analysis of relational structures and message passing schemes, naturally encounter matri- ces and graphs that capture the aggregated influence of the underlying shift operators. For conve- nience, introduce notation for these matrices and graphs. For each relation R2 of arity n, with
4

---

Published as a conference paper at ICLR 2025
shift operator A AR, we define the matrix À R.
E IR 20
S|x|S|
Σ SES
A R
S in 2 O, E S.
(5)
This matrix captures all possible ways an entity T can influence entity a via the relation R. Specif- ically, it sums over all positions j where can appear among the arguments of the shift operator A A,, and over all possible combinations of the other entities &.
We aggregate these matrices over all relations to form the aggregated influence matrix A
R
|
R
6
Next, we define the augmented influence matrix B, which plays the role of an augmented adjacency matrix in our analysis:
B ==
where 7 = max, EEEShI- A.. is the maximum row sum of Á.
Lastly, we introduce graphs that capture the aggregated message passing dynamical structure implied by the relational structure and the message passing scheme.
Definition 3.1 (Influence Graph). Given a relational structure R = (S, Ri,..., R&) and a rela- tional message passing scheme with update rule given by Equation 3 and given Q E {A, B}, where A and B are defined by Equations 6 and 7 respectively. we define the influence graph G(S, === = (S,E, w) as follows: The set of entities (i.e., nodes) is S. The set of edges con- sists of directed edges from entity to entity for each pair (a, E S x S with Qr > 0. Each edge from T to a is assigned weight w- = QQaTT.
As we will see next, these graphs make it possible to leverage and extend graph-theoretic concepts, results, and intuition to understand and analyze the behavior of relational message passing schemes.
3.1 SENSITIVITY ANALYSIS
We now analyze the sensitivity of relational message passing changes in the input features. This analysis is crucial for understanding how information propagates through the network and for iden- tifying potential bottlenecks or oversquashing effects. We begin with a standard assumption about the boundedness of the Jacobians of the message and update functions.
Assumption (Bounded Jacobians), All message functions tb²") and update functions Φl are differentiable with bounded Jacobians: There exist constants 3,16) and (()) such that [|0xb,!)) /Obrl1 < 3,10) for any inpul feature vector ha and (1001 /0m,)l S ( for any mes- sage input mj. We write g(0) max; (6)
Our main result on sensitivity is the following, which is a novel extension of GNN sensitivity anal- ysis results (c.g.. Topping et al. 2022, Lemma and Di Giovanni et al. 2023 Theorem 3.2) to relational (and topological) message passing, We provide the proof in Appendix C.I
Lemma 3.2 (Sensitivity Bound for Relational Message Passing), Consider a relational structure R (S, Ra...., R&) with update rule given by Equation 3 Bnnd satisfying Assumption 7 Then, for
any a, r E S and t > 0, the Jacobian at layer with respect to the input features (t 0) satisfies
(4) Th 0h! (0)
[-1
II F=o
a 3(0
(B')..
(8)
Thus, the bound on the Jacobian of the o-feature with respect to the input r-feature depends on the (a, -e-etry of the f-th matrix power B', which reflects the number and strength of t-length paths from to a in the graph G(S, B). Structural properties of G(S, B) that lead to small val- of (B²)a,r such as bottlenecks or long distances between nodes, therefore contribute to the phenomenon of oversquashing, where the influence of distant entities is diminished.
5

---

Published as a conference paper at ICLR 2025
As demonstrated throughout this work, result offers systematic framework for extending other theoretical findings on oversquashing in graphs, which do not directly apply to simplicial com- plexes and similar relational structures. This includes the influential works by Topping et al. (2022).
Di Giovanni et al. (2023), and Fesser & Weber 2023). By leveraging our axiomatic framework, we derive principled extensions on the impact of local geometry (Section [32]). depth (Section (.3). and hidden dimensions (Section 3.4) in higher-order message passing, addressing settings where prior results are not applicable. Additionally, this result offers clear approach for deriving analogs of key quantities such as curvature (Definition 3.3) and can serve as guide for future work.
3.2 THE IMPACT OF LOCAL GEOMETRY
Lemma 3.2 shows that the entries of the matrix B which encode the number and strength of connec- tions in relational message passing scheme, control feature sensitivity. Prior works relate similar bounds to notions discrete curvature for unweighted undirected graphs, such as balanced Forman curvature (Topping et al. 2022), Ollivier-Riect curvature (Nguyen et al., 2023), and augmented For- man curvature (Fesser & Weber 2023). via counting local motifs, such as triangles and squares, in the underlying graphs. Following this approach, we derive result analogous to Fesser & Weber [203 Proposition 3.4), introducing a motif-counting quantity inspired by the augmented Forman curvature, but adapted for the particular weighted directed graphs arising in setting.
Definition 3.3. Let G (S,E, w) be a weighted directed graph with entities (nodes) S, edges E, and edge weights w: E - 1Rz0- For each entity E S, define the weighted out-degree w Eit-ooEE Wh-ro and the weighted in-degree w. = (o- W For an edge (r - o) E, define the weighted triangle count WT Eees W We-ver and the weighted quadrangle count Wr = -Egisaes Wx-+E1 WW11+t22 Wo2-oo- Then, the extended Forman curvature of the edge (r + o) is defined as:
EFCg(T, 4 w. we 3wT 2
(9)
We immediately get the following result, inspired by Nguyen et al. (2023) Proposition 4.4) and
Fesser & Weber (2023, Proposition 3.4), and which is exemplary of results connecting sensitivity analysis to notions discrete curvature. We provide the proof in Appendix C.2
Proposition 3.4. Consider relational structure R- = (S, RI...., RR) with update rule given by Equation 3 and satisfying Assumption 7 Denote G(S, Then, for any o, T E S with an edge
(T σ) G. the following holds:
!h!2 (2)
II a 310)
[BFCO(T,O) + w. + wi
(10)
0h [0]
In principle, a similar result using balanced Forman curvature (as in Topping et al. 2022 Theo- rem 4) is possible using framework, and we leave that extension for future work. Connections to Ollivier-Rieci curvature are discussed in Appendix B.1
We present experimental analyses related to curvature relational structures in Section D.3 (edge curvature distribution) and Appendices[D.1 (edge (edge curvature visualization) and [.2 (weighted curva- ture). We further propose relational extension of curvature-based rewiring techniques in Section and empirically analyze the impact of relational rewiring using real-world and synthetic benchmarks in Sections 5.1 and 5.2 respectively.
3.3 THE IMPACT OF DEPTII
To facilitate our analysis of depth, we make the following non-restrictive assumptions: Assumption (Row-Normalizedd Shift Operators). Each shift operator A R, associated with relation
R, is row-normalized, such that for all a E S,
11. if A A R. 00,
Σ
A A
(1I)
0,
if
Ee A 0.
E
Assumption (Bounded (1) and ). There exist constants O'max 0 and Bmax > such that for all layers f, al < Ommax and ((0) < Buax-

---

Published as a conference paper at ICLR 2025
We now present our main result the impact of depth in relational message passing, extending a previous result by Di Giovanni et al. (2023) Theorem 4.1) to our setting. We provide the proof in Appendix C.3 By the combinatorial distance from T to a in the graph G(S, A), we mean the in the graph. Similarly, by combinatorial length of a directed path, we mean the number edges in the path.
smallest number of edges in directed path from
Theorem 3.5 (Impact of Depth on Relational Message Passing). Consider a relational structure R = (S, R R2) with update rule given by Equation and satisfying Assumptions 7 2 and
3
Let T, E S be entities such that the combinatorial distance from T to a in the graph ( A) is Denote by we(a, T) the number of directed paths from G(S, A). Then, for any O S m < T, there exists a constant C > O, depending only on Omax Bmax. k. and m, but not nor the specific relations in R, such that
of combinatorial length at most in
ahg (r+m)
Cwr+m (a, m20mm P MY,
(12)
2h (0)
where M maX An,..
This result indicates that the sensitivity can decay exponentially with depth when M 1 1/(20max Bmax); particularly when the number of walks w)(a,7) is limited by the structure of G(S, A). Such exponential decay is a characteristic of the oversquashing phenomenon, where infor- mation from distant nodes becomes increasingly compressed, reducing its influence on the output.
We present experimental validation of this result in Section 5.2
3.4 THE IMPACT OF HIDDEN DIMENSIONS
In situations where the Lipschitz constants of the message and update functions from Assumption ! are affected by hyperparameters, such as the widths of neural networks implementing said functions, one can have ((0) (pp.,) and (6) O(p41)). This is the case, for instance, when the message and update functions are shallow neural networks (see Appendix [B.2] and Appendix C.4).
Writing p/. max; Pi, and substituting ((0) O(p') and (2) =O(pe+1) into the bound from Lemma 3.2. one gets:
The
[II pe+1 p'e
SC.
(B') (B').r"
(13)
Th (0)
where C' is a constant independent of the layer widths. p is the maximum dimension of the message vectors at layer f, and Pe+1 is the output dimension of the update function at layer f.
This implies that low hidden dimensions in the message and update functions contribute to a low sensitivity upper bound, which can exacerbate the oversquashing problem. Increasing the hidden dimensions will raise the upper bound, which can help improve the model's ability to propagate information effectively and enhance performance tasks. However, increasing the hidden dimen- sions risks overfitting due to the increased model complexity (Bartlett et al. 2017).
We present experimental validation of this result in Section 5.2
Takeaway Message (Theoretical)
By reformulating higher order structures relational structures, key results oversquashing in graph neural networks extend to relational message passing schemes through the aggregated influence matrix and the influence graph. This conceptual framework enables analysis of the impact of local geometry, depth, and hidden dimensions in relational message passing schemes, just as in graph neural networks.
4 REWIRING HEURISTICS FOR RELATIONAL STRUCTURES
Inspired by First-Order Spectral Rewiring (FoSR) (Karhadkar et al. 2023), we propose a rewiring heuristic that integrates additional connections into relational structure without altering its original
7

---

Published as a conference paper at ICLR 2025
connections. To capture the overall connectivity of relational structure, define the collapsed adjacency matrix, which counts the number of direct connections between entities.
Definition 4.1 (Collapsed Adjacency Matrix), Given a relational structure R = R...... Rk), the collapsed adjacency matrix A cal for the structure R is defined by:
k
col O,T
Σ Σ EES
((0.)ER..=Z) for some jE m. 0, O,TES.
(14)
i=1
This matrix captures direct connections between entities through any relation, effectively collapsing the relational structure into graph. Our proposed relational rewiring algorithm is as follows.
Algorithm Relational Rewiring Algorithm
Require: Relational structure R. (8, ....... Rx); graph rewiring algorithm REWIREALGO
1: Construct the collapsed adjacency matrix Aol (Definition 4.1
2: Build the graph g A )ol)
3: Apply REWIREALGO to Godl to obtain additional edges Enow
4: Define new relation R&+11 Frew
5: Update the relational structure: R = Rs, Rs, Rk+1)
Adding new connections (Enew) without removing existing ones improves the model capacity to cap- ture long-ram rang-range dependencies while preserving the original relational structure. We experimentally analyze the impact of relational rewiring using real-world and synthetic benchmarks in Sections 5.1 and [.22 respectively. Future work could explore rewiring algorithms that remove or reclassify edges, such spectral pruning (Jamadandi al. 2024), either by re-labeling the edges relations or by deletion. We report preliminary empirical results on pruning Appendix D
Takeaway Message 3 (Practical)
Graph rewiring techniques for improving information flow and mitigating oversquashing can be adapted to relational structures. This approach improves long-range connectivity and enhances message propagation while maintaining the integrity of the original connections.
5 EXPERIMENTS AND RESULTS
5.1 REAL-WORLD BENCHMARK: GRAPH CLASSIFICATION
We run an empirical analysis with real-world datasets to compare the performance of different graph, relational graph, and simplicial message passing models, and the impact of relational rewiring on said models. We provide more details in Appendix E
Task and Datasets. We use graph classification tasks ENZYMES, IMDB-B, MUTAG, NCII, and PROTEINS from the TUDataset (Morris et al. 2020) for evaluation.
Graph Lifting. For the topological message passing models, graphs are separately treated com- plexes with only graph nodes (0-dimensional simplices) and upper adjacencies, and also lifted into clique and ring complexes (see appendix).
Models. We evaluate three types of models: a) Graph message pussing models: SGC (Wu et al. 2019) GCN (Kipf & Welling. 2017), and GIN (Xu al. 2019); b) Relational graph message passing models: RGCN (Schlichtkrull et al. 2018) and RGIN; c) Topological message passing models: SIN (Bodnar et al. 2021b). CIN (Bodnar et al. 2021a), and CIN++ (Giusti et al. 2024).
Relational Rewiring. We apply relational rewiring for 40 iterations (Section 4) using three choices for REWIREALGO: SDRF (Topping et al. 2022). FoSR (Karhadkar et al. 2023 ). and AFRC (Fesser & Weber 2023). Due to computational constraints,
run the three choices all datasets except IMDB with Clique graph lifting, where we only run FoSR. We use fixed, dataset- and model-agnostic hyperparameters, diverging from prior work where hyperparameter sweeps carried out. It is
8

---

Published as a conference paper at ICLR 2025
important to note that hyperparameter tuning can significantly impact performance downstream tasks, as highlighted by. c.g.. Tori et al. (2024).
Training, Models are trained for up 500 epochs, with early stopping and learning rate decay based on a validation set. Additional details can be found in Appendix Results are reported as mean + standard error over 10 trials.
Results. Table shows test accuracies for the TUDataset experiments. Rewiring generally boosts performance for base graphs across models and datasets, and the impact of rewiring with our dataset- and model-agnostic choice of hyperparameters varies across datasets, with relational and topological models performance responding to rewiring similarly to graph models.
ENZYMES
IMDB-B
MUTAG
NCII
PROTEINS
Lift
Model
No Rew.
Best Rew.
No Rew:
Fo5R
No Rew.
Best Rew.
No Rew.
Best Rew.
No Rew.
Best Rew.
SOC
21.5
19.5
61.5
7000
1.0
0.7
62:2
65.0
1
GCN
32.2 2.0
30.7 1 L.5
19.1 &: 1.4
47.9 1.0
83.0 4
48.3 0.0.
49.1 0.8
111111 1.2
75.8
GIN
17.2 1.9
50.0 2.7.7
71.7 1.5
67.141 1.5
83.0 1.1
2..0
7721.00
0.5
70.6 1.4
72.2
0.08
None
ROUN
33.110 1.0
1. 1.3
08.011
12.5
135118
5321
05.4111
7192
75.6 1:2
69.6
81.5
-5.5++2.0
76.8
77.0
47.5
40.5
70.0
0::00
83.6 3.0
M5.5=
70.2=13
73:24
CIN
50.0 =:: 1.9
49.0 + 2.0
58.1 + 4.0
68.4 2.7
86.5
1.8
$7.0 2.4
51.4 2.5
88.2 2.0
70.7 1.0
71.0 +
CIN++
18.5
1.9
51.0
4: 1.5
86.6
56.0 3.9
85.0 à: 3.4
0010
00.8
d 3.8
64.8 3.1
07.9 1.9
71.4 1: 1.4
SGC
14.5 1.4
16.8
18.7 0
47.8 1.6
70.0 3.3
09.5 2.6
50.0 1.3
58.8
59.9 18
59.1
GCN
30.7
30.2
2.4
65.5
0.0.
89.6
75.0
GIN
44.0 1.7
48.5 + 2.2
69.1 + 1.2
70.8
83.0 2.8
78.8 0.7
78.2 + 0.6
68.7 1.4
72.8
Clique
RGCN
18.8 1.2
45.2
1.5
71.0 1.0
00.7 2 1.6
79.5 1: 1.7
$1.5
72.9 0.8
75.0 J: 0.9
12. 18
74.2 1.2
RGIN
5508 1.5
55.8 2.5
71.6 0.9
09:0 1.4
$0.0 2.3
2..0
0.00
79:5
7L3
7188 11.17
61.0.12.
76.8
15.1100
06.3
CIN
19.8 1.9
46577 +
62.6 + 2.4
68-1+ 1.6
85.5 2.8
86.5
61.8 2.3
72.6
0.8
70.7
70.3++0.88
CIN+
50.5 2.1
192.7 + 1:5
62.8 + 3.8
64.7 1.5
900. + 2/2
84.5++33
61.5
76.8
0.4
68.3 + 1.3
71.9 1.0
SGC
16.5+ 1.6
10.3 + 1.2
60.1+1.9
40.9 1.9
65.5 3.6
75.0+-6-7
1.2
51.4+ 0.4
44.8 2.3
40.3++3.6
GCN
34.8
32.0
46
48.0 1.2
+ 2.7
2.
4..3
72.2 0.6
72.7++1.2
GIN
46.74-2.4
47.0++
1.6
1.7
73
88.00
1.00+199
77.6
69.8+14
7-.1
Ring
RGUN
RGIN
35.2+1.1 1.7
45.3+ 1.3
45.7
49.2
1.5
11.
68.6
67.2 1.8
2031
1.0
87.0 2.9
83.5 2.7
87.5 2.4
210+2.1
78.4
+3.5+00.5
0.7
19.8 9 0.7
1335
+ 0.6
68.8 1.5
70.7 1.6
71.3
71:3 12
1.5
SIN
2.
48.0
2.0
50.6 1.9
00:9 2.1
2.5
80.0 0..8
10
1.77
CIN
17.5120
19.5
2.1
76.5
08.7
68.5
CIN+
1.7
46.3 1
L88
06.0 1.4
67.8 1.3
85.5 2.0
90.01:27
56.8 1 4.5
76.0
1.01....
0.6
68.1
12
70.1
12
Table 1: Test accuracy for TUDataset experiments. Each value is presented the mean + standard error across ten trials. The best-perforning result for each dataset is highlighted in gold, while the second-best is in silver. The results after rewiring are shown with green text if the mean increased and red text if the mean decreased.
5.2 SYNTHETIC BENCHMARK: RINGTRANSFER
We confirm the theoretical results from Section 3 using the RINGTRANSFER benchmark, graph feature transfer task designed to tease out the effect of long-range dependencies in message-pussing models using rings of growing size. We follow the experimental setup of Karhadkar al. (2023) Did Giovanni et al. 2023), and provide more details in Appendix [.2] We test the impact of neu- ral network hidden dimensions (Section 3.4), relational structure depth (Section
and relational structure local geometry (Sections 3.4 and 4 on task performance by varying the hidden dimen- sions, ring sizes, and rewiring iterations. The results, consistent with the theory, demonstrate that increasing network hidden dimensions improves performance up to a point, after which it declines, potentially due to overfitting. Larger ring sizes lead to performance deterioration, as the effects of long-range dependencies and bottlenecks start to take over. At the same time, rewiring improves performance by facilitating communication between distant nodes and mitigating oversquashing. As illustrated in Figure message passing on graphs and simplicial complexes demonstrate similar trends, consistent with our theoretical predictions.
5.3 ADDITIONAL EXPERIMENTS AND ANALYSES
We report additional analyses in Appendix D.I and Appendix D.2 There, we visualize the curva- ture of relational structures for dumbbell graphs and their corresponding clique complexes. We also reports statistically significant linear relationship between the weighted curvature of graphs and their lifted clique complexes. These interesting patterns merit further investigation. We also present the following additional experiments: (1) neighbors match for path of cliques and tree datasets in
9

---

Published as a conference paper at ICLR 2025
RSCKAIN
100
100
80
Accuracy (%6)
Accuracy (%)
80
Acourecy
60
40-
20
20
10
10
8
10
Hidden Dimension
Nodes
berations
(a) Hidden Dimensions
(b) Size
(c) Rewiring
Figure 2: Performance on RINGTRANSEER obtained by varying model hidden dimensions (left), ring size (middle), and number of rewiring iterations (right).
Appendix D.4 (2) graph regression for ZINC in Appendix D.5 (3) node classification for COR-
NELL, WISCONSIN, TEXAS, CORA, and CITESEER in Appendix D.6] (4) simplex pruning on the MUTAG dataset in Appendix D.8 and (5) full TUDataset results in Appendix F.
DISCUSSION AND CONCLUSIONS
This work addresses pressing questions about oversquashing in topological networks and higher- order generalizations of rewiring algorithms raised by the TDL community (Questions 2 and 9 of Papamarkou al., 2024). We introduce theoretical framework for unifying graph and topological message passing via relational structures, extending key graph-theoretic results on oversquashing and rewiring strategies to higher-order networks such as simplicial complexes via inffuence graphs that capture the aggregated message passing dynamical structure on relational structures. Our ap- proach applies broadly other gressage-passing schemes, including relational GNNs, high-order GNNs, and CW networks, providing a foundation for future theoretical and empirical research. Em- pirical results on real-world datasets show that simplicial networks respond to rewiring similarly to graph networks, and synthetic benchmarks further confirm our theoretical findings.
Certain aspects are worthy further investigation. particular, we compare message passing on graphs and their clique complexes through proxies (e.g., performance tasks), the significant differences in size and structure make direct empirical comparisons, c.g., of curvature, less the- oretically rigorous. While we observe statistically significant patterns when comparing weighted curvatures, further theoretical and empirical investigation is needed. Furthermore, the rewiring al- gorithms applied our relational rewiring heuristic were not originally designed with weighted directed influence graphs in mind. Potentially, further improvements could be obtained by imple- menting algorithms specifically tailored for rewiring weighted directed graphs
For future work, exploring global geometric properties of relational structures, studying oversmooth- ing, and empirically analyzing more relational Developing theoretical tools and tailored rewiring heuristics for weighted directed graphs will be crucial, as will be tools for direct comparisons of peessage-passing across different relational struc- tures. Furthermore, systematically and empirically assessing our framework's 's higher-order exten- sions of more state-of-the-arr (SoTA) graph rewiring solutions is essential. By unifying topological message passing into message passing relational structures and generalizing graph-based analysis to this setting, we hope that the present work can aid in both rigorous analysis and direct comparison between different higher-order message passing schemes.
schemes are promising directions.
Lastly, for practitioners, we recommend topological message passing as yet another relational learn- ing tool with relational rewiring preprocessing step.
Reproducibility Statement The code for replicating experiments is available at https: //github. com/ httph/aaann/nimmmaaaaaa -ovaaal-avvessusiiiggggg Experimental settings and implementation details are described in Section 5 and Appendices and
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
GM and have been supported by NSF CCF-2212520. GM also acknowledges support from NSF DMS-2145630, DFG SPP 2298 project 464109215, and BMBF in DAAD project 57616814.
REFERENCES
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical im- plications. In International Conference on Learning Representations, 2021. URL https:
//openzeview. wttp://wwwnee/ttmmaaaaa---------
Alessia Antelmi, Gennaro Cordasco, Mirko Polato, Vittorio Scarano, Carmine Spagnuolo, and Dingqi Yang. A survey on hypergraph representation learning. ACM Computing Surveys, 56
(1):1-38, 2023.
Hugo Attali, Davide Buscaldi, and Nathalie Pernelle. Delaunay graph: Addressing over-squashing and over-smoothing using delaunay triangulation. In Forty-first International Conference on Ma- chine Learning, 2024.
Pradeep Kr. Banerjee, Kedar Karhadkar, Yu Guang Wang, Uri Alon, and Guido Montúfar. Over- squashing in GNNs through the lens of information contraction and graph expansion. In 2022 58th Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp- 1-8, 2022. doi: 10.1 10//AAllerto49993.22222.99999999
Federico Barbero, Cristian Bodnar, Haitz. Sáez de Ocáriz Borde, and Pietro Lio. Sheaf attention networks, NeurIPS 2022 Workshop on Symmetry and Geometry Neural Representations, 2022.
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. for neural networks. In Advances in Neural Information Processing Systems, volume 30. Cur- Associates, Inc., 2017. URL URL http::///cccceeeeeeeeeeee neurips wwtp:cceepppppcpeeeeeeeeeeeee files/ paper/2017/ http://eee2222225522 httpa22222.011111113355533aaa3e.
nonemallyy-oomalized margin bounds
Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. Understanding oversquash- ing in GNNs through the lens of effective resistance. In Proceedings of the 40th Interna- tional Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Re- search, pp. 2528 2547. PMLR, 2023.
b aackk3.... h
Cristian Bodnar, Fabrizio Frasca, Nina Otter, Yu Guang Wang, Pietro Liò, Guido Montúfar, and Michael M. Bronstein. Weisfeiler and Lehman go cellular. CW networks. In Advances Neural Information Processing Systems, 2021a. URL https:://pperreviers net. forummiii...
UVPZCMVV.sSG
Cristian Bodnar, Fabrizio Frasca, Yuguang Wang. Nina Otter, Guido Montúfar, Pietro Lió, and Michael Bronstein. Weisfeiler and Lehman go topological: Message passing simplicial net- works. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. ht htttps://proceecinng
PMLR, 2021b. URL httpppeeee/.33///caaaaaa....a. http://ooaraa......mmm html
Cristian Bodnar, Francesco Di Giovanni, Benjamin Paul Chamberlain, Pietro Lio, and Michael M. Bronstein. Neural sheaf diffusion: A topological perspective on heterophily and oversmoothing in GNNs. In Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho (eds.), Ad- vances Neural Information Processing Systems, 2022. URL /tllittts////peeevieee .eet/ Forum? 2 BhoZ
Michael M. Bronstein, Joan Bruna, Taco Cohen, and Petar Veličković. Geometric deep leam- ing: Grids, groups, graphs, geodesics, and gauges, 2021. URL http:: htttps://aaratt. http:://////...//////// abs/ 21 04. 13478
11

---

Published as a conference paper at ICLR 2025
Benjamin Chamberlain, James Rowbottom, Davide Eynard, Francesco Di Giovanni, Xiaowen Dong, and Michael Bronstein. Beltrami flow and neural diffusion on graphs. In Advances in Neural Information Processing Systems, volume 34, pp. 1594-1609. Curran Associates, Inc., 2021. URL. httpp::://pppsoottt ngs neur www.sesnrrpppccooooooom ct/ -ir httpp/pprrraeasppppaereeeeepeeee patps//ppp//221111
file /tle://ccedd00002222667662221210 pttp:eeer00...rpppae..ee.
Zhengdao Chen, Soledad Villar, Lei Chen, and Joan Bruna. On the equivalence be- tween graph isomorphism testing and function approximation with GNNs. In Ad- vances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https://proceeseee neur.ns..........oeee........... wwtpccpppppppppeeeeeeee www.ffllepppaae ffllss/paper/2119) ELLe/1eee1Lcoo222223//4333333333
Paper papeerppff
George Dasoulas, Johannes F. Lutzeyer, and Michalis Vazirgiannis. Learning parametrised graph shift operators. In International Conference on Learning Representations, 2021. httpss::::
Francesco Di Giovanni, Lorenzo Giusti, Federico Barbero, Giulia Luise, Pietro Liō, and Michael M. Bronstein. On over-squashing in message passing neural networks: The impact of width, depth, and topology. In Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pp. 7865-7885. PMLR, 2023. URL https: 7/ prpoceedings... ml r. press v202
2iovanni2233 12. html
Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs.
AAAI 2021 Workshop on Deep Learning on Graphs: Methods and Applications (DLG-AAAI 202/), 2020. htt.httpss//axxi.orr////////
Stefania Ebli, Michaël Defferrard, and Gard Spreemann. Simplicial neural networks. In TDA & Beyond, 2020. URL
Marzieh Eidi and Jürgen Jost, Ollivier Ricci curvature directed hypergraphs. Scientific Reports, 10(1):12466, 2020. URL /ttpa//..//////ooooo///////13110
Yam Eitan, Yoav Gelberg, Guy Bar-Shalom, Fabrizio Frasca, Michael Bronstein, and Haggai Maron. Topological blind spots: Understanding and extending topological deep learning through the lens of expressivity. arXiv preprini urXiv:2408.0544 2024.
Bahare Fatemi, Perouz Taslakian, David Vazquez, and David Poole. Knowledge hypergraph embed- ding meets relational algebra. Journal of Machine Learning Research, 24(105): 2023.
Lukas Fesser and Melanie Weber. Mitigating over-smoothing and over-squashing using augmenta- tions of Forman-Rics curvature. In The Second Learning on Graphs Conference, 2023. URL httpp:://pperew//
net
Lukas Fesser and Melanie Weber. Mitigating over-smoothing and over-squashing using augmenta- 002123399.08883388 09384
tions of forman-ricel curvature, 2024.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. 2019.
arXiv preprint arXiv:
Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z. Alaya, Aurélie Boisbunon, Stanis- las Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, Léo Gautheron, Nathalie T.H. Gayraud, Hicham Janati, Alain Rakotomamonjy, Ievgen Redko, Antoine Rolet, Antony Schutz, Vivien Seguy, Danica J. Sutherland, Romain Tavenard, Alexander Tong, and Titouan Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78): 1-8, 2021. BRLhhtp::/ htttp:/jmlr jmlr org httpp/ppppsss////2 200/222202-5555 211./20045551110 html
Fernando Gama, Alejandro Ribeiro, and Joan Bruna. Stability of graph neural networks relative perturbations. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 9070-9074. IEEE, 2020.
Lorenzo Giusti. Awesome topoloical deep learning, 2024. URL htttps://gitii com/ wttp://ttttteeeeeeeeettooooooooo -deep- learning Accessed: Sep. 28, 2024.
12

---

Published as a conference paper at ICLR 2025
Lorenzo Giusti, Claudio Battiloro, Lucia Testa, Paolo Di Lorenzo, Stefania Sardellitti, and Sergio Barbarossa. Cell attention networks. In 2023 International Joint Conference on Neural Networks (LJCNN) pp. 1-8. IEEE, 2023.
Lorenzo Giusti, Teodora Reu, Francesco Ceccarelli, Cristian Bodnar, and Pietro Liò. Topological message passing for higher- order and long range interactions. In 2024 International Joint Con- ference on Newral Networks (JJCNN, pp. 1-8, 2024. doi: 10.1 111100/C/NNNN0999000000 2024. 10650343.
Christopher Wei Jin Goh, Cristian Bodnar, and Pietro Lio. Simplicial attention networks. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022. URL https: //openreviens ew. net./ fortm/ d=Sc ffw. RNWkpec
Aric Hagberg, Picter Swart, and Daniel A Schult. Exploring network structure, dynamics, and function using networkx. Technical report, Los Alamos National Laboratory (LANL), Los Alamos, NM (United States), 2008.
Mustafa Hajij, Kyle Istvan, and Ghada Zamzmi. Cell complex neural networks. In TDA & Beyond, 2020. URL
Mustafa Hajij. Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzmán-Sáeen and Karthikeyan Natesan Ramamurthy, Higher-order attention networks. arXiv preprint arXiv:2206.00060 2(3):4, 2022.
Mustafa Hajij. Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Juuzáán-Sáenn Karthikeyan Natesan Ramamurthy, Tolga Birdal, Tamal K. Dey, Soham Mukherjee, Shreyas N. Samaga, Neal Livesay, Robin Walters, Paul Rosen, and Michael T. Schaub. Topological deep http///avvv....////v// wttpaaaww...ooor//aaaaaaaaaae//e
learning: Going beyond graph data, 2023.
00606
Jakob Hansen and Robert Ghrist. Toward a spectral theory of cellular sheaves. Journal of Applied and Computational Topology, ((4):315-358, 2019.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchanl Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E. Oliphant. Ar- ray programming with NumPy. Nature, 58577825)357-362, September 2020. doi: 1038/ 941586-020-264922 URL
264-269-22
Wilfrid Hodges. Model theory. Cambridge University Press, 1993.
Keke Huang, Yu Guang Wang, Ming Li, and Pietro Lio. How universal polynomial bases enhance spectral graph neural networks: Heterophily, over-smoothing, and over-squashing. In Forty-first International Conference on Machine Learning, 2024a. URL
net/
Fooumm1d=22LH6Va177
Xingyue Huang, Miguel Romero Orth, Pablo Barceló, Michael M Bronstein, and ismail ilkan Cey- lan. Link prediction with relational hypergraphs. arXiv preprint 200::2200..0062,, 2024b.
J. D. Hunter. Matplotlib: A 2d graphics environment. Computing in Science & Engineering, 9(3): 90-95, 2007. doi: 10.1 109/MCSF..007.55.
Adarsh Jamadandi, Celia Madriaa,, and Rebekka Burkholz. Spectral graph pruning against over-squashing and over-smoothing. 2024.
04612
Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montúfar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In The Eleventh International Conference on Learning Representations, 2023. URL https:////.. http///pprreiiiiee htt.e///ee//eeeeeeeeeeeeeeeeeeee wft..t/eeooouumm3-3-fof.........
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https: //openreview wttt://orom..ds...t......
13

---

Published as a conference paper at ICLR 2025
Siu Kwan Lam, Antoine Pitrou, and Stanley Seibert. Numba: a flvmm-based python jit compiler. In Proceedings of the Second Workshop on the LLVM Compiler Infrastructure in HPC, LLVM 15, New York, NY, USA. 2015. Association for Computing Machinery. ISBN 9781450340052. doi: 2833166
10.1145/2833157, 18.14/22833152..33312.
htllhttps://dd wto. 1145/113311111
Hao Li, Chen Li, Jianfei Zhang, Yuanxin Ouyang, and Wenge Rong. Addressing over-squashing in gnns with graph rewiring and ordered neurons. In 2024 International Joinl Conference on Neural Networks (JCNN), pp. 1-8. IEEE, 2024.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018. URL BRRLhtts:://// /top::://do..oo /ttttp:://doi.og/11...o (0166099aaa8 www.i.l2111.....................
Richard Liaw, Eric Liang, Robert Nishihara, Philipp Moritz, Joseph E. Gonzalez, and lon Sto- ica. Tune: research platform for distributed model selection and training. arXiv preprint arXiv:1807.05118, 2018.
Yang Liu, Chuan Zhou, Shirui Pan, Jia Wu, Zhao Li, Hongyang Chen, and Peng Zhang. Curvdrop: A ricci curvature based approach prevent graph neural networks from wer-smoothing and over-squashing. In Proceedings of the ACM Web Conference 2023, pp. 221-230 2023.
Yu Liu, Quanming Yao, and Yong Li. Generalizing tensor decomposition for n-ary relational knowl- edge bases. In Proceedings of the web conference 2020. pp. 1104-1114, 2020.
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably powerful graph networks. In Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https::/
www.nnnuriii.e cc/paper.epppeeeeeeeeeeeee files/
Gonzalo Mateos, Santiago Segarra, Antonio G Marques, and Alejandro Ribeiro. Connecting the dots: Identifying network structure via graph signal processing. IEEE Signal Processing Maga- zine, 36(3):16 43, 2019.
Philipp Moritz, Robert Nishihara, Stephanie Wang, Alexey Tumanov, Richard Liaw, Eric Liang, Melih Elibol, Zongheng Yang, William Paul, Michael I Jordan, et Ray: A distributed frame- work for emerging {AI] applications. In 13th USENIX symposium on operating systems design and implementation (OSDI 18), pp. 561-577, 2018.
Christopher Morris, Martin Ritzert, Matthias Fey, William I. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and Leman go neural: Higher-order graph neural networks. In Proceedings the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609, 2019. CRLLhttps: /ow. ortp/0..10000..0...00 aaai.
330144602306
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Mar- ion Neumann. TUDataset: A collection benchmark datasets for learning with graphs In ICML 2020 Workshop Graph Representation Learning and Beyond (GRL+ 2020), 2020. URL
http://eprints.ccm www.issivviiee..... at 6469/
Florentin Münch. Ollivier curvature, betweenness centrality and average distance, 2022. URL
htttps://ariiii orgg abs 2209. 15564
V. Nanda. Computational algebraic topology lecture notes, 2021. Available online.
Khang Nguyen, Nong Minh Hieu, Vinh Duc Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squahhing using Ollivier-Ricci curvature. In Proceedings of the 40th International Conference Machine Learning, volume 202 of Pro- ceedings of Machine Learning Research, pp. 25956 25979. PMLR, 2023. URL https: ioproceedings.mrr.ppe httpeess//v2///gggenn3n.......
Maximilian Nickel, Kevin Murphy, Volker Tresp, and Evgeniy Gabrilovich. A review of relational machine learning for knowledge graphs. Proceedings of the IEEE, 104(1):1 11-113111333,,0 2015.
Hoang Nt and Takanori Machara. Revisiting graph neural networks: All we have is low-pass filters. 905. 9000/95000000000
arXiv preprint arXiv: /00iv/99050000 1905009550 2019. URI. wttpt:tppt/tttt htt.:htssss/.a....orro//o//////
14

---

Published as a conference paper at ICLR 2025
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. International Conference on Learning Representations, 2020. URL https:
The pandas panda developpent team. http:////w.......aaaaadddd////aa Pandas, February 2020. URLhttps:
3509134
Theodore Papamarkou, Tolga Birdal, Michael M. Bronstein, Gunnar E. Carlsson, Justin Curry, Yue Gao, Mustafa Hajij. Roland Kwitt, Pietro Lio, Paolo Di Lorenzo, Vasileios Maroulas, Nina Mi- olane, Farzana Nasrin, Karthikeyan Natesan Ramamurthy, Bastian Rieck, Simone Scardapane, Michael T Schaub, Petar Veličković, Bei Wang, Yusu Wang, Guowei Wei, and Ghada Zamzmi. Topological deep learning is the new frontier for relational learning. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine PMLR, 2024. URL
Position:
Learning Research, pp.
mir.
html
Mathilde Papillon, Mustafa Hajij, Audun Myers, Helen Jenne, Johan Mathe, Theodore Papamarkou, Aldo Guzmán-Sáenz, Neal Livesay, Tamal Dey. Abraham Rabinowitz, Aiden Brent, Alessandro Salatiello, Alexander Nikitin, Ali Zia, Claudio Battiloro, Dmitrii Gavrilev, German Magai, Gleb Bazhenov, Guillermo Bernardez, Indro Spinelli, Jens Agerberg, Kalyan Nadimpalli, Lev Tely- atninkov, Luca Scofano, Lucia Testa, Manuel Lecha, Maosheng Yang, Mohammed Hassanin, Odin Hoff Gardaa, Olga Zaghen, Paul Hausner, Paul Snopoff, Rubén Ballester, Sadrodin Barik- bin, Sergio Escalera, Simone Fiorellino, Henry K Kvinge, Karthikeyan Natesan Ramamurthy, Paul Rosen, Robin Walters, Shreyas N. Samaga, Soham Mukherjee. Sophia Sanborn, Tegan Emerson, Timothy Doster, Tolga Birdal, Abdelwahed Khamis, Simone Scardapane, Suraj Singh, Tatiana Malygina, Yixiao Yue, and Nina Miolane. ICML 2023 Topological Deep Learning Challenge: Design and results. In Proceedings of 2nd Annual Workshop on Topology, Algebra, and Geometry in Machine Learning (TAG-MLL), volume 221 of Proceedings of Machine Learning Research, pp-
3-8. PMLR, 2023a. URL html
mlr pttpspese////ppppll//ooooo
Mathilde Papillon, Sophia Sanborn, Mustafa Hajij, and Nina Miolane. Architectures of topolog- ical deep learning: A survey of message-passing topological neural networks. arXiv preprint arXiv:2304. 10031, 2023b.
Mathilde Papillon. Guillermo Bernárdez, Claudio Battiloro, and Nina Miolane. Topotune: A frame- work for generalized combinatorial complex neural networks. arXiv preprint arXiv:2410.06530, 2024.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high- performance deep learning library. Advances in neural information processing systems, 32, 2019.
Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, Thirion, O. Grisel, M. Blondel, P. Pretten- hofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830) 2011.
Hongbin Pei. Yu Li, Huiqi Deng, Jingxin Hai, Pinghui Wang, Jie Ma, Jing Tao, Yuheng Xiong, and Xiaohong Guan. Multi-track message passing: Tackling oversmoothing and oversquashing in graph learning via preventing heterophily mixing. In Forty-first International Conference on Machine Learning, 2024.
Chendi Qian, Andrei Manolache, Kareem Ahmed, Zhe Zeng, Guy Van den Broeck, Mathias Niepert, and Christopher Morris. Probabilistic task adaptivee graph rewiring. ICML 2023 Workshop on Disferentiable Almost Everything: Disserentiable Relaxations, Algorithms, Operators, and Simu- lators, 2023.
Joshua Robinson, Rishabh Ranjan, Weihua Hu, Kexin Huang, Jiaqi Han, Alejandro Dobles, Matthias Fey, Jan Eric Lenssen, Yiwen Yuan, Zecheng Zhang, al. Relational deep learning: Graph representation learning on relational databases. In NeurIPS 2024 Third Table Representation Learning Workshop, 2024.
15

---

Published as a conference paper at ICLR 2025
T. Konstantin Rusch, Michael M. Bronstein, and Siddhartha Mishra. A survey oversmoothing in graph neural networks. arXiv preprint arXiv:2033.109%0 2023. URL httpps://p......./ 10. 0054445550/aaa 2303. 10993
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling, Modeling relational data with graph convolutional networks. The semantic web: 15th international conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, proceedings 15, pp. 593-607. Springer, 2018.
Dazhong Shen, Chuan Qin, Qi Zhang, Hengshu Zhu, and Hui Xiong. Handling over-smoothing and over-squashing in graph convolution with maximization operation. IEEE Transactions on Neural Networks and Learning Systems, 2024a.
Xu Shen, Pietro Lio, Lintao Yang, Ru Yuan, Yuyang Zhang, and Chengbin Peng. Graph rewiring and preprocessing for graph neural networks based on effective resistance, IEEE Transactions on Knowledge and Data Engineering, 2024b.
Dai Shi, Andi Han, Lequan Lin, Yi Guo, and Junbin Gao. Exposition on over-squashing problem on GNNs: Current methods, benchmarks and challenges. arXiv preprint arXiv:2311.07073,00 2023. URL httpps:///oi..ooo 1tt.://./000...../////
10. 48550/ arvvv 2311.07073
Dai Shi, Andi Han, Lequan Lin, Yi Guo, Zhiyong Wang, and Junbin Gao. Design your own universe:
A thysics-informet agnostic method for enhancing graph neural networks. International Journal of Machine Learning and Cybernetics, pp. 1-16. 2024.
Stevan Stanovic, Benoit Gaüzère, and Luc Brun. Graph neural networks with maximal independent set-based pooling: Mitigating over-smoohing and over-squashin. Pattern Recognition Letters, 2024.
Julian Suk, Lorenzo Giusti, Tamir Hemo, Miguel Lopez, Konstantinos Barmpas, and Cristian Bod- nar. Surfing on the neural sheaf. In NeurlPS 2022 Workshop on Symmetry and Geometry Neural Representations, 2022. URL /ttpps://opereeiieeee net/ forum? 1x=1xxxxx222xx2x
Li Sun, Zhenhao Huang, Hua Wu, Junda Ye, Hao Peng, Zhengtao Yu, and S Yu Philip. Deepricci: Self-supervised graph structure- co-refinement for alleviating over-squashing. In 2023 IEEE International Conference on Data Mining (ICDM), pp. 558-567. IEEE, 2023.
The GUDHI Project. GUDHI User and Reference Manual. GUDHI Editorial Board, 3.1.1 edition, 2020. URL htttpttts///uuue
inria. fr/ fr/doo/3... 1.17
Jake Topping. Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Understanding over-squashing and bottlenecks on graphs via curvature. In Interna- lional Conference on Learning Representations, 2022. URL hnttpss:/<penreview: net/
Bronstein.
Eorum? 2imimmidd-Unm 7dmm7m//2222222 jRG2p-1
Floriano Tori, Vincent Holst, and Vincent Ginis. The effectiveness of curvature-based rewiring and the role of hyperparameters in gnns revisited. arXiv preprint arXiv:2407.0938/ 2024.
Shikhar Vashishth, Soumya Sanyal, Dasgupta S Nitin, and Partha Talukdar. Composition- based multi-relational graph convolutional networks. In International Conference Learning Repre- sentations, 2019.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Michael L. Waskom. seaborn: statistical data visualization. Journal of Open Source Software, (60):3021, 2021. doi: 10.21 10.21105/joss.00221 URL 03021
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Sim- plifying graph convolutional networks. In Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 6861-6871. PMLR, 2019. URL httlhhttss:///pooooe ngs. prw.spppsss...... v97 wall 9e. html
16

---

Published as a conference paper at ICLR 2025
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful graph neural networks? In International Conference on Learning Representations, 2019. URL https:
Naganand Yadati. Neural message passing for multi-relational ordered and recursive hypergraphs. Advances in Neural Information Processing Systems, 33:3275-3289, 2020.
17

---

Published as a conference paper at ICLR 2025
Appendix
Table of Contents
A Related Work
18
B Additional Remarks
21
Remarks for Section
21
B.2 Remarks for Section 3.4
21
C
Proofs
22
Proofs for Section
22
Prools for Section 3.2 and Appendix [..
................................
23
Proofs for Section
24
Proofs for Section 3.4 and Appendix B.2
25
D
Supplementary Analyses
27
Graph Lifting Example and Curvature
................................
27
D.2
Graph Lifting and Weighted Curvature
................................
28
D33
Graph Lifting and Edge Curvature Distribution
28
D.4
Synthetic Benchmark: NEIGHBORSMMTCH
28
D.5
Real World Benchmark: Graph Regression (Zinc)
................................
32
D.6
Real-Worlh Renchmark: Node Classification
................................
32
D.
Ablation Tests
32
D.8
Simplex Pruning
33
Additional Experimental Details
33
E.
Real World Benehmark: Graph Classification on TUDataset
33
B.2
Synthetic Benchmark: Ring Transfer
36
F
Implementation Details
36
Model Details
................................
36
F22
Hardware
................................
37
F3
Libraries
37
F4
Graph Litting
39
Layers
39
G
Higher-Order Graphs Relational Structures
44
H
Worked Example: Relations and Operators for a Path Graph
45
Computational Complexity
48
L.I
Clique Complex Size
48
1.2
Clique Lift Complexity
49
Running Times
50
A RELATED WORK
Topological Networks Topological deep learning (TDL) integrates algebraic topology with neu- ral networks to create message- message-passing schemes that are more expressive than graph neural net- works. An early contribution nar et al. (2021a), which extends the Weisfeiler-Lehmnn (WL) test from graphs to simplicial com- plexes. Simplicial neural networks (SNNs) built on SWL generalize graph isomorphism networks
the simplicial Weisfeiler-Lehman (SWL) test introduced by Bod-
18

---

Published as a conference paper at ICLR 2025
Xu et al. 2019), offering provably stronger expressiveness. CW networks (CWNss (Bodnar ct al. b) extend message passing to cell complexes, achieving greater power than the tradi- tional WL test and exceeding the 3-WL test. These hierarchical, geometrically- groouddd represen- tations enable effective handling of higher-order interactions. HHajj et al. (2020) proposed a general cassage-passing scheme for cell complexes, though it lacks formal analysis of expressiveness and complexity. In contrast, [Bodnar et al. (2022) and Suk et al.] (2022) introduced neural sheaf diffu- sion models, which learn sheaf structures over graphs, particularly excelling heterophilic graph tasks. Attention mechanisms have been integrated into topological message passing in works such as Goh et al. (2022) for simplicial complexes, [Barbero et al. (2022) for sheaves, and Giusti et al.) (2023) for cellular complexes. Additionally, Hajij et al. (2022) extends message-passing to combi- natorial complexes. Our work represents a first step toward extending the theory of oversquashing and oversmoothing, widely studied in graph neural networks, to these topological networks
(GIN)
We note that our relational structures approach generalizes a powerful perspective in which simpli- cial complexes and similar constructs are treated as augmented Hasse diagrams-2 a viewpoint that has shown both practical and theoretical advantages. Recent works have leveraged this perspective: Hajij et al. (2023) provided general description of topological message passing schemes, |Eitan ct al. (2024) explored the expressivity limits of topological message passing. and Papillon et al. (2024) introduced a framework for systematically transforming any graph neural network into topological analog. Our work aligns with and contributes to this growing body of research.
For detailed surveys of topological deep learning architectures, we refer to Papiilon et al. (023h) and Giusti (2024). We also refer the reader to the recent position paper by Papamarkou et al. (2024) on open problems TDL.
Oversquashing, Oversmoothing, and Graph Rewiring Oversquashing refers to the phe- nomenon where information from distant nodes is compressed into fixed-size vectors during mes- sage passing, limiting the ability of a model to capture long-range dependencies. In GNNs, this has been extensively studied, with works such those of [Alon & Yahav (2021), Topping et al.) (2022), and Di Giovanni et al. (2023) naming and relating the phenomenon to the geometric prop- erties of graphs. To address this issue, numerous techniques have been proposed, including spatial and curvature-baaie based rewiring methods such as SDRF (Topping et al.) (002)). BORF (Nguyen et al.) 2023). and AFRC (Fesser& & Weber (023). which modify the graph structure improve connectivity and alleviate oversquashing. Spectral rewiring approaches, such as FOSR (Karhadkar et al., 2023), optimize the graph spectral gap to enhance long-range message propagation, while implicit methods such as Graph Beltrami Diffusion (Chamberlai et al., 2021) and Graph Transformers (Dwivedi & Bresson 2020) allow information flow across a fully connected graph without explicitly modifying the topology.
Related to oversquashing, another significant challenge in GNNs is oversmoothing, where node features become indistinguishable they are excessively aggregated through layers of message passing. Li et al. (2018), Oono & Suzuki (2020), and Nt & Machara (2019) have identified and the- oretically analyzed oversmoothing, showing that it limits the effectiveness of deep GNNs. Gener- ally, there is trade-off between mitigating oversquashing and avoiding oversmoothing. and various rewiring techniques aim balance these competing objectives.
Following foundational work on understanding and mitigating oversquashing and oversmoothing in graph neural networks, the field has rapidly evolved with various innovative and sophisticated approaches in recent years. For example, [iu et al. (2023) introduced CurvDrop. a Ricci curvature- based, copology-award method address both failure modes of message passing, while (unn et al. (223) proposed DeepRicci, self-supervised Riemannian model designed to alleviate oversquash- ing. Qian et al. (023) developed a probabilistic framework leveraging differentiable k-subset sam- pling, and SSen et al. (2024a) introduced technique based on maximization operations in graph convolution. |Shen et al. (2024b) used effective resistance for graph rewiring and preprocessing. Li et al. (2024) combined graph rewiring with ordered neurons, while Stanovic et al. (2024) proposed maximal independent set-based pooling to mitigate both oversquashing and oversmoothing. Shi et al. (2024) presented physics-informed, agnostic method targeting both failure modes, and Pei jet al. (2024) addressed them through multi-track message passing. Attali et al. (2024) employed Delaunay triangulation of features, while Huang al. (2024a) proposed particular spectral filters
19

---

Published as a conference paper at ICLR 2025
to improve spectral GNNs. Collectively, these works demonstrate the breadth and depth of recent advancements, highlighting a vibrant and rapidly evolving research landscape.
However, the study of oversquashing and oversmoothing in topological message passing remains largely unexplored. While works such as those of Bodnar et al. (202Tb), Bodnar et al. (202Ia), and Giusti al. (2024) have alluded to the potential of topological message passing to capture group interactions and long-range dependencies, a theoretical analysis of oversquashing and oversmooth- ing in higher-order structures like simplicial or cellular complexes is, to the best of our knowledge, absent from the literature. Our work aims to fill this gap, providing a rigorous first step in study- ing oversquashing in topological message passing. Moreover, our framework for extending graph rewiring to relational rewiring (Section D). along with future innovations from the topological deep learning community, promises a wealth of topological and relational rewiring techniques for further assessment and refinement.
For more exhaustive expositions on oversquashing and oversmoothing, we refer the reader to the excellent recent surveys of (Shi et al. (2023) and Rusch et al. (2023).
Relational Learning Relational graph neural networks (R-GNNs) extend traditional GNNs to handle multi-relations data, particularly in the context of knowledge graphs, where nodes represent entities and edges capture diverse types of relationships between them. Knowledge graphs, such as those used in knowledge representation and reasoning tasks (Nickel et al. (2015), are inherently multi-relational and benefit significantly from RGNNs, which model the varying nature of relations explicitly. The relational graph convolutional network (R-GCN) (Schlichtkrull et al. 2018) is a foun- dational approach that assigns distinct transformations to each relation type, allowing for efficient representation learning on multi-relational graphs. Extensions such Relational Graph Attention Networks (RGAT) (Veličković et al.) 2018) incorporate attention mechanisms, enabling the model focus on the most important relations during message passing, Additionally, Composition Graph Convolutional Networks (CompGCN) (Vashishth et al. 2019) apply compositional operators to better capture interactions in knowledge graphs.
Recent works in relational learning have introduced various extensions for modeling multi-relational and higher-order interactions. Hypergraph-band based approaches, such as Fatemi et al. (2023) and Huang et al. (2024b), unify relational reasoning with hypergraph structures, enabling the modeling of higher-order relationships. geessage-passing frameworks like the one proposed by Vadati (2020) extend traditional GNN paradigms to ordered and recursive hypergraphs. Additionally, tensor de- composition methods such as GETD (Liu et al., 2020) represent hypergraphs as high-dimensional tensors, allowing efficient encoding of hyper-relational data. We refer the reader to the excellent survey by Antelmi et al. 2023) for a comprehensive overview of relational hypergraphs and their representation learning techniques. [Robinson et al.) (2024) recently extended relational learning to relational databases consisting of data laid out across multiple tables. Lastly, topological deep learn- ing, which is one focus of this work, is a new frontier in relational learning (Papamarkou et al., 2024).
Our work unifies relational graph neural networks and topological neural networks by viewing com- plexes as relational structures, bridging the gap between the two fields.
Graph Lifting Graph lifting transforms graph into a higher-dimensional structure to enable more expressive message-passing schemes. For example, higher-order graph neural networks (k-GNNs) (Morris al., 2019) lift graphs by representing k-node subgraphs as entities, capturing more com- plex relationships between nodes. Similarly, Chen et al. (2019) and Maron et al. (2019) proposed lifting graphs to higher-order structures to improve graph isomorphism testing. topological mes- sage passing, graphs are lifted into structures like clique complexes to capture interactions beyond pairwise relationships. Recently, this topic has gained increased attention, as highlighted by the ICML Topological Deep Learning Challenge 2024 (Papillon et al. 2023a), which emphasized the development of topological lifting techniques across various data structures, including graphs, hy- pergraphs, and simplicial complexes. Among these, high-order graphs, simplicial complexes, and cellular complexes fit naturally within the relational structure framework and can be analyzed uni- formly through this lens.
20

---

Published as a conference paper at ICLR 2025
B ADDITIONAL REMARKS
B. REMARKS FOR SECTION 3.2
Remark B.1 (Ollivier-Ricci Curvature for Weighted Directed Graphs). We recall the definition of Ollivier-Rice curvature (ORC) for weighted directed graphs from Eidi & Jost (2020). Consider weighted directed graph (S, &, w), where S is the set of entities (nodes), & is the set of directed edges, and w & + R20 assigns non-negative weights to edges. We abuse notation, and for any For each entity a E S,
two entities E. E without an edge (E ( 71) E E, we write wg-n denote the weighted out-degree and weighted in in-reer as in Definition
3.3 by:
out Wo
Σ
w
Σ
W1--00-
(a (m-
(E-O)EE
For a directed edge (a + 7) E & with non-zero weight wa-tr measures:
> O, we define the probability
M4 1e (E) = W
1o (5) = We-aa
EES.
wout"
wel
The Ollivier- Ricci curvature of edge (or r) with non-zero weight Wo->r is then defined as:
(o,T)==1 W (1 p
Wo-rr
where W (ptr, prut) is the (directed) Wasserstein distance between the measures μ and pem defined by:
W (ua 14 (out)
inf TEIT (HEB (IQUE))
Σ =E,,
E-NES
where TT in (Q2)) is the set of all joint probability measures on S x S with marginals pe and po out and d(E, 1) is the distance from & (incoming neighbor a) to n (outgoing neighbor of T) in the graph 9 (the shortest directed path distance based on edge weights).
Remark B.2. Assume that the edge (a 10-7% T) & exists and has non-zero weight Wr-st 0 in the influence graph G(S, B). Then, the sensitivity bound for information flow from to a from I Lemma 3.2 can be related to the Ollivier-Ricci curvature k(a,T) () of the edge (a - T) as follows:
0h
S (II
(1- 11-Wo-rr (1- (1-
0h.0) (0)
-- Imax
where S is the maximum weighted 3-step path from incoming neighbors of to oulgoing neigh- bors of This result indicates that lower Ollivier-Ricci curvature (smaller k(a,T)) leads to reduced sensitivity, thereby contributing to oversquashing, The connection leverages the existence of the re- versed edge (a + 7) addition to the edge (T - σ) over which information flows, which is not guaranteed to be the case in generic relational message passing scheme, but is the case for undirected graphs where k(a,T) k(T,o). This result aligns with Theorem 4.5 from Nguyen et al. (2023) but without requiring their assumption of linearity in the message and update functions. An- alyzing oversquashing for connections beyond 2-steps requires stronger assumptions, such as the influence graph G(S, B) being strongly connected. These assumptions present obstructions to ana- lyzing oversquashing in general relational structures with Ollivier-Rica curvature.
We provide the proof in Appendix
C.2
B.2 REMARKS FOR SECTION
Remark B.3 (Lipschitz Constants for MLP Message and Update Functions). Consider the following message and update functions at layer t:
Message function:
h
h
(00 (n.) h
(0) hg:; .) = -w(")
f
(
E
21

---

Published as a conference paper at ICLR 2025
where w is weight matrix of appropriate dimensions, and [ denotes column-wise concatena- tion.
Update function:
m
0,1
(ml)
(2) m
=f ((()
0,k
where f and g are the wosponent-wise applications of non-linear functions f and g with bounded derivatives Cj and Cg. respectively. Lee, f.g. R + R, and ['(x) S Cj and lg (x) S C for all
Assume that the entries of all weight matrices w!lh) and W(() are bounded in absolute value by constant Cu O. Then, the Lipschitz constants { and a satisfy:
8 S Cupiss
and
a < C. Cy
(t) where Pi, is the dimension of the message vector m m and Pet1 is the output dimension of the update function Φ:.
We provide the proof in Appendix C.4
C PROOFS
C.1 PROOFS FOR SECTION 3.1
Proof of Lemma 3.2
First, we compute the Jacobian of Equation 3
Oh
1++1)
&
d
0m (x)
Oh
ôm!
Dh (0)
(cb(s)
Oub (5)
Th.
(s)
Jublo (s)
oh
0m, (+)
Oh
Oh
Oh
(0)
SESTi-1
By the submultiplicative and additive properties of the induced 1 1-norm (maximum absolute column sum) and the boundedness of the Jacobians of the functions (x)) and xb?" (Assumption
get:
0h(+t)
(++1)
acb
(x)
@h.C)
(o)
Oh
Σ
A
+
Th (0)
dm!
Oh!
0h
Ih (0)
Th
Oh(s)
0h
5 (s)
((0)
A r.
+
Ih
0h
i=1
0h! (*)
ih (4)
5 (1)gg()
R. A
+ Σ
o.
Oh.
Jh. (0)
--
j=1
ih
I ((())
A E
Oh
(0)
Ōh.
1=1 -
1=1
Here, used that the entries of A R. nonnegative, and Σ EeEsm A. S7
22

---

Published as a conference paper at ICLR 2025
We now prove the lemma using induction the layer t. For the base case t = 1, we get
Th (
Oh (0)
Th (0)
I (0) 3(0) (()))
R 0
Öh, (0)
Oh (0)
EES
j=1
k
Re 1
= (0) 3(0)
I T +
R:
1=1
EES
j=1
= ())000)))
I D.T
R
O,T
==1
a 3(0)
+I+ A R
0,5
= (0) (
where we used that A For the induction step, assume the bound holds for L. We now compute:
Σド=ī Eges A R: 1555:-.
This proves the base case.
Oh (++
Oh (
Oh
(8) 5
S g00
R E
0h (0)
7
ah
(0)
Th
(0)
1=1
$E8"1-1
j=l
R4-1
II 1=
(6) g(0)
Y (B') 0,T
+ Σ
R
B
5,17
1=1 $ES"
==1
II E=
(0) g(0
(TIB') oiT
+
Σ
A
R
B'
im
0,7
II (0) g(0)
II+ Σ
A R
B'
6=
1=1
O,T
(1) 3(0)
(B++)
O,T
To see this, note that:
(( Σ
k
A
R
B'
A Rg
(B'),.
o. U.5
a,t
i=1 VES
k
Σ
All Ci..in I.tRks...nnn 2 (B').. U.
i=1
j=1
n2
A R
B'
0
EgsT
EES"C-1
This completes the proof.
C.2 PROOFS FOR SECTION 3.2 AND APPENDIX B.1
3.4 In the influence graph GSS, B), the edge weights correspond to the entries of B, that is, W--v0 B Therefore, the (a, r) entry of B is
Proof of Proposition
(B2 )B²),,+=
> B B B
" Wr- WT.
EES
EES
23

---

Published as a conference paper at ICLR 2025
From Lemma 3.2 with
2, have
0h
[I F=
(B²) (B*),r-
0h
(0)
wr-
f=
Rewriting the curvature formula to solve for wT, and since wF 0, we get
(EFCg(TT,)) + w + w 2
WT
3 (EFCg(T, + w out + w - 4).
Substituting back, we obtain the desired inequality. This completes the proof.
Proof of Remark B.2 Consider the influence graph G(S B) (S,E, w) derived from the matrix
B, where the edge weights correspond to the entries B: Wig-nn = By.g- Assume that the reversed
edge (o 7) exists with weight W O. From Lemma 3.2 with 2, have:
[i ==
Ii (1 0=
(00
(B*)..
Σ EES
Wg-+o W =
II t=
(0 (a00(0)) g(e)
wrs
ah
where Wy = Eg W Wg-+0-
We construct a transference plan to transport mass from p to nour. We do not move
but
wont u
move the rest the mass with a cost at most w from the incoming neighbors to the outgoing neighbors of 7, and we get:
W (1or poput) (1
WT Wit wour
3 max
The Ollivier-Rei Rieicer-Ricciiic curvature of the edge (a + T) is:
W (no), ) Wo-sr
-a,T)=1-
Substituting and rearranging, we obtain:
(1 (1- Wr W k(o, k(o.7)))
WT S w
Wi max
We thus get:
0h (2)
< II
(0) g(t) (03)
|I
(000) 1=
wout (1
k(0, Wo-rr (1 (1-1(o, ((),))))
Oh! (0)
wr
u wmax
==
This completes the proof.
C.3
PROOFS FOR SECTION 3.3
Proof of Theorem 3.5 We start with the bound from Lemma 3.2 and expand the right-hand side
using the binomial theorem:
oh (r+m)
r+m-1
II
(g)()
(>I A m+m
Oh. (0)
++
(0) (())))
g(t)
r + m
" --m- (A:)
f=0
24

---

Published as a conference paper at ICLR 2025
Since the combinatorial distance from in the graph ((S, A) is r, the first 1 terms of the sum vanish:
Öh
(++))
r+m
II t=0
(0 gle)
Σ
r + m
) y - (A:
Th;
i
Using A S Wil(o,T)MM S mm (a, T)M and letting q =
@h(rtm) (r)m) Th
S
p+
II t=0
a 3())
M wir (0,
Σ
m
r +
7 7 -9.
0h (
r
9=0
We can bound (r+g) as follows:
r m
(r + mr 1 m. ... (1 + m)
m
(r + m)(r
1 mm)
(1 m) mm)
r+
+ + q) 1 g) ... (..(1 + q)
9
r!
1+ m
(1+
1
m
m
1 +
m
(1 + m
m
q
Substituting this bound, we get:
Ohg
(r+m)
II t=0
a (0)())
M ('rrt
(1+ m
(1 + m) m
m
7th M
Th
+
9=0
n- II E=
r-
(1) g(t) ()((()))
M (ow+ml(
1+ m +1
m
(1 + m)"(("""" + M)"
10 300)
(1+m) m)²
(1 +
(7 + Mi) wm+m(o,T) 2m +
II 1=
(11
m
M
m +
Using 1 + m+1
< 2, M < k. and 7 s k:
Oh (r+m)
-+=--
<
II t=r
wi (2k(1 + m) (0,
I 3(0)) 1=0
(2M1)
Oh (0)
Define C = (Ommx 3max)
)m (2k(1 + m)) n This depends only Ommax Piaxo ki and m.
Finally, we can write:
Oh (r+m)
< Owrtmla ( (S, Bmaxx) (
(15)
Öh (0)
This completes the proof.
C.4 PROOFS FOR SECTION 3.4 AND APPENDIX B.2
Proof of Remark B.3 We derive the bounds for (( and (1) separately.
Derivation of a(:);
The message function is linear:
(h.0)
h .....
( = w('H
(t)
25

---

Published as a conference paper at ICLR 2025
he hgg
where H ag
is the concatenated feature vector.
We need to compute the Lipschitz constant 8 of the message function 1/! with respect to each neighbor's feature vector b
(4)
The Jacobian of v. (t) with respect to hg is:
1 (1) W
(+) 45)
ahg (8)
where w (z),z denotes the columns of W corresponding
(6)
Since the entries of W are bounded by Cw. and h (1) with entries bounded by C..
E RR,, the matrix
ag ob de is of size Pt, Pt
Using the induced matrix 1-norm:
Jabl (2) Th
Pict
@ub!!) (t)
max ISiSPt
(9)
an
k=
(os!0 oh
Since each entry
S Cuu the sum over is bounded by CuPi,. Therefore,
k.1
S OwPi.
Th
Thus, the Lipschitz constant 8(()) satisfies:
8(0) < CuPi.
Derivation of (1)
The update function is given by:
((())
m
(0)
m
m,.k)
(8)
(WW)M.).
g
m sr,1
where M
g m o.k
We need to compute the Lipschitz constant (9) of the update function (()) with respect to each input message m (!)
0.
First, compute the Jacobian of (t)) with respect to m
(t)
(
(t)
aM (
0m
(1)
aM!!)
dm!!)
(2)
0.
26

---

Published as a conference paper at ICLR 2025
aM 0m (0) 5,
Compute
0M (0)
diag gg mm
dm
(8)
where the non-zero block diag (g' (m
is position i.
Compute (e UM
O5) UM
= diag (5' (W!) w
Therefore,
(t)())
diag (I' (W(MM.)) w(0. 2.) diag (g' (m
0m (1)
(8) where (.):)) 2,) denotes the columns of W(() corresponding to o.
The matrix as(*) is of size Pe+1 Pi,t- im!!
Since 15'(z) < Cy. (x)) & Cg. and ((Wi))&al S Cw. the entries of ag Cw
are bounded by
8m To
0,
Using the induced matrix I-norm:
OΦ (1)
Pel1 Σ
max 1S1SPt,
dm 0,
(t)
dm 0
(4)
l=
k.
Each column sums over up to P++1 entries, each bounded by C. Therefore,
(e)
S CC
8m 0,
Thus, the Lipschitz constant (t) satisfies:
a1 Coppe
D SUPPLEMENTARY ANALYSES
D.1 GRAPH LIFTING EXAMPLE AND CURVATURE
As shown in Section D.3 the edge curvature distribution is non-trivially impacted by the graph lifting procedure. We explore this more in this section.
One possible explanation for the general positive distribution shift is the widening of bottleneck regions as well as the addition of many nodes and edges in densely connected regions. We observe this gualitatively in Figure 3 We can see that the narrow path is widened into two nodes instead of one. We also see that the clique regions gain lot more nodes and edges than the path. The Ollivier-Rieei curvature becomes much more red, while the balanced Forman curvature and
27

---

where be denotes betwenness centrality and curv denotes the Ollivier-Rice curvature. This measure, originally in introduced by Münch (2022), places more weight on bottleneck edges which gives a weighted average of the curvature in the graph. This measure has the added benefit that it captures Published as a conference paper at ICLR 2025
augmented Forman curvature maintain higher number of small, negatively curved edges. This example is consistent with the observations from Figure
In the augmented Forman eurvature plot, negative. While this edge may not propagate information very well due to its negative curvature, there now many edges for information to flow around this edge. This provides some qualitative evidence that incorporating global structure into analysis of graph lifting could present an important future direction.
that the curvature for edge DI becomes more
D.2 GRAPH LIFTING AND WEIGHTED CURVATURE
The addition of many nodes and edges, well as the shift in the curvature distribution, makes direct comparisons between graphs and their corresponding lifts more challenging. While this widened bottleneck may alleviate oversquashing, measures like algebraic connectivity may not measure this effect since widened bottlenecks are counteracted by the addition of many nodes. Similarly, aver- age curvature could be biased by the addition of many positively curved edges located in densely connected regions. We instead propose the betweenness weighted curvature
WC
Σ bo(e) curv(e), eEB(G)
(16)
both local information propagation through curvature as well as global information propagation through betweenness centrality. To account for the influence of more positively weighted edges, also consider the negative betweenness weighted curvature
nwc
Σ eEE(G)
be(e) curv(e)
(17)
where X is the indicator function.
In Figure we create a scatter plot of the weighted curvature of a graph and its corresponding clique complex: (wc(G), wc(C)). We can see that the weighted curvature generally becomes less negative after complex construction for Ollivier-Ricci and balanced Forman curvature, which may suggest that oversquashing is alleviated. However, the augmented Forman curvature makes the weighted curvature more negative for all graphs in the MUTAG dataset. This is consistent with F which produced a small number of negatively curved edges for augmented Forman curvature. Interestingly, there is a strong linear correlation in each of the scatter plots. Further study is required to understand this trend.
D.3 GRAPH LIFTING AND EDGE CURVATURE DISTRIBUTION
Understanding the impact information propagation of lifting graph to a clique complex is cru- cial. Graph lifting often adds numerous edges and nodes, complicating theoretical analysis, as the structural differences between the relational structures corresponding plex can be significant. As a first step, we analyze the edge curvature distribution to gain empirical insight into the clique graph lift. Figure 5 shows the kernel density estimate (KDE) of edge cur- vature on the MUTAG dataset. Ollivier-Rice Ricci curvature (Nguyen et al.) (2023) increases uniformly, while balanced Forman curvature (Topping et 2022) generally increases with some edges becom- ing slightly more negative. A more pronounced shift is observed with augmented Forman curvature (Fesser & Weber 2023). but the overall effect on information propagation remains unclear, as global graph structure is not captured in this analysis.
graph and its clique com-
D.4 SYNTHETIC BENCHMARK: NEIGHBORSMATCH
The neighbors match experiment is a graph transfer task introduced by Alon & Yahav 202 to test oversquashing in GNNs. We build on the inplementation of Karbadkar et al. (2023) which adapts this benchmark to test rewiring. Each graph in the dataset is a path of cliques as shown in Figure 6 Each of the green nodes is assigned distinct random label which is represented by
28

---

Published as a conference paper at ICLR 2025
Graph
Camplex
14
04
-0.4
(a) ORC
Complex
122
100
075
870
Garaftue
8.95
(b) BFC
Graph
Complex
(c) AFC
Figure 3: Long dumbbell graph before and after lifting its clique complex. Edges are colored based on their curvature: Ollivier Ricci curvature (top), balanced Forman curvature (middle), and augmented Forman curvature (bottom). Note that this uses Boundary, Co- Co-boundary, Lower, and Upper relations. These are presented as edges for visual clarity.
29

---

Published as a conference paper at ICLR 2025
Data
y
Data
y=x
0.49x + 0.54
R² - 0.96
y= 0.43x 0.05
R²= 0.93
0
-055
-1-
Complex
Complex
-1.0
-2
-1.5
2.0
-4
-3
-2
-2.0
-1.5
-1.0
Graph
Graph
(a) ORC WC
(b) ORC NWC
Data
y-x
Data
y-x
y 0.85X + 0.11
R² 0.86
y- 0.78x 0.22
0.84
Complex
-2
Complex
-1.5
-2.0
-4
-3
-2.0
-1.5
-1.0
Graph
Graph
BFC WC
(d) BFC NWC
Data
y=x
y=x
y=
0.35
R²
1.54x
0.76
R 0.94
-2
-5
-4
Complex
-10
Complex
-6
-15
-8
-20
-12
-10
-8
-6
-6
Graph
Graph
(c) AFC WC
(f) AFC NWC
Figure 4: Weighted curvature scatter plots for MUTAG: Ollivier Ricci eurvature (top), balanced For- man curvature (middle), and augmented Forman curvature (bottom); betweeness weighted curvature (left) and negative betweenness weighted curvature (right).
Lift None Cloue
Lift
3.0
None
2.5
Clique
1.5
0.4
1.0
0.5
0.2
0.0
-1.0
-0.5
0.0
0.5
0.0
-1.0
-0.5
0.0
0.5
1.0
-7.5
-5.0
-2.5
0.0
2.5
(a) ORC
(b) BFC
(c) AFC
Figure 5: Edge curvature distribution across all graphs in the MUTAG dataset: Ollivier-Ried curva- ture (left), Balanced Forman curvature (middle), and Augmented Forman curvature (right).
30

---

Published as a conference paper at ICLR 2025
Figure NeighborsMatch Graph with 3 cliques of 5 nodes.
one-hot encoding. The root node, colored red, is also assigned random label which encoded using one-hot encoding. The goal is for the neural network learn which green node has the same one-hot encoding as the root node based solely on the output of the neural network at the root node.
In this experiment, we choose the number of nodes in each clique to be to avoid excessively large clique complexes when performing graph lifting. Note that we see similar trends as in the Ring Transfer experiment. However, this creates much larger clique complex which may present greater challenge for rewiring methods. We can see in Figure 7 that the Clique and Ring lifts require more rewiring iterations achieve the same performance as their graph counterparts. This is likely related to the lifts having many more nodes and edges than the original graph. The original graph has 15 nodes and 32 edges, whereas the clique lift has 77 nodes and 764 edges and the ring lift has 77 nodes and 854 edges.
100
90
80
Accurscy (%)
70
60
50
None
30
Clicue
20
50
100
150
200
250
Figure 7: Neighbors Match Rewiring experiment.
We also benchmark trees and trees with cycles attached to the leaves on the NeighborsMatch bench- mark (see Figure M. We note that a tree as an acyelic connected graph has Betti numbers bn (number of connected components) and b, 0 (number of independent loops cycles). On the other hand, a tree with n attached cycles has Betti numbers bo = and 6, = n. As such, the two structures are topologically very distinct when considered as I-simplicial complexes: the tree is con- tractible and has a trivial fundamental group, while the tree with attached cycles is not contractible and has non-trivial fundamental group corresponding to a free group with n generators. However, their relational message passing structures are quite similar, and they demonstrate almost identical prototypical oversquashing trends (see Figure 9)
31

---

Published as a conference paper at ICLR 2025
Tree with no attached cycles
(h) Tree with attached cycles
Figure 8: Tree without and with attached cycles have very distinct topologies.
100
Kone
Clague Line
Clique Cycle
Ring Line
Ring Cyde
60
Figure 9: Neighbors Match Rewiring experiment on trees and trees with cycles, with increasing tree depths. "None", "Clique", and "Ring" indicate the graph lifting applied. "Line" and "Cycle" indicate whether lines or cycles are attached to the leaves.
D.5 REAL-WOO WORLD BENCHMARK: GRAPH REGRESSION (ZINC)
In this section test methods the ZINC dataset. Due to increased computational demands, we do not perform hyperparameter sweep for this experiment and instead use the hyperparameters from the TUDataset experiments. We also test this the ring lifting procedure. The ring lift consists of adding cycles in the graph as 2-cells the complex as in Bodnar et al. (2021a). In this work, restrict the rings have size at most 7. Structures like carbon rings are important in molecule datasets and prediction tasks can benefit from encoding larger rings in the lifting procedure. The results are presented in Table 2 where we see clear improvement from the Ring lift across all models and rewirings tested for the ZINC dataset.
D.6 REAL-WORLD BENCHMARK: NODE CLASSIFICATION
In this section, we test the lifting and rewiring methods on node classification tasks. The results
of this experiment are shown in Table 3 The rewirings considered included FoSR and the pruning
algorithm introduced in Appendix [D8 The best results for each dataset and model are highlighted in gold. Notably, GIN and CIN++ benefited from lifting on all datasets tested.
D.7 ABLATION TESTS
We perform ablation studies evaluate the effect of increasing the number of layers and rewiring iterations, as well as the effect increasing the hidden dimensions and rewiring iterations, on the performance of CIN++ the graph classification MUTAG dataset with FoSR rewiring. The results
32

---

Published as a conference paper at ICLR 2025
GIN
R-GIN
SIN
CIN++
Complex
Rewiring
None
0.405 + 0.001
0.368
0.003
0.370 + 0.003
0.339 + 0.005
None
FoSR
1.056 + 0.010
1.485 + 1.045
0.377 = 0.005
0.374 + 0.008
None FoSR
0.409 + 0.006
0.326 + 0.003
0.331 = 0.004
0.320 + 0.006
Clique
0.844 + 0.011
0.420
0.002
0.369 = 0.003
0.379 0.008
None
0.332 + 0.006
0.215
0.003
0.223 = 0.004
0.214 0.003
Ring
FoSR
0.641 + 0.011
0.232 0.002
0.212 = 0.003
0.211 - 0.002
Table 2: ZINC (MAE). Lower values are better.
are presented in Tables 4 and S This analysis complements the experiments in Section 5.2 by testing real world data. We note that the results of the ablation studies for the MUTAG dataset do not show clear pattern across all rewiring iterations. However, we broadly see that rewiring too much tends to hurt performance they begin oversmooth information. We also generally see that increasing the hidden dimension tends to improve performance. Due to time constraints and limited compute, we could only test one dataset and perform 10 trials for each set of hyperparamters. With more trials, the standard сπтоr will decrease and make the patterns more clear. Nguyen et al. (2023) and Fesserr & Weber (2024) performed similar ablations and considered 100 trials for each set of hyperparameters. As in the experiments from Section 5 and the results reported in Rusch al. (2023) and Nguyen al. (2023). we expect that increasing the hidden dimension will improve classification accuracy. Similarly, incrasiig layers will initially improve performance until the model becomes too deep and experiences oversmoothing.
D.8 SIMPLEX PRUNING
In this section we analyze the impact of pruning edges in the influence graph. For the pruning algo- rithm, we consider removing the edge with the highest balanced Forman curvature. More precisely, first convert the simplex into the influence graph and collapse multi-edges. Then compute the balanced Forman curvature of each edge in the graph. Finally, we remove the edge with the highest curvature. This process is repeated 40 times. When removing edge with higher arity e = (a, 7, 6), the entire higher-order edge removed from the simplex. When an edge (a,7) with higher multiplicity is selected, all instances of that edge are removed from the graph.
The results of this experiment are shown Table 6 In eight out of twelve experiments, the per- formance improves with some amount of pruning- Notably, GIN and CIN++ attain their highest performance with 40 pruning iterations. This suggests that rewiring algorithms that implement edge pruning and edge addition could be the most promising candidates for simplicial rewiring algo- rithms. This is in part due to the addition of many nodes and edges in the graph lifting procedure.
E ADDITIONAL EXPERIMENTAL DETAILS
For all experiments, we split the dataset randomly using 80% for training. 10% for validation, and 10% for testing. For classificiation, we use the cross entropy loss. Each experiment run with early stopping using the validation set. Also, if there is improvement for 10 iterations, the learning rate decreased. For all rewiring methods, we only consider adding edges and no edge removal. Each rewiring method is run for 40 iterations.
E. WORLD BENCHMARK: GRAPH CLASSIFICATION ON TUDATASET
To train and evaluate these method on real world data, we use the TUDataset (Morris et al. 2020). These graph classification tasks commonly used to benchmark message passing neural networks. We have included summary statistics for MUTAG, NCII, ENZYMES, PROTEINS, and IMDB-
BINARY in Table
33

---

Published as a conference paper at ICLR 2025
(a) GIN
CORNELL
WISCONSIN
Complex
Rewiring
41.6
37.9
2.5
82.4 0.7
None
Prune
45.8
4.0
55.3 4.9
48.1 3.9
70.6 0.4
84.4 0.8"
33.7
60.0
82.7
FoSR
40.5 3.5
64.7 5.3
36.5
2.6
68.6 0.8
84.4 0.6
Clique
Prune
36.8 2.6
31.
47.3 3.7
72.0
0.8
82.4 0.5"
None
3.6
58.9 2.3
55.8 2.2
69.0 = 0.8
83.2 0.6
FoSR
2.1
61.1 +: 3.3
$5.0 + 3.3
Ring
Prune
47.4
65.3
3.2"
None
46.3 3.1
38.9 3.3
34.6 + 3.0
(b) RGIN
CORNELL
TEXAS
WISCONSIN
CITESBER
CORA
Complex
Rewiring
FoSR
54.2
3.3
71.2
73.2
81.9 0.8
None
Prune
52.6 3.5
65.3 4 3.2
2.1
7..2
85.6 0.7'
None
39.5 5.0
67.9 3.2
69.2
72.2 1.0
86.4 0.7
FoSR
51.1
62.1 3.7
68.5
73.4
85.7 0.6
Clique
Prune
47.9 2.3
64.2
60.4 2.0
73.3
85.9 0.6"
None
30.5
3.1
68.5
72.1 101100 0.9
86.6 0.6
FoSR
37.4
69.6
66.5 2.4
Ring
Prune
4.1
4.7
74.6 2 2.5"
2.7
(c) SIN
CORNELL
TEXAS
WISCONSIN
CITESBER
CORA
Complex
Rewiring
FoSR
30.5 3.5
34.7 4. 4.1
30.8 +..
51.3 + 111
50.6 2.1
0.6
81.7 0.8*
Nome
42.6 1: 2.9
52.6 4.3
50.4 2.8 2.8
66.9 0.8
81.6 0.8
FoSR
36.3
49.5 3.0
47.3 3.0
60.2
1.2
68.2 + 0.9
Clique
Prune
40.5
56.3 3.0
51.5 3.1
64.8 0.9"
75.6 1 1.2*
None
15.8::2.77
0.7
FoSR
33.7
53.1 3.5
Ring
Prune
42.1
38.4
2.8
35.0 + 3.3"
Nome
38.9 3.3
34.7
1. 2.2
61.2 3.5
(d) CIN+
CORNELL
TEXAS
WISCONSIN
CITESBER
CORA
Complex
Rewiring
FoSR
41.6 2.0
35.3
51.9
44.9 1.1
64.0 + 1.8
None
42.6
4.7
61.
45.2
55.7
1.8*
None
43.2 +: 4.4
59.5 2.6
54.2 3.8
44.7 1
63.6 1: 2.0
FoSR
47.9
66.3
61.6
GL4 1.0
78.6
Clique
Prune
32.6
37.9 3.2
63.8 3.5
60.5 1 0.7
77.0 1.0*
None
2.75
65.3
63.2
79.1 0.7
Ring
Prunc
4.7
63.2
36,9 + 2.5"
Nome
3..244.22
642
63.1 + 3.0
Table 3: Node classification experiments. Experiments with used 1d curvature for pruning.
In Tables and 10 we provide all the results for Table | from Section 5 We note that in Table [ we only report the Lift=None results for FoSR, and not AFR4 or SDRF, for fair compar- ison with Lift=Clique and Lift=Ring, where we only report the results for FoSR. We note that for 24/32 = 75% of the results on ENZYME, MUTAG, NCII, and PROTEINS, the best performing rewiring algorithms for Lift=None and Lift=Clique agree. Similarly, the best rewiring algorithms for Lift=None and Lift=Ring agree in 17 17/32- 53% of the experiments. In Figure 10 com- pare model performance on graphs and the corresponding clique complexes, and note how graph, relational graph, and topological models all respond similarly to relational rewiring.
34

---

Published as a conference paper at ICLR 2025
Comparison of Model Performance
100
ENZYMES Rewire)
ENZYMES (Best Rewire)
(No Rewire)
(Best Rewire)
Rewire)
80
(Best Rewire)
PROTEINS (No Rewire)
Cilqul Performance
PROTEINS (Best Rewire)
x
60
100
Lift=None Performance
Figure 10: Comparison of model performance between graph representations (Lift=None) and corre- sponding clique complex representations (Lift=Clique). Each point corresponds to specific model on given dataset, comparing the performance with and without rewiring.
35

---

Published as a conference paper at ICLR 2025
Rewire Iterations
10
20
40
Lift
Layers
None
2
86.0 + 2.9
8.40
75.5 + 1.7
8..5
4
87.5 + 2.3
81.0 2..
2.9
6
89.0 + 2.7
2.8
3.7
8.80
Clique
2
85.5 1..5:22
1.
81.0=222
4
86.0 1.9
83.5 2.9 3.6
79.0
6
84.5 =
80.0
12.533.1
80.5 + 2.3
Ring 2
84.5 +: 1.9
2.44
86.5
87.0
4
86.5 + 2.6
2..5
00.5335
86.5 + 1.7
6
82.0 + 1.9
86.0
1.8
86.0 + 2.7
88.0 2.5
Table 4: Impact of increasing the number of layers and rewiring iterations for FoSR on the MUTAG dataset with CIN++.
Rewire Iterations Hidden Dimension
0
10
20
40
Lift
None
16
81.5 + 2.5
77.5
3.7
74.0 + 1.8
32
83.0 2.9
2.8
84.5
82.0 4.2
64
85.0 + 1.8
2.1
8.5
2.4
Clique
16
87.5 3.0
3.6
79.0 2.6
32
83.5 2.2
81.0
80.5
78.5 4
64
2.6
81.0
7.8
2
Ring
16
1.7
8..0
8..
1.1
32
2.8
8
8.2
83.5 1.3
64
85.5 + 3.0
85.0 3.2
86.0 1.8
84.5 + 1.9
Table Impact increasing the hidden dimensions and rewiring iterations for FoSR on the MU- TAG dataset with CIN++.
E.2 SYNTHETIC BENCHMARK: RINGTRANSFER
The RingTransfer benchmark is graph transfer task introduced by [Bodnar al. (202la). Each graph in the dataset is a cycle graph of size 2k for some k: 2 1. A node is randomly selected as the root node and the node j = + ke( mod)2k on the opposite side of the cycle designated as the feature node. All features are initialized to zero except for the feature node which contains one-hot label among the 5 classes. The task is to then predict the label by reading the feature stored in root node. This is shown for cycle graph with 10 nodes in Figure 11] where the red node is the root node and the green node is the opposite node. Note that the size of the ring determines the number of layers necessary for model to complete the task successfully. By increasing the size of the ring, we can test how depth and the task distance impact training performance. When increasing the ring size, the model depth is 2h: + so that task information remains within the model's 's receptive field.
F IMPLEMENTATION DETAILS
F.I MODEL DETAILS
Each model consists of multiple graph-convolution layers. For more details about the convolutional
layers, refer to Appendix F.5 The hyperparameters are presented Table [2] For the real world experiments, each model has a neural network head consisting of pooling operation followed by two layer neural network with ReLU and dropout. The only exception to this is the SGC model which uses pooling and single linear layer for the head. For the synthetic graph transfer experiments, there is no neural network head. Instead, the neural network just returns the feature of the root node the final layer.
36

---

Published as a conference paper at ICLR 2025
Prune Iterations
10
40
Complex
Model
None
GIN
83.0 3.1
8..5
89.0
86.0 = 2.1
RGIN
81.5 + 1.7
84.0
91.
86.0 = 1.2
SIN
88.5 3.0
8.1 2.5
86.5 = 2.5
CIN+
$5.0
1.
8.00
84.5 = 2.5
Clique
GIN
83.0 2.8
1.7
8.1
90.5 1.4
RGIN
86.0 2.3
81.0
2.5
85.0 = 1.7
SIN
3.2
8.2 2.2
84.5 = 3.4
CIN+
90.5
84.5
3.2
91.0 = 1.8
Ring
GIN
90.0 + 2.2
87.5
88.0 +
85.5 1.6
RGIN
87.0 2.3
86.5 2.6
87.0 2.4
SIN
87.5 1.5
$7.0
84.0 - 2.4
88.0 = 2.3
CIN+
87.5 2.6
80.5 + 3.3
88.0
81.5 1.5
Table 6: MUTAG pruning experiment. Removing edges with highest balanced Forman Curvature.
Dataset
Graphs
Classes
Avg. Nodes
Avg. Edges
Features
MUTAG
188
17.93
19.79
NCII
4110
29.87
32.30
37
ENZYMES
600
32.63
62.14
3
PROTEINS
1113
39.06
72.82
1000
19.77
96.53
0
Table 7: TUDataset Statistics.
F.2 HARDWARE
Experiments were run system with Intel(R) Xeon(R) Gold 6152 CPUs @ 2.10GHz NVIDIA GeForce RTX 2080 Ti GPUs.
F.3 LIBRARIES
Code Use: Rewiring algorithms were adapted from the works of Karhadkar et al. (2023) and Fesser & Weber 2023). We used PyTorch Geometric Benchmarks for neural network hyperparameters. We build on the work Giusti et al. (2024) for clique graph lifting and ring transfer: The real world (2020). The SGC model was adapted from the work of Wu et al. (019). For curvature implementations, we adapt code from Nguyen
graph datasets were sourced from the work Morris
al. (2023) for Ollivier-Ree Ricci and Fesser & Weber (2033) for BFC and AFC.
Python libraries: Torch Geometric (Fey & Lenssen
2019). Torch (Paszke et al. 2019). Scikit-Learn
(Pedregosa al. 2011 Ray (Moritz et al. 2018). Ray Tune (Liaw 2018 Seaborn (Waskom
Figure 11: Graph for the RingTransfer experiment.
37

---

Published as a conference paper at ICLR 2025
(a) SGC
ENZYMES
IMDB B
MUTAG
NCI1
PROTEINS
Rewiring
Nome
18.3 1 1.2
49.5 1.5
64.5 1 5.8
55.2 1 1.0
62.2 1 1.4
None
17.0
48.6
65.5
54.1 0.7
65.0
FoSR
18.2 1.7
50.0 1.8
52.5 62.5
49.3
0.8
64.8 + 1.1
None
14.5 1.4
48.7 2.2
70.0
50.0 1.3
59.9
- 1.8
Clique
AFR4
16.3 1.0
> day
62.3 3.0
56.8 0.8
59.1
1.4
FOSR
16.0 1.4
47.8 E 1.6
60.5 5.8
50.0
0.6
50.0
+ 4.3
SDRF
16.8
0.9
>> 12 hours
69.5 2.6
50.8 0.7 0.7
54.9
3.2
65.5
Ring
AFR4
19.3
1 1.2
day
72.5 3.2
50.6 0.6 0.6
1 day
0.8
SDRF
19.0 1.3
12 hours
2.7
014
49.3 = 3.6
(b) GCN
ENZYMES
IMDB-B
MUTAG
PROTEINS
Lin
Rewiring
None
32.2 4 2.0
49.1 1.4
71.0 1 3.8
48.3 3 0.6
73.1 + 1,2
None
AFR4
30.5 1: 2.5
48.6
1.0
69.0 1 2.7
48.4 0.6
72.6
1
1.5
FoSR
27.2 4: 2.5
47.9
8.50
49.1
75.8
SDRF
30.7 + 1.5
46.7#12
72.5
48.9
74.5 = 1.5
None
30.7
69.9
Clique
AFR4
28.2 2.2
day
6.00
48.3
72.5
- 0.9
FOSR
26.0
3.1
81.3
48.8
75.0
1.4
SDRE
30.2 2.4
12 hours
72.0 2.6
49.6
19.6.0.8 0.6
72.1
1.2
None
34.8 1 1.3
46.9 1 1.4
72.0 2.7
49.3 0.9
72.2
1.3
Ring
AFR4
29.0
day
2.3
0.6
day
FOSR
28.8 + 1.6
48.0 1.2
77.5 2.1
47.9 17.90...6
71.3 = 1.6
12 hours
2.8
(c) GIN
ENZYMES
IMDR-R
MUTAG
NCTI
PROTEINS
Rewiring
None
47.2
1.9
71.7 1.5
83.0 3.1
77.2
70.6 = 1.4
Nome
AFR4
50.0 1 2.7
69.7 1 1.8
88.0
1 2.4
77.9 0.5
70.1 1 0.9
FrSR
33.3 1.7 1.7
67.1
1.5
75.5
1.7 1.7
64.8
72.2 + 0.8
SDRF
45.5 2.1
65.8
2.0
84.5 2.8
1.0
72.0
None
14.01..
69.1 1.2
83.0
7.8
68.7 - 1.4
Clique
day
FoSR
39.3 4: 1.4
70.8 1.1
79.0
63.5 0.7
72.8
1.2
SDRE
41.7 2.2
> 12 hours
73.5
7..9
69.2 - 0.8
None
46.7 2.4
70.1 1.7
$8.01...1
78.9 0.6
69.8
1.4
Ring
AFR4
47.0 1.6
> day
89.0 1.9 1.9
77.5
> day
FoSR
0.8
72.0 +
SDRE
41.2 23
1.6
>> 12 hours
79.0 2.7
75.9 0.9
72.1 = 0.9
Table 8: Baseline and rewiring results for SGC, GCN, and GIN. Numbers highlighted in blue corre- spond to no rewiring and numbers highlighted in red are the best among the rewiring methods.
38

---

Published as a conference paper at ICLR 2025
(a) RGCN
ENZYMES
MUTAG
NCTI
PROTEINS
Rewiring
47.6
72.5 2.5
53.2
None
AFR4
36.2 1 2.3
48.1
1.0
69.5 1 3.4
54.3 1.1
72.8
1
1.2
39.3 4:
71.2
-
SDRF
42.5 + 1.3
2.2
76.0
63.4 1.1
75.6
= 1.2
None
48.8
1.2
71.0 1.0
79.3
72.9 0.8
72.4
1.6
Clique
AFR4
42.3 1
2.4
day
78.0 2.1
75.0 0.9
74.2
1.2
FoSR
39.3
4 2.5
69.7 1.5
79.0 3.2
64.5 0.6
70.9
+ 1.4
>
None
35.2 1
1.7
71.1 1.4.4 1.4
83.5 2.7
73.9
70.7
1.6
Ring
34.8
2.1
day
80.5
2.9
73.5
day
FoSR
38.5 + 1.5
70.0 + 1.6
84.0
2.1
0.8
71.3
1,2
SDRE
45.7
1.5
12 hours
79.5 1 3.7
68.3 1.3:00
0.6
68.8
1.1
(b) RGIN
ENZYMES
IMDR-R
MUTAG
NCTI
PROTEINS
Rewiring
None
46.8 1.8
69.6 1.6
81.5 1.7
76.8 1.1
1.1
70.8 +
1.2
None
AFR4
49.8
73.2
85.5 2.0
77.0 0.7
71.1
FOSR
18.2
48.9 2.9
85.5 2.8
55.1
72.4
1.4
49.7 2.1
6..4
85.0
6288 2.7
70.9
None
50.8 1.5
71.6 - 0.9
2.3
7.6
71.5
= 1.5
Clique
AFR4
55.8
2.5
> day
85.0
79.3
71.0
+ 1.1
FoSR
46.2 1.4
69.0 1.4
2.4
72.7 2..6
71.8
1.7
SDRF
45.5 16.5100
1.6
> 12 hours
83.0
7.94
69.
2.4
None
45.3
68
8.90
68.8
Ring
AHR4
49.2 + 1.5
1 day
2.44
79.8 0.77
1 day
FoSR
47.3 1.6
67.2
4.2
0.7
71.3 1.5
SDRE
47.2
12 hours
81.0
0.5
70.0 0.9
Table 9; Baseline and rewiring results for RGCN and RGIN. Numbers highlighted in blue corre- spond to no rewiring and numbers highlighted in red are the best among the rewiring methods.
2021
Matplotlib (Hunter 2007
Networkx (Hagberg et al., 2008).
Pandas pandas development
Team
2020). Numpy Harris et al.
2020). Numba (Lam et al. 2015). Gudhi (The GUDHI Project
2020
POT Flamary al. 2021
F.4
GRAPH LIFTING
We lift graphs to clique and ring complexes for relational message passing using Algorithm 3 We refer to this graph lifting as the Clique and Ring lifts. Note that when representing a graph as a complex (c.g., max-dim O), simply add the t relation to the edges. We refer to this graph lifting as the None lift. The resulting complex has trivial cell intersections and does not contain cell unions. This is outlined in Algorithm 2 We note that whereas clique lifts introduce higher- order simplices by introducing simplices for cliques in the graph, ring lifts instead promote cycles to 2- 2-dimensional cells.
F.5 LAYERS
We review the implementation of the layers and update rules used in the models considered in this work. In the following, C(.), (+))), and N.(-) follow the definitions Definition [.3] Given a relational structure R = (S, R....., RR), the notation E R refers to iterating over the relation indices r = 1, 2..., k. For binary relation R C S, R(-) denotes the incoming neighborhood of an entity, i.e., for any a, E if E (v(r), then (a, T) E R.
SGC Following Wu al. 2019), the SGC update rule is:
h (1+1)
Σ
h
FER TEAR, (a)
where no learnable weights nor mon-linearite are used, and signals are simply aggregated over neighborhoods.
39

---

Published as a conference paper at ICLR 2025
(a) SIN
ENZYMES
MUTAG
PROTEINS
Lin
Rewiring
Nome
47.5 1 2.3
70.0 1 1.4
88.5
1 3.0
77.0
0.6
70.2
1.3
None
AFR4
44.0 2.5
71.0 1.0
85.5
1.7
1.7
76.4
0..40..4 0.4
69.6
+ 1.3
FoSR
45.7 + 2.6
63.0 2.7
86.5
2.8
2.4
73.2
SDRE
16.8 2.11
62.8 3.3
8..0
54.7 3.5
70.2 - 1.8
Nume
66.9
Clique
AFR4
16.5 1.2
day
13.5+111
75.4
69.6 + 1.0
FOSR
38.2
2.2
64.0 2.3
83.3
2.7
65.2
70.4
1.2
SDRF
44.8
1
12 hours
80.0 1 3.5
73.9 1.4
68.7 1.2
None
40.3
+ 2.2
50.6 1.9
85.0
80.0 0.8
70.6 + 1.1
Ring
AFR4
day
day
FOSR
39.8 1.6
60.9 2.1
86.0
7.22
72.1 = 0.7
(b) CIN
ENZYMES
IMDB-B
MUTAG
NCII
PROTEINS
Rewiring
None
51.4
70.7 +
Nome
AFR4
48.2 1
58.8 1 4.3
87.0 1 2.4
53.3
1 2.6
71.0
1.4
FoSR
49.0 2.0
2.4
81.0 1.0 1.8
66.2
+ 2.0
70.9 - 1.3
SDRF
55.3 2.5
82.5
4.3
None
49.8 1.9
52.6 2.4
65.5
51.8 2.3
70.7
1.2
Clique
day
FoSR
37.2 4 1.8
68.1
1.6
82.5 3.0
66.9 0.9
70.3 - 0.8
42.0 2.3
> 12 hours
78.5 4.1
72.3 0.8
67.9 1.8
None
47.5.200
48.6
93.5 2.1
51.6 3.2
68.7
Ring
AFR4
49.5 2.0
>> day
92.5 1.5
G8.2 4.2
>> day
FOSR
70.4
68.5
SDRE
38.2 1: 2.2
> 12 hours
88.0 1 2.4
76.5 1 0.5
65.6 + 1.3
(c) CIN+
ENZYMES
IMDR-B
MUTAG
NCTI
PROTEINS
Lift
Rewiring
None
48.5 + 1.9
06.6
85.0
60.8 + 3.8
67.9 + 1.9
None
AFR4
51.0 1.5
61.0
91.0 2.3
54.8 3.7
70.7 = 1.3
FOSR
50.5 1.8
3.9
#2.0
64.8 3.1
71.4
1.4
SDRF
45.8 1: 2.2
53.3 2.3 2.3
87.5 2.3
58.0 1 4.4
69.3
1.6
50.5
68.3
Clique
AFR4
52.7 1: 1.6
> 1 day
84.5 1: 3.3
60.6 4.8
66.7 1 1.3
SDRP
47.7 + 1.5
12 hours
81.0
76.8 0..40.4 0.4
70.0 - 1.7
None
47.5
1.7
66.0 1.4
85.3
56.8 4.5
1.2
Ring
AFR4
46.3 1.8
day
90.0
59.5 4.1
day
FOSR
46.0 2.8
67.8 1 1.3
85.0
71.9 1 0.8
70.1 1 1.2
4.52
Table 10: Baseline and rewiring results for SIN, CIN, and CIN++. Numbers highlighted blue correspond to rewiring and numbers highlighted in red are the best among the rewiring methods.
Parameter
Value 1000
Number of Graphs
Trials
Default Neighbors Match Cliques
Default Neighbors Match Clique Size
Default Ring Transfer Nodes
10
Table 11: Synthetic Parameters
40

---

Published as a conference paper at ICLR 2025
Parameter
Value
Layers
Hidden
64
Dropout
0.5
Pooling
Multidimensional
False
Max Dimension
Table 12: Model Parameters
Parameter
Value
Optimizer
Adam
Batch Size
64
Learning Rate
0.001
Max Epochs
500
Stop Criteria
Validation
Stop Factor
1.01
Stop Patience
100
Table 13: Optimization Parameters
Algorithm Graph Lifting (None)
Input: Unweighted undirected graph G = (V, E), node features (Xu)veV Output: Relational structure (S, Rupper)) and features (X,)oeS
I: Initialize S =
> Entities
2: for each node E do
3:
- (v)
4: S-SU {a}
5:
X,
Features
6: end for
7:
Initialize Rupper
0
Relations
8: for each edge {u, v) E E do
9: O,T u,
10: Repper + Ruppor U ((o,T),(T,)))
end for
12: return (S, (Rupper H) and (x,)oe loes
41

---

Published as a conference paper at ICLR 2025
Algorithm 3 Graph Lifting (Complex)
Input: Unweighted undirected graph = (V, E), node features (x,)vev, relation types A C (boundary, coboundary, lowe, upper). max simplex dimension max_dim Output: Relational structure (S, {R, brea) and features (x,) )x)
1: Initialize S =
>> Entities
2: for each non-empty clique C V with a S max_dim do
3: S S
4: X, x Evco X
Features
5: end for
6: for each relation type E A do
7: Initialize R = /
Relations
8:
for each entity S do r bbundary then for each r B(or) do Rr + Rr ((a,T) end for else if r coboundary then for each C(o) do R2 + R2 ((o,T) end for else if r lower then for each r E NN((o) do R2 R2 U ((a,T,ann))
9:
11:
13:
15:
17:
18:
19:
20:
end for else if upper then for each r E N4 do R2 Rr U ((C,T)
21:
22:
23:
24: end
end for
26: end for
end for
28:
return (S, (Re)rea) and (x,)
42

---

Published as a conference paper at ICLR 2025
GCN
Following Kipf & Welling (017), the GCN update rule is:
dddd m00 )
h ((+1) =f w
Σ FER TENR,
where f is a point-wise non-linearity (c.g,, ReLU), W is learnable weight matrix, and d, deg(r) +
GIN Following Xu et al. 2019). the GIN update rule is:
(a+O)ng + Σ Σ
h (++)) MLP())
w
TER (EN,
where W()) is learnable weight matrix and is a learnable scalar. Here, MLP consists of two layer fully connected layers, each followed by point-wise con-linearity (c.g.. ReLU) and a BatchNorm layer.
R-GCN Following Schlichtkrull et al. (2018), the R-GCN update rule is:
h (++1) =f (t) ( a
Σ Σ
w (()
(i)
FER (EN
where f is component-wis non-linearity (e.g., ReLU), and w roor and ( are learnable weight matrices.
R-GIN Following Xu et al. (2019) and Schlichtkrull et al. (2018) the R-GIN update rule is
h(++1) (:(t) h(?
Σ MIP(() FER
(1 (1+
Σ h
TEN.(o)
where W root a learnable weight matrix and each c, is a learnable scalar. Here, each MLP consists of two layer fully connected layers, each followed by a point-wise non-linearity (e.g., ReLU) and BatchNorm layer. and MLP(') is a relation-specifie MLP.
SIN Following Bodnar al. (021b). the SIN update rule is:
MLP B.
(1 (1+ ho
h 8EB(()
Σ
(1)
MLP
(1+ (
Σ
h
h (++1) (t.((t)
U.p
8ENi(()
additionally, when rewiring:
MLP Brees p
(1 + (Reww
he +
h
&EN (a)
where [-] denotes column-wiss concatenation and each c, is a learnable scalar. Here, each MLP con- sists of two layer fully connected layers, each followed by point-wise non-linearity (e.g., ReLU) and BatchNorm layer. and MI.P(!) is relation-specifee MI.P.
43

---

Published as a conference paper at ICLR 2025
CIN
Following Bodnar et al. (2021a), the CIN update rule is:
M. B. ( (1+ hō)
Σ
h
rEB(ar
(e)
MLP T.p
(1+G) + Σ M.PM.p
h h(++1) MLPP()
U.p
TEN+iO) SEC(O.T
hg
(c)
additionally, when rewiring:
MLP Rosw
(1 + Rago
Σ
h
(E)
R (a)
where denotes column-wise concatenation, each c, is learnable scalar, and MLPM,p a single fully connected layer projecting back to the dimension of h The other MLPs consists of two layer fully connected layers, each followed by point-wise non-linearity (e.g.. ReLU) and a BatchNorm layer. When entity unions aren't 't contained in the relational structure due to dimension constraints, we instead use h
CIN++ Following Giusti et al. 2024), the CIN++ update rule
MLP (1+e8) hd
Σ
h
rEB(rr
h
MLP T.
(1+4)
(0)
Σ
MLPM.P
h
TEN;(O)
SEC(O,T)
(++1) MLP(() 7
U.p
h
MLP 4.P
(1+4)
E
MLP
h
(L)
TEN
BEB(a.T)
additionally, when rewiring:
MLP MLPR RacniP
(1 + ERoce h6 +
Σ
h
8EN (a)
where [-] denotes column-wise concatenation, each is learnale scalar. MLP and MLP P are single fully connected layers projecting back to the dimension of h.(') The other MLPs consists of two layer fully connected layers, each followed by point-wise non-linearity (e.g.. ReLU) and a NorchNorm layer. When entity unions or intersections aren't 't contained in the relational structure
due to dimension constraints, we instead use h()) 0.
G HIGHER-ORDER GRAPHS ARE RELATIONAL STRUCTURES
Although we do not focus on higher-order graph neural networks (k-GNNs) (Morris et al.) 2019) in this work, we briefly illustrate how they naturally fit into our relational framework. In A GNNNs graphs are lifted into oigher-order graphs following the procedure outlined in Algorithm framework, these higher-order graphs can be viewed relational structures, where each entity rep- resents a set of nodes of size n k. The relations between these entities are of two types: local relations, which connect entities differing by one node and where the differing nodes are adjacent
In our
44

---

Published as a conference paper at ICLR 2025
in the original graph, and global relations, where the differing nodes are not adjacent in the origi- nal graph. From this perspective, k-GNN message passing on higher-order graphs is equivalent to R-GCN message passing the corresponding relational structures. We leave the theoretical and empirical study of these relational structures for future work.
Algorithm Graph Lifting (Higher-Order Graph)
Input: Unweighted undirected graph (V, E), node features (x,) eev, entity size n Output: Relational structure ( (ool Rigoss }) and features (xa)an JaES
1: Initialize S = 0
> Entities
2: for each subset a S V with lor = n do
3: S+ {o}
4: Xo t LuEo X
Features
5: end for
6: Initialize Riocal 0, Ryioval =
Relations
7: for each pair a, E S do
8: if f n then
9:
Let {8) o and =T
10:
(sa, ( E then
11:
Rocal + Biocs (((o,T)(TTo)}
12:
else
13:
Rylobel Rgioba: U ((o,T), end
14:
15:
end if
16:
end for
return (8, (Rioca1, Rgiobai and (xo)oES
H WORKED EXAMPLE: RELATIONS AND OPERATORS FOR A PATH GRAPH
In this section, we illustrate, via a small example, the definitions of simplicial complex, relational structure, and influence graph.
Simplicial Complex. Consider the simplicial complex K. corresponding the path graph i i-j k. The complex K. consists of
O-simplices (vertices): (1), {j), {k}. and
1-simplices (edges): {t,j), {j. k}.
Relational Structure.
The relations on the set of entities S = K. are as follows:
Relation Ry (identity):
Rı = l a EK
= ((()), (U)). (()), ((4J)), ((i))))
Relation R2 (boundary):
Rs (())
(li.)) (t..). ((i,6) (G.)).
Relation Rg (co-boundary):
Rs = (ox,))))
((),)
45

---

Published as a conference paper at ICLR 2025
Relation R4 (lower adjacency):
R4 0
((1,)) (i,k),
(11))))
Relation Rg (upper adjacency):
Rs
(ii) (i.)), (0),,)), ) (i.)), ((+), (i.
If assume, for the sake of example, that all relations are involved in message passing, this gives rise to the relational structure
R(K) (S, R1, R2, R3, R1, Rs).
Of course, one could restrict message passing
smaller subset of the relations
[R1, R2, R3, R4. Rs}.
(R}
Boundary
Co-boundary
Lower
Upper
(a) Simplicial Complex IC
(b) Adjacency Relations on K.
8
i
j
i.
k
22
2
12
1
8
(c) Influence Graph G(S,B) B)
Figure 12: (a) The simplicial complex K. consisting of nodes i, k, and edges {i,j), ki. (b) The adjacency relations on K., showing boundary, co-boundary, lower, and upper relations. (c) The influence graph G(S, B) representing the information flow between the entities.
Shift Operators. In what follows, we index the entries in matrices as follows:
Index
Simplex
2
[
3
{k}
4
[i,]]
5
{j,k}
46

---

Published as a conference paper at ICLR 2025
For instance, the 14th entry in matrix would correspond to the connection (fi), {i.))). We assume, for the sake of example, that all shift operators correspond to the adjacency tensors, i.c., the entries with indices corresponding entries are all O. Of course, normalized adjacency tensors and others could be similarly considered. As such, get the following:
entities that are related by relation are equal to 1, and the remaining
Shift operators A Ri and A Ri (identity relation):
0
0
0
0
1
0
A
R1
R4
0
0
1
0
0
0
0
0
Shift operators A R2 and A R2 (boundary relation):
0
0
0
0
0
A R A R2
0
1
1
0
0
1
Shift operators A Ra and À Rs (co-boundary relation):
0
0
0
0
A Rs A
0
0
0
0
0
Shift operator R4 and A R4 (lower adjacency relation):
The non-zero entries of A are
A R4
A R4
=1
R
The aggregated influence for A Ra:
0
0
0
0
0
A R4
0
0
0
0
1
Shift Operator Rs and À Rs (upper adjacency relation):
The non-zero entries of A Its are
A Rs
A Rs.
A
RG
=
(3)
The aggregated influence for À Ra:
1
0
1
1
À Rs
0
0
0
0
47

---

1 Published as a conference paper at ICLR 2025
Lastly, the aggregated influence matrix À arising from including all relations R₁ to Rş:
A
A
R1
+
A
A
A n
0
2
0
1
1
2
2
0
2
0
1
1 1/
The maximum row sum of À is y = 7, giving rise to the augmented adjacency matrix
B
I
A
8
0
1
8
2
2
2
1
2
8
1
0
8
The influence graph is finally constructed from B follows:
Nodes: Each simplex in AC
Edges: For each (a, r), if Bor > 0, there is a directed edge from to with weight B
I COMPUTATIONAL COMPLEXITY
It is well known in the TDL community that topological methods can require much more computa- tion due directly modeling higher-order structures. This typically incurs combinatorial complexity in the algorithms. A common strategy is to truncate the dimensionality of the objects considered to maintain polynomial complexity. Another option to use a sparse complex construction method. As noted earlier, more work is needed in understanding graph lifting and which method is preferred in given setting. In this section, we analyze the running times required for TDL with clique complexes.
1.1 CLIQUE COMPLEX SIZE
The exact computational requirements of performing clique lifting depend on the graph in consider- ation. However, there are few cases where we can provide precise estimates.
Clique lifting of dimension In this case, the highest dimensional cell is the edge cell. Consider graph G = (V, E) with [V| n nodes, | = m edges, and maximum node degree d. The corresponding clique complex has:
1. n + cells
2. 2m boundary relations
3. 2m co-boundary relations
4. ΣvEV ((deg(e)) < 2md lower relations
5. 2m upper relations
Note that we need to count the upper and lower relations for each direction of the edge so we get factor of 2.
Clique lifting of dimension 2 If G has FF ls faces, then the clique K. contains
n + m + cells
2. 2m 3k boundary relations
3. 2m 3k co-boundary relations
48

---

Published as a conference paper at ICLR 2025
4. Ever 2( (( + EoeF X(anT) lower relations
5. 2m + 6k upper relations
In dense graphs, the number of lower relations can be very large. Depending on the dataset under consideration, one may opt for model like CIN where lower relations ignored.
Complete Graph We can provide precise estimates when we have complete graph. This can help us understand performance the limiting case that the graph very dense or contains large cliques. Consider complete graph K, on nodes and the cell the boundary n m cells and the co-boundary of m cells. upper adjacent to (n m cells. It is lower adjacent to m(n m) cells. Counting all the cells of dimension d = 1, we get
21, .... m. for m 2 1. This
1. na ( cells
2. na(n - 1) boundary relations (if > 0)
3. na(d + 1) co-boundary relations
4. na(d (n d 1) lower relations (if d >
5. na(d (n d 1) upper relations
where the d > condition comes from the fact that there isn't 't a cell { in the complex so there aren't lower co-boundary relations for zero dimensional cells. Computing the total number of cells gives 2 - 1. The total number of edges is
-n(n 1)
Σ d=0
T3 (n (n d 1)(d 1))
d+1
22 (2 + 2" 2) n (2222²)
2
This bound is prohibitive for large n. If we restrict to two dimensional cells, we get the total number of cells is
n23 + 5n
+ +
O
6
and the total number of relations is
(-24 + 41n 24n + +7n) = (n²)
1.2 CLIQUE LIFT COMPLEXITY
Our main use case is computing complexes for two-dimensional cells. In this section, compute the complexity of clique lifting. Note that computing the and I-dimensional cells is fast since they encoded directly in the graph nodes and edges, respectively. The boundary and coboundary relations encode edge incidence to a node and are also easily obtained. The upper relations on the O-cells are just the edges in the graph. The lower relations on the edges are all pairs of edges in the graph sharing a node. This can be efficiently computed by storing the edge incidences in dictionary in (m) time and then computing all pairs the neighborhood of each node. This requires O (n (n+ Evev ( (dog(v)) computation. For connected graphs, this reduces to 0(md)-
Computing the two-dimensional cells can also be done efficiently. By storing the neighborhood dictionary, we just need loop over pairs of edges (u, v), (u, w) in the neighborhood of and check if ww, E G. This can be done in O (Evev (deg(e))
O(md) time. The boundary,
co-boundary, and upper adjacencies can be easily computed in O(k) time. The lower adjacency computation for 2-cells can require more time. For a given edge (u, v). consider the 2-cells such that (u, v) < a. Each pair of these gets lower adjacency and can be efficiently added. This results
[Ce))
Σ KEE
49

---

Published as a conference paper at ICLR 2025
computation. We can bound this
Σ eE
[(()))
c(e)) < max (C()]]
Σ c 2
[C()]
3/
max ((e))
2
cEB
and get the complexity bound
O (k ((e)))
This is analogous to the result with lower adjacency of 1-cells that relied on the maximum node degree in G. The maximum co-boundary degree max, [C(e) is the analogue of node degree for 2-cells. So, the clique complex construction up to dimension 2 has time complexity:
O + lo max (C())))
1.3 RUNNING TIMES
Lift
None
Clique
Ring
ENZYMES
2.12
6.89
1 11.81
IMDB-B
3.51
45.04
101.98
MUTAG
1.60
1.22
1.48
NCII
4.70
20.26
26.62
PROTEINS
2.99
16.07
30.73
ZINC
63.47
94.70
106.37
TEXAS
6.02
2.64
0.65
WISCONSIN
6.09
2.78
0.74
CORNELL
5.05
2.76
0.62
CORA
5.77
8.29
45.71
CITESEER
7.05
7.65
NA
Table 14: Time to perform graph lifting and download datasets from Torch Geometric.
50


Reviews:
[{"review_id": "DhVVtjRgcr", "reviewer": "Reviewer_HYLT", "summary": "The authors present a generalisation of theoretical results on oversquashing in graph learning to topological deep learning by formulating these within the framework of relational structures. This framework more generally presents an interesting approach for extending theoretical results from graphs to higher order structures.", "questions": "- Is there a correspondence between the message passing graph introduced  by Bodnar et al. and the aggregated influence matrix introduced in Eq.6? \n- The rewiring algorithms considered in the paper are limited to the addition of edges however sometimes lifting graphs to clique complexes can introduce redundancies therefore could maybe rewiring algorithms that also prune edges be a better fit this context? \n- The rewiring algorithms considered in the paper are limited to binary edges however in general rewiring algorithms that also include the modification of higher order edges might further improve performance. Do the results presented in the paper provide insights into how one could proceed to formulate such higher order rewiring algorithms?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "- The paper is well written and easy to follow. \n- Relational structures seem to provide a general unified framework that includes not only simplicial message passing but also other higher order structures. \n- Propositions and theorem are well defined and proofs are mathematically sound.", "weaknesses": "- The experimental settings where the combination of lifting and rewiring leads to performance improvements seems to be limited.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qckRJbOSDp", "reviewer": "Reviewer_Sfm7", "summary": "The authors make three main contributions.\n\nFirst, they propose a general message-passing scheme for relational structures and show that it generalizes R-GCNs, simplicial neural nets, and higher-order GNNs. This interesting connection will hopefully prevent different communities with different terminologies from working in parallel on the same type of problems. \n\nIn Definition 2.6, you should make sure all variables are properly introduced. For instance, $p_t$ is the size of the feature representation of the \\sigma s at time t. This size variable does not occur in the previous simplicial message-passing scheme. Making the terminology consistent or at least introducing each with a sentence will help readers to more easily understand the terminology. \n\nThis approach of reformulating higher-order structures as relational structures allows insights about over-squashing from graph neural networks (GNNs) to be translated to a broader class of relational message-passing systems. Introducing the aggregated influence matrix and influence graph as core tools makes it possible to study how factors like local geometry, network depth, and hidden dimension size impact message passing in these systems, much like in traditional GNNs.\n\nFinally, the authors use the proposed framework and connection to generalize rewiring methods from prior work to the relational setting. Here, it would be interesting to understand better how computationally complex the rewiring techniques are regarding the number of relations, their arity, and elements in S. This would make the trade-off between these heuristics and the gains in the experiments more explicit. \n\nThe paper makes important theoretical contributions. Most notably, I appreciate the connection between relational GNNs and topological GNNs. Bridging one or more communities that are thinking about similar problems and making them aware of each other is important. The paper is generally well-written and easy to follow. As mentioned above, there is some minor room for improvement in the definition of the terminology. Some more explanations in natural language when defining terminology could make it a bit easier for the reader. \nThe main weaknesses of the paper are the “real-world” datasets used in the experiments and the missing discussion of the complexity–accuracy trade-off by omitting a discussion of the computational complexity of the rewiring techniques. This should be an easy fix for the latter by adding another section to the appendix and referring to it in the main paper. Regarding the former, I believe no graph ML method should only be evaluated with the TUD dataset. This provides very limited empirical evidence for a method. Several other datasets (e.g., those about atomistic structures such as QM9, MD17, the peptides datasets, and many more) could have been used. The method could have also been tested on node and link prediction problems, which is the main area of use for relational GNNs. All of these datasets and evaluation setups have shortcomings, of course, but a broader set of problems would make the empirical results much more convincing. This is a very strong theoretical paper with weak empirical evidence that the proposed method is helpful in practice and worth the overhead.", "questions": "- Why did you not run experiments on realistic datasets beyond TUD?\n- Why did you not consider entity (node) and link prediction experiments, which are typically the main targets of relational GNNs", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "- Strong theoretical contribution, establishing connections between different classes of GNNs.\n- Theoretical machinery for understanding over squashing and other phenomena in relational and topological GNNs\n- New rewiring heuristics for relational and topological GNNs", "weaknesses": "- Missing discussion of the computational complexity of rewiring\n- Weak experimental results due to very limited set of problems the approach was evaluated with", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "kiaTcA1ToH", "reviewer": "Reviewer_MJXt", "summary": "This paper provides both theoretical and experimental insights into oversquashing within Topological Deep Learning (TDL), a research direction recently highlighted as important for the TDL community in a recent position paper [1]. The authors encode topological structures, specifically simplicial complexes, as relational structures, allowing these to be transformed into weighted graphs via shift operators. Using this framework, they extend existing work on graph oversquashing and adapt popular rewiring algorithms to topological domains. The paper then presents experimental evidence supporting the theoretical findings and evaluates the combined performance of rewiring and TDL methods on TUD graph benchmarks.\n\n[1] Theodore Papamarkou, Tolga Birdal, Michael M Bronstein, Gunnar E Carlsson, Justin Curry, Yue Gao, Mustafa Hajij, Roland Kwitt, Pietro Lio, Paolo Di Lorenzo, et al. Position: Topological deep learning is the new frontier for relational learning. In Forty-first International Conference on Machine Learning, 2024.", "questions": "Is there significance in using multiple relations rather than a single one, other then for clarity? Could tighter bounds,  e.g. in equation (8)  be achieved by considering matrices  $B^{R_i}$ rather then a single $B$? Conversely, is it possible to combine all relations into a single “union relation”?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper successfully extends key results on graph oversquashing to topological domains, providing a comprehensive theoretical foundation for this adaptation.\n\n2. The paper tackles questions that have been of interest to the TDL community, as highlighted in the recent position paper [1].\n\n[1] Theodore Papamarkou, Tolga Birdal, Michael M Bronstein, Gunnar E Carlsson, Justin Curry, Yue Gao, Mustafa Hajij, Roland Kwitt, Pietro Lio, Paolo Di Lorenzo, et al. Position: Topological deep learning is the new frontier for relational learning. In Forty-first International Conference on Machine Learning, 2024.", "weaknesses": "1. The novelty of the paper is somewhat limited. It reduces simplicial complexes to an \"influence graph\" and then re-derives several previously established results on graph oversquashing. The observation that simplicial complexes can be encoded as graphs has been explored in prior work e.g. [1,2,4] (which i would quote if not quoted already), and many of the paper’s results on oversquashing closely mirror existing studies.\n\n2.  An important question regarding oversquashing and TDL is understanding the effects of oversquashing in topological domains compared to standard graphs. Specifically, it remains unclear whether lifting graphs to higher-order domains could mitigate some effects of oversquashing. The paper does not address this question theoretically, and its empirical analysis only begins to explore this comparison. Instead, it primarily focuses on extending existing results on graph oversquashing to TDL, leaving a key question raised in the position paper [3] only partially addressed.\n\n3. A minor critique is that the paper quickly reduces simplicial message passing to a relational setting, which is more combinatorial than topological. It would be interesting to see an analysis of oversquashing that leverages properties of the underlying topology of the simplicial complexes, such as topological curvature.\n\n4. The experimental section has several issues: First, the real-world benchmarks are limited to TUD datasets, which are somewhat outdated, with a small number of samples and problematic evaluation. It would strengthen the results to include newer benchmarks, such as the Zinc and OGB datasets. These datasets were also used in the papers introducing  CIN and CIN++ which are baselines used in this paper. Additionally, since recent TDL models such as CIN and CIN++ use cyclic lifting rather than clique lifting, it would have been beneficial to include cyclic lifting across all experiments. Lastly, the effects of rewiring on real-world datasets appear inconclusive, making it difficult to determine when rewiring should be applied with TDL models.\n\n[1] Yam Eitan, Yoav Gelberg, Guy Bar-Shalom, Fabrizio Frasca, Michael Bronstein, and Haggai Maron. Topological blind spots: Understanding and extending topological deep learning through the lens of expressivity. arXiv preprint arXiv:2408.05486, 2024.\n\n[2] Mustafa Hajij, Ghada Zamzmi, Theodore Papamarkou, Nina Miolane, Aldo Guzm´an-S´aenz, Karthikeyan Natesan Ramamurthy, Tolga Birdal, Tamal K Dey, Soham Mukherjee, Shreyas N Samaga, et al. Topological deep learning: Going beyond graph data. arXiv preprint arXiv:2206.00606, 2022.\n\n[3] Theodore Papamarkou, Tolga Birdal, Michael M Bronstein, Gunnar E Carlsson, Justin Curry, Yue Gao, Mustafa Hajij, Roland Kwitt, Pietro Lio, Paolo Di Lorenzo, et al. Position: Topological deep learning is the new frontier for relational learning. In Forty-first International Conference on Machine Learning, 2024.\n\n[4] Mathilde Papillon, Guillermo Bern´ardez, Claudio Battiloro, and Nina Miolane. Topotune: A framework for generalized combinatorial complex neural networks. arXiv preprint arXiv:2410.06530, 2024.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "PHbotYPm9R", "reviewer": "Reviewer_Qn33", "summary": "This paper addresses a well-known issue in Graph Neural Networks known as over-squashing. It introduces a framework called the Relational Message Passing Model, which unifies various higher-order message-passing approaches. This unification is leveraged to theoretically examine over-squashing within the context of higher-order message-passing.", "questions": "Please refer to the weaknesses.\n\nSuggestion:\n\nIt is observed in line 167 that certain projections exist from $ R_4(\\sigma) $ to $ R_2(\\sigma) $ and from $R_2(\\sigma) $ to $ R_1(\\sigma) $ (similarly, from $ R_5(\\sigma) $ to $ R_3(\\sigma) $ and from $ R_3(\\sigma) $ to $R_1(\\sigma) $). The relational structure could be further enriched by treating the set of relations as a directed set. Considering the direct limit of this directed set may provide a comprehensive summary of all the relations within the given relational structure. This could serve as a terminal object for defining message functions, potentially enhancing the model’s representational capacity.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This paper addresses a critical gap in the literature on over-squashing. Over-squashing remains underexplored in the context of higher-order message-passing architectures like simplicial neural networks and CW networks. This paper takes an essential first step toward addressing this gap within Topological Deep Learning. By presenting a unifying, axiomatic framework, a relational perspective on simplicial and cellular complexes is provided. This unified approach facilitates the analysis of over-squashing in topological message-passing networks.", "weaknesses": "The paper appears to be a relatively straightforward extension of Topping et al. (2022). This impression arises primarily from Definition 2.6, which is positioned as the core contribution. This definition raises several concerns:\n\n1. The substitution of $R_i$ with $\\mathcal{S}^{n_i}$\n  seems to have minimal impact on the overall definition, effectively diminishing the role of relations $R_i$ within the definition.\n\n2. The shift operator $A^{R_i}$, associated with relation $R_i$, quantifies the signal passed from $(\\xi_1, \\cdots, \\xi_{n_i-1})$ to $\\sigma$ when $(\\sigma, \\xi_1, \\cdots, \\xi_{n_i-1}) \\in R_i$. However, it does not account for the signal passed from $(\\sigma, \\xi_2, \\cdots, \\xi_{n_i-1})$ to $\\xi_1$. Consequently, $A^{R_i}$ may not serve as an adequate representation of $R_i$.\n\n3. The update rule and message functions $m^{(t)}_{\\sigma,i}$ can be viewed as updated versions of the update rule and message function that appear in Equation 1 from Topping et al. (2022), adapted for dimensions $k$ and $n_i$. These functions exhibit a behavior similar to the update rule and message functions in Equation 1 from Topping et al. (2022) when computing the Jacobian in Lemma 3.2. Consequently, this lemma appears to be a straightforward extension of Lemma 1 from Topping et al., lacking significant innovation or depth.\n\n\nTopping et al. \"Understanding Over-Squashing and Bottlenecks on Graphs via Curvature.\", 2022.\n\nMinor Comments:\n\nLine 34: \"Questions 2 and 9\" should be changed to \"research directions 2 and 9.\"\n\nDefinition 2.3: The symbol $\\succ$ is used but not defined. This definition may be updated by replacing $\\succ$ with $\\prec$.\n\nDefinition 2.4: Is this definition necessary for the paper’s main arguments?\n\nDefinition 3.1: In the expression \"$Q \\in \\tilde{A}, B$\", it would be clearer to write \"$Q \\in \\lbrace \\tilde{A}, B \\rbrace$.\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xiGFgPxyFQ", "reviewer": "Reviewer_SPF6", "summary": "This paper proposes a unified axiomatic framework, aiming at the over-squashing phenomenon and the lack of theoretical analysis in graph topological message passing. The framework examines simplicial complexes and their message-passing schemes from the perspective of relational structures, closely combines graphs and topological message passing, and extends them to high-order structures, enhancing the theoretical analysis ability and effectively alleviating the over-squeezing problem.", "questions": "Please refer to weaknesses.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. The message-passing theory of simple complexes and their relational structures is comprehensively and intensely studied, and a detailed explanation and rigorous proof are provided.\n\n2. The article has a clear structure and a smooth and natural expression, which is easy for readers to understand and grasp.", "weaknesses": "1. The literature review on relational graph neural networks mainly focuses on research in 2020 and before, which limits the comprehensive grasp of the latest progress in this field. It is necessary to include more recent research results to enhance the timeliness and persuasiveness of the review.\n\n2. Although the comparison method includes a baseline for 2024, more is needed in terms of SOTA (state-of-the-art) comparison in the past two years to ensure the comprehensiveness and superiority of the evaluation.\n\n3. Given that this study aims to explore the over-squeezing problem, unfortunately, the paper fails to show the results of the application of this method in deeper models, thus failing to verify and strengthen the conclusions obtained in a more in-depth manner. The lack limits the comprehensiveness and persuasiveness of the study.\n\n4. Although the paper mentions the impact of local complexity, model depth, and hidden dimension on performance, unfortunately, it fails to provide corresponding ablation experiments to verify the impact and effectiveness of these factors from an experimental level, which to some extent weakens the experimental support for the conclusions.\n\n5. Many of the formulas in the paper are not original, so it is recommended that the author provide corresponding references for these equations.\n\n6. Why does the article take up so much space on the simplicial complex and its influence on over-squashing? Although this part is also essential, its level of detail exceeds the description of the solution part far, giving people a slightly unbalanced impression. The content distribution can be appropriately adjusted to make the solution part more detailed to ensure the focus is highlighted.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)