Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?

A key challenge in deriving unified neural solvers for combinatorial optimization (CO) is efficient generalization of models between one set of tasks to new tasks not used during the initial training process. To address it, we first establish a new GNN encoder, 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 to 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.

Combinatorial optimization (CO) is a mathematical problem family concerned with finding the best solution from a finite, discrete set of solutions, where exhaustively searching for every possible solution is typically not possible. Many CO problems are suitable to be represented as graphs, flexible data structures that consists of objects (called nodes or vertices) and edges that denote the existence (or a type of) a relationship between objects. CO problems on graphs include maximum clique (finding the largest subset of nodes that are all connected to each other), maximum independent set (finding the largest subset of nodes that are not directly connected to each other with an edge), among many others. Interestingly, many CO problems can be "converted" to each other by transforming a graph according to certain rules (called reductions) to obtain another graph, such that e.g., the maximum clique on the original graph is equivalent to the maximum independent set of the other graph. In this paper, we first explore the question "If the rules to convert one CO problem graph to another are simple, does that mean a neural network can use knowledge from the first problem effectively to solve the second?" We first show that the real determinant of whether a neural network can use one task to solve another relies more on how much the rules change the graph structure, rather than just the simplicity of the rules themselves, though there is correlation between the two. In light of this, we propose a neural network framework for graphs that can learn on multiple CO tasks simultaneously without requiring any labels. Finally, we explore strategies inspired by CO reductions on which tasks to train neural networks with so that they generalize to unseen tasks most effectively.