acceptodds
Under review as a conference paper at ICLR 2027

Neural Combinatorial Optimization on Hypergraphs

Abstract

Along with AI computing shining in scientific discovery, neural combinatorial optimization (NCO) has shown promise across diverse problems. Yet, existing neural solvers struggle to solve combinatorial optimization problems (COPs) on large-scale hypergraphs (e.g., hypergraph max-cut, hypergraph partitioning), due to limited computational frameworks. In this work, we propose HyperNCO, an NCO framework for hypergraph COPs. We contribute: (I) A unified one-hot encoded polynomial unconstrained binary optimization (PUBO) formulation for modeling hypergraph COPs; (II) GPU-accelerated algorithms for one-hot encoded PUBO problems; (III) A Gini coefficient-based continuous relaxation annealing strategy to ensure high-quality solutions while preventing convergence to local optima. Experimental results demonstrate that HyperNCO achieves competitive solution quality compared to existing heuristics and state-of-the-art neural solvers, while offering significant advantages in computational efficiency and framework generality.

Primary area:
optimization
Keywords:
Neural Combinatorial Optimization, Unsupervised Learning, Hypergraph

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_eLJHOpenReview ↗
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
  1. 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.

  2. 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
  1. 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.

  2. In Eq. (12), the constraint $ \sum_{v\in e}x_{v,i}\geq |e|z_{e,i}-(|e|-1) $ seems not to force ze,i=1z_{e,i}=1 when all vertices in the hyperedge have label ii. As written, setting every ze,i=0z_{e,i}=0 and every ye=1y_e=1 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.

  3. The partitioning comparisons use different balance requirements. Appendix D.1 imposes a hard balance tolerance of δ=1\delta=1 for Gurobi/SCIP, while HyperNCO uses a soft penalty and sometimes returns substantially imbalanced partitions. For example, on EAT with k=6k=6, HyperNCO-FEM reports 2870 cuts with B1=43B_1=43%, while Gurobi reports 3581 cuts with B1=0B_1=0%. 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

We thank the reviewers for their careful reading and comments. We address the weaknesses they mentioned below.

Weakness 1:

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.

Weakness 2:

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.

Weakness 3:

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."

Question 1:

Please refer to our respond to Weakness 1 and 2.

Question 2:

Our implementation is correct. The mistake was introduced when we attempted to formalize the code logic as mathematical expressions.

Question 3:

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.

I thank the authors for their responses and the revised manuscript. My concerns have been addressed, and I decide to maintain my positive score.

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

The paper proposes HyperNCO, which formulates problems such as hypergraph partitioning, Max-kk-cut, and graph coloring as higher-order polynomial objectives based on one-hot variables. It solves these problems through continuous relaxation, GPU-accelerated tensor operations, and a progressively adjusted quadratic penalty term. The framework supports two implementation approaches: direct optimization of the variables or the use of a neural network. While the primary contribution lies in integrating these components into the context of hypergraph combinatorial optimization, further clarification is needed regarding the novelty of the penalty term itself, as well as whether the experimental results sufficiently demonstrate an advantage over existing solvers.

Critical strengths
  1. The framework offers a unified formulation. It addresses several hypergraph optimization problems through a shared representation and optimization pipeline while preserving higher-order interactions. Providing both direct optimization and neural-network-based implementations also facilitates studying the contributions of different components.
  2. Some reported results are promising. For example, on PubMed with k=3k=3 in Table 1, Ours-NN achieves a cut value of 1157 compared with 1253 for KaHyPar, with both methods reporting zero imbalance. However, this individual result does not resolve the broader evaluation concerns below.
Critical weaknesses
  1. The novelty of the proposed annealing penalty is insufficiently established. Equation (9) is equivalent, up to positive scaling and an additive constant, to the quadratic case of CRA’s categorical-variable penalty [1, Appendix C.1]. The authors should clarify the methodological contribution beyond adapting existing relaxation and annealing techniques to hypergraph problems.
  2. The baseline formulations and evaluation protocol raise substantial validity concerns. As written, Equation (12) permits every hyperedge to be counted as cut regardless of the vertex assignment, requiring verification of the actual implementation. Furthermore, the partitioning comparisons impose near-exact balance on Gurobi/SCIP while permitting substantial imbalance for HyperNCO, such as 43% on EAT with k=6k=6. Figure 4 also reports cut counts exceeding the stated number of edges. These issues require corrected formulations, consistent reporting, and comparisons under identical balance constraints and matched computational budgets.

[1] Yuma Ichikawa. Controlling Continuous Relaxation for Combinatorial Optimization. Advances in Neural Information Processing Systems, 37:47189–47216, 2024.

Questions for authors
  1. Does Equation (12) match the implemented baselines? As written, it allows every hyperedge to be counted as cut regardless of the assignment. It is better to clarify the reported cut values.
  2. Do the partitioning gains persist under identical balance constraints and matched computational budgets, given the substantially greater imbalance permitted for HyperNCO?
  3. What is novel about the annealing mechanism beyond CRA [1], whose categorical penalty with α=2\alpha=2 is equivalent to Equation (9) up to scaling and an additive constant?
  4. Should the authors explain why Figure 4 reports cut counts exceeding the stated number of edges and why the Cooking200 SCIP results in Table 4 exactly match the Gurobi partitioning results in Table 1.
3 comments

We thank the reviewers for their careful reading and comments. We address the weaknesses they mentioned below.

Weakness 1:

We thank the reviewer for the valuable feedback. We have checked the paper of CRA and found the k-Potts penalty in its Appendix.

In the revision, we do not claim Eq. 9 as a novel penalty. In Sec. 4.3 (Page 6) we clarify that for α=2\alpha=2 the CRA kk-Potts penalty reduces to ΦCRA=γk2ϕ(x)+γn(k+1−k2)\Phi_{\mathrm{CRA}}=\gamma k^2 \phi(x)+\gamma n(k+1-k^2) and ∇xΦCRA=k2∇xϕ\nabla_x \Phi_{\mathrm{CRA}}=k^2 \nabla_x \phi. Eq. 9 is therefore identical to CRA's penalty up to an additive constant and a rescaling of γ\gamma absorbed into the schedule.

We will reviese the Abstract and Introduction so that this is presented as an empirical study rather than as a new penalty. In Sec. 1, our contribution is "3)Empirical Study of the Annealing Scheme for One-hot k-labeling Variables. Inspired by CRA Ichikawa 2024, we introduce and empirically study the continuous relaxation annealing strategy built on the Gini-Simpson index (i.e. the α=2\alpha=2 member of the CRA's penalty family)".

We would like to clarify, however, that the contributions of this paper remain valid:

Our motivation in this work is to address the severe computational bottleneck in solving general multi-variable, multi-label problems (e.g., hypergraph COPs). This is why we believe the trick in Fig. 3 is crucial for better understanding the subtle challenge in solving hypergraph COPs.

Therefore, although the annealing strategy has been extensively studied​ recently, it does not represent the fundamental challenge​ in solving hypergraph COPs, nor is it the primary focus​ of this work.

Weakness 2:

We thank Reviewer 2 and Reviewer 3​ for catching the typo in Eq. 12. Based on the Weakness 2 from Reviewer 3, we have corrected this error.

Both Reviewer 2 and Reviewer 3​ pointed out that in Tab. 1 (Page 7), Gurobi and HyperNCO were not compared under the same balancedness. This is because 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 with the experimental results of Ours-FEM under strictly balanced conditions. Moreover, the win-count summary is provided (Tab. 2, Page 8) 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.

We reviewed our code​ and found that the graphs used in the Fig. 4 experiments have 7,000 edges (Page 10), not 5,000​ as previously stated. We have fixed this error.

Question 1:

Please refer to our respond to Weakness 2. Our implementation is correct. The mistake was introduced when we attempted to formalize the code logic as mathematical expressions.

Question 2:

Please refer to our respond to Weakness 2.

Question 3:

Please refer to our respond to Weakness 1.

Question 4:

Please refer to our respond to Weakness 2. We reviewed our code​ and found that the graphs used in the Fig. 4 experiments have 7,000 edges (Page 10), not 5,000​ as previously stated. We have fixed this error. Moreover, we have reviewed our code and fixed the error of Cooking 200 in Tab. 4.

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.

Dear Reviewer stPc,

Thank you again for your time and thoughtful feedback on our work. During the rebuttal period, we addressed your comments in detail and incorporated the corresponding clarifications and additional experiments into the revised manuscript (highlighted in blue).

As the discussion period comes to a close tomorrow, we would be grateful to know whether our revisions have adequately addressed your concerns, and whether you feel the paper's contributions are now clearer. We would greatly appreciate your feedback before the deadline.

Thank you for your time and consideration.

Many thanks, The Authors.

Thank you for the revisions and additional experiments. These address several of my original concerns. However, I still think the current novelty and the experimental improvements are limited. I therefore change my recommendation to weak rejection.

Reviewer_g13nOpenReview ↗
Rating
2(+1)
Confidence
2
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This work proposes HyperNCO, a neural combinatorial optimization framework for solving combinatorial problems on hypergraphs. The combinatorial optimization problems considered in this work include Hypergraph Partitioning, Hypergraph Max-k-cut, and Hypergraph Proper Coloring.

Specifically, the contributions are: 1) a one-hot-encoded PUBO formulation that generalizes PI-GNN’s QUBO loss to k-labeling problems via Hadamard products of one-hot vectors, (2) a GPU-tensorized loss (Eq. 5) using a (1−H)(1-H) broadcasting trick for column-wise reduction over hyperedge members, and (3) a Gini–Simpson-style penalty for continuous relaxation annealing, pitched as a stable alternative to Shannon-entropy penalties.

Critical strengths
  1. The GPU tensorized formula in Eq 5 is a useful trick. The ablation in Fig 6 shows that a roughly 20x speedup occurs over naive hyperedge-traversal implementation given by Eq 4.

  2. The dataset sweep spans hyperedge cardinalities from 2.33 to ~19.99, consists of three problem types with k∈{2,⋯ ,6}k \in \{2, \cdots, 6\}. The ablations isolate multiple design choices including annealing (Fig 4, 5), GPU acceleration (Fig 6) and HyperGNN model choice (Fig 7). The negative results, for e.g. where greedy beats HyperNCO on coloring, are provided honestly.

Critical weaknesses
  1. The "unified NCO framework" claim that the authors make is not backed up by the results. In Tables 1 and 4, Ours-FEM ties or beats Ours-NN on BAT, EAT, UAT, DBLP, CiteSeer, Primary and High. The HGNN+ variant helps, but only on the high-cardinality hypergraphs (e.g Pubmed). The HGNN+ layers add nothing on 7 out of 10 datasets.

  2. It is very difficult to parse/read Table 1, and the places where their method actually outcompetes the baselines are not a lot. The HyperNCO (+variants) is strictly the best on half of the (dataset, k) pairs, with Gurobi and KaHyPar taking the rest of the spots. A win-count summary, or a normalized gap-to-best plot, would make the actual standing of the method far clearer.

  3. In Table 2, HyperNCO loses to a plain degree-based greedy on BAT, EAT, UAT, DBLP, and Primary, and loses or ties SCIP on hypergraphs. The authors themselves state that "a simple degree-based greedy algorithm achieves the best performance in both speed and solution quality (chromatic number) for graph datasets" and on hypergraphs, "HyperNCO can find valid colorings faster but struggles to match the optimal chromatic numbers". The paper should either reframe coloring as a demonstration of validity rather than quality, or drop it.

  4. The penalty ϕ(x)=γ∑i(1−∑jxij2)\phi(x) = \gamma \sum\limits_i (1 - \sum\limits_j x^2_{ij}) is the Gini-Simpson index. The Gini coefficient is the statistic G=∑i∑j∣xi−xj∣2n2xˉG = \frac{\sum\limits_i\sum\limits_j |x_i - x_j|}{2n^2\bar{x}}, and is a different object from the GS index. CRA (Ichikawa, NeurIPS 2024) have already proposed this penalty in a slightly different form. The paper motivates Eq. 9 against FEM's Shannon entropy but never compares against CRA's polynomial penalty. Without a head-to-head ablation against CRA, Eq 9 cannot be claimed as a novel contribution over Ichikawa 2024.

Questions for authors
  1. In Table 1, could you provide a win-count summary (best-per-row across methods)? The current cell format makes it very difficult to assess the method’s overall standing.

  2. The ablation in Table 1 and Table 4 shows Ours-FEM tying or beating Ours-NN on 7 of 10 datasets. Does this imply the HGNN+ layers are only useful at high hyperedge cardinality, and if so, how should readers interpret the "unified NCO framework" positioning?

  3. In Fig. 6, the "trivial algorithm" baseline is your own naive implementation of Eq. 4. Could you also compare against PI-GNN’s claimed trivial PUBO extension on the same hypergraphs?

  4. Table 2 shows HyperNCO losing to degree-based greedy on five datasets. Given this and the SCIP wins on hypergraphs, what is the use case where HyperNCO is the method of choice for coloring?

  5. Table 8 distinguishes Uniform and Non-uniform hypergraphs. Could you specify the cardinality distribution used for the Non-uniform case?

2 comments

We thank the reviewers for their careful reading and comments. We address the weaknesses they mentioned below.

Weakness 1:

We thank the reviewer and agree with the empirical observation. From Tab. 1 (Page 7) and Tab. 10 (Page 18), we observe: large-carcinality hyperedges introduce high-order terms that require mixing vertex features. We summarize the win-count of HyperNCO variants (NN and FEM) accross various cardinality in Tab. 3 (Page 8).

The "unified" claim refers to the formulation (One-hot encoded PUBO cost for partitioning, coloring, and max-k-cut) and the training pipeline (GPU implementation in Eq.5 and the annealing stategy), not to the encoder (HGNN+, GraphSAGE). We will make this explicit in the revision by phrasing the claim as "a unified formulation and training pipeline with an optional encoder, Contribution 2) in Page 2".

Weakness 2:

We agree that Tab. 1 is dense. 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 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.

Weakness 3:

In Tab. 4 (Page 10), we observe that HyperNCO achieves a trade-off between runtime and chromatic number​ across four hypergraph datasets (High, Cora, PubMed, and Cooking 200). We think that this is valuable in specific scenarios, such as channel allocation in dynamic wireless networks.

As the reviewer suggested, our previous description in Section 5.2 was inappropriate. Therefore, we will revise the text at the end of Section 5.2 as follows: "HyperNCO achieves a trade-off between runtime and chromatic number across four hypergraph datasets (High, Cora, PubMed, and Cooking 200). This trade-off​ is valuable in specific scenarios, such as channel allocation in dynamic wireless networks. Exact solvers like SCIP and Gurobi struggle to compute initial solutions under rapidly changing network topologies. Meanwhile, although greedy algorithms are fast, they only yield suboptimal (or excessively large) chromatic numbers on these hypergraphs."

Weakness 4:

We thank the reviewer for the valuable feedback. We agree that ϕ(x)=1−∑jxij2\phi(x)=1-\sum_j x_{ij}^2 is the Gini–Simpson index. Moreover, we have checked the paper of CRA and found the k-Potts penalty in its Appendix.

In the revision, we do not claim Eq. 9 as a novel penalty. In Sec. 4.3 we clarify that for α=2\alpha=2 the CRA kk-Potts penalty reduces to ΦCRA=γk2ϕ(x)+γn(k+1−k2)\Phi_{\mathrm{CRA}}=\gamma k^2 \phi(x)+\gamma n(k+1-k^2) and ∇xΦCRA=k2∇xϕ\nabla_x \Phi_{\mathrm{CRA}}=k^2 \nabla_x \phi. Eq. 9 is therefore identical to CRA's penalty up to an additive constant and a rescaling of γ\gamma absorbed into the schedule.

We will reviese the Abstract and Introduction so that this is presented as an empirical study rather than as a new penalty. In Sec. 1, our contribution is "3)Empirical Study of the Annealing Scheme for One-hot k-labeling Variables. Inspired by CRA Ichikawa 2024, we introduce and empirically study the continuous relaxation annealing strategy built on the Gini-Simpson index (i.e. the α=2\alpha=2 member of the CRA's penalty family)".

Question 1:

Please refer to our respond to Weakness 2.

Question 2:

Please refer to our respond to Weakness 1.

Question 3:

The trivial algorithm in Fig. 6 is PI-GNN's one-hot encoded PUBO extension. We named it the trivial algorithm​ because PI-GNN did not originally provide​ an implementation for one-hot PUBO. We will explicitly clarify​ this issue in Appendix B.2 (Page 14).

Question 4:

Please refer to our respond to Weakness 3.

Question 5:

We provide the implementation details​ of the non-uniform setup​ in footnote 5 of Appendix B.3 (Page 16) as follows:

"We generated non-uniform hypergraphs using a low-order-first edge-size distribution from the DHG library. Given a vertex set VV, the cardinality kk of each hyperedge is sampled from {2,…,∣V∣}\{2,\ldots,|V|\} according to pk=3−(k−2)∑j=2∣V∣3−(j−2)p_k=\frac{3^{-(k-2)}}{\sum_{j=2}^{|V|}3^{-(j-2)}}, where k=2,…,∣V∣k=2,\ldots,|V|. Subsequently, we select kk vertices uniformly at random to form a hyperedge. Consequently, the proposal weight for a hyperedge cardinality decreases by a factor of three whenever the cardinality increases by one. This favors smaller hyperedges while allowing hyperedges of different sizes."

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.

Reviewer_g13nOpenReview ↗

Response to rebuttal

Thank you for your detailed rebuttal. My response is below.

Weakness 1: The authors propose a reframe around “a unified formulation and training pipeline with optional encoder”. They do not dispute the observation that the HGNN etc layers don’t really add much on 7 out of 10 datasets.

Weakness 2: The authors have provided a win-count summary as requested. Their method wins on 46/50 (92%) comparisons against heuristics and 26/46 (57%) against Gurobi under matched balance conditions. My only issue here is that the method is not meaningfully competitive against Gurobi, which is the fair comparison under matched balance conditions.

Weakness 3: Here the authors have decided to reframe as a runtime vs chromatic number tradeoff. They state one use case: “channel allocation in dynamic wireless networks” where exact combinatorial solvers would struggle with changing topology, and greedy would be suboptimal. I accept this reframe, but with the caveat that the authors don’t empirically demonstrate this claim on dynamic hypergraph coloring.

Weakness 4: The authors concede that Eq 9 is the Gini-Simpson index and not the Gini coefficient, and now state that they don’t consider Eq 9 as a novel contribution.

Given the authors’ rebuttal and also the points raised by the other reviewers, I raise my score from 1 to 2.

Comments on the paper

2 comments

Revision summary — all items below are highlighted in blue in the revised PDF

Concern raisedWhere it is now addressed
Eq. 9 vs. CRA (all three reviewers)No longer claimed as novel: Sec. 4.3 (p. 6) states equivalence to CRA's k-Potts penalty up to scaling and an additive constant; Abstract and contribution 3 reworded as an empirical study
Eq. 12 / Eq. 10 (Reviewer2 W2, Reviewer3 W2)This was a typo in formalizing the code into math.
Tab.1 used different balance requirements (Reviewer1 W2, Reviewer2 W2, Reviewer3 W3)Added Ours-FEM_bal rows in Tab. 1 (p. 7) at exactly 0% imbalance. Matched-balance win counts in Tab. 2 Panel B (p. 8): HyperNCO 26 vs. Gurobi 20
"Unified framework" overclaimed (Reviewer1 W1)Narrowed to the formulation + training pipeline with optional encoder.
Fig. 1–3 readability, missing pseudocode (Reviewer3 W1)Figs. 3 redrawn with labelled tensor shapes. Algorithms 1–3 in App. D (pp. 19–22)
Fig. 4 edge count. Cooking200 duplicating Tab. 1 (Reviewer2 Q4)These were typos. Fig. 4 instances have 7,000 edges (corrected).
Non-uniform cardinality distribution (Reviewer1 Q5)Clarified in Footnote 5, App. B.3 (p. 16)
FEM timing protocol (Reviewer3 W3)Clarified in Footnote, p. 8
PI-GNN "trivial" baseline (Reviewer1 Q3)Clarified in App. B.2 (p. 14)

We thank the reviewer for the valuable feedback, and especially for helping us recognize the similarity between Eq. 9 and the k-Potts penalty in CRA. We have taken this observation seriously: the revised manuscript no longer claims this formulation as novel, and instead positions it as an empirical study.

We would like to clarify, however, that the central motivation of this work is to address the severe computational bottleneck in solving general multi-variable, multi-label problems​ (e.g., hypergraph COPs). From this perspective, the mechanism in Fig. 3 is crucial: it is precisely what makes solving hypergraph COPs tractable at scale, and it is where a substantial part of our technical contribution lies. Accordingly, we believe the paper's contributions remain valid:

  • A unified formulation + training pipeline​ for hypergraph COPs, with an optional encoder;
  • A scalable mechanism (Fig. 3) that removes the key computational bottleneck;

The remaining items (e.g., Eq. 12, the Fig. 4 edge count, and the Cooking200 duplication) were presentation errors (typos), now corrected as detailed in the table above.

Happy to provide any additional details.

We thank all reviewers for their time and careful reading. We are grateful to Reviewer 3 for maintaining a positive assessment, and to Reviewers 1 and 2 for raising their scores after reviewing the revised manuscript.

Many thanks, The Authors.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.