Sharpness-aware Zeroth-order Optimization for Graph Transformers

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.

Authors

• Yang Liu College of Computer Science, Sichuan University Engineering Research Center of Machine Learning and Industry Intelligence, Ministry of Education
• Chuan Zhou University of Michigan
• Yuhan Lin Bestpay AI Lab
• Shuai Zhang New Jersey Institute of Technology
• Yang Gao Nanjing University
• Zhao Li Key Laboratory of Computing Power Network and Information Security, Ministry of Education, Shandong Computer Science Center (National Supercomputer Center in Jinan), Qilu University of Technology (Shandong Academy of Sciences) Evay Info
• Shirui Pan Griffith University, Queensland, Australia

Keywords

• Data Mining: DM: Mining graphs
• Data Mining: DM: Theoretical foundations of data mining