Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variants
Authors: Gangda Deng
Hongkuan Zhou
Rajgopal Kannan
Viktor Prasanna
Venue: NeurIPS 2025 poster ()
Keywords: heterophily
deeper GNNs
mixture of experts
Primary area: deep_learning

Abstract: 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.

Mixture of Scope Experts at Test: Generalizing Deeper Graph Neural Networks with Shallow Variants
Gangda Deng
Hongkuan Zhou
University of Southern California
University of Southern California
Los Angeles, USA gangdade@usc. edu
Los Angeles, USA hongkuazZusc. edu
Rajgopal Kannan
Viktor Prasanna University of Southern California
DEVCOM ARL Army Research Office Los Angeles, USA rajgopal kannan. ci civearmy.m. mil
Los Angeles, USA prasannalusc.eda
Abstract
Heterophilous graphs, where dissimilar nodes tend to connect, pose 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 the- oretical and empirical analysis, we systematically demonstrate shift in GNN generalization preferences across nodes with different homophily levels 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 GNNs across a wide range of datasets while significantly improving accuracy. Our code is available at httpt:///iithubb.. http:/gghhh...omo/////ss/ss/////
Introduction
AONCOK
Graph neural networks (GNNs) are emerging as powerful tools for graph mining applications, such as social recommendelictionn (17) traffic predic- tion (27.. and fraud detection [49 GNNs' superior performance is largely attributed to graph homophily, where similar nodes tend to be connected. However, some graphs exhibit het- erophily, where connected nodes tend be dissimilar. When aggregating het- erophilous information, GNNs tend to generate similar embeddings for nodes of different classes, leading to subopti- mal performance.
Actuanyy GWail
Off GRNY
GNMU
butter
-306
0.
shallow GHiN better
0.50 3.75
0.50
Figure 1: Performance amazon-ratings. Deeper GNNs exhibit performance disparities across node subgroups with different homophily ratios, with the shaded area indicating the node distribution. (Right) Deeper GNNs and their shallow variants show shift generalization preference across homophily ratios, with the red dotted line indicating the average training set homophily (0.38).
(Left)
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

To find homophily on graphs where heterophily dominates, GNNs need to search for neighbors from higher hops. Typically, GNN with L layers of propagation can perceive the entire L-hop neighborhood for each node, making the scope (i.e., receptive field) size tightly coupled with the GNN's depth. However, a persistent challenge is that GNNs experience performance degradation as they become deeper. Studies have shown that deeper GNNs suffer from three key issues: reduced expressivity due to over-smoothing [32] 72), model degradation from optimization challenges [80 and large generalization gaps caused by overfitting 773. While many techniques have been proposed to address the first two issues, these solutions often sacrifice generalization 13 resulting in limited overall performance improvements.
Existing theoretical analyses of deeper GNN generalization adopt a purely global perspective [3] 64]. which overlooks the diversity of local structural patterns (c.g.. homophily) that appear in real-world graphs. For example, Figure [ (left) shows that variations in homophily can induce substantial performance discrepancies for deeper GNNs. Recent work has moved toward more realistic assumptions by modeling graphs as mixtures of node subgroups with varying homophily levels 45 39]. However, these theories are restricted to one- two-layer GNNs and thus fail to reveal the generalization behavior of GNNs with increasing depths.
To address this gap, we derive a new PAC-Bayesian generalization bound, which reveals a shift in model generalization preferences across nodes with different homophily levels as depth increases. This provides a new understanding of deeper GNNs' failure: while deeper GNNs achieve better generalization than their shallow variants either homophily or heterophily region, they sacrifice generalization performance in the other region, thus limiting overall performance. Figure (right) demonstrates the generalization preference shift with increasing depth in woal-world data.
These insights motivate us to learn the generalization patterns of GNN experts with varying depths with a gating model, which can combine the advantages of
Forward Bockwarrd
Ohop Expert
hop Export
Whss 2 hop Expert Traising
soft Scoping during Export Training
Scoping during
Training
Expert Training
l
both shallow and deeper GNNs. We first
MLP Layer
MUP Layer
GMN
examine existing approaches to handle GNN depth, which can be broadly cat- egorized into two paradigms: "Deeper GNN" and "Graph MoE" (FigureZlefuy "Deeper GNN" typically uses skip con- nections to mix embeddings from differ- ent scopes, while "Graph MoE" stacks varying numbers of GNN layers as ex- perts for their corresponding scopes. These methods use gating mechanisms
GNN Layor
Layer
GNN Layer
GNN Layer
VZ
GNN Layer
Expert Logits
Gating Model
Goting Model
Gating Model
VC
Goting Training
Deeper
(b) Graph
MOSCAT
Figure 2: The landscape of GNNs with scope mixing.
to mix knowledge from different scope experts and impose soft scoping: while each expert encodes only its own scope during forward propagation, gradients from higher-hop information still flow back to the shallow experts through the gating model. Although this can be expressive, shallow experts tend to overfit noise from higher-hop neighbors, resulting in suboptimal performance. For empirical evidence, please refer to Appendix G.5
To address this issue, we propose a new paradigm that decouples the gating module from GNN training. As illustrated in gating model learns to node-adaptively combine predictions from shallow experts to enhance the generalization of the deeper expert. This enforces hard scoping: each expert can only learn from the knowledge available in its specific scope. Notably, the gating model should be trained on a holdout set to accurately measure the generalization preference of experts.
we first train each expert independently. Then, a specialized
Based on this paradigm, we develop concrete method named Moscat: Mixture of scope experts at test-a a post-procee post-processing attention-basse gating model that seamlessly integrates with various GNN architectures to exploit depth. We further develop two techniques: seerophill-bbassee sample filtering and scope-aware logit augmentation to address technical challenges in scope expert mixing (detailed in Section 4). Our main contributions are summarized as follows:
novel paradigm: We propose a novel decoupled expert-gating paradigm that learns generalization patterns of GNNs with different depths, supported by our theoretical analysis.

---

Superior flexibility: Moscat detects various patterns of expert failure, enabling better gating that significantly improves performance across various GNN architectures.
SOTA performance:
Moscat outperforms state-of-the-art GNNs, Graph Transformers, and Graph MoEs across wide range of datasets with varying sizes and homophily ratios.
2
Preliminaries
We denote a graph as 9 (V, with node set V [=)]== edge set & C V. Nodes are associate with node feature matrix X E R VIxF and one-hot class label matrix Y E R By Nr we denote the neighbors of v, which is the set of nodes directly connected to V. Let A be the adjacency matrix, D be the diagonal degree matrix and A D- AD- be the normalized adjacency matrix, where A + D, = D I, and I the identity matrix. Further preliminary details and related work are in Appendix C and
Node Homophily. Homophily metrics are widely used as graph properties to measure the probability of nodes with the same class connected to each other. In this paper, we mainly use a nise-wise homophily metric called node homophily [52] It defines the fraction of neighbors that have the same class for each node u: Hu E N₂ Vu- Ve Jol//NNl
Node subgroup. The nodes in graph can be divided into non-overlapping node subgroups, with each subgroup containing nodes that share similar properties (e.g.. node homophily).
3
Understanding Generalization Disparity across GNN Scope Experts
3.1 Unpacking the Depth Dilemma: Why Do GNNs Struggle with Generalization?
Existing studies have proved that deeper GNNs are more expressive [50 25
48 [0]. In practice,
however, performance degradation is widely observed when going deep. Unlike previous studies that attribute the failure of deeper GNNs to single cause, we argue that this failure stems from multiple factors, varying based on GNN architectures. To analyze each factor separately, we break down the error of deeper GNNs on unseen samples. Let F denote the function class for given deeper GNN architecture, and fs J denote a function learned on the training set S. The population risk (true risk) of Is over the entire data distribution can be decomposed as:
R (Js)) = Rs (JS,ERM) + R& (Js) - i&s (JS,ERN) + R(Js) - fts (Js); representation envor
optimization error
generalization error
where Rs the empirical risk (training error) and fs. fS.ERM is the empirical risk minimizer. In the following, we discuss these errors and connect them with recent findings: (1) Representation error measures the minimum error over the function class F on S, evaluating the expressive power of
the GNN architecture, A major factor limiting deeper GNNs' expressivity is over-smoothing [32) where node representations become indistinguishable after multiple GNN layers. Recent studies (8) show that GNNs without -inearii between propagation layers (e.g.. SGC) tend to suffer from over-smoothing. (2) Optimization error depicts how well fs trained by calculating the risk difference between the learned model Is with the empirical risk minimizer Js, ES. Research shows that deeper GNNs encounter significant training difficulties 41 and exhibit model degradation (80) as depth increases, leading to decreased accuracy in both training and testing. The primary cause is gradient- related issucs such as vanishing gradients [30] and gradient instability [13]. These problems can be mitigated through optimization tricks like ciip-connctiooss. (3) Generalization error measures how well the trained model fs generalizes from the training set to the true distribution. The overfitting 773 3 issue has been identified to explain why well-trained deeper GNNs with higher expressivity failed to outperform their shallow variants. To address this issue, existing works typically reduce GNN parameters or employ regularization techniques.
While useful, existing solutions face inherent trading-offs between these three types of errors (See Appendix for detailed analysis). Given these theoretical limitations and the ineffective use of depth in practice, crucial question emerges: Is it possible to enhance the generalization capabilities of deeper GNNs without compromising their expressivity increasing training difficulty?
3

---

3.2 Subgroup Generalization Bound for GNNs with Varying Scopes: A Data-Centric Perspective
To investigate this question, we conduct theoretical analysis of how GNNs generalize at different depths. Rather than focusing on model architecture [3]. we take a data-centric perspective to understand generalization across diverse local structural patterns. Recent work [45 39] has shown that real-world graphs comprise node subgroups with varying homophily levels, causing GNNs to exhibit generalization discrepancies across these subgroups. However, these studies only focus on simplified GNNs with one or two layers, which fails to explain deeper GNNs' failure. Though deeper GNNs have superior expressivity and may generalize better specific subgroups, these improvements often get obscured by overall performance degradation. To rigorously analyze generalization disparity with respect to GNN depth and examine the role of homophily, derive new generalization bound for multi-layer GNNs by extending [45] is non-i.i.d. PAC-Bayesian analysis on GNNs with one-hop adopt the contextual stochastic block model (CSBM) with 2 classes for a controlled study, which is widely used for graph analysis 4 677.
aggregation. Following the assumptions used in (45]
Assumption 3.1 (CSBM-Subgroop dataset). The generated nodes consist of two disjoint sets C1 and C2 of the same size. The features for nodes belonging to C1 and C2 are sampled from N N(1,; I) and (J2, I), respectively. Each set consists of M subgroups. Each subgroup m, appears with probability Pr(m), has probabilities of intra-class edge p(m) and inter-class edge ((m) = - ((m)
The dataset can be denoted as (11,, p2, (Pm 9m Pr(m))(mmm IM M=))
Since the key distinction between deeper neural networks and deeper GNNs is the expansion of scopes, we use SGC as our GNN model. SGC decouples scope enlargement from the addition of linear transformations. allowing us to specifically analyze how varying scopes impact generalization.
Assumption 3.2 (GNN model).
We use the following architecture:
fd (g" (X, 9); W(), w ((()))),,W(())) where g²
denotes an L-hop mean aggregation function and f is ReLU-activated L' L'-layer MLP with hidden dimension d.
The following theorem is based on the PAC-Bayes analysis with margin loss [4 12]. bound the generalization gap between the expected loss CD. (0) of test subgroup for 0 margins and the empirical loss (0) on train subgroup S for a margin ?
We aim to
Theorem 3.3 (GNN Subgroup generalization bound). Assume the aggregated features (Xx,))
share the same variance I Let 9 be any classifier in the parameter set ( li=1 and S denote the training set. For any test subgroup m E (1.... ........ .M} and large enough number of the training
modes Ns [Vsl, with probability at least 1 8 over the sample {yo JeEss there exists 0 < a
we have:
c (0) - (3(()) 50 (0 (em + plps - Pm) P2-1) + +
[W] (cm) )2/2 0
In(1/5)
Ng
N20
where ||W||2 = Σn'
ii=1 Will P = 1| -ell is feature distribution separability, cm max minreVs 1|9 ( (X (x(XX9)) 10 is the bound of the aggregated feature distance, (p. go) represents L-hop homophily coefficient.
and D Tz-1 = B oE (E M}
Proofs and details are in Appendix B With sufficiently large training set Ns. the bound is dominated by the first term. has the following properties. Prop.1: The generalization error for each subgroup m depends on the aggregated feature distance Em well as the homophily ratio difference ps Pm- Prop.2: Consider any two subgroups and j where p; > ps and p5 < ps. respectively. Due to the decay of [I'zi1l when increasing L. the minimum achievable generalization error occurs different depth for these two subgroups. Prop.3: Varying L yields a larger disparity in generalization error on heterophilous graphs (where rz-1 [-1, 1)) than on homophilous graphs (where Iz-1 E [o, 1)).
Theorem 3.3 suggests that varying the depth shifts the GNN generalization pattern across subgroups. This creates notable disparity in subgroup generalization between shallow and deeper GNNs, especially on heterophilous graphs. particular, the generalization disparity emerges between test partitioned by the average homophily ratio of training set.
subgroups with low and high

---

3.3 Performance Disparity across Scope Experts on Real-World Datasets
In this subsection, we empirically examine our theoretical analysis from multiple perspectives. First, we use Jaccard Coefficient to calculate the overlapping ratio of correctly predicted test nodes between each pair of depths. Figure Bl (Top) shows that all overlapping ratios are relatively small, indicating that each variant can correctly predict unique subset of nodes. The ratio between deeper and shallow variants is even lower. On Penn94, GCN models with depth L 2 2 deviates from its shallow vari- ants, while GAT shows deviation greater depths (L 2 5). Second, we further com- pare the performance of deeper and shallow GNNs across node subgroups with different ho- mophily levels. As shown in Figure I (Right), shallow and deeper GNN variants exhibit a sig- nificant generalization disparity between sub- groups partitioned by the average homophily ratio of training set. Third, we examine the significance of the observed generalization dis- parity. Since training randomness can lead to performance variations, we compare the union of nodes correctly predicted by (1) models of different depths and (2) models with the same depth but different random seeds. Figure (Bot- tom) demonstrates that the performance gains from increased depth significantly exceed those from training stochasticity, particularly on the heterophilous graph (amazon-ratings com- pared to the homophilous graph (PubMed). We defer additional empirical evidence and analysis to Appendix G.9
LH0
5-12
1.12
1.00
5:22
0.17
LKD
3.75
3.00
022
0.81
0.74
8:13
Lx2
8.72
7.5
3.00
0.55
0.7
3.53
0.45
6.66
0.22
1.30
2.65
3:78
611
LCC
0.15
6:4
0.27
8.74
L-5
8:55
857
6.64
L-2
1-4
L-6
L-1
02
Sktn (11
Figure 3: (Top) The overlapping ratio on Penn94. (Bottom) Test accuracy under Oracle ensemble. Multi-Scope represents the ensemble of GNNs with depths ranging from L 0 (MLP) n (n < 6). Fixed-Scops represents the ensemble of GNNs with identical depth L Loeat. The horizontal red dotted line shows the SOTA GNN accuracy.
In summary, our theoretical and empirical anal-
ysis provides a new understanding of GNNs' depth dilemma: Increasing GNN depth enhances generalization for certain subgroups but inevitably compromises generalization for others, leading to suboptimal overall performance. This insight demonstrates the value of combining predictions from deeper and shallow GNN models during inference an approach that improves overall generalization while maintaining expressivity and avoiding additional training complexity.
4 Proposed Method: GNN-Moscat
Moving from the paradigm (Figure 2 right) practical implementation, several technical challenges emerge: (1) Feature construction. Although node homophily is strong identifier for experts' generalization disparity (Section (32),, it's not available during testing. (2) Training sample selection. The training set for experts is noisy for training the gating model since experts can all achieve high accuracy on the training set but cannot generalize equality well. (3) Diverse expert architectures. Expert failures may stem from complex reasons Suush as over-smoothing, model degradation (underfitting). and overfitting (Section 3.1 that vary across different expert architectures.
We introduce Moscat, a post-processing gating model for scope experts that successfully addresses these challenges. Figure 4 presents an overview of our proposed method. 4.1 presents the overall model and 4.2 discuss the properties.
4.1 The MoE Workflow
Scope Experts Training, Different depth GNN models serving as experts of their corresponding scope is a hot topic in recent Graph MoE research 6] consider the number of propagation layers as depth while keeping the transformation layers fixed. Formally, given a GNN architecture M and the maximum number of layers 7 T we independently train Lmax + 1 models {M' .... ...,. M with depth from 0 to Lmax, where M is an MLP.
78 75 For decoupled GNNs like SGC, we
5

---

Scope-Aware Logit Augmentation (for Expert L)
Node Homophilly Distribution
Training
Expert d: MLP
Legite
Sample Patering
Logits
Repart i GHN [Lx1]
Legghts
After thtrrig
Filtored
Label Embeedingg
Encoding
Pegetfark
Lineur W
Litew W;
MLP
Expert Lioas shi (.t.ndd)
Legits
Two +1
Liteor W....
Scope Experts Training
Heterophily-Biaseed Sample Filtering
Gating Model
G
W
Softrax
Training
Figure 4: Overview of Moscat. (1) Different-depth GNN models serve as scope experts (with MLP as 0-hop), each trained independently. (2) Collect logits from each expert by running inference on the expert-training set Veep and a holdout set Vhoia, then perform heterophily- biiaee filtering to form the gating-training set V gate.. (3) Enhance logits with label embeddings and structural encoding. (4) Train the gating model using node labels, with learnable parameters shown in yellow blocks.
Holdout Set for Gating Model. Let Vesp denote the training set for the experts. To understand how experts generalize, we reserve holdout set Vhola from the labeled data for training the gating model 6, ensuring Veep n Vnold = Ø. To expand the gating model's training data, we may optionally include a subset of Veep to form the final gating training set Vinte S Veep U Vhold-
Heterophily-Bianne -Biased Sample Filtering. However, samples in Vexp can be noisy for gating model training, which fall into two categories: (1) Samples that are underfitted or properly fitted by all experts are ideal for & training, as they accurately reflect each expert's 's performance. (2) Samples that are overfitted by some experts become problematic for & training since á will mistakenly assign high weights to the overfitted experts for that subgroup. Importantly, we notice that experts tend to overfit to heterophilous nodes Vexp-hes. This is because heterophily nodes exhibit more diverse neighborhood label patterns than homophily nodes, making them more challenging for experts to generalize (See Appendix G.6p. To address these cases, we introduce a hyperparameter 7 E [o, 1J that randomly filters out samples in Veep-het- We also add binary hyperparameter to determine whether to use Veep
for gating training. We denote the node sample dropped from Veep as Vesp-drop E (Vesp: Vesp-her )-
Additionally, certain nodes present a particular challenge where all experts fail to make correct predictions. These difficult samples Van willwwroggg S Vexp U Vhola. found primarily in the heterophily region, fall into two categories: (1) Cases where individual experts make incorrect predictions, but their logits still contain valuable structural patterns that contribute to task prediction. (2) Cases where all experts generate meaningless predictions, either due to inherent dataset noise or architectural limitations. To address both scenarios, we introduce binary hyperparameter to control the masking of these samples Vwr-drop E (Vall-wrong, Ø }.. The final training set for the gating model Φ is:
Vgatt == (Vhold U (Vexp') ' Vexp-drop)) \ Vwr-drop
(3)
Scope-Aware Logit Augmentation. Expert logits serve as a crucial input for the gating model, encoding both structural information and the expert's 's confidence. However, experts may suffer from overfitting, showing strong confidence despite poor generalization. Theorem 33. shows that experts' generalization capability across subgroups can be identified by node homophily, which is defined as the similarity between a node's own label distribution and its neighborhood's s label distribution. We extend this concept to higher-hop neighbors and approximate it using pscudo-label distribution. Let (1) denote the logits for expert M We propose label embeddings to augment M logits with pseudo neighborhood label distribution from to Lmax hops: <lub
[ ( | ... Ä Lmix (mixz()) (1a)
When expert lacks expressivity, it can suffer from over-smoothing as depth increases. To help identify when over-smoothing happens in experts, we augment their logits with structural encoding, incorporating node smoothness and centrality. Let ( = L represent node features smoothed within the scope size L. We measure its distance from both the original feature (() = X and the
final smoothed feature (x)) Á x X, where Age (d, + 1)² (d. + 1)² /2| + |D 32). For
each node v, we calculate two distance scalars E! xx(") x!!0 (0) l|a and (11) ||x_! (L) x (c0 1

---

to measure smoothness. We also incorporate PageRank centrality Re to encode node position. The structural encoding can be represented Eame (E(L)
E(() ||. Finally, we combine these
components form the overall augmented logits for expert M ((L) (z() Elabel (saue)
where (()) E X Fan and Faug = C + max C' 0++
..... Gating Model Training. Taking the augmented logits from all experts as input , (( }. train the gating model on gaee, using node labels Y. Figure illustrates the architecture of our gating model ø. Moscat uses an attention- -batid gating mechamism to calculate weight JL,v for expert on node v. Find denotes the hidden dimension and WL L E R Fm Fin a. E R Rid, W mix E RR +1) +1m are learnable weights. Notably, it's crucial to separate transformation weights WL and as for each expert. Since experts may suffer from over-smoothing and overlitting to varying degrees, each expert favors a specific combination of predefined structural patterns in ç(P), Formally,
gL- Sigmoid (Hzag), H2 ReLU (<u)W)). L {0, Lmax):
[90: ;9t... = Sof tmax ([9o) ; I.... Wiix))
gr. E IR. VI is the node-adaptive gating weights for expert L. Then, the knowledge from all experts to make predictions Y f (Eien diag (gL) Empirically, we find out that using a simple MLP as f(-) performs best compared to more complex models like GNNs or Transformers. For the gating model optimization, we employ the same loss function used to train the experts In this paper, we focus on the node classification task, therefore, we adopt the cross
classifier f()) combine
entropy loss (CE) to train the gating model: L = E.
CE
(Ó(()) ( Y, 1L
4.2 Discussion and Analysis
Runtime and space analysis. Moscat is lightweight module with relatively small training time and memory consumption. Please refer to Appendix G.2 and G.3 for detailed analysis.
Comparison with LLM MoEs. Unlike LLM Moïs with joint training. Moscat employs separate "rainn-then-merge" strategy for GNN experts. Please refer to Appendix E for details.
Comparison with ensemble methods. Ensemble methods typically require extensive tuning of models with varying hyperparameters and architectures. In contrast, Moscat focuses on a controlled study of scope/depth effects by using identical architecture and hyperparameters across all experts.
5 Experiments
In this section, we aim to answer the following questions to verify the effectiveness of Moscat. Q1: How does Moscat perform in improving GNNs with varying architectures? Q2: How does Moscat compare to other techniques in enhancing deeper GNNs? Q3: How does each component of Moscat contribute its overall performance? To understand why Moscat is effective, we further conduct case study at the end of this section and defer other in-depth experimental analyses to the Appendix: Appendix G.7 investigates how expert training affects Moscat performance, Appendix G.8 provides a visual interpretation of how Moscat enhances GNN generalization, and Appendix G.10 analyzes AH's learned gating weights of different scope experts.
5.1 Experimental setup
Datasets.
We evaluate Moscat on real-world datasets with varying node homophily ratios and graph sizes. We exclude commonly used small heterophilous graphs (fewer than thousands of nodes) due to their high variance and lack of statistical significance [53] Please see Appendix F.T for details.
Evaluation Setup. We assess model performance on node classification task using test accuracy (ROC-AUC on genius). We adopt two sample splits for our method: (1) Moscat*. We split the training set into two disjoint subsets-oa one for training the GNN experts Veep and another for the holdout set Vhota- The split ratio serves as tunable hyperparameter, and we do not use the original
validation set for expert/gate training. (2) Moscat. Following prior work [29 62 we leverage the
7

---

Table I: Moscat exhibits large improvements various base GNN architectures. Each *-Moscat (+) combines predictions from 7 base GNN models with O (MLP) to 6 convolution layers. We report the best accuracy among these base GNN models as baselines.
Equizzel
saag-patezta
arxiv-yoar 0. 0.6M
Flicks
anazoa-rat ingo
PannBG
geal'us
ogtu-arxiv
NNodls
2321
2.9M
80250
24492
40000
0.4M
0.16M
Ang.. Improv.
VEdges
46996
13M
1.2M
0.89M
93050
1.3M
1M
2.3M
Node Houso.
0.16
0.28
0.51
0.64
MLP
58,57 9:199
31.13 4000
37.25 60.30
47.48
20:99
41.85 60.77
74.63 -0:30
86,80
+0,07
55.68
21
SGC
40.04 1:1777
48.71 20.10
45.88 50.33
52.07
20.15
49.58
20.55
81.17 -1:00
88.01
+00.00
71.89
=0.10
302-Yoscat+
42773 #22006
55.45
+0007
52.09 d0.27
53.78
20.07
51.82
6:.29
54.75 =0:41
92.31
4:000
73.31
=0.10
6.05%
43,35
$1.97
55,16
10.06
51.86
1- 90
54.40
-0.11
52.72
10.53
84.80
01:40
92.29
10.00
73,94
-0.23
6.53%
GCN
41.33 81.46
50.79 60:16
48.65
60.34
55.52
20.36
48.55
10.18
82.54 00:43
90.22
10.77
72.13 10:17
OCN CON-
42.1
55.29
52.58
57.33
51,02 40.50
85,51
92.37
73.37
=0.14
4.25%
52.25
85,76
4.96%
GAT
39.36
44.45 H0.M
52.77
49.78 10:47
81.81
72.01
GAT-Noccat+
2:011
$2.56 10.40
=11.0
-0.07
6.29%
DAT-Moucat
#2.03
54.77
$:000
56.06
6:033
58.52
53.77 1:.51
00.90
1:0.31
74.13 00117
6.99%
49.18
60023
51.75
$2.45
+:057
82.34 =0.51
90.41
=0:17
GON -Moocata
43,61 8.218
$4.86
15
$4.60
1:004
57.45
20:21
$3.99 1.0.1M
85.33
11:30
92.36
1.0.07
73.33
3.59%
OCHII- MBRII-Moccat
43.71
1:1.85
$4.55
160.16
55.10
1:045
57.95
20.16
$4.38
3:0.59
$5.66
-0.50
92.38
1.0.08
74.13 0.22
4.05%
AUMGEN
35.00
2.2.56
48,90
15.15
45.45
2:0.5
54.51
20.32
53.57
4:042
83.38
0044
64.74
3:5.55
71.85 00.41
42.81
4:200
$5.04
+00.0
50.72
1:022
56.40
-0.44
56.03
10.50
85.79
00:23
91.90
10.84
73.25 00
f 11.97%
+2.78 =2,00
54.84
1:010
50.82
1:015
56.81
20:23
$6.36
20.52
$6.03
00333
91,91
1:0.15
73.79 =0.20
1 12.28%
Table 2: Moscat achieves new sfate-of-thh-ar results with proper base GNNs. For each dataset, GNN-Moscat( reports the highest accuracy obtained by selecting its base GNN from GAT, MixHop, GCNII and ACMGCN (see Table B). Graph MoE baselines are likewise tuned over their respective supported GNN architectures. The top 1st 2nd and 3rd results are highlighted.
Type
Model
anaprpa
arxiv-ywa:
Flickr
Pece
oghomarzsiiv
J12GCN
35.10 1:115
00M
J9.09 -0.00
$1.60
2:020
46.31 1:014
81.31
1:000
GOM
72.80 11022
GPEGUN
38.95 11.09
20.19 10.03
43.00
-0.21
53.25
=0.14
48.19 20002
84.34
1:020
90105
1:031
71.30 :10.12
Ileeerophily
ESGNN
35.02 6:1.0
45.44 10.05
45.99
-0.35
$1.30
=0
52.74
10.83
83.87
100000
88.05
$1.51
23,50 10.10
GNN
GAT
MixHop
39.36 2:159
41.92 2:183
52.16 $0.00
44.45 10.33
51.81 =0.17
52.77 =0.32
55.30
55.87
:0:13
52.74 50.47
49.75 10.47
84.86
81.81 10002
1:040
90.58
88.44
2:106
1:.16
72.01 1.0.2
71
10.29
GCNIT
42.48
49.18 10.25
51.75
56.31 50:27
$2.45 50.57
82:34 10.51
90:41
1.0.5
72.74 10.17
ACMGCN
48.90
45,45
54,51
53.37
20.42
83.38
64.74
15.55
71.35
Graph
GraphcPP
00M
$3.27
OOM
GOM
O0M
Transtormer
Polysormer
40.17 #2.11
00M
10.15
53.67
46.63
=042
53.48 10013
53.72
$4.14 20002
54.96
60.22
$4.60
83:07
$0.31
GOM
12.76
73.46
10.16
GMaF
35.49
51.19 10.00
49.87 -034
53.03
53.47 60.68
10:30
88.58 10.55
71.88 10.32
Graph MoE
Mowsi
37.75 23773
45.38 19.56
52.56 -:22
55.48
20.32
49.13 10054
84.56 1:031
84,50
1:054
72.52
10.07
DA-Mobs
36,66 10.78
51.46
10.45
47.99
=0.20
52.21
=0.75
50.67
$0.50
80.14 4:0.00
91.36
1-0118
71.96
10.16
Ours
GB3--oscatt
GD3--oocaa
43.61 8:218
43.71 1:58
55.39 10,07
55.33
10.11
56,06
55.53 20.15
00.25
58.04
58.52
2:013
:0.19
56,02
56.36
30052
5:.50
86.63 5:0.00
86.72 3:0.3
92.36
92.35 8:0.88
3:007
73.53
74.13
3.0.27
19.07
labeled data in the validation set. We use the complete training set as Veep and sample 90% of the validation set for Voold, reserving the remaining 10% for gating model validation. While the validation set naturally serves as a holdout set for evaluating model generalization, other baselines can not fully utilize this advantage. Please refer to Appendix F.2 for details about these two setups.
Baselines and Hyperparameters. We compare ours against popular homophilous GNNs, het- erophilous GNNs, Graph Transformers, Graph MoEs, and also deeper GNNs with various skip- connections. For baseline hyperparameters, we follow their original papers when available; otherwise, we conduct hyperparameter search using Optuna ( For Moscat, we tune only the gating model's hyperparameters, while experts inherit the same settings as their baseline counterparts. Detailed baseline descriptions and hyperparameters are listed in Appendix F3 and Appendix F.4
5.2 Performance comparison
Improvements over GNNs. To address Q1, Table I shows that both Moscat variants consistently yield substantial improvements across all base GNNs. Moscat* shows comparable accuracy to Moscat, validating that AH's effectiveness does not stem from utilizing more labeled data. Notably, Moscat achieves the lowest performance gains with GCNII and the highest with ACM-GCN. This is because GCNII aims to avoid overfitting, limiting AH's impact. Conversely, ACM-GCN is more expressive and prone to overfitting. Table 2 further shows that by selecting proper base GNNs as experts, Moscat can outperform state-of-the-an methods by a large margin on all datasets. In contrast, Graph MoEs and Graph Transformers struggle on certain datasets, highlighting the superiority of our paradigm. Appendix G.I compares with leaderboard results.
8

---

6.50
0.80
0.50
ALYOON Mosck
0.32
0.22
0.56
ACHGON
0.58
0.40
0.52
GCA
BON PAscAA
6:18
0.76
0.50
0.45
0.76
0.40
0.54
0.46
0.56
(LM Moscat
0.52
0.82
0.52
DANU
0.30
0.50
0.50
SCC
0.48
0.78
0.48
Figure Moscat outperforms classic GNNs (c.g. SGC, GCN) and soft-scoping GNNs (c.g. GAMLP, ACMGCN), GAMLP and ACMGCN adaptively learn the scope of SGC and GCN, respectively.
Compare with techniques for deeper GNNs. To an-
Table 3: Accuracy comparison of deeper
swer Q2, we compare Moscat with skip-connection methods for deeper GCN, We examine (1) residual con- nections (Res: ResNet-like residual connection (23). II: GCNII-like initial residual, Cat: GraphSAGE- self concatenation (22)) and (2) learnable gating mechanisms (JK: JKNet with concatenation layer aggregation, Attn: GAMLP-like layer aggregation, G²: gradient gating framework (7 As shown in Table performs other ikip-connection techniques Penn94. Additionally, Moscat achieves sigmificant improvements GNNs with skip-connections amazon-ratings. However, skip-connections mix output from different scopes, causing experts to make similar predictions and limiting AH's effectiveness.
GCNs (set 6).
Maazoc-ratilee
Pcmm3
GCN
46.68 1.065
70,08 L1.13
85.76
$2.96
Moscas
$1.50 :0.00
83.71
Connections
Residual
GCN-II
Noscos
51.77 =0.43
54.38 +0.50
30.52 =055
83.66 -0.50
out-
GCN Cat
34,46-00.40 20040
54.46
30.40 =0.00
Moscac
56.66 10057
$4.56 -0.58
GCN-JK
-0.48
Moscaa
Gating
GCN.Amn
49.51
Hoscat
52.70
=0.88
85.64 =0.55
GCN-G
49.06 +0.32
78.50
=1.36
Noscat
51.04
20.54
83.78 =0:48
Performance variation with depths. As depth increases, we further investigate how Moscat improves two state-of-the-art deeper GNNs with cross-layer gating, ACMGCN (8T and GAMLP (40.
[igure5]showe that classic GNNs like GCN and SGC often degrade rapidly beyond 2 layers. With gating. GAMLP and ACM-GCN sustain gains up to 4-6 layers. In contrast, GNN-Moscat achieves the best results across all depths and continues to improve through 6-10 layers. Notably, when increasing the maximum layers from 1-10, GNN-Moscat with message- message-passing architectures (GCN, ACMGCN) derive 4-10% accuracy improvements (Figure 5 top), whereas GNN-Moscat with decoupled architectures (SGC, GAMLP) yields only 1-2% gains (Figure bottom). This gap likely arises from the higher expressivity of pressage-passing models, which enables depth-varying experts to produce more diverse predictions. See Appendix G.4 for additional experiments.
5.3 Ablation study
In this subsection, we evaluate each compo- nent in Moscat to answer Q3. As shown in Table using Mean-Ensemble to average GNN logits across different depths cannot guarantee accuracy improvements, primar- ily due the poor performance of deeper GNNs. By enabling node-level adaptation, Moscat consistently achieves significant improvements over -eaan-essebbl.. We evaluate the effectiveness of critical compo- nents in Moscat by removing them one at a time: (1) When we remove the holdout set and train both the gating model and experts on the full training set, we observe dras-
Table 4: Ablation study. Mean-Ensemble combines all scope experts with uniform weights. For Moscat, w/o Holdout-Set trains the gating model on the same expert training set, w/o Multi- ensemble experts with the same best scope, w/o Hetero-Fite Filter removes heterophily- biased sample filtering, and w/o Scope-Augment re- moves scope- aware logit augmentation.
Squiree1
asozoo-ratings
PunnD4
arxiv-yoax
SGC
40.04 +1.77
40.58 -0.55
81.17 :0040
45.88
-0.92
w/ Meaz Ensemble
39.65
11.76
50.56
10.53
80.20
1.0.7
46.68 -0.25
300-Noscaze
42.73 12.00
51.82 1.029
84.75 3:0.41
$2.09
-0.27
BGC-Moxcse
43.35 #11
52.72 +00.5
$4.30 -10.49
$1.86 =0.30
we Holdoat
39.86
1.2.31
10.31
77.72 1.0.95
49.30
-0.23
weo Multi Scope
80.88
11.72
51.09 1.0.6
82.20
1..45
46.63
-0.28
Heluro-Fillx
84.64
tic accuracy drop compared to Moscat*
Scope Augment
2:00.44
47.10 =0.25

---

(which also restricts model training within the training set). This highlights the necessity of the holdout set. (2) Multi-Scope experts prove critical for incorporating knowledge from different scopes. (3) Heterophily-biasee
sample filtering is designed as an optional technique, where "-" denotes it not being used in our hyperparameter settings. We find it critical for sampling high-quality data for gating model training. (4) Scope-aware logit augmentation shows particular effectiveness when combined with SGC, likely due to SGC's limited model expressivity.
5.4 Case Study: how Moscat become effective?
We examine the >40% performance gain of ACMGCN-Moscat on genius (Table [ Dropping the MI.P expert and using only six weak experts (1-6 layers ACMGCN) yields
Miact
deaper
shallon experta better
625
the same improvement, so the strong expert isn't driving this effect. Figure 6 (layers 1-2 omitted) shows that: (1) Even mistaken ACMGCN predictions carry structurally in- formative logits. (2) When there are suf- ficient training samples, Moscat can learn proper expert mixtures for correct predictions. (3) With limited samples, Moscat can still learn to select the best-performing expert.
Node Himmoph
Figure 6: Moscat over ACMGCN on genius.
6
Conclusion
In this paper, we investigate the challenges of applying deeper GNNs to heterophilous graphs. Our analysis reveals that GNNs exhibit shifting generalization preferences across nodes with different homophily levels as their depth increases. To address this, we propose Moscat, which follows a novel decoupled expert-gating paradigm. Experiments show that Moscat can improve GNN generalization, better exploit deeper GNNs, and adapt to diverse architectures.
Acknowledgments and Disclosure of Funding
This work is supported by DEVCOM ARL Army Research Office (ARO) under grants 191 and INF232220, and by National Science Foundation (NSF) under grant OAC-2209563. Distribution Statement A: Approved for public release. Distribution is unlimited.
References
[1] Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pages 21-29. PMLR, 2019.
[2] Takuya Akiba, Shotaro Sano, Toshihiko Yanase, Takeru Ohta, and Masanori Koyama. Optuna: next-generation hyperparameter optimization framework. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2019.
[3] Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E. Hinton, Layer normalization. arXiv preprint arXiv:1607.064500 2016.
[4] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions multi-layer networks. urXiv preprint arXiv:2204 09290,99999. 2022.
[5] Aleksandar Bojchevski, Johannes Gasteiger, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 2464-2473, 2020.
[6] Chandramani Chaudhary, Nirmal Kumar Boran, Sangeeth, and Virendra Singh. Gnndld: Graph neural network with directional label distribution. In ICAART (2), pages 165-176, 2024.
10

---

[7] Ming Chen, Zhewei Wei, Bolin Ding, Yaliang Li, Ye Yuan, Xiaoyong Du, and Ji Ji-Rong Wen. Scalable graph neural networks via bidirectional propagation. Advances in neural information processing systems, 33:15 4556-14566, 2020.
[8] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference on machine learning, pages 1725 1735- PMLR, 2020.
[9] Xuanze Chen, Jiajun Zhou, Jinsong Chen, Shanqing Yu, and Qi Xuan. Mixture of decoupled message passing experts with entropy constraint for general node classification. arXiv preprint arXiv:2502.08083 2025.
[10] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? Advances in neural information processing systems, 33:10383-10395 2020.
[11] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988,, 2020.
[12] Eugenio Clerico, George Deligiannidis, and Arnaud Doucet. Wide stochastic networks: Gaus- sian limit and pac-bayesian training. In International Conference on Algorithmic Learning Theory, pages 447 440-470. PMLR, 2023.
[13] Weilin Cong. Morteza Ramezani, and Mchrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34:9936-9949, 2021.
[14] Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets. Advances in Neural Information Processing Systems, 13:17,,0-13271, 2020.
[15] Chenhui Deng, Zichao Yue, and Zhiru Zhang. Polynormer: Polynomial-expresiiee graph transformer in linear time. arXiv preprint arXiv:2403.01232. 2024
[16] Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint arXiv:2004. // 198, 2020.
[17] Chen Gao, Yu Zheng, Nian Li, Yinfeng Li, Yingrong Qin, Jinghua Piao, Yuhan Quan, Jianxin Chang, Depeng Jin, Xiangnan He, et al. A survey of graph neural networks for recommender systems: Challenges, methods, and directions. ACM Transactions on Recommender Systems, (1):1-51, 2023.
[18] Xinyi Gao, Wentao Zhang, Junliang Yu, Yingxia Shao, Quoc Viet Hung Nguyen, Bin Cui, and Hongzhi Yin. Accelerating scalable graph neural network inference with node-adaptive propagation. arXiv preprint arXiv:2310.10999. 2023.
[19] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:/810.0599) 2018.
[20] Johannes Gasteiger, Chendi Qian, and Stephan Günnemann. Influence-based mini-batching for graph neural networks. In Learning on Graphs Conference, pages 9-1. PMLR, 2022.
[21] Shengbo Gong, Jiajun Zhou, Chenxuan Xie, and Qi Xuan. Neighborhood homophily guideed graph convolutional network. arXiv preprint arXiv:2301.09885/ 2023.
[22] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[23] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[24] Keke Huang, Jing Tang, Juncheng Liu, Renchi Yang, and Xiaokui Xiao. Node-wise diffusion for scalable graph learning. In Proceedings of the ACM Web Conference 2023, pages 1723-1733, 2023.
11

---

[25] Wenbing Huang, Yu Rong, Tingyang Xu, Fuchun Sun, and Junzhou Huang. Tackling over- smoothing for general graph convolutional networks. arXiv preprint arXiv:2008.09880 2020.
[26] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448-456, pmlr, 2015.
[27] Weiwei Jiang and Jiayun Luo. Graph neural network for traffic forecasting: A survey, Expert systems with applicatiions 207: 2022.
[28] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1r0iv::60..029900000 2016.
[29] Kwei-Herng Lai, Daochen Zha, Kaixiong Zhou, and Xia Hu. Policy-gnn: Aggregation opti- mization for graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 461-471, 2020.
[30] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, pages 9267-9276, 2019.
[31] Guohao Li, Chenxin Xiong, Ali Thabet, and Bernard Ghanem. Deepergen: All you need to train deeper gens, arXiv preprint arXiv:2006.077 07739, 2020.
[32] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[33] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Learning, pages 13242-13256. PMLR, 2022.
[34] Xunkai Li, Jingyuan Ma, Zhengyu Wu, Daohan Su, Wentao Zhang, Rong-Hua Li, and Guoren Wang. Rethinking node-wise propagation for large-scale graph learning. In Proceedings of the ACM on Web Conference 2024, pages 560-569, 2024.
[35] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non non-hone aan-hoopphilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
[36] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902, 2021.
[37] Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4424-4431, 2019.
[38] Andreas Loukas. What graph neural networks cannot learn: depth vs width. In International Conference on Learning Representations, 2020. URL //pparr//operrevier wwwpeearriiiii.neeffouueee net/forum? id=B112bp4YWS
[39] Donald Loveland, Jiong Zhu, Mark Heimann, Benjamin Fish, Michael T Schaub, and Danai Koutra. On performance discrepancies across local homophily levels in graph neural networks. In Learning on Graphs Conference, pages 6-1, PMLR, 2024.
[40] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-War Chang, and Doina Precup. Revisiting heterophily for graph neural networks. Advances in neural information processing systems, 35:13624 366-1335, 2022.
[41] Sitao Luan, Mingde Zhao, Xiao Chang, and Doina Precup. Training matters: Unlocking potentials of deeper graph convolutional neural networks. In International Conference on Complex Networks and Their Applications, pages 49-60. Springer, 2023.
12

---

[42] Yuankai Luo, Qijiong Liu, Lei Shi, and Xiao-Min Ming Wu. Structure- aware semantic node identifiers for learning on graphs. arXiv preprint 0rXiv:240S.16433 2024.
[43] Yuankai Luo, Lei Shi, and Xiao-Ming Wu, Classic gnns are strong baselines: Reassessing gnns for node classification. arXiv preprint arXiv:2406.08993, 2024.
[44] Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and faimess of graph neural networks, Advances Neural Information Processing Systems, 34:1048-1061, 2021.
[45] Haitao Mao, Zhikai Chen, Wei Jin, Haoyu Han, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang. Demystifying structural disparity in graph neural networks: Can one size fit all? Advances in neural information processing systems, 36:37013-37067, 2023.
[46] Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Improving graph neural networks with simple architecture design. arXiv preprint wxXi:2205.0063:: 2021.
[47] Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata. Feature selection: Key to enhance node classification with graph neural networks. CAAI Transactions Intelligence Technology, 8(1): 14-28, 2023.
[48] Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI conference on artificial intelligence, volume 33, pages 4602-4609, 2019.
[49] Soroor Motie and Bijan Raahemi. Financial fraud detection using graph neural networks: A systematic review. Expert Systems With Applications, page 122156, 2023.
[50] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint arXiv: /905. 10947, 2019.
[51] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classificatton. In International Conference on Learning Representations, 2020. URL
https://openrrevev.. http://wwww....eeeoo.oooo///daaa
[52] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287, 2020.
[53] Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we re- ally making progress? In The Eleventh International Conference on Learning Representations, 2023. URLhttps. //pp:////////eee//eeeeee wttpeeerreeieeeeeeeefooorrttttte net//forummid==tbbbffttt 5w
[54] Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. Character- izing graph datasets for node classification: Homopphly-heteeopphh dichotomy and beyond. Advances in Neural Information Processing Systems, 36, 2024.
[55] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35: 4501-145155 2022.
[56] Emanuele Rossi, Bertrand Charpentier, Francesco Di Giovanni, Fabrizio Frasca, Stephan Günnemann, and Michael M Bronstein. Edge directionality improves learning heterophilic graphs. In Learning on Graphs Conference, pages 25-1. PMLR, 2024.
[57] T Konstantin Rusch, Benjamin Paul Chamberlain, Michael W Mahoney, Michael M Bronstein, and Siddhartha Mishra. Gradient gating for deep multi-rate learning on graphs. ICLR, 9:25, 2023.
[58] Noam Shazeer, Azalia Mirhoseini, Krzysztof Maziarz, Andy Davis, Quoe Le, Geoffrey Hinton, and Jeff Dean. Outragcously large neural networks: The sparsely-gater mixture-of-experts layer. arXiv preprint arXiv: 170100653333 2017.
[59] Laurens Van Der Maaten. Accelerating t-sne using tree-based algorithms. The journal of machine learning research, 15(1):322133245, 2014.
13

---

[60] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, al. Graph attention networks. stat, 1050(20):0--85555 2017.
[61] Haotao Wang. Ziyu Jiang. Yuning You, Yan Han, Gaowen Liu, Jayanth Srinivasa, Ramana Kompella, Zhangyang Wang, al. Graph mixture of experts: Learning on large-scale graphs with explicit diversity modeling. Advances in Neural Information Processing Systems, 36, 2024.
[62] Xiao Wang, Hongrui Liu, Chuan Shi, and Cheng Yang. Be confident! towards trustworthy graph neural networks via confidence calibration. Advances in Neural Information Processing Systems, 34:23768 23779, 2021.
[63] Zhen Wang. Zhewei Wei, Yaliang Li, Weirui Kuang, and Bolin Ding. Graph neural networks with node-wise architecture. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, pages 1949-1958 2022.
[64] Zhiyang Wang, Juan Cervino, and Alejandro Ribeiro. A manifold perspective on the statistical generalization of graph neural networks. arXiv preprint arXiv:2406.05225, 2024.
[65] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6871. PMLR, 2019.
[66] Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nic, Haitian Jiang, Yatao Bian, and Junchi Yan. Simplifying and empowering transformers for ange-graph representations. Advances in Neural Information Processing Systems, 36, 2024.
[67] Xinyi Wu, Zhengdao Chen, William Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. arXiv preprint urXvv:22/2.1070/ 2022.
[68] Keyulu Xu. Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pages 5453-5462 PMLR, 2018.
[69] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https 7 //openrevies net teee/forrmmiidryGG5....
[70] Zhe Xu, Yuzhong Chen, Qinghai Zhou, Yuhang Wu, Menghai Pan, Hao Yang, and Hanghang Tong. Node classification beyond homophily: Towards a general solution. In Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '23, page 2862-2873, New York, NY, USA, 2023. Association for Computing Machinery. URL httph:ttt///oiii.. org/10. 1145/
ISBN 9798400701030. doi: 10.1145/3580305.355520 3580305 3599446
[71] Yuchen Yan, Yuzhong Chen, Huiyuan Chen, Minghua Xu, Mahashweta Das, Hao Yang, and Hanghang Tong. From trainable negative depth to edge heterophily in graphs. In Thirly-seventh Conference on Neural Information Processing Systems, 2023. URL htttps://openreete net:/forumFiddp$llotttuu
[72] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), pages 1287-1292. IEEE, 2022.
[73] Chaoqi Yang, Ruijie Wang, Shuochao Yao, Shengzhong Liu, and Tarek Abdelzaher. Revisiting over-smoothing in deep gens. arXiv preprint arXiv:2003.1366. 2020.
[74] Chenxiao Yang, Qitian Wu, Jiahua Wang, and Junchi Yan. Graph neural networks are inherently good generalizers: Insights by bridging gnns and mips. arXiv preprint arXiv:2212.090334 2022.
[75] Zelin Yao, Chuang Liu, Xianke Meng, Yibing Zhan, Jia Wu, Shirui Pan, and Wenbin Hu. Da-moe: Addressing depth-sensitivity graph-level analysis through mixture of experts. arXiv preprint arXiv:2411.03025, 2024.
14

---

[76] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020. URI.
[77] Hanqing Zeng, Muhan Zhang, Yinglong Xia, Ajitesh Srivastava, Andrey Malevich, Rajgopal Kannan, Viktor Prasanna, Long Jin, and Ren Chen. Decoupling the depth and scope of graph neural networks. Advances in Neural Information Processing Systems, 34:19665-19679 2021.
[78] Hanqing Zeng, Hanjia Lyu, Diyi Hu, Yinglong Xia, and Jiebo Luo. Mixture of weak and strong experts on graphs. In The Twelfth International Conference on Learning Representations, 2024. URL /RK.itttps://pperrviieee
[79] Wentao Zhang, Mingyu Yang. Zeang Sheng, Yang Li, Wen Ouyang, Yangyu Tao, Zhi Yang, and Bin Cui. Node dependent local smoothing for scalable graph learning. Advances in Neural Information Processing Systems, 34:20321 -20322, 2021.
[80] Wentao Zhang. Zeang Sheng. Ziqi Yin, Yuezihan Jiang, Yikuan Xia, Jun Gao, Zhi Yang, and Bin Cui. Model degradation hinders deep graph neural networks. In Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining, pages 2493-2503, 2022.
[81] Wentao Zhang, Ziqi Yin, Zeang Sheng, Yang Li, Wen Ouyang, Xiaosen Li, Yangyu Tao, Zhi Yang, and Bin Cui. Graph attention multi-layer perceptron. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 4560-4570, 2022.
[82] Jiajun Zhou, Chenxuan Xie, Shengho Gong, Jiaxu Qian, Shanqing Yu, Qi Xuan, and Xiaoniu Yang. Pathmlp: Smooth path towards high-order homophily. Neural Networks, 180: 2024.
[83] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020.
15

---

A Related Work
A.1 Graph neural networks meet heterophily
GNNs were initially designed under the homophily assumption and have recently gained signif- icant interest due to their superior performance and small parameterization. Various aspects of
GNNs have been widely studied, including scalability [22 76 5 20] expressivity
69 38 51], and
generalization 13 74 45).
To extend GNNs to heterophilous graphs, existing works primarily focus on improving higher-order neighborhood utilization [7T]. MixHop [ extracts features from multi-hop neighborhoods in each layer. GCNII [8] prevents wwerssmotthing in deeper GCNs by proposing initial residual connections and identity mapping. To adapt to graphs with different label patterns, GPR-GNN [T] learns signed scalar weights for the propagated features with different propagation steps. Other works focus on
mapping topology [36 33 40), using global attentions [5 or exploiting edge directionality [56] to
improve learning on heterophilous graphs.
A.2 GNNs with personalized scoping
Personalized scoping aims to set a tailored receptive field to each node to restrict the length of feature propagation, which is able to extract essential long-range dependencies while reducing computational overhead. Although this idea has been around for a long time and has a fundamental impact on various GNN domains, few works summarize these advancements from the personalized scoping perspective. Here, we classify these works into two categories based on whether or not each scope is learned.
Heuristics methods. The heuristics for personalized scoping originate from works that generalize personalized PageRank (PPR) to GNNs. PPNP [19] first introduces PPR as the final propagation matrix for decoupled GNNs. GBP 7 combines reverse push and random walks to approximate PPR propagation. NDL. [79 examines the smoothing effects in graph diffusion, noting that the level of smoothness should node-specifie. NDM (44 advances this by developing a unified diffusion kernel that extends PPR with the heat kernel and enables custom propagation steps following NDLS. To generalize personalized scoping to non-decoupled GNNs, ShaDow (77) proposes a design principle that decouples the scope from the model depth. For each node, shallow scope is constructed using its neighboring nodes with the top-k PPR.
Learnable methods. However, these heuristics assume homophily and heavily rely on topological information, often falling short on heterophilous graphs. Recent research has explored parameterized techniques to address this issue. One line of work integrates personalized scoping into GNN architectures. We refer to these methods as soft personalized scoping since they typically learn node-dependent weights to control the scope. GeniePath [77 proposes gated unit as the scope controller. GAMLP [8]) uses the attention mechanism to enable personalized scoping on a decoupled GNN [16. NW-GNN (63] further extends this to non-decoupled GNNs by proposing node-wise architectural search. ACM-GCN [40] employs an alternative strategy by introducing additional identity channels beyond aggregation.
A.3 Graph Mixture of Experts
Another line of work considers different depths of GNNs as different experts and develops a gating module to activate a small subset of experts for each input node. PoNicy-GCN [29] uses reinforcement techniques and takes the average accuracy of different depth models as rewards. GraphMoB [61] and DA-MoE 75 proposes top-K K sparse gating technique for mixing multiple GNN experts. Additionally, Mowst [78 proposes separating rich self-features from informative neighborhoods by using mixture of weak MLP and strong GNN experts. However, these methods require retraining the GNN models, which introduces significant overhead and may suffer from overfitting, potentially downgrading each model's performance.
B Proof
The following provides the proof for Theorem 3.3
16

---

Lemma B.1. Under Assumption 3.1 Assumption 3.2 and assume the aggregated features (x G)
share the same variance I For any subgroup i.j J E M and any nodes E Vi. E V/ with aggregated features f, = =g (X, 9), and f = (X g) we have:
Pr(ys = c1 c1((.)) Pr(y: cc
(p- ko)
(Ifs, fuul + (p= - P5) (Ppr())) (pm gml] (mll-1)
(5)
where p = |1 uell and k is small constant.
Proof. To begin with, we recall that Assumption 3.1 assumes every node feature follows the normal distribution. The aggregated features F = (X, 9) = AD= X for different subgroups of different classes has the following distribution:
f ~ N (p o'I). for w E Vm, CE {1,2], m E (M).
(6)
where Ve denotes the node subset with class label and belongs to subgroup m. pe,m denotes the mean value of L-hop aggregated features of V..
Next, we break down Pr(yu e1 (f.), which is the conditional probability of node a E V; classified class ei given feature f,, with Bayes theorem
Pr(y = cc(
Pr(fu (/, =
c1) cI) Pr(ya = =1)
(fu(ful c1) Pr(ya = =c1 Pri (Pu = 02) Pr(y 02)
[fn (4.-111 (1)/2
exp
-2a
(a)
(fw (1
(fa و,
exp
-202
+ exp
20
where (a) utilize Assumption 3.1 that different classes have the same number of samples and the PDF of normal distribution. Hence, we have
Pr(Eu = c1 [f,) - Pr(y = c.f. =
(f. (!))
(f. (( 20²²
(f. (fe-
(o 2n²2
cxp
2n²
exp
exp
2
exp
(8)
(f., - 14 و
(f. 1Gu-11111
(1)
(f., (fu-H1/ (b))
(f., (fu-p(
exp
-20"
+ exp
20
exp
-20*
+ exp
-20
(fw - (
Note that the denominator can be bounded [0, since each component exp
[0, 1].
220*
We can then denote the denominator exp( A),, where A is constant. Hence, we have
Pr(y (.l.. - Pr(y, =c]ff))
(f,, Mi, (1))2 + (f. - 12.
(1))
exp
-202
(fu - Mig (L) 2 + (fu-
(22/22
H2.3
-1)
exp
-202
(9)
(f.
(1 (G(1 (fu, (()) + (f.. 122 - (f, 12
(a) 2
[(c. - -1(1 + (fa (.,) (f. f.)) (1 (11)))
20
(fo - -11 + (fr 1 (Io - f.)) + (1 12. (12) ]
+
17

---

(a) is derived from the Lagrange mean value theorem. Let (fu 11,,) + (f. -² C and (f.- (f.-H())) )2 + (fu M2, )2 D. Given that Pr(ja c1 (.) and Pr(ye- 01 (f,)) probabilities
that smaller than 1, we can derive
C A 0 and -2
D
A < <.
(10)
-20²
From the Lagrange mean value theorem, we have
exp(x) - exp(v) exp(E), & (x.
(11)
I y
Let x
C
and y = D
A. Given Equation
12
we have exp(E) S 1. Hence,
-20
-20"
C
D-C
D
exp
-
A
exp
A
<
(12)
2
-2
20²
The proof for (a) is complete.
Equation 9 shows that Pr(y, ci (f... - Pr(y. ci (f,)) can be bounded by three terms:
The maximum distance between any node feature to the mean value any subgroup
max Cij (1.
[l (1
(13)
2. The feature distance ||C,, f. between node u and w.
3. The mean value difference between subgroup and j: u p1 and 12,
(L)
P22.
first bound term (1) Eij. Recall that f. follows the normal distribution with variance o², For the mean value of the aggregated feature of node set V! and V? we have
+ ()(p))())) 14,m (1.-1)]
1,2 = p; (p(m)()))
(14)
and
(1(--1)) + p.Epp(m)
12,m [[-11)]
2,1 = (.pp)(
(15)
which reveals that for every L we have
(L) (L) min(H1, u2) S M1, 12, I max( U2)
(16)
since every Pr(m) lie in [0, 1]. Therefore, Eij can be bounded by
Gj < |4 12ll + ko,
(17)
where k is small constant. When l: 3, this equation holds with probability close to To bound the term (3), we derive the following equation based on Equation [4 and Equation 15
(T)
(T)
11. 22
(p: 4:) Epr(m)
11, - (p: qc)
(L-1)
(Ep(m))
12,m
(1-1)
(L-1) (L-1)]
(pi ) Err(m)
fi,m
12,m
(18)
(p: 4.) (pr(m)
(pm - qm) Epr(o)
|1.00
(I--2)
2,0
(I--2) 2)
(p: 4.) Epr(m) [pm - gm]] Epr(m)
11,m
(L-2)
422m
(L-2)
(p: 9.) Epr(m) [pm - 9ml) 1-1 1-1 (#1) 222
18

---

We also have
(L) (D)
Mi, Pi.
(p: P₃) Bpr(m)
fi,
(1-1)
+ (qt 4z) Brr(m) 222 (mm))
(pi Pς) Epr(m)
fi. (1-1))
2m (1-11)
(19)
(c)
(p: p3) _BP(m))
(pm qm) (Pp(() [Po - qol 90l 1-2 (M) u2)
(p. pÿ) Brr(m) [Pm 9m] 1--1 (M1 12),
(L) (L)
where (a) utilizes the definition of p; + Follow the same proof, can derive 22, -m1 (.
M22.
Next, substitute terms (1), (2), and (3) to Equation 9 continue the proof. Let p we have
|| 442
Pr(yu = ei (f) - Pr(y= = (.)
20 (f. 11 (f. (1)))) ) (f, (12))) ) + (fo (!!
[|fu foll (ps p.) Epp(m) Pm - qml) (-m (w1 H22
(20)
2 (p ko)
[If. - foll + p(ps - pÿ) -Ep(()) (pm qm (mm)t-) }1-11
The proof for Lemma B.I is complete.
3.3 Theorem in 45 provides a PAC-Bayes subgroup generalization bound for GNNs with one-hop aggregation. In our work, we extend their theorem arbitrary hop to investigate how different scope sizes affect the generalization of different subgroups. Besides that, both theorem follows the same setting. To avoid replicates, we only provide the proof for the different parts and direct readers to the specific sections of [45] for the rest details and proofs.
Proof for Theorem
Appendix F.4 in 455 provides complete proof for the proposed PAC-Bayes bound. There exists 0 a 1 we have
4
Ch - C3(0)
EE WilL
$ (2/// (P:(PP))) - ln3
(cm
2/1
(7/8)2/M/N) Ng
(21)
3
1
+ N2
In
+ 2
+
4N
L 2a
where D3/3 is bounded by 45 Lemma 4.
Lemma (5) further depends on the bound [45's Lemma 2 in Appendix which calls out
main difference compared with our theorem. By substituting 45 's Lemma with our Lemma B.I we complete the proof for our Theorem 3.3
C (0) (3)
2K (p + ko) 0²
(cm p Pm) Ept(o) Ipo 90l"--1)
(22)
DK Will (7/8)//1
3 In +2
1
2/E
N
AN
1.-1-20
For the first term, K is the number of classes, 1 small constant, and < We denote Epr(o) [Po q0 1-- as I T-11. 1. For the rest the terms, b and y are constants. We denote ||W||2
Σl' [. Since
1, we have aN
We simplify Equation 22 as follows:
19

---

(8) (0)
$ 0 02
(m + p ( pmn)Ta :0 |W]] (cm )o/4))
+ 0 11(1/6)
(23)
Ng
C Supplementary Preliminaries
C.1 Scope and Depth
The scope of model M for a node is latent subgraph 9M) that contains all the nodes Mio S V and edges Elo used by M when predicting v.
Definition C.1 (Size of scope). Assume MM is connected. The size of scope (
ma d (u, v), where d (u, v) denotes the shortest path distance from u to
We focus on GNN architectures where the model depth equals the size of the scope for every node in this paper.
C.2 Homophily Metries
The homophilyyheterophily metrics are widely used as graph properties to measure the probability of nodes with the same class connected to each other. This paper uses node-wise homophily metric called node homophily class for each node:
52
Node homophily defines the fraction of neighbors that have the same
[u] Hu N₁ Vu yo We
(24)
In Table 2 we also report the average node homophily for each dataset:
H node
M Σ
1
hnoe [w).
(25)
There are also some other commonly used homophily metrics in the literature. Edge homophily [
83
measures the fraction of edges that connect nodes of the same class. Class homophily 336
40)
further addresses the sensitivity issue of edge homophily on graphs with imbalanced classes. For instance, genius dataset (36] has majority class for roughly 80% of nodes, which can mislead edge homophily into elassifying it homophilous graph (H& 0.618). In contrast, class homophily
accurately identifies it as a heterophilous graph (H class 0.080). However, class homophily does not satisfy some desired properties, such as asymptotic constant baseline and empty class tolerance. [54] proposed a variant called adjusted homophily to address this issue.
C.3 GNN Basics.
As pioneer work, graph convolutional network (GCN) 28 provides a layer-wise architecture that stacks feature propagation with linear transformation approximate spectral graph convolutions. The (1 + 1)-th th layer of GCN is defined as:
h (E+1) ReLU V
(ENEN A A !!
(26)
where h = x,,- Subsequent GNNs typically modify GCN in terms of aggregator and backbone.
Some works develop more expressive aggregators 66
14 34
For example, GAT 660 substituting
the degree-normalized coefficients in GCN's aggregator with learnable attention scores. Another line
of works alters the backbone by decoupling aggregation from transformation
19
46
or adding skip connections between layers [68] 3] 80] For instance, SGC 665 eliminates the
ReLU (-) function in the GCN layer to allow precomputing feature propagation. JKNet 688 directly
maps the concatenated outputs of each layer [h.),, ..),.... (h.") to the prediction.
20

---

C.4
Personalized Scoping.
graphs often exhibit mix of homophilous and heterophilous patterns [6 33 45 An
ideal way to mncoporate sufficient homophilous information is to set personalized scope, allowing different nodes to have distinct scope sizes.
Definition C.2 (Model with personalized scoping). Assume the input graph is connected with radius exceed max.ev
[M]
The model M has personalized scoping if Eu, V. where G g
The above definitions assume the graph's 's radius is larger than each node's s scope size, which is true for most nodes in large graphs. According the definition, an L-layer GCN does not support personalized scoping because it forces the scope size to be uniformly L for every node. To break this limit, recent works (e.g., ACMGCN, GAMLP, NW-GNN, GNN-G²) propose additional gating
modules that learn the weight (9) for each hop on a node-dependent basis:
h qui Σ L=
(2)
where
(27)
By setting the weights of larger scopes to for some nodes, these methods allow different nodes to have different scope sizes. In this paper, we adopt broader definition: we consider model to support personalized scoping if it can generate node-adaptive weights for each scope embedding. Notably, our proposed method Moscat also enables personalized scoping for any base GNN architecture through an attention- based gating mechanism.
(f - -z()) s 20 cm + p(ps Pmm) -mm) + +
|W]1 (em )2/1/
In(1/5) No
+ +0
N
(28)
D Supplementary Analysis for Deeper GNNs Failure
The depth dilemma. Increasing the GNN depth favorably increases the number of non-linear transformations and expands the scope each node to exponentially incorporate more neighboring information. Existing studies also show that deeper GNNs are provably more expressive by using distance-bbsed metrics [50 25 and WL-based metrics 44S
10 In practice, however, performance degradation is widely observed when going deep. Many novel architectures have been proposed to alleviate this issue, yet they achieve only marginal gains over shallow variants, which is undesirable given deeper GNNs' superior expressive power and substantially higher computational costs. How effectively leverage the depth remains an open question.
Limitation of existing solutions. While useful, current techniques for deeper GNNs face inherent trading-off's off's between these three types of errors. Residual connections (c.g., ResGCN) address the vanishing gradient issue but result in larger generalization gap [33. Learnable cross-layer gating modules (e.g., G²-GNN) achieve personalized scoping to alleviate over-smoothing, but they lead to an increase in training difficulties and the risk of overfitting. Meanwhile, GCNII attempts to prevent overfitting by mixing initial embeddings and adding identity mappings to weight matrices, but this comes at the cost of reduced expressivity.
E Compare Expert-Gate Joint Training MoEs with Independent -rain-then- MoEs
Expert-gate joint training is widely used in current MoE methods for LLMs. Instead, Moscat employs separate -eaa--then-merge" strategy which is optimized for GNN experts. Our work is motivated by the observation that directly transferring MoE designs from LLMs to GNNs faces inherent challenges. In LLMs, the gating module and experts are co- co-trained using Top-K K sparse gating to reduce training and inference time while maintaining performance. However, for GNNs, no clear scaling law exists, and sparse gating plus more parameters do not necessarily translate into accuracy improvements. In our experiments with Moscat, we found that Top-K sparse gating (especially with small K) often results in an accuracy drop compared to dense gating. Recent work [9] also reveals that sparse
21

---

Table Hyperparameter searching space for GNNs.
Hyperparameters
Range
learning rale
0.05, 0.01, 0.005, 0,001, Se-4, Se-5,
normalization
layer 33] batch 26]-1
hidden dimension
32, 64, 128, 256, 512
dropout
{ 0.1, 0.3, 0.5, [ 2, 3, 6,
number of convolation layers
Table Hyperparameter Searching space for Moscat.
Hyperparameters
Range
Notes
scupe Leasx
15,61
increusing Lyeas slightly improve accuracy
Moacat specifie hyperparameters
validation ratio y)
0.1
dalaset specilic parameter
Valas masked rytio
10, 0.3, 0.5, 0.9, 1,-1
indicates Vey
Noscat training
mask wrong
Thae, False |
learning
0.005, 0.001, Se.4, le-4, Se:5
hyperparameters for in Noscat
normalication
layer, batch,
dalasel specilic parameter
hidden dimension dropout
128, 256
fix 256 larger datasets (if OOM)
(0)
lix dropout works the best
number layers
[3]
3-layer sutticient settings
gating can lead to performance losses on heterophilous datasets. Our independent- seeenndentttrain--ee train-then-merge approach for GNN MoEs offers distinct advantages expert-gate joint training:
Diverse Generalization Capabilities: GNN experts, which vary in scope and architecture, exhibit substantial disparities generalization capability, which has been largely overlooked. Graph data spans wide range of domains from different perspectives (e.g.. homophily, centrality). By training experts independently, we allow each to specialize and become robust domain generalizers.
Avoiding Harmful Regularization: Standard joint training requires regularization to balance node distribution among experts and prevent collapse. However, graph domains often unevenly distributed, typically following a power-law. Imposing such regularization can diminish the expressive power of the GNN experts. Our experimental results (Table
demonstrate that existing GNN MoEs underperform even well-tuned single GNNs, whereas
Moscat successfully learns meaningful gating weights (see Figures 18 and 19
without
compromising the underlying GNN training.
In summary, we highlight the limitations of directly applying LLM MoE training strategies to GNNs and demonstrate how Moscat provides more promising alternative that better leverages the unique properties of graph data. We believe Moscat will provide valuable insights to the community and open new directions for advancing GNN capabilities.
Table 7: Values of the hyperparameter a used in the Moscat* setting reported in Table
1
Squirrel
easp-pstente
arxiv-year
Flickr
anszon-ratingg
Penn94
geniue
ogba-arxiv
Moscate
0.65
0.55
0.65
0.65
0.85
0.9
0.85
0.9
0.9
BAT-Hoacat+
0.55
0.65
0.65
0.85
0.9
0.85
0.
0.85
CONII-Noscat-
0.6
0.65
0.85
0.85
0.9
0.85
0.9
0.85
ACNGOX-Moscabe
0.55
0.65
0.65
0.85
0.9
0.85
0.
F Experimental Settings
F11 Datasets
We evaluate Moscat on datasets with various homophily ratios. used the filtered version of Squirrel datasets, which removes all the duplicated nodes that share the same neighbors and
22

---

Table 8: Base GNN model selected for -MNsaas on each dataset in Table
2
Squirrel
enap patents
araiv
Flickr
ratings
Penn84
geniue
ogbo-arxiv
Base GNN CW--Mocatt())
GCNII
MixHop
GAT
GAT
ACMGCN
MixHopp
OCNTI
GAT
Table 9: Comparison of Moscat with other methods use validation set for model training.
Method
Squirrel
arazca-ratinge
Penn94
Method
Squirrel
amazoa-ratinge
Penn94
GCN
41.33 +1.46
48.55
=0.38
82.54
+0.43
GAT
39.36 +:1
49.78 +:047
81.81 +-062
GCN-ft
41.36
12.49
48.34
83.07
GAT-ft
39.74 1.221
10.39
82.65 10.75
GCN-mlp
40.37
11.76
48.79 -0.57
82,60
+0.50
GAT-mlp
38.96
+:225
50.32
+3.40
81.87 +:060
CON-Yoscate
42.91
+1.96
51.02 =0:50
85.51
+0.42
CAT-Moscatt
43.10 +-1
52.56 +0.40
85.41 +00488
GCN Xoecat
43.55 L2.08
52.25
10
85.76
10.32
GAT Moecss
43.10
12.13
53.77
10.61
85.35 1.0.99
labels. These duplicates exist widely in the train and test set and can cause data leakage. The amazon-ratings dataset is from [53]. For the Penn94, arxiv-year, genius and
datasets, we follow the same settings as [35] with 50% random splits for train/valid/test. We run 10 times on each of the 10 benchmark datasets. We follow the setup in (53), which does not convert the directed graphs to undirected graphs and does not use reverse edges since the outgoing neighbors might not be observed during real-world inference.
F.2 Moscat* and Moscat
Moscat*, In this setting, we reserve the original validation set Vvat exclusively for validating both the GNN experts and the gating model, ensuring Veai is not used during model training. We introduce a hyperparameter a E (0, 1) to denote the ratio of data sampled from the original training set Vusin for expert training Vexp- The remaining Vurin is designed as the holdout set Vhold. reserved for gating training. To alleviate the experts' performance drop caused by training on only a subset of Vusin- we create complementary split on Virain with the same a. In this split, the expert-training set V completely overlaps with the holdout set Vinia from the first split. We then follow the same procedure to train another set of experts and gating models. At inference time, we average the outputs of the two gating models to form the final prediction. Adding the complementary split results in an average accuracy improvement of around 0.3, with also no validation set V.ai used during training. In practice, Moscat* achieves its best results when ar is between 0.55 ~ 0.9 and remains stable across this range. The configuration of is shown in Table
Moscat. In this setting. we follow prior work 29 62 to train the gating model on the original validation set. In our experiments, we sample 90% of the original validation set Vval as Vhold and use the remaining 10% for gating validation. In some cases we observe further gains by training the gating model on the full V and validating on Vinan. Thereby, we introduce a binary hyperparameter n E (0, 0.1}, where 17 = 0.1 denotes the former split and r the latter.
Importantly, the validation set serves as a natural holdout set for assessing generalization across training epochs and hyperparameterss Our method, Moscat, can be seen fine-grained extension of this idea: rather than using Vral merely for early stopping, we leverage it to evaluate and weight different experts over node subgroups. In practice, Moscat a plug-and-pll on pre-preeine trained GNN checkpoints without any retraining of the base model; we only train lightweight MLP gating model on the modestly sized validation set (which seldom includes filtered samples from the training set), making it both fast and meemrry-efficient
module that operates
To verify that performance gains arise from expert mixing rather than simply from extra training data, we compare against two baselines in Table 9 Junder the same validation split as Moscat:
GNN-ft: fine-tuning the entire pre-trained GNN on Vval-
GNN-mlp: freezing the GNN backbone and training an auxiliary MLP classifier (taking GNN logits as input) on Veat
The results indicate that additional training on the validation set offers, at best, marginal accuracy improvements and sometimes leads to degradation compared to standard GNNs, likely due to the small size of Vaa and the risk of overfitting. Together with the consistently superior gains of Moscat+,
23

---

Table 10: Hyperparameter settings for Moscat. We additionally include the original node features as the gating model input for all expert models in the amazon-rating dataset. We observe that node features are highly informative for the gating model prediction the amazon-ratings dataset, but they have negative effects or no impact on other datasets.
Moscat specific hyperparameters
Hyperparameters for MLP
Datasel
Model
Ien
?
mask wrong
learning rate
hidden dim.
norm
SGC-Moscat
6
0.1
0.001
GCN-Moscat
0.1
0.005
128
Squirrel
GAT-Moacat
0.1
0.001
128
GCNI1-Moscat
0.1
0.0005
128
4ON-GC8-Moscat
0.1
0.001
128
SGO-Moacat
6
0.1
1
0.00005
256
batch
GCN-Moscat
6
0.1
0.5
0.00005
256
batch
amazon-ratings
GAT-Moscat
6
0.1
0.3
0.0001
256
butch
GCNII-Moscat
6
0,1
0.9
0.0001
256
batch
ACM-GCN-Moscat
0.00005
256
batch
SGC-Moscat
6
0.1
0.005
256
hatch
GCI-Moacat
6
0.1
0.005
256
batch
Penn94
GAT-Moscat
6
0.1
0.0001
batch
GCNII-Moscat
butch
4CH-GCN-Moscat
0.1
0.00005
256
layer
SGC-Moscat
6
0.001
GCN-Moscat
0.001
256
Flickr
GAT-Moacat
0.001
256
GCNII-Moscat
0.1
0.0001
256
4ON-GC8-Moscat
0.1
0.001
256
SGC-Moacat
0.005
256
layer
GCN-Moscat
6
0.1
0.005
256
layer
arxiv-year
GAT-Moscat
6
0.001
256
layer
GCNII-Moscat
6
0.1
0.005
256
layer
ACM-GCN-Moscat
layer
SGC-Moscat
6
0.1
0
0.0005
256
hatch
GCN-Moacat
6
0.1
0
0.00005
256
batch
genius
GAT-Moacat
6
0.1
0.00005
layer
GCNII-Moscat
layer
ACM-GCX-Moscat
0.1
0.00005
256
layer
SGC-Moscat
6
batch
GCN-Moscat
0.005
128
batch
suap-patenta
GAT-Moscat
0.005
128
batch
GCNII-Moscat
6
0.005
128
batch
4ON-CC8-Moscat
6
0.005
128
batch
SGC-Moscat
6
0.1
1
0.001
256
layer
GCN-Moscat
6
0.1
0.9
0.0005
256
layer
ogbn-arxiv
GAT-Moscat
6
0.1
0.9
0.0005
256
layer
CCNII-Moscat.
6
0.1
1
0.0005
256
layer
ACM-GCX
LCN-GCN-Noscat
6
0.1
0.0005
layer
24

---

these results confirm that our improvements stem from adaptive expert mixing rather than from naively adding more labeled training data.
F.3 Baselines
To evaluate the flexibility of Moscat, we select three classic homophilous GNNs (GCN (28).
SGC [65). GAT [60]), and two state-of-the-art heterophilous GNNs (GCNII [8, ACM-GCN 44))
which cover comprehensive GNN architectural designs. We note that many scope mixing methods
have assumptions about GNN architectures. For example, [18] can only be used on decoupled GNNs
like SGC, while 40 34 70 are incompatible with GNNs using learnable aggregators like GAT. We
further compare our methods with four models designed for node classification under heterophily:
H2GCN [33] GPRGCN [TT] FSGNN [46]. MixHop [ three Graph Transformers: GraphGPS [55
SGFormer [66], Polynormer [5]; and three Graph MoEs: GMoE [1], Mowst [78), DA-MoB 75
We also include skip-connection methods designed for deeper GNNs: Jumping Knowledge
68
GAMLP 81 and G G2-GNN 57
F.4 Hyperparameters
In this section, we first clarify the hyperparameter settings for both GNNs and Moscat, Then, we provide detailed instructions and analysis for Moscat tuning.
Table 5 shows the hyperparameter search range for baseline GNNs. We set them according to the original paper for other special hyperparameters. Unless stated, we do not tune GNNs with residual connections or jumping knowledge. We also include an extra dropout layer on the input node feature, using& dropout ratio different from the one after each hidden layer. For SGC, we an MLP instead of a single linear layer. For every MLP, including the one used in Moscat, we add residual connections and fix the number of layers to 3.
We observe that normalization is important for GNNs, especially on larger datasets, and tuning the depth can provide substantial accuracy gains. With proper hyperparameter tuning, classic GNNs are strong baselines on heterophilous graphs, which aligns with recent works' observation [53] 42). When tuning the hyperparameters of the MLP in Moscat, we notice it is not sensitive to the number of transformation layers. Setting the number of layers to works well in every setting. We also find that Moscat faces an accuracy drop when setting dropout feature dropout to value larger than O. Therefore, we set the layers of MLP to 3 and dropout to zero for all settings, as shown in Table 10
We further investigate tuning the Moscat-specific hyperparameters. Table displays each hyperpa- rameter's explanation and search range. For the hidden dimension of Moscat, we notice that Moscat often works well when setting the dimension to 256. In smaller datasets such as Chameleon, we observe that a lower dimension is enough and enjoys better training. We limit the dimension for dataset to 128 due the GPU memory constraint. Note that set the upper bound of the Moscat maximum scope size Lmax to 6, rather than limiting it to a shallow 2 to 3 hop neighborhood (77) expanding it to global scope (3 This is because (1) shallow scope does not contain sufficient homophily in heterophilous graphs 83 and (2) according to the six degrees of separation theorem, 6-hop neighborhood is already large enough for many Wikipedia, citation, and social networks. Further increasing the scope size will only provide marginal improvement. As shown in Table TO setting Lmux works best in most cases. Limax can be used crucial parameter to trade off accuracy and overhead (see Appendix G.4for more details).
the anap-patent
Table 10 shows the best hyperparameters for Moscat results presented in Table same hyperparameter configuration as Moscat, with an additional hyperparameter a tuned separately (see Table for best configuration and Appendix F22 for more details). We additionally include the original node features as one of the inputs for all models in the amazon-rat ratings dataset (not for other datasets) since we observe that node features are highly informative for mazon-rating but have adverse or negligible effects on other datasets.
I Moscat* uses the
F.5 Software and Hardware
We implement Moscat using Python 3.11, PyTorch 2.0.1, PyG 2.4.0, and CUDA 12.2. All the experiments are conducted on machine with dual 96 Core AMD EPYC 9654 CPUs paired with
25

---

Table 11: Leaderboard comparison. ACM-GCN+ and GloGNN++ MLPs transform the entire adjacency matrix, which is only applicable to the transductive setting.
Rank
amazon-ratings
Penn94
PubWed
1"
55.54 10.51
86.18 00
91.95 +:0.1 GNNDLD [6
tuned-GAT 43
PatMMLP 82
2d
54.92 +:0.2
86.09 =0.56
91. +:0.50
NII
Dual-Net
NHGCN
3
54.81 +0.49
86.08 -043
-:0.59
Polynormer [5
ACM-GCN+ 40
ACM-Snowballl (40
56,66
00.57
87.13 0045
92.40 :0.46
Ours
SAGE-Moscat (Lam 6)
MixtHop-Moscat (Luu 16)
GCNII-Moscca Moscat (Leas 6)
1,TBB ECC-DDRS RAM and a single NVIDIA RTX 6000 Ada GPU with 48GB ECC-GDDR6 VRAM.
G Additional Experiments and Analysis
G.1 Leaderboard Comparison
Since Moscat is flexible for GNNs with various architectures, can GNN-Moscats achieve state-of- the-art performance? To answer this, Table IT summarizes our comparison with the top methods reported amazon-ratinn ratings, Penn94, and PubMed leaderboards from Paper With Code. To the best of our knowledge, we find two methods, NID [42] and PathMLP (82), have reported top performance but have not been included in the leaderboard. We also include this method in comparison. The result demonstrates the superior performance of GNN-Moscat. Note that we follow the standard setup for training the base GNN models and do not include any additional tricks.
G.2 Runtime Analysis
Let L' denote the number of MLP layers and Fbia denote the hidden dimension. The time complexity of the gating model F is bounded by O (C'Lmx)V/ (/ + |V| + L' (
Although GNN-Mosccat requires first individually training Lmux + 1 GNN experts and then training an additional gating model, it does not add much overhead during training. This is due to:
1. Model depth is one of the most critical hyperparameters for GNNs on heterophilous graphs, with deeper models typically achieving better performance. Regardless, training GNNs with to 6 layers is necessary during the hyperparameter search for the optimal number of layers L. Table 12 shows the accuracy when fixing the number of layers of the baseline GNNs to 2, well as the accuracy when selecting the optimal number of layers through hyperparameter tuning.
2. Since GNNs of different depths can be trained in parallel, the total (parallel) training time for GNN-Moscat has two components: the time to train the deepest GNN (L = Lmma) and the gating model training time. The simplicity of our design enables efficient utilization of the GPU resources, while other personalized scoping methods require complex architecture (e.g., GNN-G emmploss additional GNNs for gating at each layer) or significantly longer training epochs (e.g., Mowst iteratively trains GNNs and the gating module). Table shows the parallel training time of Moscat remains low compared other methods.
3. Moscat can be flexibly applied to shallow GNNs only while maintaining significant accuracy improvements, reducing the computational overhead of training deeper GNNs. As shown in Figure 7 and 8 the majority of accuracy gains from Moscat occur with GNNs of depth L 4.
26

---

Table 12: Performance comparison for GNNs with different depths.
Model
Chanelocn
Squirrel
arxiv-yoar
genius
1,=2
38.79
39.55
45.28
87.53 88.01 (L=1)
L-hest
(L=3)
40.04 (L==1)
45.88 (L=4)
GCN
L=2
39.75
40.56
43.76
89.15
1.-hest
41.74 (1.-))
(1.=6)
48.68 (1.+5)
(1.m4)
GAT
L=2
37.97
37.57
50.16
86.53
(L=5)
(L=4)
52.77
(L=4)
Table 13: Parallel training time comparison.
Chameleon
amazon amazon-ratiine ratings
Penn94
GCN (L=6)
1.5% (x1000)
12.67s
7.27s (x1.00)
Moscat
x0.19
x0.16
x0.23
GCM CCR-Moscat
x1.19
x1.16
x1.23
GCN-Attn
x1.40
x2.63
x2,34
GCN-G"
x1.79
x13.6
x3.36
GCN-Mowa
x61.6
x41.9
x23.4
G.3 Space Analysis
Moscat allows each expert and the gating model be trained separately. Practitioners can flexibly adjust the parallelism of expert training to balance runtime and memory consumption. Let Lmax denote the maximum depth of GNN experts, P'iia denote the hidden dimension, and Vexp and Vgat denote the training sets for experts and the gating model, respectively. Taking GCN as an example, we have two boundary cases:
If we prioritize minimal memory overhead, can train each expert sequentially. The space complexity is therefore bounded by training the deepest GNN expert: (LLmxx|Vess Finat + Lmax
If we prioritize minimal runtime, we can train all experts in parallel. The space complexity then becomes proportional to the total number layers (1 + .... Immax) across all experts: O (L Vexpp Fhid L L 422
The memory consumption of the gating model training is relatively small and won't 't become bottleneck: O (Lmax |'i + Pia) since Fiis < [Vaaeel < \Vexpl- In conclusion, with comparable runtime, Moscat requires approximately Lmax times more memory than single Lmaxx layer GNN during training.
G.4 Depth Analysis
We investigate how GNN-Moscct performance changes when varying the maximum depth T.max of GNN experts. Figure and Figure[Jcompare the performance of GNN-Moscat and corresponding GNN on amazon-rating
dataset and arxiv-year dataset, respectively. As depth increases, GNN performance first increases and then decreases or remains unchanged, which is undesirable given deeper GNNs superior expressive power [3 In contrast, GNN-Moscat leverages depth more effectively, showing a consistent upward trend performance as expert depth increases. This indicates promising characteristic of GNN-Moscat: it does not require careful tuning of L tuning to achieve good performance. We found that Lmax = is a good trade-off between accuracy and computational overhead for all datasets and all base GNNs. For cases with strict runtime requirements, setting Lmx = 2 for GNN-Moscat consistently achieves performance that better than or comparable the best GNN with depths between and 10.
G.S Empirical Evidence of Deeper Soft Scoping Methods Suffer from Overfitting
We plot the training and test accuracy representative soft scoping method ACMGCN 40 (see Figure D). The figure demonstrates that the 6-layer ACMGCN achieves higher training accuracy than the 2-layer version. However, in homophily regions, the 6-layer model exhibits lower test accuracy. This suggests that while deeper soft scoping methods offer greater expressive power, they are also
27

---

030
Figure 7: Performance comparison between GNN and GNN-Moscat on amazon amazon-rating ratings dataset. The x-axis represents the number of layers for GNN and Lmax for GNN-Moscat.
Figure 8: Performance comparison between GNN and GNN-Moscas on arxiv-year dataset. The x-axis represents the number of layers for GNN and Tanax for GNN-Moscat.
prone to overfitting, Considering the architecture of soft scoping methods, we speculate this issue arises because shallow layers/experts in soft scoping models may overfit to noise from higher-hop neighbors.
G.6 Supplementary Details for Satrophily-Biassee Sample Filtering
Heterophily nodes exhibit more diverse neighhorhood label patterns than homophily nodes, which makes them more challenging for experts to generalize from. As result, experts typically show a larger generalization gap on heterophily nodes. When experts overfit Vexp-het (i.e., the heterophilous nodes in Vexp), their logits on these samples show high prediction accuracy with high confidence. Consequently, the gating model may incorrectly assign large weights to these overfitted experts on heterophily nodes after training on Vexp-het-
To further illustrate the effectiveness and reasoning behind Vexp-het filtering technique, demon- strate an example using GCN and SGC on the maazon-ratingg dataset (see Figure TOP. When comparing the homophily-accuracy curves for experts of depths 0 to 6 across the training, validation, and test sets, we observe that:
The curves for the validation and test sets are nearly identical.
Although the training set's curves align with those on the validation set in the homophily region, they show significant deviations in the heterophily region.
These findings motivate us to exclude samples from Vesp-tet when training the gating model.
G.7 How Expert Training Affects Moscat Performance
In this section, we analyze how expert training affects performance by varying the dropout ratio, hidden dimensions, and training epochs for each expert. We set to "'" for all GNN-Moscat models in this analysis. Although we did not tune the GNN experts for enhanced GNN-Moscaa performance in Table[2] the insights from this hyperparameter tuning suggest that further improvements accuracy can be achieved for GNN-Moscat models.
Table 14 presents a performance comparison between GAT and GCNII, along with their Moscat variants (GAT-Moscat and GONII-Moscat), across various dropout ratios on two homophilous datasets: arxi arxiv-year and PubMed. We observe that the dropout ratio decreases, the accuracy of both GAT and GCNII experiences a slight decline, suggesting an increased risk of overfitting. In contrast, the Moscat versions exhibit an improving accuracy trend.
This phenomenon is further explained by analyzing the distribution of nodes into three categories:
1. "All wrong" nodes misclassified by all experts.
28

---

ACMGCS
AQH-20VIL-E)
Thaiiing
1890
3393
3.90
3330
3303
14
83
622
644
0,5
0.3
0.2
0-4
6.6
0.5
Figure 9: Training and test accuracy the shallow (L = 2) and deeper (L = 6) soft scoping method ACMGCN on the amazon-rat dataset. Results indicate that deeper ACMGCN exhibits more pronounced overfitting, particularly on homophilous nodes.
Vaining Sat
Validation
Pager Dopth
80
0.2
Homoppity
Homoppii
Homopniy
Figure 10: The accuracy of GCN experts training/validationnneen sets of the amazon
dataset. The red dotted line shows the average homophily ratio of the training set.
2. "All correct" nodes correctly classified by all experts.
3. "Others" nodes that do not fall into the above two categories
Table 14 indicates that with decreasing dropout, the percentages of "all wrong" and "all correct" nodes both decrease while the proportion of "others" increased This shift creates a larger margin for possible performance gains when applying Moscat. Moreover, both GAT-Moscat and GCNII-Moscat consistently outperform their standard GNN counterparts across different dropout levels. This suggests that incorporating Moscat enhances robustness and stability across varying dropout settings.
We further compare the performance of GCN, GAT, and their Moscat variants on the heterophilous dataset amazon-ratee -aazon-ratings. Table illustrates how test and training accuracies evolve as the hidden dimensions for all experts increase. For both GCN and GAT. test accuracy shows only modest improvements while training accuracy increases substantially, highlighting an increased generalization gap. In contrast, although the test accuracies of GCN-Moscat and GAT-Moscat also improve, the performance gains relative to their base models follow different trends. Specifically, the accuracy gains of -CMMMss over GCN gradually decrease with larger hidden dimensions, whereas those of GAT-Moscat over GAT continue to increase. This divergence is explained by the observation that, with increasing hidden dimensions, the percentage of "all correct" for GCN experts rises, while the percentage of "all wrong" for GAT experts falls-leading to distinct variations in the performance margins when applying Moscat.
To investigate the effect of expert training on Moscat performance, we selected experts from check- points at 300, 1000, and 2000 training epochs, corresponding to underfitting (i.c., low test and training accuracy), well-fitting (i.e., good test and training accuracy), and overfitting scenarios (i.c., similar test accuracy but much higher training accuracy), respectively. Figure T6 shows that training epochs increase, for both GCN and GAT experts, the frequency of "all wrong" predictions decreases, while "all correct" predictions initially rise and then decline. For GNN -Mscctt it is desirable for experts to fit the training data properly; however, the benefit overfitting depends on the expert architecture (e.g., GAT benefits more from overfitting, whereas GCN does not).
Overall, these experiments suggest promising directions for tuning experts to enhance Moscat performance further. Additionally, we note that GNN experts exhibit higher percentage of "others"
29

---

Taining Set
Vildation Set
Test Set
30
Homopnityy
Homepptyy
4omophiy
Figure 11: The accuracy of SGC experts on Training/vlliaationness sets of the amazon-ratings dataset. The red dotted line shows the average homophily ratio of the training set.
Table 14: Test accuracy comparisons across different dropout ratios for GNN experts. We set Lmmxx 6 and fix other GNNs and Moscat hyperparameters. For GAT and GCNII, we report their best accuracy across configurations with 1-6 layers.
Dropout
0.5
0.3
0.1
GAT
72.14 +0.17
72.17 =0.17
72.01
=0.22
All wrong
18.9%
18.0%
17.6%
ogbn-arxtt -rxiv
All correct
56.5%
56.5%
56.0%
Others
25.1%
25.6%
26.4%
GAT -oscat
73.69 40.19
73.85
#:0.20
73.91
#:0.6
A
+1.55
+1.68
+1.90
GCNII
91.27 40.51
91.18
#0.72
91.20 =0.65
All wrong
5,4%
4.6%
4.6%
PubMad
All correct
86.1%
84.8%
84.7%
Others
8.5%
10.6%
10.7%
CONTI-Moscat
92.04 +0033
92.32 +:0
92.24 =0037
+0.83
+1.14
+1.04
Table 15: Test accuracy comparisons across different hidden dimensions for GNN experts. We set Tynux 6 and fix other GNNs and Moscat hyperparameters. For GCN and GAT, report their best accuracy across configurations with 1-6 layers. (00.00 +.0000) denotes the corresponding training accuracy.
Hidden Dimensions
128
256
512
GCN
47.33 =:0.5
48. ::066
1:0.88
(59.03 1:1554
(61.51 4:2.33)
(63.25 1:2.85)
All wrong
30.1%
30.1%
30.0%
correct
17.2%
Others
53.1%
52.7%
52.6%
GON-Yoacas
50,75 =0.87
$1.07 +0.50
51.34 #0.68
amazon-ratinga
+3.42
+2.89
+2.79
48.55 #:055
42 #6.56
49,78 ::0.47
GAT
(59.19 1:156)
(65.20 605.200.
(:0.88)
(72,42 1:0.9)
All wrong
29. 5%
28.8%
27.0%
17.2%
17.2%
17.0%
Others
$3.3%
54.0%
56.0%
GAT -oscat
50.68 10055
$1.57 10.53
52.43 10.57
A
+2.13
+2.15
+2.65
heterophilous graphs than homophilous graphs, which may explain why Moscat achieves significant accuracy improvements on heterophilous graphs.
G.8 Interpretation and Visualization
The above experiments have demonstrated the effectiveness of Moscat in improving GNN gener- alization by mixing GNN models with different scopes. To further understand how expert mixing influences generalization, we introduce variant of Moscat called Adaptive Scope (AS). In this variant, instead of predicting node labels, the gating model predicts the IDs of scope experts.
30

---

Table 16: Test aceuracy comparisons across different training epochs for GNN experts. We select checkpoints at 300, 1000, and 2000 training epochs for each expert, representing underfitting, well- fitting, and overfitting states, respectively. and Moscat hyperparameters. For GCN and GAT, report their best accuracy across configurations with 1-6 layers. (00.00 +0.00) denotes the corresponding training accuracy.
set Im = 6, expert droput to 0, and fix other GNNs
Training Epochs
1000
(underfiting)
(well-fittin)
(overfitting)
44.73
48.34 1:049
48.22
GCN
(51,50 +:1899
(65.47 +0.92)
(68.42 +1.13)
All wrong
8%
29.7%
26.9%
correct
11.7%
17.9%
16.0%
Others
58.6%
52.4%
57.1%
GON -assact
49.03 1.0.2
51.11 1.0.64
51.27 1.074
amszon-Tatings
A
+4.30
+2.77
+3.05
GAT
46.
+:0.5
49.53 +0058
49,59
(54.56 1:1,7)
(67.44
1:0911
(78,39 1:1115)
All wrong
29.6%
27.0%
23.4%
correct
12.9%
16.8%.
16.4%
Others
57.5%
56.2%
60.2%
GAT-Moacat: A
+0075
52.12 +0.64
+:045
+2.32
+2.59
+3.75
O-layer GNN (MIP)
prediction
2-layer
AS prediction
prediction
Figure 12: (Left) Visualization of t-SNE on GNN embeddings for Penn94. Green and orange dots indicate nodes with different labels. (Right) In each embedding visualization, nodes that AS (a variant of Moscat) predicts to have the corresponding depth are highlighted.
To analyze the behavior of AS, scope experts, which are GAT models with layers ranging from 0 to 2, on the Penn94 dataset add output linear layer to each GAT model and visualize the
t-SNE 59 to visualize the hidden embeddings from three
(Figure Left). Specifically, hidden embeddings just before this layer. Since AS predicts the optimal scope expert (i.e., Scope-0, 1cope-1, or Scope-2) for each node, we highlight nodes according to the predicted scope expert in the embedding visualization (Figure 12 Right).
From Figure 22
we make three key observations:
AS tends to select nodes that the model can differentiate more easily.
2. The nodes chosen by are located near the center of each cluster.
3. An outlier in one model's embedding can serve as the center in another model's embedding.
31

---

These findings support our hypothesis that GNNs with different depths can generalize better on different subsets of nodes.
G.9
More Empirical Findings of Performance Disparity across Scope Experts
empirically examines our theoretical findings through several experiments. this section, we extend these experiments to include more GNN models and datasets.
Section 3.3
G.9.1 Overlapping Ratio
Figure 13 and Figure 14 present heatmaps of the Jaccard overlap ratios (of correctly predicted test nodes) between pairs of scope experts (scope sizes 0-6) for five GNN architectures (SGC, GCN, GAT, GCNII, and ACMGCN) across multiple datasets. Darker cells denote lower overlap in each matrix, indicating that the corresponding expert pair correctly predicts largely distinct sets of test nodes, while lighter cells indicate higher overlap. Based on these two figures, we make several observations:
Scope-0 and Scope-1 experts diverge most: with scopes of 0 and exhibit the lowest overlap with other experts, suggesting they capture unique information relative to larger-scope variants.
Across architectures and datasets, experts
2. Dataset homophily drives overlap: Heterophilous datasets (e.g., Chameleon, Squirrel, and snap-patents with average node homophily less than 0.2) show consistently low overlaps (often < 0.7), whereas homophilous datasets (e.g., arxiv-year, PubMed) yield high overlaps (often > 0.7).
3. Architectureddepeddett diversity: Attention-based models (GAT, ACMGCN) produce lower overlaps and more varied patterns, particularly GAT Penn94 and ACMGCN Pubmed, indicating greater specialization among experts. In contrast, the decoupled SGC architecture exhibits uniformly higher overlaps, reflecting more redundant predictions among its experts.
G.9.2 Performance Disparity
Theorem 3.3 reveals a clear generalization disparity between shallow and deeper experts across node homophily subgroups. Specifically, the disparity related to the average node homophily ratio the training set. Although our theoretical analysis is based on SGC, our experiments indicate that the observations also hold for other, more complex GNNs.
Figure 15 illustrates the performance gap between deeper and shallow experts across several datasets. In the figure, a positive bar indicates that the deeper experts outperform the shallow ones. The results confirm our theory by showing significant performance differences between regions divided by the average homophily ratio.
We also notice distinct patterns across various GNN architectures:
SGC and GCN: regions with low homophily (heterophilous regions), deeper experts always perform worse than shallow experts.
50C
GCN
GAT
CCMI
ACHDON
pubmed
L-3
1-3
Lx3
L45
SGC
GCN
GC
GOM
ACMGON
Led
be0
L40
140
1-1
66
arxiv
L-2
1/2
140
145
L46
Figure 13: The overlapping ratio matrices for scope experts on homophilous datasets.
32

---

30C
60X
CCM
ADMSON
chameleco leon
Lsb
Lan
Lot
L-
Lod
ADMSON
squirrel
Lig
Loa
Los
Lid
Lnd
L-EL-1 Ln
DEL-11--1-Stae--10 L=Bl-1 Ln 1- (-44----
penn34 amazon. Fariang
Lea
Lnd
Ud
Lod
L-d
[+ Ladttaat
Lobtet to
L-d
Led
Lo4
Li5
Ld5
L-6
Li0
flickr
Ui5
L-5
SDC
COI
COVI
ADMSON
-as
arxiv- year
L-4
L-0
Lid
LoB
SGC
60
66
GOVI
ADNSON
Lig
L-6
L10
Lid
L-d
Lxt
genius
L-EL-1 BLL--L----3------00
50C
COI
GC
COII
AOMSOV
snap- patents
Lab
Lid
Litto wwd Lo Figure 14: The overlapping ratio matrices for scope experts on heterophilous datasets.
L- una Lodk-rink
L-dued Lod Lod L.4
L= bodt-ii
Led Lov Lov--- Lod
GAT and GCNII: In these architectures, deeper experts sometimes outperform shallow experts even in heterophilous regions.
ACMGCN: Here, deeper experts consistently outperform shallow experts heterophilous regions.
A possible explanation for these differences is that GAT, GCNII, and ACMGCN incorporate specific designs for handling heterophilous information. For instance, GAT uses attention- neighbor aggregation, GCNII applies inception residual connections, and ACMGCN integrates both high-pass and full-pass filters. In contrast, SGC and GCN lack these mechanisms. particular, stacking multiple high-pass and full-pass filters appears be highly effective for learning heterophily.
33

---

equiiig
Test accuracy differences between deeper and shallow experts. Positive values (blue) indicate deeper experts perform better, while negative values show shallow experts perform better. The red dotted line shows the average homophily ratio of the training set. We have observe the following trends. The deeper variants of homophilous GNNs (e.g., SGC, GCN) tend to perform worse than their shallow counterparts in heterophily regions. For GNNs designed for heterophily (e.g., GAT, GCNII, ACMGCN), some cases, their deeper variants can outperform shallow ones in heterophily regions. Notably, the deeper variant of ACMGCN consistently outperforms its shallow variant across all datasets, which underscores the effectiveness of its high-pass filter in leveraging heterophily.
Figure 15:
G.9.3 Ensembling Upper-bound
We further investigate the extent of the observed generalization disparity across different GNN architectures and datasets. Specifically, for given set of scope experts, we determine the upper bound by calculating the percentage of nodes correctly predicted by at least one expert. Figures I6 and 17 illustrae the upper bounds for homophilous and heterophilous datasets, respectively.
Across representative GNN architectures, all datasets exhibit sub-linear curves and notable accuracy improvements, ranging from approximately 10% to 50%, Lmux increases. This trend suggests that test-time scaling promising by increasing the number of experts for different scopes.
Furthermore, our findings indicate that GAT, GCNII, and ACMGCN are best performing architectures with sufficiently large T whereas SGC tends to perform the worst. These results underscore critical role of expert architectural design.
34

---

SGC
2C4
G4T
ACMGO
pubmed
arxiv
Test Accuracy
0.25
0.54
0.92
0.93
0.00
0.89
Letar
Figure 16: Upper-bound test accuracy achieved by scope expert ensemble on homophilous datasets. We report the percentage of nodes correctly predicted by at least one expert with the depth ranging from L (where n < 6).
SGC
GCN
GAT
GENII
ACMGON
0.75
0.70
0.3
0.55
0.30
0.55
0.85
0.5
0.50
0.40
andiwyear
1.50
qarius
anapp-attems
0.70
0.55
0.3
0.35
0.7
0.50
0.6
0.30
0.6
6.55
0.55
0.50
0.50
Arus
Figure 17: Upper-bound test accuracy achieved by scope expert ensemble on heterophilous datasets. We report the percentage of nodes correctly predicted by at least one expert with the depth ranging from L 0 to (where n < 6).
G.10 Analysis of the Gating Weights
Figure and Figure illlsttrate the distributions of gating weights for various experts in Moscat.
The results indicate that Moscat effectively learns gating weights, thereby preventing the collapse issue (i.e., some experts receive extremely small weights across nodes) noted in prior studies [55] 58). Moreover, the gating model tends to assign larger weights with greater variance to shallow experts (c.g., Scope-O and Scope-I) compared to deeper ones. This behavior suggests that Moscat
SGC
GCN
GAT
GCNI
ACMECN
pubmed
GCN
GAT
(CNI
ACMEON
a
Densty
5
6125
0256 value
AJ50
0.244 vallum
0.340
6.540
0.045
valuu
Value
volue
Figure 18: Learned attention-based gating weight distributions on homophilous datasets. Different color denotes the weight distributions for different scope experts.
35

---

chameleon
0.399
0039
1144
036 K13
1140
0.34
S2C
GON
GAT
GCMI
ACNOCN
squirrel
GAT
amazon ratings
1-48
0.79
0336
6.10
8139
0333
03.8
3.19
5:45
6:36
6339
0239
5140
0255
5.59
6333
5:44
5.143
59
penn94
50C
60h
GAT
6CHI
ACNOCN
fllckr
E12
5128 0018
622
024
0.14
8.20
5.10
5.130
arxiv-year
53
6.14
0.75
314
K1R
8138
0348
0.000
0.148
0366 0258
6.2
130
53C
GON
GAT
15.
GCNI
ACNOON
genius
Dendty
40
vallue
villue
villue
Figure 19: Learned attention-basse gating weight distributions on heterophilous datasets. Different color denotes the weight distributions for different scope experts.
36

---

learns more personalized weights for shallow experts, while it adopts more uniform weighting scheme for deeper experts. One plausible explanation for this trend is that increasing the scope size leads to a higher likelihood of overlapping neighbors among different nodes. Therefore, the gating model tends to learn the same weight on deeper experts for these nodes.
37

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Our abstract clearly reflects the contribution and scope of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The proposed method might not be effective for datasets with high homophily ratios (e.g., with homophily score larger than 0.8). Please refer to Section 3.3 for details.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
38

---

Justification:
Our theory assumptions and proofs are mentioned in Section 3
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: In Section of the paper, we provide detailed description of the method we propose. Experimental settings and hyperparameters reported in the Appendix
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome deseribe the particular way they provide for reproducibility, In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
39

---

Answer: [Yes]
Justification: The code is available an annoyymos repository and is included in the Supplemental Material.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (https
ssicnlolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Details of the experimental setup and hyperparameters are provided in the Appendix F
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer:
[Yes]
Justification:
We report the standard deviation across multiple runs.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the eтror bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
40

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative еπхо rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We include all the details in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
Our research conform with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:[NA]
The paper proposes general- purppse algorithmic method and does not target any specific application domain, so societal impacts are expected to minimal and were not discussed.
Justification:
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
41

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper provides code but does not release any data or models with potential for misuse.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All of the creators original owners of assets used in our paper are cited properly.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URI
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
42

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The paper introduces new algorithm and provides code with basic documen- tation.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve human subjects or crowdsoureing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
43

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification: LLMs only used for minor editing.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non -tandtdndard components.
Please refer to our LLM policy (https: for what should or should not be described.
44


Reviews:
[{"review_id": "m3BOaQxDZP", "reviewer": "Reviewer_2PbC", "summary": "The authors propose Moscat, a framework for training a mixture of GNNs that addresses existing limitations of over-smoothing and generalization. Different from previous work relying on mixtures of experts (MoE) where experts are trained jointly together with an agreggation module, Moscat proposes to train experts separately (and possibly simultaneously), and then train a gating module aimed at combining their strengths and improving generalization. The authors present extensive theoretical and empirical findings motivating Moscat, as well as experimental results that demonstrate the effectiveness of their proposed approach.", "questions": "1. How much more expensive is it to run Moscat in terms of memory usage, in comparison with a single GNN?\n2. Is Moscat robust to the way the data is split for generating the hold-out set used to train the gating model?\n3. When faced with new datasets in real world problems, how would you advice practitioners starting with Moscat to make the large number of options (underlying GNN architecture, number of layers, hold-out set, heterophily-biased sampling, scope-aware logit augmentation, plus tunable hyperparameters) more manageable?\n4. Could you please clarify which parts of Moscat adress each of the challenges listed at the beginning of Section 4 (L217-226)?", "limitations": "The authors do not discuss the limitations of Moscat (apart from a short sentence in the Checklist), which justifies my Quality score. I would advice the authors to reflect on limitations such as cost, and the lack of a more principled approach, which could help understand the method as well as making future directions of research more clear.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. The authors provide a comprehensive motivation for their approach, rooted in issues like over-smoothing, vanishing gradients, and overfitting. Theorem 3 is insightful as it points to an explanation for the low performance of GNNs in some cases, involving disparity of generalization between homophilous and heterophilous groups of nodes at different layers of a GNN.\n2. The previous result is accompanied by experiments that support the low overlap between correctly classified nodes across different layers of a GNN.\n3. In spite of several heuristics included in Moscat, the overall approach is simple and intuitive: instead of designing specific GNNs, or jointly training experts, train separately L experts and then train a gating model. This is useful because the framework can be applied to a broad class of GNNs, as evidenced in the experiments.\n4. The approach incorporates heuristics that are well motivated and effective, such as heterophily-biased sample filtering and scope-aware logit augmentation.\n5. The improvements brough by Moscat are clear and significant, both when examining the improvements over the same architecture, and in comparison with strong baselines (including MoE approaches).\n6. The authors provide ablation experiments that justify the different parts of Moscat (Table 4) and interesting interpretation experiments in the appendix.\n\n**Weaknesses**\n\n1. The fundamental message behind Moscat is that in general, a single deep GNN is almost guaranteed to perform poorly on node classification. Therefore, the solution is to train several GNNs of different depths, while learning how to combine them properly. This means that the cost of training Moscat is always larger than the cost of a single GNN.  Runtime analysis is deferred to the appendix, though I believe it should play a more central role; but more importantly it should also include a **space complexity** analysis, together with experimental results, that answers the question: how much more expensive is it to run Moscat? This would help contextualize if the observed gains are worth the cost.\n2. The hold-out set seems important for training the gating model, but it seems that the authors adopt a single static way to generate this split. Whether this is a source of variation in performance is not clear.\n3. The approach is composed by several moving parts (underlying GNN architecture, number of layers, hold-out set, heterophily-biased sampling, scope-aware logit augmentation, plus tunable hyperparameters), rather than a more principled solution to the issues of GNNs discussed and found by the authors. I would expect that this would limit the practical impact of Moscat due to increased systems complexity and optimization cost, in contrast with a more principled solution.\n4. Even though the paper is focused on the case of heterophilous graphs, it would have been interesting to see if Moscat also works well on homophilous graphs. The closest case is Pubmed, but extending these experiments would further increase our understanding of how performant and broadly applicable Moscat is.", "was_revised": true, "final_justification": "The authors have addressed all my remarks and questions during the rebuttal and discussion periods. These even led to additional insights that I hope the authors can incorporate in their work. I therefore keep my recommendation for acceptance.\nI think this is a solid contribution, and as such I would be willing to champion this paper if necessary.", "rebuttal": "We sincerely thank the reviewer for the encouraging and constructive feedback.\nOur detailed responses are as follows.\n\n## W1 / Q1\nThank you for your constructive comments. We agree that space consumption should be carefully considered.\n\nMoscat allows each expert and the gating model to be trained separately. Practitioners can flexibly adjust the parallelism of expert training to balance runtime and memory consumption. Let $L_\\text{max}$ denote the maximum depth of GNN experts, $F_{\\text{hid}}$ denote the hidden dimension, and $\\mathcal{V}\\_{\\mathrm{exp}}$  and  $\\mathcal{V}\\_{\\mathrm{gate}}$ denote the training sets for experts and the gating model, respectively. Taking GCN as an example, we have two boundary cases:\n\n- If we prioritize minimal memory overhead, we can train each expert sequentially. The space complexity is therefore bounded by training the deepest GNN expert: $O\\left(L\\_{\\text{max}}|\\mathcal{V\\_{\\text{exp}}}|F\\_{\\text{hid}} + L\\_{\\text{max}}F\\_{\\text{hid}}^2\\right)$.\n- If we prioritize minimal runtime, we can train all experts in parallel. The space complexity then becomes proportional to the total number of layers ($1 + 2 + \\cdots + L\\_{\\text{max}}$) across all experts: $O\\left(L\\_{\\text{max}}^2|\\mathcal{V}\\_{\\text{exp}}|F_{\\text{hid}} + L\\_{\\text{max}}^2F\\_{\\text{hid}}^2\\right)$\n\nThe memory consumption of the gating model training is relatively small and won't become a bottleneck: $O\\left(L\\_{\\text{max}}|\\mathcal{V\\_{\\text{gate}}}|F\\_{\\text{hid}} + L\\_{\\text{max}}F\\_{\\text{hid}}^2\\right)$, since $F\\_{\\text{hid}} \\ll|\\mathcal{V}\\_{\\text{gate}}|\\ll|\\mathcal{V}\\_{\\text{exp}}|$.\n\n**In conclusion, with comparable runtime, Moscat requires approximately $L\\_{\\text{max}}$ times more memory than a single $L\\_{\\text{max}}$-layer GNN during training.**\n\nWe also measured the peak GPU memory consumption for training GCN and GCN-Moscat with $L\\_{\\text{max}}=6$ as shown in the following table:\n\n|  | L=0 (MLP) | L=1 | L=2 | L=3 | L=4 | L=5 | L=6 | Total (Moscat) |\n| --- | --- | --- | --- | --- | --- | --- | --- | --- |\n| amazon-ratings | 1294MB | 618MB | 980MB | 1194MB | 1418MB | 1616MB | 1832MB | 8952MB |\n| arxiv-year | 1164MB | 772MB | 1026MB | 1240MB | 1474MB | 1688MB | 1922MB | 9286MB |\n\nOn amazon-ratings, GCN-Moscat ($L\\_{\\text{max}}=6$) requires 8952MB, which is approximately **4.9x** more than GCN (L=6) at 1832MB. The arxiv-year dataset also shows a similar ratio.\n\n## W2 / Q2\n\nIn the paper, we examine Moscat on two different setups for the holdout set (Section 5.1): \n\n(1) For \"Moscat\", we use 10% of the original validation set for validating the gating model and the rest for gating model training. We found the accuracy is stable by tuning this ratio between 0%~30%. The accuracy drops gradually by further increasing the ratio beyond 30%. Hence, we fix it to be 10% for all datasets.\n\n(2) For \"Moscat$\\ast$\", we don't use the original validation set for expert/gate training. Instead, we partition a holdout set from the original training set. We introduce a hyperparameter $\\alpha$ to represent the proportion of nodes for expert training, and the remaining $1-\\alpha$ portion serves as the holdout set. Experts have fewer training samples and achieve lower accuracy with a lower $\\alpha$, but the gating model can better capture experts' generalization patterns. Experts achieve higher accuracy with a higher $\\alpha$, but the gating model may be less effective. In practice, we found that the downstream accuracy achieves the best and is relatively stable when $\\alpha$ is between 0.55 $\\sim$ 0.9. The table below shows the accuracy of GCN experts and GCN-Moscat$\\ast$ with different $\\alpha$ values on Penn94. We observed that while expert accuracy decreases as $\\alpha$ decreases, the overall accuracy remains relatively stable.\n\n| $\\alpha$ | 0.6 | 0.65 | 0.70 | 0.75 | 0.80 | 0.85 | 0.90 |\n| --- | --- | --- | --- | --- | --- | --- | --- |\n| GCN | 80.03 ±0.37 | 80.66 ±0.33 | 80.90 ±0.45 | 81.14 ±0.26 | 81.36 ±0.38 | 81.62 ±0.28 | **82.02** ±0.34 |\n| GCN-Moscat$\\ast$ | 84.87 ±0.55 | 85.01 ±0.55 | 85.08 ±0.51 | 85.12 ±0.39 | 85.38 ±0.32 | **85.51 ±0.28** | 85.43 ±0.34 |\n\nWe notice that Moscat$\\ast$ often achieves the best accuracy with $\\alpha$ around 0.85~0.90. Please refer to Appendix F.2 for more details. \n\n## W3 / Q3\n\nThe core reason for Moscat to have all these components is that we want it to be general to various datasets and GNN architectures. While Moscat has a large potential hyperparameter search space, we have established clear, principled best practices that significantly reduce this complexity. These guidelines, derived from our comprehensive experiments and analysis, make adapting Moscat to new datasets straightforward.\n\n1. **Expressive GNN experts.** Although Moscat can adapt to various expert architectures, we observed that Moscat achieves better accuracy with more expressive GNN architectures (e.g., GAT, ACMGCN, MixHop), as shown in Table 1. This occurs because expressive architectures enable GNNs to maintain high training accuracy as depth increases, essential for learning patterns from higher-order neighbors. For details on how expert parameters affect Moscat's performance, please refer to Appendix G.6.\n2. **Moscat hyperparameter tuning.** We organize the entire hyperparameters (hparams) space for the gating model training into three distinct categories:\n    1. **Hparams that do not need to be tuned.** By referring to Tables 6 and 8, we conclude that dropout=0, weight decay=0, number of MLP layers=3, and hidden_dim=256 work well for all settings. The maximum depth $L_{\\text{max}}$ has also been extensively studied in Appendix G.3. The conclusion is straightforward: higher $L_{\\text{max}}$ can achieve higher accuracy but incurs higher cost. We found $L_{\\text{max}}$=6 achieves a good accuracy-overhead balance across all settings.\n    2. **Hparams that require minimal tuning for near-optimal performance.** Learning rate is crucial, as each dataset has its specific range of effective learning rates. Three other binary parameters worth tuning are: holdout-set-related ratio $\\eta$, the \"mask wrong\" flag, and batch/layer normalization. Since these three are all **binary** parameters, the search space remains small.\n    3. **Hparams that can achieve slight improvements with further tuning.** Adjusting the holdout-set-related ratio $\\alpha$ and heterophily-biased sampling related ratio $\\gamma$ beyond their default values can slightly improve performance on some datasets.\n\nFor more comprehensive information, please refer to Appendices F.2 and F.4. Components such as scope-aware logit augmentation can always be employed as they introduce virtually no adverse effects. We will provide this guidance on GitHub with a more detailed, self-contained version to assist practitioners in implementation.\n\n## W4\n\nThank you for your constructive feedback. Our paper already includes results from two homophilous datasets: Ogbn-Arxiv and Pubmed. To address your suggestion, we have evaluated Moscat on two additional widely used homophilous datasets, WikiCS and Amazon Computers, presented below:\n\n|  | Ogbn-Arxiv | WikiCS | Pubmed | Computers | Avg. Improv. |\n| --- | --- | --- | --- | --- | --- |\n| Node Homo. | 0.64 | 0.66 | 0.79 | 0.80 |  |\n| GCN | 72.13 ±0.17 | 80.71 ±0.52 | 90.15 ±0.71 | 91.76 ±0.39 |  |\n| +Global Ensemble | 73.16 ±0.11 | 81.18 ±0.46 | 91.37 ±0.62 | 92.00 ±0.36 | $\\Uparrow$0.91% |\n| +Moscat | 74.09 ±0.32 | 82.39 ±0.46 | 91.97 ±0.44 | 94.27 ±0.49 | $\\Uparrow$2.39% |\n\nWe follow the same settings as in our paper and introduce a new baseline \"Global Ensemble,\" which uses Bayesian optimization to tune the global ensemble weights on the validation set. The results show that Moscat also works well on homophilous datasets, achieving a $\\Uparrow$2.39% average$%$ improvement, significantly more effective than Global Ensemble with only $\\Uparrow$0.91% improvement. However, there's still a notable gap compared to the $\\Uparrow$5.28% average improvement that Moscat achieves on the heterophilous datasets tested in our paper.\n\nAlthough there exist datasets with even higher homophily ratios (e.g., Amazon Photo at 0.85 and Coauthor-CS at 0.92), a single GNN can already achieve over 95% accuracy on these datasets. These datasets are likely too simple and therefore inappropriate for evaluating our method.\n\n## Q4\n\nSection 4 (L217-226) lists the following three challenges:\n\n1. \"Feature construction\" corresponds to \"Scope-Aware Logit Augmentation\".\n2. \"Training sample selection\" corresponds to \"Heterophily-Biased Sample Filtering\".\n3. We have dissected the adaptation to \"Diverse Expert architecture\" into the following three challenges:\n    1. **Over-smoothing:** As discussed in the \"Scope-Aware Logit Augmentation\" paragraph, our \"Structural Encoding\" technique enables the gating model to assess the likelihood that an expert for a given scope will experience over-smoothing.\n    2. **Model degradation (Underfitting):** As discussed in the \"Heterophily-Biased Sample Filtering\" paragraph, we select samples in experts' training set $\\mathcal{V}\\_{\\text{exp}}$ to form the gating model training set $\\mathcal{V}\\_{\\text{gate}}$, which enables the gating model to learn how well each expert fits nodes with various structural patterns.\n    3. **Overfitting:** We also use the holdout set $\\mathcal{V}\\_{\\text{hold}}$ to form $\\mathcal{V}\\_{\\text{gate}}$, which enables the gating model to detect experts' overfitting. We further introduce \"Label Embeddings\" to approximate node homophily, which can predict experts' generalization patterns.\n\nWe will add clear pointers in our revised version to better structure Section 4.\n\n## Limitations\n\nWe appreciate the reviewer's suggestion and will include a dedicated section discussing Moscat's limitations. Due to the space limit, please refer to our response to \"Reviewer Hr9P Limitations\"."}, {"review_id": "xBUDcrIm9A", "reviewer": "Reviewer_rzM3", "summary": "This paper studies the generalization of deep layer GNNs and find deeper GNNs achieve better generalization than their shallow variants in either homophily or heterophily region, they sacrifice generalization performance in the other region. Then, the authors propose a mixture of experts model to select GNNs with different layers for different nodes. Experimental results demonstrate the proposed method can be applied in to different backbones.", "questions": "Please refer to the weaknesses.", "limitations": "The authors should illustrate how do they select the heterophilous nodes and the performance on the low labeling rate.", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n1. The problem of generalization disparity of deep GNNs is worth to explore.\n2. The paper is well-written and easy to follow.\n\nWeaknesses:\n1. The novelty is limited. The generalization disparity of deep gnns has been studied in several papers, for example, GMoE [1] also argue that different nodes require different hop of information. The theoretical analysis majorly follows [2], and I did not find something new here. Also, the MoE in GNNs is also utilized in several papers. For example, Link-MoE [3] also first train different GNN experts and then train the gating model to select different experts for different samples.\n\n2. The authors filter out heterophilous nodes when training the experts. However, the heterophily of nodes are unknown due to the lack of ground-truth. How do the authors select the heterophilous nodes?\n\n3. The authors leverage a high labeling rate in the experiments, which is impractical in the real-world applications. Can the proposed method work well when the labeling rate is low? \n\n[1] Graph Mixture of Experts: Learning on Large-Scale Graphs with Explicit Diversity Modeling\n\n[2] Demystifying structural disparity in graph neural networks: Can one size fit all? \n\n[3] Mixture of Link Predictors on Graphs", "was_revised": true, "final_justification": "I have thoroughly read the authors’ rebuttal. While they have addressed some of my concerns, I still question the novelty of their work. Moreover, based on my own experiments, I remain concerned about the effectiveness of their homophily estimation. I have updated my rating to borderline reject.", "rebuttal": "We thank the reviewer for the time and effort spent reviewing our paper. We appreciate the opportunity to address any concerns and clarify potential misunderstandings. Our detailed responses are as follows.\n\n## W1\n\n> The generalization disparity of deep gnns has been studied in several papers, for example, GMoE [1] also argue that different nodes require different hop of information.\n>\n\nExploring generalization disparities of GNNs across varying depths is crucial and creates new opportunities to advance this field. However, we argue that **this question remains largely unexplored**. \n\nExisting studies like GMoE and ACMGCN primarily focus on designing expressive architectures (e.g., node-adaptive hop aggregation) to better fit training data rather than investigating generalization disparity. In contrast, our work specifically examines generalization, and to the best of our knowledge, we are the first to formally investigate \"How GNNs of different **depths** generalize across **node subgroups**.\" We also establish novel and significant conclusions, such as \"Varying the depth shifts the GNN generalization pattern across node subgroups.\" \n\nOur method's substantial performance improvements over these existing approaches provide strong empirical validation for the significance of our findings.\n\n> The theoretical analysis majorly follows [2], and I did not find something new here.\n> \n\nPaper [2] provides a valuable foundation regarding how GNNs generalize across nodes with different structural properties. However, while [2] focuses on the generalization disparities between **GNN vs MLP**, our work examines the differences between **shallow vs deeper GNN**. Although [2] establishes a mathematical framework to study GNNs' generalization gap, we extend this framework **beyond 1-layer GNNs** to investigate how depth variation affects GNN generalization performance on nodes with various structural properties. This extension is crucial because depth is the most critical parameter of GNNs, determining the model's receptive field and fundamentally distinguishing GNNs from other neural networks.\n\n> Also, the MoE in GNNs is also utilized in several papers. For example, Link-MoE [3] also first train different GNN experts and then train the gating model to select different experts for different samples.\n> \n\nCoincidentally, both Moscat and Link-MoE share the same insight that \"train-then-merge\" MoEs are more suitable for graph learning than expert-gate joint training MoEs (please refer to our Appendix E for more details). However, Link-MoE is based on empirical heuristics found in link prediction tasks (e.g., heuristics link predictors like common neighbors show different generalization patterns than GNN link predictors), while Moscat's design is to address the prevalent yet critical generalization issue of deeper GNNs in heterophilous graphs, backed by solid mathematical foundations. They have drastically different targets, assumptions, and model designs.\n\nBeyond sharing the same \"train-then-merge\" philosophy with Link-MoE, our work bridges two key areas in graph learning: (1) Deeper GNN and (2) Graph MoE. As shown in Figure 2, we connect \"expert-gate joint training\" MoE design to GNN \"soft scoping\" and \"train-then-merge\" MoE to GNN \"hard scoping\". We further justify why \"hard scoping\" design is more suitable for GNNs, a critical insight rarely discussed in previous literature.\n\n## W2\n\nRecall that the definition of node homophily used in our paper is \n\n$$\n\\mathbf{h}_v^{\\text {node }}=\\left|\\left\\\\{u \\in \\mathcal{N}_v: y_u=y_v\\right\\\\}\\right| /\\left|\\mathcal{N}_v\\right|,\n$$\n\nwhere $y_v$ is the label for node $v$ and $\\mathcal{N}_v$ denotes $v$'s neighbors. We aim to calculate the homophily score $\\mathrm{h}^{\\text {node }}\\_v$ for every node $v\\in \\mathcal{V}\\_{\\text{train}}$ in the training set. However, the label for neighbor node $u\\in\\mathcal{N}_v$ is not available when $u$ is in the test set $u\\in \\mathcal{V\\_{\\text{test}}}$. To address this issue, we remove all edges connected to unlabeled nodes (i.e., remove all the test nodes from $\\mathcal{N}_v$) before calculating the homophily ratios for training nodes. Hence, there is strictly no information leakage, and the comparison is fair. \n\nPlease refer to run_moscat.py (lines 411-422) in our supplementary material for detailed implementation. In our revised version, we add a note to clarify this approximation of the homophily score.\n\n## W3\n\nThank you for this insightful comment. Since most existing studies (e.g., [1, 3, 4]) on heterophilous graphs employ high labeling rates, we adopted this standard setting to directly compare with prior work in our paper. We have now added experiments for low labeling rate scenarios below. \n\nFor these additional experiments, we maintain the same test sets from the original paper and vary the proportion of available labels for training and validation from 20% to 100%, with 100% representing the setup used in our paper. All other experimental parameters remained unchanged.\n\n|  | Labeling Ratio | 20% | 40% | 60% | 80% | 100% |\n| --- | --- | --- | --- | --- | --- | --- |\n| Amazon-Ratings | GCN | 41.25 ±1.08 | 44.44 ±0.56 | 45.98 ±0.59 | 47.39 ±0.53 | 48.55 ±0.38 |\n|  | GCN-Moscat | 43.42 ±0.75 | 46.50 ±0.73 | 48.86 ±0.37 | 50.54 ±0.64 | 52.25 ±0.69 |\n|  |  |  |  |  |  |  |\n| Penn94 | GCN | 74.00 ±0.69 | 77.65 ±0.52 | 80.11 ±0.43 | 81.35 ±0.53 | 82.54 ±0.43 |\n|  | GCN-Moscat | 78.17 ±1.05 | 81.95 ±0.81 | 83.71 ±0.54 | 84.75 ±0.59 | 85.76 ±0.32 |\n|  |  |  |  |  |  |  |\n| Flickr | GCN | 52.49 ±0.34 | 53.60 ±0.42 | 54.51 ±0.28 | 54.93 ±0.25 | 55.52 ±0.36 |\n|  | GCN-Moscat | 54.49 ±0.49 | 55.52 ±0.34 | 56.61 ±0.30 | 57.46 ±0.17 | 57.75 ±0.16 |\n\nOur results show that Moscat consistently outperforms a single expert across different labeling rates by a significant margin. As training sample sizes vary, experts may suffer from overfitting or underfitting. Moscat's decoupled gating design effectively handles both scenarios. \n\nThe results also reveal three distinct patterns: (1) For Amazon-Ratings, the performance gap between GCN-Moscat and GCN widens as the labeling ratio increases. (2) For Penn94, this gap narrows with higher labeling ratios. (3) For Flickr, the performance difference remains consistent across all labeling ratios.\n\nTo understand these patterns, we follow the methodology in Appendix G.6 to measure the percentage of nodes that are misclassified (all_wrong) or correctly classified (all_correct) by all GCN experts:\n\n|  | Labeling Ratio | 20% | 40% | 60% | 80% | 100% |\n| --- | --- | --- | --- | --- | --- | --- |\n| Amazon-Ratings | all_wrong | 28.01 | 27.49 | 26.07 | 25.24 | 24.62 |\n|  | all_correct | 9.12 | 10.96 | 11.33 | 11.84 | 12.22 |\n|  |  |  |  |  |  |  |\n| Penn94 | all_wrong | 5.11 | 4.06 | 3.38 | 3.10 | 2.88 |\n|  | all_correct | 29.07 | 33.11 | 34.67 | 36.08 | 36.61 |\n|  |  |  |  |  |  |  |\n| Flickr | all_wrong | 31.26 | 30.86 | 29.74 | 29.51 | 29.57 |\n|  | all_correct | 25.48 | 26.83 | 26.54 | 27.11 | 27.37 |\n\nBased on the above table, we observe: \n1. On Amazon-Ratings, \"all_wrong\" significantly decreases as the labeling ratio increases. This suggests that experts can better specialize in their respective domains with more labeled data, which enhances performance after mixing. \n2. On Penn94, \"all_wrong\" slightly decreases while \"all_correct\" increases significantly as the labeling ratio increases, indicating that experts become more accurate and overlapped when trained with more labeled data. This increased overlap reduces Moscat's effectiveness. \n3. On Flickr, both \"all_wrong\" and \"all_correct\" remain relatively consistent across labeling ratios, which explains why Moscat's improvements are also relatively stable.\n\n\n[1] Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods\n\n[2] Demystifying structural disparity in graph neural networks: Can one size fit all?\n\n[3] A critical look at the evaluation of GNNs under heterophily: Are we really making progress?\n\n[4] Revisiting Heterophily For Graph Neural Networks"}, {"review_id": "txrWBQy70F", "reviewer": "Reviewer_XLzJ", "summary": "This paper investigates a key phenomenon in Graph Neural Networks (GNNs): with increasing depth, they successfully capture homophily from multi-hop neighborhoods, yet exhibit a generalization bias across nodes with different degrees of homophily. Building on this finding, we propose a novel GNN architecture inspired by the Mixture-of-Experts (MoE) framework. Extensive experimental results validate the efficacy of our proposed method.", "questions": "With many mathematical symbols and formulas, the paper ultimately concludes that some parts of the network should be shallower while others should be deeper. However, the transition from the theoretical discussion to the Mixture-of-Experts framework is not sufficiently motivated. From my perspective, it currently feels somewhat like the we wanted a theory and then developed one to fit. While this new perspective—linking network depth and heterophily—is interesting and novel, I would like to see a stronger connection established between homophily and network depth.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n- The paper's innovative use of a Mixture-of-Experts (MoE) is interesting. This allows the GNN to learn adaptive depths for distinct \"subgroups\" of nodes (e.g., those with varying homophily levels), which is a clever solution to handle non-uniform graph structures.\n- The proposed method exhibits superior flexibility and performance. These claims are well-supported by extensive and rigorous experiments that validate the architecture's effectiveness across various benchmarks.\n\nWeakness\n\n- For the motivation of the paper, particularly the first three paragraphs,\n    - Figure 1 shows how different levels of homophily affect the performance of GNNs. When we intentionally change the graph structure to make it more or less homophilous, most standard GNNs respond in similar ways because their message-passing relies on homophily. However, I don’t think this experiment here motivates the proposed method well.\n    - The authors claim that deeper GNNs can capture homophily over a larger scope, or in common terms, a larger receptive field. However, it is not clear why a larger scope would help GNNs on heterophilous graphs. This point is not sufficiently discussed in the paper, nor are any related works cited. Heterophily is a well-studied area with many existing approaches, such as heterophily-oriented GNNs and Graph Transformers. Most of these methods do not treat the receptive field as a primary tool for addressing heterophily.", "was_revised": true, "final_justification": "The idea of linking homophily and network depths is interesting. But based on both the current version of the paper and the authors’ rebuttal, I believe that the correlation (or namely, why would we put these things together to formulate an analysis) between receptive field and heterophily remains insufficiently substantiated.", "rebuttal": "Thank you for your thoughtful feedback. We genuinely appreciate your encouragement and insights. Our detailed responses are as follows.\n\n## Weaknesses\n\n> Figure 1 shows how different levels of homophily affect the performance of GNNs. When we intentionally change the graph structure to make it more or less homophilous, most standard GNNs respond in similar ways because their message-passing relies on homophily. However, I don’t think this experiment here motivates the proposed method well.\n> \n\nWe want to clarify that Figure 1 presents GNN performance on real-world data **without any manual intervention**. Unlike many existing works (e.g., [1, 2, 3]) that intentionally alter graph structure to synthetically generate datasets with different **graph-level** homophily ratios, we calculate **node-level** homophily ratios using the original graph structure and then group nodes into different subgroups based on their homophily scores. This approach gives Figure 1 practical significance and provides strong motivation for our work.\n\n> The authors claim that deeper GNNs can capture homophily over a larger scope, or in common terms, a larger receptive field. However, it is not clear why a larger scope would help GNNs on heterophilous graphs. This point is not sufficiently discussed in the paper, nor are any related works cited. Heterophily is a well-studied area with many existing approaches, such as heterophily-oriented GNNs and Graph Transformers. Most of these methods do not treat the receptive field as a primary tool for addressing heterophily.\n> \n\nThank you for your careful review. We will add more related citations to support this claim in our revised version.\n\nWe respectfully argue that many existing works have already shown that a larger scope (usually beyond 2 or 3 hops) is essential for learning heterophilous graphs. Many of these methods build upon using a large scope and design various techniques to address the challenges that arise when the scope is large. For example, GPR-GNN [3] sets a learnable weight for each hop and uses a large scope size K=10 in all its experiments. GCNII [4] and G$^2$-GNN [5] are specifically designed for deep GNN architectures. MixHop [6] proposes adding higher-order graph convolution operators in each layer, which directly enlarges the receptive field. Additionally, both our work (Table 12) and existing research [7, 8] have demonstrated that heterophilous graphs generally prefer deeper GNNs.\n\nH$_2$GCN [2] also theoretically justifies that higher-order neighborhoods will be more homophilous on heterophilous graphs, which encourages GNNs to use a larger scope.\n\n## Questions\n\n> With many mathematical symbols and formulas, the paper ultimately concludes that some parts of the network should be shallower while others should be deeper. However, the transition from the theoretical discussion to the Mixture-of-Experts framework is not sufficiently motivated. From my perspective, it currently feels somewhat like the we wanted a theory and then developed one to fit. While this new perspective—linking network depth and heterophily—is interesting and novel, I would like to see a stronger connection established between homophily and network depth.\n> \n\nMoscat stems directly from our theoretical findings. In our revised paper, we will clarify the narrative that connects these theoretical insights to the specific architectural choices we made in our design. In the following, we will explain the logic flow of connecting homophily and network depth in the paper. Below, we outline the logical progression that links homophily and network depth in our paper.\n\n1. In Section 1, we recall that a larger scope is required for addressing heterophily. We will add more citations in our refined version to justify this claim.\n2. In Section 3.1, we dissect the challenges that GNNs face when tackling a larger scope. We reveal that the trained GNN model should be both expressive enough to capture higher-order patterns and generalizable enough to avoid overfitting. Although existing approaches for deeper GNNs can ensure expressivity and achieve close to 100% training accuracy, they suffer from poor generalization and may even fail to achieve better test accuracy than their shallow variants.\n3. To investigate this phenomenon, Section 3.2 presents a theoretical analysis and concludes that (1) the test nodes can be categorized into low and high homophily regions based on the training set's average homophily ratio. (2) As network depth/scope increases, the model's generalization capability exhibits distinct trends in these two regions (indicating a shift in generalization pattern). (3) This insight explains why simply increasing GNN depth often fails to improve accuracy.\n4. The above analysis directly motivates our method design:\n    1. From a higher level, this identified \"generalization pattern shift across depths\" (Section 3.2) motivates and supports our train-then-merge MoE framework for GNN models with various depths. In other words, rather than investigating how to train GNNs from scratch, we focus on learning the generalization patterns of already trained GNN models in a post-training stage.\n    2. From a lower level, the specific challenges that deeper GNNs encounter (Section 3.1) motivate our design choices:\n        - **Over-smoothing:** Our \"Structural Encoding\" technique enables the gating model to assess the likelihood that an expert for a given scope will experience over-smoothing.\n        - **Model degradation (Underfitting):** As discussed in the \"Heterophily-Biased Sample Filtering\" paragraph, we select samples in experts' training set $\\mathcal{V}\\_{\\text{exp}}$ to form the gating model training set $\\mathcal{V}\\_{\\text{gate}}$, which enables the gating model to learn how well each expert fits nodes with various structural patterns.\n        - **Overfitting:** We also use the holdout set $\\mathcal{V}\\_{\\text{hold}}$ to form $\\mathcal{V}\\_{\\text{gate}}$, which enables the gating model to detect experts' overfitting. We further introduce “Label Embeddings” to approximate node homophily, which can predict experts' generalization patterns (Theorem 1).\n    \n\n[1] Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond\n\n[2] Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs\n\n[3] Adaptive Universal Generalized PageRank Graph Neural Network\n\n[4] Simple and Deep Graph Convolutional Networks\n\n[5] Gradient Gating for Deep Multi-Rate Learning on Graphs\n\n[6] MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing\n\n[7] A critical look at the evaluation of GNNs under heterophily: Are we really making progress?\n\n[8] Classic GNNs are Strong Baselines"}, {"review_id": "BDT9SVLBxG", "reviewer": "Reviewer_Hr9P", "summary": "This paper investigates the problem of deeper GNNs theoretically and empirically, from which tries to propose a post-processing method of mixture of experts to improve the generalization capability while maintaining the high expressiveness. The proposed method is verified with extensive experiments that have been reported in Appendix.", "questions": "- How can you decide the optimal number of experts automatically?\n- Is the implementation of comparing methods fully conducted to the original proposals?\n- What is the limitation of the proposed method? It should be discussed at the conclusion for the future work.", "limitations": "The same as above.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "* Strengths\n- Sound baseline of theoretical investigation on the problem of deeper GNNs.\n- Reasonable proposal of the proposed method.\n- Extensive evaluation with large variations of datasets and metrics.\n\n* Weaknesses\n- Optimal number of experts and deep and shallow models should be presented in detail.\n- The main text needs more refined presentation. Especially, the figures need to be replaced with readable size and format.", "was_revised": true, "final_justification": "After reading all the rebuttals, I'm satisfied with them, and retain my original score.", "rebuttal": "We are grateful for the reviewer’s thoughtful remarks and support for our work. Our detailed responses are as follows.\n\n## Weaknesses and Questions\n\n> Optimal number of experts and deep and shallow models should be presented in detail.\nHow can you decide the optimal number of experts automatically?\n> \n\nWe use a hyperparameter $L_{\\text{max}}$ to determine the maximum depth of all experts. There are a total of $L_{\\text{max}}+1$ experts with scope sizes ranging from 0-hop (MLP) to $L_{\\text{max}}$-hop.\n\nIn our main experiments, we tune $L_{\\text{max}}$ from 1 to 6 and find that $L_{\\text{max}} = 6$ achieves the best results in most settings (Table 10). We also observe that increasing $L_{\\text{max}}$ beyond 6 can further improve accuracy (Appendix G.3). The optimal number of experts follows a clear pattern: **higher values of $L_{\\text{max}}$ consistently yield better accuracy but at increased computational cost** (Figures 6, 7, 8). As we add more and deeper experts, the less accuracy improvement we can expect from each additional one. Our experiments show that $L_{\\text{max}}=6$ provides a good balance between accuracy and computational overhead across all tested settings.\n\n> Is the implementation of comparing methods fully conducted to the original proposals?\n> \n\nYes, for baseline implementations and hyperparameters, we strictly followed the original papers (either those proposing the baselines or those evaluating existing approaches on newly proposed datasets). We conducted a hyperparameter search using Optuna when specific hyperparameters weren't provided in the original work.\n\nSince Moscat is designed as a post-processing approach, we use exactly the same baseline models as experts in our main experiments. In Appendix G.6, we also investigate how intentionally altering expert training affects Moscat's performance.\n\n> The main text needs more refined presentation. Especially, the figures need to be replaced with readable size and format.\n> \n\nThank you for your feedback. We will refine the paper's presentation based on all reviewers' comments and carefully adjust the figure sizes and formats to ensure better readability.\n\n## Limitations\n\nWe will include a dedicated section discussing the limitations of Moscat in our revised version. The main limitations are as follows:\n\n- **Increased resource cost:** Moscat introduces extra memory and computational overhead due to training and inference with multiple experts in parallel.\n- **Limited effectiveness in homophilous graphs:** The method is less effective on homophilous datasets compared to heterophilous ones. Please refer to our response to \"Reviewer 2PbC W4\" for details.\n- **Lack of expert variations beyond depth:** Our work does not explore how factors beyond depth impact mixing performance, such as alternative expert training strategies or model architectures.\n- **Heuristic design and hyperparameter sensitivity:** Moscat currently relies on several heuristic choices and requires additional hyperparameter tuning. Future work could focus on developing more principled, neural-based approaches for training set selection and architecture search (for both experts and the gating model) to improve robustness and automation."}]

Author rebuttal:

Meta-review: This paper presents a compelling study on the generalization disparities of deeper GNNs across nodes with different homophily levels. The proposed method, Moscat, is a novel and effective post-training mixture-of-experts framework that leverages these insights to significantly improve performance. The theoretical analysis is sound, and the experimental validation is extensive and rigorous, demonstrating strong improvements across various architectures and datasets. While one reviewer had concerns about novelty, the majority recognized the work's contributions, and the authors have thoroughly addressed all technical questions in the rebuttal. The paper is well-motivated, clearly presented, and offers valuable insights for the community. I recommend acceptance.
Decision: Accept (poster)