Spatio-Spectral Graph Neural Networks

Summary

The authors are proposing Spatio-Spectral Graph Neural Networks ($S^2GNNs$), a hybrid model that combines (Spatial) Message Passing Neural Networks (MPNNs) and Spectral Graph Neural Networks. The authors argue that, by combining message-passing with spectral filters, the model can better model both local and global information, alleviating phenomena such as over-squashing and under-reaching. The authors discuss the design space of their proposed method and showcase a technique for obtaining position encodings that can make their model more expressive than the 1-WL test. The authors perform multiple experiments on both synthetic and real-world datasets.

Strengths

- The paper is well-written, and the figures and tables are aesthetically pleasing. - The tackled problem is well-motivated. - The method is relatively easy to comprehend. The idea is simple and elegant, yet it has very strong empirical results. - The proposed $S^2 GNN$ is analyzed very well. Including mechanistic in-context learning experiments is very interesting in the context of long-range modeling on graphs. Moreover, the connections between $S^2 GNNs$ and SSMs that the authors make are insightful and could be very interesting to some readers. - The empirical results on the Peptides datasets are very good. $S^2 GNNs$ obtain state-of-the-art results on peptides-func *without* using Position Encodings, which is very hard to accomplish even with models that consider the graph as being complete (such as Graph Transformers). Moreover, the proposed method uses significantly fewer parameters than other competing models. - The theoretical analysis is well thought out. The authors also make some remarks about the advantages of having spectral filters, and they provide some very useful intuitions that connect them to using virtual nodes (Fig 3, Fig 4). - The authors introduce two new datasets - a long-range clustering dataset (\textsc{LR-CLUSTER}) and a long-range regression dataset that is then used to make several observations about their model - such as the ability to solve long-range tasks and the alignment between the clusters and the learned spectral filters. - The authors also propose a way of obtaining some Laplacian Position Encodings that improve the overall performance and make their model more expressive than the 1-WL test. - The paper contains an extensive amount of supplementary materials detailing other experiments and proofs for the theoretical results.

Weaknesses

- The paper's main weaknesses are that the main text is somewhat unfocused, and some related work is not mentioned. I will detail in the following: - While the authors generally do a very good job of providing valuable theoretical insights regarding their design choices, I would argue that some of them are unnecessary and distract the reader from the main points of the paper. For instance, I believe the discussion about "high-resolution filters for low frequencies" from lines 149-167 to be somewhat hand-wavy and distracting, especially the remark that "as graph problems discretize continuous phenomena, stability to the graph perturbations is a strong domain-agnostic prior". While I don't think that the discussion is bad, I feel that the supplementary materials would be a much better place in which to include it. - I believe that Subsection 3.3 (Parametrizing Spectral Filters) is somewhat confusing, especially for a reader who is not very familiar with spectral methods. I did not initially understand the discussion about the window (Lines 247-253), and I believe it should contain more context. The authors should either expand the section or move it to the supplementary materials. - The proposed positional encodings are a nice addition, but similar laplacian positional encodings, such as [[1]], have not been discussed as related work. Other works, such as [[2]], are cited in the paper but not in the context of the laplacian positional encodings that they propose. - Some other recent methods deal with long-range relationships on graphs and have not been discussed in the related work. Notably, GRED [[3]] uses Linear Recurrent Units to model distant relationships with a mechanism similar to k-hop MPNNs and also draws inspiration from SSMs; AMP [[4]] has a message filtering mechanism and is adaptively increasing the number of layers depending on the dataset; NBA [[5]] is passing messages in a non-backtracking manner, obtaining a slightly better score than $S^2 GCN$ on *peptides-struct* ($0.2424$ v.s. $0.2447$), and PR-MPNN [[6]] rewires graphs adaptively by learning a probability distribution for the adjacency matrices. - The authors mention on line 69 that the runtime of their method is equivalent to that of an MPNN, but I could not find a table containing a direct comparison. It would be great if this were included somewhere. There are training times on page 35, Table 6, but no comparison with a simple MPNN (such as a GCN or a GIN model). Overall, I believe that the paper is very strong. The model is conceptually simple but contains novel ideas. The empirical results are very good, and the authors test their method on many different scenarios. I found the mechanistic in-context learning experiments to be particularly interesting. I believe the work could have a considerable impact on how we design GNN architectures going forward. As stated previously, the main weakness is that the paper feels somewhat unfocused, and some important related work is omitted. This is a somewhat strange complaint to have, but I feel that the scope of the paper is very broad. In my opinion, the overall style of the paper would be better suited for a journal submission if some details from the appendix were moved into the main text. For a conference with more limited space, I would advise the authors to move some of the more in-depth details to the appendix. This is in no way an argument for rejection, I just believe that the paper would be a lot nicer to read if it didn't contain these details in the main text. I recommend a 7 (Accept), but I will update my score to an 8 (Strong Accept) if the authors expand their related work discussion and provide more details for Subsection 3.3. I would also recommend to the authors that they move some of the details from Section 3 to the Appendix, but not doing so will not affect my final score. [1]: https://arxiv.org/abs/2110.07875 [2]: https://arxiv.org/pdf/2012.09699 [3]: https://arxiv.org/pdf/2312.01538 [4]: https://arxiv.org/pdf/2312.16560 [5]: https://arxiv.org/pdf/2310.07430 [6]: https://arxiv.org/abs/2310.02156

Questions

- In the graph rewiring literature, the models are often benchmarked on other graph-level datasets (such as QM9, Zinc, or the TUDataset collection). Did the authors try their method on these datasets? I am not requesting these experiments, but they would be a nice addition. - The Long-Range Graph Benchmark also contains COCO-SP, PascalVOC-SP, and PCQM-Contact. Did the authors try to benchmark their models on these datasets? I'm personally not a fan of COCO-SP and PascalVOC-SP because they're obtained from Computer Vision datasets, so the GNN inductive bias might not be appropriate for them. Still, PCQM-Contact is a molecular dataset, and it would be interesting to see some results on it.

Rating

8

Confidence

4

Soundness

4

Presentation

3

Contribution

4

Limitations

- The limitations are addressed in the appendix.

Summary

This paper proposes Spatio-Spectral Graph Neural Networks (S²GNNs) to address the limitations of ℓ-step Spatial Message Passing Graph Neural Networks (MPGNNs), such as limited receptive fields and over-squashing. S²GNNs combine spatial and spectral graph filters for efficient global information propagation, offering tighter error bounds and greater expressiveness than MPGNNs. They outperform traditional MPGNNs, graph transformers, and graph rewirings on benchmarks and scale efficiently to millions of nodes.

Strengths

1. Combining spectral and spatial methods is interesting. The proposed method can overcome many problems associated with MPNNs. 2. The theoretical proofs in this paper are sufficient and, in my opinion, sound. 3. This paper offers a lot of intuitive analysis, with examples that help readers understand the concepts. 4. S²GNN performs excellently in multiple tasks and can be extended to various applications. It also demonstrates scalability, running efficiently on graphs with millions of nodes.

Weaknesses

1. This paper's writing and structure can be further improved. Adding descriptions to the notation and including pseudocode would enhance readability. 2. The experiment includes too few baselines. For instance, only GAT and GCN are used as baselines in Tables 3 and 4, while some of the latest methods, such as SpecFormer, which also uses Eigenvector, are not considered.

Questions

1. Please refer to the weaknesses mentioned above. 2. What is the upper bound of the graph size that the EVD used in S²GNN can support? For example, can it handle graphs with billions of nodes, such as papers100m? 3. In real tasks, are the eigenvectors $k$ sensitive to performance? For instance, on products and TPU graphs, would using a larger $k$ improve performance?

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

2

Limitations

The authors discussed limitations in the Appendix.

Summary

The paper presents Spatio-Spectral Graph Neural Networks (S$^2$GNNs), a novel paradigm that combines spatial and spectral parameters to overcome the limitations of $\ell$-step MPGNNs, notably their restricted receptive fields and over-squashing issues. S$^2$GNNs achieve global information propagation efficiently, surpassing MPGNNs in approximation accuracy, expressivity, and scalability, demonstrated through superior performance on various graph tasks and ability to handle large-scale datasets.

Strengths

1. The paper presents a rigorous theoretical basis and comprehensive analysis, reinforcing the validity of the proposed approach. 2. The proposed method is straightforward and practical, with the added advantage of being easily integrable into a wide range of existing GNN models. 3. The method has been extensively tested across various backbones and datasets of differing types and sizes, demonstrating its robustness and versatility.

Weaknesses

1. **Deficiency in Ablation Studies for Embedding Updates**: Eq.~(1) within the paper that updates to the latent embeddings are achieved through the summation of spectral and spatial layers. This method warrants a broader range of ablation studies, such as exploring concatenation, normalization, or adopting a randomized approach to select between spectral or spatial optimizations like [1], to validate the robustness and efficiency of these embeddings. 2. **Inadequate Comparative Analysis for Over-Squashing and Long-Range Interactions**: The paper's treatment of over-squashing and long-range interactions could be enhanced by incorporating comparative analyses with established methods. Notably, the GCNII[2], which utilizes skip connections and PageRank to facilitate up to 64 layers in a GNN, and methods based on random walks that intensify depth-first search capabilities for extended influence, should be examined. This inclusion would enhance the analysis and provide a more rigorous evaluation of the proposed model’s capabilities in handling long-range interactions. [1] Chang, Heng, et al. "Not all low-pass filters are robust in graph convolutional networks." Advances in Neural Information Processing Systems 34 (2021): 25058-25071. [2] Chen, Ming, et al. "Simple and deep graph convolutional networks." International conference on machine learning. PMLR, 2020.

Questions

See above

Rating

6

Confidence

5

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Summary

The proposed method Spatio-Spectral Graph Neural Networks (S2GNNs) combine the spectral GCN and spatial GCNs embeddings linearly. The paper considers a deep dive into spectral filter properties and attempt to motivate the combination with spatial filtering. There are well known results repeated in the method section, which could have been part of background. Also, the contribution towards directed graphs is not clear.

Strengths

1. The paper considers a deep dive into spectral filter properties and attempt to motivate the combination of spectral filters with spatial filtering. 2. The linear combination of spectral and spatial embeddings is new.

Weaknesses

1. There are well known results repeated in the method section. For example, it is established that the spectral filters are permutation equivariant, Locality relates to spectral smoothness. 2. The paper sometimes fails to connect the dots. For example, MPNNs (spatial) suffer from oversquashing, but at the same time spectral GNNs can handle oversquashing issue. So why do we need to combine them both? Its not clear in Introduction. 3. Contribution towards the directed graphs is unclear, any spectral filters can be adapted to directed graphs via magnetic Laplacian. The main point of the paper is to demonstrate the superiority against existing methods for undirected settings first.

Questions

GNNs aim to learn data driven filters. “Ideal” filters may NOT be a “good” choice always. Then what is the need of implementing an ideal discontinuous spectral filter discussed in Section 3.2? In the experiments, did you take the directionality into account in S2GNN? If, yes what is the performance of S2GNN without directionality?

Rating

5

Confidence

3

Soundness

2

Presentation

2

Contribution

2

Limitations

n/a

Conclusion of Discussion Period

Dear AC, dear Reviewers, We greatly appreciate the discussion of our work and we cherish the feedback! In our view, the presented paper makes profound technical contributions and accordingly contains an above-average amount of content (see next paragraph). We made the conscious decision not to withhold any significant contribution from the main body and thus make sure that our work is reviewed in its entirety. While this enforces a more compact writing style, we would like to highlight that, indeed, none of the presented aspects was deemed unnecessary by the reviewers. Instead, reviewers EZD5, H69b, and rAa9 uniformly acknowledged our theoretical foundations/analysis of our Spatio-Spectral Graph Neural Networks (S$^2$GNNs), along with our method's general applicability and strong empirical results. We are moreover certain that the 11% extra space in the camera-ready version will suffice for the discussed adjustments to increase explicitness and, hence, address all the changes suggested by the reviewers. Arguably, in comparison to impactful works like ChebNet [1] or GCN [2], our technical contributions are of much greater scope. In essence, ChebNet [1] made the Chebyshev-polynomial coefficients of [4] learnable, GCN [2] uses a fixed parametrization again but stacks multiple layers interleaved with non-linearities. Instead, we provide a new modeling paradigm rooted in approximation theory and signal processing that goes beyond pure recursive neighborhood aggregations and unlocks new design spaces. We appreciate further feedback that would benefit our work. [1] Defferrard et al. "Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering" (2016) [2] Kipf & Welling "Semi-Supervised Classification with Graph Convolutional Networks" (2017) [3] Veličković et al. "Graph Attention Networks" (2017) [4] Hammond et al. "Wavelets on Graphs via Spectral Graph Theory" (2009)