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∖Ci?
-
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.
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=100 and finds independent sets that are larger by 0.04–0.16 vertices on average at the other sizes. HEM is faster at every tested size. At n=2000, our method and HEM find independent sets of mean size 23.32 and 23.24 in 37.56 and 10.95 seconds per graph, respectively.