mlsanityData to 7 Oct 2026

Augment with Care: Contrastive Learning for Combinatorial Problems

arXiv 2202.08396 ↗First posted 17 Feb 2022cs.LG cs.AI cs.LOcited by 22

Not on the map. Why?

Abstract (arXiv)

Supervised learning can improve the design of state-of-the-art solvers for combinatorial problems, but labelling large numbers of combinatorial instances is often impractical due to exponential worst-case complexity. Inspired by the recent success of contrastive pre-training for images, we conduct a scientific study of the effect of augmentation design on contrastive pre-training for the Boolean satisfiability problem. While typical graph contrastive pre-training uses label-agnostic augmentations, our key insight is that many combinatorial problems have well-studied invariances, which allow for the design of label-preserving augmentations. We find that label-preserving augmentations are critical for the success of contrastive pre-training. We show that our representations are able to achieve comparable test accuracy to fully-supervised learning while using only 1% of the labels. We also demonstrate that our representations are more transferable to larger problems from unseen domains. Our code is available at https://github.com/h4duan/contrastive-sat.

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 31 of its 45 references that are in the map. First posted on arXiv 17 Feb 2022.

Builds on

31 of 45 references.

References · 31

  1. 2020A Simple Framework for Contrastive Learning of Visual Representationscited by 11,979
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  3. 2019Momentum Contrast for Unsupervised Visual Representation Learningcited by 7,482
  4. 2020Improved Baselines with Momentum Contrastive Learningcited by 2,282
  5. 2020Graph Contrastive Learning with Augmentationscited by 1,203
  6. 2021VICReg: Variance-Invariance-Covariance Regularization for Self-Supervised Learningcited by 1,013
  7. 2020Contrastive Multi-View Representation Learning on Graphscited by 651
  8. 2018Attention, Learn to Solve Routing Problems!cited by 646
  9. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  10. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  11. 2020Deep Graph Contrastive Representation Learningcited by 535
  12. 2019A Theoretical Analysis of Contrastive Unsupervised Representation Learningcited by 530
19 more
  1. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
  2. 2021Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Losscited by 311
  3. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  4. 2019An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problemcited by 265
  5. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
  6. 2020Solving Mixed Integer Programs Using Neural Networkscited by 178
  7. 2020Contrastive learning, multi-view redundancy, and linear modelscited by 146
  8. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  9. 2019Guiding High-Performance SAT Solvers with Unsat-Core Predictionscited by 61
  10. 2018Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSPcited by 58
  11. 2021Lossy Compression for Lossless Predictioncited by 51
  12. 2019Graph Neural Networks for Maximum Constraint Satisfactioncited by 46
  13. 2020Transfer Learning or Self-supervised Learning? A Tale of Two Pretraining Paradigmscited by 23
  14. 2018Learning Heuristics for Quantified Boolean Formulas through Deep Reinforcement Learningcited by 15
  15. 2019PDP: A General Neural Framework for Learning Constraint Satisfaction Solverscited by 14
  16. 2019Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?cited by 10
  17. 2020Learning Branching Heuristics for Propositional Model Countingcited by 9
  18. 2014Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Covercited by 8
  19. 2020CDCL(Crypto) SAT Solvers for Cryptanalysiscited by 2

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 4; 2023: 6; 2024: 3; 2025: 5; 2026: 4.

22 papers.

Sort:

  1. 2023Searching Large Neighborhoods for Integer Linear Programs with Contrastive Learningcited by 37
  2. 2022Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxationcited by 32
  3. 2023G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networkscited by 17
  4. 2023Promoting Generalization for Exact Solvers via Adversarial Instance Augmentationcited by 12
  5. 2022DeepSAT: An EDA-Driven Learning Framework for SATcited by 11
  6. 2022MA-GCL: Model Augmentation Tricks for Graph Contrastive Learningcited by 10
  7. 2023Learning To Dive In Branch And Boundcited by 10
  8. 2023Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimizationcited by 6
  9. 2024Learning Backdoors for Mixed Integer Linear Programs with Contrastive Learningcited by 5
  10. 2024Community-Invariant Graph Contrastive Learningcited by 4
  11. 2024A Unified Framework for Combinatorial Optimization Based on Graph Neural Networkscited by 4
  12. 2023Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approachcited by 3
10 more
  1. 2025Principled Data Augmentation for Learning to Solve Quadratic Programming Problemscited by 2
  2. 2025FORGE: Foundational Optimization Representations from Graph Embeddingscited by 2
  3. 2025Structure based SAT dataset for analysing GNN generalisationcited by 1
  4. 2026Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problemscited by 1
  5. 2022Learning Markov Random Fields for Combinatorial Structures via Sampling through Lov'asz Local Lemmacited by 0
  6. 2025Preference-Based Gradient Estimation for ML-Guided Approximate Combinatorial Optimizationcited by 0
  7. 2025Learning to Solve Weighted Maximum Satisfiability with a Co-Training Architecturecited by 0
  8. 2026Transfer Learning from Foundational Optimization Embeddings to Unsupervised SAT Representationscited by 0
  9. 2026Learning to Solve Compositional Geometry Routing Problemscited by 0
  10. 2026Reformulation-Contrastive Learning for Mixed Integer Programscited by 0