Dual-GNN Multilevel Coarsening for Maximum Independent Set

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.