# Graph Neural Networks for Routing Optimization: Challenges and Opportunities
## 4 Supervised Learning for Routing Optimization
### Literature Review  
Early-stage studies validated the potential application of leveraging GNNs to learn the same routing policies in a distributed approach from heuristic centralized routing algorithms. The graph-query neural network (GQNN) [53] is the first study to apply GNNs to distributed routing protocols, in which the GNN model is used in each router to decide which output interface to use, given a destination router identifier. Temporal information propagation is modeled by a gated graph neural network (GG-NN) [52], and neighborhood interaction is captured by the edge attention mechanism. Path calculation results from two different routing strategies are employed here as learning objectives (to demonstrate the scalability of the proposed model), that is, shortest path routing based on [PERSON]'s algorithm and min-max routing, which maximizes the minimum allocated bandwidth between all possible source-destination pairs in the network. The proposed GQNN achieves accuracies of 98% and 95% for the shortest path and min-max routing, respectively.  
Subsequently, a similar study is conducted in [104], in which a GN-based model [98] is used to learn the routing route generated by the genetic algorithm. With bandwidth utilization maximization as the routing objective, the proposed model achieves 61.0% accuracy for predicting the routing table of the genetic algorithm, with a 150\(\times\) faster prediction time.  
A graph-aware deep learning-based intelligent routing strategy (GADL) [105] is proposed to predict the next forwarding node with a routing policy that minimizes the average end-to-end flow latency. The proposed graph-aware convolutional structure first extracts topological information from the graph, then processes the input data based on the extracted information, and finally applies a convolution to the processed data. GADL achieves an accuracy of 86.55% for predicting the next forwarding node and a lower average network latency than OSPF.  
NGR [106] is the first deep-learning-based distributed routing system that aims to guarantee connectivity and avoid the self-loop problem in previous neural network-based  
Figure 6: The general framework of applying GNNs in a supervised learning approach for routing optimization.  
routing solutions. A GNN [67] model is used to model spatial dependency and aggregate the feature vectors of neighboring nodes. A recurrent neural network is used to model the temporal dependency and update the feature vector for a node. Then, the feature vector and input packet ID are fed into a forwarding neural network. Finally, an S-LRR (sequential link-reversal routing) algorithm determines the forwarding port for the packet based on the value vector output from the forwarding neural network. The numerical experiments show that for shortest-path routing or load balancing, NGR achieves 100% routing reliability and gain performance close to the optimal solutions.  
A GCN-based GLR is proposed in [107] to handle the highly dynamic topology and limited resource challenges in satellite networks. A high-order and low-order feature extractor and cross-process are well-designed to handle unseen topologies. Offline pre-training is introduced to reduce the on-board computation complexity. Instead of using the next node selection probability as the GNN output in previous studies, GLR uses the communication distance as the output, which is the hop count between the current and destination node. GLR outperforms the brute-force and shortest-path routing algorithms in terms of end-to-end transmission delay and packet drop rate. GLR is also more robust when facing link interruptions and has a lower routing computation cost.  
The relevant studies with supervised learning for routing optimization are summarized in Table 4.