PaperlayerView exact revision on arXiv

Source-linked AI summary

Stable Transformers for Graph Generation

Luca Miglior, Alessio Gravina, Davide Bacciu

arXiv:2609.39739v1cs.LG

TL;DR

Deep Graph Transformers offer greater expressive capacity and wider receptive fields, but repeated self-attention can weaken node-specific information. The paper studies this through spectral dynamics, introducing non-dissipative transport and a damping control; across synthetic and molecular benchmarks, the non-dissipative advantage grows with depth.

  • Problem

    Deeper Graph Transformers are intended to increase expressive capacity and information reach, but repeated self-attention can reduce node-representation diversity needed to reconstruct graph structure.

    Source: §1 · pp. 1–2

  • Method

    The paper introduces a permutation-equivariant Graph Transformer with non-dissipative transport and a damping mechanism that varies contraction while retaining the rest of the architecture.

    Source: §1 · p. 2, §3.3 · p. 6

  • Results

    Across synthetic and molecular benchmarks, the advantage of non-dissipative dynamics grows with depth, while deeper contractive denoisers degrade and eventually collapse.

    Source: §5 · pp. 9–10

  • Takeaways & Limitations

    The results identify denoiser spectral dynamics, not architectural capacity alone, as a key determinant of whether depth strengthens or undermines graph generative models.

    Source: §5 · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

The introduction asks whether a deep Graph Transformer’s behavior is determined by its layer dynamics, since depth can expand receptive fields while node-specific information fades. It presents non-dissipative transport and controlled dissipation as ways to study how these dynamics relate to graph generation.

  • Greater depth expands receptive fields, but over-smoothing, over-squashing, and vanishing gradients can weaken long-range communication and node-specific information.The paper asks how much a deep Graph Transformer’s behavior is determined by the dynamical regime of its layers.Source: §1 · p. 1
  • Standard self-attention contracts node representations across depth, attenuating differences between nodes and contributing to information loss and vanishing gradients.The paper connects these dissipative denoiser dynamics to graph generation quality.Source: §1 · pp. 1–2
  • The trajectory illustration contrasts standard denoiser states converging to one point with orthogonal transport that preserves norms and keeps node states distinct.Source: Figure 1 · p. 2
  • A Cayley-transform node-mixing operator provides non-dissipative, permutation-equivariant transport as a drop-in modification that preserves the training objective and sampling procedure.The paper also controls dissipation in discrete flow matching and reports that the advantage of non-dissipative dynamics grows with depth.Source: §1 · p. 2

2 BACKGROUND AND RELATED WORK

The background describes discrete flow matching and the Graph Transformer denoisers used to parameterize graph-state evolution. It then frames information propagation through Jacobian dynamics and reviews how increasing depth can contract node representations.

2.1 DISCRETE FLOW MATCHING FOR GRAPH GENERATION

  • Discrete flow matching generates graphs through a continuous-time Markov chain, with a denoiser trained to predict clean-state marginals for nodes and edges.The study uses DeFoG’s training objective and CTMC generation framework to examine denoiser dynamics across depth.Source: §2.1 · p. 3
  • Softmax attention makes each head’s node-mixing matrix row-stochastic, so heads form convex combinations of node values.This averaging behavior motivates analyzing how attention transforms representations across depth.Source: §2.1 · p. 3

2.2 EFFECTIVE INFORMATION PROPAGATION

  • Jacobian singular values below one attenuate perturbations and promote vanishing gradients, while eigenvalues inside the unit circle can indicate dissipative dynamics and information decay.The related-work discussion notes that whether these spectral effects arise in graph generative models and how depth affects denoising remained largely unexplored.Source: §2.2 · pp. 3–4

2.3 DEEP GRAPH TRANSFORMERS SUFFER FROM RANK-COLLAPSE

  • For SGT, Figure 3 shows increasing γ moving the Jacobian spectrum from the unit circle into increasingly contractive regimes.Its second panel reports Jacobian singular values at L = 32 for SGT and the GT proposed by Qin et al. (2025).Source: Figure 3 · p. 5
  • For the Vignac et al. (2023) GT, increasing depth drives Jacobian eigenvalues toward zero, indicating stronger contraction and difficulty propagating gradients and preserving node-specific information.Figure 2 shows the Jacobian spectra across layer counts; related work connects token alignment and graph propagation contraction with rank collapse and gradient loss.Source: §2.3 · pp. 4–5, Figure 2 · p. 4

3 CONTROLLING GRAPH TRANSFORMER DYNAMICS

The section introduces a graph-dependent, non-dissipative Graph Transformer based on orthogonal transport, then adds damping to vary its contraction while retaining the rest of the architecture.

3.1 S-GRAPH TRANSFORMER

  • The S-Graph Transformer replaces standard contractive node mixing with graph-dependent orthogonal propagation built from skew-symmetric attention scores and a Cayley transform.This construction is designed to provide non-dissipative dynamics.Source: §3.1 · p. 5

3 CONTROLLING GRAPH TRANSFORMER DYNAMICS

  • The design uses orthogonal node propagation and channel mixing to preserve signal norms throughout the network.The section frames a near-orthogonal Jacobian as a way to preserve forward and backward gradient norms while retaining graph-dependent interactions.Source: §3 · p. 5, §3.2 · p. 6

3.2 GUARANTEES OF ORTHOGONAL TRANSPORT

  • Its node-transport Jacobian is orthogonal under the stated fixed-input conditions, so compositions preserve perturbation and backpropagated-gradient norms across depth.The guarantee applies to the attention submap on active nodes, with edge and global inputs fixed.Source: §3.2 · p. 6
  • The Cayley-based construction preserves permutation equivariance because node relabeling conjugates the attention scores, skew-symmetric generator, and Cayley map consistently.The remaining channel-wise and node-wise operations commute with relabeling.Source: §3.2 · p. 6

3.3 CONTROLLING SGT DYNAMICS

  • A nonnegative damping parameter shifts the skew-symmetric matrix before the Cayley transform, interpolating from orthogonal transport toward increasingly contractive dynamics.γ0 = 0 recovers orthogonal transport; larger values increase contraction, and γ0 controls spectral attenuation across depth without changing the rest of the architecture.Source: §3.3 · pp. 6–7

4 HOW DOES DISSIPATIVITY AFFECT GRAPH GENERATION?

The experiments compare depth and dynamical regime in a flow-matching setup, finding that non-dissipative SGT increasingly outperforms contractive baselines on synthetic and molecular generation tasks. Trained Planar models also show that SGT preserves node-representation diversity across depth while the baseline collapses.

4 HOW DOES DISSIPATIVITY AFFECT GRAPH GENERATION?

  • The study varies denoiser depth and dissipation within DeFoG’s discrete flow-matching framework, retaining its training objective and CTMC sampling procedure.It evaluates synthetic and molecular tasks using structural-validity and distributional-agreement metrics.Source: §4 · p. 7

4.1 SYNTHETIC GRAPH GENERATION

  • From L = 16 onward, SGT outperforms DeFoG on Planar and SBM; at L = 32, DeFoG reaches 0.0% V.U.N. while SGT has its lowest Ratio on both.Table 1 reports graph-generation metrics on 40 generated graphs.Source: Table 1 · p. 8, §4.1 · p. 8
  • On Planar, SGT’s Ratio falls from 10.22 at L = 8 to 1.32 at L = 32, continuing to improve after V.U.N. reaches 100.0% at L = 16.SBM Ratio also improves overall; at L = 32 it reaches 1.05.Source: §4.1 · p. 8

4.2 MOLECULAR GRAPH GENERATION

  • On ZINC and MOSES, deeper SGT improves distributional fit while preserving high validity, whereas deeper DeFoG degrades on these measures.On ZINC, SGT FCD falls from 0.94 at L = 8 to 0.85 at L = 32; on MOSES, its L = 32 FCD is 1.10.Source: Table 2 · p. 9, §4.2 · p. 9

4.3 RELATING DEPTH GAINS TO REPRESENTATION DYNAMICS

  • Across Planar model depth, the baseline approaches representation-collapse limits, while SGT preserves Dong residual and effective rank, especially in the deep regime.The passage links the preserved diversity to SGT's best generation quality in the deep regime.Source: §4.3 · p. 9

5 CONCLUSION

The conclusion attributes deep Graph Transformer denoisers’ failures to increasingly contractive self-attention and presents SGT’s non-dissipative transport as an alternative. Across the reported benchmarks, deeper SGT continues to benefit while increased damping degrades generation quality.

5 CONCLUSION

  • Standard self-attention becomes increasingly contractive with depth, with vanishing gradients and collapse of node-specific information.These dynamics motivate the proposed alternative.Source: §5 · p. 9
  • SGT uses permutation-equivariant Graph Transformer architecture with intrinsically stable, non-dissipative transport.The conclusion reports that increasing damping progressively degrades generation quality.Source: §5 · p. 10
  • Across synthetic and molecular benchmarks, deeper SGT benefits while deeper contractive denoisers degrade and eventually collapse.The reported gains align with sustained gradient flow and preserved node-representation diversity.Source: §5 · p. 10

A PROOFS FOR THE S-GRAPH TRANSFORMER

The proof appendix states the conventions and conditions used for the paper’s orthogonality and conditioning claims.

A PROOFS FOR THE S-GRAPH TRANSFORMER

A.1 PROOF OF THEOREM 3.1

The proof establishes that the conditional node-transport Jacobian is orthogonal and that its layerwise products preserve perturbation and gradient norms.

A.1 PROOF OF THEOREM 3.1

  • Theorem 3.1 states that the attention submap’s node Jacobian is orthogonal when edge and global inputs are fixed.The claim is restricted to active nodes and uses the attention scores in the attention branch.Source: §A.1 · p. 16
  • Because products of orthogonal layer Jacobians remain orthogonal, perturbation and backpropagated-gradient norms are preserved at every depth.The proof obtains the layer Jacobian through an orthogonal Cayley-transform head update.Source: §A.1 · p. 16
  • Orthogonality gives singular values of one and eigenvalues with magnitude one for the conditional Jacobian.Source: §A.1 · p. 16

A.2 DAMPED SPECTRUM AND COMPOSITION BOUNDS

The damped Cayley transport has unit singular values without damping and becomes contractive with positive damping. Composition bounds quantify how damping and depth constrain node propagation, subject to stated conditions.

Damped spectrum

  • For each eigenvalue iω of K, Rγ has eigenvalue rγ(ω); its singular value is 1 at γ = 0 and below 1 at γ > 0.The result follows from the normality of Rγ, which makes its singular values equal the moduli of its eigenvalues.Source: §A.2 · p. 17

Composition bounds

  • With scores and conditioning fixed, damped layer Jacobians and their depth-wise composition obey singular-value bounds; the stated depth-scaled choice is γ = γ0/L.The composition result assumes orthogonal channel and cross-head mixing; the excerpt states the bounds for 0 ≤ γ < 2.Source: §A.2 · pp. 17–18

Padding and damping range

  • Padding is decoupled with identity action, and the positive lower bound requires γ < 2, although contractivity holds for every γ > 0.The stated assumptions concern active coordinates, fixed layer parameters, and a conditional Jacobian with edge and global inputs held fixed.Source: §A.2 · p. 18

A.3 PERMUTATION EQUIVARIANCE

The Cayley-based SGT transport preserves node-permutation equivariance through the denoiser stack. With dropout, equivariance holds in distribution when dropout masks are relabeled along with the graph.

Graph-state action

  • A graph permutation sends node features and masks through P and edge channels through PE::cP⊤, preserving the active-node count and mask identities.The node mask marks active nodes and padding; detachment changes no forward values or permutation identities.Source: §A.3 · pp. 18–19

Permutation equivariance

  • SGT is permutation equivariant, and with dropout enabled its output is equivariant in distribution when masks are relabeled with the graph.The proof assumes shared nodewise and pairwise parameters, feature-channel LayerNorm, and permutation-invariant global readouts.Source: §A.3 · pp. 18–19

Node transport

  • Relabeling conjugates the attention scores and generator, so the Cayley transport and subsequent head, channel, and bias operations preserve the node permutation.The full denoiser remains equivariant through its shared maps, invariant readouts, residuals, normalization, and layer scalars.Source: §A.3 · p. 19

B ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS

The appendix details SGT's unconditional global conditioning and the baseline models used for comparison. Experiments reuse DeFoG's released training and sampling hyperparameters across models and depths.

B ADDITIONAL EXPERIMENTAL DETAILS AND RESULTS

  • DeFoG and SGT use the public DeFoG implementation and released training and sampling hyperparameters at every depth, with SGT differing architecturally.The appendix also reports additional molecular metrics and a damping-parameter ablation.Source: B ADDITIONAL EXPERIMENTAL DETAILS AND… · p. 20
  • SGT conditions each layer on graph-level features recomputed from the noisy graph, including node and cycle counts, molecular weight on molecular datasets, and flow time.Runs are unconditional; the time embedding and graph-level vector set rotation angles and add a node-update bias, while the edge stream retains baseline FiLM modulation.Source: B ADDITIONAL EXPERIMENTAL DETAILS AND… · p. 20

B.1 EMPLOYED BASELINES

  • The employed baselines span autoregressive and recurrent, spectral and hierarchical, GNN-diffusion, and Graph Transformer diffusion or flow models.Named examples include GraphRNN, SPECTRE, EDP-GNN, DiGress, and DeFoG.Source: §B.1 · p. 20

B.2 ADDITIONAL METRICS

Across the additional molecular evaluations, deeper SGT improves reported distributional and structural metrics, while DeFoG's FCD worsens with depth. SGT also uses fewer parameters than matched-depth standard GT and remains trainable at MOSES L = 32.

B.2 ADDITIONAL METRICS

  • MOSES Test FCD decreases from 0.793 to 0.705 as SGT deepens, while Test SNN rises from 0.587 to 0.600 and filter pass rate from 99.02% to 99.21%.Scaffold similarity also increases on both Test and TestSF; the passage gives no numeric values for those increases.Source: §B.2 · pp. 20–21
  • DeFoG Test FCD worsens from 0.818 to 1.129 and TestSF FCD from 1.339 to 1.676; at L = 16, SGT has lower FCD and higher SNN on both splits.At that depth the models have the same filter pass rate.Source: §B.2 · p. 21
  • On ZINC250k, SGT Test FCD decreases from 0.943 to 0.851 and SNN increases from 0.434 to 0.452 as depth rises from L = 8 to L = 32.Scaffold similarity rises from 60.38% to 66.37% with 16 layers; fragment similarity and internal diversity increase slightly.Source: §B.2 · p. 21, Table 4 · p. 21
  • SGT uses 11.4–15.8% fewer parameters than matched-depth standard GT with comparable or lower per-epoch times, and remains trainable when the MOSES L = 32 baseline fails.The baseline failure is attributed to vanishing gradients.Source: §B.2 · p. 21, Table 6 · p. 22

B.3 ABLATION ON THE EFFECT OF γ0

At L = 32, the non-dissipative model performs best on both datasets, and increasing damping progressively worsens generation quality.

B.3 ABLATION ON THE EFFECT OF γ0

  • At fixed L = 32, only γ0 varies; γ0 = 0 gives exactly orthogonal transport, while increasing γ0 induces progressively stronger dissipation.Table 7 reports SGT V.U.N. (%) across 40 generated graphs.Source: §B.3 · p. 22, Table 7 · p. 23
  • The non-dissipative model is best on both datasets, and no amount of damping improves on it.The authors conclude that dissipation degrades deep graph generation, motivating the non-dissipative regime.Source: §B.3 · p. 23
  • On Planar, V.U.N. decreases from 100.0% to 95.0% as γ0 grows to 4; on SBM, any damping lowers it from 92.5% to 90.0%.Source: §B.3 · p. 23

Related papers

Loading 2609.39739v1…