Metraipolis › archive › dc_a61fb910f3a0

Dual-GNN Multilevel Coarsening for Maximum Independent Set — arXiv:2609.25149

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.25149
License (as archived)
CC0-1.0
Archived
2026-10-08T15:07:20.634Z
SHA-256 of the archived text
856065a66c7840c069d51c2d4e450cf448a3bb622f8c69f5ef2f8a0544aa9a8a
Stable URL of this page
https://metraipolis.com/documento/dc_a61fb910f3a0

How to cite

Dual-GNN Multilevel Coarsening for Maximum Independent Set — arXiv:2609.25149 — arXiv (en), https://arxiv.org/abs/2609.25149 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a61fb910f3a0 (Metraipolis archive dc_a61fb910f3a0, sha256 856065a66c7840c069d51c2d4e450cf448a3bb622f8c69f5ef2f8a0544aa9a8a)
BibTeX
@misc{dca61fb910f3a0,
  title = {Dual-GNN Multilevel Coarsening for Maximum Independent Set — arXiv:2609.25149},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.25149},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a61fb910f3a0; sha256 856065a66c7840c069d51c2d4e450cf448a3bb622f8c69f5ef2f8a0544aa9a8a},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.25149. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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$\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ő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.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-23 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.25149 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T14:37:29.379Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-23?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).