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.
Alex: A small weight change can have a large effect inside a graph neural network. A new training method accounts for that mismatch and reaches a fixed training target faster in most tested settings.
Sam: Faster training claims depend heavily on what counts as finishing. What did these researchers actually improve?
Alex: They measured time to a specified validation loss: error on held-out data. Their method beat AdamW, a widely used training rule, in thirteen of fifteen model-and-dataset combinations. This is an arXiv method paper by Guy Hadad and colleagues at Ben-Gurion University of the Negev, titled “Module-Aware Optimization for Graph Neural Networks.”
Sam: So this is for people training models on connected data, rather than a new way to build those models?
Alex: Yes. It changes the optimizer—the rule that adjusts model weights—not the network architecture. For graph-learning researchers, that could mean less time reaching a useful model. We’ll unpack the mismatch it addresses, the evidence for faster training, and where the extra machinery may not help.
Sam: Start with the mismatch. Why would the same weight change behave differently in a graph network?
Alex: A graph neural network mixes information across connected nodes. In the layer studied here, that mixing happens before a learned weight matrix transforms the features. So the weight matrix receives features already shaped by the graph.
Sam: Meaning the optimizer cannot judge an update just by inspecting the weights it changes?
Alex: That is the authors’ argument. The immediate effect depends on multiplying the propagated features by the weight update. If those features have much more energy in some directions, an update aligned with those directions can cause a much larger output change.
Sam: The document illustrates a balanced graph beside a hub-dominated graph. Is the point that identical updates can behave differently because the inputs have different shapes?
Alex: Yes, as an illustration. The graph and feature statistics jointly determine that shape. The authors show a fixed update producing a moderate change in one setting and an amplified change in another. They are not claiming that hub structure alone determines the outcome.
Sam: But adaptive optimizers already adjust their updates. What is missing from AdamW, and from the method this builds on?
Alex: AdamW adjusts individual parameter coordinates using gradient statistics. It does not explicitly measure which directions graph-propagated inputs amplify. The closest predecessor, Muon, treats a weight matrix as a structured object and balances its update directions, but still without looking at the inputs.
Sam: What does “balances” mean here? I want to distinguish the new idea from simply changing learning rates.
Alex: Muon uses approximate orthogonalization: making matrix directions perpendicular under a chosen measurement rule. This gives the update more balanced singular values, which describe its strength along different matrix directions. But Muon uses ordinary matrix geometry regardless of which module receives the update.
Sam: So GraphMuon changes the measurement rule to match the layer. What information does it need?
Alex: It uses the covariance of the propagated inputs—a matrix summarizing feature energy and joint variation. This identifies directions where a weight change has a strong immediate effect. GraphMuon uses that information both to choose the update direction and to set its size.
Sam: Those sound like separate interventions. How does each one work?
Alex: First, it transforms Muon’s momentum update into the input-defined geometry, orthogonalizes there, and transforms back. Then it rescales the direction according to the representation change it would induce. The first component changes the direction; the second calibrates the step.
Sam: Does it use the same covariance measurement for both jobs?
Alex: With an important distinction. For choosing directions, the authors remove average feature energy, keeping the relative shape. For sizing the step, they retain the raw feature scale. Otherwise, they would discard the very amplification they want to control.
Sam: That sounds plausible, but a plausible adjustment is not necessarily a principled optimizer. What do they establish mathematically?
Alex: They prove that the step normalization bounds the induced change in the layer’s pre-activation representation, relative to the update direction’s size. They also show that an ordinarily normalized Muon update can attain graph-induced amplification. So the mismatch is not merely a loose theoretical possibility.
Sam: And the direction change itself—is that justified, or only the final rescaling?
Alex: They justify that too, for an idealized exact version under rank and dimension assumptions. It is the counterpart of Muon’s polar update in the graph-defined geometry. The implementation approximates that operation, so the exact mathematical result and the practical algorithm should remain distinct.
Sam: Let’s move from controlled update sizes to useful training. How did they make the speed comparison fair?
Alex: Within each dataset-and-architecture pairing, optimizers shared the backbone, training budget, and evaluation protocol. The main target was the lowest mean validation loss AdamW achieved across seeds. They measured when each optimizer’s mean trajectory first reached that target, including cumulative training time.
Sam: So this is faster arrival at AdamW’s reference loss, not necessarily faster arrival at every possible endpoint.
Alex: That is the right scope. On the large-scale Open Graph Benchmark node tasks, GraphMuon reached that target about 1.3 to 2.4 times faster than AdamW. The evaluation also included molecular graph classification, graph regression, and attention-based architectures, where the model learns how to weight connections.
Sam: Faster loss reduction would be less attractive if the final predictions got worse. What happened there?
Alex: The authors report competitive or superior predictive performance overall, not uniform improvement. In the selected cross-architecture test comparisons, GraphMuon had the best numerical result in most settings. It remained close to AdamW on the attention-based citation-network model.
Sam: Can they tell whether the gains come from changing direction or just keeping the output changes under control?
Alex: Their component ablation compares each intervention separately against vanilla Muon. Step normalization produced larger gains than direction adjustment alone on the main large-scale benchmarks. Combining them performed best there. Those ablations use a different target, derived from Muon’s validation loss, so their speedups should not be mixed with the main comparison.
Sam: Computing a covariance and transforming matrices costs time. Does the method save epochs but lose the savings in overhead?
Alex: Sometimes. GraphMuon needed fewer epochs throughout the expanded evaluation, but was slower in elapsed time on Citeseer with a graph convolutional network and on ZINC with GraphGCN. The authors explicitly connect those exceptions to overhead relative to the underlying training cost.
Sam: What keeps that overhead manageable on the larger problems?
Alex: They reuse propagated features from the forward pass, rather than running graph propagation again. They estimate covariance from sampled nodes and cache its matrix decomposition. In a large-scale profiling configuration, GraphMuon added about three percent to Muon’s per-step runtime. That is one profile, not a universal overhead estimate.
Sam: What is the more fundamental limitation, beyond implementation cost?
Alex: The covariance has to be informative and reasonably stable. On small graphs, especially with wide hidden representations, it can be low-rank and noisy. Controlling the immediate representation change then does not necessarily improve convergence or generalization. The authors say AdamW can remain competitive because it does not depend on estimating this graph-level covariance.
Sam: Given those boundaries, who should read the full document, and where should they begin?
Alex: Researchers training graph networks should start with the main validation-loss comparison and the component ablation. Then read the implementation-efficiency discussion to judge whether the overhead fits their workload. Optimizer designers should begin with the theoretical properties section, especially the distinction between controlling step size and changing geometry.
Sam: And for someone outside graph learning, what is the idea worth carrying away?
Alex: An update is not small just because the weight change is small. Judge it by what the receiving layer does with it.
Sam: A useful question to bring to your next training run.