Generalizing GNNs with Tokenized Mixture of Experts

Xiaoguang Guo, Zehong Wang, Jiazheng Li, Shawn Spitzel, Qi Yang, Kaize Ding, Jundong Li, Chuxu Zhang

Abstract

Deployed graph neural networks (GNNs) are frozen at deployment yet must fit clean data, generalize under distribution shifts, and remain stable to perturbations. We show that static inference induces a fundamental tradeoff: improving stability requires reducing reliance on shift-sensitive features, leaving an irreducible worst-case generalization floor. Instance-conditional routing can break this ceiling, but is fragile because shifts can mislead routing and perturbations can make routing fluctuate. We capture these effects via two decompositions separating coverage vs selection, and base sensitivity vs fluctuation amplification. Based on these insights, we propose STEM-GNN, a pretrain-then-finetune framework with a mixture-of-experts encoder for diverse computation paths, a vector-quantized token interface to stabilize encoder-to-head signals, and a Lipschitz-regularized head to bound output amplification. Across nine node, link, and graph benchmarks, STEM-GNN achieves a stronger three-way balance, improving robustness to degree/homophily shifts and to feature/edge corruptions while remaining competitive on clean graphs.

Introduction

In real-world production environments, Graph Neural Networks (GNNs) are typically deployed as "frozen snapshots"—static models that do not update their parameters between releases. However, these models encounter an "impossible triangle" of requirements: they must simultaneously perform well on clean data, generalize to new distributions (OOD generalization), and remain stable against input noise (perturbations).

Standard static GNNs face a fundamental theoretical limit. To achieve robustness against noise, a static model must ignore "shift-sensitive" features, which inherently limits its ability to generalize to new distributions. While instance-conditional computation, such as Mixture-of-Experts (MoE), can break this floor by adapting computation paths, the routing mechanism itself is often fragile. Small amounts of noise can cause the model to "flip" its routing decision, leading to significant fluctuations in the final prediction.

Methodology: The STEM-GNN Framework

To navigate this tradeoff, we introduce STEM-GNN (Stable TokEnized Mixture-of-Experts GNN). The framework employs a three-pronged approach to ensure flexible computation does not come at the cost of fragility:

  1. MoE Encoder for Coverage: Instead of a single message-passing rule, the model uses a Mixture of Experts. A router selects a soft mixture of shared expert operators for each node, allowing the model to adapt its computation path to specific graph characteristics.
  2. VQ Tokenization for Stabilization: To prevent jittery routing, a Vector-Quantized (VQ) interface maps continuous embeddings from the encoder to a discrete codebook of tokens. Small perturbations that do not cross a quantization boundary result in zero change to the prediction head, effectively absorbing noise.
  3. Lipschitz-Regularized Prediction Head: To handle cases where noise causes a token switch, Lipschitz regularization (a Frobenius penalty) is applied to the final head. This mathematically bounds how much upstream variation can be amplified at the output.
The STEM-GNN architecture overview, illustrating the flow from input graph through MoE coverage expansion, VQ stabilization, and bounded amplification.

Experimental Results

STEM-GNN was evaluated across nine diverse benchmarks, including node classification (Cora, PubMed, Arxiv, WikiCS), link prediction (WN18RR, FB15K237), and graph classification (HIV, PCBA, ChEMBL).

Performance and Stability

STEM-GNN achieved the best average performance across all benchmarks (80.79%), outperforming both standard GNNs (GCN, GAT) and specialized OOD methods (GFT, MARIO). The model demonstrated particular strength in "OOD-high" scenarios, such as high-degree nodes in citation networks.

In stability tests involving feature masking and edge deletion, STEM-GNN maintained the strongest accuracy trends compared to baselines, showcasing graceful degradation as noise levels increased.

Accuracy trends under feature masking and edge deletion on the Cora dataset, showing STEM-GNN's superior stability compared to baselines.

Conclusion and Future Work

STEM-GNN successfully breaks the stability-generalization tradeoff by combining instance-conditional routing with stabilizing discretization. While current limitations include a fixed expert capacity and a frozen codebook after pre-training, the framework provides a robust path forward for GNN deployment. Future research will explore adaptive expert allocation and online codebook refinement to handle long-term temporal drift.

Summary updated

Abstract

Deployed graph neural networks (GNNs) are frozen at deployment yet must fit clean data, generalize under distribution shifts, and remain stable to perturbations. We show that static inference induces a fundamental tradeoff: improving stability requires reducing reliance on shift-sensitive features, leaving an irreducible worst-case generalization floor. Instance-conditional routing can break this ceiling, but is fragile because shifts can mislead routing and perturbations can make routing fluctuate. We capture these effects via two decompositions separating coverage vs selection, and base sensitivity vs fluctuation amplification. Based on these insights, we propose STEM-GNN, a pretrain-then-finetune framework with a mixture-of-experts encoder for diverse computation paths, a vector-quantized token interface to stabilize encoder-to-head signals, and a Lipschitz-regularized head to bound output amplification. Across nine node, link, and graph benchmarks, STEM-GNN achieves a stronger three-way balance, improving robustness to degree/homophily shifts and to feature/edge corruptions while remaining competitive on clean graphs.
BibTeX
@misc{guo2026generalizing,
  author = {Xiaoguang Guo and Zehong Wang and Jiazheng Li and Shawn Spitzel and Qi Yang and Kaize Ding and Jundong Li and Chuxu Zhang},
  title = {{Generalizing GNNs with Tokenized Mixture of Experts}},
  year = {2026},
  eprint = {2602.09258},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.09258},
}
Figure