Optimal Transport–Guided Stochastic Control for Graph Combinatorial Optimization

We propose an OT-guided sampling framework for solving graph combinatorial optimization through exact multilinear relaxation. Graph combinatorial optimization problems can be written as quadratic unconstrained binary optimization(QUBO). Leveraging a classical result in combinatorial optimization, we obtain a continuous multi-linear relaxation of QUBO that is exact, in the sense that it preserves the optimal binary solutions. The challenge is that the resulting energy landscape is highly nonconvex. We address this by treating the objective as an energy function and optimizing via sampling from the induced Boltzmann distribution to escape poor local optima. Viewing sampling as transporting a simple reference distribution to the target distribution, we use optimal transport to characterize more efficient probability flow and derive a stochastic optimal control problem whose solution yields an optimal sampling dynamics. We parameterize the control policy with graph neural networks to approximate the optimal control. Experiments show improved solution quality and efficiency over strong combinatorial and learning-based baselines.

Many important planning problems, such as selecting key nodes in a network or dividing a graph into well-connected parts, are difficult because the number of possible solutions grows extremely quickly. This paper studies how machine learning can help search for high- quality solutions to such graph optimization problems. We first turn the discrete problem into an equivalent continuous form, and then design a sampling process that is guided by ideas from optimal transport, a mathematical framework for moving probability distributions efficiently. A graph neural network is trained to guide this process so that it can find better solutions more efficiently. Experiments on several standard graph optimization tasks show that the proposed method can outperform strong heuristic and learning-based baselines.