S4G: Breaking the Bottleneck on Graphs with Structured State Spaces

We are grateful for the valuable feedback and encouraging comments received regarding our paper. Below, we offer detailed responses to address your inquiries.

(Weakness) The calculation of $\bar{K}$ could be expensive and requires preprocessing for efficient training. A discussion on how much time is needed to preprocess for different datasets could make the results stronger.

Following your suggestion, we report the pre-processing time for all datasets as follows.

Dear Reviewer qfiX, as the discussion period comes to a close, we would like to thank you once again for your positive assessment. Your support and inspirational comments have been invaluable to us. We remain open and eager to incorporate any further feedback or insights you might offer.

We appreciate your thorough feedback and insightful inquiries. After careful consideration of your critique, we are committed to addressing your concerns and presenting arguments that justify a higher score for the paper.

Before responding to your questions one by one, we would like to express our gratitude for mentioning SPN [1]. This work has a solid theoretical foundation and empirical analysis, and it addresses the issues encountered by multi-hop MPNN to a great extent, specifically the dependency on the power of the adjacency matrix, using a simple yet effective method. In our updated submission (please refer to the red-colored text), we introduce the works [1,2] you mentioned in our Introduction (paragraph 2 in Section 1). Furthermore, in the experimental part, we introduce SPN as a baseline (paragraph 1 in Section 4.2 and Section 4.3). We conducted experiments on both long-range and general datasets for SPN, and the results are presented in Table 2 and Table 3.

(Weakness 1) Scholarship: The paper fails to present a good coverage of the related work which also makes the contributions questionable. This is particularly the case with the coverage of recent multi-hop approaches. Authors mention that multi-hop models do not help with e.g. over-squashing as they rely on taking the powers of the adjacency matrix which amplifies the over-squashing problem. This is true, but this is exactly the reason why other multi-hop approaches have been studied extensively, see e.g. [1], where the idea is to directly aggregate information from higher-order neighbours obtained using shortest path distances (a sensitivity analysis is also conducted).

Thank you for mentioning SPN, which will enrich our related works. In our updated submission (please refer to the red-colored text), we introduced and cited SPN in the Introduction (paragraph 2 in Section 1). In the experimental section, we used SPN as a baseline and conducted experiments on long-range and general datasets (paragraph 1 in Section 4.2 and Section 4.3). The experimental results are presented in Table 2 and Table 3.

Dear Reviewer rkT5, as the discussion period draws to a close, we would like to verify if our responses adequately address your inquiries. In light of what you've mentioned, we introduced [1,2] in our paper and conducted experiments for [1]. Additionally, we discussed the difference between our model and SPN [1] in detail. All the other questions received a direct response as well. We greatly appreciate your valuable feedback and recommendations to enhance our paper. We eagerly await your response.

[1] Shortest Path Networks for Graph Property Prediction, LoG 2022

[2] Do Transformers Really Perform Badly for Graph Representation? NeurIPS 2021

Thank you for your detailed comments and valuable questions. We have carefully considered your criticism and aim to persuade you that the paper deserves a higher score by addressing your concerns.

(Weakness 1) Over-smoothing and over-squashing: The paper claims that the proposed model can address both over-smoothing and over-squashing. However, over-smoothing is caused by the lack of local neighborhood information. S4 aims to better capture distant information, which seems to be in the opposite direction of addressing over-smoothing. The experiments didn’t touch over-smoothing either.

• Our paper mentions the over-smoothing problem, but the focus of this paper is on the over-squashing and long-range problems (as emphasized in our title, abstract, and conclusion). The over-smoothing problem has been largely addressed in previous works, so we did not design experiments for it.

• S4G is not on the opposite side of over-smoothing: S4G encodes neighbors from low to high order into a sequence. Based on the memory capacity of the HiPPO framework [1], the model avoids forgetting local information, thus avoiding the over-smoothing problem. On the other hand, the main cause of the over-smoothing problem is that MPNN is similar to Laplacian smoothing [2], which leads to multiple layers of MPNN degenerating into a low-pass filter on the graph [3]. S4G does not perform message passing on the original graph structure, so it can avoid such degeneration.

• It is worth noting that we have already used a 16-layer model on our tested CLUSTER dataset, a general node classification dataset. This indicates that the performance does not decrease with depth and avoids over-smoothing issues. To further alleviate your concerns, we tested the performance of S4G from 2 to 10 layers on another node classification dataset we tested, i.e., PATTERN. The results are as follows, the performance remains stable as the number of layers increases.

  # Layers	2	4	6	8	10
  S4G	$86.72 \pm 0.03$	$86.87 \pm 0.02$	$86.83 \pm 0.04$	$86.85 \pm 0.02$	$86.85 \pm 0.03$

(Weakness 2) Lack of expressiveness analysis: By converting a neighborhood into a sequence, the model considers the shortest distance, but would inevitably lose other structural information. E.g., the model doesn’t know the edges between hop $k-1$ and hop $k$, i.e., for a certain node at hop $k-1$ which nodes at hop $k$ are connected to it. This questions the expressiveness of the proposed model. Theoretical analysis is necessary to justify the expressiveness and support the empirical results, but it’s missing.

• Our paper did not focus on the expressivity problem, we did not aim to design a expressive GNN in this work. However, we mentioned it in the conclusion and already provided some analysis in Appendix B.

• Our model has stronger expressive power than MPNN. The following is a brief proof, and a comprehensive exploration of the expressive power of S4G will be part of future work.

  • The information captured by S4G is more abundant than MPNN: In MPNN, under each node's perspective, each message passing aggregating information from the first-order star-shaped graph [4]. By contrast, S4G not only aggregates information from first-order neighbors but also from higher-order neighbors. Therefore, S4G can obtain more abundant information.
  • There exists a pair of graphs that MPNN cannot distinguish but S4G could (this example is borrowed from [5]): Consider two uncolored graphs, G1 and G2, where G1 is a hexagon and G2 consists of two disconnected triangles. With the shortest path information encoded in the SSM kernel, S4G can differentiate between G1 and G2, while the 1-WL test cannot. Since the 1-WL test is the upper bound of the expressive power of MPNN, MPNN also cannot distinguish them.

Dear Reviewer SDke, as the discussion period ends soon, we would like to check whether our responses answer your questions. Following your comments, we conducted experiments to test the model's performance when the number of layers increases. Additionally, we provided a brief proof for the expressivity of S4G. All the other questions received a direct response as well. Thank you again for your comments and suggestions to improve our paper, and we look forward to your reply.

Dear Reviewer SDke, thank you for your response. It is important to emphasize that our research does not specifically delve into the expressive power of GNNs. The investigation into GNN expressive power stands as an orthogonal research direction to our focus. Our primary focus centers around addressing challenges related to long-range interactions (LRI) and over-squashing on graphs. Discussing the expressive power of S4G at length would deviate from our research question. As evidence, existing works that focus on the over-squashing issue and LRI, such as [1,2,3,4], have also not discussed the issue of expressive power in depth, work [1,2] are theoretical works, while [3,4] design models. Nevertheless, our response already demonstrates that our model is more powerful compared to MPNNs.

[1] Understanding over-squashing and bottlenecks on graphs via curvature, ICLR 2022

[2] On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology, ICML 2023

[3] Drew: Dynamically rewired message passing with delay, ICML 2023

[4] Exphormer: Sparse transformers for graphs, ICML 2023

Thank you for further clarification! However, my major concern, i.e., theoretical analysis of expressiveness which is necessary for a sequential model over graph-structured data, is not addressed. Therefore, I still don't recommend acceptance.