# Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices

arXiv: https://arxiv.org/abs/2509.21000 · HTML: https://mlsanity.com/paper/2509.21000/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 47 references that are in the map.
- First posted on arXiv 25 Sep 2025.

## Builds on (most cited first, 30 of 30)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Benchmarking Graph Neural Networks](https://mlsanity.com/paper/2003.00982/) (2020)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Random Features Strengthen Graph Neural Networks](https://mlsanity.com/paper/2002.03155/) (2020)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [Sign and Basis Invariant Networks for Spectral Graph Representation Learning](https://mlsanity.com/paper/2202.13013/) (2022)
- [Building powerful and equivariant graph neural networks with structural message-passing](https://mlsanity.com/paper/2006.15107/) (2020)
- [Approximation Ratios of Graph Neural Networks for Combinatorial Problems](https://mlsanity.com/paper/1905.10261/) (2019)
- [Learning To Cut By Looking Ahead: Cutting Plane Selection via Imitation Learning](https://mlsanity.com/paper/2206.13414/) (2022)
- [MIP-GNN: A Data-Driven Framework for Guiding Combinatorial Solvers](https://mlsanity.com/paper/2205.14210/) (2022)
- [A GNN-Guided Predict-and-Search Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2302.05636/) (2023)
- [The Machine Learning for Combinatorial Optimization Competition (ML4CO): Results and Insights](https://mlsanity.com/paper/2203.02433/) (2022)
- [On Representing Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2209.12288/) (2022)
- [On the Stability of Expressive Positional Encodings for Graphs](https://mlsanity.com/paper/2310.02579/) (2023)
- [Practical Large-Scale Linear Programming using Primal-Dual Hybrid Gradient](https://mlsanity.com/paper/2106.04756/) (2021)
- [Graph Positional Encoding via Random Feature Propagation](https://mlsanity.com/paper/2303.02918/) (2023)
- [On the Universality of Graph Neural Networks on Large Random Graphs](https://mlsanity.com/paper/2105.13099/) (2021)
- [Learning Efficient Positional Encodings with Graph Neural Networks](https://mlsanity.com/paper/2502.01122/) (2025)
- [On Representing Mixed-Integer Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2210.10759/) (2022)
- [PDHG-Unrolled Learning-to-Optimize Method for Large-Scale Linear Programming](https://mlsanity.com/paper/2406.01908/) (2024)
- [Apollo-MILP: An Alternating Prediction-Correction Neural Solving Framework for Mixed-Integer Linear Programming](https://mlsanity.com/paper/2503.01129/) (2025)
- [Benchmarking Positional Encodings for GNNs and Graph Transformers](https://mlsanity.com/paper/2411.12732/) (2024)
- [SymILO: A Symmetry-Aware Learning Framework for Integer Linear Optimization](https://mlsanity.com/paper/2409.19678/) (2024)
- [Towards Invariance to Node Identifiers in Graph Neural Networks](https://mlsanity.com/paper/2502.13660/) (2025)
- [When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach](https://mlsanity.com/paper/2501.14211/) (2025)
- [On the Utilization of Unique Node Identifiers in Graph Neural Networks](https://mlsanity.com/paper/2411.02271/) (2024)

## Abstract (arXiv)

Integer Linear Programs (ILPs) are central to real-world optimizations but notoriously difficult to solve. Learning to Optimize (L2O) has emerged as a promising paradigm, with Graph Neural Networks (GNNs) serving as the standard backbone. However, standard anonymous GNNs are limited in expressiveness for ILPs, and the common enhancement of augmenting nodes with globally unique identifiers (UIDs) typically introduces spurious correlations that severely harm generalization. To address this tradeoff, we propose a parsimonious Local-UID scheme based on d-hop uniqueness coloring, which ensures identifiers are unique only within each node's d-hop neighborhood. Building on this scheme, we introduce ColorGNN, which incorporates color information via color-conditioned embeddings, and ColorUID, a lightweight feature-level variant. We prove that for d-layer networks, Local-UIDs achieve the expressive power of Global-UIDs while offering stronger generalization. Extensive experiments show that our approach yields substantial and robust gains across ILP benchmarks.