ConRep4CO: Contrastive Representation Learning of Combinatorial Optimization Instances across Types
Authors: Ziao Guo
Yang Li
Shiyue Wang
Junchi Yan
Venue: ICLR 2026 Poster (2026)
Keywords: Combinatorial Optimization
Contrastive Learning
Representation Learning
Primary area: unsupervised, self-supervised, semi-supervised, and supervised representation learning
TL;DR: We propose a paradigm to enhance representation learning for CO via designed contrastive learning across multiple CO problems.

Abstract: Considerable efforts have been devoted to machine learning (ML) for combinatorial optimization (CO) problems, especially on graphs. Compared to the active and well-established research for representation learning of text and vision, etc., it remains under-studied for the representation learning of CO problems, especially across different types. In this paper, we try to fill this gap (especially for NP-complete (NPC) problems, as they, in fact, can be reduced to one another). Our so-called ConRep4CO framework, performs contrastive learning by first transforming CO instances in various original forms into the form of Boolean satisfiability (SAT). This scheme is readily doable, especially for NPC problems, including those practical graph decision problems (GDPs) which are inherently related to their NP-hard optimization versions. Specifically, each positive pair of instances for contrasting consists of an instance in its original form and its corresponding transformed SAT form, while the negative samples are other instances not in correspondence. Extensive experiments on seven GDPs (most of which are NPC) show that ConRep4CO significantly improves the representation quality and generalizability to problem scale. Furthermore, we conduct extensive experiments on NP-hard optimization versions of the GDPs, including MVC, MIS, MC and MDS. The results show that introducing ConRep4CO can yield performance improvements of 61.27%, 32.20%, 36.46%, and 45.29% in objective value gaps compared to problem-specific baselines, highlighting the potential of ConRep4CO as a unified pre-training paradigm for CO problems.

Published as a conference paper at ICLR 2026
CONREP4CO: CONTRASTIVE REPRESENTATION LEARNING OF COMBINATORIAL OPTIMIZATION IN-
STANCES ACROSS TYPES
Ziao Guo', Yang Li Shiyue W Junchi Yan
School of Computer Science & School of Artificial Intelligence, Shanghai Jiao Tong University
2 Shanghai Innovation Institute
s School of Mathematical Sciences, Key Laboratory of MEA,
and Shanghai Key Laboratory of PMMP, East China Normal University [ziac. guc, yanglily, yanj jt. cn wangshiyue@stu.esm edu, cn
ABSTRACT
Considerable efforts have been devoted to machine learning (ML) for combinatorial optimization (CO) problems, especially on graphs. Compared to the active and well-established research for representation learning of text and vision, etc., it remains under-studied for the representation learning of CO problems, especially across different types. In this paper, we try to fill this gap (especially for NP- complete (NPC) problems, as they, in fact, can be reduced to one another). Our so-called ConRep4CO framework, performs contrastive learning by first transform- ing CO instances in various original forms into the form of Boolean satisfiability (SAT). This scheme is readily doable, especially for NPC problems, including those practical graph decision problems (GDPs) which are inherently related to their NP-hard optimization versions. Specifically, each positive pair of instances for contrasting consists of an instance in its original form and its corresponding transformed SAT form, while the negative samples are other instances not in cor- respondence. Extensive experiments on seven GDPs (most of which are NPC) show that ConRep4CO significantly improves representation quality and gen- eralizability to problem scale. Furthermore, conduct extensive experiments on NP-hard optimization versions of the GDPs, including MVC, MIS, MC and MDS. The results show that introducing ConRep4CO can yield performance im- provements of 61.27% %, 32.20% % 36.46% %, and 45.29 % in objective value gaps compared problem-specific baselines, highlighting the potential of ConRep4CO as unified pre-training paradigm for CO problems. Source code is available: https: //t:://gttttta com/ htt//hhnnkkn SJT0/CanRep4CO htttm//hh.......---//////eeee
INTRODUCTION
Combinatorial optimization (CO) has been attracting wide interest for its practical importance from logistics [49 to finance [44] Compared with the vector matrix-like data, e.g., image, text, and the associated short-range tasks, e.g., classification and regression, the CO problems are inherently more challenging due to their discrete and non- non-convex nature with complex constraints, which often leads to NP-complete (NPC) or even NP-hard complexity [29].
there still exist many limitations: compared to the well-developed learning approaches for representation text [43) and vision [58). the tailored representation learning framework for CO problems remains under- explored. In fact, existing ML4CO literature in technique is mainly tailored to a single problem type, e.g., TSP (51) graph matching [59 62. which may become bottleneck for their ability in the sense of not leveraging the potential cross- domain learning. This gap is especially pronounced with the fast
Despite the recent extensive research on machine learning (ML) for CO 3 17
"Correspondence author. This work was partly supported by National Natural Science Foundation of China (92370201, 625B21 19) and Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China, JYB2025XDXM411.

---

Published as a conference paper at ICLR 2026
development of multi modaiimy joint representation learning out of the CO area, e.g. CLIP 446 for both text and image.
In this paper, we try to fill the above gap by advancing the pre-training representation learning paradigm for CO problems, particularly by selecting various NPC problems, mainly including the so-called graph decision problems (GDPs), as pre-training tasks The hope is that the model trained jointly on various problem types will exhibit better expressiveness and generalization ability. To achieve our objective, we particularly leverage an important fact: NPC problems can be reduced to one another, and can all be transformed into Boolean satisfibiility (SAT), making SAT a common form bridge different original forms. This also suggests that they inherently share a latent structure worth being exploited for effective representations and ultimately for the goal of high-quality problem solving. Furthermore, there a strong connection between GDPs and their optimization versions, which are more practical in real-world applications. Most CO problems can be converted into their decision versions by adding a target value. Prior results (28) have also established polynomial-time equivalences between decision and optimization for key CO problems. We select GDPs pretraining tasks to learn representations, maintaining the potential to leverage the learned representations to enhance general CO problem-solving beyond GDPs.
Specifically, we develop a contrastive rre-training learning paradigm, ConRep4CO, tailored to CO problems beyond the vanilla version for images [10]. The pre- mre-training is performed by contrasting problem instances, where the positive sample is defined as a pair of a vanilla GDP instance with its corresponding SAT form, while the negative sample is pair that is not in correspondence. Also, decision loss is applied to guide each model to effectively learn the feature representations of the respective instances and capture the unique characteristics of its assigned problem domain. Extensive experiments are conducted to evaluate the effectiveness of the ConRep4CO paradigm, comprising two parts: 1) representation evaluation, and 2) enhancement of CO problem-solving For 1), since there is no universal metric for CO representation evaluation, in the context of our discussion, we use the accuracy of solving GDPs as a measure. We first assess the representation quality and generalizability to problem scale by solving GDPs on both pre-training identical distribution and more difficult instances. We also evaluate the cross-domain generalizability by the solving performance on unseen GDP domains. For 2), we incorporate ConRep4CO into the training of problem-specific neural solvers for minimum vertex cover (MVC), maximum independent set (MIS), maximum clique (MC), and minimum dominating set (MDS). The neural solvers enhanced by ConRep4CO consistently show significant performance improvements, demonstrating the practical applicability of ConRep4CO beyond GDPs The highlights of the paper are as follows.
1) We try to advance the frontier of representation learning, beyond the classic instance forms, e.g., text/vision, by proposing ConRep4CO, novel contrastive pre-training paradigm to learn general representations across different CO problems with complex discrete constraints and variables.
2) We leverage the SAT form to build the positiveenegatiie pairs for our carefully designed contrastive learning scheme, based on the fact that GDPs (i.e., NPC problems) can be reduced into the SAT form. merit is that our contrastive approach augmentation free. as CO instance augmentation itself is a notoriously challenging task due to unique problem structures. This is in contrast to the trivial image augmentation as done contrast to vision problems, which, in fact, is also a bottleneck for directly reusing the contrastive learning approaches in vision to combinatorial tasks.
3) Our method learns the representation across different types beyond single type. Such a unified paradigm facilitates representation learning through knowledge transfer among problem domains and mutual enhancement. Extensive experiments show that ConRep4CO not only improves representation quality but also significantly enhances problem-solving for various CO problems.
2 RELATED WORK
Machine Learning for CO. The application of machine learning to graph-based CO problems has a rich history, with recent research demonstrating substantial advancements in this domain 30: 3 41 These problems span a wide range of domains, including classical combinatorial optimization
tasks (c.g., MILP 20 74), SAT 76 34
well as structured generation problems such as
'GDPs are the decision versions of general NP- CO problems, such as the k-independent set problem corresponding to the maximum independent set (MIS) problem, and encapsulate the core challenges of CO. From the 21 NP-complete problems identified by 29 10 GDPs, highlighting their fundamental importance.
2

---

Published as a conference paper at ICLR 2026
molecule generation [71:68 and protein docking [67]. Most ML-based approaches for CO follow
a two-stage framework: (1) Graph representation learning, where graph instances are embedded
into low-dimensional vector spaces through graph neural networks (GNNs) (23 6
8
70
39] and
(2) The utilization of these learned representations to solve CO problems 27 45
61
38
336 35 (37 9 Our ConRep4CO paradigm focuses on enhancing the first stage by proposing
more general training approach. While previous work has largely focused on designing network architectures B1 22 54 60), our approach emphasizes the development of training paradigm that leverages information from multiple problem types. There are also recent works on training with different types of CO, e.g., GOAL [12], UniCO [42 and MAB-MTL [57]. However, these works are orthogonal to ours as they directly follow the multi-task paradigm without contrastive pre-training.
Graph Contrastive Learning. Many graph contrastive frameworks rely on graph augmentations, which can be broadly categorized into two types: (1) structural perturbations, such as node dropping. edge sampling, and graph diffusion [3 26]: and (2) feature perturbations, such as adding noise
to node features (24]. These augmentation strategies have demonstrated effectiveness across
range of tasks, from graph-level representations 224 73 to node-level representations [56] 53], Our
ConRep4CO paradigm moves beyond traditional graph augmentations by contrasting graph instances across multiple problem types. Instead of solely relying on structural and feature perturbations, ConRep4CO leverages the inherent characteristics of different CO problems, enabling the model to capture higher-level characteristics. Note that our approach is augmentation-free We believe this nice property as graph augmentation itself is a notoriously complex problem and much more complex than that on image data, as done in the vanilla contrastive paradigm SimCLR [10], where the augmented positive samples are generated by adding perturbations on the image e.g.. cropping, translating, warping etc.
3 METHODOLOGY
We present details of our Contrastive Representation alignment and learning for Combinatorial Optimization (ConRep4CO) paradigm. We start by introducing the preliminary background on representations of graph decision problems and SAT in Sec. 3.T Then, we elaborate on our approach to aligning multiple problem types in Sec. 3.2] Finally, introduce the overall pipeline and implementation of our ConRep4COO as well as some important training details in Sec. 3.3
3.1 PRELIMINARIES
Graph decision problem (GDP), As a fundamental computational challenge, its goal is to determine the existence of specific properties within a given graph. These properties can vary, from identifying whether a graph contains particular substructure, e.g. clique or cycle, to assessing whether it meets conditions like connectivity or planarity. Graph decision problems are typically the decision versions of general NP-hard CO problems, e.g., the k- k-independent set problem corresponding to the maximum independent set problem, and the k-vertex cover problem corresponding to the minimum vertex cover problem, making them essential in the context of NPC problems. In particular, ML-based models can be effectively utilized to address GDPs. The objective is to learn a representation of a specific GDP type and use it predict decisions based on the input graph. These representations can be understood as mappings that translate the structural properties of the input graphs into corresponding decisions, thereby capturing the underlying patterns required for decision-making in GDPs
SAT problem. A Boolean formula in propositional logic consists of Boolean variables connected by logical operators "and" (A), "or" (V), and "not" (-). A literal, denoted as 4, is defined as either a variable or its negation, and clause Cj is represented as a disjunction of n literals, V 4. A Boolean formula is in Conjunctive Normal Form (CNF) if it is expressed as a conjunction of clauses Ay= Cj. Given a CNF formula, the Boolean Satisfiability Problem (SAT) aims to determine whether there exists an assignment x of Boolean values to its variables under which the formula evaluates to true. such an assignment и exists, the formula is called satisfiable, where π is called a satisfying assignment; otherwise, it is unsatisfiable. Graph representations play an important role in analyzing SAT formulas, with four common primary forms [4] the literal-clause graph (LCG), literal-incidence graph (LIG), variable-clause graph (VCG), and variable-incident bipartite graph consisting of two types of Mides--lteralss and clauses where an edge between a literal and clause signifies the occurrence of that literal in the clause. LIG, in contrast, consists
graph (VIG). The LCG is
"The CO instance can often be represented as certain graph, e.g. a bipartite graph in 16
3

---

Published as a conference paper at ICLR 2026
Case Quiput
Graph Decision
Edec
SAT Graph
Matcchnn
Representzatio Extractor
Lonn.
Cak
SAT Culput Module
K-clese
Quipui Module
Representatin
beun
Representation Extractor
Extractor
Caka
SAT Model
color
Output Module
Graph Model
Representation Extractor
Data Flow
Loss Flow
Figure 3: Overview of ConRep4CO with the proposed contrastive learning scheme. Given instances from multiple GDP types and their corresponding SAT graphs, graph model is trained for each GDP type alongside a SAT model. Each model is composed of a Representation Extractor and an Output Module. The input graphs are processed by the Representation Extractor generate instance-level representations, which are subsequently fed into the Output Module to produce the final decisions for each instance. The decision loss is applied individually to each model, while the contrastive loss is applied to each graph model. All contrastive losses are applied to the SAT model.
solely of literal nodes, with edges representing the co-occurrence of two literals within the same clause. VCG and VIG are derived from LCG and LIG by merging each literal with its negation.
3.2 MODAL ALIGNMENT
We aim to enhance the learned represen- tations of graph instances across a diverse range of GDPs by incorporating and syn- thesizing information from multiple GDP types. Specifically, we conceptualize each GDP type as a distinct problem modality. By adopting this multi-modal perspective, we explore the potential for cross-modal information- passong schemes. Note that the term 'modality" is not strictly defined. hope to express that the problems rep- resent different forms of higher-level un- derlying difficulty and share a common underlying structure.
Segh Peteer
OUT Tomale
Gemva
Figure 1: Transformation process from various GDP
instances to the unified LCG representation of SAT.
Significant challenges arise due the in- herent disparities and structural gaps be- tween different GDP types, often exhibit- ing varying graph topologies and problem characteristics. To fill this gap, we propose introducing SAT as a unified intermediary modality. The core concept involves trans- forming each GDP instance into its cor- responding CNF formula, effectively con- verting it into SAT instance. Once trans- formed, we construct SAT-based graph representation for each instance, ensuring that all GDP instances, regardless of their original modalities, are standardized into an equivalent SAT graph representation. This transformation allows for uniform modeling across disparate problem types. Fig- [elariiiss approach modal transformation.
K-iqqu
An example of the contrastive learning pro- cess, where 'Pos. pair' and 'Neg. pair' refer to positive and negative pairs, respectively. A similar process ap- plies to other modalities with SAT.
Figure 2:
4

---

Published as a conference paper at ICLR 2026
After this transformation, we leverage contrastive learning to align the different modalities. Specifi- cally, each GDP instance and its corresponding SAT instance form a positive pair to train both the SAT and graph models, while SAT instances derived from other GDP instances within the same GDP type serve as negative samples for the graph model. Similarly, other GDP instances within the same illustrates
type serve negative samples for the SAT model. Fig. FiluSsaatts the contrastive learning process. The SAT modality, in turn, aligns with all other modalities. The goal is to facilitate information transfer across GDP modalities while preserving the distinct characteristics of each problem type.
3.3
CONREP4CO PARADIGM
3.3.1
OVERVIEW
In this section, we provide a detailed introduction to ConRep4CO. Fig. exxibiit an overview.
Consider types of GDPs, denoted PI, ......, Pr., , G1 Gg...,, G.. For simplicity, assume that each graph set G, contains m graphs, i.c. G, = (G ......... 9.Th }, for = 1, 2, ...... ........ The objective is to solve problem P. graphs in G. In total, there are m n instances, denoted by F (Pi, where 1,2, ................................ n and j 2, 2,2,..... ................................ m.
along with corresponding graph sets
We first transform each of the m x n GDP instances into CNE, thereby generating their corresponding SAT graphs, i... (P.,g)) + By. where B is the constructed SAT graph.
Then, we develop distinct graph models, MI...., Ml, each for one GDP type, and one unified SAT model Maat to address the problem space. Both the graph models and the SAT model are structured around two key components: the Representation Extractor and the Output Module. The Represen- tation Extractor, implemented as GNN-based network, is responsible for learning and extracting representations from the input graph instances, whether derived from GDP or SAT transformations. The Output Module, implemented as an MLP, then utilizes these learned representations to produce task-specific outputs, thereby enabling the resolution of the given problem.
In training, we jointly train the (n (n+11) 1) models corresponding to the GDP modalities along with the SAT modality. The supervision is derived from two parts: the decision loss and the contrastive loss. The decision loss is applied independently to each model, guiding the encoder to learn domain- specific feature representations. Mcanwhile, contrastive loss is employed to facilitate feature fusion and message passing across different modalities, enabling the models to leverage complementary information from other problem domains. For training sample and label preparation, one cost comes from generating the corresponding SAT form for each instance, which requires a polynomial complexity. While this cost is negligible for computing labels for the training instances.
3.3.2 Loss FUNCTION
We introduce the definition and computation of the two key loss functions used in ConRep4CO.
Decision Loss Laec.
defined as a binary cross-entropy loss, which can be computed by:
Ldce
Σ {- log(d.")) - (1 - d!') log(l - )
BaBath
where yout denotes the output decision of the models, and del refers to the ground truth label. For each model, the decision loss is independently computed and applied.
Contrastive Loss Lcon+ Here we adopt the classic contrastive objective as widely used in litera- ture [10] 25 52,, facilitate the alignment between the GDP and SAT modalities, Taking P, and the SAT modality as an example, Leon is formulated as:
exp(sim(fe), F (/T))/T)
exp(sim(f*, Fd )/T) ΣE=1 lifs exp(sim (Fh, 1t )/T)
Leean
log
j=1 Liz exp (xppssi(ff, (T) log
where N represents the number of instance pairs in batch, f. denotes the normalized representation of the i-th instance in the P., modality, and f... denotes the normalized representation of the corresponding instance in the SAT modality, derived from the i-th instance of the P,, modality. The parameter is the temperature scalar, and T is indicator function. The function sim(:;) measures
r r.r, Tr.
the cosine similarity between two representations, defined as sim(r,,
5

---

Published as a conference paper at ICLR 2026
Table 1: GDP solving accuracy (%) with confidence intervals (a = 0.05) of the graph models trained on an identical distribution, measuring the quality of learned representations. 'SAT Back.' refers to SAT model backbone, and 'Graph Back.' denotes graph model backbone. The 'Overall' column
represents the average accuracy across all datasets.
Graph Back
Bifiiallyy
Model
F-Cligu
A-Venon
I-Indhtt
Matching
Autmnoph
Overil
Gmmh Model
71.400
SK.50.
60 60.3606
16.4002
625100
71,24012
6564044
06.5
bany
Grugh CodeeiCo
79.360.3
02.0g9.1
67.3602
90.28..1
07.5el15
71.720.3
65.48.33
719
OCN
Grgph Mode)
63.2.0.5
62.220.2
59930.4
79.60.2
61.1an.2
70669.
63.3x014
65.7
Matium
Grghh MudpliCCuReppCCO
71.360.5
64.629.2
63.360.3
$2.2602
64.8el.1
72868.4
65.728.4
69.1
Gmghh Mode) Gnggh ModosCCu
77.x0.3
60.300
62.7a6.3
63660.3
Fasy
79.360.3
61.1e03
63.00.3
8966001
67.7
71.10.3
64/61022
71.2
LCGNGCN
Gnggh Mude) Gmph ConeeiCCo
63.2s0.
62.2s0.2
61.1.0.
63.3103
65.7
Medium
71,569,3
65,4:04
634400
64,0003
72,3603
64.40.44
69.0
Grugh Mode! Graph Model-CosRepicC
7700m0.3
58.5
60.36044
56.12022
02.72033
71226.2
63/669.
65.5
780600
6M
62990.3
$8380.1
66.291.3
71,1803
64.260.2
70.3
VCGHGCN
Medium
Gruph Mode! Gmph MuleisCn
70.60.3
63.2204
62.240.2
64.20.44
599393
630102
79.6933
62.11..3
71846.3
7066334
64/088.4
63.389.3
65.7
6Kn
Lasy
Grugh Mode)
Ongh Modee-CCn
30
9333611
618403
58249.3
53.44.44
GraphSACRR
Ginph Model
56500.2
360880
5523603
5822603
5688602
56.8
Medrum
Gmph Model Monel-CCn
728+0.3
641104
66.740.2
88.9002
76.140.
71,246.4
64840.3
70,9
Groph Mode! Gmmph Moste-CCC
76 2e0.3
06.281
91 9166991
67.95833
05.78922
0177803
70.1
Basy
77.360.3
61,9
69.760.3
937462
714e94
70L366.
6172002
72.3
ATT+NeerSSAT
PUN
Gimph Modk)
71.4004
62.8:033
66.7102
$30103
68.1:8.1
55.8004
5041033
65.7
Melium
Gmgh MudassCCRRppCCC
72.0x0.3
63.3:0.4
660010.
$6.48.2
67.2.0.3
708:0.3
63.3:9.4
69.9
(ngph Model
82.4+033
73.2-0.1
65.510
76.4-0.3
76.3
Fony
Gnggh MusessCnnRepCCOO
88.5102
66.1003
LCG
GmplaiP
Gmmhh Model
70740.
62.50011
668402
86 9403
69.466.3
62,404
08.2
Medium
Grigh ModeliCosReepCCO
71.7g0.3
72.9=9.4
$1880.3
85.620.2
73.0g9.3
57.260.4
63.260.
72.2
Each GDP modality is trained using the contrastive loss with the SAT modality, allowing independent optimization for each GDP model. In parallel, the SAT model is optimized using the average contrastive losses computed across all GDP modalities, ensuring effective alignment.
3.3.3 TRAINING DETAILS
We adopt a warm start strategy ensure the models learn robust representations. During the initial training phase, only the decision loss is utilized, while the contrastive loss is temporarily disabled. This phase allows the models to focus on learning meaningful task-specific representations based solely on the decision outcomes. Our insight is to provide a stable foundation for representation learning before introducing the more complex cross-modal alignment enforced by contrastive loss.
After the warm start phase, we introduce the contrastive loss alongside the decision loss. To balance the influence of these two losses, we introduce a parameter 8, which controls the relative weight of the decision loss during the joint training phase.
3.3.4 INCORPORATING CONREP4CO INTO CROBLEM-SPECIEEE NEURAL SOLVERS
Despite selecting GDPs as the pre-training tasks, ConRep4CO is not restricted to only GDP solving in practical applications. ConRep4CO can be incorporated into problem-specific neural solvers to enhance the learned representation and ultimately improve problem-solving. Suppose one has pre-trained a SAT model (and graph models) using ConRep4CO. The following steps can be taken:
1) Convert the decision version instances of the neural solver's corresponding problem domain into CNFs. This can typically be implemented through off-the-shelf tools, such as CNFGen [33], and requires polynomial complexity, which is negligible for computing labels for the training instances.
2) Use the loss function defined in Sec. 3.3.2 to perform contrastive learning between the neural solver model and the pre-trained SAT model. The neural solver's 's architecture may need minor adjustments, such as adding an output module, while the parameters of the SAT model are fixed, as the pre-trained SAT model already contains unified representations for various problems.
3) Fine-tune the neural solver in the original problem domain to adapt the learned representations.
When incorporating ConRep4CO into different solvers, full retraining is unnecessary the pre- trained SAT model is reusable, requiring only an efficient alignment procedure. Consequently the need for training multiple models arises infrequently, significantly enhancing practical applicability.

---

Published as a conference paper at ICLR 2026
Table 2: GDP solving accuracy (%) with confidence intervals (a 0.05) of the graph models on the hard datasets, measuring the generalizability of learned representations. 'SAT Back.' refers to SAT model backbone, and 'Graph Back.' denotes graph model backbone. The terms 'Easy" and 'Medium' in parentheses indicate the difficulty level of the datasets used for training. The 'Overall' column represents the average accuracy across all datasets.
SAT Dack.
Graph Back
Model
A Clqqe
& Domset
Vercov
CCllr
J: Inddet
Matching
Ausomerph
Overall
Graph Model (Facy)
$4.5+0.2
50040.1
S00ee01
S4.6404
50.5e0.2
66-440-3
63.1
55.6
Graph MoskkbCooiRppCCD (Pang)
$7.11111
50.110.11
50.0e0.1
68.5tL.3
50.360.2
67.9584
63640.22
57.1
LOA
GCN
Graph Model (Medium)
57. 1
562300.1
50,00.1
03.50.5
53.140.5
68.3403
632260
Graph MoskH&CooRepCCC (Malium)
S788112
56.560.1
57.7.6.3
67.64885
56.500.
7000002
65.30.2
61.6
Graph Model (Easy)
50
50.560.
Graph CoaeeeCC (Baay)
52.5
500200
53,9203
55.72022
49.9003
0866822
63.120.3
56.3
LORHGCN
Graph (Medium)
5634403
63.240.3
Graph Moskd4CooReppCC) (Modiums
$7.9603
58960.2
55,240.3
Graph Model (Eaey)
54.5
50:00010
50.0s00
54.620.4
50.5.002
66.450.3
63.1004
Graph Model CoulppiCO (Easy)
53.12112
50,0000
50,06000
55.42013
49.600.4
63.460.3
VOG+GCN
CCN
Graph Model (Medium) Graph ModeelC2llepiCD (Medium))
57 1602
5622603
50,000
63.2403
55.150.
66.3604
6322602
56.3
87.760.4
60.560.3
57.760.3
64.8602
53460.3
09.00.3
64,360.3
61.1
Graph Model (Eaxy) Graph CodkstCC (Easy)
50.3810.3
45, 1s0
50
50.5u
57.800
55.740.3
$2.0
52.9
59.9204
55.92044
5M.56633
67.9883
5M.6
LOG+NNurSAA
GnghSAGF
Graph Model (Medium) Graph Medel-CooRRppCC (Medium))
509904
57.3602
50 250.
48 18996.3
35
53.7
$9.760.3
59,560.3
60.340.
70.244.4
564104
68446.2
64220.3
62.7
Graph Modkl (Eaxy) Graph Moskk+CaaRqpiCCO (Basy)
54 2+113
39.3+11.
50, Se0.4
63.1
66.34044
59.3
54.62112
59
59.920.3
63.3stu4
55.120.3
66.788.
61.020.4
61.1
LOG+NNuwSAA
PGN
Graph Model (Mediuum) Graph Medel+CoRPppCC (Medium)
60.
58610.3
59 7202
09:120.
55.9.044
67.1292
63.520.3
62.0
61.260.3
58.940.
68.766.
69.7402
58.129.3
07.540.3
63:3502
62.8
Grapi (Fwey)
59661111
500000
40:9HL1
50,00000
53.5+0.3
680104
57.640.
Graph Mosks&CsoRRp4CCO (Basy)
39.3:11.
50.7s0.1
60.900.4
59.6e10.
53.56004
58.900.
59.5
LOG+NeursAAT
GraphGiPS
Graph (Mediium)
55 240.
68.3604
63.060.3
Graph CodeetCo (Mediuss)
638860
60.860.3
77.9.0.3
68.940.3
65.750.
6011802
61.400.3
Table 3: GDP solving accuracy (%) with confidence intervals (a = 0.05) of the graph models on Easy datasets. The 'Overall' column represents the average accuracy across all datasets.
Model
k- k-Clique
& K-Domset
V-Vercox
k-Color
K-Indset
Matching
Automorph
Overall
Graph Model
76.240.2
58.4+0.4
66.440.2
91.640.5
67.940.3
68.7.
61.740.2
70.1
Graph Model-Unseen
76.9+0.3
61.0+0.1
70.1
93.4+0.4
68.6+0.3
69.7s0.1
61.740.2
71.6
4 EXPERIMENTS
4.1 EXPERIMENTAL SETUP
Datasets. To evaluate the broad applicability of our approach, we select seven GDPs: k- k-Clique, t-Dominating Set (k-Domset), k- &-Vertex Cover (A- Vercov), k-Coloring (k-Collor) k-Independent Set (I=Ind Perfect Matching (Matching), and Graph Automorphism (Automorph). For each problem, we randomly generate graph instances that adhere to a distribution specific to the problem. To ensure comprehensive and rigorous evaluation, we create datasets with varying levels of difficulty, categorized as easy, medium, and hard, based on the size and distribution of the generated graphs. For each easy and medium dataset, we generate 160,000 instances for training, 20,000 instances for validation, and 20,000 instances for testing. For each hard dataset, we only produce 20,000 instances for testing to evaluate the generalizability of the learned representations. Additionally, we ensure an equal distribution of labels, with 50% of instances labeled as satisfiable (1) and 50% as unsatisfiable (0) across the training, validation, and test sets. The graph instances were transformed into CNF using generators from CNFGen [33. Furthermore, we evaluate the effectiveness of ConRep4CO in enhancing CO problem-sol solving on four practical CO problems: minimum vertex cover (MVC), maximum independent set (MIS), maximum clique (MC), and minimum dominating set (MDS). For MVC, we follow the setting in [72], using Erdós Rényi (ER) graphs with three scales, containing approximately 50 to 100, 100 200, and 400 to 500 vertices, respectively. For MIS, MC, and MDS, we follow the setting in 75), using RB graphs (69) for MIS and MC, and BA graphs [2] for MDS, generating two scales of datasets with approximately 200 to 300 and 800 to 1200 vertices. respectively. Please refer to Appendix C for more details about the dataset description and statistics.
Erdós-Rényi
Graph/SAT Model Backbones. We implement multiple GNN backbones for the Representation Extractor in both graph and SAT models. For the graph models, we adopt two widely used backbones, GCN BT and GraphSAGE [2], and two advanced backbones with stronger representational capacity, PGN 55 and GraphGPS 47 For the SAT model, we implement AT and GCN architecture
7

---

Published as a conference paper at ICLR 2026
Table 4: Performance MVC. 'OBJ' refers the average objective value, where lower is better for
MVC. 'Optimal' represents the best-known solution obtained using Gurobi [21].
OpIGNN
OptCNNV.CoRRe4400
GCNN
GCNN:ConRop4CO
Graph
Optimal
OBJ
OB]
gain
OBJ
OBJ
gain
ER(50,100)
54,62
55.87
93.60%
55.34
0.72
55.17
0.55
2366%
ER(100.2000
122.79
126.04
3.25
124.37
1.58
51.40%
128.29
5.50
126.75
3,96
28.00%
ER(400,500)
417.42
420.51
3.09
419.31
1,89
38.83%
443.43
26.01
436.77
19.35
25.61%
avg. gain
61.27%
25.74%
Table 5: Performance on MIS, MC, and MDS. 'OBJ' refers to the average objective value, where higher is better for MIS and MC, and lower is better for MDS. 'Optimal' denotes the best-known solution, obtained using KAMIS [2 for MIS and Gurobi [11] for MC and MDS.
GelowNet
GFlowNet-ComRepp4O
Problem Type
Graph
Optinal
OBI
gaPas
OBJ
gaPass
gain
avg. gain
RB(200,30D)
20.10
19.18
0.92
19.56
0.54
41.30%
MIST
RB(800.1200)
43.15
37.48
5.67
38.79
4.36
23.10%
32.20%
RB(200,300)
19.05
16.24
2.81
1.58
43.77%
MCT
RB(500,1200)
33,89
31.42
2.47
32,14
1.75
29.15
36.46%
BA(200.200)
27.89
28.61
0.72
28.19
0.30
58.33%
MDSL
BA(800,1200)
103.80
110.28
6.48
108.19
4.39
32.25
45.29%
specifically tailored for SAT graphs. Moreover, we employ both LCG and VCG as SAT graph representations. Please refer to Appendix(Dfor more details.
Tasks. The evaluation tasks can be divided into two parts: 1) Representation evaluation, measured by the performance of graph models on the GDP-solving task, focusing on how the learned repre- sentations can accurately determine the solution for each specific problem type. The GDP-solving performance on more difficult instances and unseen GDP domains is used assess both the in-domain (problem scale) and cross- dosainn generalizability of the learned representations. 2) Enhancement of CO problem-solving measured by the performance on four CO problems-MVC, MIS, MC, and MDS when incorporating ConRep4CO into problem-specific neural solvers, as described in Sec. 3.3.4
Baselines. For 1) representation evaluation, to ensure fair comparison, we establish baselines for the graph models trained by ConRep4CO by keeping the architectures identical while modifying only the training procedures. Each baseline graph model is trained independently its corresponding dataset. For 2) enhancement of CO problem-solving. OptGNN and GCNN from [72) are used as baseline neural solvers for MVC, while GFlowNet from (75) serves the baseline neural solver for MIS, MC, and MDS. These models are trained using the methods described in their respective papers and compared those incorporating ConRep4CO as outlined in Sec. 3.3.4
4.2 REPRESENTATION EVALUATION
4.2.
REPRESENTATION QUALITY EVALUATION
We evaluate the quality of the learned representations by comparing the accuracy of graph models in solving seven GDPs. The baseline model is referred to Graph Model, which is trained indepen- dently on its corresponding dataset. Our proposed approach, denoted Graph Model+Con Re initializes the model parameters with pre-trained checkpoint from ConRep4CO trained on the seven GDP datasets and is then fine-tuned individually. Table pressents the results for six combinations of SAT and graph backbones, evaluating the performance of both models trained and tested on datasets with identical distributions, including the easy and medium difficulty datasets. The proposed approach consistently outperforms the baseline model across most GDP tasks, at both difficulty levels, and for all six backbone combinations. These findings indicate that integrating ConRep4CO substantially enhances the quality of the learned representations, enabling more effective capture of the underlying features and characteristics of GDPs. Consequently, the enhanced representations lead to improved accuracy in solving GDPs. Notably, when employing the GraphS AGE backbone, our approach demonstrates particularly significant performance improvement over the baseline.
8

---

Published as a conference paper at ICLR 2026
Table 6: Ablation study on cross-domain information transfer. The table presents GDP-solving accuracy (%) with confidence intervals (a = 0.05). 'Graph Moiie-+ConRpppOOOOSiiing Domain'
refers to the ablated method by disabling cross-domain information transfer.
Difhcalty
Model
k-Cligae
I-Domset
K-Vercov
k-Colce
k-Indset
Marching
Autonsopph
Overall
Gruph ConieeeeoCeep Domain
78 4
61.7+0.1
67.1=0.1
99.9-0.2
65/6104
71.5+0.2
65 360.2
71.4
Easy
Graph ConRep4CO
79.3+0.3
62,040.1
67.3=0.2
90.2=0.1
67,5e0,5
71.7+0.3
65.420.3
71.9
Gruph Muald<ConRepyCO-Siiii -Co-Sii Domain
7091003
61.010.1
62.9.0.1
81.000.3
59/910.4
72.51022
61.3
Medium
Gruph Molel4ComRappCCO
71.3x0.5
64.619.2
63.3et.3
82.2.0.2
64.0s0.1
72.8.0.4
65.7at..4
69.1
4.2.2 IN-DOMAIN GENERALIZABILIT EVALUATION
To assess the in-domain generalization capabilities of the learned representations, particularly in relation to problem scale, we evaluate their performance on previously unseen hard GDP datasets, which consist of problem instances with increased scale and complexity. Table Jableepresents the results for six combinations of SAT and graph backbones, with graph models trained on the easy and medium datasets and tested on the hard datasets. The results clearly demonstrate that the representations learned by ConRep4CO show improved performance across most GDP tasks, both difficulty levels, and all six backbone combinations. This indicates that ConRep4CO also improves generalizability to more challenging and complex problem instances that were previously unseen. The improvement likely stems from the information transfer between various GDPs during pre-training, allowing the model learn shared, more general, and high-level representations. This generality is applicable to problem scale, further reinforcing the robustness of the learned representations.
4.2.3 CROSS-DOMAIn GENERALIZABILITT EVALUATION
To further evaluate cross-domain generalizability, particularly the ability to generalize to unseen problem domains during pre-training, we select 6 out of 7 GDPs as pre-training domains, with the remaining GDP serving the generalizing domain. After pre-training, we define new graph model for the generalizing domain, align it with the pre- pre-trained SAT model from the pre-training domains, and fine-tune it 20,000 instances from the generalizing domain. The graph model for the generalizing domain is referred to as Graph Model-Unseen We conduct experiments on all combinations of pre-training domains and report the GDP-solving accuracy for the generalizing domain in 3 Note that each number in the second row corresponds to a complete independent experiment, where the dataset indicated in the header is the generalizing domain, and the remaining six GDPs serve as pre-training domains. The results demonstrate that ConRep4CO enables the graph model learn better representations for an unseen GDP domain with minimal data, outperforming the baseline. This indicates that ConRep4CO not only enhances representation quality for specific tasks but also improves representation learning for problem domains that are completely unseen. The improvement is likely due to the unified SAT model capturing shared features among pre-training domains, allowing it to learn a general GDP representation applicable to unseen GDPs. Aligning with the SAT model helps the graph model learn new GDP representations more effectively and efficiently.
The results also reveal that is not necessary to include all GDP domains during pre-training when scaling to large number of GDPs Aligning with the pre-trained SAT model allows for effective transfer to new GDPs with minimal data, showing the practical applicability of ConRep4CO.
4.3 ENHANCEMENT OF CO SHOBLEM-SOLVING
We incorporate ConRep4CO into the training of neural solvers for four CO problems to evaluate how it enhances general CO problem-solving. The incorporation process is described in Sec.333..4 denoted as +ConRep4CO. The pre-training datasets are the k- Vercov dataset for MVC, the k- Indset for MIS, the k- k-Clique for MC, and the k-Domset for MDS, all with the easy difficulty level. Table 4 presents the results for MVC, while Table [5) shows the results for MIS, MC, and MDS. "gaPabs" refers to the absolute gap between the output objective and the optimal value, and 'gain' represents the improvement from incorporating ConRep4CO over the baseline, which is calculated as (gapabs, baseline gapabs. ours) ) /gapata. abs, baseline X 100%. 'avg. gain" is the average gain for each problem across all problem scales. incorporating ConRep4CO yields average gains of 61.27% (OpIGNN), 32.20%. 36.46%, and 45.29% for MVC, MIS. MC, and MDS, respectively. We observe that the gain tends to be smaller for larger-scall problems, likely due to the increased difficulty and the growing discrepancy between the scales of the pre- pre-trainin datasets and the evaluated problem. However, across all problem scales, we consistently see substantial performance enhancements. These results

---

Published as a conference paper at ICLR 2026
Table 7: The effect of the number of pre-training domains downstream performance. Values in
parentheses represent the gain over bascline.
Problem
Gmph
Optimal
Raseline
Oured
Oure-2
Ours-
Ours-4
Ourv-5
Ourve6
Ours-
MYC
ER: 100g
Sc.92
35.87
55. 75 (9,6053
55.19 (55-40933
55.07
(94.005)
54.76 158, 5053)
$4.74
(904475)
54.68 (05:2075)
54. (03.660))
MYC
20:10002000
122.7M
125.04
125
5416)
125
t0 9216)
138.99
38163
134.51 (47 18163
124.44
23163
124.39
(50.7716)
134.37 (51 A0HS)
5R/4005500
5096)
419.00
(31)))
419.39
2516)
419.33 1966)
(36))
MIS
BR6200 590g
30.10
19:18
64.22 1993
19,47 5296
19:52 (96-085))
19.55 (900329)
(8.55)
19.59 19%)
19:56 10%3
MIS
RB090011200 12009
45.15
37.48
37.02 (2.479)
38,47 (17.469)
35,60 (20.9185)
35.74 (23.22%)
36,79 (23,00))
35,77 (22.758)
38,79 (23,109)
MC:
RIEDOO
19.05
16.24
16.41 (6-099))
16:00 49%53
17.25 2599)
17:16 st/5)
17 (7:48)41-7085)
17.42 641-779)
61-47643
MC
RI090OL 1200)
31.49
31.75 (13.2699)
31.90 (19.439)
32.07 (25.319))
32.11 (27.949))
32.12 (25.349))
32,14 (29.159)
MDS
RUND000 3400
28.56 (6.948)
25:42 19%5
28.26 8388
(51 39%)
26.18 (99188))))288)
2% (59-88)5))288)
(95,9
MDS
RB1900L 1200)
103.80
110.28
110.04 (3 (3.704)
100.12 (17.906)
108 (24x995)
108.34 (29.949))
108.22 (31.799)
108.17 (32.586)
108.19 (52.259)
demonstrate that ConRep4CO enhances general CO problem-solving beyond GDPs by effectively integrating with problem-speciffe neural solvers, highlighting its strong application potential.
4.4 ANALYSIS ON BROSS-DOMAID INFORMATION TRANSFER
central component of our framework the facilitation of information transfer across different problem domains. To evaluate the effectiveness of this mechanism, we conduct an ablation study by disabling the cross-domain information transfer. Specifically, we train each graph model indepen- dently with its own SAT model, without leveraging cross-domain information. We then compare this ablated approach with our original method, as shown in Table 6 The results indicate that the ablated approach yields inferior performance, thereby highlighting the importance and effectiveness of the cross-domain information transfer in enhancing representation learning.
4.5 FURTHER STUDY ON MULTIPLE DOMAIN INFORMATION TRANSFER
This section investigates the impact of multi-domain information transfer on model performance. We address two key questions: 1) What is the effect of transferring information from multiple domains to downstream CO tasks? 2) How does this effect scale with the number of source domains? This analysis aims provide a comprehensive evaluation of our proposed cross-domain transfer mechanism. We design seven pre-training configurations, utilizing data from to 7 distinct problem domains, denoted as Ours-1 to Ours-7. Each pre-trained SAT model is subsequently used to enhance problem-speciffc neural solvers via contrastive learning. We employ OpIGNN (72) as the baseline solver for MVC and GFlowNet 75 for MIS, MC, and MDS. The aligmment between the pre-trained SAT models and the solvers is performed on 5,000 easy-level instances, with an additional 1,000 instances for validation. The subsequent training procedures for the solvers remain consistent The results are presented in Table 7 The Ours-1 config- uration, which does not leverage cross-domain information transfer, shows a modest performance gain of approximately 5%. This result primarily reflects the benefit of the SAT transformation itself and suggests that pre-training on a single domain provides limited representational enhancement. As the number of pre- pre-training domains increases, the performance gain grows in a sublinear fashion. The improvement is sharpest when expanding from one to two domains, after which the rate of gain decelerates, converging at around five six domains. This saturation effect is likely attributable to diminishing returns in novel information.
with their original implementations 72 75
5 CONCLUSION AND OUTLOOK
We have introduced ConRep4CO, a novel contrastive paradigm designed to promote learning repre- sentation for CO problems across problem types. The results indicate that it not only improves the quality and generalizability of the learned representations but also significantly enhances general CO problem-solving. highlighting the potential of ConRep4CO research. Future work will focus on exploring unsupervised approaches to reduce reliance on labeled data, thereby increasing applicability in data-sparse scenarios. Additionally, we will investigate other potential forms to replace the currently used SAT form to perform contrastive learning, aiming for broader application more general CO problems, such as mixed-integer linear programs (MILP).
unified pre-training paradigm for CO
10

---

Published as a conference paper at ICLR 2026
ETHICS STATEMENT
This research follows the ICLR Code of Ethics and ensures that no ethical concerns are overlooked. The study does not involve human subjects sensitive personal data. All datasets used are either synthetic or publicly available, and the methods for data generation and transformation are transparent and reproducible. We have tried to minimize bias in our experiments and ensure that the results do not perpetuate unfair outcomes. Additionally, the authors declare no conflicts of interest or financial sponsorships that could have influenced the research. Our work is committed to contributing positively to the field of combinatorial optimization.
REPRODUCIBILITY STATEMENT
prioritize reproducibility and have taken steps to ensure that our experiments can be independently replicated. Detailed descriptions of the datasets provided in Appendix Additionally, the detailed network architectures are outlined in Appendix D
We
REFERENCES
[1] JL. Ba. Layer normalization. arXiv preprint arXiv:1607.000 2016.
[2] Albert-Lászlo Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509-511 1999.
[3] Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial optimization: a methodological tour d' d'horizon. European Journal of Operational Research, 290(2):405-44) 421, 2021.
[4] Armin Biere, Marijn Heule, and Hans van Maaren. Handbook of satisfiability, volume 185. IOS press, 2009.
[5] Béla Bollobás and Paul Erdös. Cliques in random graphs. In Mathematical Proceedings of the Cambridge Philosophical Society, volume 80, pp. 419-427. Cambridge University Press, 1976.
[6] Hongyun Cai, Vincent W Zheng. and Kevin Chen-Chuan Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. JEEE transactions on knowledge and data engineering, 30(9):1616-13) 1637, 2018.
[7] Junyang Cai, Taoan Huang, and Bistra Dilkina. Multi-task representation learning for mixed integer linear programming. arXiv preprint arXiv:2412. 224::24/2.14409, /4409, 2024.
[8] Fenxiao Chen, Yun-Cheng Wang, Bin Wang, and C-C Jay Kuo. Graph representation learning: survey, APSIPA Transactions on Signal and Information Processing, 9:c15, 2020.
[9] Lvda Chen, Yang Li, and Junchi Yan. Maskco: Masked generation drives effective representa- tion learning and exploiting for combinatorial optimization. In The Fourteenth International Conference Learning Representations, 2026.
[10] Ting Chen, Simon Korbblihh, Mohammad Norouzi, and Geoffrey Hinton. A simple framework for contrastive learning of visual representations. In International conference on machine learning, pp. 1597-1607. PMLR, 2020.
[11] Xinyan Chen, Yang Li. Runzhong Wang, and Junchi Yan. Mixsatgen: Learning graph mixing for sat instance generation. In The Twelfth International Conference on Learning Representations, 2024.
[12] Darko Drakulic, Sofia Michel, and Jean-Mare Andreoli. Goal: A generalist combinatorial opti- mization agent learner. In The Thirteenth International Conference on Learning Representations, 2024.
[13] Haonan Duan, Pashootan Vaezipoor, Max B Paulus, Yangjun Ruan, and Chris Maddison. Aug- ment with care: Contrastive learning for combinatorial problems. In International Conference on Machine Learning, pp. 5627-5642. PMLR, 2022.
11

---

Published as a conference paper at ICLR 2026
[14] Paul Erdos, Alfréd Rényi, et al. On the evolution of random graphs. Publ. math. inst. hung. acad. sci, 5(1):17-60, 1960.
[15] ABKFM Fleury and Maximilian Heisinger. Cadical, kissat, paracooba, plingeling and treen- geling entering the sat competition 2020. SAT COMPETITION, 2020:50, 2020.
[16] Maxime Gasse, Didier Chételat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances neural information processing systems, 32, 2019.
[17] Maxime Gasse, Simon Bowly, Quentin Cappart, Jonas Charfreitag, Laurent Charlin, Didier Chételat, Antonia Chmiela, Justin Dumouchelle, Ambros Gleixner, Aleksandr M Kazachkov, al. The machine learning for combinatorial optimization competition (ml4co): Results and insights. In NeurlPS 2021 competitions and demonstrations track, pp. 220-231. PMLR, 2022.
[18] Jesús Giráldez-Cru and Jordi Levy. A modularity-basee random sat instances generator. 2015.
[19] Jesús Giráldez-Cru and Jordi Levy. Locality random sat instances. Conferences on Artificial Intelligence, 2017.
International Joint
[20] Ziao Guo, Yang Li, Chang Liu, Wenli Ouyang, and Junchi Yan. Acm-milp: Adaptive constraint modification via grouping and selection for hardness bardness-preserving milp instance generation. In Forty-first International Conference on Machine Learning. 2024.
[21] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024. URL https://ww/t www gurobi. com
[22] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[23] William L Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods 2017.
and applications. arXiv preprint
[24] Kaveh Hassani and Amir Hosein Khasahmadi. Contrastive multi- representation learning on graphs. In International conference machine learning, pp. 41 4116-4126. PMLR, 2020.
[25] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum contrast for unsupervised visual representation learning. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 9729 9729-9738. 2020.
[26] Taoan Huang, Aaron M Ferber, Yuandong Tian, Bistra Dilkina, and Benoit Steiner. Searching large neighborhoods for integer linear programs with contrastive learning. In International Conference on Machine Learning, pp. 13869-13890. PMLR, 2023.
[27] Chaitanya K Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv:1906.01227, 2019.
[28] Richard M Karp. Reducibility among combinatorial problems. In 50 Years of Integer Pro- gramming 1958-2008: from the Early Years to the State-of-the-Arr, pp. 219-241. Springer, 2009.
[29] Richard M Karp. Reducibility among combinatorial problems. Springer, 2010.
[30] Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. Advances in neural information processing systems, 30, 2017.
[31] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 1xXiv:1609.0290000 2016.
[32] Sebastian Lamm, Peter Sanders, Christian Schulz, Darren Strash, and Renato F Werneck. Finding nptrmaptimal independent sets at scale. In 2016 Proceedings of the eighteenth workshop on algorithm engineering and experiments (ALENEX), pp. 138-150. SIAM, 2016.
12

---

Published as a conference paper at ICLR 2026
[33] Massimo Lauria, Jan Elffers, Jakob Nordström, and Marc Vinyals. Cnfgen: A generator of crafted benchmarks. In Theory and Applications of Satisfiability Testing- SAT 2017: 20th Inter- national Conference, Melbourne, VIC, Australia, August 28 September 1, 2017, Proceedings 20, pp. 464 473. Springer, 2017.
[34] Yang Li, Xinyan Chen, Wenxuan Guo, Xijun Li, Wanqian Luo, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Junchi Yan. Hardsatgen: Understanding the difficulty of hard sat formula generation and a strong stucture-hardnnes-awarr baseline. In Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), 2023.
[35] Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2t: From distribution learning in training to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, 2023.
[36] Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha, and Junchi Yan. Fast 12t: Optimization consistency speeds diffusion-based waining-to--esting solving for combinatorial optimization. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
[37] Yang Li, Lvda Chen, Haonan Wang, Runzhong Wang, and Junchi Yan. Generation as search operator for test-time scaling of diffusion-based combinatorial optimization. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
[38] Yang Li. Jiale Ma, Wenzheng Pan, Runzhong Wang, Haoyu Geng, Nianzu Yang, and Junchi Yan. Unify ml4tsp: Drawing methodological principles for tsp and beyond from streamlined design space of learning and search. In The Thirteenth International Conference on Learning Representations, 2025.
[39] Yang Li, Jiale Ma, Yebin Yang, Qitian Wu, Hongyuan Zha, and Junchi Yan. Generative modeling reinvents supervised learning: Label repurposing with predictive consistency learning. In Forty-second International Conference on Machine Learning. 2025.
[40] Zhaoyu Li, Jinpei Guo, and Xujie Si. G4satbench: Benchmarking and advancing sat solving with graph neural networks. urXiv preprint arXiv:2309. 16941, 2023.
[41] Nina Mazyavkina, Sergey Sviridov, Sergei Ivanov, and Evgeny Burnaev. Reinforcement learning for combinatorial optimization: A survey. Computers & Operations Research, 134: 105400, 2021.
[42] Wenzhen Pan, Hao Xiong, Jiale Ma, Wentao Zhao, Yang Li, and Junchi Yan. Unico: On unified combinatorial optimization via problem reduction to matrix-encoded general tsp. In International Conference on Learning Representations, 2025.
[43] Rajvardhan Patil, Sorio Boit, Venkat Gudivada, and Jagadeesh Nandigam. A survey of text representation and embedding techniques in nlp. IEEE Access, 11:36120-36144 2023.
[44] Aleksandar Pekeč and Michael H Rothkopf. Combinatorial auction design. Management science, 49(1 1885-1555,, 2003.
[45] Marcelo Prates, Pedro HC Avelar, Henrique Lemos, Luis C Lamb, and Moshe Y Vardi. Learning to solve np-complete problems: A graph neural network for decision tsp. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4731-4738, 2019.
[46] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference on machine learning. pp. 8748 8763. PMLR, 2021.
[47] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a general, powerful, scalable graph transformer. Advances in Neural Information Processing Systems, 35:145011-4455 2022.
[48] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. Advances in Neural Information Processing Systems, 32, 2019.
13

---

Published as a conference paper at ICLR 2026
[49] Abdelkader Sbihi and Richard W Eglese. Combinatorial optimization and green logistics. Annals of Operations Research, 175:159-1755 2010.
[50] Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David Dill. Learning SAT solver from single-bit supervision. In International Conference Learning Representations, 2019.
[51] Yong Shi and Yuanying Zhang. The neural network methods for solving traveling salesman problem. Procedia Computer Science, 199:681-686, 2022.
[52] Yonglong Tian, Dilip Krishnan. and Phillip Isola. Contrastive multiview coding. In Com- puter Vision-ECCY 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part XI 16. pp. 776-794. Springer, 2020.
[53] Zekun Tong, Yuxuan Liang, Henghui Ding. Yongxing Dai, Xinke Li, and Changhu Wang. Directed graph contrastive learning. Advances in neural information processing systems, 34: 19580-19593, 2021.
[54] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 17X0::1710.110000 10903, 2017.
[55] Petar Veličković, Lars Buesing, Matthew Overlan, Razvan Pascanu, Oriol Vinyals, and Charles Blundell. Pointer graph networks. Advances in Neural Information Processing Systems, 33: 2232 2244, 2020.
[56] Sheng Wan, Yibing Zhan, Liu Liu, Baosheng Yu, Shirui Pan, and Chen Gong. Contrastive graph poisson networks: Semi-supervised learning with extremely limited labels. Advances in Neural Information Processing Systems, 34:6316-6327 2021.
[57] Chenguang Wang and Tianshu Yu. Efficient training of multi-task combinarotial neural solver with multi-armed bandits. arXiv preprint arXiv:2305.0636) 2023.
[58] Jiqqi Wang, Zhengliang Liu, Lin Zhao, Zihao Wu, Chong Ma, Sigang Yu, Haixing Dai, Qiushi Yang, Yiheng Liu, Songyao Zhang, al. Review of large vision models and visual prompt engineering. Reda-Radio,,gy, 133):100047, 2023.
[59] Runzhong Wang, Junchi Yan, and Xiaokang Yang. Neural graph matching network: Learn- ing lawler's quadratic assignment problem with extension to hypergraph and multiple-graph matching. IEEE Transactions on Patlern Analysis and Machine Intelligence, 44(9):5261-5279 2021.
[60] Runzhong Wang, Ziao Guo, Shaofei Jiang, Xiaokang Yang, and Junchi Yan. Deep learning of partial graph matching via differentiable top-k. In Proceedings of the IEEE/CVF conference computer vision and patlern recognition, pp. 6272-6281, 2023.
[61] Runzhong Wang, Yunhao Zhang, Ziao Guo, Tianyi Chen, Xiaokang Yang, and Junchi Yan. Linsatnet: the positive linear satisfiability neural networks. In International Conference on Machine Learning, pp. 36605-36625. PMLR, 2023.
[62] Runzhong Wang, Ziao Guo, Wenzheng Pan, Jiale Ma, Yikai Zhang, Nan Yang, Qi Liu, Longxuan Wei, Hanxue Zhang, Chang Liu, al. Pygmtools: A python graph matching toolkit. Journal of Machine Learning Research, 25(33):1 2024.
[63] Shiyue Wang, Ziao Guo, Changhong Lu, and Junchi Yan. Fractional langevin dynamics for combinatorial optimization via polynomial-time escape. The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025.
[64] Shiyue Wang, Haozheng Xu, Yuhan Zhang, Jingran Lin, Changhong Lu, Xiangfeng Wang, and Wenhao Li. Where paths collide: comprehensive survey of classic and learning- based multi-agent pathfinding, arXiv preprint arXiv:2505.19211 2025.
[65] Nathan Wetzler, Marijn JH Heule, and Warren A Hunt Jr. Drat-trim: Efficient checking and trimming using expressive clausal proofs. In International Conference on Theory and Applications of Satisfiability Testing, pp. 422 429. Springer, 2014.
14

---

Published as a conference paper at ICLR 2026
[66] Ben Wieland and Anant P Godbole. On the domination number of random graph. the electronic journal of combinatorics, pp. R37-R37, 2001.
[67] Huaijin Wu, Wei Liu, Yatao Bian, Jiaxiang Wu, Nianzu Yang, and Junchi Yan. Ebmdock: Neural probabilistic protein-protein docking via differentiable energy model. In The Twelfth International Conference on Learning Representations, 2024.
[68] Huanjin Wu, Xinyu Ye, and Junchi Yan. Qvae-mole: The quantum vae with spherical latent variable learning for 3-d molecule generation. Advances in Neural Information Processing Systems, 37:22745-22771 2024.
[69] Ke Xu and Wei Li. Exact phase transitions in random constraint satisfaction problems. Journal of Artificial Intelligence Research, 12:93-103, 2000.
[70] Ge Yan. Huaijin Wu, and Junchi Yan. Quantum 3d graph learning with applications to molecule embedding. International Conference on Machine Learning, pp. 19126-39137. PMLR, 2023.
[71] Nianzu Yang, Huaijin Wu, Kaipeng Zeng, Yang Li, Siyuan Bao, and Junchi Yan. Molecule generation for drug design: a graph learning perspective. Fundamental Research, 2024.
[72] Morris Yau, Nikolaos Karalias, Eric Lu, Jessica Xu, and Stefanie Jegelka. Are graph neural networks optimal approximation algorithms? Advances in Neural Information Processing Systems, 37:73124- 2024.
[73] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations. Advances in neural information processing systems, 23:5812-5822 2020.
[74] Changwen Zhang, Wenli Ouyang, Hao Yuan, Liming Gong, Yong Sun, Ziao Guo, Zhichen Dong, and Junchi Yan. Towards imitation learning to branch for mip: A hybrid reinforcement learning based sample augmentation approach. In The twelfth international conference on learning representations. 2024.
[75] Dinghuai Zhang, Hanjun Dai, Nikolay Malkin, Aaron C Courville, Yoshua Bengio, and Ling Pan. Let the flows tell: Solving graph combinatorial problems with gflownets. Advances in neural information processing systems, 36:1 19969, 2023.
[76] Xinhao Zheng, Yang Li, Cunxin Fan, Huaijin Wu, Xinhao Song, and Junchi Yan. Learning plaintext-ciphertext cryptographic problems via anf-based sat instance representation. Advances in Neural Information Processing Systems, 37:41 17:41648 6449-4166, 2024.
15

---

baselines, indicating that the learned Published as a conference paper at ICLR 2026
A DISCUSSION WITH RELATED WORK
In this section, we discuss the key differences of our ConRep4CO with some prior works 12 proposing general representation learning methods for CO.
A.1 COMPARISON WITH 12
GOAL 12 aims to develop generalist model that uses single backbone to represent multiple CO problems. The model employs a multi-type Transformer architecture and attention blocks, which suggest that different CO problems activate distinct portions of the backbone parameters. Consequently, GOAL accommodates different problems by utilizing different parts of the shared parameters, rather than exploiting the commonalities between different problems. Furthermore, GOAL's performance is slightly inferior to representations are not enhanced for each problem.
In contrast, ConRep4CO focuses on capturing the shared underlying structure across multiple CO problems, secking higher-level, abstract representation that encapsulates the essence common to different problem domains. By using SAT as a unified intermediary, ConRep4CO facilitates knowledge transfer and mutual enhancement among problems, enabling insights gained from one problem to improve the performance others. Therefore, ConRep4CO outperforms baselines trained on individual problems.
Overall, ConRep4CO differs from GOAL in its emphasis on leveraging the shared structure of multiple CO problems to improve the learned representation for individual problems, rather than simply accommodating problem-specific variations within a single model.
A.2 COMPARISON WITH
The MILP multi-task framework 7 focuses learning shared representations across tasks within single problem domain. It seeks to exploit commonalities among different tasks within the MILP domain. One could draw analogy between the front-end network architecture in the framework and the representation extractor in our graph model, with the task-specific layers serving as different output modules. The MILP multi-task framework emphasizes improving these output modules with single representation extractor, while ConRep4CO prioritizes enhancing the representation extractor by knowledge transfer and mutual enhancement across diverse problem domains. By doing so, ConRep4CO learns a higher-level, abstract representation that spans various CO problems, whereas the MILP framework primarily concentrates on task task-specific output layers for single problem domain.
To the best of our knowledge, ConRep4CO is the first framework leverage representations across different problem domains to improve representations for individual problem domains.
B DISCUSSION ON APPLICABILITY OF CONREP4CO
During the pre-training phase, our framework is designed handle any NP problem. As long as a problem can be reduced to SAT, it can be trained within our framework. We would like to clarify that all NP problems can be reduced to NPC problems, which in turn can be transformed into SAT problems. This theoretical foundation ensures that our framework is applicable to all NP decision problems, regardless of their specific structure or variable types. In this sense, our approach is problem-agnostic, enabling effective training wide range of NP decision problems.
Furthermore, our approach can facilitate vast NP- CO problems by pre-training on their decision versions, which are typically NPC. Most CO problems be converted into their decision versions by adding a target value. In our approach, we can pre-train the models on the decision versions of these CO problems to learn effective representations. These representations can be applied not only to the decision versions but also to the optimization versions of these problems (original problems).
Overall, ConRep4CO can
unified pre-training paradigm for broad range of CO problems.
16

---

Published as a conference paper at ICLR 2026
Table 8: Details of generated GDP datasets.
Untaset
Descrigtion
Parameters
Notes
Clique dinsset consres groph instances Chique
publen which
sabset vertiess which The gial is ideriit whather each fully conrasted vabelt 2 voriices ists with the zrgg. lastatces are built on canduntl generated Bodds Rérei gropis.. Parumeters inclode nimber of vertices u. odge protuiiliiss and claque sire i.
clique
Geseral, - (1) [X
The lised E] ensuring that the expacted sumber of l-- cligues de genersted groph is equal
C-ligge
venions comrocted by
Facy desatt Unilornts 18), Uniforet 4),
Medium danset UnatoenitS, A Unifoenc3, 5%
dataset: Unifemnc20, 25), Unitomc4, 61.
e-Demee deteuct mmsiios graph insoncess of 2- Dominating Set pooblen, which invelves deceminngg whelher gives comans domitating set
dominating graph the The that
y y- (1- [2) -Mil-ay 128
The bused [ie]] cosurin that number t- doninating ses the gco- exited gright equal to I.
dhe stemiity whether can docainns"" the entire graph, eisuring that all ofher vertices are eittr in the sabset or connected it. Instances ure built on nedkmnlly gencrated EadiioRknnyi graples Parsection include: number of vatters olge protahiliinss and demissiing sss size i.
aljuecnt
D-Domset
athezt veriions
Basy daseet: a UnilormsS 15), k- Unitonn 3),
Medium datuett - UnifoemiLS, 201, Unifoeat), 5% Hand daiven v Unfieeme7, 28), k- Unilurncc 6).
Vercow daaaee cousies of graph instances Vente gruph puislan, least
subuut incident ubsett The posl itemiity whether
of detemining
perameter p bised relationship t-
General pa (1) MC
bewwaz J-Clipe Venas,, couziig that lhe
Basy dunset Unitormts 15) Utifonni Harl
subset J veniiess cxists that can 'lover all the odges in the grap, easaring that each odge is connected to at loast one vente. in the sufrect Inctamas are buill on randunily genenital Falli- kénst grophs. Parametees include number of vertices i. edge protcbilices j. and venes set size..
dunset Unutoemi 201, Unifoeure, 8),
pocied size of the mizimum vente cover is the generited araphis lt.
Unifeent 25), Uaiifomee) 10).
Colocing givcn graph can valid coloring assigns one different colors each veries, etatring that venticss connected by olige have diffevent coloes, The goal is identiyy whether such a coloting schome essus for the graph ming at most èt colors Inveanoss we built en candonlly gerentaal Firlt--iig graphs. Prrmiters include number of vettices u. edge probobillies yn and number of colors
dusset consives graph instances
detemnning sajjacat sich
be oolezd with
The puanniee based relatienhip twaen i-Clique and i I-Color, ersuring that the expested minimum nuther of oolors for the yieentta griph is
the
General p= (1) MG
i-Colur
Basy dunset Uniiormts Utifonni Hanl
dunset Uniooeil15, 201, Unitoeur3, 5),
Uniferme2 25), Uaaiforn44
geaph Inkeyersen Sei problem, which detemining the J-
J-ledur dotnect
giren griph contain independent of elgos connecingg pair of ves llos
An independent
The heaed the relatiendipp twan beClope and i-lanee ensuring that the expected numbhe of independem wos in the genentte graph is equal to l.
which
General:
Ladeset
mesatng fiere subse. The goul is to ideatify whether such subsct it veriies existe within the graph, encaring thet the seliened vomoos am mutually non adjucent lustances are built on nasdonily generated Enlts Rémi grapts. Fanuneters inclode nimber of vertices u. olge prbssbiitics ys and inteperdee sot diee
Basy dusset Unliomutt Utifenn Medium
Un-iiennt datsen Unfheeee2 25) Daiffonn4,
thosu
the Perfecs whatler marching. perfect macching subset vaice
graph
Masching prohlen, which imvolus gngh consain
graphis incideal crastlyy olge the subsct. In other worth, the graph''s veriicss can be perned off so that veries is left unpaired and no tan efges. shim vertas The goal is to stemiiy whether euch perfect maching exiss within the graph, crouting that all versees are perfectly muncted, Instances are built on candomily generoted Ennls-Ran grapl,. Paramaturs incluce sumber vertiane and edge pinbabilttes
which
General In(e)//v
The selected porameerr
shopp therabeld for
Marching
Basy danset -u Unitoonto. 16), should be an even number,
Medium dbstect: - Untileen 16, 24), should be an ives number, Hard datsedt y Uniforuz24 50), should be an even manber.
crearing that the generiical
connectivity based on [
graph is aeiiher dondea oue
too sporse.
The Automorphiom problem. which involves desermaiing whether given graph las non-tisiall antomoppiien. As astumooplian is the graph's veriies iself sush that the vinsture of the gript presevvd. meaning ther the odjacency relatio-- skips betweea veriices ramain unchatged. The goel to ideatify whether there exias a way to rearange the vertices of the graph sach that appears ideeiccal
datseet
instunces
The eclectel paramsier is
Generall: p Infvl//
shap deeaboll for sradd
Antommph
Medium. datset - Uniloemi8. 10s.
Itacy domnet - Unitoent4 N).
connectiity based on [
ersuring that the penernted
Hand dataee y Unffeert 12).
angph is neliteer ico dense sor toa sperso.
original form. instaness am huil on naskenly geventte Erdys umple. Parmettes include sumber vertice edge probsbilines
C MORE DETAILS ON DATASETS
In this section, we provide more details on the utilized datasets in our main paper, including the parameters of GDP instances and the statisties of SAT instances.
C.I GDP INSTANCES
To ensure the generation of high-quality GDP instances that accurately capture the inherent character- istics of each problem, we carefully select the graph distributions and parameters used for instance generation. Some parameters refer to [40]. Table 8 provides detailed overview of the specific GDP datasets employed in the main paper.
Note that six of the seven GDPs are NP-complete, while the Perfect Matching problem is P problem.
17

---

Published as a conference paper at ICLR 2026
Table 9: SAT dataset statistics. Variables refers average number of variables, # Clauses denoted average number of clauses, Mod. (LCG) represents average modularity of LCG graphs, and Mod. (VCG) represents average modularity of VCG graphs.
Fay
Hant
NuriaMes
(NCG)
NuriaMes
Med. (LCG)
(NCC)
Voriables
Classess
Med. (LCCG)
(VCO)
C-Caage
35.69
613.25
0.4
0..6
70.86
2298,03
0.49
0.48
114.4)
5670.10
0.50
0.49
01:82
$6-10
17:11
b-Caor 13.51
112.61
0.59
0165
6942
25
0.71
0168
112.15
719-33
0.59
0.66
A-ladeet
35.35
702.93
0.49
0..6
72.55
2388.22
0,49
0.48
113.12
5549-79
0.50
0.49
Maxching
27:48
05003
0.9
0.50
3052
107.67
0.70
0.61
45.48
100
0.22
0.64
Noomooph
56.76
031
0.47
1856.20
0.1
121.55
3612.50
0.1
C.2 SAT INSTANCES
After generating the seven GDP datasets, the corresponding seven SAT datasets are generated by transforming the GDP datasets, utilizing the python toolkit CNFGen B3]. We also compute the statistics of those SAT datasets to provide comprehensive information on datasets. The dataset statistics are shown Table
Moreover, to evaluate the effectiveness of the learned representations on unseen SAT instances, we synthetically generate four more SAT datasets, including two random problems and two pseudo- industrial problems. Specifically, for random problems, generator in AT [50], and the 3-SAT dataset with the 3-SAT generator in CNFGen [33], For pseudo-industrial problems, generate the CA dataset via the Community Attachment model [18] and the PS dataset by the Appulaarty-Simillrte model [9]. The generation process the four datasets follows [40]. where the dataset descriptions and statistics can also be found.
generate the SR dataset with the SR
The ground truth of satisfiability and satisfying assignments are calculated by calling the statc-of-the- art modern SAT solver CaDiCaL (15), and the truth labels for unsat core variables are generated by invoking the proof checker DRAT-trim (65)
D DETAILS ON MODEL ARCHITECTURE
D.1 BASIC ARCHITECTURE IMPLEMENTATION
Graph Model. Each graph model is designed to address a specific type of GDP, and all models maintain a consistent architecture. To illustrate this, we focus on problem Px and its corresponding graph model M,. The graph model M,, takes graphs in the set G. input and processes them through the Representation Extractor. The input graph primarily consists of edge information, which often critical aspect of GDPs. For the initial vertex features, introduce d-dimensional
embedding for all vertices, represented as (!)
For the Representation Extractor, adopt the vanilla Graph Convolutional Network (GCN) 3 which is widely used as backbone for node embeddings graph- tasks. Assume there are layers, the embedding extraction at the i-th layer of the network is expressed
RD ÄD + ( ((--1)),,,, n
..
(3)
where H denotes the node embedding matrix, with each row corresponding to node embedding. The matrix A A is the adjacency matrix augmented with self-loops through the identity matrix D. = E3 À.j is the degree matrix, and W the learnable weight matrix. Following the extraction of node features, we apply average pooling to the node embedding matrix H( aggregate node-level information into a single representation for the entire graph instance, denoted r,, This aggregation is computed as follows:
F2 EvEp
(A) h
(4)
[V]
where V represents the set of vertices in the input graph, V/ denotes the total number vertices, and h is the extracted embedding for node r, serves the instance-level feature representation. and is subsequently fed into the Output Module, which implemented as an MLP to produce the final decision for the instance.
18

---

Published as a conference paper at ICLR 2026
SAT Model. Apart from the graph models, the SAT model Maat processes the constructed SAT graphs via its own Representation Extractor. For illustration, we consider the LCG representation. For the initial node features, we define two distinct d-dimensional embeddings: h, for all literal nodes and he
(0) for all clause nodes.
The architecture of the Representation Extractor is inspired by NeuroSAT [50]. For notational clarity, we assume that the extractor consists of layers, with both literal and clause node embeddings being iteratively aggregated and updated at each layer. At the i-th layer, the updates for the literal and clause node embeddings are formulated as follows:
h LayerNormLSTMM
SUM (MLP ,1, (1(t-1)
(6-1)
(5)
(EN(()
h LayerNormLSTM
SUM (MLP (h) (b)
(6)
(EN(()
where and represent an arbitrary literal node and clause node, respectively, N(.)) refers to the set of neighboring nodes. The summation operator (SUM) serves as the aggregation function, while STy [I] is employed as the update function.
Similar to the graph models, the instance-level representation Feat derives by averaging the literal node embeddings after the k-th layer. The instance- level representation, along with the literal-level embeddings, is passed to the Output Module, which is also implemented as an MLP, to generate the final task-specific decisions or predictions.
D.2 INITIAL VERTEX FEATURES
As illustrated in the main paper, the input graphs primarily provide edge information instead of vertex features. Therefore, we should devise initial vertex features for the models. this section, we introduce the definition of initial vertex features for the graph and SAT models.
Graph Model Vertex Feature. We begin by generating normalized, learnable d-dimensional vector, which serves the initial embedding shared across all vertices. For GDP datasets that do not require additional embedding directly used as the vertex feature for all vertices. In contrast, for GDP datasets where the parameter k plays critical role in defining the instance characteristics, such as k-Clique and k- Vercov, we first embed into a d-dimensional vector. The initial vertex embedding is then fused with the k embedding through an MLP to generate the final initial vertex features.
information, such as Matching and Automorph, this initial
SAT Model Vertex Feature. For the SAT model, we generate initial vertex features based on the type of SAT graph representation, whether it is Literal-Clause Graph (LCG) Variable-Clause Graph (VCG). In the case of the LCG graph, we initialize normalized, learnable d-dimensional vector for all literal nodes and a separate normalized, learnable d-dimensional vector for all clause nodes. Similarly, for the VCG graph, we generate a normalized, learnable d-dimensional vector for all variable nodes and another for all clause nodes.
D.3 MORE BACKBONES
To demonstrate that the performance improvement brought about by ConRep4CO is consistent, and independent with specialized model architectures, we conduct experiments on more backbones.
Graph Model Backbone. For the graph model, we employ an additional mainstream network architecture for node embedding, GraphSAGF [22]. which is widely recognized for its ability to generate inductive representations of graph nodes by aggregating information from a node's local neighborhood. The update rule for the i-th layer of GraphSAGE is defined as follows:
AGG (ReLU (Q (Q"h + c(()) I (EN(w))
h (++1) ReLU (W() CONCAT (.. (
(8)
19

---

Published as a conference paper at ICLR 2026
where h denotes the embedding for vertex N (u) refers to the neighbors of vertex Q q. W trainable parameters, and AGG is the aggregation function. In our implementation, AGG is defined as the mean function, which computes the element- wise average of the neighbor embeddings.
In addition, we implement two more advanced GNN backbones for our graph models, PGN [35] and GraphGPS [47]. Please refer to the corresponding papers for details the architectures of these two backbones.
SAT Model Backhone. For the SAT model, we incorporate GCN architecture specifically tailored for SAT graphs as an additional backbone. The node updates at the i-th layer are defined as follows:
SUM (MLP (h) h (f-1) h b(()1))) CEN(()
h
MLP
SUM (MLP ()) h!! _n!-")) (EN(()
h
MLP
(10)
where and represent an arbitrary literal node and clause node, respectively. The aggregation of neighboring node information is performed using the summation operator (SUM), which serves as the aggregation function. The updates for both literal and clause nodes are computed using an MLP.
Furthermore, extend the backbone VCG graph modeling, where all literal nodes replaced by variable nodes, and each literal and its negation are merged into single variable node. The node updates at the i-th layer of the VGC-based GCN are formulated as:
MLP
SUM (MLP (h) h (i-1) (EN(
(11)
MLP
SUM (MLP (h:-))) .h vEA((c
(1-1)
(12)
where and represent arbitrary variable node and clause node, respectively.
D.4 CASE STUDY ON MODEL OUTUT
In this section, we illustrate the model outputs for specific GDP and corresponding SAT problems for better understanding.
In the context of GDP, the model's output is typically binary, represented as 0 or 1, at the instance level. For instance, in the case of the k-Clique problem, the input consists of graph, and the output indicates whether the graph contains clique of size k. Specifically, if k-Clique is present, the output I; otherwise,
Similarly, for the corresponding SAT problem, the output denotes the satisfiability of the formula. If the formula is satisfiable, the output solution of the original GDP problem. For example, satisfiable formula indicates the existence of k-Clique in the original graph.
not, it The satisfiability result directly linked the
However, the framework is not restricted to this specific task alone. By making appropriate modifica- tions to the architecture of the output module, the models can be adapted to solve other related tasks, including both based and GDP-based tasks.
E TRAINING DETAILS
E. TRAINING PARAMETERS
For reproducibility, we present some important parameters used training in Table TO More details can be found in source code, which will be released once the paper accepted.
E.2 COMPUTATIONAL. COST
All training and inference tasks were conducted on single NVIDIA H100 GPU with 80GB of memory.
20

---

Published as a conference paper at ICLR 2026
Table 10: Parameters used for training.
Parameter
Value
Description
le-04
Learning rale.
Ir stepieesiize Ir factor
50
Leurning rule step size. Learning rate factor. Learning rate patience.
0.5
Ir patience clip. norm weight_decay
10
Clipping norm.
le-08
1.2 regularzation weight. Tieration number of GNN layers SAT model. Iteration number of GNN layers in gruph model.
mod.meeennnnnnu Jayer graph_model model. layer mip layer
32
12
Number of Lineur layers in an MLP.
0.1 (casy) 0.5 (medium)
Temperature scalar in the contrastive loss. Weight of decision loss during training.
0.5-1.00
1.75
2.0
1865
1.25
Costraative Loos
0.5
1.30
Costrastive
0.0
0.75
0.25
-19
0.90
100
120
80
302
120
60
80
320
location Tndee
Tteestion Enden
Bocation Enden
(a) CL of k-Clique
(b) CL of k-Domset
(c) CL of V--ercov
Figure 4: Contrastive loss w.r.t. training iterations across various datasets. CL denotes the contrastive loss of the training process.
The pre-training process for the SAT model and the graph models with ConRep4CO totally takes approximately 40 hours, with convergence typically occurring around the 20th epoch. Each epoch requires roughly 2 hours. Following the pre- pre-training phase, fine-tuning takes additional to 6 hours for each model to achieve optimal performance. In comparison, training the baseline SAT model takes about 45 hours, with convergence reached by the 30th epoch, and each epoch requiring approximately 1.5 hours. Notably, pre-training with ConRep4CO demonstrates a faster convergence rate, leading shorter training time. Moreover, training the baseline graph model independently each requires around 15 hours, with convergence occurring around the 60th epoch, and each epoch taking between 12 to 18 minutes.
Overall, the computational cost of training with ConRep4CO is comparable to that of the conventional training approach, with no significant increase in computational burden.
F FURTHER STUDIES
F.1 FURTHER STUDY ON CONTRASTIVE LOSS
We revise the negative sampling strategy within our contrastive learning framework to mitigate the issue of false negative samples. Specifically, within each training batch, unsatisfiable instances are selected as negative samples for satisfiable instances, and conversely, satisfiable instances are chosen as negative samples for unsatisfiable instances. This adjustment ensures that false negative samples are avoided. Consequently, we modify the contrastive loss function to reflect this change and proceed with the training of the models. The results, as shown in Table [1] demonstrate that the models trained with the revised contrastive loss exhibit performance comparable to that of those trained with the original loss. We also plot the contrastive loss curves for several GDPs during the original training process in Fig. 4 all which exhibit smooth trajectories. These results suggest that the influence of false negative samples model performance is minimal.
21

---

Published as a conference paper at ICLR 2026
Table 11: Experimental results the modified and original contrastive loss function. The table
presents the GDP-solving accuracy (%) with confidence intervals (a 0.05) for the graph models. 'Graph/SAT Modell-ConRepCOOMModeo
Loss' denotes training with the modified contrastive loss. 'SAT Back.' refers to SAT model backbone, and 'Graph Back.' denotes graph model backbone.
Gussh
Model
V-rrror
k-Cle
Marching
Ovenll
Gragh Maa.eaannnceppooooocellllleee Lons
77.1803
579
64 5:53
$6.785.1
64.2004
71.58522
M4430
893
Grigh ModeHCCiiaayCCC
79.368.3
620b6111
67.
96.36.11
67.505
73.766.3
65.40.3
719
LCG
Groph Model CanBaa4Co Modifeed
61.2013
67.1
Grggh MallseCCnnippiCC
7133885
$46202
633U03
$2.21.1
72848.4
68.20.4
69.1
Table 12: Experimental results across two graph models under different training methods. 'Graph Model (fully-trained) refers to the graph model that was trained from scratch with full training data. 'Graph Model=ConRep4CO (fine-tuned) refers the fine-tuned graph model after pre-training by ConRep4CO on small datasets.
Model
k Clique
k- D-mmsstt
k. Vercov
k-Color
k-Indeet
Matching
Automorph
Overall
Graph Model (fully-trainell trained)
67.3=0.4
66.740.2
65,4x0.4
79.140.2
59.1
72.4+0.1
65.4+0.2
67.9
Graph Modele ConRep4CO (fine-tuned)
67.9.0.2
67.040.1
66.6290.4
79.4+0.2
61.5+0.4
72.6+0.1
63.7200.
68.7
Table 13: GDP solving accuracy (%) with confidence intervals (a 0.05) of the graph models on Easy datasets. The 'Overall' column represents the average accuracy across all datasets.
Model
k-Clique
k-Domset
k-Vercov
k-Color
k-Indsei
Matching
Automorph
Overall
Graph Model-FulllDan
77.8+0.1
59.0a0.2
61.440.3
37.840.4
63.2a0.1
71.3+0.1
64.3a0.3
69.3
Graph Model-CCnRepACC
79,3+0.3
62.0:0.1
67.3+0.0
90.2:0.1
67.5+0.1
71.720.0
65.4:0.4
71.9
F.2 FURTHER STUDY ON GRAPH MODEL GENERALIZATION TO LARGE- DATA
To further assess the generalization ability of our graph models, generate large-scale instances for each GDP, with instance sizes ranging from 7 to 20 times larger than those used during pre-training. We then fine-tune the pre-trained models on this large-scale data, using subset comprising 1 of the training data. We compare the performance of the fine-tuned models with those trained from scratch with full training data, and the results presented in Table [2] indicating that models pre-trained on smaller instances using ConRep4CO can generalize effectively to larger instances through fine-tuning.
F.3 FURTHER STUDY ON DATA VOLUME
During the pre-training phase, ConRep4CO utilizes all instances from different domains, while the baselines only have access to the instances from their single domain. To further assess the impact of data volume, we increase the number of training instances for baselines, and train 7 bascline graph models with the GCN backbone separately, each on 7 x 160,000 graph instances generated from single problem type, denoted as Graph Model- FouleaFullData, and compare their performance with our approach in Table 13 It proves that the improved performance is not from increased training data.
G LARGE LANGUAGE MODEL USAGE
In this paper, large language models (LLMs) only used to find and correct grammatical errors.
22


Reviews:
[{"review_id": "Qgsa9ExYv4", "reviewer": "Reviewer_ZxEz", "summary": "This paper introduces ConRep4CO, a novel training framework that leverages contrastive learning to significantly enhance the learned representations of graph decision problems. Experimental results demonstrate that ConRep4CO's contrastive learning techniques indeed improve model performance. Furthermore, the approach shows promising extensibility, maintaining performance improvement when applied to unseen combinatorial optimization problems.", "questions": "1.\tWhat are the definitions of confidence intervals, ER, and RB?\n2.\tWhy are models only trained on the easy and medium problems (Tables 1 and 2)?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "-\tThe illustration of the training process is clear and easy to follow.\n-\tThe experimental evaluations are comprehensive.", "weaknesses": "-\tThe definitions of some symbols are missing. What are confidence intervals? What is ER in Table 4? What is RB used in Table 5?\n-\tIt is unclear why the models are only trained on the easy and medium problems without considering the hard problems (Tables 1 and 2).\n-\tSome numeric calculations in Table 4 are incorrect. For instance, GCNN+ConRep4CO gets 55.17 OBJ score, while the optimal score is 54.62. The gap_{abs} score should be 55.17-54.62=0.55, not 0.57, which is listed in the table. In fact, I find that all the gap_{abs} scores of GCNN+ConRep4CO are incorrect.\n-\tThe improvement introduced by training the model across multiple domains (Table 6) seems to be very small. The difference between the single domain setting and the multiple domain setting is within the standard deviation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "t8P45WA4JE", "reviewer": "Reviewer_FRhi", "summary": "This paper introduces ConRep4CO, a framework that leverages contrastive pretraining to generate representations for combinatorial optimization. The core innovation lies in its method of unifying diverse NP-complete problems by converting them into a Boolean satisfiability format; these SAT-derived versions serve as positive counterparts to their original instances within the contrastive learning objective. Empirical evaluation across seven graph-based decision problems and four optimization tasks indicates that the framework not only enhances performance but also exhibits robust generalization, positioning it as a viable paradigm for unified representation learning in the CO domain.", "questions": "1. The paper justifies the use of SAT through its universal expressiveness (reducibility). However, a deeper theoretical or visualized explanation of its representational advantage would be beneficial. For instance, does the SAT form act as an information bottleneck, stripping away problem-specific noise to reveal a common core, or does it function as a canonical encoder that explicitly captures fundamental combinatorial structures shared across different GDPs?\n\n2.  To ensure reproducibility and provide deeper insight, could the authors elaborate on the training details? Specifically, clarifying the objective and impact of the warm-start phase, and explaining how the balance (relative weighting) between the two loss components was determined or tuned would be highly valuable.\n\n3. The premise of the framework is that diversity in pre-training tasks fosters generalization. Was this correlation investigated? Specifically, does performance on downstream tasks improve when the model is pre-trained on a broader variety of problem types? Furthermore, which specific design elements (e.g., the specific contrastive pairing, the SAT transformation itself) are identified as most critical for enabling this effective cross-domain knowledge transfer?\n\n4. How does the method scale with an increasing number of pre-training problem types? Have you considered or experimented with other unifying formalisms beyond SAT (e.g., Integer Linear Programming) that might offer different trade-offs in terms of representation compactness or transformation complexity?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "1. The core novelty of this work lies in its use of Boolean satisfiability as a unifying representational bridge, enabling knowledge transfer across distinct combinatorial optimization problems.\n\n2. The experiments are sufficient, rigorously evaluating the framework across various graph decision problem categories, architectural backbones, and downstream solver methodologies.\n\n3. The results demonstrate observable empirical improvements, confirming that the method enhances both the quality of the learned representations and the end-to-end performance of the solvers that utilize them.", "weaknesses": "1. While the results are compelling, the paper would benefit from a deeper mechanistic analysis of the SAT-based alignment process. A more thorough investigation into why this specific form of contrastive learning fosters such effective cross-domain generalization would strengthen the theoretical contribution.\n\n2. It seems that the framework is explicitly designed for problems that can be efficiently reduced to SAT (primarily NP-complete problems). I am not sure whether I missed anything. But its applicability to problems outside this class, or to CO problems with complex, non-logical constraints (e.g., certain scheduling or routing constraints), is unclear and not explored.\n\n3. The practical scalability of ConRep4CO warrants further discussion, as the computational complexity associated with the CNF transformation and the requirement to train multiple models could present significant bottlenecks for larger, real-world instances.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KFMJFjavtO", "reviewer": "Reviewer_QCGp", "summary": "This paper proposes ConRep4CO, a contrastive pre-training framework for learning representations across different combinatorial optimization (CO) problems. The key idea is to transform graph decision problems (GDPs) into SAT form and use contrastive learning to align representations. Positive pairs consist of a GDP instance and its SAT transformation; negative pairs are non-corresponding instances. The method shows improvements on 7 GDPs and 4 downstream optimization problems (MVC, MIS, MC, MDS).", "questions": "- Pre-training uses very small graphs (5-25 vertices) while downstream performance degrades substantially with scale. Real-world CO problems typically involve thousands to tens of thousands of nodes. To be practically useful, would the approach require pre-training on much larger problem instances? Can you provide a guess of the time and ressources needed to train on graphs with 10,000+ vertices, and maintain similar performance improvements at that scale?\n- Can you add empirical comparisons to GOAL and UniCO ? These seem like important missing baselines. \n- How sensitive is performance to warm-start? What happens without it?\n- SAT Model Failure: Why does SAT model show 50% accuracy (random) on many hard instances while graph models transfer reasonably?\n- Temperature Selection: Why does temperature differ between easy/medium datasets? How was this chosen?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The use of SAT as a common modality to bridge different CO problems is creative and theoretically grounded. The motivation that NPC problems can be reduced to one another through SAT is compelling and elegantly exploited.\n- Extensive experiments across 7 GDPs with multiple architectures (GCN, GraphSAGE, PGN, GraphGPS), different difficulty levels; demonstrates generalization to both larger problems and unseen problem types.\n- The downstream results on MVC, MIS, MC, and MDS show substantial improvements\n- Ablations on cross-domain information transfer, different loss functions, and sensitivity analysis provide good insight into what drives the performance gains.", "weaknesses": "- Experiments use very small graphs. Performance gains decrease substantially with scale. Unclear how this scales.\n- No empirical comparison to GOAL, UniCO methods despite discussing them. Downstream comparisons only include problem-specific baselines.\n- Warm-start strategy mentioned as important but not ablated\n- False negatives issue: Modified loss without false negatives shows comparable performance, questioning what contrastive loss actually learns\n- Temperature differs between difficulty levels without justification or sensitivity analysis", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2GPgITDnup", "reviewer": "Reviewer_nnWe", "summary": "This paper considers a contrastive learning based approach to graph Combinatorial Optimization (CO) problems. The approach is based \non associating each CO problem with a graph decision problem. It then associates each GDP with a Boolean Satisfiability problem (SAT) and considers the corresponding SAT graph. The authors then develop models for each of the GDPs and one unified model for the SAT graphs. During training, they use a contrastive loss that purportedly aligns the GDP and SAT modalities they also use a warm-start training technique.\n\nExperimentally, the authors consider seven GDPs include k-clique, k-coloring and k-independent sets. They that adding in the ConRep4CO framework (which appears to refer to their contrastive loss between the SAT and the GDP) improves performaces verses an ablated model. The performance is quantified both on the performance of the representation for solving the GDP and the underlying CO problem, although the performance increase is substantially more modest in the former case (which makes it hard to gain intuition about the larger performance boost in the CO problem).", "questions": "what is the computational complexity of the proposed model?\n\nhow does performance compare to non message-passing based approached, e.g., reinforcement learning", "limitations": "", "rating": 4, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Method does seem to improve performance in most cases", "weaknesses": "The method is not clearly explained. More specifically, more background should be given on how a GDP may be related and how the GDP is related to a SAT or a SAT graph. Furthermore, it is not clear how the model actually operates. The overall architecture is not well-explained in the text and in my summary I am making educated guesses based on Figure 2, which is not a substitute for actually explaining the model.\n\nMethodological contributions seem incremental, although this is hard to assess to the general lack of clear explanations as noted above \n\nAdditionally, there insufficient discussion of computational complexity / run time. This makes it difficult to weigh the increase in model performance against increased cost. Notably, in CO problems, this is particularly essential. All of these problems are exactly solvable, e.g, by using GUROBI solvers, so the entire name of the game is developing fast, approximate solutions.\n\nThe code is not available. This is particularly problematic because a) the method is motivated primarily by experimental results and b) there is not enough detail given on the model in order to be able to reproduce these experiments.\n\nMinor:\n\nThe first two sentences of the abstract seem to contradict one another\n\n\"texts\" should be \"text\" in line 42\n\nNotational inconsistency G_i^j vs G_j in the start of section 3.3.1\n\nThe relative contributions of the SAT backbone and GNN backbone are hard to parse in Table 1", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)