Interference Graph

An interference graph is typically an undirected graph where an edge between node i and node j signifies mutual, harmful interference. This assumes channel reciprocity: if a transmission from i disrupts reception at j, the reverse is equally true. This symmetry simplifies the graph structure, making it suitable for modeling co-channel interference in Time Division Duplex (TDD) systems.

• Key Assumption: Bidirectional signal degradation.
• Contrast: Directed graphs are used when interference is asymmetric, such as in Frequency Division Duplex (FDD) systems with different uplink/downlink bands.

Edges are rarely binary. They are weighted to represent the severity of interference, typically quantified by the Signal-to-Interference-plus-Noise Ratio (SINR) or path loss between the two nodes. A higher weight indicates a stronger, more disruptive interference coupling.

• Metric Example: Weight = P_tx - PathLoss(d), where d is the distance between nodes.
• Algorithmic Use: Weighted edges enable nuanced graph coloring where a 'color' (resource block) can be reused if the cumulative interference weight remains below a threshold.

Unlike static social networks, an interference graph is a dynamic graph. Its topology changes continuously due to user mobility, fading channels, and varying traffic loads. Nodes (User Equipment) appear and disappear, and edge weights fluctuate with environmental conditions.

• Temporal Granularity: The graph can reconfigure on the order of milliseconds (coherence time of the channel).
• Modeling Requirement: This necessitates Dynamic Graph Neural Networks or Spatiotemporal GNNs that can process time-varying adjacency matrices and node features.

The graph's structure is heavily constrained by Euclidean geometry. Edges are not random; they exist predominantly between physically proximate nodes. The interference range is finite, meaning a node only has edges to other nodes within a specific radius.

• Locality Property: This creates a locally dense but globally sparse graph, ideal for message-passing neural networks that aggregate information from local neighborhoods.
• Contrast: This is distinct from social graphs where long-range 'small-world' connections are common.

The primary algorithmic goal on an interference graph is often modeled as a graph coloring problem. The objective is to assign a 'color' (representing a distinct Resource Block, time slot, or frequency channel) to each node such that no two adjacent nodes share the same color, minimizing the total number of colors used.

• Constraint: Adjacent nodes cannot use the same resource.
• Optimization Variant: Weighted Graph Coloring aims to maximize the sum of weights of non-conflicting assignments, prioritizing high-demand nodes.

Standard graphs model pairwise interference, but a single User Equipment (UE) can be jammed by the cumulative effect of multiple base stations. This is modeled using a hypergraph, where a hyperedge connects three or more nodes to represent a cumulative interference condition.

• Scenario: A UE at a cell edge receives weak signals from three towers; none alone is disruptive, but their sum causes a decoding failure.
• Advanced Model: Hypergraph Neural Networks are required to process these higher-order relationships for accurate resource allocation.