acceptodds
Withdrawn from ICLR 2027

Lifted Geometry-Aligned GNNs for Min--Partition

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Min--Partition is a fundamental NP-hard combinatorial optimization problem on graphs. Although learning methods have shown promise, generic architectures often fail to exploit the underlying problem geometry. This limitation can impair generalization and require costly adaptation for each new instance during inference. We introduce a KL family with node-specific weights for the probability simplex relaxation, accounting for node heterogeneity in the objective while respecting the simplex constraints. We select the node weights by minimizing a tractable spectral surrogate for relative smoothness, yielding the Geometry-Aligned KL (GA-KL) divergence. Mirror descent (MD) induced by GA-KL then provides an analytical solver aligned with the relaxed Min--Partition problem. We develop Lifted Geometry-Aligned Graph Neural Networks (LGA-GNNs) by lifting the GA-KL MD updates into latent spaces of higher dimension and adding trainable transformations to enhance representation ability. Recurrent application of the learned operator with shared and fixed parameters enables deeper refinement at inference without parameter updates or growth in model size. Experiments on random regular graphs with up to nodes, Gset instances, and diverse real-world networks demonstrate strong solution quality and practical scalability under matched runtime budgets. Moreover, LGA-GNN generalizes effectively without retraining to graphs that are larger and to heterogeneous real-world structures.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
Min-k-Partition, Learning-to-Optimize, Graph Neural Networks

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_sJv7OpenReview ↗
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
  1. The paper is well-organized. The theoretical sections are detailed and easy to follow.
  2. The method is practical.
Critical weaknesses
  1. 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.
  2. 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.

  1. 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.
  2. 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
  1. 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.
  2. 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.
Reviewer_Cu4dOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes a learning to optimize approach for the min k partition problem. Specifically, it focuses on a continuous nonconvex formulation of theproblem and proposes a graph neural network

Critical strengths
  • The paper achieves promising empirical results using a nonconvex continuous formulation of a discrete combinatorial problem. The proposed approach is quite fast and can scale to very large graphs. The method has the potential to establish state of the art results even though local search heuristics (neural and otherwise) and exact solvers are hard baselines to beat for these problems. So overall that makes the proposed approach quite promising.
Critical weaknesses

The paper's experimental results while strong seem also somewhat insufficient to me. That's my main concern. There are a few issues:

  • The experimental setup may not be telling us the full story due to the runtime constraints that have been imposed. For example, it has been observed in the literature on neural combinatorial optimization that neural network based methods can outperform solvers like gurobi when the solver's time budget is limited. However the solvers may be able to catch up pretty quickly as the budget grows. Similar things can be said for certain search heuristics. So a particularly illuminating comparison can be how gracefully the performance scales (Say on GSET) compared to those other methods when more budget is provided. I can see already this type of comparison in your detailed results so I'm curious whether your method reaches a plateau fast or if it's able to stay ahead of gurobi given more time. Obviously, Gurobi is guaranteed to achieve optimality given enough time budget but that in principle could be several hundreds of seconds. On the other hand, if it solves the instance within a minute then obviously we would have to know if the proposed method is capable of achieving that in comparable time. Even in your results we can see gurobi plateau for 5 seconds and then break out of those plateaus. Different methods scale differently with time so having a more comprehensive understanding of how that works with your method is essential before we can accept the paper.

  • Another concern about the setup is the lack of certain known strong baselines. For example, AnyCSP[1] is another RL based method that achieves strong results on maxcut (and can be adapted to k-cut). OPTFM[2] is a foundation model that has also shown strong results on maxcut. I think the timing comparisons I discussed above would be interesting given that AnyCSP/OPTFM could do really well given sufficient budget. The paper by Ma and Hao [3] also seems to be a relevant baseline that could checked especially for larger k.

  • Finally, given that the method is general for all values of k, while extensive maxcut results can make a strong case, it's obviously also important to see how well it performs for other values of k (even just against gurobi could be a good start but obviously adding a couple more baselines like the ones I mentioned would make a stronger). An experiment where you increase the k larger values (say up to 5 as they did in [3] or even more).

Overall the paper looks quite promising but since the contribution in my eyes is primarily empirical and the focus is on a specific problem, since the experimental results suggest that the method could be perhaps even the best for the problem, then how the method performs needs to be carefully dissected before the paper is accepted.

  1. One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfaction (Toenshoff et al)
  2. OPTFM: A Scalable Multi-View Graph Transformer for Hierarchical Pre-Training in Combinatorial Optimization (Yuan et al)
  3. A Multiple Search Operator Heuristic for the Max-k-cut Problem
Questions for authors

This is a question regarding the overall contribution. The paper leverages a standard nonconvex continuous formulation of the problem (e.g., similar to ROS but ok more broadly this is essentially a multilinear extension/expectation under independent categorical variables) and it innovates from previous work through this mirror descent/KL geometry approach. Couldn't you have essentially implemented a very similar method without the KL geometry (i.e., just doing projected GD updates instead)? What makes KL necessary or helpful here?

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

The paper proposes a learned Min-k-Partition solver derived from mirror descent with a graph-dependent weighted KL divergence. It introduces geometry selection, higher-dimensional neural updates, and recurrent refinement with shared parameters. The theory establishes properties of the analytical updates and their representation by the network. Experiments evaluate solution quality, runtime, and transfer across random regular graphs, Gset, and real-world networks.

Critical strengths

The architecture has a clear optimization-based motivation. The connection between weighted KL geometry, mirror descent, and message passing makes the design understandable.

The experiments cover several graph families and demonstrate transfer to much larger instances. The end-to-end timing protocol includes preprocessing, geometry construction, and rounding.

Critical weaknesses
  1. The experiments does not establish the benefits of the two central contributions, geometry selection and lifting. The million-node regular-graph experiments use uniform geometry. On signed graphs, Table 1 reports gains of 0.14–0.18 percentage points at roughly 30% additional runtime, without an equal-time control. The lifting experiments omit a learned width-k model. The representation results show that the network can imitate analytical MD, but do not explain the advantage of additional latent dimensions. These gaps leave the main contribution insufficiently supported.

  2. The comparative evaluation is not strong enough to establish a convincing advance. For k=3, the competitors are limited to Genetic, Gurobi, and ROS, with no dedicated k-way partitioning heuristic. Essential baseline configurations and the matched GNN’s update rule are also missing. Stronger comparisons and reproducible implementation details are needed to assess the reported advantage.

Questions for authors
  1. Does spectral geometry outperform uniform geometry when the latter can use the additional preprocessing time for refinement or restarts?
  2. How does a learned width-k model perform? How does analytical MD compare under the same runtime budget with a tuned step-size rule?
  3. Can you provide complete baseline configurations and the matched GNN’s update equation? Why was a specialized k-way partitioning heuristic omitted?
  4. Is the geometry nondegradation property independently verified for the practical implementation? A small Lanczos residual alone does not certify the largest eigenvalue.

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

Related papers

Discussion (0)

Sign in to comment.