Conceptio › Archive › arXiv CS

arXiv CSopen access

Learning How Much to Think: Difficulty-Aware Dynamic MoEs for Graph Node Classification

Unknown · 2026 · arxiv_cs

arXiv CS · Papers · License: Open Access · 2026

Open Source ↗Direct PDF ↓

machine learning, deep learning, neural networks

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

Learning How Much to Think: Difficulty-Aware Dynamic MoEs for Graph Node Classification

arXiv:2604.11473v1 [cs.LG] 13 Apr 2026

Jiajun Zhou, Yadong Li, Xuanze Chen, Chen Ma, Chuang Zhao, Shanqing Yu, Qi Xuan, Senior Member, IEEE

Abstract—Mixture-of-Experts (MoE) architectures offer a scalable path for Graph Neural Networks (GNNs) in node classification tasks but typically rely on static and rigid routing strategies that enforce a uniform expert budget or coarsegrained expert toggles on all nodes. This limitation overlooks the varying discriminative difficulty of nodes and leads to under-fitting for hard nodes and redundant computation for easy ones. To resolve this issue, we propose D2 MoE, a novel framework that shifts the focus from static expert selection to node-wise expert resource allocation. By using predictive entropy as a real-time proxy for difficulty, D2 MoE employs a difficultydriven top-p routing mechanism to adaptively concentrate expert resources on hard nodes while reducing overhead for easy ones, achieving continuous and fine-grained expert budget scaling for node classification. Experiments on 13 benchmarks demonstrate that D2 MoE achieves consistent state-of-the-art performance, surpassing leading baselines by up to 7.92% in accuracy on heterophilous graphs. Notably, on large-scale graphs, it reduces memory consumption by up to 73.07% and training time by 46.53% compared to the best-performing Graph MoE, thereby validating its superior efficiency. Index Terms—Graph Neural Networks, Mixture of Experts, Node Classification

I. I NTRODUCTION RAPH Neural Networks (GNNs) have emerged as the leading paradigm for representation learning on graphstructured data. By iteratively aggregating neighborhood information via message passing, GNNs have achieved remarkable success in homophily-dominant scenarios where connected nodes tend to share similar features and labels. However, as realworld applications scale to massive datasets with increasingly complex patterns, a demand for higher model reasoning capacity arises. To capture intricate structural dependencies and rich semantic information, the research community have introduced a broad spectrum of advanced architectural mechanisms. These encompass high-order message passing [1] to expand receptive fields, multi-channel spectral filtering [2], [3] to adaptively

This work was supported in part by National Natural Science Foundation of China (No. 62503423), in part by the National Key Research and Development Program of China (No. 2025YFA1510900), in part by the Key Research and Development Program of Zhejiang Province (No. 2026C02A1233), in part by the Yangtze River Delta Science and Technology Innovation Community Joint Research Project (No. 2026ZY03003, No. 2025CSJGG01000), in part by the Zhejiang Provincial Natural Science Foundation of China (No. LMS25F020005). (Corresponding authors: Jiajun Zhou.) Jiajun Zhou, Yadong Li, Xuanze Chen, Chen Ma, Shanqing Yu and Qi Xuan are with the Institute of Cyberspace Security, Zhejiang University of Technology, Hangzhou 310023, China, with the Binjiang Cyberspace Security Institute of ZJUT, Hangzhou, 310056, China, and with the Soovar Technologies Co., Ltd., Hangzhou 310056, China (e-mail: [email protected]). Chuang Zhao is with the Department of Electronic and Computer Engineering, Hong Kong University of Science and Technology, Hong Kong, China.

capture varying frequency signals, and the recent proliferation of Graph Transformers (GTs) [4]–[7] designed to model global, all-pair node interactions. While these innovations have successfully pushed the boundaries of model capacity, they simultaneously introduce a critical dilemma characterized by two intertwined challenges: 1) Redundant computational overhead in dense paradigms. The conventional dense paradigm dictates that every node must engage the entire model capacity during inference, regardless of its discriminative difficulty. This indiscriminate computational overhead significantly hinders the scalable deployment of large-capacity models on massive graphs. 2) Rigid architectural priors versus node heterogeneity. Applying a uniform architectural prior globally intrinsically lacks the flexibility to adapt to diverse local graph patterns, fundamentally limiting the model’s ability to generalize across varying structural contexts. To reconcile the conflict between expressive capacity and computational efficiency, the Mixtureof-Experts (MoE) architecture [8] has been increasingly adopted in the graph domain. By conditionally activating only a sparse subset of expert networks, MoEs offer a pathway to scale model expressiveness without incurring a proportional surge in computational cost. However, the routing paradigms of existing Graph MoEs remain fundamentally static and rigid. They typically enforce uniform routing strategies, manifesting either as fixed graph expert budgets across all nodes like GMoE [9] or relying on coarse-grained, heuristic binary toggles like Mowst [10]. Consequently, this inherent rigidity disregards the naturally varying discriminative difficulty and heterogeneous reasoning capacity demands of individual nodes. This static design fundamentally contradicts the pervasive heterogeneity characterizing real-world graph data. As corroborated by our motivational experiments detailed in Section III-A, real-world graphs comprise diverse node patterns with varying levels of discriminative difficulty. On one hand, “easy” nodes, typically residing in homophilous regions with consistent neighborhood signals, can be accurately classified with minimal computation. Forcing such nodes to be processed through a wide array of multiple experts inevitably leads to overcomputation and the potential introduction of irrelevant noise from extraneous expert branches. On the other hand, “hard” nodes are frequently located at heterophilous boundaries or within densely entangled semantic regions, demanding higher non-linearity and a larger reasoning capacity to effectively disentangle conflicting neighborhood information. For these challenging nodes, imposing a fixed, small expert budget (k) severely constrains the model’s expressiveness, inevitably resulting in under-fitting. Consequently, this static “one-size-fits-all”

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

routing paradigm creates a profound resource mismatch: it caps the performance ceiling on hard nodes while simultaneously squandering computational resources on simple ones. Recently, dynamic routing mechanisms that adapt expert budgets based on instance difficulty have shown remarkable success in Large Language Models (LLMs) and Vision Transformers [11]. However, directly porting these sequencelevel routing techniques to Graph Neural Networks (GNNs) presents unique challenges. First, unlike independent tokens in LLMs, nodes in a graph are topologically entangled (noni.i.d.). The discriminative difficulty of a node stems not only from its intrinsic feature ambiguity but also from its structural surroundings, such as neighborhood heterophily and topological noise. Second, the standard LLM practice of calculating routing weights on-the-fly based on intermediate hidden states can destabilize the recursive message-passing process in GNNs. To bridge this gap and tailor dynamic MoEs for graph topology, we propose Difficulty-Aware Dynamic Mixture-ofExperts (D2 MoE), a novel framework that shifts the routing paradigm from rigid, static expert selection to continuous, finegrained expert budget scaling. Specifically, D2 MoE leverages predictive entropy as a real-time proxy for discriminative difficulty. By dynamically adjusting a cumulative routing probability threshold p tailored to each node, D2 MoE employs an adaptive top-p routing mechanism to dictate sparse, ondemand expert activation. By explicitly driving expert resource allocation via predictive uncertainty, D2 MoE successfully reconciles the aforementioned dilemma, achieving a tradeoff between instance-wise reasoning accuracy and systemlevel computational efficiency on large-scale graphs. Our main contributions are summarized as follows: 2 • New Paradigm: We propose D MoE, a novel framework that transcends rigid static routing by enabling continuous and fine-grained expert budget scaling, resolving the resource mismatch dilemma by aligning allocation with instance-wise discriminative difficulty. • Novel Methodology: We design a difficulty-aware topp routing that employs predictive entropy as a real-time difficulty proxy. This strategy uses dense expert ensembles for hard nodes while enforcing sparsity for easy ones. • Superior Performance: Extensive experiments on 13 datasets confirm that D2 MoE not only achieves SOTA performance for node classification but also exhibits remarkable efficiency, reducing memory usage and training time by up to 73.07% and 46.53%, respectively. II. P RELIMINARIES AND R ELATED W ORKS A. Notation and Problem Definition Let G = (V, E) denote a graph, where V = {v1 , . . . , vN } is the set of N nodes and E represents the set of edges. The topological structure is described by the adjacency matrix A ∈ {0, 1}N ×N , where Aij = 1 if an edge exists between node vi and vj , and Aij = 0 otherwise. We denote the neighborhood set of node vi as N (vi ) = {vj ∈ V | Aij = 1}, which includes the node itself if self-loops exist. Each node is associated with a feature vector xv ∈ Rd , forming the feature matrix X ∈ RN ×d , where d is the dimension of the input features. The node label

information is represented by a matrix Y ∈ {0, 1}N ×C , where C is the number of classes. For a node vi belonging to class c, the row vector y i is a one-hot vector with the c-th element being 1. Given a subset of labeled nodes VL ⊂ V, the semisupervised node classification task aims to learn a function f : V → RC to predict the labels of the remaining unlabeled nodes VU = V \ VL by minimizing the prediction error on VL . B. Graph Neural Networks GNNs follow the message-passing paradigm. For a generic GNN layer ℓ+1, the representation h(ℓ+1) of node v is updated v by aggregating messages from its neighbors N (v): n o (ℓ) (ℓ) h(ℓ+1) = UP h , AGG h | u ∈ N (v) , (1) v v u where h(0) v = xv . AGG(·) collects messages from neighbors, while UP(·) combines the aggregated message with the node’s current state. This mechanism enables GNNs to capture local structural patterns but typically applies shared parameters across all nodes, enforcing a uniform architectural prior. C. Mixture of Experts with Its Applications to Graphs 1) General MoE Mechanism: Mixture-of-Experts (MoE) [8] scales model capacity by using a set of K expert networks F = {f1 , · · · , fK } alongside a router R(·). For an input h, the router first computes a routing distribution π = R(h) ∈ RK across all experts. The top-k routing then selects the k experts with the highest scores in π. The final sparse routing weights are obtained by normalizing the scores of the selected experts while masking others to zero. Finally, the model output is computed as the weighted summation of the activated experts. 2) Adoption in GNNs: Inspired by the success of MoE in LLMs, recent studies have introduced this paradigm to GNNs to tackle heterogeneity. GMoE [9] integrates experts with varying aggregation hops, enabling the dynamic selection of optimal receptive fields to capture multi-scale structural information. With a similar focus on structural variability, DAMoE [12] addresses the depth sensitivity issue arising from diverse graph scales. NodeMoE [13] employs a bank of graph filters (e.g., low-pass, high-pass) as experts, selecting the filter that best aligns with the local homophily pattern of each node. GNNMoE [14] decouples message passing into atomic operations (i.e., propagation and transformation) to construct diverse expert networks. Mowst [10] adopts a “strongweak” strategy, utilizing an MLP-based confidence metric to conditionally activate GNN experts only for low-confidence nodes. Moscat [15] introduces a decoupled expert-gating paradigm that independently trains GNNs of varying depths as scope experts and dynamically combines their predictions at test time to enhance generalization Despite effectively utilizing diverse experts to handle node heterogeneity, these methods remain constrained by rigid expert resource allocation mechanisms. Most approaches adhere to static routing with a fixed expert budget, while others are limited to coarsegrained expert toggles. Crucially, they lack the flexibility for continuous, fine-grained expert budget scaling, inevitably leading to resource mismatch where hard nodes suffer from under-fitting while easy nodes incur computational waste.

0.55

k=5 k=3 k=1

Roman Empire

0% 10 10% % 20 20% % 30 30% % 40 40% % 50 50% % 60 60% % 70 70% % 80 80% % 90 -90 % % -1 0% 00% 10 10% % 20 20% % 30 30% % 40 40% % 50 50% % 60 60% % 70 70% % 80 80% % 90 -90 % % -1 0% 00% 10 10% % 20 20% % 30 30% % 40 40% % 50 50% % 60 60% % 70 70% % 80 80% % 90 -90 % % -1 00 %

0.40

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021 Prediction Entropy

Accuracy

0.55

Chameleon-fix

0.48

0.25

1.00

Roman Empire

0.85

0.40 0.33

Prediction Entropy

0.55 0.40

Penn94

1.00

0.73 k=5 k=3 k=1

0.59 0.45

k=5 k=3 k=1

% % % % % % % % % % % % % % % % % % % % % % % % % % % % % % -10 -20 -30 -40 -50 -60 -70 -80 -90 100 -10 -20 -30 -40 -50 -60 -70 -80 -90 100 -10 -20 -30 -40 -50 -60 -70 -80 -90 100 0% 10% 20% 30% 40% 50% 60% 70% 80% 0%0% 10% 20% 30% 40% 50% 60% 70% 80% 0%0% 10% 20% 30% 40% 50% 60% 70% 80% 0%9 9 9

Prediction Entropy Interval (Deciles)

Accuacy

Accuracy

Fig. 1: Impact of static expert budgets (top-k) on node classification performance across predictive entropy intervals.

Accuracy

Prediction Entropy

0.86

0.70 k=5 k=3 k=1

Penn94

Ultimately, these observations reveal that static routing paradigms result in an inescapable dilemma: over-computation for easy nodes and simultaneous under-fitting for hard ones. This profound resource mismatch underscores the critical necessity for a difficulty-driven adaptive routing paradigm, directly motivating the design of our D2 MoE framework.

B. Theoretical Justification To theoretically justify the necessity of the dynamic computational allocation mechanism in D2 MoE, we analyze Computer Photo Coauthor CS Coauthor Physics 1.00 1.00 1.00 1.00 the generalization error of the Mixture-of-Experts (MoE) 0.90 0.91 0.90 III. M OTIVATION AND T HEORETICAL A NALYSIS0.93 architecture in node classification tasks through the lens of 0.79 0.82 0.80 0.85 A. Analysis of 0.73 Motivational Experiments k=5 k=5 k=5 k=5 the Bias-Variance Trade-off. Given a node v with predictive 0.68 0.70 0.77 k=3 k=3 k=3 k=3 k=1 k=1 k=1 k=1 0.58 0.64 the inductive bias 0.60 and limitations of0.70 entropy Uv , the expected Mean Squared Error L(v, k) of its To investigate static % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % -10 -20 -30 %-40 %-50 %-60 %-70 %-80 %-90 -100 -10 -20 %-30 %-40 %-50 %-60 %-70 %-80 %-90 -100 -10 -20 -30 -40 -50 %-60 %-70 %-80 %-90 -100 -10 -20 %-30 %-40 %-50 %-60 %-70 %-80 %-90 -100 % 0 30 40 50 top-k) 0 30 40 5Top-k 0 60 70 80 expert 0% 10% 20% routing 0% 10% 2(e.g., 0% 10% 20% 30% 40% Graph 0% 10% 2we 0% 30 40 50 60 70 strategies 80 90% 60 70 80 90%in existing 50 60 70 80 9MoEs, ensemble can be decomposed into bias, variance, 90 Wiki-CS Facebook Actor Chameleon-fix 1.00 1.00 0.75 motivational experiment. 0.55 and irreducible noise: L(v, k) = Bias2 (k) + Var(k) + ϵ. In conduct a comprehensive controlled k=5 k=3 0.85 0.90 0.61 0.48 k=1 compristhe context of dynamically weighted sparse MoEs for graph We construct a vanilla sparse Graph MoE framework 0.70 0.80 0.48 0.40 neural networks, we establish the following two fundamental ing a top-k router and a bank of K = 6 independent experts, k=5 k=5 k=5 0.55 0.70 0.34 0.33 k=3 k=3 k=3 assumptions that reflect realistic physical settings: where each expert is instantiated as a standard 2-layer GCN. To k=1 k=1 k=1 0.40 0.60 0.20 0.25 % % 0% 0% 0% 0% 0% 0% 0% 0% % % % % % 0% -20% -of 0% -20% -30%budget, 0% -20% -30% -40% -50% -60%Assumption 0% -40% 0% -60%computational 0% -80% -90% 00% 0% -50% -60% -70% -8we 0% -90% 00evaluate 1 (Weighted Bias Accumulation). P In a sparse the 10 -20 -3analyze 1 1 1 0 4 -5 -6 -7 the 8 -9 -impact 3 5 7 4 -70 -80 -90 100 1 1 1 0% 10% 20% 30% 40% 50% 60% 70% 80% 0% 0% 10% 20% 30% 40% 50% 60% 70% 80% 0%0% 10% 20% 30% 40% 50% 60% 70% 80% 0%0% 10% 20% 30% 40% 50% 60% 70% 80% 0%9 9 9 9 k MoE, the router outputs normalized routing weights the node classification performance of three Squirrel-fix Roman Empire Tolokersvariants with Penn94 i=1 πi = 0.50 1.00 1.00 1.00 and the experts are sorted in descending order of confidence 1, fixed static routing (k ∈ {1, 3, 5}) across nodes stratified by 0.43 0.84 0.86 0.86 (π1 ≥ π2 ≥ · · · ≥ πk ). Expanding the number of activated their discriminative difficulty. Crucially, to ensure a consistent 0.35 0.68 0.73 0.73 k=5 k=5 k=5 k=5 experts (increasing k) implies introducing relatively lower0.28 0.51 0.59 0.59 difficulty baseline and prevent “population drift” caused by k=3 k=3 k=3 k=3 k=1 k=1 k=1 k=1 0.20 0.35 0.45 0.45 performing tail experts. Due to the zero-sum nature of the varying model capacities, we employ a fixed, independent proxy % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % % -10 -20 -30 %-40 %-50 %-60 %-70 %-80 %-90 -100 -10 -20 %-30 %-40 %-50 %-60 %-70 %-80 %-90 -100 -10 -20 -30 %-40 %-50 %-60 %-70 %-80 %-90 -100 -10 -20 -30 -40 -50 %-60 %-70 %-80 %-90 -100 % 0 0% 0 60 70 80 0% introducing tail experts inevitably siphons probability 0% 10% 20% model 0% 10% 20node 0% 10% 20% 0% 10% 20% 30% 40% 5weights, 30 40 50 60 to 70 80quantify 30 40 50discriminative 60 70 80 90% 30 40 50 60 70 8Specifically, difficulty. 90 9 9 Prediction Entropy Interval (Deciles) Prediction Entropy Interval (Deciles) Prediction Entropy Interval (Deciles) Prediction Entropy Interval (Deciles) we utilize a fully converged 2-layer GCN as a “teacher” to mass away from the optimal top experts. Although the soft calculate the predictive entropy for all test nodes. Based weight allocation mechanism of Softmax effectively mitigates on this fixed predictive entropy distribution, test nodes are the severe bias dilution caused by uniform averaging, the bias stratified into immutable difficulty intervals (deciles from 0% still strictly and monotonically increases with k. We model to 100%), ensuring that all expert variants are strictly evaluated this sub-linear bias growth via a generalized polynomial: on identical subsets of “easy” and “hard” nodes. Bias2 (k) ∝ βk µ (β > 0, µ > 0) (2) As illustrated in Figure 1, the comprehensive results across diAssumption 2 (Uncertainty-Driven Reducible Variance). verse datasets validate a fundamental expert resource mismatch inherent in static routing. Regardless of the graph topology, The predictive entropy Uv of node v reflects the model’s uncertainty regarding its classification, which directly corresponds two distinct and consistent patterns emerge: 1) Capacity Saturation in Low-Entropy Regions: In to a high initial prediction variance. In practical ensembles, a intervals characterized by low predictive entropy (e.g., Uv ∈ certain degree of positive correlation (ρ > 0) typically exists [0%, 20%]), the performance curves of models with varying among experts, implying a theoretical lower bound for the expert budgets exhibit minimal variance and frequently overlap. variance. However, increasing the number of experts k can still Notably, the single-expert baseline (k = 1) matches or even monotonically decrease the reducible portion of the variance. marginally exceeds the accuracy of multi-expert ensembles. We model this uncertainty-driven variance reduction as: This saturation explicitly suggests that “easy” nodes, typically αUv Var(k) ∝ ρσ 2 + φ (α > 0, φ > 0) (3) residing in homophilous regions with consistent structural k signals, are fully adequately supervised by a minimal expert where σ 2 denotes the variance of a single expert’s prediction. budget. Consequently, enforcing a larger k in these regions inBy minimizing the generalized error L(v, k), we can derive the curs unnecessary computational overhead and risks introducing analytical relationship between node discriminative difficulty noise from less relevant experts. and the optimal expert budget (proof in Appendix A): 2) Capacity Craving in High-Entropy Regions: Conversely, a substantial performance divergence manifests as predictive Theorem 1 (Generalized Uncertainty-Driven Scaling Law). entropy increases (e.g., Uv > 0.5). For these challenging Under Assumptions 1 and 2, for any node v, there exists a nodes, often located at heterophilous boundaries or noisy positive monotonic relationship between its predictive entropy neighborhoods, ensembles with larger budgets (k = 3, 5) Uv and the optimal number of active experts k ∗ that minimizes demonstrate significantly superior performance compared to its generalization error: 1 the single-expert variant. This trend confirms that a fixed, small k ∗ (v) ∝ (Uv ) µ+φ (4) budget inevitably leads to under-fitting for “hard” nodes, as they inherently demand the activation of more experts to reduce Remark. Theorem 1 provides a rigorous mathematical variance and collaboratively resolve semantic ambiguity. foundation for D2 MoE to abandon static Top-k routing. The

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

IV. M ETHODOLOGY Based on the motivational analysis in Section III, we propose Difficulty-Aware Dynamic Mixture-of-Experts (D2 MoE) for graph node classification, a novel framework that transforms node discriminative difficulty into a node-wise computational budget. D2 MoE enables a dynamic routing paradigm where the model adaptively decides how many experts are required for each node during inference, rather than relying on a static routing configuration. The overall architecture of D2 MoE is illustrated in Figure 2.

& 𝑷, 𝒀

Output Hidden State of Node 𝑣

(#)

𝒉!

Linear + Softmax

Aggregate outputs from selected experts

𝑯# D2MoE Block

𝑯

𝐸"

…

… 𝐸!$"

𝐸#

𝐸!

e.g., 𝐾 = 4

D2MoE Block

𝑯

Expert Weights

…

𝑯 #$"

Epoch 𝑡 − 1

theorem proves that in realistic scenarios accounting for expert weighting and correlation, the system must establish a dynamic, non-linear positive mapping between task uncertainty and computational capacity to achieve optimal generalization. This serves as the core motivation for the routing mechanism design in Section IV (Eq. (13)). While the theoretical scaling law exhibits an unbounded power-law growth, a physical MoE system has a strictly bounded total expert capacity. Therefore, we employ a Sigmoid function as a continuous threshold mapper. The Sigmoid function preserves the non-linear, monotonically increasing property dictated by Theorem 1, while naturally mapping the unbounded predictive entropy into a valid probability simplex (0, 1) to determine the adaptive expert budget. This design serves as a rigorous practical instantiation of the theoretical scaling law under realistic hardware constraints.

π$ π% π& π'

π' π$ π& π%

Difficulty-Aware Top-𝒑 Router

Linear

(#$%)

𝒉!

Input Hidden State of Node 𝑣

𝑿 "#$

𝑷! : Probability Adaptive Budget Mapping Distribution of Node 𝑣 Predictive Entropy Mapping 𝟎 ('$") 𝑝$

𝑝% 𝑝&

𝑝'

π$

π& π% 1 0 (") threshold : 𝑝!

π'

𝒰%

Sigmoid

(')

𝑝%

𝟏 Cumulative probability threshold

Fig. 2: The architecture of D2 MoE. The complete workflow proceeds as follows: (1) D2 MoE first quantifies node-wise difficulty via predictive entropy; (2) Top-p router adaptively scales the expert resources, activating a sparse set of experts for easy nodes while mobilizing a comprehensive ensemble for hard nodes; (3) Selected expert outputs are fused to update node representations, which generate predictions and initiate the next difficulty quantification.

A. Backbone Architecture of D2 MoE where W 1 and W 2 are learnable weights, σ denotes the (l) K The overall architecture of D2 MoE follows a stacked layer- activation function, and π v ∈ R represents the probability wise Mixture-of-Experts paradigm, designed to iteratively refine distribution over experts for node v prior to selection. Unlike traditional rigid static routing, D2 MoE employs a node representations via dynamic expert interaction. (l) 1) Initial Embedding: First, the input node feature matrix difficulty-aware dynamic routing mechanism that utilizes π v N ×d X∈R is projected into a latent space compatible with to adaptively calculate a threshold and select a variable set of (l) the experts. We employ a linear transformation parameterized the most relevant experts Fbv (detailed in Section IV-B). To d×h by W 0 ∈ R , followed by a ReLU activation and a dropout effectively aggregate information from these selected experts while mitigating the over-smoothing problem common in deep operation to obtain the initial node embeddings: GNNs, we integrate residual connections. The update rule for H (0) = Dropout(ReLU(XW 0 )), (5) node v at block l is formulated as: X (l) where H (0) ∈ RN ×h and h is the hidden dimension. (l) (l−1) h(l) + π̄v,i · [Z i ]v , (8) v = hv 2) Stacked D2 MoE Layers: Subsequently, H (0) serves as (l) 2 bv i∈F the input to the core network composed of L stacked D MoE blocks. In each block l ∈ {1, . . . , L}, the input H (l−1) is (l) (l) processed in parallel by a difficulty-aware router and a bank of where [Z i ]v is the output of (l)expert fi for node v. The (l) (l) (l) experts F (l) = {f1 , . . . , fK }. Each expert fi is instantiated re-normalized routing weight π̄v,i ensures numerical stability as a standard GNN layer (e.g., GCN or GraphSAGE) with and that the contribution of active experts sums to 1:  (l) independent parameters, allowing them to differentiate and  P πv,i (l) , if i ∈ Fbv(l) , specialize in capturing diverse local patterns during training. (l) π (9) π̄v,i = b (l) v,j j∈F v The output of the i-th expert is:  0, otherwise. (l) (l) Z i = fi (H (l−1) , A). (6) 4) Output and Prediction: Finally, the aggregated represen3) Difficulty-Aware Dynamic Routing: Simultaneously, the tation undergoes normalization and non-linear activation to router R(l) (·), instantiated as a Multi-Layer Perceptron (MLP), produce the layer output: generates routing scores based on the input features. It maps H (l) = Dropout(ReLU(Norm(H (l) ))), (10) the node embeddings to the expert score dimension: (l−1) (l) π (l) )) v = Softmax(R (hv

= Softmax(W 2 · σ(W 1 h(l−1) )), v

(7)

where Norm(·) denotes a normalization layer. After L layers, the final node representation H (L) is fed into a linear classifi-

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

cation head to generate the prediction probability distribution P and the prediction labels Ŷ : P = Softmax(Linear(H (L) )), Ŷ = argmax(P ). B. Difficulty-Aware Dynamic Routing

(11)

all nodes at epoch t − 1, serving as a dynamic baseline of (t−1) discriminative difficulty. Through this design, a higher Uv (t) naturally translates into a higher threshold pv , which in turn necessitates accumulating weights from more experts in the subsequent routing stage. 3) Dynamic Top-p Routing: Finally, we implement a cumulative probability routing strategy (top-p routing) to replace the rigid static top-k routing mechanism. Mathematically, our goal is to select the minimal set of experts sufficient to satisfy the (t) cumulative probability threshold pv . This can be formulated as a constrained optimization problem. Given the routing scores (l) (l) π v ∈ RK , the active expert set Fbv is obtained by solving: X (l) Fbv(l) = arg min |S| s.t. πv,i ≥ p(t) (14) v .

The core innovation of D2 MoE lies in its routing mechanism, which transforms the abstract concept of “discriminative difficulty” into a concrete, instance-wise computational budget. This process operates in three phases: difficulty quantification, adaptive budget mapping, and dynamic execution. 1) Discriminative Difficulty Quantification: First, we establish a metric to quantify the discriminative difficulty of each node. We employ predictive entropy as a real-time proxy. To S⊆{1,··· ,K} enable a closed-loop bootstrapping strategy, we utilize the i∈S model’s prediction from the previous training epoch t − 1 to The optimal solution to Eq. (14) is efficiently obtained by guide the resource allocation at the current epoch t. For a node a greedy strategy: selecting experts with the largest routing (t−1) v, its discriminative difficulty Uv is defined as the Shannon (t) scores until the cumulative sum exceeds pv . This mechanism (t−1) entropy of its predicted class distribution P v : (t) ensures that easy nodes (low pv ) are processed by a minimal (t) C number of experts (often |S| = 1), while hard nodes (high pv ) 1 X (t−1) (t−1) Uv(t−1) = − Pv,c · log Pv,c , (12) automatically trigger a larger ensemble to resolve ambiguity. log C c=1 In summary, by transforming posterior predictive entropy where C is the number of classes, and the normalization term signals into prior routing decisions, D2 MoE effectively dis(t−1) log C ensures Uv ∈ [0, 1]. Higher entropy indicates greater mantles the constraints of rigid static routing. This mechanism uncertainty in the model’s decision-making, signaling a “hard” evolves D2 MoE into a dynamic “divide-and-conquer” system, node. To ensure training stability during the cold-start phase empowering D2 MoE to adaptively learn how much to think (0) (i.e., t = 0), we enforce full activation (pv ) for all nodes for each specific instance. Consequently, D2 MoE achieves at initialization, which mandates the utilization of the entire continuous, fine-grained expert resource allocation, maximizexpert ensemble, preventing the router from collapsing into a ing expressiveness for challenging samples while preserving trivial solution early during training. computational efficiency for simpler ones. 2) Adaptive Budget Mapping: With the quantified discrimi(t−1) native difficulty Uv , the subsequent challenge is to translate this abstract signal into a concrete computational budget for C. Training Objectives and Regularization (t−1) D2 MoE is optimized in an end-to-end manner. We formulate the current epoch. A naive strategy might map Uv linearly to a discrete number of experts. However, this is suboptimal the overall objective function, which combines the primary as the correlation between discriminative difficulty and expert classification loss with auxiliary regularization terms designed to ensure sparse and balanced expert utilization. demand is inherently non-linear. 1) Classification Objective: The primary goal is the node In this work, we argue that effective resource allocation fundamentally responds to the demand for decision confidence. classification task, optimized via the standard Cross-Entropy (t−1) Intuitively, for “easy” nodes with low Uv , signals from loss. Formally, the task loss is defined as: the dominant expert suffice to ensure certainty. In contrast, X 1 (t−1) Ltask = − Y v · log P v , (15) “hard” nodes with high Uv necessitate the aggregation |Vtrain | v∈Vtrain of opinions from multiple experts to establish a decision consensus and mitigate prediction risk. Consequently, rather where V train represents the set of training nodes, and P v and than forcing the model to predict a discrete number of Y represent the predicted probability distribution and the v experts, we reformulate the task as determining a continuous one-hot ground-truth label of node v, respectively. (t) cumulative probability threshold pv . This threshold represents 2) Regularization: While the difficulty-aware mechanism the necessary “information coverage” for reliable prediction allows for flexible resource allocation, unconstrained option node v during epoch t. To capture the complex non-linear mization in MoEs is often prone to routing collapse. We correlation between discriminative difficulty and expert demand, identify two critical risks: (1) Loss of Sparsity. To minimize we design a Sigmoid-based adaptive mapping mechanism: prediction risk, the router tends to assign uniform weights to (t) (t−1) (t−1) pv = Sigmoid γ · Uv − Ū , (13) all experts. Crucially, in our top-p routing, a flat (high-entropy) distribution forces the activation of numerous experts to meet where γ acts as a sensitivity coefficient controlling the steepness the cumulative threshold pv , effectively reverting the model to a of the Sigmoid function, and a larger γ implies that the model computationally expensive dense network; (2) Load Imbalance. is more sensitive to subtle variations in discriminative difficulty. The router may converge to utilizing only a small subset of Ū (t−1) represents the mean value of predictive entropy across strong experts for all nodes, leaving others undertrained and

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

Algorithm 1 Training Procedure of D2 MoE 1: Input: Graph G = (V, E, X, Y ), Max epochs T , Hyper-

via the load balancing loss [8]:

! L K X X parameters γ, α, β. (l) (l) LLB = K· fi · Q i , (17) 2: Output: Trained model parameters Θ. i=1 l=1 3: Initialization: Initialize model parameters Θ. 4: Cold Start: Initialize cumulative routing probability threshN N (0) 1 X 1 X (l) old pv ← 1 for all nodes v ∈ V. (l) (l) I{i ∈ Fbv(l) }, Qi = π . (18) fi = 5: for epoch t = 1 to T do N v=1 N v=1 v,i 6: // Phase 1: Adaptive Budget Mapping (Section IV-B) (l) 7: Get dynamic baseline Ū (t−1) ← Mean(U (t−1) ). where fi represents the actual selection frequency of expert 8: for each node v ∈ V do (l) (l) Ei , I{·} denotes the indicator function, and Qi is the (t) 9: Compute routing threshold pv via Eq. (13). (l) average routing probability assigned to fi . It is worth 10: end for (l) noting that fi is non-differentiable, thus the gradient of 11: // Phase 2: Forward Propagation with Dynamic Routing LLB is back-propagated solely through the differentiable term 12: Compute initial embeddings H (0) . (l) Qi , encouraging the router to lower the routing probability 13: for layer l = 1 to L do scores of overloaded experts. 14: for each node v ∈ V do (l) 3) Total Objective: The final objective function is a weighted 15: Generate expert scores π v via Router. 16: Dynamic Top-p Execution: Select minimal expert sum of the task loss and the regularization terms: (l) (t) set Fbv satisfying cumulative sum ≥ pv via L = Ltask + λ1 · LRE + λ2 · LLB , (19) Eq. (14). 17: Aggregate expert outputs with residual connection. where λ1 and λ2 control the strength of the sparsity and load 18: end for balancing constraints, respectively. 19: end for 20: Obtain final predictions P (t) . 21: // Phase 3: Optimization V. E XPERIMENTS 22: Calculate Classification Loss Ltask via Eq. (15). 23: Calculate Regularization LRE and LLB via Eq. (17). 24: Update Θ by minimizing L = Ltask + λ1 LRE + λ2 LLB . A. Experimental Setup 25: // Phase 4: Proxy Update (Bootstrap) 1) Datasets: We conduct experiments on 13 benchmarks, 26: for each node v ∈ V do covering both homophilous and heterophilous scenarios: (1) (t) 27: Update difficulty proxy Uv using current prediction Homophilous: Computers, Photo [16], Coauthor CS, Coauthor P (t) v via Eq. (12). Physics [17], Wiki-CS, Facebook [18], and Ogbn-arxiv [19]; 28: end for (2) Heterophilous: Actor [20], Chameleon-filtered, Squirrel29: end for filtered, Roman-empire [21], Tolokers, Penn94 [22]. We adopt 30: return Optimized parameters Θ. a standard 48%/32%/20% split for training, validation, and testing, except for Ogbn-arxiv which follows the official OGB [19] public splits. wasting model capacity. To address these issues, we impose 2) Baselines: We compare D2 MoE with 19 baselines catethe following constraints: gorized into four groups: (1) Vanilla Models: MLP, GCN [23], • Sparsity via Routing Entropy Minimization. To prevent GraphSAGE [24], GAT [25]; (2) Heterophilic GNNs: the router from degenerating into dense activation patterns, H2GCN [1], GPRGNN [26], FAGCN [2], ACMGCN [3], we aim to minimize the uncertainty of the routing distribution. FSGNN [27]; (3) Graph Transformers (GTs): Vanilla GT, (l) By minimizing the entropy of routing distribution π v , we ANS-GT [5], NAGphormer [4], SGFormer [28], Exphormer [7], encourage the probability mass to concentrate on a small Difformer [6]; (4) Graph MoEs: GMoE [9], DAMoE [12], subset of dominant experts. Mathematically, a lower entropy NodeMoE [13], Mowst [10], Moscat [15]. corresponds to a sharper distribution, which enables the 3) Implementation Details: We report the average test cumulative probability threshold pv to be satisfied with fewer accuracy and standard deviation over 10 runs with different experts (i.e., a smaller |S|), thereby enhancing sparsity. The random seeds. We search hyperparameters for all methods routing entropy loss is formulated as: within a unified space: hidden dimension h = 64, learning rate ∈ {0.005, 0.01, 0.05, 0.1}, dropout ∈ {0.1, 0.3, 0.5, 0.7, 0.9}. L N K 1 X X X (l) (l) The maximum epochs are set to 500 with an early stopping LRE = − πv,i · log πv,i . (16) N ·L patience of 100. We employ AdamW optimizer and weight l=1 v=1 i=1 decay. For D2 MoE, the parameter space is: regularization • Utilization via Load Balancing. To prevent expert collapse weights λ1 = 0.0001, λ2 ∈ {1e-3, 1e-1}, sensitivity coefficient where certain experts are over-utilized while others remain γ ∈{1, 5, 10}, maximum number of experts K ∈{4, 6}, idle, we enforce balanced expert utilization across all nodes maximum number of layers L ∈{1, 2}.

Tolokers

80 % % 90 90% % -1 00 %

% 70

-8 0

% 60

-7 0

% 50

-6 0

% 40

-5 0

% 30

-4 0

-1 0

-3 0

-2 0

% -1 00 % %

-9 0

% 70

-8 0

% 60

-7 0

% 50

Roman-empire

Penn94

1.00

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

0.75

0.79

0.50

0.87

0.58

0.89

0.73

0.78

TABLE I: Node classification 0.60 results: average test accuracy (%) ± standard deviation. Boldface letters mark the best performance 0.36 0.67 Actor 1.00 while underlined letters indicate the second best.

-9

-1

-8

% 80

-7

-6

0% % 50

-5 %

-4 %

-3

-2

-1 0%

-1

-9 %

-8

-7

% 70

-6

% 60

-5

% 50

-4

% 40

% 30

-3

-2

Accuracy Accuracy

10 0% % -2 20 0% % -3 30 0% % -4 40 0% % -5 50 0% % -6 60 0% % -7 70 0% % -8 80 0% % 90 90% % -1 00 %

Ours GCN GMoE DAMoE Mowst

0.67 0.56

-1

-9 %

-8 %

-7 %

-6

-5

-1

0.78 Ours GCN GMoE DAMoE Mowst

0.60

-4

0.89

0.46

0% -1

Penn94

1.00

0.73 Ours GCN GMoE DAMoE Mowst

0.68

0.87

% -9 0 % % -1 00 %

0% 70

% 00

-1

0% -9

-8

-7

0% 60

-6 %

-5

-4

-3

0% -2

% 20

-1

% 00

-1

0% -9

-8

-7

0% 60

-6 %

0% 50

-5

-4

-3

0% -2

-1

% 00

-9

-1

-8

-7

-6 %

-5 %

-4

-3

-2

-1 0%

0.15

0.00

0.00 0%

0.36

0.58

0.25

0.50

0.21

0.43

0.25

Ours GCN GMoE DAMoE Mowst

0.76

Toloker

1.00

0.79

0.50

0% 60

0.75

0.64

Ours GCN GMoE DAMoE Mowst

0.84 Ours GCN GMoE DAMoE Mowst

0.40

Roman-empire

1.00

75.18 ± 0.35 80.45 ± 0.27 78.10 ± 1.28 OOM 75.91 ± 0.44 Roman-empire 84.34 ± 0.29 79.01 ± 1.09 83.01 ± 0.46 83.87 ± 0.98 OOM OOM Ours 73.98 GCN ± 0.53 GMoE OOM DAMoE Mowst OOM 76.65 ± 0.49 79.03 ± 0.78 OOM 78.84 ± 1.99 78.04 ± 0.58 83.91 ± 0.63 84.55 ± 0.51 81.02 ± 0.63 82.86 ± 0.47

0.92

0.55

Ours GCN GMoE DAMoE Mowst

0.85 0.64

P ENN 94

Facebook

1.00

0.70 Ours GCN GMoE DAMoE Mowst

0.75

Squirrel-fix

53.18 ± 6.35 70.34 ± 1.64 79.93 ± 0.77 82.37 ± 0.64 81.34 ± 1.16 73.84 ± 1.40 81.38 ± 1.34 83.52 ± 0.87 83.87 ± 0.98 72.24 ± 1.17 76.91 ± 0.85 66.73 ± 1.18 82.26 ± 0.41 81.04 ± 4.16 80.46 ± 0.91 85.21 ± 0.40 OOM 79.43 ± 0.66 51.45 ± 1.07 81.79 ± 1.07 85.74 ± 0.51 84.63 ± 0.81 85.26 ± 0.81

WikiCS

0.75

ROMAN - EMPIRE 0.50 65.98 ± 0.43 50.76 ± 0.46 57.34 ±0.25 1.81 77.77 ± 0.49 79.47 ±0.00 0.43 67.72 ±1.00 0.63 75.83 ± 0.35 81.57 ±0.79 0.35 79.76 ± 0.41 OOM 0.58 80.36 ± 0.71 75.92 ± 0.69 0.36 87.55 ± 1.13 78.97 ± 0.54 0.15 76.41 ± 0.50 84.78 ± 0.76 74.31 ± 0.87 79.56 ± 0.51 81.92 ± 0.52 77.96 ± 0.37 84.39 ± 0.55 87.61 ± 0.26 84.09 ± 0.34

T OLOKERS

0.85

0.81

0.67

S QUIRREL - FIX 34.47 ± 3.09 33.89 ± 2.61 36.27 ± 2.12 36.61 ± 3.06 40.07 ± 2.73 40.58 ± 2.00 41.05 ± 2.67 36.58 ± 2.75 38.25 ± 2.62 39.55 ± 3.10 36.65 ± 0.80 38.31 ± 2.43 36.19 ± 3.20 40.45 ± 2.51 38.83 ± 2.19 42.24 ± 2.45 40.49 ± 2.01 38.52 ± 2.07 41.08 ± 2.08 42.25 ± 2.66 44.11 ± 3.53 40.11 ± 2.94 42.40 ± 2.38

1.00

0.88 Ours GCN GMoE DAMoE Mowst

1.00

Ours GCN GMoE DAMoE Mowst

% -8

0% 50

% -7

% -6

% -5

% -4

% -3

% -2

0.94

C HAMELEON - FIX 33.31 ± 2.32 41.85 ± 3.22 43.31 ± 3.42 44.94 ± 3.67 43.09 ± 3.85 44.27 ± 5.23 45.28 ± 4.33 43.99 ± 2.02 45.79 ± 3.31 44.27 ± 3.98 40.74 ± 2.26 46.12 ± 2.25 42.58 ± 3.24 44.44 ± 3.20 44.27 ± 3.68 46.69 ± 3.55 45.67 ± 4.54 44.16 ± 3.55 45.51 ± 2.80 43.37 ± 2.60 50.39 ± 4.71 49.16 ± 5.39 48.31 ± 4.74

Coauthor Physics

0.75

0.92

0.75

Chameleon-fix

0.85

Ours GCN GMoE DAMoE Mowst

1.00

-3

0.70

Actor

1.00

0.84

Ours GCN GMoE DAMoE Mowst

0.77

37.14 ± 1.06 30.65 ± 1.06 30.58 ± 1.18 37.60 ± 0.95 37.27 ± 1.27 36.89 ± 0.83 37.59 ± 0.95 36.89 ± 1.13 37.14 ± 1.06 37.08 ± 1.08 37.80 ± 0.95 36.99 ± 1.39 36.83 ± 1.10 36.73 ± 1.27 36.59 ± 0.90 33.78 ± 1.32 36.28 ± 1.39 37.68 ± 0.73 28.76 ± 1.01 35.50 ± 1.67 38.01 ± 1.15 38.26 ± 1.06 37.53 ± 0.88

-2

0.60

0% -1

Coauthor CS

0.85 Ours GCN GMoE DAMoE Mowst

53.46 ± 0.35 69.71 ± 0.18 70.03 ± 0.42 69.15 ± 0.18 OOM 69.95 ± 0.19 66.87 ± 1.48 69.98 ± 0.11 71.09 ± 0.21 OOM OOM 70.25 ± 0.13 71.59 ± 0.24 OOM 65.84 ± 0.24 71.66 ± 0.29 70.51 ± 0.29 71.34 ± 0.24 71.50 ± 0.22 70.37 ± 0.24 71.72 ± 0.25 71.36 ± 0.17 71.41 ± 0.24

76.86 ± 0.34 93.98 ± 0.34 94.03 ± 0.36 93.72 ± 0.35 94.36 ± 0.32 94.84 ± 0.24 91.90 ± 1.95 94.27 ± 0.33 94.32 ± 0.32 OOM 92.61 ± 0.16 93.35 ± 0.28 93.88 ± 0.40 94.23 ± 0.47 86.66 ± 0.54 94.90 ± 0.25 94.84 ± 0.28 95.12 ± 0.24 94.96 ± 0.21 94.46 ± 0.53 95.36 ± 0.26 95.47 ± 0.37 95.44 ± 0.41

0.80

79.57 ± 0.81 83.80 ± 0.66 83.99 ± 0.73 84.75 ± 0.64 84.62 ± 0.66 84.84 ± 0.54 84.47 ± 0.75 85.10 ± 0.77 85.10 ± 0.58 79.05 ± 0.97 83.27 ± 0.49 84.31 ± 0.72 84.57 ± 0.58 83.54 ± 0.70 82.67 ± 0.58 83.65 ± 0.61 85.08 ± 0.62 85.13 ± 0.84 84.04 ± 0.80 81.40 ± 0.64 84.81 ± 0.65 85.23 ± 0.65 85.45 ± 0.74

Photo

1.00 0.93

0.70

96.11 ± 0.14 96.37 ± 0.20 96.28 ± 0.31 96.69 ± 0.23 97.00 ± 0.16 96.94 ± 0.20 96.91 ± 0.27 97.00 ± 0.27 96.98 ± 0.20 OOM 96.28 ± 0.19 96.43 ± 0.20 96.89 ± 0.20 96.98 ± 0.22 96.87 ± 0.18 96.48 ± 0.23 OOM 96.73 ± 0.18 96.42 ± 0.28 97.11 ± 0.16 97.14 ± 0.21 96.89 ± 0.21 97.07 ± 0.26

ACTOR

94.80 ± 0.35 93.40 ± 0.45 93.20 ± 0.64 94.17 ± 0.46 95.62 ± 0.27 95.17 ± 0.34 94.93 ± 0.22 95.47 ± 0.33 95.51 ± 0.32 94.61 ± 0.30 93.93 ± 0.23 94.96 ± 0.25 95.62 ± 0.29 95.49 ± 0.26 95.21 ± 0.20 93.18 ± 0.58 OOM 94.51 ± 0.43 93.42 ± 0.50 94.78 ± 0.40 95.82 ± 0.15 95.42 ± 0.17 95.71 ± 0.25

O GBN - ARXIV

92.00 ± 0.56 94.26 ± 0.59 94.42 ± 0.61 95.41 ± 0.45 95.59 ± 0.48 95.44 ± 0.33 94.44 ± 0.62 95.42 ± 0.39 95.50 ± 0.41 91.58 ± 0.73 94.51 ± 0.24 94.95 ± 0.52 95.42 ± 0.26 95.41 ± 0.38 94.46 ± 0.49 94.51 ± 0.68 95.53 ± 0.41 95.49 ± 0.36 94.39 ± 0.53 95.48 ± 0.47 95.59 ± 0.52 95.64 ± 0.28 95.79 ± 0.47

FACEBOOK

W IKI -CS

C OAUTHOR

% -9 0 % % -1 00 %

% -8

% -7

% -6

% -5

% -4

% -3

% -2

0% -1

0% % 90 90% % -1 00 % 80

C OAUTHOR

Computers

Accuracy

% -8

0% 70

% -7

% -6

0% 40

85.01 ± 0.84 91.17 ± 0.54 91.44 ± 0.43 90.94 ± 0.56 91.69 ± 0.33 91.80 ± 0.55 89.54 ± 0.75 91.66 ± 0.78 91.03 ± 0.56 84.41 ± 0.72 90.01 ± 0.38 90.22 ± 0.42 91.46 ± 0.51 91.52 ± 0.55 90.70 ± 0.59 91.37 ± 0.49 91.87 ± 0.33 92.00 ± 0.43 91.57 ± 0.64 91.65 ± 0.59 92.23 ± 0.33 92.01 ± 0.38 92.14 ± 0.39

0.90

Accuracy

0.56

Prediction Entropy IntervalCS (Deciles) P HYSICS

MLP GCN GAT SAGE H2GCN-2020 GPRGNN-2021 FAGCN-2021 ACMGCN-2022 FSGNN-2022 VANILLA GT ANS-GT-2022 NAGF ORMER -2023 E XPHORMER -2023 D IFFORMER -2023 SGF ORMER -2024 GM O E-2023 N ODE M O E-2024 M OWST-2024 DAM O E-2025 M OSCAT-2025 D2 M O E (GCN) D2 M O E (SAGE) D2 M O E (GAT)

1.00

P HOTO

Ours GCN GMoE DAMoE Mowst

VANILLA H ETERO GT G RAPH M O E

% -5

% -4

% -3

0% 10

% -2

C OMPUTERS

M ETHOD

Ours GCN GMoE DAMoE Mowst

0.46

DATASET

0% -1

0% % 90 90% % -1 00 %

% -8

% -7

% -6

% -5

% -4

% -3

% -2

0.15

0.00

0.25

Ours GCN GMoE DAMoE Mowst

Prediction Entropy Interval (Deciles)

Fig. 3: Fine-grained performance comparison across different node difficulty levels. We stratify test nodes into 10 equal-sized intervals (deciles) based on their predictive entropy (calculated by a fixed proxy model). The x-axis represents entropy percentiles (from Easy to Hard), and the y-axis denotes classification accuracy. D2 MoE demonstrates superior robustness, particularly in high-entropy (hard) intervals.

B. Node Classification Performance Analysis in Sec. III-A). Based on these predictive entropy values, we 1) Overall Performance Analisys: As evidenced in Table I, sort and partition the test nodes into 10 equal-sized intervals D2 MoE establishes a new state-of-the-art by outperforming (deciles). The intervals range from [0%-10%] (lowest entropy, 19 baselines across all 13 datasets. Notably, the performance easiest nodes) to [90%-100%] (highest entropy, hardest nodes). 2 advantage is most pronounced on heterophilous graphs (e.g., We then evaluate the average classification accuracy of D MoE, Squirrel, Actor, Roman-empire), where D2 MoE surpasses the GCN, and three representative Graph MoE baselines (GMoE, strongest baselines by margins ranging from 0.07% to 7.92%. DAMoE, and Mowst) within each interval. The results across 12 datasets are visualized in Figure 3, Crucially, D2 MoE demonstrates cross-paradigm superiority, simultaneously transcending the rigid capacity limits of static from which several critical conclusions can be drawn. First, a Graph MoEs, resolving structural ambiguity better than Het- universal trend observed across all datasets and models is that erophilic GNNs, and avoiding the optimization bottlenecks of classification accuracy exhibits a strictly monotonic decrease as heavy Graph Transformers. We attribute these substantial gains predictive entropy increases. This empirical evidence strongly to the model’s sensitivity to structural and semantic ambiguity, validates our core hypothesis: predictive entropy serves as a which improves its ability to classify hard nodes. This claim reliable and effective proxy for node discriminative difficulty. Furthermore, while D2 MoE maintains comparable performance is supported by the stratified analysis as follows. 2) Fine-grained Performance Analysis across Difficulty with baselines in low-entropy intervals (0% − 30%), the Levels: To provide a deeper insight into how D2 MoE handles performance gap between our method and the baselines nodes of varying discriminative difficulty compared to baselines, becomes significantly more pronounced across the medium-towe conduct a stratified performance analysis. To ensure a high entropy intervals (40% − 100%), indicating that D2 MoE rigorous and unbiased comparison, we utilizes a pre-trained, consistently achieves higher classification accuracy on these independent proxy model to calculate the predictive entropy challenging nodes. This phenomenon highlights the efficacy of for all test nodes (same as motivational experiment settings our difficulty-aware dynamic routing. For easy nodes with low

0.43 0.21 0.00 1.00 0.87 0.73 0.60 0.46 0% -1 10 0% %

1.00

Ours GCN GMoE DAMoE Mowst

-6 0

% 40

-5 0

% 30

-4 0

% %

-3 0

-2 0

-1 0

0.00

% -1 00 %

% 80

-9 0

% 70

-8 0

% 60

-7 0

% 50

-6 0

% 40

Squirrel-fix

1.00

0% -1

-5 0

% 30

-4 0

-3 0

% 20

-2 0

% 10

-1 0

0% -1 10 0% % -2 20 0% % -3 30 0% % -4 40 0% % -5 50 0% % -6 60 0% % -7 70 0% % -8 80 0% % 90 90% % -1 00 %

0.00 %

0.68

0.40

Predic

Prediction Entropy Interval

Ours

92.08 91.60 92.23

95.40Prediction Entropy 95.48 Interval 95.29 95.19 95.79 95.82

97.07 96.98 97.14

84.99 95.33 Prediction Entropy Interval 84.85 94.25 85.45 95.47

71.62 71.20 71.72

37.49 37.30 38.26

47.75 47.67 50.39

42.79 42.12 44.11

86.54 83.03 87.61

85.66 85.37 85.74

83.40 79.52 84.55

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

w/o ℒ!"

Photo

Computer

92.50

92.23

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

96.00

w/o ℒ!"

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

95.75

Coauthor CS

96.20

w/o ℒ!"

95.83

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

Coauthor Physics

97.50

w/o ℒ!"

97.31

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

Wiki-CS

85.60

w/o ℒ!"

85.38

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

95.45

91.95

95.50

95.45

97.13

85.15

94.90

91.68

95.25

95.08

96.94

84.93

94.35

91.40

95.00

94.70

96.75

84.70

Actor

38.60

38.23

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

Chameleon-fix

51.00

w/o ℒ!"

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

50.15

Squirrel-fix

45.50

w/o ℒ!"

44.13

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

Roman-empire

90.00

w/o ℒ!"

87.70

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

w/o ℒ!"

86.00

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

93.80

Tolokers

87.00

Facebook

96.00

w/o ℒ!"

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

Penn94

88.00

w/o ℒ!"

84.75

37.85

49.30

42.75

85.40

85.00

81.50

37.48

48.45

41.38

83.10

84.00

78.25

37.10

47.60

40.00

80.80

83.00

75.00

w/o ℒ!"

Static Top-k Random Top-p

Fixed Top-p

w/o ℒ!"

Ours

w/o ℒ!"

Coauthor CS

Avg Active Experts Node Count Overall Avg Experts(1.57)

Coauthor Physics

Avg Active Experts Node Count Overall Avg Experts(2.80)

Wiki-CS

Avg Active Experts Node Count Overall Avg Experts(1.07)

Facebook

Avg Active Experts Node Count Overall Avg Experts(1.57)

Avg Active Experts Node Count Overall Avg Experts(1.07)

1E+05 1E+04 1E+03

4 1E+02 2

1E+01

Actor

Chameleon-fix

Avg Active Experts Node Count 72.00 Overall Avg Experts(2.70)

Static Top-k Random Top-p

Roman-empire

Toloker

Avg Active Experts Node Count Overall Avg Experts(1.64)

Avg Active Experts Node Count Overall Avg Experts(2.81)

1E+00

Penn94

Avg Active Experts Node Count Overall Avg Experts(3.41)

Avg Active Experts Node Count Overall Avg Experts(1.03)

w/o ℒ!"

71.75

Squirrel-fix

Avg Active Experts Node Count Overall Fixed Top-pAvg Experts(2.70)

Ogbn-arxiv

1E+05 1E+04 1E+03

Ours

1E+02

-1 0.9

-0 0.8

-0 0.7

-0

0.6

-0

0.5

-0

0.4

-0

0.3

-0

0.2

0.1

-0 0.0

-1

-0

0.9

-0

0.8

0.7

-0 0.6

-0 0.5

-0 0.4

-0 0.3

-0

0.2

0.1

-0 0.0

-1 0.9

-0 0.8

-0 0.7

-0

0.6

-0

0.5

-0

0.4

0.3

-0

0.2

0.1

-0 0.0

-1

-0

0.9

0.8

-0 0.7

-0

71.00

0.6

-0 0.5

-0 0.4

-0 0.3

-0

0.2

0.1

-0 0.0

-1 0.9

-0 0.8

-0

0.7

-0

0.6

-0

0.5

0.4

-0 0.3

-0

0.2

0.1

-0 0.0

1E+00 -1

-0

1E+01

0.9

0.8

-0 0.7

-0 0.6

-0 0.5

-0 0.4

-0

0.3

0.2

0.1

-0 0.0

71.25 .4

0 .3

71.50

Node Count (log scale)

Avg Active Experts Node Count Overall Avg Experts(1.31)

Node Count (log scale)

Photo

Computer

Average number of activated experts

Fig. 4: Ablation analysis on D MoE.

Prediction Entropy Interval

Fig. 5: Node density distribution and average number of activated experts across varying levels of discriminative difficulty. entropy, D2 MoE behaves similarly to baselines and maintains high efficiency. However, for hard nodes with high entropy, the model effectively captures the difficulty via the entropy signal and adaptively scales the computational budget. By activating a denser expert ensemble to reason about these ambiguous samples, this detect and scale capability enables D2 MoE to resolve complex patterns that static architectures fail to capture. C. Ablation Analysis on Routing and Regularization To assess the contribution of components in D2 MoE, we conduct a comprehensive ablation study by comparing D2 MoE with four variants: (1) Static top-k, which utilizes a fixed expert budget (searching k ∈ {1, 2, 3, 4, 5, 6}); (2) Fixed top-p, which employs a global constant threshold p for all nodes (searching p ∈ {0.3, 0.5, 0.7}); (3) Random top-p, which replaces predictive entropy guidance with random sampling; (4) w/o LRE , which excludes the routing entropy regularization; and (5) w/o LLB , which removes the load balancing loss. Results are visualized in Figure 4. 1) Impact of Dynamic Routing: We consider the “Static top-k” and “Fixed top-p” variants as static routing strategies because the former presumes a uniform computational budget while the latter assumes globally consistent discriminative difficulty. Results indicate that both variants suffer from significant performance degradation with average drops of 1.46% and 5.00% on heterophilous graphs. This confirms that rigid architectural priors fail to match the varying difficulty of nodes, leading to a expert resource mismatch, i.e., overcomputing for easy nodes and under-fitting for hard ones. By

breaking these rigid constraints, D2 MoE dynamically aligns the computational budget with real-time predictive entropy, effectively resolving this bottleneck. 2) Effectiveness of Difficulty Awareness: The “Random Topp” variant exhibits an average performance drop of 1.25% across all datasets. This result refutes the hypothesis that performance gains arise solely from ensemble effects caused by varying expert counts and validates predictive entropy as an effective proxy for discriminative difficulty. Guided by predictive entropy, D2 MoE allocates additional computational resources only to hard nodes near decision boundaries, ensuring that extra computation serves to resolve specific decision ambiguities rather than being applied arbitrarily. 3) Necessity of Regularization: Both regularization terms are critical for routing stability. Specifically, removing LLB causes a 2.28% decline due to expert collapse, while removing LRE leads to a 1.13% drop by encouraging flat routing distributions that introduce noise. Together, these constraints ensure a robust routing that remains globally balanced and locally decisive. D. Interpretability Analysis of the Routing Mechanism To verify whether D2 MoE effectively achieves on-demand computation based on discriminative difficulty, we conduct a joint analysis combining macroscopic statistical patterns and microscopic representation distributions. 1) Macroscopic Statistical Analysis: First, we stratify test nodes into distinct difficulty levels based on their predictive entropy and analyze the node density alongside the average expert activation count. As shown in Figure 5, the results reveal

Computers

Photo

Coauthor CS

Coauthor Physics

Wiki-CS

Facebook

Computers

Photo

Coauthor CS

Coauthor Physics

Wiki-CS

Facebook

Actor

Chameleon-fix

Squirrel-fix

Roman-empire

Tolokers

Penn94

Computers

Photo

Coauthor CS

Coauthor Physics

Wiki-CS

Facebook

Expert Activation Count Distribution

Ground-Truth Label Distribution

Expert Activation Count Distribution

Ground-Truth Label Distribution

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

Fig. 6: Visualization of learned node representations via t-SNE across 12 datasets. For each dataset, nodes are colored by Ground-Truth Labels (Top) and Activated Expert Counts (Bottom). The results highlight a clear boundary-focused resource allocation pattern.

a significant positive correlation between the computational budget and node discriminative difficulty, where the average number of active experts exhibits a strict monotonic upward trend as predictive entropy increases. This confirms that the difficulty-aware routing successfully establishes a dynamic mapping from node-wise difficulty to computational overhead. Moreover, this adaptive routing mechanism proves robust across diverse graph topologies. Even in heterophilous scenarios characterized by a skew toward high-entropy intervals, D2 MoE consistently maintains minimal expert activation for easy nodes to reduce redundancy, while selectively scaling up the budget for hard nodes to ensure sufficient reasoning capacity. 2) Microscopic Visualization Analysis: To provide microscopic evidence, we present a comprehensive visualization of the learned node representations and the corresponding expert activation patterns across all 12 datasets. Figure 6 presents the t-SNE projections of the node embeddings in the final layer, where each node is colored according to its ground-truth label (Top) and its adaptively allocated expert count (Bottom). We observe a spatial correspondence between confusion regions in the label distribution space (Top) and high activation regions in the expert count distribution space (Bottom). For homophilous datasets such as Computers, Photo, and CS, the label projections show clearly separated clusters. In these sce-

narios, D2 MoE demonstrates a clear “core-periphery” resource allocation strategy. Specifically, cluster centroids where nodes of the same class gather tightly correspond to dark blue areas (k = 1) in the expert plots. This indicates that D2 MoE correctly identifies these clear samples and processes them with minimal computational overhead. Conversely, inter class margins where different clusters meet align perfectly with warmer colors (k ≫ 1). This visual alignment confirms that the router perceives the semantic ambiguity at these decision boundaries and concentrates resources there to resolve conflicting signals. In the case of heterophilous graphs, the topology becomes more complex and appears as entangled areas in the label distribution space where class colors mix without clear separation. Accordingly, the expert activation maps shift from localized boundary highlighting to a widespread distribution of warmer colors. This represents a logical generalization because pervasive structural noise turns the majority of the graph into a difficult boundary regions. D2 MoE correctly perceives this widespread ambiguity and triggers a global expansion of expert resource to maintain robustness. In summary, D2 MoE acts as a reliable detector of semantic ambiguity regardless of whether the boundaries are localized or pervasive. It dynamically scales its reasoning capacity in alignment with the visual difficulty of the data manifold.

JOURNAL OF LATEX CLASS FILES, VOL. 14, NO. 8, AUGUST 2021

Record · ID 10370 · SHA-256 522805b4d4dfb161
Conceptio Open Knowledge Archive — every document is proof-bundled with source, license, and retrieval metadata.