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ős--Rényi 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× 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ős--Rényi graphs with edge probability p=0.35, the learned coarsening policy generalizes effectively across both unseen graph densities and structurally different graph families.
Related
- Maximum edge overlap between independent random regular graphs
- Hitting Maximum Independent Sets in Dense and Highly Connected Graphs
- Constructing two completely independent spanning trees in dual-cubes
- Efficient estimation and the cost of complete-case coarsening under monotone sequential MAR
- Formation of clusters and coarsening in weakly interacting diffusions
BibTeX
@misc{chen2026dualgnn,
title = {{Dual-GNN Multilevel Coarsening for Maximum Independent Set}},
author = {Tianfeng Chen and Xianyue Li},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.25149},
eprint = {2609.25149},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.25149},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Dual-GNN Multilevel Coarsening for Maximum Independent Set
AU - Tianfeng Chen
AU - Xianyue Li
PY - 2026
DA - 2026/09/23
PB - arXiv
DO - 10.48550/arxiv.2609.25149
UR - https://arxiv.org/abs/2609.25149
AB - 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ős--Rényi 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× 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ős--Rényi graphs with edge probability p=0.35, the learned coarsening policy generalizes effectively across both unseen graph densities and structurally different graph families.
ER -