Neighborhood Sampling

Breaks the full graph into small, independent subgraphs to enable stochastic gradient descent on hardware with limited memory. Instead of loading the entire adjacency matrix, a mini-batch is formed by selecting a set of target nodes and recursively sampling their local neighborhoods. This converts an unsolvable full-batch problem into a series of tractable, parallelizable computations, making training on a cellular topology graph with millions of base stations feasible.

Constructs the computation graph by expanding outward from a target node one hop at a time. For a 3-layer GNN, the sampler first fetches the target node's direct neighbors, then samples their neighbors, and finally samples the neighbors of those neighbors. This recursive expansion ensures the receptive field grows exponentially but the number of sampled nodes per layer remains bounded by a fixed fan-out hyperparameter, preventing the over-squashing of information from distant nodes.

Determines the probability distribution used to select neighbors. Uniform sampling assigns equal probability to all neighbors, preserving the original degree distribution. Importance-based sampling uses heuristics like node degree or PageRank to prioritize high-influence nodes, reducing variance in the aggregated message. In a cellular interference graph, this could mean prioritizing sampling for high-power macro cells over low-power small cells to stabilize training.

A strict hyperparameter that caps the number of sampled neighbors per node at each layer, directly controlling the computational footprint of the message-passing operation. A fan-out of [10, 5] means each target node samples 10 first-hop neighbors, and each of those samples 5 second-hop neighbors. This guarantees a predictable memory budget regardless of whether a node has 10 or 10,000 neighbors, a critical property for dynamic graph neural networks where node degrees fluctuate with user mobility.

Enables the trained model to generate embeddings for nodes never seen during training. Because the GNN learns an aggregation function rather than memorizing a fixed transductive embedding table, it can apply this function to the sampled neighborhood of a new base station added to the cellular topology during a network expansion. This is the foundational property that distinguishes frameworks like GraphSAGE from earlier transductive methods and makes them viable for production RAN optimization.

The statistical cost of approximation. Sampling introduces stochastic variance into the gradient estimates because the aggregated message from a subset of neighbors differs from the true full-neighborhood message. Smaller fan-outs reduce compute but increase variance, potentially destabilizing convergence. Advanced samplers like Cluster-GCN or GraphSAINT mitigate this by constructing subgraphs that minimize inter-batch variance, ensuring the trained model's resource allocation policy is robust.

The standard training paradigm enabled by sampling. A mini-batch is formed by selecting a small set of target nodes and recursively sampling their neighbors to build a computation graph.

• Computational Footprint: Reduces memory complexity from O(N) to O(batch_size * k^L), where k is the sample size and L is the number of layers.
• Stochastic Gradient Descent: Enables the use of SGD optimizers on graphs too large to fit in GPU memory.
• Dependency Graph: Each mini-batch constructs a local, bipartite dependency graph between layers for message passing.

A failure mode that sampling strategies must mitigate. Over-squashing occurs when information from an exponentially growing receptive field is compressed into a fixed-size node embedding, preventing long-range signal propagation.

• Bottleneck Effect: Arises from the topological structure, not just the number of layers.
• Sampling's Role: Strategic sampling can expand receptive fields or prioritize high-importance edges to alleviate the bottleneck.
• Related to Over-Smoothing: Distinct from over-smoothing, where node representations become indistinguishable, though both plague deep GNNs.

An alternative sampling approach that partitions the graph into dense clusters using METIS or similar algorithms. Mini-batches are formed from these clusters, maximizing intra-batch connectivity.

• Subgraph Sampling: Operates on entire subgraphs rather than individual node neighborhoods.
• Efficiency: Reduces the number of inter-cluster edges cut, leading to more informative message passing per batch.
• Stochastic Multiple Partitions: Randomly reassembles clusters across epochs to maintain stochasticity and reduce bias.

A variance-reduction technique that samples neighbors non-uniformly based on their relevance. Importance sampling assigns higher probability to neighbors that contribute more to the message-passing operation.

• Variance Reduction: Minimizes the estimator variance introduced by random sampling, leading to more stable training.
• Adaptive Methods: Schemes like FastGCN treat nodes as i.i.d. samples and weight them by degree, while others learn sampling distributions.
• Cellular Application: In an interference graph, high-interference neighbors can be sampled with higher probability to prioritize critical relationships.

The explicit management of a node's k-hop neighborhood size during sampling. The receptive field grows exponentially with model depth, so sampling bounds it to a manageable, fixed size.

• Layer-wise Sampling: Each GNN layer independently samples a fixed number of neighbors, preventing combinatorial explosion.
• Subgraph Sampling: Methods like GraphSAINT sample entire subgraphs and perform full GCN on them, implicitly controlling the receptive field.
• Trade-off: A larger sample size captures more structural information but increases compute; a smaller size is faster but may miss critical long-range dependencies.