acceptodds
Under review as a conference paper at ICLR 2027

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 Erdos–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 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 Erdos–R\'enyi graphs with edge probability , the learned coarsening policy generalizes effectively across both unseen graph densities and structurally different graph families.

Primary area:
optimization
Keywords:
Graph Neural Networks, Graph Coarsening, Maximum Independent Set, Combinatorial Optimization

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_ib7gOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper proposes a Dual-GNN multilevel coarsening framework for the maximum independent set (MIS) problem. The method achieves near-optimal solution quality on several synthetic graphs while substantially reducing runtime compared with the exact solver.

Critical strengths
  1. The paper is well motivated, as developing effective learning-based solvers for MIS is an important direction.

  2. The empirical results are strong and the evaluation is relatively comprehensive.

Critical weaknesses
  1. A recent comprehensive MIS benchmark (Wu et al., TMLR 2026) is missing. This benchmark includes strong baselines such as OnlineMIS and also evaluates on other synthetic graphs such as RB graphs, neither of which is considered in this paper. It would be helpful to include these baselines and graph families.

  2. The evaluation in this paper is conducted on synthetic graphs. Including real-world graphs would provide a more convincing assessment of the practical effectiveness and generalization of the proposed method.

  3. The related work section discusses classical graph coarsening methods such as METIS (Karypis and Kumar, 1998), but the empirical evaluation in this paper does not compare with these classical coarsening approaches. Adding such comparisons would strengthen the evaluation of the proposed learned coarsening approach.

Reference:

Yikai Wu, Haoyu Zhao, Sanjeev Arora. Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set. TMLR 2026.

Questions for authors

Please address the weaknesses mentioned above.

2 comments

Response to Reviewer ib7g

Thank you for the constructive review and for suggesting ways to broaden our evaluation. Our revisions and clarifications are summarized below.

1. Wu et al.’s benchmark.

We have cited Wu et al. (TMLR 2026) and discussed their findings on the strength of classical MIS solvers. To broaden our comparison with ReduMIS, we evaluated frozen ER-trained our method on the complements of 24 DIMACS maximum-clique instances. Our method and ReduMIS obtained mean independent-set sizes of 33.33 and 33.38, respectively, and matched the published reference values on 16 and 20 instances. Detailed experimental results are provided in Table 12 of the appendix.

2. Real-world graphs.

We evaluated the ER-trained model without retraining on 100 graphs each from COLLAB and REDDIT-MULTI-5K, the two real-world datasets used by Wu et al. On COLLAB, our method achieved a mean independent-set size of 8.74, only 0.01 below DIFUSCO, while outperforming all other baselines, including OnlineMIS, ReduMIS, and iSCO. On REDDIT-MULTI-5K, our method achieved the highest mean independent-set size, tied with greedy methods, OnlineMIS, iSCO,LwD. Detailed experimental results are provided in Table 9 of the appendix.

3. Classical coarsening.

We have added Table 3 to the Main Results section to compare our full method with a variant that replaces the Partition GNN with METIS-style heavy-edge matching (HEM). This variant replaces the learned coarsener in our method with a greedy rule that contracts adjacent clusters based on the number of edges between them. Both variants use the same representative-state model, downstream MIS solver, and refinement budgets. We evaluate them on the same 50 ER graphs at each of the five sizes.

Our method matches HEM at n=100n=100 and finds independent sets that are larger by 0.040.04–0.160.16 vertices on average at the other sizes. HEM is faster at every tested size. At n=2000n=2000, our method and HEM find independent sets of mean size 23.3223.32 and 23.2423.24 in 37.5637.56 and 10.9510.95 seconds per graph, respectively.

Thanks for the detailed response. I will keep my rating.

Reviewer_akNtOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors propose DGMC, a supervised dual-GNN multi-level MIS-specific coarsening method which allows for compressed (reduced) optimization space. The authors evaluate on multiple graph families with testing generalization.

Critical strengths
  • The method is novel as the learning part is applied for a problem specific coarsening and then representation.

  • The experimental results (although can be more comprehensive) are good when compared to the SOTA heuristic (ReduMIS) on the larger graphs.

Critical weaknesses

Weaknesses/Questions/Suggestions

  • Overall, the paper is not very well-written. Some parts are unclear. Examples include some of the below points.

  • The run-time of the proposed method is very large when compared to the training-data-free method (pCQO-MIS) and when compared to the test run time of the learning method EGN (which is unsupervised).

  • Add references. For example, include a reference for each application in lines 35 to 38.

  • For closely related problem that are not graph problems, you can cite the reduction between 3SAT to MIS [A].

  • It is important to cite that MIS is NP-Hard [B].

  • "Maximal MIS" is not very formal. I suggest using Maximal IS, or MaxIS.

  • In [C], the authors proposed a compress then de-compress by standard clustering approach to handle large graphs. However, they needed a procedure to ensure that the combined set (from local MISs of the clusters) maintains the independence property. This is not trivial. However, the authors say "deterministically completed" without any details.

  • Baselines: The evaluation of the paper can be improved by including:

1- A more recent Quadratic CPU+GPU method (mQO-MIS) [D]

2- Sampling GPU methods such as (ReSCO) [E]

3- ILP solvers that don't depend on classical branch-and-bound, such as CP-SAT [F]

4- Since the method is GPU-based, then a GPU ILP solver can also be included, such as the recent NVIDIA cuOPT [G]

5- ANYCSP [H]. This is an RL-based solver that is, like DGMC, generalizable not only to other graph families, but, in some cases, to other problems.

  • An evaluation using the classical DIMACS dataset [I] would strengthen the evaluation. Note that the suggested baselines and benchmark is meant to comprehensively evaluate the method instead of using it to determine the merit of the proposed approach. In short, DGMC does not need to beat all other methods on all settings, but it is valuable to evaluate across different configurations.

  • How is the training set being labeled? These details are important and should be included.

  • For the feature vector in Eq. (6), can the authors elaborate more on "the external boundary of C_i"? Do you simply mean V∖CiV\setminus C_i?

  • For folks whom are not very familiar with GNNs, functions AGG and UPDATE may not be very clear. I suggest defining these formally and show where the actual trainable weights are. This applies to || in Equation (15).

  • In Figure 2, what is the difference between Linear+ReLU and FC->ReLU?

  • What is B in line 238?

  • For Figures 2 and 3, do the colors in candidate pair and local state have meaning? If they don't, remove them to avoid confusion.

  • What is Complete(.,.) in Equation (16)?

  • In line 310, how do you solve the weighted MIS? Is it using the ILP in (1)? If yes, then how do back-propagate through it to update the weights of your two GNNs. If no, can you elaborate more?

  • It is never made clear how test-time is different from the training stage.

  • Run-time setup is missing from the results of Table 4.

  • There are no details about the completion-aware and "deterministic recovery".

References

[A] Introduction to Algorithms, MIT Press 2009

[B] Reducibility Among Combinatorial Problems, Complexity of Computer Computations 1972

[C] A Differentiable Approach to The Maximum Independent Set Problem Using Dataless Neural Networks, Neural Networks 2022

[D] Mutation-Guided Differentiable Quadratic Combinatorial Optimization, Arxiv 2026

[E] Reheated Gradient-based Discrete Sampling for Combinatorial Optimization, TMLR 2025

[F] https://developers.google.com/optimization/cp/cp_solver/ Google OR-Tools

[G] https://www.nvidia.com/en-us/ai-data-science/products/cuopt/ NVIDIA

[H] One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction, IJCAI 2023

[I] Cliques, coloring, and satisfiability: second DIMACS implementation challenge, American Mathematical Soc., 1996.

Questions for authors

See above.

6 comments

Response to Reviewer akNt

We sincerely thank you for the careful review and constructive feedback. Our revisions and clarifications are summarized below.

1. Clarity of the presentation

We have reorganized the method section around the inference pipeline. The Partition GNN scores cluster merges, while the Representative GNN ranks local independent sets. DGMC then searches for compatible states, decodes them, and completes the solution. We will further clarify this pipeline and distinguish rollout-based training from inference with fixed model parameters.

2. Runtime compared with pCQO-MIS and EGN

We acknowledge DGMC's relatively high solving times on 1,000- and 2,000-vertex instances. Nevertheless, its runtime remains practical, and our additional experiments show that DGMC is faster than mQO-MIS, CP-SAT, and cuOpt on the evaluated instances (Appendix Table 11).

3. References and theoretical background

We have added references for the applications in Lines 35–38, cited [A] for the 3-SAT-to-MIS reduction, and cited [B] for the NP-hardness of MIS.

4. Terminology for maximal independent sets

We have replaced "Maximal MIS" with "Maximal IS" in Figure 1.

5. Prior clustering-based MIS and feasibility during recovery

Unlike Alkhouri et al. (2022), whose Algorithm 2 resolves cross-community conflicts after combining local solutions, DGMC ensures compatibility during coarse search. Each state is a local independent set. Two states conflict if they belong to the same cluster or contain vertices connected by an original edge. Thus, any independent set in the state conflict graph decodes into a feasible independent set in the original graph. Greedy completion then extends it to a maximal independent set. We have clarified this in Section 4.4.

6. Additional baseline experiments

We evaluated all five suggested baselines on ER test instances: mQO-MIS, ReSCO, OR-Tools CP-SAT, NVIDIA cuOpt, and an MIS adaptation of ANYCSP. Results are in Appendix Table 11.

7. Evaluation on DIMACS benchmarks

We evaluated 24 complemented DIMACS maximum-clique instances (125–500 vertices), where independent sets correspond to cliques in the original graphs. Without retraining, DGMC produced feasible solutions on all instances, averaging 33.33 versus 33.38 for ReduMIS. Although slightly below ReduMIS, DGMC outperformed all other baselines in solution quality (Appendix Table 12).

8. Generation of training targets

Both GNNs use heuristic rollout targets. The Partition GNN targets the final solution size after a candidate matching and the remaining pipeline. The Representative GNN uses greedily completed local-state sizes to construct cluster-wise soft targets, as described in Section 4.5.

9. External boundary in Eq. (6)

The external boundary of CiC_i contains vertices outside CiC_i adjacent to at least one vertex inside it. Each is counted once, with the count normalized by n=∣V∣n=|V|. We have added this definition after Eq. (6).

10. Message passing and vector concatenation

We have defined AGG and UPDATE in Section 3 and clarified the notation || after Eq. (8).

11. Linear and FC notation in Figure 2

Both denote a fully connected layer followed by ReLU. We have unified the notation in the figure.

12. Definition of B

BB is the maximum cluster size in original vertices. We have defined it in Section 4.2 before ∣Ci∣+∣Cj∣≤B|C_i|+|C_j|\leq B.

13. Color conventions in Figures 2 and 3

In Figure 2, blue and red distinguish the candidate clusters, matching their quotient-graph colors. In Figure 3, we have labeled selected and unselected vertices and replaced the multicolored output icon with a single-color one.

14. Definition of Complete in Eq. (16)

Complete greedily adds vertices while preserving independence until no eligible vertex remains, yielding a maximal independent set.

15. Weighted MIS search and gradient flow

States are weighted by cardinality. We initialize greedily on the state conflict graph and use beam search to rank feasible seeds by completed solution size. Gradients flow through both GNNs via supervised losses against fixed rollout targets.

16. Training versus test-time inference

Training uses heuristic rollouts to supervise both GNNs. At test time, their parameters are frozen; they score cluster merges and local states from the input graph, followed by compatible-state search and completion.

17. Runtime setup for Table 4

We have added the timing setup for Table 4. Appendix Table 7 reports wall-clock runtimes on the same BA, SBM, and WS instances.

18. Completion-aware search and deterministic recovery

Beam search ranks seeds by their completed independent-set sizes (Eq. (16)). Recovery extends each decoded seed on the original graph. Under the minimum residual degree rule, it repeatedly selects the eligible vertex with the fewest eligible neighbors, breaking ties by vertex ID, until the independent set is maximal.

Reviewer_akNtOpenReview ↗

Response to rebuttal

First, I would like to thank the authors for their efforts. Please see my responses below.

In general, could the authors highlight changes in the paper using colored text? It is difficult to follow the revisions and compare them with the original submission. The numbering in the authors’ response does not correspond to that of my review, so I follow the authors’ numbering below.

-5- Section 4.4 does not clearly explain the difference between Alkhouri et al. (2022) and the proposed approach. This point remains unclear.

-6- I am concerned that the evaluation setup, particularly the choice of time budgets, may favor the proposed method. The authors should report MIS size over time for all baselines, regardless of whether CP-SAT achieves optimality, for every graph category. For example, if CP-SAT runs for more than 2.8 seconds, would it achieve an MIS size of 19.20 for n=500n=500? Also, most, if not all, of these baselines are not cited. For mQO and ReSCO, could the authors explain the selected settings? The choice of p=0.35p=0.35 may not be the most representative density setting; I recommend including p=0.5p=0.5.

-7- For the DIMACS graphs, the evaluation also appears limited by the selection of graph sizes. Why consider only graphs with 125 to 500 vertices? DIMACS includes many larger graphs; see Table 1 in “A short review on the maximum clique problem algorithms with classical, AI, and quantum methods.” For mQO, did the authors use the CPU-only version or the GPU+CPU version? Since the proposed method is GPU-enabled, the comparison should include the GPU+CPU version. To clarify, my recommendation for a more comprehensive evaluation in points 6 and 7 is not intended to assess whether the proposed method outperforms every baseline on every graph. The goal is to thoroughly understand its capabilities and limitations.

-8- My question about how the training set is labeled remains unanswered. Since the method uses supervised learning, the true or best-known solutions are needed as targets in the training loss, which is not provided in the paper. How are these best-known solutions obtained? Have the authors tried training their GNNs using suboptimal target solutions? How would that affect the performance at test time.

-10- For AGG and UPDATE, the added text describes what these functions do but does not provide formal definitions showing their trainable weights.

-11+13- I could not find definitions of the notation in either the figure or its caption. The color convention also remains undefined.

-16- The detailed training steps should be discussed in the paper.

-17- Regarding solution quality versus runtime in Tables 4 and 7, it is difficult to compare the results when the tables appear in different sections and on different pages. Also, why were Greedy and pCQO-MIS run for less than one second and approximately three seconds, respectively? What would happen if Greedy were given 13 seconds or more, as the proposed method was? This question also applies to Erdos GNN, which is unsupervised and, unlike the proposed method, does not require labeled graphs.

-18- Further details are needed about the completion-aware mechanism and “deterministic recovery.” For example, in line 329, the authors describe the Complete function without explaining its sequential complexity on larger graphs or its impact, including how often it is used.

Response to Reviewer’s Follow-up Comments.

Thank you for your detailed feedback. Our responses are provided below. We have also highlighted the revisions in the manuscript using colored text for clarity.

-5- We have revised Section 4.4 to clarify the key distinction (line 322-348). In general, Alkhouri et al. (2022) independently compute local solutions and resolve cross-community conflicts after merging them by replacing or removing selected vertices. In contrast, our method constructs a conflict graph over local independent sets and jointly selects mutually compatible states. Consequently, their union is already an independent set in the original graph, requiring no conflict resolution. Subsequent greedy completion only adds eligible vertices while preserving the selected states.

-6- Tables 14–17 now report feasible independent-set sizes at wall-clock checkpoints up to 60 s for ER, BA, SBM, and WS graphs. Increasing the runtime budget does improve the solution quality of the baseline methods. However, only ReduMIS slightly outperforms our method in some cases. Table 12 reports CP-SAT's best feasible solutions regardless of optimality certification. On ER graphs with n=500n=500 and p=0.35p=0.35, CP-SAT averaged about 18.1 at 60 s, compared with 19.20 in 3.41 s on average for our method.

We have added the baseline citations in Section 5.1. We used the authors' GPU pmQO-MIS implementation with 512 parallel candidates and up to 4000 gradient steps per round, followed by CPU 1-for-2 local search on up to five retained candidates. We repeated search rounds within the 60-second budget. ReSCO used the authors' reheating rule with 64 chains and up to 10000 steps per chain.

On 50 additional ER graphs with n=500n=500 and p=0.50p=0.50, our model averaged 13.12 without retraining. ReSCO and CP-SAT reached 13.10 and 12.64 at 60~s, respectively (Table 18).

-7- The original evaluation used a predefined subset of 24 DIMACS graphs selected to cover several graph families within the 125–500-vertex range. We have expanded the benchmark to all 80 DIMACS complement graphs, ranging from 28 to 4,000 vertices, with 25 instances above 500 vertices(Appendix Table 11). The original comparison used CPU-only mQO-MIS. The updated comparison includes the hybrid CPU–GPU implementation, pmQO-MIS, which runs batched gradient search on the GPU and local search on the CPU. The results show that, on the DIMACS benchmark, our method achieves slightly lower solution quality than ReduMIS but outperforms the other baseline methods.

-8- First, we would like to clarify that our models are trained using soft labels rather than exact ground-truth labels, as detailed in Section 4.5 (line 373-380). Both GNNs in the reported DGMC system are supervised by the cardinalities of feasible independent sets obtained from heuristic rollouts. For the Partition GNN, we try several candidate matchings at a coarsening level, run the remaining coarsening and solution-recovery steps for each, and train the network to rank matchings by the resulting independent-set sizes. For the Representative GNN, we fix each candidate local state, greedily complete it on the residual graph, and convert the resulting cardinalities into soft targets for a cross-entropy loss. We also computed certified reference solutions for the training pool. For the 100- and 300-vertex graphs, we solved maximum clique on the complement graph using exact branch-and-bound.

-10- We have added detailed mathematical formulations in Section 4.2.

-11+13- We have added explanations of the color coding to the captions of Figures 2 and 3.

-16- We have added a detailed description of the training steps in Section 4.5.

-17- We apologize for the readability issues caused by the previous formatting. We have now merged the solution quality and runtime tables into a single table for clarity (Table 4). Greedy runs a deterministic residual minimum-degree construction and returns when it reaches a maximal independent set. Repeating the same construction returns the same solution. Therefore, the runtime is less than one second because the algorithm has already completed its execution. For Erdős GNN and pCQO-MIS, we evaluated the solution quality under different experimental configurations and runtime budgets( Appendix Table 14,15). The results show that relaxing the time constraints indeed improves solution quality, but both methods still underperform our proposed approach.

-18- We have clarified the Complete⁡\operatorname{Complete} procedure in the revised manuscript. It greedily selects the minimum-degree vertex in the remaining graph, breaking ties by vertex ID, to ensure deterministic recovery. With a min-heap and incremental degree updates, each call takes O((n+m)log⁡n)O((n+m)\log n) time. We also clarify that completion is used to rerank local states, evaluate partial seeds during beam search, and recover the final solution, with repeated seeds cached within each beam search.

Reviewer_iEEdOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Authors studied maximum independent set problem with a GNN approach. Maximum independent set is a fundamental problem in computer science and it has numerous different applications across different areas. The problem is a computationally hard problem as it was shown that unless P = NP, no polynomial time algorithm can approximate MIS within factor of n1−ϵn^{1-\epsilon} for a constant ϵ\epsilon.

Authors used two GNN to compress the large input graph before applying a combinatorial approach on top of that. The first GNN role is to combine nearby vertices into small clusters of at most 8 vertices and the second GNN choses the top 3 valid MIS per cluster to create a much smaller conflict graph. Then a solver which is based on a combinatorial approach chooses a combination of non conflicting clusters and maps them back to the input graph and finally tries to add any remaining vertex that can be compatible with others in the combination.

In the experiments they trained their model on Erdos Renyi graphs with at most 300 vertices and p=0.35. They achieve more than 99% accuracy on ER with 500 vertices and the speed up is 189 times compare to exact solver. They also beat all heuristics and baselines for ER, Barabási–Albert, Stochastic Block Models, and Watts–Strogatz graphs.

Critical strengths

I like the idea that their approach uses both GNN and combinatorial methods for this problem. They used GNN to make the space smaller for the combinatorial method which suffers from slowness.

Critical weaknesses

Authors did not test their algorithm on real world data. Also, they mostly used random graph models which are not necessarily hard examples for MIS like the near regular expanders.

Questions for authors

Is there an intuition behind the constant 8? If the graph scales to a large size, say 1 million vertices, how should these constants changes?

2 comments

Response to Reviewer iEEd

Thank you for highlighting the combination of learned coarsening and combinatorial search, and for suggesting a broader evaluation.

1. Real-world graphs.

To evaluate generalization to real-world graphs, we tested the same ER-trained our models on COLLAB and REDDIT-MULTI-5K without retraining. In comparison with nine baseline methods, DGMC achieved a mean independent-set size of 8.74 on COLLAB, only 0.01 below the best-performing method (DIFUSCO, 8.75), while outperforming the other eight baselines, including ReduMIS (8.70) and Deg-Greedy (8.68). On REDDIT-MULTI-5K, DGMC achieved 350.73, tying the best result among all compared methods. These results demonstrate that our method remains highly competitive on real-world graphs despite being trained exclusively on synthetic ER graphs, providing further evidence of its cross-distribution generalization capability. Detailed experimental results are provided in Table 8 of the appendix.

2. Regular graphs and harder benchmarks.

On 20 random 16-regular graphs with 200 vertices, the mean solution sizes were 42.65 for our method, 42.20 for ReduMIS, and 37.95 for greedy. This experiment tests degree regularity. Evaluation on graphs selected for high expansion remains open. We also evaluated 80 complements of DIMACS clique instances, where our method and ReduMIS obtained mean solution sizes of 61.16 and 61.41, respectively. Detailed experimental results are provided in Table 11 of the appendix.

3. Why B=8B=8, and how should the parameters scale?

A cluster of at most BB vertices has at most 2B2^B possible subsets, so B=8B=8 caps this number at 256. In a paired inference sweep on 20 ER validation graphs with 500 vertices and fixed top-3 retention, increasing BB from 4 to 8 reduced the cluster count from 125 to 63 and increased the mean solution size before final polishing from 18.95 to 19.15. On a separate instance, increasing BB from 8 to 16 raised local state enumeration and filtering time from 0.44 to 74.85 seconds. These results illustrate the trade-off behind our choice of B=8B=8. Detailed experimental results are provided in Table 9 of the appendix.

For a million-vertex graph, we would start with B=8B=8 and K=3K=3, then tune them against the observed conflict-graph size and memory budget. Even with fully packed clusters, B=8B=8 implies at least 125,000 clusters, so we would first profile conflict-graph construction and global search. Our current experiments leave performance at that scale open.

Thank you so much for the response, I'll keep my positive score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.