# When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 35 references that are in the map.
- First posted on arXiv 24 Jan 2025.

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

- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Solving Mixed Integer Programs Using Neural Networks](https://mlsanity.com/paper/2012.13349/) (2020)
- [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)
- [Finding Symmetry Breaking Order Parameters with Euclidean Neural Networks](https://mlsanity.com/paper/2007.02005/) (2020)
- [Symmetry Breaking and Equivariant Neural Networks](https://mlsanity.com/paper/2312.09016/) (2023)
- [On Representing Mixed-Integer Linear Programs by Graph Neural Networks](https://mlsanity.com/paper/2210.10759/) (2022)
- [Multiset-Equivariant Set Prediction with Approximate Implicit Differentiation](https://mlsanity.com/paper/2111.12193/) (2021)
- [Equivariant Symmetry Breaking Sets](https://mlsanity.com/paper/2402.02681/) (2024)
- [SymILO: A Symmetry-Aware Learning Framework for Integer Linear Optimization](https://mlsanity.com/paper/2409.19678/) (2024)
- [Learning to Configure Mathematical Programming Solvers by Mathematical Programming](https://mlsanity.com/paper/2401.05041/) (2024)

## Built on by (most cited first, 3 of 3)

- [Feature Augmentation of GNNs for ILPs: Local Uniqueness Suffices](https://mlsanity.com/paper/2509.21000/) (2025)
- [A General Deep Learning Framework for Wireless Resource Allocation under Discrete Constraints](https://mlsanity.com/paper/2603.19322/) (2026)
- [FunL2O: LLM-Guided Feature Function Design for Learning to Optimize](https://mlsanity.com/paper/2607.27389/) (2026)

## Abstract (arXiv)

A common characteristic in integer linear programs (ILPs) is symmetry, allowing variables to be permuted without altering the underlying problem structure. Recently, GNNs have emerged as a promising approach for solving ILPs. However, a significant challenge arises when applying GNNs to ILPs with symmetry: classic GNN architectures struggle to differentiate between symmetric variables, which limits their predictive accuracy. In this work, we investigate the properties of permutation equivariance and invariance in GNNs, particularly in relation to the inherent symmetry of ILP formulations. We reveal that the interaction between these two factors contributes to the difficulty of distinguishing between symmetric variables. To address this challenge, we explore the potential of feature augmentation and propose several guiding principles for constructing augmented features. Building on these principles, we develop an orbit-based augmentation scheme that first groups symmetric variables and then samples augmented features for each group from a discrete uniform distribution. Empirical results demonstrate that our proposed approach significantly enhances both training efficiency and predictive performance.