Dual-GNN Multilevel Coarsening for Maximum Independent Set

# Dual-GNN Multilevel Coarsening for Maximum Independent Set
Source: [https://arxiv.org/html/2609.25149](https://arxiv.org/html/2609.25149)
Tianfeng ChenAffiliation:School of Mathematics and StatisticsAffiliation:Lanzhou UniversityEmail:[chentf2025@lzu\.edu\.cn](mailto:)Xianyue Li\*Affiliation:School of Mathematics and StatisticsAffiliation:Lanzhou UniversityEmail:[lixianyue@lzu\.edu\.cn](mailto:)

###### 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×\\timesspeedup\. 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 probabilityp=0\.35p=0\.35, the learned coarsening policy generalizes effectively across both unseen graph densities and structurally different graph families\.

## 1Introduction

The MIS problem asks for the largest subset of vertices in a graph such that no two selected vertices are adjacent\. As a fundamental NP\-hard combinatorial optimization problem, MIS arises in applications including scheduling, resource allocation, network design, and conflict\-free selection\. It is also closely related to other canonical graph problems, such as maximum clique and minimum vertex cover\. Despite its simple formulation, solving MIS becomes increasingly difficult as the graph grows, since a locally promising vertex decision may exclude many combinations that would lead to a better global solution\.

Existing approaches to MIS can be broadly divided into exact and heuristic methods\. Exact MIS algorithms typically explore a branch\-and\-bound search tree, often interleaving branching with problem\-specific reduction rules in the branch\-and\-reduce paradigm\([Xiao and Nagamochi, 2017](https://arxiv.org/html/2609.25149#bib.bib1)\)\. Such methods are highly effective on many practical instances, but exact optimization generally requires combinatorial search whose cost grows rapidly with graph size and structural complexity\. By contrast, specialized heuristic solvers combine kernelization, evolutionary search, and local improvement to find large independent sets on graphs where exact optimization becomes computationally expensive\. These methods often achieve strong empirical performance, but their reduction, search, and refinement strategies are largely hand\-designed and may require substantial computation to adapt to different graph distributions\.

Learning\-based combinatorial optimization offers a complementary direction\. Graph neural networks \(GNNs\) have been used to predict vertex\-level solution likelihoods and guide tree search\([Li et al\., 2018](https://arxiv.org/html/2609.25149#bib.bib2)\), to optimize distributions over feasible sets without supervised labels\([Karalias and Loukas, 2020](https://arxiv.org/html/2609.25149#bib.bib3)\), and to guide recursive decisions through self\-training\([Brusca et al\., 2023](https://arxiv.org/html/2609.25149#bib.bib4)\)\. By learning from families of related graph instances, these approaches can capture structural patterns that are difficult to encode using fixed heuristics\. Nevertheless, constructing a globally consistent independent set from local predictions remains challenging, as selecting one vertex can affect the feasibility and utility of many subsequent choices\. Moreover, directly applying a GNN together with a search procedure to the original graph does not fundamentally reduce the computational burden associated with optimization over a large decision space\. Recent evaluations of learning\-guided tree search for MIS further indicate that strong performance may depend substantially on classical algorithmic components such as kernelization, rather than on learned predictions alone\([Böther et al\., 2022](https://arxiv.org/html/2609.25149#bib.bib13)\)\. This observation motivates architectures in which learning and combinatorial optimization have clearly separated and measurable roles\.

To reduce the cost of combinatorial search, we propose*Dual\-GNN Multilevel Coarsening*, a task\-aligned framework that contracts the original graph into a smaller optimization problem\. Unlike conventional coarsening methods that primarily preserve spectral or structural properties\([Jin et al\., 2020](https://arxiv.org/html/2609.25149#bib.bib5)\), our method learns coarsening decisions from their effects on the recovered MIS objective\. A Partition GNN scores candidate contractions between clusters, while a Representative GNN ranks the local independent\-set states retained for coarse optimization\. The resulting reduced problem is solved using completion\-aware search, after which the selected coarse solution is decoded and completed on the original graph to produce a valid maximal independent set\.

Experiments on Erdős–Rényi and structured graph families demonstrate favorable quality–runtime trade\-offs across graph sizes and densities\. On 500\-vertex instances with certified optima, our method obtains an average independent\-set size of19\.2019\.20, corresponding to99\.5%99\.5\\%of the optimal value of19\.3019\.30, while reducing the mean empirical wall\-clock time from643\.57643\.57to3\.413\.41seconds\. Across graph sizes from 300 to 2,000 vertices, it consistently outperforms the evaluated learning\-based baselines in mean solution quality\.

Our main contributions are:

- •We introduce a dual\-GNN multilevel framework that learns both task\-aligned cluster contractions and representative\-state selection for MIS\.
- •We formulate coarsening as a bounded\-state compression procedure that preserves multiple feasible local independent\-set configurations within each cluster, enabling global compatibility to be resolved on a substantially smaller conflict graph\.
- •We demonstrate substantial empirical runtime reductions and near\-optimal solution quality across multiple graph sizes, densities, and topology families\.

## 2Related Work

#### Heuristic MIS solvers\.

A simple approach to MIS is greedy construction, which repeatedly selects a feasible vertex according to a fixed or dynamically updated priority\. Greedy algorithms are efficient and always return a maximal independent set, but their solution quality depends strongly on the selection rule\. More advanced solvers combine reductions with global search and local improvement\. ReduMIS, for example, integrates kernelization with evolutionary search to compute high\-quality independent sets on large graphs\([Lamm et al\., 2017](https://arxiv.org/html/2609.25149#bib.bib6)\)\. Another line of work formulates MIS as continuous optimization\. pCQO\-MIS optimizes a non\-convex clique\-informed quadratic objective from multiple initializations and converts the resulting solutions into maximal independent sets\([Alkhouri et al\., 2025](https://arxiv.org/html/2609.25149#bib.bib7)\)\. Unlike distribution\-trained models, pCQO\-MIS performs differentiable optimization separately for each input instance\.

#### Learning\-based MIS solvers\.

Learning\-based methods use GNNs to capture recurring structural patterns across graph instances\. GCN\-TreeSearch predicts vertex\-level solution likelihoods and uses them to guide tree search\([Li et al\., 2018](https://arxiv.org/html/2609.25149#bib.bib2)\)\. Erdős Goes Neural learns a distribution over feasible sets through an unsupervised objective followed by deterministic decoding\([Karalias and Loukas, 2020](https://arxiv.org/html/2609.25149#bib.bib3)\)\. Dynamic MIS instead uses a GNN to guide recursive subproblem selection and improves the policy through self\-training\([Brusca et al\., 2023](https://arxiv.org/html/2609.25149#bib.bib4)\)\. Our approach differs from these methods by applying learning to multilevel coarsening: the two GNNs determine which clusters to contract and which local states to retain before the reduced combinatorial search\.

#### Graph coarsening\.

Graph coarsening became widely established through multilevel graph partitioning, where a graph is repeatedly contracted, partitioned at the coarsest level, and then uncoarsened and refined\([Karypis and Kumar, 1998](https://arxiv.org/html/2609.25149#bib.bib8)\)\. More recent methods primarily aim to preserve spectral or structural properties\([Loukas and Vandergheynst, 2018](https://arxiv.org/html/2609.25149#bib.bib10);[Jin et al\., 2020](https://arxiv.org/html/2609.25149#bib.bib5)\), while Cai et al\. use a GNN to learn coarse edge weights under general preservation objectives\([Cai et al\., 2021](https://arxiv.org/html/2609.25149#bib.bib9)\)\. Such objectives are not necessarily aligned with MIS, since a structurally reasonable contraction may remove useful independent\-set configurations\. Our method instead learns contraction and representative\-state scores from rollout\-based estimates of the final MIS quality\.

## 3Preliminaries

#### Maximum independent set\.

LetG=\(V,E\)G=\(V,E\)be an undirected graph with vertex setVVand edge setEE\. A subsetI⊆VI\\subseteq Vis an independent set if no two vertices inIIare adjacent\. The maximum independent set problem seeks an independent set of maximum cardinality\. Using a binary variablexv∈\{0,1\}x\_\{v\}\\in\\\{0,1\\\}to indicate whether vertexvvis selected, the problem can be formulated as

α⁡\(G\)\\displaystyle\\alpha\(G\)=max⁡∑v∈V𝐱∈\{0,1\}\|V\|⁡xv\\displaystyle=\\max\_\{\\mathbf\{x\}\\in\\\{0,1\\\}^\{\|V\|\}\}\\sum\_\{v\\in V\}x\_\{v\}\(1\)s\.t\.\\displaystyle\\text\{s\.t\.\}xu\+xv≤1,∀\(u,v\)∈E\.\\displaystyle x\_\{u\}\+x\_\{v\}\\leq 1,\\qquad\\forall\(u,v\)\\in E\.An independent set is*maximal*if no additional vertex can be added without violating independence\.

#### Graph neural networks\.

A graph neural network constructs a representation𝐡v\(k\)\\mathbf\{h\}\_\{v\}^\{\(k\)\}for each vertex by repeatedly aggregating information from its neighbors\([Kipf and Welling, 2017](https://arxiv.org/html/2609.25149#bib.bib11);[Hamilton et al\., 2017](https://arxiv.org/html/2609.25149#bib.bib12)\)\. A generic message\-passing layer can be written as

𝐦v\(k\)=AGG\(k\)⁡\(\{𝐡u\(k−1\):u∈𝒩⁡\(v\)\}\),𝐡v\(k\)=UPDATE\(k\)⁡\(𝐡v\(k−1\),𝐦v\(k\)\),\\mathbf\{m\}\_\{v\}^\{\(k\)\}=\\operatorname\{AGG\}^\{\(k\)\}\\left\(\\left\\\{\\mathbf\{h\}\_\{u\}^\{\(k\-1\)\}:u\\in\\mathcal\{N\}\(v\)\\right\\\}\\right\),\\qquad\\mathbf\{h\}\_\{v\}^\{\(k\)\}=\\operatorname\{UPDATE\}^\{\(k\)\}\\left\(\\mathbf\{h\}\_\{v\}^\{\(k\-1\)\},\\mathbf\{m\}\_\{v\}^\{\(k\)\}\\right\),\(2\)where𝒩⁡\(v\)\\mathcal\{N\}\(v\)denotes the neighborhood ofvv\. In this work, GNNs are applied not only to the original graph but also to quotient graphs, where each node represents a cluster of original vertices\.

#### Multilevel graph coarsening\.

Graph coarsening constructs a sequence of progressively smaller graphs by grouping vertices into clusters\. At levelℓ\\ell, let

𝒞\(ℓ\)=\{C1\(ℓ\),…,Cnℓ\(ℓ\)\}\\mathcal\{C\}^\{\(\\ell\)\}=\\left\\\{C\_\{1\}^\{\(\\ell\)\},\\ldots,C\_\{n\_\{\\ell\}\}^\{\(\\ell\)\}\\right\\\}\(3\)be a partition of the original vertex set\. Each cluster is represented as a node in the quotient graphG\(ℓ\)G^\{\(\\ell\)\}, and two coarse nodes are connected when their corresponding clusters share at least one edge in the original graph\. A contraction combines two disjoint clusters,

Ci​j\(ℓ\+1\)=Ci\(ℓ\)∪Cj\(ℓ\)\.C\_\{ij\}^\{\(\\ell\+1\)\}=C\_\{i\}^\{\(\\ell\)\}\\cup C\_\{j\}^\{\(\\ell\)\}\.\(4\)Contracting a set of non\-overlapping pairs produces the next level of the hierarchy,

G\(0\)→G\(1\)→⋯→G\(L\),G\(0\)=G,G^\{\(0\)\}\\rightarrow G^\{\(1\)\}\\rightarrow\\cdots\\rightarrow G^\{\(L\)\},\\qquad G^\{\(0\)\}=G,\(5\)with\|V\(ℓ\+1\)\|<\|V\(ℓ\)\|\|V^\{\(\\ell\+1\)\}\|<\|V^\{\(\\ell\)\}\|\. Classical multilevel methods select contractions using structural heuristics\([Karypis and Kumar, 1998](https://arxiv.org/html/2609.25149#bib.bib8)\)\. Our method instead uses learned, task\-aligned scores to construct the hierarchy and preserve local decisions that are useful for the final MIS solution\.

## 4Dual\-GNN Multilevel Coarsening

### 4\.1Framework Overview

Figure[1](https://arxiv.org/html/2609.25149#S4.F1)provides an overview of our framework\. Given an input graphG=\(V,E\)G=\(V,E\), the method first constructs a multilevel coarsening hierarchy\. Initially, each vertex forms a singleton cluster\. At every level, the current clusters are represented as nodes in a quotient graph, whose edges summarize the connectivity between clusters\. The Partition GNN encodes this quotient graph and scores candidate cluster pairs\. Based on these scores, a set of non\-overlapping pairs is selected as a matching and contracted to form the next coarsening level\. This process is repeated until a stopping criterion is reached, while a maximum cluster size limits the complexity of subsequent local optimization\.

After constructing the hierarchy, we enumerate feasible local independent\-set states within each final cluster\. The Representative GNN evaluates these states using both their local properties and the context provided by the final quotient graph\. Only a bounded set of representative states is retained for each cluster\. The retained states define a coarse conflict graph: each node represents a local independent set, its weight is the number of selected original vertices, and an edge indicates that two states are mutually exclusive or contain conflicting vertices in the original graph\. Consequently, the size of the coarse search space is controlled explicitly by the representative\-state budget rather than by the total number of locally enumerated states\.

The coarse conflict graph is then processed by a bounded combinatorial search to obtain candidate seeds\. Since the size of a coarse seed does not fully reflect its potential on the original graph, we use completion\-aware evaluation to rank candidates according to the independent sets obtained after decoding and residual completion\. The best candidate is mapped back to its original vertices and deterministically completed to a maximal independent set\.

![Refer to caption](https://arxiv.org/html/2609.25149v1/Dual_GNN_True_Compression_Pipeline_MIS_editable.png)Figure 1:Overview of the proposed Dual\-GNN Multilevel Coarsening framework
### 4\.2Partition GNN

The Partition GNN determines which clusters should be contracted at each level of the coarsening hierarchy\. Let𝒞\(ℓ\)=\{C1,…,Cmℓ\}\\mathcal\{C\}^\{\(\\ell\)\}=\\\{C\_\{1\},\\ldots,C\_\{m\_\{\\ell\}\}\\\}denote the current partition of the original vertex set, and letQ\(ℓ\)Q^\{\(\\ell\)\}be the corresponding quotient graph\. Our partitioning stage maintains only the vertex membership of each cluster\. Local independent\-set states are generated after the final coarsening level, which avoids an exponential growth of intermediate states\. Figure[2](https://arxiv.org/html/2609.25149#S4.F2)provides an overview of the Partition GNN pipeline for scoring candidate cluster contractions\.

Each quotient node is represented by a six\-dimensional feature vector

𝐱i=\[\|Ci\|n,\|∂Ci\|n,dQ​\(i\)mℓ−1,ρ⁡\(Ci\),d¯​\(Ci\)n,dmin​\(Ci\)n\]\.\\mathbf\{x\}\_\{i\}=\\left\[\\frac\{\|C\_\{i\}\|\}\{n\},\\;\\frac\{\|\\partial C\_\{i\}\|\}\{n\},\\;\\frac\{d\_\{Q\}\(i\)\}\{m\_\{\\ell\}\-1\},\\;\\rho\(C\_\{i\}\),\\;\\frac\{\\bar\{d\}\(C\_\{i\}\)\}\{n\},\\;\\frac\{d\_\{\\min\}\(C\_\{i\}\)\}\{n\}\\right\]\.\(6\)Here,∂Ci\\partial C\_\{i\}is the external boundary ofCiC\_\{i\},dQ​\(i\)d\_\{Q\}\(i\)is its degree in the quotient graph,ρ⁡\(Ci\)\\rho\(C\_\{i\}\)is its internal edge density, andd¯​\(Ci\)\\bar\{d\}\(C\_\{i\}\)anddmin​\(Ci\)d\_\{\\min\}\(C\_\{i\}\)are the mean and minimum original degrees of the vertices in the cluster\. To distinguish weak and strong interactions between clusters, an edge betweenCiC\_\{i\}andCjC\_\{j\}is assigned the normalized weight

ωi​j=\|E⁡\(Ci,Cj\)\|\|Ci\|​\|Cj\|,\\omega\_\{ij\}=\\frac\{\|E\(C\_\{i\},C\_\{j\}\)\|\}\{\|C\_\{i\}\|\|C\_\{j\}\|\},\(7\)whereE⁡\(Ci,Cj\)E\(C\_\{i\},C\_\{j\}\)denotes the set of original edges crossing between the two clusters\.

We apply residual GraphSAGE layers to the weighted quotient graph to obtain a contextual embedding𝐡i\\mathbf\{h\}\_\{i\}for every cluster\. For each admissible pair\(Ci,Cj\)\(C\_\{i\},C\_\{j\}\), we additionally construct a pairwise feature vector𝐩i​j\\mathbf\{p\}\_\{ij\}containing the cross\-edge density, boundary Jaccard similarity, cluster\-size balance, quotient degree difference, merged boundary size and merged cluster size\. The learned contraction utility is computed as

ui​j=MLPP\(\[𝐡i\+𝐡j∥\|𝐡i−𝐡j\|∥𝐡i⊙𝐡j∥𝐩i​j\]\)\.u\_\{ij\}=\\operatorname\{MLP\}\_\{P\}\\left\(\\left\[\\mathbf\{h\}\_\{i\}\+\\mathbf\{h\}\_\{j\}\\;\\middle\\\|\\;\|\\mathbf\{h\}\_\{i\}\-\\mathbf\{h\}\_\{j\}\|\\;\\middle\\\|\\;\\mathbf\{h\}\_\{i\}\\odot\\mathbf\{h\}\_\{j\}\\;\\middle\\\|\\;\\mathbf\{p\}\_\{ij\}\\right\]\\right\)\.\(8\)The sum, absolute difference, and element\-wise product makeui​ju\_\{ij\}invariant to the ordering of the two clusters\.

![Refer to caption](https://arxiv.org/html/2609.25149v1/partition_gnn_architecture_editable.png)Figure 2:Partition GNN–Guided Cluster Contraction PipelineOnly pairs satisfying\|Ci\|\+\|Cj\|≤B\|C\_\{i\}\|\+\|C\_\{j\}\|\\leq Bare considered\. We define the structural contraction utility as

ui​jstruct=−\|\(∂Ci∪∂Cj\)∖\(Ci∪Cj\)\|n\+0\.35​\|∂Ci∩∂Cj\|max⁡\(\|∂Ci∪∂Cj\|,1\)−0\.10​ωi​j\.u\_\{ij\}^\{\\mathrm\{struct\}\}=\-\\frac\{\|\(\\partial C\_\{i\}\\cup\\partial C\_\{j\}\)\\setminus\(C\_\{i\}\\cup C\_\{j\}\)\|\}\{n\}\+0\.35\\frac\{\|\\partial C\_\{i\}\\cap\\partial C\_\{j\}\|\}\{\\max\(\|\\partial C\_\{i\}\\cup\\partial C\_\{j\}\|,1\)\}\-0\.10\\omega\_\{ij\}\.\(9\)The learned and structural utilities are combined as

qi​j=ui​jstruct\+λP​ui​j,λP=0\.5,q\_\{ij\}=u\_\{ij\}^\{\\mathrm\{struct\}\}\+\\lambda\_\{P\}u\_\{ij\},\\qquad\\lambda\_\{P\}=0\.5,\(10\)where a larger value indicates a more favorable contraction\. The coefficientλP\\lambda\_\{P\}is selected on the validation set and fixed for all experiments\. Candidate pairs are sorted in descending order ofqi​jq\_\{ij\}, after which a greedy matching selects non\-overlapping contractions\. In the variant without the Partition GNN, the learned term is removed, and the same candidates are ranked usingui​jstructu\_\{ij\}^\{\\mathrm\{struct\}\}alone\.

### 4\.3Representative GNN

After the final coarsening level, each cluster may have several feasible local independent\-set states\. Keeping all of them would reduce the efficiency gained from coarsening\. However, selecting states only by their size may remove some states that work better with the rest of the graph\. We therefore use a Representative GNN to rank the feasible local states of each final cluster according to both their local quality and their compatibility with the surrounding graph\. Figure[3](https://arxiv.org/html/2609.25149#S4.F3)provides an overview of the Representative GNN pipeline for scoring and selecting representative local states for each final cluster\.

For a final clusterCiC\_\{i\}, we enumerate its non\-empty local independent sets,

𝒮i=\{S⊆Ci:S≠∅,\(u,v\)∉E∀u,v∈S\}\.\\mathcal\{S\}\_\{i\}=\\left\\\{S\\subseteq C\_\{i\}:S\\neq\\emptyset,\\;\(u,v\)\\notin E\\ \\forall u,v\\in S\\right\\\}\.\(11\)The empty state is represented implicitly by not selecting any state from the cluster during coarse optimization\. Each stateS∈𝒮iS\\in\\mathcal\{S\}\_\{i\}is associated with its cardinalityw⁡\(S\)=\|S\|w\(S\)=\|S\|and its external blocking set

B⁡\(S\)=\{v∈V∖Ci:∃u∈S​such that​\(u,v\)∈E\}\.B\(S\)=\\left\\\{v\\in V\\setminus C\_\{i\}:\\exists u\\in S\\text\{ such that \}\(u,v\)\\in E\\right\\\}\.\(12\)A stateSSdominates another stateTTifw⁡\(S\)≥w⁡\(T\)w\(S\)\\geq w\(T\)andB⁡\(S\)⊆B⁡\(T\)B\(S\)\\subseteq B\(T\), since thenSSis not worse for any assignment outside the cluster\. States with identical blocking sets are deduplicated, and dominated states are removed before learning ranking\.

The Representative GNN encodes the final quotient graph using the same six\-dimensional cluster descriptors introduced in Equation[6](https://arxiv.org/html/2609.25149#S4.E6)\. Quotient edges are weighted by their normalized cross\-edge densities from Equation[7](https://arxiv.org/html/2609.25149#S4.E7)\. Residual GraphSAGE layers then produce a context\-dependent embedding𝐡i\\mathbf\{h\}\_\{i\}for every final cluster\. This embedding allows the state ranker to account for how the cluster is situated relative to the other clusters rather than evaluating each local state in isolation\.

For each candidate stateS∈𝒮iS\\in\\mathcal\{S\}\_\{i\}, we construct the six\-dimensional state feature vector

𝐳i​S=\[\|S\|\|Ci\|,\|B⁡\(S\)\|n,d¯​\(S\)n,dmin​\(S\)n,\|B⁡\(S\)\|max⁡\(\|∂Ci\|,1\),\|S\|wimax\],\\mathbf\{z\}\_\{iS\}=\\left\[\\frac\{\|S\|\}\{\|C\_\{i\}\|\},\\;\\frac\{\|B\(S\)\|\}\{n\},\\;\\frac\{\\bar\{d\}\(S\)\}\{n\},\\;\\frac\{d\_\{\\min\}\(S\)\}\{n\},\\;\\frac\{\|B\(S\)\|\}\{\\max\(\|\\partial C\_\{i\}\|,1\)\},\\;\\frac\{\|S\|\}\{w\_\{i\}^\{\\max\}\}\\right\],\(13\)whereB⁡\(S\)B\(S\)is the set of external vertices blocked bySS,d¯​\(S\)\\bar\{d\}\(S\)anddmin​\(S\)d\_\{\\min\}\(S\)are respectively the mean and minimum original\-graph degrees of the vertices selected bySS, and

wimax=maxT∈𝒮i⁡\|T\|w\_\{i\}^\{\\max\}=\\max\_\{T\\in\\mathcal\{S\}\_\{i\}\}\|T\|\(14\)is the cardinality of the largest local independent\-set state in clusterCiC\_\{i\}\. These features describe the local solution size, its external conflicts, the degree characteristics of its selected vertices, and its quality relative to the other states of the same cluster\. The Representative GNN combines these local features with the embedding of the corresponding cluster:

ri​S=MLPR⁡\(\[𝐡i∥𝐳i​S\]\),r\_\{iS\}=\\operatorname\{MLP\}\_\{R\}\\left\(\\left\[\\mathbf\{h\}\_\{i\}\\;\\middle\\\|\\;\\mathbf\{z\}\_\{iS\}\\right\]\\right\),\(15\)where𝐳i​S\\mathbf\{z\}\_\{iS\}denotes the state\-level feature vector andri​Sr\_\{iS\}is the learned representative score\.

States are ranked independently within each cluster according tori​Sr\_\{iS\}\. We retain the top\-kkstates in each cluster, wherek=3k=3is selected on the validation set\. A sensitivity analysis ofkkis provided in Appendix[5](https://arxiv.org/html/2609.25149#A1.F5)\. The retained states form the nodes of the subsequent coarse conflict graph\.

![Refer to caption](https://arxiv.org/html/2609.25149v1/reprenst.png)Figure 3:Representative GNN state\-selection pipeline
### 4\.4Coarse Optimization and Solution Recovery

The retained states define a weighted coarse conflict graph\. Each node represents a local stateSSand has weight\|S\|\|S\|\. Two states are connected if they belong to the same cluster or if their selected vertices conflict in the original graph\. We then solve a weighted MIS problem on this conflict graph to obtain a feasible coarse seed\.

Since the coarse objective does not account for vertices that can be added after decoding, candidate seeds are evaluated using

F⁡\(Iseed\)=\|Complete⁡\(Iseed,G\)\|\.F\(I\_\{\\mathrm\{seed\}\}\)=\\left\|\\operatorname\{Complete\}\(I\_\{\\mathrm\{seed\}\},G\)\\right\|\.\(16\)
Finally, the best seed is mapped back to its original vertices and greedily completed on the residual graph\. The resulting solution is independent by construction and maximal because completion terminates only when no additional feasible vertex can be added\.

### 4\.5Training the Dual GNNs

Both GNNs are trained using rollout\-derived supervision\. For the Partition GNN, we generate several candidate matchings at each coarsening level, execute the remaining coarsening and solution\-recovery pipeline, and use the final MIS size as the utility of each matching\. The network is trained with a ranking loss that assigns higher scores to matchings producing larger recovered independent sets\.

For the Representative GNN, each feasible local state is fixed and greedily completed on the residual graph\. The size of the completed independent set is used as its rollout utility\. These utilities define soft ranking targets, and the network is trained using cross\-entropy\. We train the two models alternately: the Representative GNN is trained on hierarchies generated by the Partition GNN, after which the Partition GNN is updated using rollouts produced with the learned representative policy\. Both models are optimized using AdamW\.

## 5Experiments

### 5\.1Experimental Setup

#### Datasets and splits\.

We conduct the main experiments on Erdős–Rényi \(ER\) graphs with edge probabilityp=0\.35p=0\.35\. The training pool contains 800 graphs, consisting of 400 graphs with 100 vertices and 400 graphs with 300 vertices\. An additional set of 100 graphs with 500 vertices is reserved for validation and model selection\. For evaluation, we use 50 ER graphs for eachn∈\{100,300,500,1000,2000\}n\\in\\\{100,300,500,1000,2000\\\}, together with BA, SBM, and WS graphs withn=1000n=1000for structural\-shift evaluation\.

#### Baselines\.

We compare our method with both classical and learning\-based MIS approaches\. The classical baselines include a residual minimum\-degree greedy heuristic, an exact maximum\-clique solver applied to the complement graph and ReduMIS\([Lamm et al\., 2017](https://arxiv.org/html/2609.25149#bib.bib6)\)\.

The learning\-based baselines include Erdős Goes Neural\([Karalias and Loukas, 2020](https://arxiv.org/html/2609.25149#bib.bib3)\), Dynamic MIS\([Brusca et al\., 2023](https://arxiv.org/html/2609.25149#bib.bib4)\), and pCQO\-MIS\([Alkhouri et al\., 2025](https://arxiv.org/html/2609.25149#bib.bib7)\)\.

#### Implementation details\.

Both the Partition GNN and the Representative GNN use two residual GraphSAGE layers with a hidden dimension of 64\. At each coarsening level, the number of clusters is reduced by approximately 50%\. Coarsening terminates when the number of clusters reaches 25, when no sufficient set of admissible contractions remains, or after at most four coarsening rounds\. The maximum cluster size is set toB=8B=8to keep local\-state enumeration tractable\.

The two GNNs are trained using rollout\-derived supervision on the training split, and checkpoints are selected according to the recovered MIS objective on the validation split\. Experiments are conducted on a workstation equipped with an Intel Core i7\-10870H CPU and an NVIDIA GeForce RTX 3060 Laptop GPU with 6 GB of memory\. The implementation uses Python 3\.13\.5, PyTorch 2\.7\.1 with CUDA 11\.8, PyTorch Geometric 2\.6\.1, NumPy 2\.3\.3, NetworkX 2\.8\.8, and PySCIPOpt 5\.6\.0\.

### 5\.2Main Results

#### Solution Quality across Graph Sizes\.

We first evaluate the solution quality of all methods on the Erdős–Rényi test sets\. Each test set contains 50 independently generated graphs with edge probabilityp=0\.35p=0\.35\. We report the mean cardinality of the returned independent sets, where a larger value is better\. Certified optimal values are available for graphs with up to 500 vertices\.

Table 1:Solution quality on ER graphs\.Table[1](https://arxiv.org/html/2609.25149#S5.T1)compares the solution quality of different methods on ER graphs of varying sizes\. Each entry reports the mean MIS size and sample standard deviation over the same 50 test instances\. Overall, our method achieves the best or tied\-best solution quality among all non\-exact methods across all graph sizes\. For small instances withn=100n=100, our method reaches the optimal solution, matching pCQO\-MIS and ReduMIS\. Atn=300n=300andn=500n=500, it remains very close to the optimum and outperforms the other learning\-based and heuristic baselines\. As the graph size increases, the advantage becomes more evident\. Forn=1000n=1000andn=2000n=2000, where optimal solutions are unavailable, our method obtains the largest independent sets among all compared methods, achieving average solution sizes of 21\.28 and 23\.32, both exceeding those obtained by ReduMIS\. These results indicate that the proposed method maintains strong solution quality as the problem size grows and scales effectively to larger ER graphs\.

#### Runtime Comparison\.

We next compare the empirical solving time of the evaluated methods\. Table[2](https://arxiv.org/html/2609.25149#S5.T2)reports the mean wall\-clock time per graph\. Offline training time is excluded\. For the exact baseline, all instances with 100, 300, and 500 vertices are solved using an exact maximum\-clique solver on the complement graph\. Exact results are not available for the two largest graph sizes\.

Table 2:Mean solving time on ER graphs\.The exact solver becomes particularly expensive atn=500n=500, requiring 643\.57 seconds per graph on average\. In comparison, our method requires only 3\.41 seconds, yielding an approximately189×189\\timesspeedup while retaining 99\.5% of the optimal solution value\.

For ReduMIS, the internal search time is constrained to match the solving time of our method\. This limit controls only the internal search phase of ReduMIS and does not include graph conversion, preprocessing, initialization, process invocation, or solution parsing\. We therefore report the measured end\-to\-end wall\-clock time for all methods\. As a result, the observed runtime of ReduMIS can exceed its nominal internal search budget\.

Greedy and the direct prediction baselines are faster in absolute runtime, but Table[1](https://arxiv.org/html/2609.25149#S5.T1)shows that this is accompanied by a considerable reduction in solution quality\. Similarly, pCQO\-MIS is faster than our method on the two largest graph sizes, but returns independent sets that are smaller by 0\.82 vertices atn=1000n=1000and 2\.32 vertices atn=2000n=2000\. Overall, our method provides a favorable quality–runtime trade\-off: it exceeds the solution quality of ReduMIS while requiring substantially less computation\.

#### Generalization across Graph Densities\.

To evaluate robustness to changes in graph density, we test the models on ER graphs withn=500n=500and edge probabilities ranging from 0\.05 to 0\.70\. Each test set contains 50 independently generated graphs\. Our GNNs are trained only on ER graphs withp=0\.35p=0\.35and are applied to all other densities without retraining\.

Table 3:Solution quality across ER graph densities\.Note:Atp=0\.05p=0\.05andp=0\.10p=0\.10, pCQO\-MIS completed all 50 optimization batches but produced no binary assignment satisfying its released fixed\-point maximality check under the fixed GNM hyperparameters; we therefore report these runs asFail\.

Table[3](https://arxiv.org/html/2609.25149#S5.T3)shows that our method generalizes effectively across a broad range of graph densities despite being trained only atp=0\.35p=0\.35\. It consistently outperforms the greedy heuristic, Erdős Goes Neural, and Dynamic MIS\. Compared with pCQO\-MIS, our method obtains better results fromp=0\.20p=0\.20top=0\.50p=0\.50and remains within 0\.04 vertices atp=0\.70p=0\.70\.

Our method is also competitive with ReduMIS throughout the density range\. It outperforms ReduMIS atp=0\.20p=0\.20,p=0\.35p=0\.35andp=0\.50p=0\.50, trails it by only 0\.06 vertices atp=0\.70p=0\.70\. The larger gaps of 1\.36 and 0\.58 vertices atp=0\.05p=0\.05andp=0\.10p=0\.10indicate that very sparse graphs remain the most challenging density shift for the learned coarsening policy\. Nevertheless, even in this regime, our method improves substantially over the greedy and learning\-based prediction baselines\. The corresponding solving times across different graph densities are reported in Appendix Table[5](https://arxiv.org/html/2609.25149#A1.T5)\.

#### Generalization across Graph Structures\.

To further evaluate robustness to structural distribution shifts, we test our method on three families of high\-density synthetic graphs withn=1000n=1000: Barabási–Albert \(BA\), Stochastic Block Model \(SBM\), and Watts–Strogatz \(WS\) graphs\. These graph families respectively exhibit heterogeneous degree distributions, community structure, and small\-world characteristics\.

Table 4:Comparison across graphs with different structural properties atn=1000n=1000\.As shown in Table[4](https://arxiv.org/html/2609.25149#S5.T4), our method achieves the highest average MIS size on all three graph families, consistently outperforming the greedy heuristic, the direct learning\-based methods, pCQO\-MIS, and ReduMIS\. Compared with the strongest baseline, ReduMIS, our method improves the average solution size by 0\.48, 0\.38, and 0\.46 vertices on BA, SBM, and WS graphs, respectively\. The gains over pCQO\-MIS are more pronounced, reaching 2\.35, 2\.09, and 1\.46 vertices, while the substantially larger margins over Erdős Goes Neural and Dynamic MIS highlight the advantage of learning to coarsen the optimization problem rather than directly predicting solutions\. These consistent improvements indicate that the proposed framework generalizes effectively beyond the ER training distribution and remains robust to heterogeneous degree distributions, community structures, and small\-world topology\.

Due to space constraints, the ablation results for the Dual\-GNN architecture are presented in Figure[4](https://arxiv.org/html/2609.25149#A1.F4)in the appendix\. The state\-space compression statistics across different graph sizes are also reported in Table[6](https://arxiv.org/html/2609.25149#A1.T6)in the appendix\.

## 6Conclusion

We presented Dual\-GNN Multilevel Coarsening, a learning\-guided framework for efficiently finding large independent sets\. Rather than predicting a solution directly on the original graph, our approach learns how to reduce the optimization problem while preserving decisions that are useful for the final MIS objective\. The Partition GNN constructs a task\-aligned coarsening hierarchy, and the Representative GNN selects a compact set of local independent\-set states for coarse optimization\. Completion\-aware search and deterministic recovery then translate the reduced solution back to the original graph, guaranteeing that every returned solution is a valid maximal independent set\.

Future work could extend the multilevel coarsening framework to a broader range of combinatorial optimization problems\. In particular, it would be valuable to investigate whether task\-aligned coarsening strategies can be adapted to problems with different feasibility structures and objective functions, such as vertex cover, graph matching, and routing problems\. Exploring such extensions could help assess the generality of the framework and further clarify the role of learned coarsening in reducing large combinatorial search spaces\.

### AI use statement

In this work, we used generative AI tools to assist with language editing, including improving grammar, clarity and readability\. These tools were not used to generate the research ideas, design the methodology, conduct the experiments, analyze the results, or select and verify the cited literature\. All AI\-assisted text was carefully reviewed and revised by the authors to ensure its accuracy and consistency with the underlying research\. The authors take full responsibility for the final content of this work, including all text, claims, results, and artifacts\.

## References

- I\. Alkhouri, C\. Le Denmat, Y\. Li, C\. Yu, J\. Liu, R\. Wang, and A\. VelasquezDifferentiable quadratic optimization for the maximum independent set problem\.InProceedings of the 42nd International Conference on Machine Learning,pp\. 1102–1127\.Cited by:[§2](https://arxiv.org/html/2609.25149#S2.SS0.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2609.25149#S5.SS1.SSS0.Px2.p2.1)\.
- Bötheret al\.\(2022\)M\. Böther, O\. Kißig, M\. Taraz, S\. Cohen, K\. Seidel, and T\. FriedrichWhat’s wrong with deep learning in tree search for combinatorial optimization\.InThe Tenth International Conference on Learning Representations,Cited by:[§1](https://arxiv.org/html/2609.25149#S1.p3.1)\.
- Bruscaet al\.\(2023\)L\. Brusca, L\. C\. Quaedvlieg, S\. Skoulakis, G\. Chrysos, and V\. CevherMaximum independent set: self\-training through dynamic programming\.Advances in Neural Information Processing Systems36,pp\. 40637–40658\.Cited by:[§1](https://arxiv.org/html/2609.25149#S1.p3.1),[§2](https://arxiv.org/html/2609.25149#S2.SS0.SSS0.Px2.p1.1),[§5\.1](https://arxiv.org/html/2609.25149#S5.SS1.SSS0.Px2.p2.1)\.
- Caiet al\.\(2021\)C\. Cai, D\. Wang, and Y\. WangGraph coarsening with neural networks\.InInternational Conference on Learning Representations,Cited by:[§2](https://arxiv.org/html/2609.25149#S2.SS0.SSS0.Px3.p1.1)\.
- Hamiltonet al\.\(2017\)W\. Hamilton, Z\. Ying, and J\. LeskovecInductive representation learning on large graphs\.Advances in neural information processing systems30\.Cited by:[§3](https://arxiv.org/html/2609.25149#S3.SS0.SSS0.Px2.p1.1)\.
- Jinet al\.\(2020\)Y\. Jin, A\. Loukas, and J\. JaJaGraph coarsening with preserved spectral properties\.InInternational Conference on Artificial Intelligence and Statistics,pp\. 4452–4462\.Cited by:[§1](https://arxiv.org/html/2609.25149#S1.p4.1),[§2](https://arxiv.org/html/2609.25149#S2.SS0.SSS0.Px3.p1.1)\.
- Karalias and Loukas \(2020\)N\. Karalias and A\. LoukasErdos goes neural: an unsupervised learning framework for combinatorial optimization on graphs\.Advances in Neural Information Processing Systems33,pp\. 6659–6672\.Cited by:[§1](https://arxiv.org/html/2609.25149#S1.p3.1),[§2](https://arxiv.org/html/2609.25149#S2.SS0.SSS0.Px2.p1.1),[§5\.1](https://arxiv.org/html/2609.25149#S5.SS1.SSS0.Px2.p2.1)\.
- Karypis and Kumar \(1998\)G\. Karypis and V\. KumarA fast and high quality multilevel scheme for partitioning irregular graphs\.SIAM Journal on scientific Computing20\(1\),pp\. 359–392\.Cited by:[§2](https://arxiv.org/html/2609.25149#S2.SS0.SSS0.Px3.p1.1),[§3](https://arxiv.org/html/2609.25149#S3.SS0.SSS0.Px3.p1.4)\.
- Kipf and Welling \(2017\)T\. N\. Kipf and M\. WellingSemi\-supervised classification with graph convolutional networks\.InInternational Conference on Learning Representations,Cited by:[§3](https://arxiv.org/html/2609.25149#S3.SS0.SSS0.Px2.p1.1)\.
- Lammet al\.\(2017\)S\. Lamm, P\. Sanders, C\. Schulz, D\. Strash, and R\. F\. WerneckFinding near\-optimal independent sets at scale\.Journal of Heuristics23\(4\),pp\. 207–229\.Cited by:[§2](https://arxiv.org/html/2609.25149#S2.SS0.SSS0.Px1.p1.1),[§5\.1](https://arxiv.org/html/2609.25149#S5.SS1.SSS0.Px2.p1.1)\.
- Liet al\.\(2018\)Z\. Li, Q\. Chen, and V\. KoltunCombinatorial optimization with graph convolutional networks and guided tree search\.Advances in neural information processing systems31\.Cited by:[§1](https://arxiv.org/html/2609.25149#S1.p3.1),[§2](https://arxiv.org/html/2609.25149#S2.SS0.SSS0.Px2.p1.1)\.
- Loukas and Vandergheynst \(2018\)A\. Loukas and P\. VandergheynstSpectrally approximating large graphs with smaller graphs\.InInternational conference on machine learning,pp\. 3237–3246\.Cited by:[§2](https://arxiv.org/html/2609.25149#S2.SS0.SSS0.Px3.p1.1)\.
- Xiao and Nagamochi \(2017\)M\. Xiao and H\. NagamochiExact algorithms for maximum independent set\.Information and Computation255,pp\. 126–146\.Cited by:[§1](https://arxiv.org/html/2609.25149#S1.p2.1)\.

## Appendix AAppendix

#### Ablation of the Dual\-GNN Components\.

To examine the contribution of the two learned components, we compare the full model with three ablated variants: removing the Partition GNN, removing the Representative GNN, and removing both GNNs\. When the Partition GNN is removed, cluster contractions are determined using the corresponding structural heuristic without learned guidance\. When the Representative GNN is removed, candidate local states are selected using the non\-learned scoring rule\. All variants use the same test instances and downstream optimization protocol as the full model\. Figure[4](https://arxiv.org/html/2609.25149#A1.F4)reports the mean MIS size on ER graphs withp=0\.35p=0\.35across different graph sizes\.

![Refer to caption](https://arxiv.org/html/2609.25149v1/gnn_ablation.png)Figure 4:Ablation of the two GNN componentsThe full model consistently achieves the best performance across all graph sizes, demonstrating the effectiveness of both GNN components\. Removing the Representative GNN leads to a larger performance drop, indicating the importance of learned state selection\. Removing the Partition GNN has a smaller effect on medium\-sized graphs, but the performance gap increases on larger graphs\. Removing both GNNs produces the weakest overall results\. These results confirm that both GNN components play important roles in the proposed framework and are necessary for maintaining strong solution quality across different graph scales\.

#### Runtime across Graph Densities\.

Table[5](https://arxiv.org/html/2609.25149#A1.T5)reports the mean solving time of different methods on ER graphs under varying edge probabilities\.

Table 5:Mean solving time on ER graphs under different edge probabilities\.†pCQO\-MIS returned empty, non\-maximal solutions atp=0\.05p=0\.05andp=0\.10p=0\.10\. The reported runtimes correspond to these unsuccessful runs and therefore do not represent the time required to obtain valid MIS solutions\.

Our method maintains a relatively stable runtime across different graph densities, ranging from 3\.26 to 5\.23 seconds\. It is consistently faster than ReduMIS, although lightweight greedy and some direct neural baselines require less computation\.

#### State\-Space Compression across Graph Sizes\.

Table[6](https://arxiv.org/html/2609.25149#A1.T6)reports the reduction from the original graph to the final state\-conflict graph for different graph sizes\.

Table 6:State\-space compression on ER graphs of different sizes\.Although the number of candidate local states increases rapidly with the graph size, the bounded state\-selection mechanism keeps the final conflict graph compact\. For graphs with at least 300 vertices, only approximately 2% of the candidate states are retained for the final optimization\.

#### Sensitivity to the Representative\-State Budget\.

We select the representative\-state budgetkkusing the held\-out validation set of 100 ER graphs withn=500n=500andp=0\.35p=0\.35\. We evaluatek∈\{1,2,3,5\}k\\in\\\{1,2,3,5\\\}while fixing the trained models and all other inference and search parameters\. The adaptive state\-allocation branch is disabled in this experiment, so each final cluster retains at most thekkhighest\-scoring states\.

![Refer to caption](https://arxiv.org/html/2609.25149v1/topk_sensitivity.png)Figure 5:Sensitivity to the representative\-state budgetkkAs shown in Figure[5](https://arxiv.org/html/2609.25149#A1.F5), increasing the budget fromk=1k=1tok=3k=3improves the mean MIS size from 19\.15 to 19\.20, indicating that retaining multiple local configurations benefits global coordination during coarse optimization\. Increasing the budget further tok=5k=5does not improve the solution quality, while increasing the mean runtime from 3\.80 to 4\.46 seconds\. We therefore usek=3k=3in all main experiments, as it provides the best validation quality while avoiding the additional computational cost associated with a larger retained state set\.