Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variants

Gangda Deng (University of Southern California (SSO)) · Hongkuan Zhou (University of Southern California) · Rajgopal Kannan (Army Research Lab) · Viktor Prasanna (University of Southern California)

disparityempirical analysis expressivitygeneralization preferencesgnn architecturesgnn depthgraph neural networksheterophilous graphshomophilymixture of scope expertsmoscatperformance degradation receptive field theoretical analysis

Heterophilous graphs, where dissimilar nodes tend to connect, pose a challenge for graph neural networks (GNNs). Increasing the GNN depth can expand the scope (i.e., receptive field), potentially finding homophily from the higher-order neighborhoods. However, GNNs suffer from performance degradation as depth increases. Despite having better expressivity, state-of-the-art deeper GNNs achieve only marginal improvements compared to their shallow variants. Through theoretical and empirical analysis, we systematically demonstrate a shift in GNN generalization preferences across nodes with different homophily levels as depth increases. This creates a disparity in generalization patterns between GNN models with varying depth. Based on these findings, we propose to improve deeper GNN generalization while maintaining high expressivity by Mixture of scope experts at test (Moscat). Experimental results show that Moscat works flexibly with various GNN architectures across a wide range of datasets while significantly improving accuracy.