acceptodds
Under review as a conference paper at ICLR 2027

Feature Extraction Advantage of Graph Transformers: Primal-Dual Decomposition and Reconstruction-Risk Analysis

Abstract

Graph Transformers (GTs) replace fixed topology-driven aggregation with feature-adaptive attention, yet the source of their feature-extraction advantage remains unclear. In particular, how this adaptivity produces discriminative representations and measurable reconstruction benefits is not understood. This paper develops a unified framework connecting primal–dual decomposition, unrolled sparse coding, and reconstruction-risk analysis. We first prove that linearized GT attention admits an exact finite decomposition: key-induced primal atoms analyze the input, while query-induced dual atoms synthesize the output from the resulting projection coefficients. We extend this viewpoint to masked softmax attention through an exact normalized exponential-kernel expansion. We then show that removing feature dependence from the query–key coordinates reduces attention to a fixed linear graph filter, with GCN and spectral graph convolution arising as topology-driven special cases. This identifies the boundary between adaptive attention and fixed aggregation. Motivated by the decomposition, we interpret a deep GT as an unrolled proximal-gradient solver for an -regularized coding problem: attention generates an adaptive dictionary, and successive layers perform residual correction and group-sparse coefficient refinement. Finally, using a ridge surrogate, we derive explicit lower bounds on the reconstruction-risk advantage of adaptive GT-inspired filters over fixed GCN filters. The shared-basis specialization isolates spectral adaptivity by allowing the two filter families to differ only through their spectral weights. Controlled experiments verify the decompositions and the degeneration to fixed filtering, and show that adaptive attention improves class discriminability and lowers reconstruction risk relative to fixed topology-driven aggregation.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Graph transformers, primal-dual decomposition, graph convolutional networks, reconstruction risk

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.20 over 5 reviews, above 96% of the others.
Reviewer_sgGdOpenReview ↗
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

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 HH, with ai=H:,i⊤BH:,ia_i=H_{:,i}^\top BH_{:,i} and c=dσ2>0c=d\sigma^2>0, strict improvement holds exactly when

∃i:αai≠cλi2.\exists i:\quad \alpha a_i\ne c\lambda_i^2.

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)VxjC_{i,\nu}=\sum_{j\in\mathcal N_i}h_k^\nu(x_j)Vx_j

are combined with query coefficients hqν(xi)/(ν!Zi)h_q^\nu(x_i)/(\nu!Z_i). 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 RR has per-node error O(BR+1/(R+1)!)O( B^{R+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(αai−cλi2)2(λi2+α)2(ai+c).\Delta_H :=\mathbb E[\ell(Z_A)]- \min_{\theta\in\mathbb R^N}\mathbb E[\ell(Z_{H\operatorname{Diag}(\theta)H^\top})] =\sum_{i=1}^N\frac{(\alpha a_i-c\lambda_i^2)^2}{(\lambda_i^2+\alpha)^2(a_i+c)}.

All denominators are positive. Therefore

ΔH>0⟺∃i: λi2≠αaic.\Delta_H>0\quad\Longleftrightarrow\quad \exists i:\ \lambda_i^2\ne\frac{\alpha a_i}{c}.

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 DD, formation of the data residual Y−DZY-DZ, propagation by D⊤D^\top, 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 DD and D⊤D^\top.

Response to Question 4: In the revised theorem, the dictionary changes between stages, while remaining fixed within each stage. Stage 1 minimizes JD1(⋅;XV⊤)\mathcal J_{D_1}(\cdot;XV^\top). Stage 2 minimizes JD2(⋅;M2)\mathcal J_{D_2}(\cdot;M_2), with M2M_2 the completed first-stage output. Appendix A.4 proves descent within each stage and convergence to the composition Z2⋆(Z1⋆)Z_2^\star(Z_1^\star) 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 DD, Corollary 1 constructs attention parameters realizing DD; swapping query and key parameters realizes D⊤D^\top. 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.

The authors’ reply cleared up my concerns, so I’ve raised my score.

AuthorsOpenReview ↗

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.

Reviewer_8nxPOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper aims to provide a theoretical explanation for the feature-extraction advantage of Graph Transformers (GTs) over Graph Convolutional Networks (GCNs), focusing on feature-adaptive attention as opposed to fixed topology-driven aggregation. The authors claim that the feature adaptivity of GTs allows them to extract more informative and discriminative representations compared to fixed graph convolution. They provide a theoretical characterization of attention as a feature analysis and reconstruction process, and show that fixed graph convolution can be recovered as a restricted case of GT attention The authors support their theoretical findings through controlled synthetic experiments, demonstrating that feature-adaptive filtering improves class discriminability and that greater spectral flexibility can reduce reconstruction error. Overall, the paper presents a unified theoretical perspective on how adaptive attention can provide greater flexibility in feature extraction and reconstruction compared to topology-driven graph aggregation.

Critical strengths

1)The paper provides a coherent theoretical perspective connecting attention decomposition, sparse representation learning, and reconstruction-risk analysis` 2)The paper derives explicit theoretical bounds characterizing the potential reconstruction advantage of adaptive graph filters over fixed graph convolution. This is a meaningful extension beyond qualitative expressivity arguments, as it relates the benefits of adaptivity to the spectral properties of the underlying signal and graph filters.

Critical weaknesses

While the synthetic experiments support the proposed mathematical characterizations, they provide limited evidence of their broader implications for feature extraction. In particular, Experiment 3 demonstrates the benefit of an expanded filter family, but its non negative reconstruction-risk advantage is guaranteed by construction. Additional experiments testing the theoretical predictions under more varied conditions would strengthen the contribution.

Questions for authors

As mentioned in the weaknesses section, could the authors provide additional experimental evidence demonstrating the broader significance of their theoretical findings? In particular, could they evaluate the tightness of the reconstruction-risk bounds and investigate whether the observed improvements persist under more varied graph and signal conditions,?

3 comments

We thank the reviewer for the constructive assessment, particularly for recognizing (i) the coherent connection between attention decomposition, sparse representation learning, and reconstruction-risk analysis, and (ii) the value of explicit spectral bounds beyond qualitative expressivity arguments. These are central to our contribution: the primal-dual perspective explains the feature analysis and reconstruction mechanism, while the risk analysis quantifies the potential benefit of adaptive filtering in terms of signal and filter spectra.

We agree that the nested filter families in Experiment 3 guarantee the nonnegative sign of the oracle risk advantage. Your suggestion motivates a quantitative question: how much of this advantage do the bounds capture, and how does their informativeness depend on graph and signal structure? We add one focused supplementary study, “Experiment 4: Informativeness and Tightness of the Risk Bounds” (Appendix D), to address this question.

1. Broader controlled conditions. We consider homophilic and heterophilic SBMs, Erdős–Rényi graphs, and geometric graphs, all with expected non-self degree 12. Signal profiles include low-frequency, high-frequency, cross-band, and isotropic draws. We use n=120n=120, d=16d=16, α=0.2\alpha=0.2, noise levels σ∈{0.3,1,2}\sigma\in\{0.3,1,2\}, and 20 seed blocks, giving 960 graph–target–noise instances. Each clean target has the same normalized energy and is held fixed during noise evaluation. This varies topology, spectral concentration, and noise at matched graph size, expected degree, and signal scale.

2. Tightness and the mechanism behind the advantage. We distinguish the compact norm-based bound, the shared-basis spectral expression and the basis-optimized expression in Appendix B and Corollary 3, respectively. Within the oracle symmetric spectral-filter surrogate, they satisfy

Bcompact≤Bshared≤Boracle=ΔoracleB_{\mathrm{compact}}\le B_{\mathrm{shared}}\le B_{\mathrm{oracle}}=\Delta_{\mathrm{oracle}}.

Here, the shared-basis expression captures the benefit of adapting spectral weights in the graph basis; the difference Δoracle−Bshared\Delta_{\mathrm{oracle}}-B_{\mathrm{shared}} isolates the additional potential of adapting the basis. We report the fraction of the exact oracle gap retained by each bound, rather than only its sign.

For low- and high-frequency signals, the shared-basis expression retains 91.29–99.99% of the oracle gap, averaging over graphs and seeds at each signal/noise setting (Table 5). Thus it provides a quantitatively informative characterization in these regimes. For cross-band signals, the retained fractions are 97.99%, 81.67%, and 63.43% at σ=0.3,1,2\sigma=0.3,1,2, respectively. The remaining gap is precisely the basis-adaptation component (Fig. 6). These results separate spectral reweighting from basis adaptation and quantify their dependence on signal structure and noise.

3. Where does the compact bound lose sharpness? The compact norm-based expression is substantially more conservative; Table 5 reports its complete coverage. A controlled example further identifies a source of slack: signed spectral mismatches can cancel in its aggregate numerator even when their individual squared contributions remain nonzero. At the cancellation noise level, the compact bound vanishes while the mean oracle gaps remain 0.1013–0.2775 per entry across the four graph generators. For this target, the shared-basis expression equals the oracle gap (Fig. 7). This explains why a zero simplified guarantee need not imply no reconstruction benefit, and clarifies when the spectral expression is more informative than its compact relaxation.

4. Numerical verification and interpretation. For each instance, we use 256 fresh, paired noise draws. The Monte Carlo gaps agree with the exact expected gaps, with RMSE 9.03×10−49.03\times10^{-4} per entry; the analytical hierarchy holds in all 960 instances. Monte Carlo agreement checks the numerical risk evaluation, whereas the strongest oracle equality follows from spectral optimization. The oracle uses the fixed clean target, so these results quantify the existing theoretical comparison rather than establish that a trained GT attains it. In particular, an isotropic target is a finite matrix whose sample subspace can be exploited by the oracle; this does not establish transfer of that subspace to new signals.

This single addition is confined to Appendix D. All revised and newly added manuscript text, equations, tables, and captions are marked in blue. Apart from Theorem 3 whose result has been strengthened, the original theoretical results and Experiments 1–3 remain unchanged; only the presentation/wording has been revised. The study directly addresses bound tightness and broadens the graph/signal conditions, providing quantitative insight beyond the nonnegative oracle comparison. We appreciate the suggestion, which helps make the empirical support and interpretation of our risk analysis more precise.

Reviewer_8nxPOpenReview ↗

Thank you for the response

I thank the authors for their detailed response. The new results substantially address my concerns and strengthen the empirical rigour of the paper. I found the theoretical contributions to be well developed, but I am inclined to agree to some extent with Reviewer LkXV regarding the motivation and significance of the work. Given my relatively broad rather than specialized research experience in this area, I find it difficult to confidently assess how substantial the theoretical contributions are. I will maintain my score and recommend that the Area Chair place greater weight on the assessments of reviewers with higher confidence, particularly since several such reviews are available for this paper.

AuthorsOpenReview ↗

Thank You for Your Continued Positive Recommendation

We thank the reviewer for the thoughtful final assessment and for maintaining a positive recommendation. We particularly appreciate the recognition that the additional results substantially address the earlier concerns and strengthen the empirical rigor of the paper, as well as the assessment that the theoretical contributions are well developed.

Regarding motivation and significance, our study addresses a focused explanatory question: how the filter flexibility of graph transformers relates to their feature-extraction capabilities. The exact attention decompositions make the underlying operators explicit, while the constructive realization results clarify their relationship to fixed graph filtering. The group-sparse coding construction and population-oracle reconstruction-risk comparison then connect this flexibility to precise optimization and risk statements under explicit assumptions. We view this connection between operator representation, optimization, and reconstruction as the central theoretical contribution. It provides concrete settings in which the consequences of filter flexibility can be examined mathematically, offering a useful foundation for further theoretical studies and potentially informing future GT design.

Again, we appreciate the reviewer’s careful consideration of the contributions and their scope, and the constructive feedback that has helped us improve the precision, clarity, and supporting evidence of the manuscript.

Reviewer_3iaXOpenReview ↗
Rating
4(+1)
Confidence
4
Informativeness
3(+1)
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper studies the feature-extraction advantage of graph transformers by combining attention decompositions, fixed-filter containment, a sparse-coding interpretation, a reconstruction-risk analysis, and controlled illustrations. The synthesis is informative and the manuscript is generally clear. My remaining concerns are about keeping the notation consistent across sections and stating the logical status of the different claims. These are presentation-level issues that should be straightforward to address.

Critical strengths
  • The manuscript connects theory and controlled experiments closely and is honest about several limitations of the analysis.
  • Each experiment has a clear role and maps directly onto a theoretical component, which makes the empirical section easy to interpret.
  • The paper appropriately presents the studies as mechanism-focused and acknowledges that the ridge analysis is a surrogate rather than a full account of trained transformers.
Critical weaknesses
  • The notation linking the attention operator, fixed filter, sparse-coding dictionary, and spectral comparator changes across sections. A compact notation table and one sentence connecting DθD_\theta, DGTD_{GT}, A, H, and P would make the argument much easier to follow.
  • The paper moves among exact operator identities, an optimization interpretation, an expressivity construction, and an oracle risk benchmark. The section introductions should state this hierarchy explicitly so that readers can see which conclusions are exact, interpretive, existential, or oracle.
Questions for authors
  • Could the authors include a compact notation table for the main operators and spectral bases?
  • Please clarify whether the dictionary DD in the sparse-coding section refers to the same operator as DGTD_{GT}, or only a generic analogue.
  • The discussion after Corollary 3 connect reconstruction risk to feature-extraction advantage. However, the shared-basis gap can be positive even when the bases already agree, so it is not solely a measure of basis mismatch.
  • What is the main practical implication of the masked-softmax expansion for understanding feature extraction?
  • In the masked-softmax definitions (p. 4, lines 190–191), replace ‘Parallelly, For’ with ‘For’ and remove the duplicated comma after the query-monomial definition, just before the key-monomial definition.
  • In Theorem 4 (p. 6, line 288), change ‘there exist a GT filter’ to ‘there exists a GT filter’.
4 comments

We thank the reviewer for highlighting the close connection between the theoretical results and the controlled experiments, the clear purpose of each experiment, and the explicit acknowledgment of the ridge surrogate's limitations. We understand the main concerns to be consistency of notation and clarity about explanations of theoretical results. We have addressed these concerns through the notation table, revised transitions and theorem statements. The responses below explain these changes in detail.

Response to Weakness 1: We have added Table 1 and replaced the earlier DθD_\theta notation by DD in the coding and risk formulations. Here the filter DD is implemented by the chosen propagation operator; A=HDiag⁡(λ)H⊤A=H\operatorname{Diag}(\lambda)H^\top is the prescribed graph-filter comparator. In the symmetric ridge comparison, D=PDiag⁡(θ)P⊤D=P\operatorname{Diag}(\theta)P^\top, where PP may differ from HH. Thus HH is the fixed graph basis and PP is a candidate basis.

Response to Weakness 2: The revised Section 4 separates the claims as follows:

  • Exact identities: Theorems 1–2 decompose the stated attention outputs, with the value-adjoint convention made explicit.
  • Existential representation: Corollary 1 constructs an unmasked linearized attention layer for a prescribed filter using node identifiers and sufficient width.
  • Constructed optimization architecture: Theorem 3 specifies reconstruction blocks and proves fixed-stage convergence, including a two-stage composition with nonsingular dictionaries. It is an existence result for these networks.
  • Set inclusion: Corollary 2 compares reachable representations with matched coding ingredients and then takes infima of the same task loss.
  • Oracle risk: Theorem 4 and Corollary 3 optimize a ridge surrogate over fixed symmetric filters using the signal second moment, and separate spectral-weight and basis contributions.

The revised transitions distinguish representability, optimization, and reconstruction risk.

Response to Question 1: Yes. The table 1 consolidates the notation; we have placed it near the beginning of Section 4.

Response to Question 2: In the current Theorem 3, DD is first an arbitrary filter in JD(Z;Y)\mathcal J_D(Z;Y). The construction then realizes two operations DZDZ and D⊤(Y−DZ)D^\top(Y-DZ) using graph propagation or positional linearized attention. In the GT construction, DD is therefore an attention-realizable filter. The filter is fixed within a coding stage. The theorem does not identify a generic feature-dependent attention layer with one proximal block.

Response to Question 3: We agree. The original interpretation conflated spectral-weight mismatch with basis mismatch. Revised Corollary 3 separates them. Writing c=dσ2c=d\sigma^2 and ai=H:,i⊤BH:,ia_i=H_{:,i}^\top BH_{:,i},

Δoracle=ΔH+Δbasis,\Delta_{\rm oracle}=\Delta_H+\Delta_{\rm basis},

ΔH=∑i(αai−cλi2)2(λi2+α)2(ai+c),Δbasis=∑icaic+ai−∑icμic+μi.\Delta_H=\sum_i\frac{(\alpha a_i-c\lambda_i^2)^2}{(\lambda_i^2+\alpha)^2(a_i+c)},\qquad\Delta_{\rm basis}=\sum_i\frac{ca_i}{c+a_i}-\sum_i\frac{c\mu_i}{c+\mu_i}.

Both terms are nonnegative. The first is the exact improvement from optimizing spectral weights while retaining HH. The second is the additional improvement from optimizing the basis after the weights. The discussion on Corollary 3 now uses these two interpretations. The refined Theorem 4 and Corollary 3 are marked in blue.

Response to Question 4: It identifies the neighborhood statistics that softmax attention combines. With

Ci,ν=∑j∈Nihkν(xj)Vxj,xˉism=1Zi∑ν∈N0ℓhqν(xi)ν!Ci,ν,C_{i,\nu}=\sum_{j\in\mathcal N_i}h_k^\nu(x_j)Vx_j,\qquad\bar x_i^{\rm sm}=\frac1{\mathcal Z_i}\sum_{\nu\in\mathbb N_0^\ell}\frac{h_q^\nu(x_i)}{\nu!}C_{i,\nu},

the mask selects available neighbors, keys form value-weighted statistics of those neighbors, and queries select their contributions under the row normalizer Zi\mathcal Z_i. Thus neighborhoods with the same uniform mean can produce different outputs through higher-order key–value statistics. The revised explanation follows Theorem 2. Appendix A.2 also gives a finite-order approximation statement. If ∣⟨Qxi,Kxj⟩∣≤B|\langle Qx_i,Kx_j\rangle|\leq B and ∥Vxj∥2≤U\|Vx_j\|_2\leq U, truncating the exponential numerator at total degree RR gives

∥xˉism−xˉi(R)∥2≤UeBBR+1(R+1)!.\|\bar x_i^{\rm sm}-\bar x_i^{(R)}\|_2\leq U\frac{e^B B^{R+1}}{(R+1)!}.

This quantifies an approximation diagnostic.

Response to Question 5: Thanks for pointing this out. The suggested corrections have been made.

Response to Question 6: We thank the reviewer. This has been corrected.

Reviewer_3iaXOpenReview ↗

Thanks for the Clear Responses

The authors'response addresses my earlier concerns well. The distinction between a population-oracle benchmark and learning a filter from noisy observations is now explicit, and the condition for strict improvement makes the reconstruction-risk comparison more informative. Clarifying the shared architectural ingredients also helps establish the scope of the comparison. These are substantive improvements. I continue to find the connection between attention expressivity and reconstruction risk particularly valuable, as it provides an explanation of what greater filter flexibility can offer beyond a representability result alone.

By the way, one detail in the revised Theorem 3 remains unclear to me: why does the GT construction require nonsingular filters, whereas the GCN family has no such restriction?

AuthorsOpenReview ↗

Nonsingularity for Stagewise Convergence and Stability

We thank the reviewer for the encouraging feedback and for drawing attention to this distinction. The nonsingularity condition is a sufficient assumption for the quantitative analysis of the two-stage composition, rather than a requirement for GT filter realization.

For the single-stage GCN construction, both the dictionary and the coding input remain fixed. Convexity, coercivity, and an appropriate step size suffice to establish convergence of the proximal-gradient reconstruction blocks, including when the filter is singular. Through the filter realization in Corollary 1, the same single-stage convergence argument also applies to the corresponding GT reconstruction network.

The two-stage GT construction requires an additional ingredient: control of how the finite-depth approximation error from the first stage affects the second-stage solution. Nonsingularity supplies a direct sufficient condition for this analysis. It makes each stage objective strongly convex, gives a contraction factor strictly below one for the reconstruction update under the stated step-size conditions, and provides a Lipschitz bound on the second-stage solution as its coding input changes. Appendix A.4 combines the within-stage contraction estimates in Eqs. (18)–(19) with the input-stability estimate in Eq. (20) to obtain the explicit finite-depth error bound in Eq. (21). This establishes convergence to the composition of the coding optima as both stage depths increase.

Thus, the different assumptions reflect the different guarantees being established: convergence for a fixed coding problem in the first part, and quantitative control of a composition with approximate intermediate representations in the second. Singular filters remain representable by the attention construction in Corollary 1. The nonsingularity assumption supports the current stagewise convergence proof and should not be interpreted as an intrinsic limitation on GT expressivity.

Having considered the authors' further response, I am satisfied with the clarifications provided. I have also carefully read the other reviewers' comments and the corresponding author responses, paying particular attention to the technical concerns raised by reviewers who reported high confidence. These exchanges reinforce my own assessment that this is a meaningful theoretical contribution with value for future research on graph transformers.

The novelty is particularly evident in the connection between exact attention decompositions, constructive filter realizations, and reconstruction-risk analysis. Together, these results offer a coherent account of GT feature-extraction flexibility. The motivation is also convincing: understanding the mechanisms underlying this flexibility is an important question that complements empirical advances in GT architectures. I find the distinction between representational capability, the optimization interpretation of the constructed networks, and the population-oracle risk comparison useful. It makes the contribution easier to assess and provides a foundation for subsequent theoretical investigations and potentially for more principled model design. The revisions improve clarity by stating the relevant assumptions explicitly and aligning the interpretations with the scope of the proved results.

Across the previous discussion rounds, the authors have responded carefully and substantively to the questions that I have raised. My concerns have been satisfactorily addressed, and I have no further concerns. As a final evaluation, I consider the paper suitable for publication at ICLR and support clear acceptance.

Reviewer_HnouOpenReview ↗
Rating
4(+2)
Confidence
4(+1)
Informativeness
3
Presentation
3
Soundness
3(+1)
Read review
Paper summary

This paper develops a unified account of why graph transformers can be stronger feature extractors than fixed graph convolutions. The analysis connects four complementary views: primal-dual operator decompositions for linearized and softmax attention, constructive realization of fixed graph filters, an optimization interpretation through group-sparse coding, and a shared-basis reconstruction-risk comparison. I found the operator-level perspective useful and the overall theoretical synthesis promising. The remaining concerns are limited to notation, theorem scope, and the phrasing of several interpretations; they appear straightforward to address without changing the central results.

Critical strengths
  1. The paper gives exact decompositions for both projected linearized attention and masked softmax attention, making the feature-dependent operators explicit rather than treating attention as a black box.
  2. The constructive fixed-filter realization is a clear and useful expressivity result: it identifies conditions under which a graph transformer can reproduce a prescribed graph filter.
  3. The decomposition, sparse-coding interpretation, and reconstruction-risk analysis form a coherent explanatory around adaptive feature extraction.
  4. The paper is explicit about the surrogate nature of the risk model and supports the formal discussion with controlled synthetic diagnostics.
Critical weaknesses
  1. Theorem 3 proves a proximal-gradient recurrence for a fixed dictionary DD, whereas the subsequent transformer interpretation allows a layer-dependent attention-generated filter. The text should distinguish the exact fixed-DD update from the varying-DD case, which is more precisely described as a one-step update for a frozen layerwise objective or as an optimization-inspired recurrence.
  2. The group-sparsity notation needs correction. The stated ℓ2,1\ell_{2,1} penalty is described as row-group sparsity, while the displayed thresholding operation acts on columns. Defining the norm explicitly and using one consistent grouping convention would make the result straightforward to verify.
  3. Theorem 4 should state α>0\alpha>0 and σ>0\sigma>0 for the displayed finite optimizer, treat σ=0\sigma=0 as a separate boundary case, and label the clean-signal-dependent solution as an oracle benchmark. These qualifications make the theorem precise without changing its main comparison.
Questions for authors
  1. Can Theorem 3 distinguish the exact fixed-D proximal update from the layer-varying, frozen-objective interpretation?
  2. Which axis is intended to be group sparse in the ℓ2,1\ell_{2,1} objective? Theorem 3 and Appendix A.4 disagree about the grouping axis: the update shrinks columns, whereas the proof calls the penalty row-group sparse. The proximal subscript in proof also uses λ\lambda while the objective uses α\alpha.
  3. Can Theorem 4 state α>0\alpha>0 and σ>0\sigma>0 and explain the σ=0\sigma=0 boundary?
  4. Can the clean-signal-dependent optimum be identified consistently as an oracle benchmark?
  5. Could the paper distinguish the projected output in Theorem 1 from the graph-specific statement in Corollary 1?
4 comments

We thank the reviewer for recognizing the value of the exact attention decompositions, the constructive realization of fixed graph filters, and the coherent connection between sparse coding and reconstruction risk, supported by controlled diagnostics. We understand the main concerns to be the scope of the optimization interpretation, the inconsistent group-sparsity notation, and the assumptions and oracle status of the risk comparison. We have addressed these concerns by replacing the unrestricted layer-varying solver claim with a proved fixed-stage construction, defining columnwise groups consistently, and stating the population-oracle assumptions and the separate noiseless boundary. Our detailed point-by-point responses are provided below.

Response to Weakness 1: We agree that a changing dictionary does not automatically define iterations for one fixed objective. The second part of Theorem 3 now treats two prescribed nonsingular dictionaries, each held fixed within its stage. Stage 1 codes M=XV⊤M=XV^\top using D1D_1; stage 2 codes the first-stage output using D2D_2. With K1,K2K_1,K_2 reconstruction blocks, the output converges to Z2⋆(Z1⋆)Z_2^\star(Z_1^\star) as both depths tend to infinity. Positional linearized attention now can realize both prescribed filters, whereas the comparator GCN is tied to one topology-driven filter. The advantage established here is the freedom to implement distinct dictionaries across coding stages. This replaces the original unrestricted layer-varying solver interpretation with an explicit, proved construction.

Response to Weakness 2: The groups are feature-channel columns. Theorem 3 now defines $ \Vert Z \Vert_{2,1}:=\sum_{j=1}^{d'}\Vert Z_{:,j} \Vert_2 $, Z∈RN×d′Z\in\mathbb R^{N\times d'}. Each group contains one channel across all nodes. Appendix A.4 uses this grouping consistently in Theorem 3 and its proof.

Response to Weakness 3: Theorem 4 now explicitly assumes α>0\alpha>0 and σ>0\sigma>0. It formulates a population oracle: X∗X^* may be random, B=E[X⋆(X⋆)⊤]B=\mathbb E[X^\star(X^\star)^\top] is finite, the noise is independent with zero mean and E[ηη⊤]=σ2dIN\mathbb E[\eta\eta^\top]=\sigma^2dI_N. For a fixed orthogonal basis PP, Lemma 1 in Appendix A.5 gives the finite optimum αP:,i⊤BP:,i/(σ2d)\sqrt{\alpha P_{:,i}^\top BP_{:,i}/(\sigma^2d)}. Corollary 3 chooses an eigenbasis of BB and identifies an attaining filter. Thus the optimum is an oracle determined by the signal distribution and noise variance. Appendix B treats σ=0\sigma=0 separately: the oracle risk is an infimum approached through growing filter scales.

Response to Question 1: Yes. The revision distinguishes fixed-dictionary optimization from composition across coding stages. In the two-stage construction now, the first stage has objective JD1(⋅;M)\mathcal J_{D_1}(\cdot;M), and the second has objective JD2(⋅;M2)\mathcal J_{D_2}(\cdot;M_2), where M2M_2 is the completed first-stage output and remains fixed during the second stage. The proof establishes convergence of the composition. The advantage established here is the freedom to implement distinct dictionaries across coding stages. The argument extends to any fixed finite cascade of nonsingular filters and hence explains when GT's flexibility can be observed.

Response to Question 2: The intended grouping is columnwise, as in (Response to Weakness 2), and the proof separates the minimization column by column with aligned subscript now.

Response to Question 3: Yes. Theorem 4 states α>0\alpha>0 and σ>0\sigma>0, and Appendix B separates the noiseless case. With ai=H:,i⊤BH:,ia_i=H_{:,i}^\top BH_{:,i}, the noiseless oracle risk is

$ \Delta_{\mathrm{oracle}}=\sum_i\frac{\alpha^2a_i}{(\lambda_i^2+\alpha)^2}. $

For the GT-realizable filter D=tIND=tI_N, the associated reconstruction satisfy

DZD=t2t2+αX⋆⟶X⋆.DZ_D=\frac{t^2}{t^2+\alpha}X^\star\longrightarrow X^\star.

Thus the reconstructed signal approaches the clean input.

Response to Question 4: The revised theorem explicitly defines

Δoracle=E[ℓ(ZA)]−min⁡D∈D=D⊤E[ℓ(ZD)].\Delta_{\mathrm{oracle}}=\mathbb E[\ell(Z_A)]-\min_{D\in\mathcal D=D^\top}\mathbb E[\ell(Z_D)].

The optimizing basis diagonalizes B=E[X⋆(X⋆)⊤]B=\mathbb E[X^\star(X^\star)^\top] and its squared filter weights are αμi/(σ2d)\alpha\mu_i/(\sigma^2d). The construction in Appendix A.5 represents this oracle using positional linearized attention. The contribution statement now identify this symmetric-oracle comparison.

Response to Question 5: The revised paragraph after Theorem 1 distinguishes the raw output xˉi′∈Rd′\bar x_i'\in\mathbb R^{d'} from the value-adjoint transform V⊤xˉi′∈RdV^\top\bar x_i'\in\mathbb R^d. It supplies a raw-output identity using synthesis atoms χs,t\chi_{s,t}.

Reviewer_HnouOpenReview ↗

Authors have clarified my key concerns; I still have some minor issues.

I thank the authors for providing detailed responses. My main concerns regarding the scope of the optimization interpretation, the group-sparsity notation, and the assumptions and oracle status of the reconstruction-risk comparison have been well clarified. I particularly appreciate the care taken to translate these clarifications into concrete revisions: replacing the unrestricted layer-varying solver interpretation with a proved two-stage construction, consistently defining the columnwise groups, and explicitly separating the population-oracle comparison from the noiseless boundary case. These changes make the theoretical statements and their intended scope considerably clearer.

In particular, the exact attention decompositions and constructive realization of prescribed graph filters, together with the connection between sparse coding and reconstruction risk, provide a coherent and valuable theoretical perspective on the feature-extraction flexibility of graph transformers. I consider this synthesis a meaningful contribution to understanding their representational capabilities beyond fixed graph filtering.

However, I still have two minor follow-up questions, mainly concerning the interpretation and potential applications of the results:

  1. In what settings would the columnwise ℓ2,1\ell_{2,1}-penalized formulation be particularly useful, and how should the resulting feature-channel sparsity be interpreted?

  2. Beyond the fixed-stage construction, what would happen if GTs implemented filters that vary from layer to layer? A brief discussion of how the optimization interpretation would change would be helpful.

AuthorsOpenReview ↗

Further Response to Reviewer Hnou’s Additional Minor Questions

We thank the reviewer for the encouraging feedback and for recognizing the value of our exact attention decompositions, constructive filter realizations, and the coherent connection between sparse coding and reconstruction risk. Together, these results provide an operator-level explanation of GTs' feature-extraction flexibility, with its reconstruction benefit characterized through an explicit population-oracle comparison. We appreciate the opportunity to further clarify the role of channel sparsity and the interpretation of layer-varying filters.

1. Interpretation and potential uses of the ℓ2,1\ell_{2,1} penalty

The columnwise penalty ∥Z∥2,1=∑j∥Z:,j∥2\lVert Z\rVert_{2,1}=\sum_j\lVert Z_{:,j}\rVert_2 promotes sparsity across representation channels: it can suppress an entire channel across all nodes, while allowing retained channels to vary across nodes. This is useful when a compact representation with a shared set of active channels is desirable—for example, when signal information is concentrated in a small subset of representation channels.

More precisely, for a fixed pre-activation input UU, the objective separates across columns, and the zero vector is optimal for channel j exactly when ∥U:,j∥2≤ηα\Vert U_{:,j}\Vert_2 \le \eta\alpha.

Thus, channel suppression is determined by the balance between reconstruction fidelity and regularization. The selected channels belong to the coded representation; since the first-stage input is Y=XV⊤Y=XV^\top, they need not coincide with the original input attributes. In Theorem 3, this formulation supplies a concrete feature-extraction objective and the associated group-shrinkage nonlinearity.

2. Optimization interpretation of layer-varying filters

For the reconstruction architecture considered in Theorem 3, each block implements one proximal-gradient step for

JD(Z;Y)=12∥Y−DZ∥F2+α∥Z∥2,1\mathcal{J}_D(Z;Y)=\frac{1}{2}\lVert Y-DZ\rVert_F^2+\alpha\lVert Z\rVert_{2,1},

with the dictionary DD and coding input YY held fixed during that step. If the dictionary changes at every layer, the corresponding objective generally changes as well. The resulting network can therefore be interpreted as a sequence of updates for layer-specific objectives, but this alone does not establish convergence to a common minimizer or exact solution of each coding problem.

The revised theorem provides a precise construction in which different dictionaries are used across coding stages, with each prescribed nonsingular dictionary held fixed within its stage. The second stage takes the first-stage output as its fixed coding input. Appendix A.4 proves convergence to the composition of the two coding optima and, in Eq. (21), explicitly bounds the finite-depth approximation error.

This construction establishes how GTs can use distinct dictionaries for successive representation transformations, extending the fixed-filter coding construction. More general layer-varying filters offer additional modeling freedom, while guarantees for their optimization behavior require further conditions on how those filters vary.

Reviewer_HnouOpenReview ↗

All my concerns have been satisfactorily addressed

I thank the authors for the additional clarifications on my two follow-up questions.

The role of the columnwise sparsity penalty and the scope of the optimization interpretation are now clear to me. I have also carefully considered the other reviewers' comments and the authors'responses, which further strengthen my confidence in the paper's theoretical contribution. In particular, the connection between attention expressivity, sparse coding, and reconstruction risk provides a valuable perspective on GT feature extraction and may inform the development of future GT architectures.

All my concerns have now been satisfactorily addressed, and I am happy to raise my score and recommend acceptance.

Reviewer_LkXvOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper claims that fixed topology-driven aggregation is inferior to graph attention. In a sense, they compare fixed aggregation of the form L(X) = AXW where A is the aggregation operator with the attention form L(X) = A(X)XW where A(X) is the attention operator.

They claim to answer the question what feature adaptivity contribute and where it comes from.

Critical strengths

I cannot see any

Critical weaknesses

The paper has many flaws.

  1. Why is the question important? What is the real goal behind it? For me the motivation is very weak.

  2. Comparing with naive fixed mixing is wrong. Many graph method use edge features. If a_{ij} = f(x_i, x_j) where (i,j) are two nodes and a is the edge weight, and then L(X) = A(a)XW, then we have the same structure as the authors describe. Still attention may be better. This is not discussed in the paper.

  3. The theorems are not clear and I doubt they are even needed as theorems. The authors try to "look smart" rather than convince me that there is a motivation to prove(?) (I a mot sure that the proofs are relevant or correct).

  4. If this paper is to appear anywhere then the authors need to rewrite it, motivate what they do and convince there is merit to the theory.

Questions for authors

See the main problem (2) above and the writing.

2 comments
AuthorsOpenReview ↗

Clarifying the Motivation, Scope, and Theoretical Contributions

We thank the reviewer for raising the concerns about motivation, the comparator, and the theoretical results. We address them using the paper's definitions, proofs, and numerical evidence.

1. Motivation and research significance. Our question is how attention analyzes and reconstructs features, and what reconstruction cost can arise when propagation is restricted to a fixed graph filter. This goes beyond observing that an aggregation matrix can depend on features: it connects explicit query–key–value decompositions, constructive filter containment, and quantitative spectral risk analysis.

The distinction matters because the same graph can carry signals with different spectral energy profiles. A topology-driven filter applies a prescribed response, whereas adapting spectral weights or directions can better match the signal. Sections 1–2 therefore ask how attention provides this flexibility and how its potential benefit can be quantified. This provides an operator-level explanation and a criterion for the cost of restricting the filter family.

2. The adaptive-edge example and the comparator. We agree that aij=f(xi,xj)a_{ij}=f(x_i,x_j), recomputed from current features, defines feature-adaptive propagation. It belongs on the adaptive side of our distinction. Section 3 specifies the fixed-filter comparator AXWAXW, including normalized-adjacency GCNs. “Fixed” refers to propagation, not to the trainable channel transformation. Fixed edge attributes can define a weighted graph filter; signal-dependent edge weights instead define an adaptive operator.

Thus, the comparison isolates fixed versus feature-dependent propagation, not attention versus every other GNN. Sharing the form A(X)XWA(X)XW also does not make two model classes identical: parameterization, masks, and normalization constrain the attainable operators. Our theorems analyze the stated attention mechanism and fixed-filter restriction; they do not rank attention against arbitrary adaptive edge-weighting rules. Your example is compatible with this scope. In the risk comparison, both sides solve the same ridge coding objective and use the same reconstruction loss; the distinction is the admissible filter family.

3. What the theoretical results establish. The results have distinct roles:

  • Theorems 1–2 / Appendices A.1–A.2: exact analysis–synthesis identities for projected pre-activation outputs V⊤xˉiV^\top\bar x_i. They identify key-induced analysis atoms and query-induced synthesis atoms. The masked-softmax expansion retains both the mask and row normalization, so this explanation is not confined to linearized attention.
  • Corollary 1 / Appendix A.3: an SVD construction realizes a prescribed fixed filter using linearized attention, one-hot positional encodings, and sufficient query/key width. It explicitly identifies how feature-independent query/key coordinates recover fixed propagation.
  • Theorem 3 / Appendix A.4: an exact proximal-gradient recurrence for a fixed dictionary, with an optimization-inspired layerwise interpretation when the attention-generated dictionary changes.
  • Theorem 4 / Corollary 3 / Appendices A.5–A.6: explicit bias–variance calculations and oracle spectral optimization under a common ridge reconstruction objective.

For example, for α,σ>0\alpha,\sigma>0, the shared-basis oracle gap is

∑i(αai−cλi2)2(λi2+α)2(ai+c),ai=∥hi⊤X∗∥22,c=dσ2.\displaystyle\sum_i\frac{(\alpha a_i-c\lambda_i^2)^2}{(\lambda_i^2+\alpha)^2(a_i+c)},\qquad a_i=\|h_i^\top X^*\|_2^2,\quad c=d\sigma^2.

Here hi,λih_i,\lambda_i are eigenvectors/eigenvalues of the fixed filter. The gap is strictly positive if any αai≠cλi2\alpha a_i\ne c\lambda_i^2. This gives both its magnitude and a strict-improvement condition beyond the nonnegative sign implied by set inclusion. Optimizing the basis further separates the contribution of spectral reweighting from that of changing the reconstruction directions. The clean-target-dependent optimum is an oracle benchmark; the text preceding Theorem 4 explicitly distinguishes this surrogate comparison from a particular GT's layerwise training dynamics.

4. Focused additional evidence. Experiment 4, prepared for Appendix D, covers four graph generators, four signal profiles, three noise levels, and 20 seeds. The shared-basis expression retains 91.29–99.99% of the oracle gap for low/high-frequency signals, averaged over graphs/seeds at each setting. For cross-band signals, the retained fractions are 97.99%, 81.67%, and 63.43% at σ=0.3,1,2\sigma=0.3,1,2, respectively; the residual gap isolates the additional potential of basis adaptation. The study also explains where compact norm-based simplification loses sharpness. These results quantify bound informativeness across varied conditions.

We hope these clarifications make the motivation, technical contribution, and intended comparison clearer, and respectfully invite reconsideration in light of the stated scope and additional evidence.

Reviewer_LkXvOpenReview ↗

The response did not answer my questions

For edge weights the structure is actually different (seems like the authors do not see that. It is G^T \sigma(WGXA) where G is the incidence matrix and W are the weights.

The theorems are hard to understand (seems that you are just trying to be fancy). Again, the motivation is lacking to me

I keep my score

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.