Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a framework that adds in an extra GNN layer after the Attention layer of Transformer, which enables better quality modeling in graph data. In particular, the GNN layer learns a per-head transformation that imposes learnable filter coefficients, which demonstrates better performance than static filters coefficients.

main_review: The paper discusses augmenting the Transformer structure to better suit the nature of graph data modeling. My main concern is that the paper itself does not compose a coherent story of why the GNN layer should be effective and makes a difference as a whole.

## Pros
The paper provides a good way to interleave GNN and Attention layers. Compared to simply injecting graph structures into positional embeddings, this method gives a novel way to fuse benefits from both sides.

## Cons
* The descriptions and notations by the paper are preventing a coherent understanding. e.g. the superscript $h$ (e.g. $\alpha^h$) is used to represent the corresponding head number while superscript $l$ is used to represent the layer number. When combined with the output representation $x$, it would be unclear for a first-time reader to notice the meanings of $x^h$ and $x^l$ are different.
* The method itself is hard to be in the SOTA class. For example, in Table 1, even for SpecTRA+GCKN+3RW which is the best among 3/6 datasets, it can still not outperform the previous SAN-Sparse one on the remaining 3/6 datasets. Given its added complexity compared to SAN (they share most of the parts in the positional embedding scheme), it’s hard to justify its effectiveness.
* A fair Transformer comparison is needed. It would be beneficial to state the added number of parameters compared to the baseline Transformer. As in most cases that would induce larger model capacity.
* Minor:
  * The current draft itself can be more polished to be a qualified submission. There are some typos and unclear statements:
  * Equation (6) double `)` 
  * Equation (8) Missing $V$
  * 2 lines above Equation (11)$h^{th}$ -> $h$-th
  * Figure 3, it would be better to show unsmoothed filter frequencies for limited-point graphs (e.g. (a)).

summary_of_the_review: The proposed method gives a new way of enhancing Transformer models in the graph domain. However, the experiments are not sufficient to justify the efficacy of the new model given its added complexity.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a novel model called SpecTRA to optimize the performance of the transformer model on the graphs. This proposed model induces a spectral module into the original transformer architecture to enable it to decomposite graph spectrum and filter the frequency domain and thus leading to more useful information.
main_review: Strength:
1. This paper has clear motivation and goal; that is since the transformer model naturally gives diverse attention sub-spaces, which correspond to the multiple filters covering the spectrum of the graph. Under these settings, the goal of the model is then to learn the filter coefficients; this process also naturally provides interpretability.
2. This paper has solid theoretical proof.
3. The experiment is pretty comprehensive; it includes many models from recent years as baselines and the comparison is done on six different datasets under three different tasks.
4. Overall this paper is well organized where the authors clearly know what they are talking about.

Weakness:
1. From the experiment section we can see that the proposed model can do pretty well on some tasks while doing worse on other datasets. This variance in performance could suggest that the proposed model need certain prerequisite to be fully functional. More datasets are needed to fully test the functionality of this model.
2. The proposed model is usually combined with other modules to achieve the best performance while the base version of it is definitely not the best in comparison to other models. More ablation studies might be necessary to justify the role that the proposed model plays in the system.
summary_of_the_review: This paper proposes a model that tries to improve the performance on the transformer on graph structure data. The proposed model has pretty good motivation and reasonable theory support, with the performance being relatively good in comparison to other baselines on some tasks. Overall, this is a solid paper, but it might more experiments to justify the importance of the proposed model.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes SpecTRA to construct spectral filterings on top of vanilla multi-head self-attention networks to have coefficients for each input graph. Specifically, SpecTRA computes the filter coefficients from the attention weights of vanilla multi-head self-attention networks by defining a mapping function (i.e., Equation 9) from the attention space to the filter coefficient space.
main_review: + The paper is well-structured.

+ The paper lacks its motivation. I can understand the motivation for filtering graphs for GNNs (Gao et al., 2021), but adapting this existing motivation to argue that the transformer cannot effectively segregate the noise from the signal is not enough. Some recent models (Mialon et al., 2021; Kreuzer et al., 2021) and SpecTRA are only suitable for small-size graphs due to utilizing the self-attention networks on the whole input graph. However, it is worth noting that these recent models ignore Graph-BERT [1] and Graph-Transformer [2].  Both Graph-BERT and Graph-Transformer can work quite well for node and graph classification and can be adapted for large-size graphs as they employ the self-attention networks on neighbors to take the local structures into account, which the recent models (Mialon et al., 2021; Kreuzer et al., 2021) and SpecTRA are missed.

+ Furthermore, it is straightforward to directly adapt Equation 6 for H^h with the learnable parameter \alpha instead of computing \alpha from the attention weights in Equation 9. Equation 9 is the main contribution in SpecTRA, but why does SpecTRA need it? What is the motivation behind it? What are the results of directly adapting Equation 6 with the learnable \alpha?

+ Regarding Equation 10, x^h_i is the vector at node x_i in the h-th attention head obtained from Equation 9. Is x^h_i actually from Equation 8? Because if it is from Equation 9, it means that SpecTRA constructs GCNs on top of the vanilla multi-head self-attention networks, followed by spectral filterings. This makes a confusion as if it is correct, SpecTRA is an extension of Graph-Transformer with additional using spectral filterings inspired from Gao et al., (2021).

+ SpecTRA lacks novelty as it is incremental. The performance gains are marginal.

+ The obtained results mainly come from the existing positional encoding schemes (Kreuzer et al., 2021). Without the existing positional encoding schemes, SpecTRA-Base is outperformed by other existing models such as GIN. Therefore, the main contribution shown in Equation 9 is incompetent.

+ The paper misses the results of the closely related works Graph-BERT, Graph-Transformer.

+ Why are the GIN and GCN results on MUTAG and NCI reported in Table 1 different from the original paper?

[1] Graph-Bert: Only Attention is Needed for Learning Graph Representations. https://github.com/jwzhanggy/Graph-Bert

[2] Universal Graph Transformer Self-Attention Networks. https://github.com/daiquocnguyen/Graph-Transformer

summary_of_the_review: The paper lacks the motivation and the proposed model SpecTRA is incremental.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a model for graph representation learning based on a transformer and on two GNNs: a message-passing neural network that learns graph filter coefficients from the transformer's attention weights, and a spectral GCN with parameters given by these filters coefficients. This choice of architecture is motivated by the assumption that different filter shapes are necessary to discriminate the specific spectral components associated with different graphs.
main_review: Correctness: No correcteness concerns.

Technical novelty and significance: The idea that different filter shapes are necessary to discriminate the spectral components associated with different graphs makes sense, therefore, learning the filter coefficients of the GNN used to distinguish between these graphs is a compelling solution. However, other architectural choices are not as well motivated. For example, why do the authors learn the spectral GCN filter weights from the attention matrix of the transformer, which can have a completely different sparsity pattern than the input graph? Why not learn the filter weights from the graph itself, e.g., by using a GNN? What is the rationale behind this choice of architecture? 
Another technical concern relates to Theorem 4.1. While the authors claim that this theorem justifies the proposed architecture, it is not clear how. That smooth functions can be approximated by Chebyshev polynomials is a well-known result. Can the authors clarifiy which aspects or parts of their method are justified by Theorem 4.1? I recommend adding a more detailed discussion of the theorem's implications to Section 4.1. 

Empirical novelty and significance: One of the goals of the numerical results is to assess "the impact of recently proposed position encoding schemes on SpecTra". Yet, none of these position encoding schemes were proposed by the authors. Moreover, the numerical results are unconvincing. The proposed method achieves similar performance to the compared methods except for ZINC. Additionally, errors with three decimal digits are not statistically significant for averages over 4 runs.

Other comments:
- The abstract and the introduction are difficult to understand and do not give a clear picture of the paper's contributions.
- In the beginning of Section 4.1, the authors should specify how the node feature embeddings fed to transformer are obtained from the graph.
summary_of_the_review: The idea that different filter shapes are necessary to discriminate the spectral components associated with different graphs makes sense, therefore, learning the filter coefficients of the GNN used to distinguish between these graphs is a compelling solution. However, other architectural choices---such as learning the spectral GCN filter weights from the transformer's attention matrix---are not well motivated. Moreover, the numerical results are unconvincing.
review_title: null

Meta-review: This paper proposes a novel approach to include graph information into Transformers. Reviewers expressed concerns on 2 main issues -

1) The exact architecture proposed in the paper is not well motivated. In words of one of the reviewers 'I still do not understand why the authors learn the spectral GCN filter weights from the attention matrix of the transformer, which can have a completely different sparsity pattern than the input graph, instead of learning the filter weights from the graph itself, e.g., by using a GNN. '. Authors tried to provide an explanation in the response however I think it needs to be made much more rigorous for it to be well motivated.

2) The interplay between existing position encoding schemes and the proposed method. This point also confused couple of reviewers as the empirical results seem to be strongly influenced by the choices of position encoding. Authors, I think did a great job in addressing this concern by providing additional results during the response period. 

Given the weak experimental results and lack of clear motivations I think the paper is not currently ready for acceptance.
Decision: Reject