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 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).
- 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.
- 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.
- 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.
- 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.
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