acceptodds
Under review as a conference paper at ICLR 2027

Stable Transformers for Graph Generation

Abstract

Graph generative models increasingly rely on Graph Transformers (GT) to capture complex dependencies among nodes and edges. While deeper architectures should provide greater expressive capacity and a broader receptive field, their effectiveness can decline with depth: repeated self-attention progressively contracts node representations, impeding information flow and gradient propagation. We analyse this phenomenon from a dynamical systems perspective, focusing on how the denoiser's spectral dynamics affect graph generation. We show that standard GT denoisers become increasingly dissipative as depth grows, leading to vanishing gradients and representation collapse. To isolate the effect of these dynamics, we construct a permutation-equivariant GT with inherently stable, non-dissipative transport. We also introduce a damping mechanism that continuously interpolates between non-dissipative and increasingly contractive regimes, enabling a direct assessment of how dissipation influences generation. Experiments on synthetic and molecular graph generation benchmarks show that the gap between these regimes widens with depth: non-dissipative dynamics preserve representation diversity and gradient flow, sustaining strong generative performance, whereas greater contraction progressively impairs it. These findings identify the denoiser's dynamical regime as a key design factor for deep graph generative models.

Primary area:
generative models
Keywords:
Graph Generation, Discrete Flow Matching, Graph Transformers

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_MuUHOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies how the dynamics of deep Graph Transformer denoisers affect graph generation. The authors propose SGT, which replaces standard attention-based node mixing with a Cayley-transform-based orthogonal operator while preserving permutation equivariance. A damping parameter allows controlled comparisons between orthogonal and contractive transport. Within the DeFoG framework, experiments on Planar, SBM, ZINC250k, and MOSES show that SGT remains effective at greater depths where the standard backbone degrades. Representation and spectral analyses provide evidence linking these improvements to reduced representation collapse and better signal propagation.

Critical strengths
  1. The paper offers a useful perspective on why increasing denoiser depth can hurt graph generation. The orthogonal transport construction, damping experiments, and representation analysis connect architectural choices to observable generation behavior. This makes the work informative beyond the proposed model.

  2. The empirical gains are meaningful and extend beyond preventing failure at extreme depths. On ZINC250k, SGT reduces FCD from 1.43 to 0.94 at the same eight-layer depth, with further improvement at greater depths. Its ability to sustain effective generation at 32 layers, where the DeFoG backbone collapses on the synthetic benchmarks, supports the practical value of the architecture.

Critical weaknesses
  1. Theorem 3.1 explicitly assumes fixed attention scores, edge inputs, and global inputs, but the relevance of this conditional result to the actual model dynamics remains unclear. Fixing attention establishes orthogonality of the transport operator while excluding gradients arising from the dependence of attention on node representations. The spectral and representation analyses provide useful evidence, but their connection to the conditional Jacobian is not sufficiently explained. Since gradient preservation is central to the explanation of the depth gains, the paper needs a clearer justification for why this conditional analysis captures the behavior of the complete model.

  2. The ZINC250k results contain an inconsistency that affects the depth comparison. Table 2 reports an FCD of 1.81 for the 16-layer DeFoG baseline, whereas Table 4 reports 1.30; both tables report 1.43 for the eight-layer baseline. These values imply opposite trends as depth increases. The results need to be reconciled before the claim that DeFoG deteriorates with depth on this dataset can be assessed.

Questions for authors
  1. Please generate more graphs on the synthetic benchmarks or repeat the evaluation with a few sampling seeds. The differences in the damping experiment are fairly small, so repeated sampling would make the trend more convincing. These evaluations can use the existing checkpoints.

  2. Table 7 only reports V.U.N. I would also like to see the corresponding Ratio values. Similar validity rates can hide differences in the generated distributions, which may reveal more about the effect of damping.

  3. The eight-layer results are interesting: SGT already improves on ZINC, but its Planar Ratio is 10.22 versus DeFoG’s 2.41. What explains this difference? Any insight from the existing training curves would be useful here.

4 comments

We thank the Reviewer for their thoughtful comments and constructive feedback. We appreciate their recognition that our work offers a useful perspective on why increasing denoiser depth can hurt graph generation, and that the orthogonal transport construction, damping experiments, and representation analysis connect architectural choices to observable generation behavior, making the work informative beyond the proposed model. We also appreciate their acknowledgment that the empirical gains are meaningful and extend beyond preventing failure at extreme depths, with SGT achieving improvements even at shallow depths and sustaining effective generation at greater depths. We address their concerns below and hope these clarifications will help improve their assessment towards acceptance.

W1 We thank the Reviewer for this comment. We clarify that, for a given layer (\ell), the attention scores, edge inputs, and global inputs are already determined when evaluating the transport operator at a specific point in the forward pass. Indeed, the input representations do not change within the evaluation of a single layer. More specifically, the attention scores are determined by the input representations X(ℓ)X^{(\ell)} and the corresponding projection weights W(ℓ,h)W^{(\ell,h)}. Both are already determined (i.e., fixed) when evaluating the transport operator at a specific point in the forward pass. Therefore, the attention scores are well-defined and fixed for that evaluation, allowing us to analyze the orthogonality of the resulting Cayley transform. This does not imply that the attention scores are independent of the input representations, but rather that our analysis considers the transport operator induced by a given input. Therefore, these are not additional assumptions imposed on the model, but simply the quantities defining the transport operator at that point. We have revised the statement to avoid introducing unnecessary assumptions and clarify this distinction.

W2. We thank the Reviewer for spotting this typo. The correct FCD value for DeFoG at L=16L=16 is 1.81. We have corrected the corresponding entry in the table. Therefore, our original conclusions remain unchanged, confirming our claims regarding the negative effect of increasing depth on the baseline.

Q1. Following the reviewer’s suggestion, we trained our model with three additional random seeds. Table 1 now reports the mean and standard deviation of V.U.N. and Ratios across four seeds for each layer configuration. We sampled 40 graphs from each independently initialized model, yielding 160 graphs per configuration.

Q2. We thank the Reviewer for the insightful suggestion. Table 7 (now Table 9 in the revised manuscript) now reports the Ratios of the generated graphs, helping to better clarify the damping effect of γ0\gamma_0. We have therefore updated Table 9 to include these ratios for each tested value of γ0\gamma_0 in the L=32L=32 configuration. We are currently extending this ablation to the remaining layer configurations and will update the manuscript once these experiments are complete.

Q3. We thank the reviewer for pointing this out. During our investigation, we identified a genuine error in the checkpoint-selection step of our evaluation pipeline, which selected an early, undertrained checkpoint. The reported ratio of 10.22 was therefore computed using an undertrained model. We have corrected the selection procedure and repeated the evaluation. The corrected Average Planar ratio, averaged across four training seeds, is 2.63, and we have updated the manuscript accordingly. This was an isolated issue, and no other runs reported in the manuscript were affected. Thank you again for your support in spotting this error.


We hope these clarifications and revisions address the Reviewer’s concerns, and we would be grateful if they would consider reassessing their evaluation and score based on the updated text and the above comments.

Thank you for adding the four-seed results, damping Ratios, and QM9 experiments. These strengthen the empirical support. The FCD discrepancy and checkpoint-selection issue have also been addressed, resolving my concerns on those points. I also appreciate the clarification in another response that Figure 3(b) measures the full-layer Jacobian, providing useful evidence about the complete architecture.

My remaining concern is the revised Theorem 3.1 and its proof. The statement now explicitly says that attention scores are computed from the input representations, but Appendix A.1 still uses J=Cᵀ⊗R. This expression includes only the derivative with R held fixed. For F(X)=R(X)XC, the full differential also contains (dR(X))XC. Evaluating the forward pass at a determined input does not remove this term.

Please restore the fixed-score and fixed-conditioning qualifications and identify the guarantee as concerning the conditional transport Jacobian. If the implementation uses stop-gradient, this should be stated in the model definition. The empirical evidence for well-conditioned full-layer Jacobians is valuable, but needs to be distinguished from this conditional theoretical result. I am maintaining my score of 5 for now; correcting this issue, together with the additional experiments, would support reconsideration toward weak acceptance.

We thank the Reviewer for the constructive feedback and for acknowledging that the additional experimental results strengthen the empirical support of our work.

We have now revised Theorem 3.1 and its proof in Appendix A.1 to explicitly account for the dependence of the attention scores on the input representations, rather than assuming them to be fixed, as we do not employ stop-gradient in our experiments.

Indeed, our objective is not to enforce exact orthogonality of the full Jacobian, but rather to maintain near-orthogonal dynamics that substantially mitigate dissipation and preserve information propagation. The revised theorem formalizes this by expressing the Jacobian as an orthogonal component plus a drift term, showing that its singular values remain close to one when this drift is sufficiently small.

This theoretical characterization is also supported by the empirical evidence in Figure 3(a), where the Jacobian eigenvalues of the trained SGT remain close to the unit circle, consistent with the intended near-non-dissipative regime. Figure 3(b) further provides evidence of well-conditioned gradient propagation through the complete architecture.

We hope these revisions address your remaining theoretical concern and, together with the additional experiments, support reconsideration of your score toward acceptance.

Dear Reviewer MuUH,

As the rebuttal discussion period is approaching its end (less than 24h remaining), we would like to kindly follow up on our response.

We hope that the theoretical concern has now been addressed, and we would appreciate any further feedback. While we would be happy to clarify any remaining points, we hope that you might reconsider your score towards acceptance in light of these improvements.

Best regards,
The Authors

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

This work introduces SGT, a novel replacement for Graph Transformer (GT) denoisers. Unlike prior methods, SGT preserves node representation instead of contracting it and leads to better information flow and gradient propagation in deeper networks. Authors argue (mainly based on prior literature) that the dissipative dynamics of self-attention in GTs are responsible for vanishing gradients as network depth grows. Instead, the authors propose SGT, a drop-in, non-dissipative replacement for self-attention based on the Cayley transport. The authors argue theoretically that SGT guarantees non-dissipative propagation and empirical results demonstrate that SGT-based networks improve with increasing depth and generally outperform other methods.

Critical strengths
  1. The manuscript is well motivated and very insightful, especially section 2 which connects dissipative dynamics to graph generation quality.
  2. The proposed solution only alters the self-attention mechanism (leaving the surrounding framework unchanged) and scales better with depth without any hyperparameter search.
Critical weaknesses

In order of importance:

  1. Proof of Theorem 3.1 is particularly confusing as it makes several assumptions without proper justification.
    1. The proof argues that "For each hh, skew-symmetry of K(h)K^{(h)} implies that its Cayley transform R(h)R^{(h)} is orthogonal (Helfrich et al., 2018)" (lines 834-836). However, the cited theorem by Helfrich et al. requires that K(h)K^{(h)} be a real-valued, skew-symmetric matrix with ∣Kij(h)∣≤1|K^{(h)}_{ij}| \le 1. The magnitude requirement for each element is neither justified nor mentioned in the manuscript.
    2. When taking the element-wise derivative of Z(h)Z^{(h)} with respect to input node representation X(h)X^{(h)}, the authors assume that the attention matrix (S(ℓ,h)S^{(\ell, h)}) is fixed (lines 838-839). However, as defined, "S(ℓ,h)S^{(\ell, h)} is the attention-score matrix at layer ℓ\ell and head hh obtained from the query-key interactions before softmax normalization" (lines 260-262). Since S(ℓ,h)S^{(\ell, h)} depends on the input node representation (i.e. X(h)X^{(h)}), I am unsure why the fixed assumption is valid.
  2. Experimental results appear to be from a single training run and without any error bars or standard deviations.
  3. The ablation experiment exploring the dynamical regime (i.e. the effects of γ0\gamma_0) is only applied to a network with the highest explored depth (L=32L=32). The lack of data for other explored depths (L=8,16L = 8, 16) limits the conclusions that can be drawn about the effect of the dynamical regime.
Questions for authors

Clarifications that will affect my assessment:

  • Please provide clarifications and additional results to address the weaknesses outlined previously. Standard deviations or error bars should be at least provided for SGT results and ablations.

Questions/Suggestions for future work,

  • Could the dampening factor (γ0\gamma_0) be learned or optimized on a per-layer basis? If non-dissipation is truly advantageous to graph generation in deeper models, I would expect a learned dampening factor to lean towards non-dissipation (i.e. 0).
6 comments
AuthorsOpenReview ↗

Response 1/2

We thank the Reviewer for their thoughtful comments and constructive feedback. We appreciate their recognition of the well-motivated and insightful connection between dissipative dynamics and graph generation quality, as well as the simplicity of our proposed solution, which only alters the self-attention mechanism while leaving the surrounding framework unchanged and scales better with depth without requiring hyperparameter search. We address their concerns below and hope these clarifications will help improve their assessment towards acceptance.

W1.1. We thank the reviewer for raising this point. We clarify that the entrywise bound ∣Kij∣≤1|K_{ij}|\leq 1 is not required for the orthogonality of the Cayley transform. Theorem 3.1 of Helfrich et al. (2018) establishes that every orthogonal matrix can be represented through a scaled Cayley transform with a bounded skew-symmetric matrix. This is a result concerning the expressiveness of the parametrization, not a necessary condition for orthogonality. Indeed, for any real skew-symmetric matrix KK, the Cayley transform R=(I+K)−1(I−K)R=(I+K)^{-1}(I-K) satisfies R⊤R=IR^\top R=I, independently of the magnitude of its entries. Notably, Helfrich et al. (2018, Section 3.1) themselves illustrate this property using a skew-symmetric matrix with entries of magnitude 447.212. Therefore, our orthogonality guarantee holds without any additional boundedness assumption on the attention scores, and the proof remains valid as stated.

W1.2. We clarify that for a given layer ℓ\ell and attention head hh, the attention scores are determined by the input representations X(ℓ)X^{(\ell)} and the corresponding projection weights W(ℓ,h)W^{(\ell,h)}. Both are already determined (i.e., fixed) when evaluating the transport operator at a specific point in the forward pass. Indeed, the input representations do not change within the evaluation of a single layer. Therefore, S(ℓ,h)S^{(\ell,h)} is well-defined and fixed for that evaluation, allowing us to analyze the orthogonality of the resulting Cayley transform. This does not imply that the attention scores are independent of the input representations, but rather that our analysis considers the transport operator induced by a given input. Moreover, regardless of the input dependence of the attention scores, the Cayley transform always produces an orthogonal transport matrix. Therefore, this is not an additional assumption imposed on the model and to avoid further confusion we removed the statement.

W2. We thank the Reviewer for the feedback. In our experiments, we followed the evaluation protocol widely adopted in the graph generation literature, including Vignac et al. (2023), Qin et al. (2025), and Eijkelboom et al. (2024). Nevertheless, we have now included standard deviations for our synthetic results, by retraining the models on three additional seeds. We updated the manuscript accordingly. Given the extensive cost of running these experiments, we hope to report complete results before the rebuttal deadline or, alternatively, include them in the final manuscript.

W3. We thank the Reviewer for this suggestion. We conducted the ablation on γ0\gamma_0 using the best-performing configuration (L=32L=32) to isolate the effect of the dynamical regime in the setting achieving the highest generation quality. However, the effect of different dynamical regimes across depths is also investigated indirectly through our comparison with DeFoG. Indeed, as discussed in our theoretical analysis, DeFoG exhibits contractive dynamics comparable to those induced by SGT with stronger damping (e.g., γ0≈4\gamma_0 \approx 4). Therefore, comparing DeFoG and SGT at L=8,16,32L=8,16,32 already provides an indication of how different dynamical regimes affect generation quality as depth increases. Nevertheless, To complement the evidence already provided by our comparison with DeFoG, we are currently extending the ablation to L=8L=8 and L=16L=16, further investigating how the dynamical regime affects generation quality across depths. Given the extensive cost of running these experiments, we hope to report complete results before the rebuttal deadline or, alternatively, include them in the final manuscript.

AuthorsOpenReview ↗

Response 2/2

Q1. Please refer to the weaknesses.

Q2. We thank the reviewer for this interesting suggestion. Indeed, γ0\gamma_0 could be made learnable, potentially with a different value for each layer, allowing the model to adaptively control its dynamical regime. However, in this work, we deliberately keep γ0\gamma_0 fixed to isolate the effect of dissipation on graph generation, enabling a controlled comparison between non-dissipative and increasingly dissipative dynamics, which is central to our research question. We agree that learning γ0\gamma_0 could provide an interesting complementary experiment which could strengthen the generation capabilities of the model. Investigating such adaptive, layer-dependent dynamics is an interesting direction for future work. We included this discussion in the conclusion section.


We hope these clarifications and revisions address the Reviewer’s concerns, and we would be grateful if they would consider reassessing their evaluation and score based on the updated text and the above comments.

Dear Reviewer,

As the rebuttal discussion period is approaching its end, we would like to kindly follow up on our responses and the additional results and clarifications provided.

We would appreciate hearing whether our responses have addressed your concerns or if there are any remaining points you would like us to clarify. We would be happy to discuss them further and hope you might reconsider supporting the acceptance of our work in light of the new evidence.

Best regards,

The Authors

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

This paper addresses the use of Graph Transformers used as discrete denoisers for graph generation. The authors analyze self-attention from a dynamical systems perspective, showing that repeated row-stochastic attention leads to dissipative dynamics across depth. As a result, they propose S-Graph Transformer (SGT), which replaces softmax self-attention with a Cayley-based orthogonal node-mixing operator derived from a skew-symmetric score matrix, alongside orthogonal channel mixing. To support their thesis, they conducted experiments on synthetic (Planar and SBM) and molecular (Zinc and Moses) datasets. According to the proposed metrics, they have good results compared to the other methods.

Critical strengths

The authors have well motivated the perspective of connecting spectral dynamics to deep graph generation.

It is interesting that the connection between rank collapse and dissipative spectral dynamics in the transformer to directly discretizes the flow-matching graph generation.

Another strength of the method is its use of the Cayley transform, which combines the guarantee of orthogonality without requiring constrained Stiefel manifold optimization or projection steps, and preserves equivariance by constructing the transform via skew-symmetrization.

The paper uses a dampling framework of principled causal verification to prove that the spectral dissipation actually affects the generative fidelity using the dampling parameter γ=γ0/L\gamma = \gamma_0 / L.

Critical weaknesses

The article presents some problems:

  • In the proof of the theorem 3.1, it is claimed that the attention score S(l,h)S^{(l,h)} is kept fixed. However, the score is a dynamic function of input node representations X(l)X^{(l)} via query-key projections. This should break the statement that the overall Jacobian layer JlJ_l is orthogonal during the forward or backward passes. Furthermore, Equation 10 adds LayerNorm and a Feed Forward Neural Network αl\alpha_l: X(l+1)=X~(l)+αlFFN(LN(X~(l)))X^{(l+1)} = \tilde{X}^{(l)} + \alpha_l \text{FFN}(\text{LN}(\tilde{X}^{(l)})), in which the first is resetting the vector magnitudes to a fixed hypersphere surface and the latter is continuously stretching or squashing the vector lengths depending on their feature direction. This will make the full layer map to not be isometric.

  • The introduction of the Cayley transform requires a skew-symmetric matrix that is built via K(l,h)=ϵ(y)2N(S−S⊤)K^{(l,h)} = \frac{\epsilon(y)}{2\sqrt{N}}(S - S^\top). However, this forces the diagonal elements of KK to be zero, but the standard self-attention relies on non-zero diagonal entries.

  • In table 6, the specified computational costs are not well explained, nor is the baseline or how the method compares against the other competitors, the training time is only for small graphs (N≤100N \le 100), and the timing for sampling is completely omitted, since the multi-layer matrix inversion at every flow step is a major bottleneck.

  • Considering both performance and time, there are minor performance gains in the metrics by increasing the depth on both Zinc and Moses, while the times grow substantially.

  • For the synthetic datasets, in the competitors' papers, they used other MMD metrics that are not reported here, and using only four datasets is a restricted experimentation. In the benchmarks of the other article they use as well community-small, proteins, QM9, or OGBG.

  • In the paper it is not taken into consideration, or just marginally in the experiments, alternatives to the discrete flow matching, like continuous space diffusion models (e.g. GSDM [1], GDSS [2], or GGSD [3]) that allow high-order ODE solvers to accelerate sampling, or one-shot models (e.g. SPECTRE) that generate graphs in a single forward pass. Given that SGT requires O(N3)O(N^3), this gets worse on the minor gains for bigger layers.

The article is readable, however, it has some minor problems:

  • There is no graphic schema of SGT explaining the flow and the major components of the algorithm

  • The metrics in the main paper are quite vague, the metrics in the appendix should be moved, giving more significance than reporting just the MMD of validity & uniqueness & novelty, and the ratio.

  • This is only a personal preference, but in the introduction there are too many consecutive citations, e.g., for the second sentence, there are 10 citations.

[1] Luo, T., Mo, Z., & Pan, S. J. (2023). Fast graph generation via spectral diffusion. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(5), 3496-3508.

[2] Jo, J., Lee, S., & Hwang, S. J. (2022, June). Score-based generative modeling of graphs via the system of stochastic differential equations. In International conference on machine learning (pp. 10362-10383). PMLR.

[3] Minello, G., Bicciato, A., Rossi, L., Torsello, A., & Cosmo, L. (2025, May). Generating graphs via spectral diffusion. In International Conference on Learning Representations (Vol. 2025, pp. 72574-72593).

Questions for authors

Beyond the explanations for the weaknesses I noted, I'd like an explanation for the first two: could you compute and show the empirical Jacobian spectrum of the full layer map? Does the full model actually maintain singular values near 1?

On the experimental side, could you complete the timing benchmark against the other methods you tried? Also, a comparison with another dataset like OGBG-molhiv or OGBG-molpcba, and report other metrics should be doable in small times. It is a plus if you can implement and compare against some of the continuous methods like the ones I have mentioned in the weaknesses or more recent ones, but I need at least pros and cons compared to them.

8 comments
AuthorsOpenReview ↗

Response 1/3

We thank the Reviewer for their thoughtful comments and constructive feedback. We appreciate their recognition of the well-motivated connection between spectral dynamics and deep graph generation, the use of the Cayley transform to guarantee orthogonality while preserving equivariance, and the principled study of how spectral dissipation affects generative fidelity through the damping mechanism. We address their concerns below and hope these clarifications will help improve their assessment towards acceptance.

W1. We clarify that for a given layer ℓ\ell and attention head hh, the attention scores are determined by the input representations X(ℓ)X^{(\ell)} and the corresponding projection weights W(ℓ,h)W^{(\ell,h)}. Both are already determined (i.e., fixed) when evaluating the transport operator at a specific point in the forward pass. Indeed, the input representations do not change within the evaluation of a single layer. Therefore, S(ℓ,h)S^{(\ell,h)} is well-defined and fixed for that evaluation, allowing us to analyze the orthogonality of the resulting Cayley transform. This does not imply that the attention scores are independent of the input representations, but rather that our analysis considers the transport operator induced by a given input. Moreover, regardless of the input dependence of the attention scores, the Cayley transform always produces an orthogonal transport matrix. Therefore, this is not an additional assumption imposed on the model and to avoid further confusion we removed the statement. Regarding Eq. 10, we never claimed that the complete architecture is fully isometric. Indeed, our goal is to achieve stable, non-dissipative propagation, enforcing a near-orthogonal Jacobian to preserve the norms of forward and backward gradients (lines 252-255). This result is also shown empirically in Fig. 3b, where our trained SGT obtains a well-conditioned Jacobian with singular values close to one. Specifically, LayerNorm and the FFN are used to balance conservative propagation with more general transformations, improving the ability of the model to learn complex dynamics. This is also consistent with the state-space model literature [1,2], where the desired dynamical properties are often imposed on specific components rather than the entire architecture.

[1] Orvieto et al. Resurrecting recurrent neural networks for long sequences. ICML 2023

[2] Gu et al. Efficiently modeling long sequences with structured state spaces. ICLR 2022

W2. We emphasize that the central goal of our work is precisely to replace standard self-attention with a transport mechanism possessing more favorable stability properties. Therefore, different implementation choices are expected. Importantly, while the diagonal elements of the skew-symmetric matrix K\mathbf K are necessarily zero, the Cayley transform produces an orthogonal matrix R\mathbf R whose diagonal entries can be non-zero. Thus, the proposed transport mechanism still allows nodes to retain information from their own representations, similarly to standard self-attention, while providing the additional stability properties that motivate our approach.

W3. Table 6 (in the original manuscript, Tab 7 in the revised one) reports the parameter count and training time per epoch of SGT compared against DeFoG, one of the most recent and competitive baselines, across all considered benchmarks. We stress that most of the considered baselines, as detailed in Sec. 2.1 and 2.3, build upon the standard Graph Transformer architecture introduced by Vignac et al. (2023), and therefore share similar architectural computational characteristics. To further improve our computational analysis, we have now included sampling-time measurements in Table 7 (App B.3). We note that the computational scaling of sampling is consistent with that of training at the level of individual denoiser evaluations.

AuthorsOpenReview ↗

Response 2/3

W4. We thank the reviewer for the comment, however we believe that the improvements are not necessarily minor. For instance, compared to DeFoG at L=8L=8, SGT L=32L=32 reduces FCD by 40.6% on ZINC250k and 17.9% on MOSES, and reduces ratio by 45.6% and 49.5% on Planar and SBM, respectively. Moreover, the results obtained by increasing the number of layers within SGT are primarily intended to highlight the ability of our architecture to mitigate the vanishing-gradient issues affecting standard Graph Transformers. Our goal is not to claim that increasing depth always provides the best trade-off between performance and computational cost; indeed, the optimal number of layers is a task-dependent hyperparameter that can be selected according to the desired balance between generation quality and efficiency.

W5. We thank the reviewer for this suggestion. To strengthen our experimental evaluation, we included experiments on QM9 to the revised manuscript (Table 8, Appendix B.4).

We are currently running experiments on PROTEINS. In the dataset below, we report the current results with baseline performance taken from the SPECTRE paper. Our L=8L=8 model achieves the lowest Degree, Clustering, and Orbit discrepancies and the lowest overall Ratio among the evaluated models, and, notably, report MMDs close to the training set. We are running these experiments with L=16L=16 and L=32L=32 configurations and will report the results here as soon as they are available. The PROTEINS results will also be included in the final version of the manuscript.

ModelDeg. ↓Clus. ↓Orbit ↓Spectral ↓Ratio ↓
Training set0.00030.00680.00320.00091.0
GraphRNN0.00400.14750.58510.015282.3
GRAN0.04790.12340.34580.012582.7
MolGAN*0.00080.06440.00810.00214.2
GG-GAN (RS)*0.47270.17720.73260.4102875.8
GG-GAN*0.51920.52200.73260.3996906.5
SPECTRE (k=16)0.00560.08430.02670.005216.9
SPECTRE (k=16, real spectra)0.00130.04690.02870.00206.0
Ours (L=8)0.00040.04240.00500.00243.7

W6. We thank the reviewer for this observation. We would like to clarify that our goal is not to establish the superiority of discrete flow matching over alternative graph generation paradigms. Rather, our work addresses a fundamental limitation of graph generative models employing self-attention-based denoisers: the increasingly dissipative dynamics that hinder information and gradient propagation, particularly as network depth increases. Hence, our contribution targets the denoiser architecture in flow matching methods rather than the generative framework itself. Nevertheless, we now include a broader comparison to better contextualize our results. We have therefore extended our experimental tables to include the mentioned methods (GSDM, GDSS, GGSD, and SPECTRE) and added the corresponding references to Sec. 2.1 and Appendix B.1.

W7 Minors. We thank the Reviewer for these suggestions, we have now incorporated a graphic schema of SGT in Figure 6, Appendix B.6. Regarding the additional metrics, we opted to report them in the appendix due to space constraints. However, we would be happy to move them to the main text if the Reviewer considers this important. Concerning the number of citations in the Introduction, our intention was to properly acknowledge the relevant contributions from the literature. Nevertheless, we would be happy to reduce the number of citations if the Reviewer considers this important for readability.

Q1. We kindly note that Fig 3b already provides an empirical analysis of the Jacobian singular values of the full layer transformation for a trained model with L=32L=32 layers, thus accounting for all architectural components rather than only the orthogonal transport operator. The results show that the singular values remain concentrated around 1, even at this depth, providing empirical evidence that the complete architecture maintains well-conditioned Jacobians and mitigates vanishing and exploding gradients. Importantly, while our theoretical guarantees concern the orthogonal transport mechanism, these results demonstrate that its favorable propagation properties are largely preserved in practice despite the additional architectural components.

AuthorsOpenReview ↗

Response 3/3

Q2. As discussed in our response to W3, Table 7 reports the parameter count and training time per epoch of SGT compared against DeFoG, one of the most recent and competitive baselines, across all considered benchmarks. We stress that most of the considered baselines employ similar Graph Transformer backbones (as discussed in Sec 2.1) and therefore share comparable computational characteristics. To make our analysis more complete, we have now extended our computational analysis to include sampling-time measurements in Table 7. Regarding the additional datasets, we are not aware of flow-matching-based graph generation methods evaluated on OGBG-molhiv or OGBG-molpcba. Therefore, considering the limited time available during the rebuttal period, we opted to extend our evaluation to the more commonly adopted QM9 and Proteins benchmarks (also suggested by the Reviewer), allowing for a more direct comparison with existing graph generative models. We report these additional results and evaluation metrics in Appendix B.4. Regarding the models suggested by the Reviewer (i.e., [1, 2, 3, SPECTRE]), we note that these methods differ from ours in terms of generative framework and state space, and more importantly our contribution focuses on the denoiser architecture. Under the denoiser network’s lens, GSDM GDSS and GGSD all share the same building blocks that we analyze in our manuscript, i.e., they employ a Transformer architecture as backbone, without them being explicitly designed to provide stable and non dissipative node-mixing. The denoising architectures inside these frameworks hence suffer from the problems that we discussed in our work (Sec 2.3).

Importantly, we note that, under this light, our orthogonal transport operator is not tied to any specific generative framework. It could, in principle, replace the denoising networks and node-mixing operators in the mentioned works. In fact, we consider this as an interesting future work, as the application of our operator could play a decisive role in score-based denoising networks where the flow of gradients at large depths is particularly important.

Regarding further empirical evaluation: we note that SPECTRE performance was already included in the original version of the manuscript (Synthetic benchmark results, Table 1). Following the reviewer’s suggestion, we now included GSDM and GDSS on ZINC (Table 2) and SPECTRE, GDSS, GGSD, GSDM on QM9 benchmark (Table 8), in order to allow for a better comparison and broader evaluation. We also included the discussion above of the pros and cons in Sec 2.1.


We hope these clarifications and revisions address the Reviewer’s concerns, and we would be grateful if they would consider reassessing their evaluation and score based on the updated text and the above comments.

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

This work studies the representation collapse in deep graph transformer architectures. By using mathematical notions of spectral analysis and dynamical systems (complemented by demonstrative examples) the authors show how graph transformers and the softmax attention mechanism can collapse node representation to a rank-one state as depth increases. To resolve this issue they propose replacing the softmax attention with a Cayley-parameterized orthogonal transformation. This forces the eigenvalues of the network's jacobian to lie strictly within the unit cycle preventing rank collapse. The model is evaluated on planar and sbm synthetic networks as well in two molecular datasets (moses and zinc) that show that it is immune to represention collapse and decreased performance in graph generation tasks.

Critical strengths
  • The proposed mechanism to replace the softmax self-attention mechanism is simple in nature and guaranteed to prevent rank collapse as depth increases. This is demonstrated in practice by the experiments.
  • The introduction of the γ\gamma damping parameter allows for controlled ingestion of dissipative dynamics enabling an elaborate ablation study to support the main claim.
Critical weaknesses
  • The orthogonal transport is essentially an all-pass filter and prevents any non-uniform scaling. This might restrict the expressiveness of the model in certain power-law and locally triangle-dense networks. Works like "Simplified graph convolution with heterophily" from Chanpuriya & Musco essentially allow adaptive spectral filtering.
  • The proposed architecture is evaluated on graph generative tasks. The issue of representation collapse in those tasks by increased depth is in my opinion less of a concern than in other learning tasks (node classification, link prediction, graph clasisification) as one can easily do a binary search on the optimal depth L evaluating on the quality of the generated networks to the original network.
  • The experiments limit to two types of synthetic networks and molecular networks that have a size of very few nodes ~10-40 overall where even using a depth of L=32 is questionable in the first place for networks that do not require a large receptive field due to small size and diameter (latter is of course a property of large networks as well).
Questions for authors
  • Has this architecture been studied in other downstream learning tasks?
  • Why is the performance of DeFoG on L=32 missing from table 2?
  • Could there be /have the authors experimented with some relaxation of the model that allows for non-uniform scaling?
4 comments
AuthorsOpenReview ↗

Response 1/2

We thank the Reviewer for their thoughtful comments and constructive feedback. We appreciate their recognition of the simplicity of the proposed mechanism, its guarantee to prevent rank collapse, and the controlled introduction of dissipative dynamics through the damping parameter, enabling an elaborate ablation study supporting our main claim. We address their concerns below and hope these clarifications will help improve their assessment towards acceptance.

W1. We thank the Reviewer for the comment and note that our primary goal is not to maximize the expressiveness of the transport operator, but rather to investigate the benefits of stable, non-dissipative dynamics for graph generation. While we agree with the reviewer that orthogonality may reduce the expressiveness of the transport operator, we emphasize that SGT achieves strong, state-of-the-art results across the considered benchmarks, including competitive FCD and ratio scores, suggesting that orthogonal transport does not significantly limit its effectiveness in practice. We believe that incorporating more expressive transport operators that also preserve the stability properties of our SGT is an interesting direction for future work, which we now discuss in the conclusion of the updated manuscript. In this respect, the work of Chanpuriya & Musco, which focuses on adaptive spectral filtering for node classification, without providing the non-dissipative propagation guarantees that motivate our approach, nor addressing graph generation through flow matching, could represent an interesting starting point.

W2. We respectfully disagree that representation collapse is less concerning in graph generative tasks. As discussed in Sec. 2.3, standard self-attention progressively contracts node representations as depth increases, leading to representation collapse and vanishing gradients. These phenomena directly affect the ability of the denoiser to preserve node-specific information and effectively propagate gradients during training, ultimately degrading graph generation quality. While we agree that the optimal depth can be selected through hyperparameter tuning, this does not address the underlying issue. Rather, it limits the model to depths at which these phenomena are less severe, preventing it from effectively exploiting the additional capacity and receptive field offered by deeper architectures. Our goal is precisely to overcome this limitation by introducing a stable, non-dissipative transport mechanism that preserves information propagation as depth increases. Importantly, our experiments show that SGT outperforms standard Graph Transformer denoisers even at shallower depths, suggesting that the benefits of non-dissipative dynamics are not restricted to very deep architectures. Finally, while we agree that the proposed approach could also be beneficial for other graph learning tasks, our work specifically focuses on understanding and addressing the limitations of Graph Transformer denoisers for graph generation through flow matching. We therefore consider evaluating the core idea behind SGT on node classification, link prediction, and graph classification an interesting extension, but outside the scope of the present work.

AuthorsOpenReview ↗

Response 2/2

W3. We would like to clarify that the motivation for increasing depth in Graph Transformers is not primarily related to enlarging the receptive field. Unlike standard message-passing GNNs, Graph Transformers employ global self-attention, allowing any pair of nodes to exchange information within a single layer, regardless of graph size or diameter. Increasing depth instead enables the composition of more complex nonlinear transformations, potentially improving the denoiser's ability to capture complex structural dependencies. Our experiments support this motivation: increasing SGT's depth from 8 to 32 improves the Ratio on Planar from 2.63 to 1.32 and the FCD on ZINC250k from 0.94 to 0.85, while standard Graph Transformer denoisers progressively degrade. Similar trends are present in all our experiments. Therefore, we believe that the benefits of deeper architectures should not be assessed solely in terms of the receptive field required by the underlying graphs.

Finally, we note that the considered benchmarks are not limited to graphs with 10–40 nodes as shown in the table below and in Table 3 (App.B.2).

DatasetType# graphstrain / val / testNodes mean ± stdNodes min–maxEdges mean ± stdEdges min–maxnode typesedge types
planarsynthetic200128 / 32 / 4064.0 ± 0.064–64177.8 ± 1.8173–18111
sbmsynthetic200128 / 32 / 40104.0 ± 37.444–187500.4 ± 211.6129–1,12911
zincmolecular249,455224,568 / 24,887 / 24,88723.2 ± 4.56–3824.9 ± 5.35–4593
mosesmolecular1,936,9621,584,663 / 176,225 / 176,07421.7 ± 2.38–2723.3 ± 2.87–3184
protein (new)real graphs918587 / 147 / 184257.9 ± 105.5100–500646.4 ± 282.8186–1,57511
qm9 (new)molecular130,83197,734 / 20,042 / 13,0558.8 ± 0.51–99.4 ± 1.20–1444

These are established benchmarks for graph generation, following the experimental setting of DeFoG and related works.

Q1. As already discussed in W2, our work specifically focuses on understanding and addressing the limitations of Graph Transformer denoisers for graph generation through flow matching. While the proposed approach could potentially be extended to other graph learning tasks with appropriate modifications, evaluating its effectiveness beyond graph generation is outside the scope of the present work and represents an interesting direction for future research.

Q2. In Table 2 at L=32L=32, DeFoG suffers from severe vanishing gradients, preventing the model from training effectively. This is consistent with the behavior observed on the synthetic benchmarks (Table 1), where DeFoG at L=32L=32 achieves 0% V.U.N. Consequently, we omitted the molecular generation results at this depth, as the model failed to train.

Q3. We thank the Reviewer for this suggestion and we highlight that our architecture already incorporates a damping parameter (γ0\gamma_0) that allows us to relax the orthogonality constraint and progressively introduce dissipative dynamics. As shown in Proposition 3.2, increasing γ0\gamma_0 moves the eigenvalues of the transport operator inside the unit circle, allowing different model behaviors. We have already explicitly investigated this relaxation in Appendix B.5, where we evaluate γ0∈{0,0.5,1,4}\gamma_0 \in \{0, 0.5, 1, 4\}, i.e., from a stable to a more dissipative behavior (see Fig. 3a). The results show that increasing dissipation consistently degrades generation quality, supporting our choice of non-dissipative transport γ0=0\gamma_0=0.


We hope these clarifications and revisions address the Reviewer’s concerns, and we would be grateful if they would consider reassessing their evaluation and score based on the updated text and the above comments.

Dear Reviewer,

As the rebuttal discussion period is approaching its end, we would like to kindly follow up on our responses and the additional results and clarifications provided.

We would appreciate hearing whether our responses have addressed your concerns or if there are any remaining points you would like us to clarify. We would be happy to discuss them further and hope you might reconsider supporting the acceptance of our work in light of the new evidence.

Best regards,

The Authors

Reviewer_3eBdOpenReview ↗

thanks for the detailed response

I would like to thank the authors for their response. I agree that the emphasis of the work is to highlight the dissipative dynamics of existing graph transformers and the negative effect they have on graph generative tasks. Thanks, also for the clarification and the distinction between the receptive field of standard GNNs and the global attention and non-linear composition of graph transformers. With this in mind I am leaning towards raising my score to 3. However, I still consider that the introduction of an operator that only allows for rotations needs further exploration, as the evaluation is performed on few and rather small graphs.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.