When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917957815238656 |
|---|---|
| author | Chen, Qian Li, Lei Li, Qian Wu, Jianghua Wang, Akang Sun, Ruoyu Luo, Xiaodong Chang, Tsung-Hui Shi, Qingjiang |
| author_facet | Chen, Qian Li, Lei Li, Qian Wu, Jianghua Wang, Akang Sun, Ruoyu Luo, Xiaodong Chang, Tsung-Hui Shi, Qingjiang |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_14211 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach Chen, Qian Li, Lei Li, Qian Wu, Jianghua Wang, Akang Sun, Ruoyu Luo, Xiaodong Chang, Tsung-Hui Shi, Qingjiang Machine Learning Optimization and Control 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. |
| title | When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach |
| topic | Machine Learning Optimization and Control |
| url | https://arxiv.org/abs/2501.14211 |