When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach
This addresses a specific bottleneck in using GNNs for ILPs with symmetry, offering an incremental improvement for optimization and machine learning applications.
The paper tackles the challenge of applying Graph Neural Networks (GNNs) to integer linear programs (ILPs) with symmetry, where symmetric variables limit predictive accuracy, and proposes an orbit-based feature augmentation approach that significantly enhances training efficiency and predictive performance.
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.