Graph Neural Network (GNN)

The foundational mechanism where nodes iteratively update their state by receiving and aggregating feature vectors from their local neighborhood. Each node's new representation is a function of its previous state and the aggregated 'messages' from its neighbors. This process is formalized in the Message Passing Neural Network (MPNN) framework, which defines distinct message, aggregate, and update functions. In a cellular topology, a base station's representation would be updated by messages from its interfering neighbors, encoding their current load and transmission power.

A fundamental mathematical property ensuring that a GNN's output for a node or entire graph is unchanged regardless of the arbitrary ordering of input nodes. This is critical because graph data has no inherent node sequence. A GNN's aggregation function—such as sum, mean, or max—must be a symmetric function that produces the same result for any permutation of neighbor inputs. This guarantees a consistent, canonical representation of the network topology, unlike a standard neural network that would treat different node orderings as distinct inputs.

Unlike transductive methods that require the entire graph structure at training time, inductive GNNs like GraphSAGE learn a function that generates embeddings based on a node's local neighborhood features. This allows the trained model to generalize to previously unseen nodes or entirely new graphs without retraining. In a cellular network, this means a GNN trained on one city's topology can be deployed in another city, or can immediately generate embeddings for a newly deployed base station, making it essential for dynamic, evolving network infrastructures.

Two distinct paradigms for defining convolution on graphs:

• Spatial Graph Convolution: Operates directly in the node domain by aggregating features from a node's immediate neighbors, analogous to a convolutional kernel sliding over an image. It is computationally efficient and localized.
• Spectral Graph Convolution: Operates in the Fourier domain defined by the Graph Laplacian Matrix, filtering graph signals based on their frequency components. This provides a mathematically rigorous framework but is computationally expensive for large graphs and tied to a specific graph structure.

Standard GNNs treat all neighbors equally during aggregation. Graph Attention Networks (GATs) introduce a self-attention mechanism that dynamically learns to weigh the importance of different neighboring nodes. An attention coefficient is computed for each edge, allowing the model to focus on the most relevant connections and implicitly ignore noisy or irrelevant ones. In an interference graph, a GAT can learn to assign higher weight to a dominant interferer and lower weight to a weak, distant signal, leading to more precise resource allocation decisions.

Two critical limitations that constrain GNN depth and expressivity:

• Over-Smoothing: As the number of layers increases, node representations become indistinguishable due to repeated aggregation from overlapping neighborhoods, losing local information. This limits deep GNNs for tasks requiring fine-grained node classification.
• Over-Squashing: Information from an exponentially growing receptive field is compressed into a fixed-size vector, preventing the model from learning long-range dependencies between distant nodes. This is a bottleneck for capturing global network effects in large cellular topologies. Architectures like Graph Transformers aim to mitigate this via global self-attention.

A general framework that formalizes GNN computation as a process of nodes exchanging vector messages with neighbors. Each node aggregates incoming messages using a permutation-invariant function like sum, mean, or max, then updates its hidden state via a learnable function. In a cellular interference graph, a base station node receives messages encoding the transmit power and queue length of adjacent cells, allowing it to learn a representation of local contention. The message function itself can be a simple linear transformation or a multi-layer perceptron. MPNNs unify many popular architectures including Graph Convolutional Networks and GraphSAGE under a single conceptual umbrella.

A GNN architecture that introduces a self-attention mechanism to dynamically weight the importance of neighboring nodes during aggregation. Instead of treating all neighbors equally, GAT computes an attention coefficient for each edge, allowing the model to focus on the most relevant connections. In a cellular topology, this means a base station can learn to pay more attention to a high-power interferer than to a distant, low-impact neighbor. The attention weights are computed via a shared, learnable linear transformation followed by a softmax normalization. Multi-head attention, where multiple independent attention mechanisms run in parallel and their outputs are concatenated, stabilizes training and captures different relationship types simultaneously.

An inductive GNN framework that generates node embeddings by sampling and aggregating features from a node's local neighborhood. Unlike transductive methods that require the full graph at training time, GraphSAGE learns a function that can produce embeddings for previously unseen nodes or entirely new graphs. This is critical for cellular networks where user equipment continuously joins and leaves. The framework supports multiple aggregation functions:

• Mean aggregator: Takes the element-wise mean of neighbor features
• LSTM aggregator: Applies an LSTM to a random permutation of neighbors
• Pooling aggregator: Feeds neighbor features through a dense layer followed by max-pooling Neighborhood sampling with a fixed sample size ensures computational cost remains bounded even for high-degree nodes.

A GNN operation that defines convolution in the Fourier domain of the graph Laplacian matrix. The graph Laplacian L = D - A (degree matrix minus adjacency matrix) encodes fundamental topological properties. Its eigendecomposition yields a set of orthonormal basis vectors that represent the graph's frequency spectrum. A spectral convolution filters the graph signal by multiplying its Fourier transform with a learnable filter in the spectral domain. Chebyshev polynomial approximations avoid the expensive eigendecomposition, enabling efficient localized filtering. In cellular networks, spectral methods naturally capture global structural patterns like community structure among clusters of small cells, but they are inherently transductive and struggle with evolving topologies.

A GNN operation that defines convolution directly on the graph's spatial domain by aggregating features from a node's immediate neighbors. This is analogous to a convolutional kernel sliding over an image, but adapted to irregular connectivity. The operation is inherently local: each node's new representation is a function of its own features and those of its one-hop neighborhood. Stacking multiple spatial convolution layers expands the receptive field, allowing information to propagate across the graph. In a cellular topology, a two-layer spatial GNN allows a base station to incorporate information from its neighbors' neighbors, capturing second-order interference effects. Spatial methods are computationally efficient, support inductive learning, and form the basis of most modern GNN architectures including GCN, GraphSAGE, and GAT.

A GNN architecture that applies the global self-attention mechanism of the Transformer to all nodes in a graph. Unlike message-passing GNNs that are constrained to local neighborhoods, a Graph Transformer allows each node to attend to every other node, potentially mitigating the over-squashing problem where information from distant nodes is compressed into a fixed-size vector. To incorporate topological information that is lost when removing the graph structure constraint, Graph Transformers inject positional encodings such as Laplacian eigenvectors or random walk probabilities into node features. In large cellular networks, this global attention enables a central controller to model long-range dependencies between distant base stations that share spectrum but are not direct neighbors in the interference graph.