# Graph Neural Networks for Routing Optimization: Challenges and Opportunities
## 2 Basics
### Graph Neural Network Basics
The message-passing phase is defined as follows:  
\[\mathbf{m}_{v_{i}}^{(t)}=\sum_{v_{j}\in\mathcal{N}(v_{i})}\mathcal{M}^{(t)}( \mathbf{X}_{i}^{(t-1)},\mathbf{X}_{j}^{(t-1)},\mathbf{e}_{ij}) \tag{2}\]  
where \(\mathbf{m}_{v_{i}}^{(t)}\) is the message aggregated from the neighbors of node \(v_{i}\), \(\mathcal{M}^{(t)}(\cdot)\) is the aggregation function in the \(t\)th iteration, \(\mathbf{X}_{i}^{(t)}\) is the hidden state of node \(v_{i}\) in the \(t\)th iteration, and \(\mathbf{e}_{ij}\) is the edge feature vector between node \(v_{i}\) and node \(v_{j}\). The readout phase is defined as follows:  
\[\mathbf{X}_{i}^{(t)}=\mathcal{U}^{(t)}(\mathbf{X}_{i}^{(t-1)},\mathbf{m}_{v_{ i}}^{(t)}) \tag{3}\]  
where \(\mathcal{U}^{(t)}(\cdot)\) is the readout function in the \(t\)th iteration. In spectral-based GCNs, the filter depends on the Laplacian matrix, which is derived from the graph structure. Therefore, the model trained on a specific graph cannot be directly applied to other graph structures. To solve this problem, the graph attention network (GAT) [77] introduces an attention mechanism based on a graph convolutional network that enables the model to focus on the most relevant information. GAT has lower complexity and only focuses on adjacent nodes, without depending on the information from the entire graph. When applied to a new graph, GAT does not need to repeat the training model. The multi-head attention mechanism with \(K\) heads is leveraged in the propagation step in the GAT, which can be denoted as follows:  
\[\mathbf{X}_{i}^{(t)}=\|_{k}\sigma(\sum_{j\in\mathcal{N}(v_{i})}\alpha^{k}( \mathbf{X}_{i}^{(t-1)},\mathbf{X}_{j}^{(t-1)})\mathbf{W}^{(t-1)}\mathbf{X}_{ j}^{(t-1)}) \tag{4}\]  
where \(\|\) is the concatenation operation, \(\sigma\) is the activation method, and \(\alpha^{k}(\cdot)\) is the \(k\)-th attention mechanism. More GAT variants have been developed for more complex graphs, such as heterogeneous GAT [78] and dynamic GAT [79]. In routing optimization, different GNN architectures such as GCN, GAT, and GraphSAGE have been employed, each offering distinct advantages depending on the network conditions and tasks [80]. GCNs, which operate by applying spectral convolutions over graph structures, are effective for tasks where global network information needs to be captured, such as predicting delay or congestion across a broad topology. However, GCNs often struggle with scalability and handling dynamic, real-time updates in large networks [81]. GATs, which use attention mechanisms to focus on the most relevant neigh bors during message passing, perform better in environments with high variability, such as mobile or UAV networks, where certain connections are more critical than others [82]. This ability to dynamically weigh edge importance allows GATs to excel in networks with frequent topology changes. GraphSAGE, which generates node embeddings by sampling and aggregating features from a node's neighborhood, is particularly advantageous for large-scale networks where computational efficiency is crucial. It performs well in tasks like traffic prediction and load balancing by leveraging inductive learning, enabling it to generalize effectively to unseen nodes or topologies without retraining [83]. Overall, the choice of GNN architecture depends on the specific routing task: GCNs are suited for static or semi-static conditions, GATs for highly dynamic networks, and GraphSAGE for large-scale, resource-constrained environments requiring real-time adaptability. Scalability is a critical concern when applying GNNs to large-scale networks, particularly those with millions of nodes and edges. As network size increases, so do the challenges in terms of training time, computational resources, and inference efficiency. GNN models, such as GCNs, struggle with scalability because the graph convolution operations involve all neighbors of a node, which leads to an exponential growth in computations for deep networks [84].