The Dual-GNN Multilevel Coarsening framework uses learning to guide multilevel graph coarsening while retaining combinatorial search for final decision making and achieves the best mean solution quality among all evaluated methods.
Abstract
The maximum independent set (MIS) problem is a fundamental NP-hard combinatorial optimization problem with applications in scheduling, resource allocation, and network analysis. Exact solvers can provide high-quality solutions or optimality certificates, but their computational cost grows rapidly with graph size, while hand-crafted heuristics improve scalability at the expense of guarantees. Learning-based methods offer an alternative by exploiting structural patterns across graph instances, yet directly predicting independent sets can make global coordination difficult on large graphs. We instead use learning to guide multilevel graph coarsening while retaining combinatorial search for final decision making. Our Dual-GNN Multilevel Coarsening framework uses a Partition GNN to score candidate contractions and a Representative GNN to select top-k local independent-set states for each final cluster. Experiments on Erd\H{o}s--R\'enyi graphs with up to 2,000 vertices demonstrate a favorable quality--runtime trade-off. On 500-vertex instances with certified optima, our method achieves an average independent-set size of 19.20, corresponding to 99.5\% of the optimal value of 19.30, while reducing the mean wall-clock time from 643.57 seconds for exact solving to 3.41 seconds, yielding an approximately 189$\times$ speedup. On larger graphs with 1,000 and 2,000 vertices, our method achieves the best mean solution quality among all evaluated methods. Moreover, although trained only on Erd\H{o}s--R\'enyi graphs with edge probability $p=0.35$, the learned coarsening policy generalizes effectively across both unseen graph densities and structurally different graph families.
A graph-aware tiny recursive model that iterates on a latent state with adaptive halting and needs only a lightweight problem-specific decoder is proposed, which achieves a better balance between solution quality and inference speed on both the Traveling Salesman Problem and the Maximum Independent Set problem.
Graph coarsening reduces the large Quadratic Unconstrained Binary Optimization (QUBO) formulations arising when vehicle-routing problems are solved by quantum annealing. Nearby customers with compatible time windows are merged into super-nodes, the reduced problem is solved, and the solution is expanded to the original...
K-adaptive Ensembled Partitioning (KEP) is presented, which combines recursive bisection and direct 𝐾 -way search and replaces hard-feasibility Fiduccia–Mattheyses (FM) with an augmented-Lagrangian refinement step (AL-FM) that can cross short infeasible regions before repairing balance.
This paper finds that solutions produced at the early search stage of MILP solvers are often structurally close to the solutions found after full-budget search, and proposes a new solver-informed paradigm that shifts the learning target from variable assignment to early-to-final consistency.
Guanli Li, Chengrui Gao, Chenguang Wang et al.· 0 citations
It is demonstrated that while algorithms do eventually converge to theoretically predicted bounds, this convergence can be remarkably slow; in the intermediate regime where instances are already highly constrained, local algorithms achieve solutions substantially better than their predicted performance in the high-cons...
A. Umar, Jean Barbier, Matthieu Jonckheere et al.· 0 citations
This paper develops a differentiable framework for multi-objective MaxCut by combining an adjacency-based quadratic formulation with linear scalarization, thereby reducing the problem to a preference-conditioned single-objective signed-weight MaxCut problem.
Jing-Hang Huang, Cheng-Han Huang, Alvaro Velasquez et al.· 0 citations
Related blog posts
Microsoft Research Blog· microsoft.comNov 16, 2026
AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.
MIT News · Artificial Intelligence· news.mit.eduNov 13, 2026