Generalizing GNNs with Tokenized Mixture of Experts
This addresses the problem of deploying robust and generalizable GNNs for practitioners, though it is incremental as it builds on existing methods like mixture-of-experts and tokenization.
The paper tackles the tradeoff between stability and generalization in static graph neural networks (GNNs) by proposing STEM-GNN, a framework that uses a mixture-of-experts encoder, tokenized interface, and regularization to achieve a stronger balance, improving robustness to distribution shifts and corruptions while remaining competitive on clean graphs across nine benchmarks.
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.