  Recent advances in graph neural network architectures and increased
computation power have revolutionized the field of combinatorial optimization
(CO). Among the proposed models for CO problems, Neural Improvement (NI) models
have been particularly successful. However, existing NI approaches are limited
in their applicability to problems where crucial information is encoded in the
edges, as they only consider node features and node-wise positional encodings.
To overcome this limitation, we introduce a novel NI model capable of handling
graph-based problems where information is encoded in the nodes, edges, or both.
The presented model serves as a fundamental component for hill-climbing-based
algorithms that guide the selection of neighborhood operations for each
iteration. Conducted experiments demonstrate that the proposed model can
recommend neighborhood operations that outperform conventional versions for the
Preference Ranking Problem with a performance in the 99th percentile. We also
extend the proposal to two well-known problems: the Traveling Salesman Problem
and the Graph Partitioning Problem, recommending operations in the 98th and
97th percentile, respectively.
