- Rating
- 4(+2)
- Confidence
- 4
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This theoretical paper provides a conceptually coherent explanation of why graph transformers may extract more informative features than fixed graph convolutions. Its main contribution lies in integrating exact attention decompositions, implementations based on fixed graph convolutions, an optimization perspective, and a reconstruction-risk comparison into a unified theoretical framework. The exact masked-softmax expansion and the connection between expressivity and reconstruction risk are particularly interesting. The paper is clearly presented and well organized, with good readability throughout. Overall, the theoretical results provide valuable insights into the feature extraction capabilities of graph transformers.
Critical strengths
S1: The paper focuses on an important explanatory question rather than only reporting another architectural improvement.
S2: The distinction between fixed graph filters and feature-dependent attention is made constructive through explicit operator expansions and a containment result.
S3: The exact softmax multi-index expansion and the shared-basis risk calculation are technically interesting components with potential use beyond this paper.
S4: The authors provide experimental studies to validate the theoretical insights. The numerical results demonstrate interesting findings that are generally consistent with the theoretical analysis, further supporting the main claims of the paper.
Critical weaknesses
W1: Theorem 4 chooses its spectra and, in Corollary 3, its basis using the clean signal. This is a meaningful oracle benchmark, but it leaves open how one would approach it from noisy observations.
W2: The reconstruction-risk result is a useful oracle comparison, but the contribution statement should identify it consistently and state the condition under which the adaptive shared-basis class improves strictly over the fixed filter.
W3: Corollaries 1–2 compare representable filters or reachable reconstructions. For the infimum comparison to follow, the two models seems should share the relevant initialization and constraints.
Questions for authors
Q1: What is the consequence of the exact masked-softmax expansion beyond rewriting the attention operator?
Q2: Under what condition is the shared-basis improvement over the fixed filter strict?
Q3: Which architecture is covered by the proximal theorem?
Q4: What objective, if any, is optimized when the attention-induced dictionary changes across layers?
Q5: Could the authors clarify whether the infimum comparison requires the two models to share the parameter setting, with one admissible family contained in the other?
3 comments
The authors’ reply cleared up my concerns, so I’ve raised my score.
Thank you for your final assessment
We thank the reviewer for the positive final assessment and for recognizing the soundness, informativeness, and key strengths of our work. Your previous comments and suggestions have helped us further improve the clarity of the manuscript.
We thank the reviewer for recognizing the importance of explaining feature extraction, the constructive connection between fixed filters and attention, and the technical value of the masked-softmax expansion and spectral risk calculation. We understand the main concerns to be the clean-signal dependence of the oracle, the conditions in theories, and the the scope of the proximal architecture. The revision makes the population-oracle interpretation explicit, separates spectral-weight and basis gains, and specifies the shared coding ingredients and stagewise construction. These changes address the scope and comparison concerns. Detailed point-by-point responses follow.
Response to Weakness 1: Theorem 4 now formulates a population oracle: the optimal filter depends on $ B=\mathbb{E}[X^\star(X^\star)^\top] $ and the noise variance. The paragraph after Theorem 4 explicitly identifies learning this filter as a separate estimation and optimization problem, and the conclusion retains finite-data learning as future work. A possible route, beyond the proved results, is to estimate the signal second moment from independent noisy training samples on the same node set. One could use the estimated eigenvectors and filter weights on evaluation data. This is a possible plug-in construction. Unknown noise variance introduces an additional estimation problem.
Response to Weakness 2: The contribution statement now identifies an attainable population symmetric-oracle advantage, and the conclusion uses the same oracle interpretation. Revised Theorem 4 specifies the distributional assumptions. Corollary 3 separates spectral-weight and basis improvements. For the shared graph basis H, with ai=H:,i⊤BH:,i and c=dσ2>0, strict improvement holds exactly when
∃i:αai=cλi2.
This follows from the sum of nonnegative squares in Eq. (6). A basis change can add further improvement.
Response to Weakness 3: We agree. The paragraph before Corollary 2 now requires the same network setting including the architectures, the input feature matrix, nonlinearity, depth, and parameter constraints with the only difference being the filters used.
Response to Question 1: The expansion identifies which neighborhood information contributes to the output. The key–value statistics
Ci,ν=∑j∈Nihkν(xj)Vxj
are combined with query coefficients hqν(xi)/(ν!Zi). This separates the roles of the mask, keys, queries, and row normalization, and explains how attention can distinguish neighborhoods with the same uniform mean but different higher-order statistics. The revision also adds a finite-order approximation bound in Appendix A.2: numerator truncation at degree R has per-node error O(BR+1/(R+1)!).
Response to Question 2: Lemma 1 and Corollary 3 give the exact shared-basis improvement
ΔH:=E[ℓ(ZA)]−minθ∈RNE[ℓ(ZHDiag(θ)H⊤)]=∑i=1N(λi2+α)2(ai+c)(αai−cλi2)2.
All denominators are positive. Therefore
ΔH>0⟺∃i: λi2=cαai.
Response to Question 3: The revised Theorem 3 covers an explicitly constructed reconstruction network. One block performs a proximal gradient step. It requires propagation by D, formation of the data residual Y−DZ, propagation by D⊤, a residual connection, and columnwise group shrinkage. The GT implementation uses linearized attention with one-hot node identifiers, identity value maps on the signal channels, and positional query/key parameters representing D and D⊤.
Response to Question 4: In the revised theorem, the dictionary changes between stages, while remaining fixed within each stage. Stage 1 minimizes JD1(⋅;XV⊤). Stage 2 minimizes JD2(⋅;M2), with M2 the completed first-stage output. Appendix A.4 proves descent within each stage and convergence to the composition Z2⋆(Z1⋆) as both stage depths grow. It does not assert that the whole cascade minimizes one common objective.
Response to Question 5: Yes: the comparison requires containment of admissible operators with the coding ingredients matched. It does not require the two architectures to have identical parameter vectors. Given a GCN propagation filter D, Corollary 1 constructs attention parameters realizing D; swapping query and key parameters realizes D⊤. Matching the input, network architecture, nonlinear activation, penalty and depth then reproduces the same output by induction over blocks. Therefore the inclusion is asserted for a GT family.