- Rating
- 3
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper aims to proove the suboptimality of graph transformers for graph denoising when compared to other operators such as graph spectral attention or the proposed graph convolutional attention (GCA) operator. Then experiment on the three frameworks to prove the theory.
Critical strengths
- the paper is clear
- easy to follow
- builds on prior theory
Critical weaknesses
-
propositions 1 and 2 are not self contained and one needs to look at the appendix to see their meaning.
-
Also hard to know what is the justificaiton for using the three classes directly in the loss, as they don't guarantee recovering A even if in some cases U is recovered one still needs the eigenvalues. Moreover, only the spectral and GCA may attempt that so the standard scores are already biased from start as it has no eigenvalue info from your definitition
-
Some inovation concern is that the whole model is adding filtering to the features before the attention layers? or is there something more we are missing?
-
lines 211-213 makes S equal to A but no motivation given?
-
lines 223-224 assume the leaned weights are diagonal which usually is not?
Questions for authors
Please wee weaknesses above
W1
We thank the reviewer for this comment. We believe the propositions are largely self-contained in the current presentation. Proposition 1 states the minimum loss achievable with standard attention scores and identifies the optimal score matrix as E[B]. Proposition 2 gives the corresponding result for spectral attention scores and identifies the optimal map as h⋆(Λ)=E[B∣Λ]. The proofs, of course, are provided in the appendix due to space constraints. That said, we are open to improving the exposition. It would be helpful if the reviewer could clarify which definitions or aspects of the propositions they find difficult to follow, so we can address the issue more directly.
W2
We thank the reviewer for asking about the motivation for these classes. We organize the analysis in two stages. In Section 2, we study how attention scores can denoise the eigenvalues while expressed in the noisy eigenbasis. In Section 3, we build on this score analysis and study the full attention map. We show that the softmax applied to the scores can further denoise the graph by removing noise from the eigenvectors. The three classes in Section 2 differ in how their scores can use the noisy eigenvalues. Standard attention has scores of the form UWQWK⊤U⊤, where WQ and WK do not depend on the noisy eigenvalues. Spectral attention replaces WQWK⊤ with an arbitrary matrix-valued function h(Λ) of the noisy spectrum. GCA further restricts this dependence to a pointwise function η(Λ), applying the same scalar function to each noisy eigenvalue. This last form can be implemented using graph filters. We do not expect each class to recover A on its own. In particular, the first class cannot in general recover the eigenvalues of A. It serves as a reference for measuring what is gained by using the noisy eigenvalues. The spectral class describes the most general dependence on them, and GCA shows how a graph filter can provide a practical form of that dependence. Section 3 then shows how the softmax builds on these scores to remove noise from the eigenvectors, complementing the eigenvalue denoising studied in Section 2.
W3
In GCA, graph filters form the query and key representations, replacing the learned linear projections used in standard attention. Their product forms the attention-score matrix, so the filtering determines how the scores depend on the noisy graph spectrum. Furthermore, on the theoretical side, the paper uses spectral analysis to explain why this change can help graph denoising. We show that standard attention scores learn an average spectral denoising rule across the training distribution, which can be suboptimal when graph spectra vary. Allowing the scores to depend on the noisy eigenvalues can reduce the denoising loss, and GCA provides a practical way to implement this dependence. Another key aspect of the paper is our analysis of the softmax, which shows that it can further denoise the graph by approximately projecting the noisy eigenvectors onto the clean eigenspace. To the best of our knowledge, this theoretical explanation of the denoising role of softmax is novel, and no similar analysis has appeared in prior work.
W4
The adjacency matrix A and the graph Laplacian L are standard choices for the graph shift operator S. We set S=A because the quantity being denoised is A itself, so its eigendecomposition gives a direct spectral representation of the target. This choice also keeps the theoretical analysis simple. We will add this motivation to the paper.
W5
We thank the reviewer for pointing out that Eq. (14) uses diagonal weights. In the theoretical construction, the input is the full eigenvector matrix U. We impose diagonal HQ(l) and HK(l) to filter each eigenmode independently. This isolates the spectral response of the filters and lets us show that polynomial graph filters can approximate pointwise functions of the eigenvalues. The diagonal restriction is used for this approximation argument. It is not an assumption that graph-convolution weights are generally diagonal. The practical GCAT model uses a more general parameterization. At each layer, it applies polynomial graph filters to the feature matrix X with full, non-diagonal learned weights. For example, with two filter taps, Q=XWQ,0+AˉXWQ,1, with an analogous expression for K. Thus, the theoretical construction shows how graph filters can implement pointwise spectral responses, while the practical model uses general graph-filtered queries and keys. We will make this distinction clear in the paper.
We would be happy to address any remaining concerns you may have. We kindly ask the reviewer to consider our responses, as well as the additional, more robust experimental results provided in the global comment.