Low-Latency Relay Selection in NR-V2X Vehicular Communications via Graph Isomorphism Networks with Edge Features

Reliable, low-latency uplink connectivity is a key requirement for C-V2X networks in dense urban environments, where fast channel variations and blockages often degrade direct vehicle-to-infrastructure links. Multi-hop relaying can restore coverage, but relay-link activation under radio, capacity, and routing constraints results in an NP-hard optimisation problem. This problem is typically solved via Mixed-Integer Linear Programming (MILP), whose runtime scales poorly with graph size. The authors address this gap by introducing an edge-aware Learning-to-Optimise framework for real-time relay selection. Each V2X snapshot is modelled as a directed graph: node features encode vehicle state and traffic demand, while edge features capture radio-link capacity. An offline MILP oracle generates optimal relay configurations that supervise a Graph Isomorphism Network with Edge Features (GINE), enabling edge-level relay activation through a single forward pass, with tightly bounded inference latency. To bridge learning and exact optimisation, the paper also proposes a hybrid GINE-Pruned MILP (GP-MILP) strategy in which GINE predictions prune the MILP search space.

The GINE model closely matches MILP decisions at the link level, achieving an accuracy of 0.9589 and an $F_1$-score of 0.9544 on the validation set. End-to-end connectivity gains over a 1-hop MILP baseline are consistent: up to 9.2% with four RSUs and 12% with two RSUs. Inference latency remains tightly bounded, with all evaluated instances completing within 5 ms. The hybrid GP-MILP strategy preserves MILP-equivalent solutions (same objective value) while achieving solver runtimes below 30 ms for more than 98% of the graph instances. These results demonstrate that MILP-grade optimisation is compatible with stringent NR-V2X latency budgets.