Module-Aware Optimization for Graph Neural Networks

Guy Hadad, Haggai Roitman, Moshe Eliasof, Bracha ShapiraarXiv 2026 · arXiv

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.

Motivation for graph-aware optimization. A fixed parameter-space update can yield vastly different effects depending on the graph structure.

Methods

GraphMuon extends the Muon optimizer (which uses orthogonalized matrix updates) by making it "graph-aware" through two primary mechanisms:

  1. 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.
  2. 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.
Empirical validation showing that GraphMuon tightly controls representation-level perturbations compared to vanilla Muon.

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.
Training dynamics on OGBN-MAG showing GraphMuon reaching higher accuracy in significantly fewer epochs.

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

Abstract

Different optimizers impose different geometries on parameter updates. Adaptive methods such as Adam and AdamW use coordinate-wise updates, while matrix-aware optimizers such as Muon utilize weight-matrix structure through orthogonalized updates. For Graph Neural Networks (GNNs), however, the effective geometry of its weight matrices is shaped not only by its learned channel-mixing weights, but also by the graph-propagated representations it acts on. Thus, even if an update is well normalized as a matrix, its effect on the layer output can be amplified when applied to graph-propagated features. To address this gap, we introduce GraphMuon, a graph-aware optimizer that adapts Muon's matrix updates to the covariance structure of graph-propagated layer inputs. GraphMuon performs orthogonalization in a metric defined by these propagated representations and normalizes step sizes according to the update's induced effect on the layer representation. We show that theoretically, vanilla Muon can suffer from graph-induced update amplification, while our GraphMuon can mitigate this effect. As such, our GraphMuon yields a graph-metric analogue of Muon's polar update step. Empirically, GraphMuon achieves $1.32\times$-$2.42\times$ validation-loss time-to-target speedups over AdamW on three large-scale OGB benchmarks. Across 15 dataset-architecture configurations spanning node classification, inductive graph classification, and graph regression, it achieves lower time-to-target in 13 cases, while maintaining competitive or superior predictive performance. Code is available at https://github.com/guy-hadad/GraphMuon.
BibTeX
@misc{hadad2026module,
  author = {Guy Hadad and Haggai Roitman and Moshe Eliasof and Bracha Shapira},
  title = {{Module-Aware Optimization for Graph Neural Networks}},
  year = {2026},
  eprint = {2611.08379},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.08379},
}
Figure