Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes Specformer, a Transformer-based graph spectral filter that captures the magnitudes and relative dependencies of all Laplacian eigenvalues. Specformer is permutation equivariant and can perform non-local graph convolutions. Extensive experiments on the node-level and graph-level datasets demonstrate Specformer's promising performance.
strength_and_weaknesses: Strengths：

1)	The motivation for using self-attention in the spectral domain is clear and inspiring.

2)	The authors' theoretical comparisons of Specformer to Polynomial GNNs, MPNNs, and Graph Transformers indicate Specformer's flexibility and universality, which looks sound to me.

3)	Experiments demonstrate that Specformer can learn a flexible and expressive filter and outperform baselines on node-level and graph-level tasks, particularly on heterophilic graph datasets.

4)	This paper is well-written and easy to follow.

Weaknesses:

1)	The scalability of Specformer is seriously limited by its quadratic time complexity.

2)	It would be helpful to empirically compare Specformer with baselines in terms of time and space overhead, even as the Specformer's time complexity is theoretically analyzed.

3)	Some baseline experimental results are missing, and no explanation. For example, the results of the Graphormer on MolHIV and MolPCBA are not displayed in Table 3 but are reported in the Graphormer's paper.

4)	The experimental datasets are small and a bit old. Using large and latest datasets (such as ogbn-arxiv in OGB and Penn94 in LINKX [1]) may significantly enhance the paper's quality.

[1] Lim, Derek, et al. "Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods." In NeurIPS 2021.

clarity,_quality,_novelty_and_reproducibility: Clarity: The paper is overall reader-friendly. 

Quality and Novelty: This paper has a clear motivation, and the proposed method is marginally novel.

Reproducibility: There is no available code.

summary_of_the_review: The motivation of this paper is clear, and the proposed method is promising. However, Specformer's quadratic time complexity is a serious limitation, and the experimental results are incomplete since some baseline results are missing. Due to the negative aspects of this work, I am slightly inclined to recommend rejection, but I would encourage the authors to address some of the issues raised in the comments in the rebuttal.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a spectral graph filter via introducing transformer structure, the idea seems novel, but the following points need to be concerned and explained.

strength_and_weaknesses: 1. The author introduces some weaknesses for current spectral fitler, but the explaination is not convincing enough. 
1) At first, the authors propose -- "mapping a single eigenvalue to a single filtered value, thus
ignoring the global pattern of the spectrum", which means that the interaction among eigenvalues are lacked. However, how to understand the interaction among different eigenvalues (frequiences in Graph Signal Processing)? 
I think that this assumption should be supported via theoretical analysis. 
2) Secondly, the authors propose -- "these filters are often constructed based on some fixed-order polynomials, which have limited expressiveness and flexibility". 
In fact, the polynomials paradigm was proposed to avoid the huge cost of eigenvalue decomposition for calculating U of Laplacian matrix. 
However, the proposed model needs to calculate U, which introduces huge cost. In other words, we can also learn the fiter parameters based on other networks (without transformer) if we ignore the cost of eigenvalue decomposition. 
Thus I think the proposed model does not handle the trade-off between computation cost and expressiveness.
2. I also have some questions for the architecture of proposed model, includes,
1) How to understand the benifits of Eq.(2)-the EE form which encodes the eigenvalues? 
2) The proposed model needs to calculate all eigenvectors U and eigenvalues (O(n^3)), the complexity analysis is not true. 
clarity,_quality,_novelty_and_reproducibility: 
1. The author introduces some weaknesses for current spectral fitler, but the explaination is not convincing enough. 
1) At first, the authors propose -- "mapping a single eigenvalue to a single filtered value, thus
ignoring the global pattern of the spectrum", which means that the interaction among eigenvalues are lacked. However, how to understand the interaction among different eigenvalues (frequiences in Graph Signal Processing)? 
I think that this assumption should be supported via theoretical analysis. 
2) Secondly, the authors propose -- "these filters are often constructed based on some fixed-order polynomials, which have limited expressiveness and flexibility". 
In fact, the polynomials paradigm was proposed to avoid the huge cost of eigenvalue decomposition for calculating U of Laplacian matrix. 
However, the proposed model needs to calculate U, which introduces huge cost. In other words, we can also learn the fiter parameters based on other networks (without transformer) if we ignore the cost of eigenvalue decomposition. 
Thus I think the proposed model does not handle the trade-off between computation cost and expressiveness.
2. I also have some questions for the architecture of proposed model, includes,
1) How to understand the benifits of Eq.(2)-the EE form which encodes the eigenvalues? 
2) The proposed model needs to calculate all eigenvectors U and eigenvalues (O(n^3)), the complexity analysis is not true. 
summary_of_the_review: This paper proposes a spectral graph filter via introducing transformer structure, the idea seems novel, but the following points need to be concerned and explained. The author introduces some weaknesses for current spectral fitler, but the explaination is not convincing enough. How to understand the benifits of Eq.(2)-the EE form which encodes the eigenvalues? The proposed model needs to calculate all eigenvectors U and eigenvalues (O(n^3)), the complexity analysis is not true. More questions can been seen above.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, authors challenge a usual way of designing a spectral function with a dimensional-wise mapping on Graph diffusion. Based on this, authors pay more attention on the global pattern of the specturm rather than single eigenvalue and propose a learnable set2set spectral filter. Based on the new spectral filter, more powerful spectral graph neural network is built. In experiments, authors demonstrate the convincing result for the proposed method.
strength_and_weaknesses: Strength
1. The idea is novel because all of spectral GNNs only focus on the spectral filter on the single eigenvalues. And it is very easy to find the rationality, even if the whitening is used in images, we still need nxnxk convolution filter rather than nxnx1 convolution filter. Thus I believe the motivation is reasonable, and we all ignore this.
2. The proposed method also inspires me. Although it still has some drawbacks but still surprises me.
3. Comprehensive experiments are convincing in my opinion.

Weaknesses:
1. I am curious if the set2set filter is able to find some interesting patterns from a spatial perspective. Because existing experiments are so quantitive, is there any possibility of digging up some quantitative experiments to demonstrate what kind of pattern the proposed method is able to find and the scalar-based spectral filter cannot?
2. The computational complexity is quite high because of eigenvalues. So is it possible to explicitly use eigenvalues rather than implictly work on eigenvalues? Because I notice the experiments on small datasets. Although this method is promising, I still hope there is any possibility for a large-scale version.
clarity,_quality,_novelty_and_reproducibility: This paper is easy to follow and the clarity is good. Overall, the quality is good for an ICLR paper. The novelty is pretty good. No code is provided to evaluate reproducibility.
summary_of_the_review: This paper is very interesting, although there are some shortcomings in implementations. It opens an promising direction for GNN. I am optimistic about these issues. Thus I make the recommendation to accept.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper introduces Specformer, a novel Transformer-based architecture for node- and graph-level prediction tasks. A Specformer layer embeds structure (eigenvalues) and node features separately, and then combines the obtained representations using graph convolutions. The model performs self-attention in the spectral domain. Experiments on synthetic and real-world datasets show the effectiveness of the proposed method.
strength_and_weaknesses: 
Strengths
 - Simplicity. The idea is easy-to-follow. 
 - The paper introduces synthetic datasets for which it reports the approximation capability of Specformer.
 - Good performance. The proposed method yields good performance overall. For instance, it gets 0.066 MAE on the ZINC dataset.

Weaknesses
 - Limited evaluation setup. Despite the promising results, the paper lacks relevant benchmarks for node-level tasks and only considers molecular datasets (small graphs) for graph classification. 
 - It is unclear whether the computational overhead of the proposed method is significant or not, and how it compares to other GNNs. 
 - The paper provides limited theoretical insights about the proposed architecture.

clarity,_quality,_novelty_and_reproducibility: Regarding **clarity and quality**, I have a few concerns and questions:

- C1: There are some unclear statements in the paper. For instance: 
  - "spectral filters are often approximated via fixed order" , "this truncated approximation is less expressive". What do we want to approximate here? 
  - "The reason is that the spectrum of Squirrel is more difficult to learn" (Section 5.4). Isn't the spectrum only the multiset of eigenvalues?

- C2: What is $\hat{S}_i$ in Eq. (6)? Does the matrix $W_x$ change with $l$? If so, I would write explicitly for precision and clarity.

- C3: How is the MLP in Eq. (5) applied to size-varying graphs in graph-level tasks? The dimensionality of $S_m$ would change with the graph size.

- C4: The paper repeatedly mentions expressivity to motivate the proposal and the adoption of Transformers. How does the expressive power of the proposed method compare to other GNNs? What are the limitations of the proposed approach?

 - C5: Does the complexity analysis (paragraph on Page 5) account for the eigendecomposition? How does the training/test time of the proposed method compare to other GNNs? Is the Laplacian eigendecomposition pre-computed? Is it negligible?
 
 - C6: It is hard to observe some curves (e.g., ground truth) in Figure 2.  

 - C7: Experiments on graph-level tasks only consider molecular data. Is there any particular reason? The graphs in these datasets are rather small. Also, the paper does not consider very popular benchmarks for node classification from OGB. I am curious about the method's performance across graphs of very different sizes.

Regarding **originality**, to the best of my knowledge, the proposed architecture is somewhat novel. 

**Reproducibility**: Code is unavailable during the reviewing process. Thus, we can not check further details and correctness. Also, some details about training (e.g., optimizer) and model selection are missing.
summary_of_the_review: Overall, the paper is relatively well-written and introduces a promising architecture for node- and graph-level prediction tasks. I have raised some concerns regarding the significance of the empirical evaluation, the computational cost/scalability, reproducibility, and clarity. Also, the paper provides limited theoretical insights about the proposed architecture, and the motivation behind some model choices is unclear/ not strong. Therefore, I am ranking this paper as marginally below the acceptance threshold.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper proposes to use a set to set transformer architecture over eigenvalues of graph Laplacian to learn more expressive spectral filters. Compared to the polynomial parameterization used in classical spectral GNNs such as Chebynet, transformer over eigenvalue set can model their dependencies and can approximate wider filter functions, especically considering that polynomial functions cannot handle multiple eigenvalues and must give them the same filtering (even they represent different frequencies). It is a pity that the authors did not point it out in their analysis and motivation. Nevertheless, the expressivity is at the cost of doing eigenvalue decomposition, which is impossible for large networks. So a cutoff of largest and smallest K eigenvalues are used for large networks. 

I want the authors know that this is identified as a borderline paper and a reviewer-AC meeting is conducted to discuss the paper. Through the discussion, both reviewers and I agree that the motivation of using transformer makes much sense (though the authors did not fully reveal where the additional expressivity comes from compared to polynomial GNNs) and the experimental results are impressive (both ZINC and Squirrel are new SoTA). To verify the results, one reviewer and I volunteered to reproduce the results using the submitted code. The reviewer reported that with some effort, they successfully reproduced the ZINC results with 0.0678 MAE in 500 epochs (the original takes 1000 epochs). However, on my side, the node-level code provided by the authors cannot run. There is no README, no preprocessed data, no script for preprocessing datasets other than arxiv and Penn, and no comments or direction in the jupyter notebook. I believe for papers with such significant results, a reproducibility check is a must. However, the submitted code seems not in a fully runnable state.

Considering all above, I still believe that the strengths outweigh the weaknesses. This paper can inspire new ways to design spectral GNNs and has impressive empirical results. So I recommend an accept but strongly encourage the authors to polish and complement the code and ensure the reproducibility of the experiments.
justification_for_why_not_higher_score: This paper presents some very impressive results. However, the results are not fully reproducible with the submitted code.
Decision: Accept: poster