Link Prediction

Traditional link prediction relies on heuristic scores like Common Neighbors or Adamic-Adar, which are predefined and static. In contrast, GNN-based models learn a parameterized scoring function directly from the graph's topology and node features. This allows the model to adapt to the specific characteristics of a cellular deployment, such as urban canyons or dense small-cell layouts, rather than applying a one-size-fits-all metric.

• Heuristic: Common Neighbors, Jaccard Coefficient, Preferential Attachment
• Learned: Graph Autoencoder (GAE) scoring, Neural tensor networks
• Advantage: Learned functions capture complex, non-linear interference patterns invisible to simple heuristics

Most GNN-based link prediction models follow an encoder-decoder architecture. The encoder is a GNN that generates a low-dimensional embedding vector for each node by aggregating information from its local neighborhood. The decoder then takes a pair of node embeddings and computes a scalar score representing the probability of a link existing between them.

• Encoder: GraphSAGE, GAT, or a GCN that produces node embeddings z_u and z_v
• Decoder: A simple dot product z_u^T z_v, a cosine similarity, or a small MLP
• Training: The model is trained on existing edges (positive samples) and randomly sampled non-edges (negative samples) using a binary cross-entropy loss

A critical application is forecasting future handover events between base stations. The cellular topology is modeled as a dynamic graph where nodes are base stations and edges represent historical handover sequences. A spatiotemporal GNN can predict the next serving cell for a moving user equipment by learning mobility trajectories.

• Input: Sequence of connected base stations, signal strength measurements, and UE velocity
• Output: Ranked list of most likely next serving cells
• Benefit: Proactive resource reservation reduces handover latency and call drops, enabling seamless connectivity for high-speed users

In dense deployments, measuring pairwise interference between every base station is impractical. Link prediction can infer missing interference relationships from partial measurements. By modeling the network as an interference graph where edges represent significant co-channel interference, a GNN can predict unmeasured edges based on the known topology and terrain features.

• Known edges: Measured interference above a threshold
• Predicted edges: Likely interference based on proximity, antenna orientation, and propagation environment
• Impact: Enables accurate resource block allocation and power control without exhaustive drive testing

The choice of negative samples—node pairs without a link—is crucial for training effective link predictors. Random sampling is common but can produce easy negatives that don't challenge the model. Advanced strategies sample hard negatives that are geographically close or share many neighbors, forcing the model to learn finer distinctions.

• Uniform random: Simple but may yield trivially separable negatives
• Proximity-based: Sample node pairs within a certain distance threshold
• Adversarial: Dynamically select negatives the current model misclassifies
• Impact on cellular graphs: Prevents the model from predicting interference between distant, non-interacting cells

A key advantage of GNN-based link prediction over transductive matrix factorization is inductive generalization. Once trained on a set of existing cellular topologies, the model can predict links for a newly deployed network or a region with added small cells without retraining. This is because the GNN learns a function of node features and local structure, not memorizing specific node IDs.

• Transductive: Requires retraining for any new node; memorizes training graph structure
• Inductive: Generalizes to unseen nodes and graphs using learned aggregation functions
• Use case: A network operator deploys new small cells and immediately predicts their interference relationships with the existing macro layer

The foundational framework for most modern GNNs, including those used for link prediction. Nodes iteratively update their hidden states by receiving and aggregating 'messages' from their immediate neighbors. For a potential handover link between two base stations, an MPNN computes a representation of the edge by combining the final states of its endpoint nodes, which have been enriched by the local radio environment topology.

A dominant unsupervised architecture for link prediction. A GNN encoder compresses the graph into a low-dimensional latent space, learning a dense vector (embedding) for each node. A decoder then computes a score—typically the dot product or a simple neural network—between two node embeddings to reconstruct the adjacency matrix, directly predicting the probability of a missing or future edge. Variants like VGAE add variational inference for robustness.

The process of representing the properties of a connection between two nodes as a numerical vector, which is critical for informed link prediction. In a cellular network, this includes engineering features like:

• Path loss and channel gain between two base stations
• Geographic distance and antenna bearing difference
• Historical handover success rate These features are concatenated with the node embeddings before the final edge probability is computed.

A crucial training technique for link prediction that addresses extreme class imbalance. Since real-world graphs are sparse (most possible edges do not exist), the model is trained on a balanced set of positive edges (observed links) and negative edges (sampled non-existent links). Strategies include:

• Random sampling: Uniformly select absent node pairs
• Hard negative mining: Select non-edges that the model currently scores highly
• Distance-based sampling: Select geographically plausible but absent radio links

A GNN variant designed for graphs whose topology and node features evolve over time, essential for modeling user mobility in cellular networks. For link prediction, a dynamic GNN can forecast future handover events by processing a sequence of graph snapshots. Architectures often combine a spatial GNN with a temporal module like an RNN or temporal attention to capture how interference relationships and user associations shift across the network.

A critical failure mode in deep GNNs where information from an exponentially growing receptive field is compressed into a fixed-size node embedding vector. This prevents the model from learning long-range dependencies between distant nodes, such as a cascading interference relationship across multiple cells. For link prediction, over-squashing can cause the model to miss potential handover adjacencies between non-neighboring base stations that share a common, distant interferer. Graph Transformers with global attention are a primary mitigation.