# Graph Neural Networks for Routing Optimization: Challenges and Opportunities
## 2 Basics
### Graph Neural Network Basics  
In intelligent routing schemes, local or global topology information of the underlying network is important for making routing decisions. However, owing to network topology complexity and dynamicity, traditional machine learning models defined in Euclidean space often have difficulty processing network topology information well. GNNs are novel neural network structures proposed in recent years that can effectively deal with the challenge of topological information extraction. The node and edge features are represented as vectors in the GNNs and updated in each round based on the topological dependencies and update function. GNNs have proven effective for various tasks, for example, network topology information extraction and link prediction, with good scalability and generalization performance. For routing problems, GNNs can learn the complex relationship between the network topology, traffic demand, and routing policy to generate accurate estimates of delay distribution and loss for the source/destination [61]. In this part, a brief introduction to representative GNNs is provided. More discussion on GNNs can be found in recent surveys [62; 63; 64; 65; 66]. GNNs [67] are based on the message-passing mechanism, which updates the state of a particular node with information from its neighbors. Subsequently, the convolution operation is introduced into graph convolutional networks (GCNs), and two families of GNNs are developed: spectral-based GCNs and spatial-based GCNs. Spectral-based GCNs define the convolution operation in the spectral domain based on graph signal processing techniques and are successful with many well-known GCN  
Figure 5: The general framework of applying reinforcement learning for routing optimization. variants, such as ChebNet [68], GCN [69], CayleyNet [70], and AGCN [71]. To provide the mathematical formulation of the GCN, the following notations are introduced. A graph is denoted as \(G=(V,E)\), where \(V\) is the set of nodes and \(E\) is the set of edges. The network topology is denoted as the adjacency matrix \(\mathbf{A}\). When there is an edge \(e_{ij}\in E\) between node \(i\) and node \(j\), and the element \(A_{ij}=1\). Otherwise, \(A_{ij}=0\). The degree matrix \(\mathbf{D}\) measures the number of neighbors for each node, i.e., \(D_{ii}=||\mathcal{N}(v_{i})||\), where \(\mathcal{N}(v_{i})\) is the neighbor node set of node \(v_{i}\). The node feature matrix is \(\mathbf{X}\in R^{N\times d}\), where \(d\) is the feature dimension and \(N\) is the node number. The Laplacian matrix is \(\mathbf{L}=\mathbf{D}-\mathbf{A}\) and its normalized variant is \(\tilde{\mathbf{L}}=\mathbf{I}_{N}-\mathbf{D}^{-\frac{1}{2}}\mathbf{A}\mathbf{D }^{-\frac{1}{2}}\), where \(\mathbf{I}_{N}\) is the identity matrix of size \(N\). The graph convolution operation \(*G\) in GCN is defined as follows:  
\[\mathbf{X}_{*G}=\mathbf{W}(\tilde{\mathbf{D}}^{-\frac{1}{2}}\tilde{\mathbf{A} }\tilde{\mathbf{D}}^{-\frac{1}{2}})\mathbf{X} \tag{1}\]  
where \(\mathbf{W}\) is the learnable model parameter, \(\tilde{\mathbf{A}}=\mathbf{A}+\mathbf{I}_{N}\) and \(\tilde{\mathbf{D}}_{ii}=\sum_{j}\tilde{\mathbf{A}}_{ij}\). Spectral-based GCNs cannot handle directed graphs and have low scalability in most cases, with some exceptions [72; 73]. Spatial-based GCNs are more flexible and more general. By defining the corresponding update, message passing and readout functions, different spatial-based GCN variants can be represented in a unified form of a message-passing neural network (MPNN) [74], for example, PATCHY-SAN [75] and DCNN [76]. The two stages run iteratively in the MPNN, namely, a message-passing phase and a readout phase.