# Graph-Based Resource Allocation for Integrated Space and Terrestrial Communications
## 3 Graphs for Signal Processing in Wireless Networks
### Signal Processing on Graphs and Graph Neural Networks  
The input datum (generally referred to as a signal) is processed through filtering by one of the matrices which describe the graph's structure (usually the Laplacian or the degree matrix). Another common term for filtering is graph shift, because the graph's matrix shifts the signal's samples around the vertices of the graph [16; 17]. This operation (similar to data analysis in the time and frequency domains) can be described in either the vertex (analytically analogical to the time domain analysis), or the spectral (the Fourier transform of the vertex domain signal) domains. The fundamental expression of graph signal processing (GSP), given in the vertex domain, is:  
\[\mathbf{y}=h_{0}\mathbf{A}^{0}\mathbf{x}+h_{1}\mathbf{A}^{1}\mathbf{x}+\dots+h_{M-1}\mathbf{A}^{M-1}\bm {x}=\sum_{m=0}^{M-1}h_{m}\mathbf{A}^{m}\mathbf{x}\,, \tag{1}\]  
where a signal \(\mathbf{x}\) is filtered (or shifted) by a graph with an adjacency matrix \(\mathbf{A}\) by \(m=0,\dots,M-1\) filters, i.e., \(M\) different shifts are applied to the signal (corresponding to \(M\) stages of a filter), and their products are combined to obtain the resultant signal \(\mathbf{y}\), while \(h_{0},\dots,h_{M-1}\) are the scaling coefficients. The graph discrete Fourier transform (GDFT) of the signal \(\mathbf{x}\) is expressed as \(\mathbf{X}=\mathbf{U}^{-1}\mathbf{x}\), where \(\mathbf{X}\) is the vector of GDFT coefficients, while \(\mathbf{U}^{-1}\) is a matrix composed of the column eigenvectors of \(\mathbf{A}\). Correspondingly, the eigen  
Figure 3: General graph structures relevant to RA methods. (**a**) Complete graph. (**b**) Bipartite graph. (**c**) Star graph. (**d**) Path graph.  
decomposition of the adjacency matrix is as follows: \(\mathbf{A}=\mathbf{U}\mathbf{\Sigma}\mathbf{U}^{-1}\), \(\mathbf{\Sigma}\) being the matrix of eigenvalues of \(L\) that is used to express the graph filtering equation in the spectral domain:  
\[\mathbf{Y}=\sum_{m=0}^{M-1}h_{m}\mathbf{\Sigma}^{m}\mathbf{X}\,. \tag{2}\]  
Solving the problem of finding the filter's coefficients that minimize the \(l_{2}\)-norm error is commonly achieved via the Taubin \(\alpha-\beta\) algorithm. The parameters \(\alpha\) and \(\beta\), which determine the optimal solutions, are found empirically. This method is well illustrated through examples in [14; 17].  
GNNs combine GSP and the feature-extraction properties of traditional neural networks to allow for the efficient analysis of non-Euclidean data, as is represented via graph structures. These model-learning approaches are based on extracting information from the attributes/features of a graph's vertex, as well as the vertices with which it is connected through edges (which may also have separate attributes) [11; 18]. By aggregating them via a particular mathematical operation (most often convolution), a hidden representation of this vertex is produced. Each GNN layer processes the input data (attributes matrix) \(\mathbf{X}\in\mathbb{R}^{M\times S}\), i.e., \(M\) vertices with \(S\) attributes each, in a manner similar to (1), through the matrix \(\mathbf{U}_{L}\) composed of the column eigenvectors of the Laplacian matrix \(\mathbf{L}\) and the neuron weights matrix \(\mathbf{W}\). As an example, the output of the \(k\)-th layer \(\mathbf{X}_{:,j}^{k}\) of a convolutional GNN is defined thus:  
\[\mathbf{X}_{:,j}^{k}=\mathcal{F}\left[\sum_{i=1}^{C-1}\mathbf{U}_{L}\,\mathbf{W}_{i,j}\, \mathbf{U}_{L}^{T}\,\mathbf{X}_{:,i}^{k-1}\right]\,,\,j=1,\ldots C\,, \tag{3}\]  
where \(C\) is the number of the layer's output channels (consequently, \(C-1\) is the number of input channels) and \(\mathcal{F}\) is the layer activation function. Other notable types of GNN are graph attention networks, graph auto-encoders, graph recurrent networks, and spatial-temporal GNNs [11].