- Rating
- 1
- Confidence
- 4
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 1
Read review
Paper summary
This paper focuses on the neural solver for the Min-k-Partition problem. The main value of the proposed method is its improved generalization to new instances compared to prior work. To achieve this goal, the authors propose a series of improvements over conventional GNN-based methods. 1. a geometry-aware divergence (GA-KL) that adapts the optimization geometry to the graph structure. 2. a lifted GNN architecture that generalizes analytical mirror descent updates into trainable layers. 3. a recurrent refinement scheme that reuses the same learned operator at inference without parameter updates.
The theoretical derivation is clear overall, and the application to the Min-k-Partition problem is reasonable. However, I have concerns about the core contributions of this paper, and it lacks important comparative experiments.
Critical strengths
- The paper is well-organized. The theoretical sections are detailed and easy to follow.
- The method is practical.
Critical weaknesses
- The authors define the problem as Min-k-partition, which is easily confused with the graph partitioning problem. In fact, what the authors actually solve is the max-k-cut problem. In contrast, the graph partitioning problem has significantly more important and widespread industrial applications.
- Several important baseline comparisons are missing, such as FEM and CRA. While the early PI-GNN exhibited suboptimal performance, FEM and CRA were specifically proposed to improve upon it. The absence of these baselines makes it difficult to fairly evaluate the true performance of the proposed method.
[1] Free-energy machine for combinatorial optimization. Nature Computational Science 2025.
[2] Controlling continuous relaxation for combinatorial optimization. NeurIPS 2024.
- PI-GNN and FEM are both unified frameworks for classes CO problems. When specialized to a specific problem, they can also enhance generalization via pretraining (please refer to Differentiable Integer Linear Programming, ICLR 2025). FEM further mitigates poor local optima by running multiple replicas. It remains difficult to assess whether the recurrent refinement strategy adopted in this paper is more effective in comparison.
- Several important experimental details are missing, such as the sizes (number of nodes and edges) of the Cora and CiteSeer datasets. More importantly, the authors did not provide the source code or a reproducibility statement, which is essential for properly evaluating the experimental results presented in this paper.
Questions for authors
- Do the authors believe that the proposed method can be extended to the graph partitioning problem? It would be helpful to include experimental comparisons to support this claim.
- Can the authors provide a comparison between the proposed method and FEM? Ablation studies on the annealing mechanism and random seeds are crucial for evaluating the effectiveness of the proposed method.