Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization? Semih Cantürk, Thomas Sabourin, Frederik Wenkel, Michael Perlmutter, Guy Wolf Abstract A key challenge in deriving unified neural solvers for combinatorial optimization (CO) is efficient generalization of models between a given set of tasks to new tasks not used during the initial training process. To address it, we first establish a new model, which uses a GCON module as a form of expressive message passing together with energy-based unsupervised loss functions. This model achieves high performance (often comparable with state-of-the-art results) across multiple CO tasks when trained individually on each task. We then leverage knowledge from the computational reducibility literature to propose pretraining and fine-tuning strategies that transfer effectively (a) between MVC, MIS and MaxClique, and (b) in a multi-task learning setting that additionally incorporates MaxCut, MDS and graph coloring. Additionally, in a leave-one-out, multi-task learning setting, we observe that pretraining on all but one task almost always leads to faster convergence on the remaining task when fine-tuning while avoiding negative transfer. Our findings indicate that learning common representations across multiple graph CO problems is viable through the use of expressive message passing coupled with pretraining strategies that are informed by the polynomial reduction literature, thereby taking an important step towards enabling the development of foundational models for neural CO. We provide an open-source implementation of our work at https://github.com/semihcanturk/COPT-MT . † † affiliationnotice: Equal contribution 1 Introduction The ability to transfer performance from one task to another is a crucial challenge in the development of modern AI since it eliminates the need to train a model from scratch each time that a new task is encountered. Instead, we seek to train a model to perform well on a representative collection of problems in such a way that it may be easily adapted to each new task in a relatively lightweight manner. Common techniques for this include partial fine-tuning as well as attaching relatively simple downstream task heads to an otherwise frozen architecture ( 34 ; 48 ; 9 ; 47 ; 22 ) . For example, in medical image analysis, pretrained vision models have been shown to provide meaningful features, significantly improving conventional ML efficacy ( 21 ) , and a promising initialization for further fine-tuning under data scarcity conditions ( 11 ) . We note that while transferability has only recently emerged to the forefront of modern ML/AI, it has been a cornerstone of theoretical CS for many decades. Indeed, the study of computability and complexity relies on a hierarchical structure of equivalence classes defined by appropriate reductions between problems ( 7 ; 35 ) . Perhaps the most prominent examples are the classes P and NP, containing problems that are solvable in deterministic vs. non-deterministic polynomial time (correspondingly). To show that a problem is in P, one has to either find a direct algorithm that solves it, or – perhaps more often – an indirect solution via a polynomial reduction to another problem that is known to be in P. This reduction would translate the inputs to the target problem, and then translate the solution from it back to that of source problem. As long as both translation steps can be done in polynomial time, their cascade with the polynomial algorithm for the target problem would also result in a polynomial algorithm. Similarly, membership in NP can be established either by verifying a hypothesized solution in polynomial time, either directly, or indirectly via reduction to a known NP problem (i.e., by translating the candidate solution to test on it). In particular, the study of such reductions gives rise to the notion of NP-complete (or NP-hard) problems – those to which every problem in NP can be (polynomially) reduced. Indeed, these problems form an upper bound on NP complexity, in the sense that if any of them is solvable in polynomial time, it would immediately enable polynomially solving any problem in NP via a cascade of reductions. We note that while the discussion above focused on polynomial complexity (due to its prominence), numerous other complexity classes have been extensively studied, such as poly-logarithmic, linear, or randomized-polynomial time, as well as ones focusing on other algorithmic aspects, such as parallelization capabilities and space requirements. A common theme in each of these is the reliance on complexity-bounded reductions, yielding the notion of completeness (or hardness) of problem classes. Further, in these studies, typically only a handful of core problems that are directly solved via a handcrafted algorithm, whereas the other problems are indirectly solved by reducibility. We refer the reader to 7 ; 35 for further details and extensive background on these topics. Intuitively, one could argue that the aim of foundation models in deep learning is similar, at least in spirit, to these studies, in that they aim to establish a core set of tasks (with associated loss terms and curated data) that are sufficient to elicit emergent behavior, by which entire families of problems (or tasks) will be easily, if not trivially, approached with relatively simple adaptation of the core foundation model. In this work, we investigate whether the notion of efficient (e.g., complexity-bounded) reducibility can inspire, or potentially inform, decisions regarding transferability. This is particularly relevant in combinatorial optimization problems on graphs, which have been of high interest in recent graph neural network studies, as well as in theoretical computer science, motivated in part by applications in, e.g., logistics ( 3 ) , health care ( 51 ) , and scientific discovery ( 33 ) . Notably, most graph CO problems are NP-hard and feature an exponential search space, which makes their direct solution computationally prohibitive. Nevertheless, numerous recent work have produced promising results for generating approximate solutions for individual CO tasks, often using networks that are trained by task-specific loss functions ( 29 ; 19 ; 31 ; 50 ) . Here, we seek to build on their work towards a unified model that is able to solve multiple CO tasks simultaneously, utilizing connections between transferability and reducibility. In particular, we aim to replace traditional reductions (driven by complexity bounds) with efficient transfer learning mechanisms suitable for integration in deep learning paradigms, and establish empirically their cross-task generalization feasibility. In doing so, we aim to provide an important stepping stone towards the development of foundation models that form a universal neural solver for CO problems. To this end, we first establish, in Sec. 3 , new baselines for individual CO tasks based on the Graph Combinatorial Optimization Network (GCON) network introduced by 45 and show that this method matches the performance of most current methods, and occasionally even establishes a new state-of-the-art (albeit not our primary focus here). Namely, we focus on the following six problems, described in further detail in Sec. 3.3 : Maximum Independent Set (MIS), Minimum Dominating Set (MDS), Minimum Vertex Cover (MVC), Max Clique, Max Cut, and Graph Coloring. We then turn our attention to transferability, first studying in Sec. 4 pairwise transferability between three of these tasks. There, we explore the relation between reducibility and transferability, while also elucidating the challenges in translating theoretical knowledge to practical application in deep learning settings. Next, in Sec. 5 we shift towards a more realistic setting, addressing a primary prerequisite for the development of transferable foundation models, which are based on forming a unified trunk pretrained via multi-task learning, and that can generalize to new tasks with relatively light-weight adaptation. Our results indicate that indeed some connections arise between the notions of reducibility and transferability, although these connections are not trivial and further work is needed to fully elucidate them. Nevertheless, we see our contributions as providing a stepping stone for further studies on this topic, and a promising starting point for future work on universal neural CO solvers. Figure 1 : (Left) Reduction between tasks for pairwise transferability section: MIS/MVC are complements, but MaxClique is based on an auxiliary graph. (Right) Multi-task learning / fine-tuning architecture (pretraining set in green, fine-tuning set in purple) 2 Related work Several prominent lines of research have emerged as part of the recent interest in graph CO problems. We focus here on a brief summary of the ones most relevant to this work. A more extensive discussion is provided in Appendix B . In particular, we focus here on unsupervised approaches, e.g., 19 , which proposed a surrogate loss function for the maximum clique and graph partitioning problems, together with sequential decoding of probabilistic predictions to obtain valid solutions. 31 paired this framework with a GNN derived from the geometric scattering transform ( 14 ) to obtain further competitive results on approximate max clique, while 30 used a similar setup for the traveling salesman problem. A recent subset of unsupervised GNN-based solvers use physics-inspired loss functions based on 29 , which showed that many CO problems map to the Ising model, and minimizing the corresponding Hamiltonian representing its energy landscape is equivalent to solving them. 39 ; 24 tackle max cut and MIS using this recipe while 40 extend it to graph coloring. More recently, 38 used task-specific Hamiltonians to train a diffusion model and attain competitive results across multiple tasks. Multi-task Neural CO. Most attempts to develop a unified model for CO problems are based on supervised or reinforcement learning. Examples include GOAL ( 10 ) based on imitating expert trajectories, UniCO ( 53 ) based on a Markov Decision Process, and the RL models in 25 ; 44 based on gradient homogenization and a multi-armed bandits respectively. Another approach aims to obtain a generic representation via SAT bipartite graphs ( 18 ; 49 ) or syntax trees capturing problem constraints ( 6 ) . Unlike these methods, we rely on unsupervised learning with task-specific loss functions, which avoids problems arising from the large size of the state space in RL. Moreover, we avoid transforming the graphs to a common SAT or abstract representation but rather work on the original graph structure by using a GCON backbone that leverages a complex filter bank and localized attention mechanisms to learn approximate solutions to CO problems ( 45 ) . Finally, unlike most of these methods, which do not justify their selection of pretraining tasks, we aim to use known polynomial reductions to show similar problems transfer effectively between each other, thus guiding our pretraining tasks selection. See Appendix B for further discussion. Polynomial reductions for CO problems. Combinatorial optimization problems have been extensively studied in the computer science literature, e.g., with Karp’s 21 NP-complete problems ( 20 ) . Many polynomial reductions are well known between these problems, such as the equivalence relations shown in 15 between the maximum clique (MaxClique), maximum independent set (MIS) and minimum vertex cover (MVC) problems (see Lemma B.1 in Appendix B ). Moreover, 12 demonstrate the existence of a kernel subset of Karp’s 21 problems, which span the rest of the problems via the notion of linear orbit, defined via linear reducibility. In particular, their work implies that MaxClique, MaxCut, Node Cover (MVC and therefore MIS), and Set Cover (of which MDS is a special case) reside in the linear orbit of 0-1 Programming. Note that, conversely, problems like Chromatic Number ( K -coloring) and the Hamiltonian Cycle Problem appear to occupy different linear orbits. A formal discussion and further details are provided in Appendix B . 3 Methodology Table 1 : Energy-based loss functions for CO problems considered. Table extended from 38 . CO Problem Objective: \min_{X\in\{0,1\}^{N}}H(X) MIS H(X)=-A\sum_{i=1}^{N}X_{i}+B\sum_{(i,j)\in\mathcal{E}}X_{i}\cdot X_{j} MDS H(X)=A\sum_{i=1}^{N}X_{i}+B\sum_{i=1}^{N}\left(1-X_{i}\right)\prod_{j\in\mathcal{N}(j)}\left(1-X_{j}\right) MaxClique H(X)=-A\sum_{i=1}^{N}X_{i}+B\sum_{(i,j)\notin\mathcal{E}}X_{i}\cdot X_{j} MaxCut H(\sigma)=-\sum_{(i,j)\in\mathcal{E}}\frac{1-\sigma_{i}\sigma_{j}}{2}\quad where \sigma_{i}=2X_{i}-1 MVC H(X)=A\sum_{i=1}^{N}X_{i}+B\sum_{(i,j)\in\mathcal{E}}\left(1-X_{i}\right)\cdot\left(1-X_{j}\right) K -Coloring H(X)=\sum_{i=1}^{N}(1-\sum_{k=1}^{K}X_{i,k})^{2}+\sum_{(i,j)\in\mathcal{E}}\sum_{k=1}^{K}X_{i,k}X_{j,k} We frame each CO task as an unsupervised learning problem, and assume we do not have access to the set of interest or even the size of this set. Throughout, we assume undirected and unweighted graphs G:=\left(V,E\right) , V=\{v_{1},\ldots,v_{N}\} , though much of our work can easily be extended to weighted graphs. We denote the complement of G as \bar{G}:=\left(V,\bar{E}\right) . When training models from scratch, our pipeline largely follows 45 and 19 . We first train a GNN encoder, which is trained by a task-specific, unsupervised loss function to generate a vector \operatorname{\mathbf{p}} whose i -th entry \operatorname{\mathbf{p}}_{i}=\operatorname{\mathbf{p}}[v_{i}] is interpreted as the probability that v_{i} is in the set of interest. That is, the \mathbf{p}_{i} may be thought of a soft proxies for the indicator variables X_{i}\in\{0,1\} which indicate whether v_{i} is a member of this set. We then use a sequential, rules-based decoder that strictly enforces the problem constraints to arrive at the final set of interest. We now discuss the individual elements of our pipeline. 3.1 GNN Encoder Our GNN encoder relies on the Graph Combinatorial Optimization Network (GCON) architecture introduced in 45 . Unlike local message-passing GNNs such as GCN, GIN or GAT which effectively perform low-pass filtering over the graph, GCON uses a rich bank of multi-scale wavelet filters inspired by the geometric scattering transform ( 14 ; 13 ; 54 ) . 45 demonstrate that such networks can learn rich node representations, and avoid typical information bottlenecks of localized message-passing. We follow a a common architectural design of a linear layer before and after the GNN layers, as well as nonlinearities (leaky ReLU), batch normalization, and graph size normalization after each layer. We additionally concatenate all GNN layer outputs as our input to the final linear layer, which empirically helps performance over most tasks. We apply sigmoid activation after the final layer to map the outputs to \left[0,1\right] . As in 45 , we use the vertex degrees, local clustering coefficients, and triangle counts as node features. Empirically, this performed superior compared to the Dirac encodings used in 19 and largely on par with Laplacian and random walk-based encodings. The output of our GNN is a vector \operatorname{\mathbf{p}} where \operatorname{\mathbf{p}}_{i} is thought of as the probability that v_{i} is in the set of interest. 1 1 1 For K -coloring, we output K vectors where (\mathbf{p}_{k})_{i} is thought of as the probability that v_{i} has color k . Table 2 : Performance comparison of GCON with other baselines on RB-small datasets (Mean \pm Std). The best deep learning-based method is listed in gold , second best in silver . † indicates Gurobi outperforms all deep learning methods. Method Type MVC \downarrow MClique \uparrow MIS \uparrow True Size — 206.95 19.07 20.07 GUROBI OR — † 19.05 † † 19.98 † GFN SSL — 16.24 19.18 GCN SSL-GNN 221.56 \pm 0.05 15.33 \pm 0.04 17.67 \pm 0.20 GIN SSL-GNN 221.63 \pm 0.23 15.28 \pm 0.14 17.50 \pm 0.04 GATv2 SSL-GNN 220.76 \pm 2.26 15.56 \pm 0.09 17.58 \pm 0.07 GCON SSL-GNN 211.69 \pm 0.16 16.92 \pm 0.13 18.12 \pm 0.11 3.2 Sequential Decoder The sequential decoder processes the probabilistic output \mathbf{p} of the GNN encoder and enforces the hard problem constraints to arrive at a valid solution. In each case, we order the nodes by probability of being included in the solution set (based on \operatorname{\mathbf{p}} ) and initialize the solution set S^{*}=\varnothing . We then iterate over the ordered node set and add v_{i} to S^{*} only if it does not violate the problem constraints. As demonstrated in 19 , this blueprint follows the method of conditional expectation ( 36 ) . However, we note that this approach does not guarantee the optimal solution, especially when the GNN encoder assigns similar high probabilities to multiple nodes that may constitute distinct solution sets. Therefore, we employ k seeds where each seed selects a different node to initialize the set with (choosing the k nodes with the highest probabilities as initial nodes). We construct k sets, S^{*}_{1},\ldots S^{*}_{k} , and return the largest or smallest depending on the task. We note that while a similar approach is proposed in 45 , their implementation constructed the k sets sequentially, leading to dramatically increased runtimes. By contrast, our sets are constructed in a parallelized manner, enabling the efficient use of higher k . 3.3 Objective Functions As objective functions, we rely on the Ising formulations of the CO problems, as provided in 29 and displayed in Table 1 . When training our network, we optimize the probabilistic vector \mathbf{p} rather than X\in\{0,1\}^{N} . The Ising model and equivalent quadratic unconstrained binary optimization (QUBO) formulations have emerged as an effective framework to unify many CO problems by assigning an energy function (namely the Hamiltonian) to every task such that its optimal solution minimizes the total energy ( 29 ; 23 ; 17 ; 39 ) . The loss functions for MIS, MDS, MaxClique and MDS involve two terms A and B that can be tuned additionally; the ratio of A to B controls how strongly to penalize constraint violations in relation to maximizing or minimizing the size of the objective set. Setting A