While deep learning models that leverage local features have demonstrated significant potential for near-optimal routing in dense Euclidean graphs, they struggle to generalize well in sparse networks where topological irregularities require broader structural awareness. To address this limitation, we train a Cascaded Mixture of Experts (Ca-MoE) to solve the all-pairs near-shortest path (APNSP) routing problem. Our Ca-MoE is a modular two-tier architecture that supports the decision-making for forwarder selection with lower-tier experts relying on local features and upper-tier experts relying on global features. It performs adaptive inference wherein the upper-tier experts are triggered only when the lower-tier ones do not suffice to achieve adequate decision quality. Computational efficiency is thus achieved by escalating model capacity only when necessitated by topological complexity, and parameter redundancy is avoided. Furthermore, we incorporate an online meta-learning strategy that facilitates independent expert fine-tuning and utilizes a stability-focused update mechanism to prevent catastrophic forgetting as new graph environments are encountered. Experimental evaluations demonstrate that Ca-MoE routing improves accuracy by up to 29.1% in sparse networks compared to single-expert baselines and maintains performance within 1%-6% of the theoretical upper bound across diverse graph densities.
Figures & tables
Fig. 1: The Ca-MoE framework for forwarder selection. The Router directs the graph sample ⟨O,D,v,nbr(v)⟩ to a selected lower-tier expert that predicts a Q -value for each neighbor node u in nbr(v) , where nbr(v) denotes the set of v ’s neighbors. The candidate forwarder u^ for a near-shortest path from node v to destination node D is identified as a node in nbr(v) with the highest Q -value. This candidate is validated by the Deferral rule : the sample is cascaded to the upper-tier expert only if the confidence is insufficient. Dashed lines denote conditional execution paths, illustrating selective activation based on the graph sample (in orange) and the adaptive activation based on the candidate forwarder for the graph sample (in purple).
Fig. 2: Comparative performance of the Greedy-Tensile , Greedy-Lax , and Greedy-Spectral routing policies across different densities of Euclidean graphs. Each sub-figure illustrates a set of graphs where a different routing policy dominates: different graphs are enumerated on the x-axis; for each graph, the y-axis denotes the frequency with which each expert selects the best next forwarder for nodes v given samples ⟨O,D,v,nbr(v)⟩ from that graph. In sub-figures (b) and (c), the choices for v are constrained relative to the shortest paths from origin O to D . Recall that a forwarder is determined to be the “best” if it yields the maximal optimal Q -value, Q∗(O,D,v,u) .
Fig. 3: The online meta-learning pipeline. Upon the arrival of a new graph Gt , experts are selectively fine-tuned via a fine-tuning sampler. To prevent catastrophic forgetting, updated models ( H′ ) are validated against a persistent Evaluation Dataset ( ED ) before replacing the current experts ( Ht−1 ).
Symbol
Meaning
Value
Ntrain
size of seed graphs for training experts
50
ρGT
density of seed graph
5
for training Greedy-Tensile
ρGL/GS
density of seed graphs
2
for training Greedy-Lax and Greedy-Spectral
R
communication radius
1000
TABLE I: Simulation Parameters
Fig. 4: Comparative APNSP prediction accuracy on individual graph instances ( Gt ) for Ca-MoE against single-expert baselines. The x-axis enumerates specific graph instances, while the y-axis reports the routing accuracy.
Fig. 5: Evolution of average APNSP prediction accuracy across the sequence of seen graphs G1..Gt shown in Figure 4 . The figure illustrates the continual generalization capability of the framework. The x-axis represents the chronological sequence of arriving graphs, and the y-axis denotes the average accuracy on all graphs encountered up to time t .
Fig. 6: Comparative APNSP prediction accuracy across the sequence of seen graphs G1..Gt shown in Figure 5(a) . This comparison highlights the framework’s robustness to initialization by tracking the convergence of Ca-MoE(Random) (arbitrarily initialized experts) against the standard Ca-MoE framework and other baselines.
Fig. 7: Ca-MoE’s expert utilization on individual graph instances. The x-axis enumerates specific graph instances, while the y-axis reports the the frequency with which each expert is activated for contributing the final selection of forwarder.
Mixture-of-experts models use input-dependent routing to activate specialized subnetworks, increasing model capacity without running every parameter for each input.