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
Primary area: learning on graphs and other geometries & topologies
Keywords: topological deep learning, oversquashing, rewiring, relational graph neural networks, simplicial complexes, relational structures

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.

Decision: accept (poster)
Reviewer scores: 8, 8, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730191358709

thread_type:
official_review

<thread_object>
creator: reviewer_spf6

<content>
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.

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.

2. 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.

2. 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.

3. 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.

4. 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.

5. Many of the formulas in the paper are not original, so it is recommended that the author provide corresponding references for these equations.

6. 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.

questions:
Please refer to weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730252957827

thread_type:
official_review

<thread_object>
creator: reviewer_qn33

<content>
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.

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:

1. The substitution of $R_i$ with $\mathcal{S}^{n_i}$
  seems to have minimal impact on the overall definition, effectively diminishing the role of relations $R_i$ within the definition.

2. 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$.

3. 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.


Topping et al. "Understanding Over-Squashing and Bottlenecks on Graphs via Curvature.", 2022.

Minor Comments:

Line 34: "Questions 2 and 9" should be changed to "research directions 2 and 9."

Definition 2.3: The symbol $\succ$ is used but not defined. This definition may be updated by replacing $\succ$ with $\prec$.

Definition 2.4: Is this definition necessary for the paper’s main arguments?

Definition 3.1: In the expression "$Q \in \tilde{A}, B$", it would be clearer to write "$Q \in \lbrace \tilde{A}, B \rbrace$."

questions:
Please refer to the weaknesses.

Suggestion:

It 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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730370059166

thread_type:
official_review

<thread_object>
creator: reviewer_mjxt

<content>
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.

[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.

strengths:
1. The paper successfully extends key results on graph oversquashing to topological domains, providing a comprehensive theoretical foundation for this adaptation.

2. The paper tackles questions that have been of interest to the TDL community, as highlighted in the recent position paper [1].

[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.

2.  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.

3. 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.

4. 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.

[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.

[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.

[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.

[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.

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”?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730465062895

thread_type:
official_review

<thread_object>
creator: reviewer_sfm7

<content>
summary:
The authors make three main contributions.

First, 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. 

In 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. 

This 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.

Finally, 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. 

The 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. 
The 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.

strengths:
- Strong theoretical contribution, establishing connections between different classes of GNNs.
- Theoretical machinery for understanding over squashing and other phenomena in relational and topological GNNs
- New rewiring heuristics for relational and topological GNNs

weaknesses:
- Missing discussion of the computational complexity of rewiring
- Weak experimental results due to very limited set of problems the approach was evaluated with

questions:
- Why did you not run experiments on realistic datasets beyond TUD?
- Why did you not consider entity (node) and link prediction experiments, which are typically the main targets of relational GNNs
</content>
</thread_object>

</thread>
<thread>
creation date:
1730725327666

thread_type:
official_review

<thread_object>
creator: reviewer_hylt

<content>
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.

strengths:
- The paper is well written and easy to follow. 
- Relational structures seem to provide a general unified framework that includes not only simplicial message passing but also other higher order structures. 
- 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.

questions:
- Is there a correspondence between the message passing graph introduced  by Bodnar et al. and the aggregated influence matrix introduced in Eq.6? 
- 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? 
- 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732173951299

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Common Response (Revision 1)

comment:
We thank all the reviewers for their evaluations and constructive feedback. We summarize the main updates to the manuscript below:

**Appendix D4: NeighborsMatch on trees and trees with attached cycles**

We benchmark trees and trees with attached cycles on NeighborsMatch to analyze the impact of topology on a prototypical example of oversquashing.

**Appendix D5: Real-World Benchmark - graph classification on ZINC (12K)**

We evaluate the impact of adding 40 edges to the graphs of the ZINC dataset (12K) and impact of ring lift on graph classification performance.

**Appendix D6: Real-World Benchmark - node classification on Cornell, Texas, Wisconsin, CiteSeer, and Cora**

We independently evaluate the impact of adding 40 edges to and pruning 40 edges from the graphs of real world dataset on on node classification performance.

**Appendix D7: Ablation test on the impact of network width and depth, and number of rewiring iterations**

We perform ablation tests to assess the influence of network width, depth, and the number of rewiring iterations on oversquashing and model performance.

**Appendix D8: Simplex pruning**

We describe how to incorporate edge pruning into our framework and report experiments on the impact of pruning edges from the MUTAG dataset on graph classification performance.

**Appendix H: Worked out example - relational structure and influence graph for a path graph**

We provide a detailed worked example illustrating the construction of the relational structure and influence graph for a simple path graph to clarify the definitions introduced in the manuscript.

**Appendix I: Computational complexity analysis**

We add a computational complexity analysis to explicitly discuss the trade-offs of the proposed methods in terms of relations, arity, and the size of the underlying structures.

Due to the limited duration of the discussion period and available computational resources, the new experiments were carried out on a limited scope and without tuning the rewiring hyperparameters. In the final version, we will expand the experimental settings and descriptions of the new experiments, and tune the rewiring (incl. pruning) hyperparameters.

All modifications or updates in the manuscript taking care of the reviewer suggestions are highlighted in purple.

Kindly let us know if you have any further questions or suggestions. We welcome and value your comments and feedback!
</content>
</thread_object>

</thread>
<thread>
creation date:
1732501688618

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
Dear Reviewers,

As the author-reviewer discussion period is ending soon, we kindly ask if you could review our responses to your comments. If you have further questions or comments, we will do our best to address them before the discussion period ends. If our responses have resolved your concerns, we would greatly appreciate it if you could update your evaluation of our work accordingly.

Thank you once again for your valuable time and thoughtful feedback.

Best regards,

The Authors
</content>
</thread_object>

</thread>
<thread>
creation date:
1740513876657

thread_type:
public_comment

<thread_object>
creator: ~diaaeldin_taha1

<content>
title:
Camera-Ready Revision

comment:
Dear Reviewers and Chairs,

We sincerely appreciate your valuable feedback and careful review of our work. Since the rebuttal, we have expanded the experiments in Sections 5.1 and 5.2, as well as Appendices D4, D6, D7, D8, and E1. We have now uploaded the camera-ready version of the manuscript.

Looking forward to seeing you in Singapore!

The Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper unifies theoretical work on over-squashing in graph neural networks and more general topological message-passing algorithms. All reviews for this paper are positive,. The reviewers felt that the paper was well-presented overall and that the theoretical contributions were interesting and helped provide a good starting point for understanding over squashing in topological deep learning. The reviewers felt that the experimental results were limited, and the authors did address this concern by adding more experiments during the rebuttal. But ultimately the reviewers still did not feel that the strength of the paper lied in its empirical contributions.