Sharpness-aware Zeroth-order Optimization for Graph Transformers

Yang Liu, Chuan Zhou, Yuhan Lin, Shuai Zhang, Yang Gao, Zhao Li, Shirui Pan

Abstract

Graph Transformers (GTs) are powerful but notoriously difficult to train because they often rely on non-differentiable operators. This paper introduces SZO (Sharpness-aware Zeroth-order Optimizer), a novel optimization framework that uses gradient-free estimation combined with "sharpness-aware" techniques to navigate complex loss landscapes. SZO enables the integration of powerful non-differentiable structural features, resulting in more robust models that generalize better on molecular graph tasks.

Introduction

Graph Transformers have revolutionized graph-structured data processing by using global attention to capture long-range dependencies. However, a significant bottleneck exists: many effective structural features—such as shortest-path distances or graph rewiring—are inherently non-differentiable. Traditional gradient-based optimizers like Adam require differentiability throughout the model, forcing researchers to either simplify their models or find complex workarounds for these "Challenge Operators."

The Graph Transformer architecture incorporating non-differentiable "Challenge Operators" and the optimization objective of finding a flat loss landscape.

The Challenge of Non-Differentiability

Zeroth-Order Optimization (ZOO) provides a potential solution by estimating gradients using only forward passes, bypassing the need for backpropagation through non-differentiable layers. However, vanilla ZOO is highly sensitive to "sharp" loss landscapes, where minor parameter changes lead to significant error spikes. This sensitivity often results in poor training stability and weak generalization.

Proposed Method: SZO

To address these limitations, the authors propose SZO, which integrates ZOO with Sharpness-Aware Minimization (SAM).

  1. SZO Algorithm: Instead of merely seeking the global minimum, SZO identifies a "flat" neighborhood in the loss landscape. It utilizes a two-step gradient estimation process: the first identifies the descent direction, while the second ensures the parameters converge to a region where the loss function is stable.
  2. Gradient Estimators: The framework supports two estimators: a Coordinate-wise Gradient Estimator (CGE) for individual parameter perturbation and a Randomized Gradient Estimator (RGE) for sampling random directions in parameter space.
  3. Parallelized Acceleration: To mitigate the computational cost of multiple forward passes, the authors implemented forward parallelization, allowing parameter perturbations to be computed simultaneously across multiple GPUs.
  4. Sparsity Constraints: A top-K operator is incorporated into the attention mechanism to focus on significant activations, further optimizing computational efficiency.

Experimental Results

The researchers evaluated SZO using two Graph Transformer backbones, GROVER and CoMPT, across nine benchmark datasets from MoleculeNet. The results demonstrate that SZO consistently outperforms standard Adam, vanilla SAM, and basic ZOO.

Comparison of SZO against baseline models and other optimizers on graph classification tasks (ROC-AUC).

On the BBBP classification task, CoMPT+SZO achieved a 0.964 ROC-AUC, significantly improving upon the base CoMPT (0.948). In regression tasks, such as ESOL, CoMPT+SZO reached a state-of-the-art RMSE of 0.505. Ablation studies confirmed that the "Sharpness-aware" component is critical; while vanilla ZOO often underperformed relative to SGD, SZO provided a substantial boost in both accuracy and stability.

Discussion and Conclusion

The success of SZO highlights that for Graph Transformers, the geometry of the loss landscape is as crucial as the absolute minimum. By prioritizing flatness, the model becomes more resilient to the inherent noise in graph data. Furthermore, SZO proves that Zeroth-Order methods are viable for large-scale GTs when combined with proper sharpness constraints and parallelization.

While SZO introduces higher computational overhead due to the required forward passes, it removes the non-differentiability barrier, allowing for more expressive graph modeling. Future work will focus on scaling SZO to massive graphs and refining perturbation schedules to accelerate convergence.

Summary updated

Abstract

Graph Transformers (GTs) have emerged as powerful tools for handling graph-structured data through global attention mechanisms. While GTs can effectively capture long-range dependencies, they introduce difficulties in optimization due to their complex, non-differentiable operators, which cannot be directly handled by standard gradient-based optimizers (such as Adam or AdamW). To investigate the above issues, this work adopts the line of Zeroth-Order Optimization (ZOO) technique. However, direct integration of ZOO incurs considerable challenges due to the sharp loss landscape and steep gradients within the GT parameter space. Under the above observations, we propose a Sharpness-aware Zeroth-order Optimizer (SZO) that combines Sharpness-Aware Minimization (SAM) technique facilitating convergence within a flatter neighborhood, and leverages parallel computing for efficient gradient estimation. Theoretically, we provide a comprehensive analysis of the optimizer from both convergence and generalization perspectives. Empirically, we conduct extensive experiments on various classical GTs across a wide range of benchmark datasets, which underscore the superior performance of SZO over the state-of-the-art optimizers.
BibTeX
@inproceedings{liu2025sharpness,
  author = {Yang Liu and Chuan Zhou and Yuhan Lin and Shuai Zhang and Yang Gao and Zhao Li and Shirui Pan},
  title = {{Sharpness-aware Zeroth-order Optimization for Graph Transformers}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2025},
  doi = {10.24963/ijcai.2025/348},
}
Figure