Research map / Graph learning / GNN architectures
When GNNs meet symmetry in ILPs: an orbit-based feature augmentation approach
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that GNNs with permutation equivariance/invariance cannot distinguish symmetric ILP variables, and proposes orbit-based random feature augmentation (sampling per orbit from a discrete uniform set) guided by three principles, improving top-m% error and training efficiency on BPP, BIP, and SMSP.
Problem
Classic GNNs predicting ILP solutions cannot distinguish symmetric (same-orbit) variables, so their predictions for symmetric variables are identical and can be wrong.
Approach
Augment variable-node features with random values sampled per orbit from a discrete uniform set of size equal to the orbit cardinality (and an Orbit+ variant reusing samples across orbits with matching column structure), guided by distinguishability, augmentation parsimony, and isomorphic consistency; combined with SymILO to adjust labels.
Key results
- On SMSP, Orbit+ reduces Top-30% error from 34.0 (No-Aug) and 19.3 (Position) to 0.0, and Top-50% from 35.2 (Position) to 1.0.
- On BIP at Top-50%, Orbit+ achieves 5.5 versus 13.4 for Position.
- Orbit+ reaches minimum validation loss in about 20 epochs on BPP and BIP while Uniform and Position need 30-40 epochs.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace Position augmentation with Orbit+ | GNN solution prediction · BPP | Top-90% error: 5.6 -> 4.3 | Helped |
| Replace Position augmentation with Orbit+ | GNN solution prediction · BIP | Top-50% error: 13.4 -> 5.5 | Helped |
| Replace Position augmentation with Orbit+ | GNN solution prediction · SMSP | Top-50% error: 35.2 -> 1.0 | Helped |
| Use Orbit+ instead of Orbit augmentation (ablation) | GNN solution prediction · BPP | Top-70% error: 1.3 -> 0.9 | Helped |
| Use Orbit+ instead of Orbit augmentation (ablation) | GNN solution prediction · BIP | Top-70% error: 39.0 -> 39.4 | Hurt |
| Use Orbit+ instead of Orbit augmentation (ablation) | GNN solution prediction · SMSP | Top-70% error: 17.9 -> 14.9 | Helped |
| Use Orbit+ instead of Orbit augmentation (ablation) | GNN solution prediction · BIP | Top-90% error: 75.7 -> 79.2 | Hurt |
| Use Orbit-based feature augmentation instead of no augmentation | GNN solution prediction · BIP | Top-30% error: 30.4 -> 3.6 | Helped |
| Use Orbit-based feature augmentation instead of no augmentation | GNN solution prediction · SMSP | Top-30% error: 34.0 -> 0.0 | Helped |
| Provide Orbit+ predictions to CPLEX | CPLEX on BIP · BIP, 100s solving time | objective value: 16.9 -> 15.5 | Helped |
| Provide Orbit+ predictions to CPLEX | CPLEX on SMSP · SMSP, 100s solving time | objective value: 37.8 -> 13.7 | Helped |
| Replace Position augmentation with Orbit+ | GNN solution prediction · BIP | constraint violations: 22.12 -> 3.68 | Helped |
Surprising findings
- Uniform continuous noise performs worse than discrete positional IDs in many settings, and the no-augmentation baseline shows very large errors on symmetric instances.
Limitations
- Approach tailored to ILPs with formulation symmetry; unclear transfer to other problem classes.
- Isomorphic consistency principle mainly applies to supervised settings with multiple optimal label choices.
- Relies on SymILO label adjustment to handle conflict samples.
Experimental setup
Datasets: BPP (generated, 500 instances) BIP (ML4CO, 300 instances) SMSP (380 instances)
Benchmarks: BPP BIP SMSP
Metrics: Top-m% error objective value vs CPLEX time constraint violation
Baselines: No-Aug Uniform Position
Builds on: SymILO Bliss Position IDs (Chen et al. ILP GNN) uniform random feature augmentation for GNNs symmetry-breaking sets
Closest papers by meaning
- SymILO: A Symmetry-Aware Learning Framework for Integer Linear Optimization (NeurIPS 2024 · similarity 0.89)
- Beyond the Permutation Symmetry of Transformers: The Role of Rotation for Model Fusion (ICML 2025 · similarity 0.85)
- REVISITING MULTI-PERMUTATION EQUIVARIANCE THROUGH THE LENS OF IRREDUCIBLE REPRESENTATIONS (ICLR 2025 · similarity 0.85)
- A Tale of Two Symmetries: Exploring the Loss Landscape of Equivariant Models (NeurIPS 2025 · similarity 0.85)
- On Making $SE(2)$-Invariant Networks Optimal (NeurIPS 2026 · similarity 0.84)
- Equivariance Everywhere All At Once: A Recipe for Graph Foundation Models (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.