Skip to content

Dual-GNN Multilevel Coarsening for Maximum Independent Set

Sep 2026 · arXiv.org · Vol abs/2609.25149 · 0 citations · 13 references
Computer Science Mathematics

TL;DR

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.

View source

Similar papers

#machine learning Preprint Sep 2026

Compute Time Scaling with Recursive Models for Combinatorial Optimization

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.

Zheng-Xin Zhang, P. Swoboda · 0 citations
#machine learning Preprint Sep 2026

GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer

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...

Y. K. Rezk, Paweł Gora · 0 citations

FastPart: A Powerful Portfolio-based Hypergraph Partitioner

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.

Unknown authors · 0 citations
Preprint Aug 2026

Learning Early-to-Final Solution Consistency for MILP Acceleration

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
Preprint Aug 2026

On the Slow Convergence to Trivial Solutions of Algorithms for Hard Optimization Problems

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
Preprint Aug 2026

Parallelizable Gradient-Based Optimization For Multi-Objective MaxCut

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 Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

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.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.