- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
The paper proposes HyperNCO, an instance-wise unsupervised optimization framework for hypergraph partitioning, max-k-cut, and proper coloring. It represents vertex assignments with one-hot vectors, evaluates high-order objective terms through GPU tensor operations, and uses a signed quadratic annealing penalty to gradually encourage discrete assignments. The framework supports both neural encoders and directly optimized logits.
Critical strengths
-
Reasonable motivation and a coherent formulation. High-order interactions are central to hypergraph optimization. The one-hot product construction provides a natural way to detect monochromatic hyperedges and formulate the three studied problems.
-
The paper evaluates both graph and hypergraph datasets and compares neural and direct-logit variants. The annealing ablations, runtime measurements, and explicit discussion of GPU memory limits are useful for understanding where the framework works well.
Critical weaknesses
-
Presentation and implementation details need to be clearer. Figs. 1-2 are crowded, and some labels are too small to read comfortably. Fig. 3 contains a useful example, but numbered operations and explicit tensor shapes would make it easier to follow. The optimization procedure would also benefit from compact pseudocode: the annealing schedule, adaptive coloring penalties, stopping criterion, and conversion from soft assignments to valid discrete solutions are currently scattered or underspecified. There are also small terminology issues: Eq. (9) uses Gini impurity rather than the usual Gini coefficient, and the explanation of Eq. (8) says “more than two colors,” whereas the stated constraint only requires a hyperedge to be nonmonochromatic.
-
In Eq. (12), the constraint $ \sum_{v\in e}x_{v,i}\geq |e|z_{e,i}-(|e|-1) $ seems not to force when all vertices in the hyperedge have label . As written, setting every and every is feasible, allowing the objective to count every hyperedge as cut regardless of the actual assignment. The intended lower bound seems to be $ z_{e,i}\geq \sum_{v\in e}x_{v,i}-(|e|-1).$ The same issue appears in Eq. (10). This could be a typo, but it matters because the reported solver results do not follow from the written max-k-cut formulation.
-
The partitioning comparisons use different balance requirements. Appendix D.1 imposes a hard balance tolerance of for Gurobi/SCIP, while HyperNCO uses a soft penalty and sometimes returns substantially imbalanced partitions. For example, on EAT with , HyperNCO-FEM reports 2870 cuts with , while Gurobi reports 3581 cuts with . These results reflect different feasible sets, so the lower cut count alone does not establish better partitioning quality. The timing protocol also needs clearer labeling, particularly whether FEM runtime includes all ten replicas and whether coloring times correspond to the reported color counts.
Questions for authors
Q1: Please improve the figure readability and add pseudocode covering the full optimization and decoding procedure. Please also specify the annealing schedule and how the two coloring penalties are updated.
Q2: Could the authors check the constraints and confirm which formulation was actually used for Gurobi and SCIP? If the implementation used the written constraints, the affected comparisons would need to be rerun.
Q3: Could you provide results comparing the partitioning methods under a shared balance tolerance, or provide a cut-vs-imbalance curve? Please also clarify the total replica budget and distinguish time to first feasible coloring from time to reach the reported number of colors.
2 comments
I thank the authors for their responses and the revised manuscript. My concerns have been addressed, and I decide to maintain my positive score.
We thank the reviewers for their careful reading and comments. We address the weaknesses they mentioned below.
We have restructured Fig. 1 (Page 2) and 2 (Page 3), and improved the content of Fig. 3 (Page 4) and Tab. 1 (Page 7). We have added pseudocode in Appendix D (Page 19,20,21,22). We have also renamed the annealing strategy to Gini–Simpson-index-based annealing.
We thank the reviewer for the careful reading. We have fixed this problem in Eq. 12. The mistake was introduced when we attempted to formalize the code logic as mathematical expressions.
The hMETIS algorithm does not guarantee balancedness, making it difficult to compare it fairly with Gurobi. To address this issue, we have supplemented Tab. 1 (Page 7) with the experimental results of Ours-FEM under strictly balanced conditions. Moreover, the win-count summary is rewritten (Tab. 2) and split into the two tiers. Against the heuristics, HyperNCO attains the lowest cut in 46 of the 50 cells (92%), and is the sole winner in 42 (84%). Gurobi is not a competitor in this tier since it always returns exactly balanced partitions. As matched balancedness HyperNCO wins 26 cells against Gurobi's 20.
For FEM, the reported runtime is a single replica's wall-clock. We have added a footnote in the revision (Page. 8) to clarify this: "For the FEM variant the replicas share no parameters, so they can be trained as one batch, at the cost of proportionally more memory. The batched wall-clock would be close to that of one replica. We therefore report the per-replica time rather than 10x."
Please refer to our respond to Weakness 1 and 2.
Our implementation is correct. The mistake was introduced when we attempted to formalize the code logic as mathematical expressions.
Please refer to our respond to Weakness 3.
Overall, we believe we have addressed the reviewer's main concerns of this paper. We are happy to provide additional clarifications and engage further in the discussions if we have misunderstood any crucial points.
Many thanks, The Authors.