TL;DR
GraphMuon is a novel optimizer tailored for Graph Neural Networks (GNNs) that adapts parameter updates to the specific geometry of graph-propagated data. By accounting for how graph structure amplifies or attenuates feature changes, it achieves significant training speedups—up to $2.4\times$ faster wall-clock time—while maintaining or even improving predictive accuracy.
What Problem Does This Paper Address?
Standard optimizers like Adam or the more recent matrix-aware Muon treat weight matrices as isolated operators. However, in a GNN, a weight matrix $W$ acts on representations $X_g$ that have already been transformed by the graph's topology (e.g., through neighborhood aggregation).
This means the "effective" input geometry is shaped by the graph. A weight update that looks small in "parameter space" might actually cause a massive, unintended jump in the "representation space" if it aligns with the graph's dominant features, such as hub nodes. This mismatch between the optimizer's geometry and the model's actual forward pass leads to inefficient training and unstable updates.
Methods
GraphMuon extends the Muon optimizer (which uses orthogonalized matrix updates) by making it "graph-aware" through two primary mechanisms:
- Graph-aware Orthogonalization: Instead of standard Euclidean orthogonalization, GraphMuon performs updates in a metric space defined by the covariance of the graph-propagated inputs ($C_g$). This ensures that the update direction respects the underlying distribution of features as seen by that specific layer.
- Graph-aware Step Normalization: It scales the learning rate based on the actual perturbation induced in the layer's output ($\|X_g \Delta W\|_F$), rather than just the magnitude of the weight change itself. This prevents the "graph-induced update amplification" that plagues standard methods.
The algorithm reuses activations from the forward pass to estimate these statistics efficiently, keeping the computational overhead low.
Datasets
The authors evaluated GraphMuon across 15 different dataset-architecture configurations to ensure broad applicability:
- Large-scale Node Classification: OGBN-ARXIV, OGBN-PRODUCTS, and OGBN-MAG.
- Heterophilous Graphs: The QUESTIONS benchmark.
- Inductive Graph Classification: Molecular benchmarks OGBG-MOLBACE and OGBG-MOLTOX21.
- Graph Regression: The ZINC dataset.
- Transductive Node Prediction: Classic benchmarks like Cora and Citeseer.
Key Insights and Ideas
- The Geometry Mismatch: The core "aha" moment is the realization that graph propagation acts as a "pullback" of the output-space geometry. Standard optimizers are essentially "blind" to this transformation, leading to updates that are poorly calibrated for GNNs.
- Provable Amplification: The authors theoretically prove that even "well-behaved" matrix-aware updates (like those from vanilla Muon) can be significantly amplified by the graph's dominant eigenvalues. GraphMuon is designed specifically to cancel out this effect (see Theorem 1 in the paper).
- Module-Awareness: This work pushes a broader principle in deep learning: the geometry used by an optimizer should depend not just on the shape of a parameter tensor, but also on the module in which that parameter appears.
Key Results
- Significant Speedups: On large-scale OGB benchmarks, GraphMuon achieved wall-clock time-to-target speedups of $1.32\times$ to $2.42\times$ over AdamW.
- Consistent Performance: Across 15 configurations, it reached the target validation loss in fewer epochs in every single case and achieved faster wall-clock convergence in 13 of them.
- Improved Generalization: In several instances, GraphMuon achieved superior test performance (e.g., on OGBN-MAG and ZINC), suggesting that its principled updates provide a beneficial inductive bias for GNN training.
Limitations and Future Work
- Small Graphs: On very small graphs, the estimated covariance matrix can be noisy or low-rank. In these regimes, the graph-aware metric might be poorly estimated, and standard methods like AdamW remain highly competitive.
- Mini-batch Variability: For small inductive tasks, the noise introduced by mini-batching might dominate the benefits of graph-aware normalization.
- Future Directions: The authors suggest adapting the "strength" of graph-awareness dynamically based on the reliability of the covariance estimate (e.g., using effective rank or spectral anisotropy). There is also potential to extend this "module-aware" optimization principle to other specialized architectures beyond GNNs.
Summary updated