acceptodds
Under review as a conference paper at ICLR 2027

A Threshold-Search Projected Gradient Method for Graph-Cut Optimization

Abstract

Many graph-cut clustering models can be formulated as the minimization of differentiable functions over one-hot assignment matrices. Projected gradient (PG) methods provide a natural first-order approach for such problems. Their usual stepsize strategies, however, may lead to stagnation due to the discreteness of the feasible set: once the stepsize is sufficiently small, the projection returns the current assignment matrix unchanged. To address this issue, we characterize the threshold structure of the projection mapping with respect to the projection parameter. We show that it is piecewise constant and can change only at a finite set of explicitly computable row-wise thresholds. Building on this structure, we propose the Threshold-Search Projected Gradient (TSPG) method, which searches directly over this finite set of thresholds rather than continuously adjusting the stepsize. TSPG accepts successive trial moves that satisfy sufficient decrease and terminates after finitely many outer iterations. For graph-cut objectives, we further derive incremental updates that reduce the cost of objective and gradient evaluations. Experimental results demonstrate the effectiveness and computational efficiency of TSPG compared with existing graph-cut solvers.

Primary area:
optimization
Keywords:
projected gradient, threshold search, stepsize selection, graph-cut clustering, incremental updates

Reviews

Among:
Shape:
1234this paper, Bottom 25%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.75 over 4 reviews, above 25% of the others.
Reviewer_yFsAOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors propose a threshold search algorithm for a projected gradient method for clustering over data methods. The method is theoretically supported by the one-node local optimality.

Critical strengths
  • The paper is technically sound and well-written.

  • The one-flip search theory.

  • The computational complexity is appreciated.

Critical weaknesses
  • Arguing that the method is a not a specialized optimization method is weak (lines 48 to 51). The proposed method, similar the refs in line 49, is also a specialized method.

  • While the continuous relaxation may enable scalability, the algorithm still search over a discrete set.

  • Although the authors do a good job in describing previous methods, I am not too familiar with the literature (and hence my confidence). From an optimization perspective, the proposed method is just a projection method with a greedy-like search for the thresholds.

  • Why X_bar in the RHS of Eq. (6) is in a set? The projection operator clearly return a matrix.

  • We typically relax to continuous domain for scalability. However, the proposed method requires to search over a discrete set (indexed by the square brackets) for every gradient update (indexed by the regular brackets). I understand that previous methods can stagnate, but the authors don't show an example of this, only an overall result comparison. I recommend showing this empirically to support the proposed method.

  • Why only one c? How was it chosen, and what is the sensitivity of the proposed approach to it?

  • An illustrative diagram (with indices) with mathcal{I} and mathcal{M} will make the description of the notation (and generally the method) easier to follow.

  • While the PG interpretation part (Section 3.2) well explains the intuition, m_t from Algorithm 1 is not mentioned. Can the authors elaborate more?

  • m_t comes again in Theorem 2 without proper description. This is an important part.

  • Why there is no proof for Prop 2?

  • In Theorem 2, the inner search loop searches over the 1-flip neighborhood, and if m_t>=1, then the obj might minimize. The result only covers the one-flip neighborhood. Does the algorithm search over other sets? For example, MaxCut has a 2-flip procedure which means there is a search over a different neighborhood.

  • What is the feature extractor function for obtaining v? And what is the impact of its choice? A comparison is needed for other extracting functions.

  • Can you define the assignment evaluation measure?

  • Why there is no comparison with pure discrete methods? For example, a greedy approach or an integer programming approach (if there are any)?

  • Can the method be GPU-parallelizable? Given the use of the gradients, a discussion about that is recommended here to evaluate scalability.

  • How K were selected for each dataset? Can you provide an explanation? What happens if you vary K per each dataset?

  • When you say averaged over 20 runs? Where does the randomness comes from (initialization of X^(0) or the initial ordering)? Details are needed here. How do you initialize X^(0)?

Questions for authors

Please see weaknesses.

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

The paper optimizes graph-cut objectives (Ncut, MMcut) directly over one-hot assignment matrices with projected gradient. It shows that small stepsizes make the projection stagnate (Prop. 1) and that the projection is piecewise constant, changing only at N row-wise thresholds (Prop. 2). TSPG sorts these thresholds and accepts successive one-vertex reassignments while a sufficient-decrease test holds, with incremental O(N) updates. Experiments on 8 UCI datasets report shorter runtimes than coordinate descent (CD) and FPC at comparable objective values.

Critical strengths
  • The paper is clearly written and mathematically sound. Props. 1–2 and Thms 1–2 are correct and fully proved.

  • The characterization of the PG path over one-hot matrices is exact and simple, and the link to a shifted problem (Eqs. 18–20) is neat.

  • The incremental formulas (Eq. 23, Appendix D) are correct and practical, and they handle domain issues properly (Eq. 41).

  • The evaluation reports objective values alongside clustering metrics, which is appropriate for a solver paper. FPC is run with the authors’ code.

Critical weaknesses
  • The method amounts to a gradient-ranked greedy local search. The threshold ρ̄_i (Eq. 11) is exactly the first-order predicted gain of moving vertex i. TSPG thus sorts single-vertex moves by linearized gain and applies them while each yields a decrease of at least c. The PG and threshold framing reinterprets classical move-based partitioning (Kernighan–Lin, Fiduccia–Mattheyses), and this connection is not discussed.

  • The theoretical guarantees are weak.

    • TSPG stops as soon as the first-ranked move fails. Thm 2 therefore only gives one-flip optimality of a surrogate model Q_c, which is weaker than the one-flip optimality of Φ that CD provides.
    • Finite termination (Thm 1(iii)) holds for any strict-descent method on a finite set. With c = 10⁻⁹, the bound is uninformative.
  • The benchmark graphs appear nearly uninformative.

    • Across all datasets, the MMcut values are close to K² and the Ncut values close to −1 (Table 1). These are the values attained by balanced partitions of a near-constant similarity matrix, which suggests that the fixed-bandwidth kernel exp(−‖vᵢ − vⱼ‖²) yields an almost flat graph. Consistently, NMI is close to 0 on several datasets, and the solvers differ only in the third decimal.
  • Some efficiency claims are not supported as stated.

    • Avg-AssignE counts sweeps for CD (N × K moves each), iterations for FPC and single moves for TSPG, so the claim of “fewer evaluations” compares different units.
    • The claim of lower runtime than all solvers is contradicted by Table 1, where MM-Mcut is faster on CTG and Optdigits.
  • Protocol and scope.

    • No standard deviations are reported.
    • CD is run with random rather than its dedicated initialization, and it is unclear whether the original code was used.
    • Spectral clustering, Graclus and Nie et al. (2024a) are missing as baselines.
    • The cost analysis omits the dense W (O(N²) memory), and the largest graph has only N = 30k.

The results are correct, but the contribution remains modest for a venue of this level, and the near-degenerate objectives limit the empirical significance. The closest prior works are the CD solvers of Nie et al. (2024b) and Li et al. (2026), together with classical move-based partitioning; the actual contribution is the gradient-based ordering of candidate moves. The writing and notation are clear. Several directly relevant references are missing: weighted kernel k-means for discrete Ncut (Dhillon, Guan & Kulis, TPAMI 2007), Kernighan & Lin (Bell System Technical Journal, 1970), iterative hard thresholding onto nonconvex sets (Blumensath & Davies, ACHA 2009) and tight relaxations of balanced cuts (Hein & Bühler, NeurIPS 2010).

Questions for authors

Suggestions

  • State the equivalence to gradient-ranked local search and position the method against Kernighan–Lin/FM and Graclus. Add a variant that keeps scanning after a failed trial, so that the terminal point is one-flip optimal for Φ.
  • Use informative graphs (self-tuning bandwidth, k-NN sparsification), and report cluster sizes and the objective gap to the best known value.
  • Report single-move evaluations and runtimes with standard deviations, including W construction, and add large sparse graphs (N ≥ 10⁵).

Questions

  • What bandwidth and normalization were used, and what are the cluster sizes at the reported solutions?
  • What fraction of TSPG terminal points are one-flip optimal for Φ?
Reviewer_Yo9xOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

For graph-cut optimization problem, this paper proposes a threshold-search projected gradient method. The main contributions are summarized as follows: (1) The authors characterize the threshold structure of projected gradient updates over one-hot assignment matrices and proposes a threshold-search strategy that searches over a finite set of candidate solutions instead of continuously adjusting the step size. (2) The authors establish finite termination and one-flip local optimality properties and develops an incremental update strategy to improve computational efficiency.

Critical strengths

(1) The proposed threshold-search strategy avoids ineffective updates caused by excessively small step sizes, improving the efficiency of projected gradient method. (2) An incremental update strategy is developed to reduce the computational cost of objective function and gradient evaluations, further improving optimization efficiency.

Critical weaknesses

(1) Some mathematical notations are not clearly defined or consistently used. (2) This paper lacks sufficient comparisons and ablation studies. For example, comparisons with projected gradient methods using fixed or adaptive step sizes are missing. Moreover, the individual contributions of threshold search and incremental updates are not evaluated. (3) Although TSPG improves computational efficiency on some datasets, its advantages over existing discrete optimization methods are not consistent. The experimental results do not sufficiently demonstrate the practical benefits of TSPG. (4) TSPG accepts the first candidate satisfying the discrete condition. Could this strategy overlook better candidate solutions and affect the quality of the final solution? (5) The experiments report average objective function values over multiple runs but do not provide the frequency with which each method obtains better solutions. Such comparisons would help assess the optimization quality of TSPG.

Questions for authors

Could the authors clarify whether accepting the first candidate satisfying the sufficient decrease condition affects the quality of the final solution?

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

The paper targets the optimization on binary or discrete values. They are first formulated as optimization problem on binary row-stochastic matrices (single 1 entry per row), and the authors suggested a Threshold-Search Projected Gradient (TSPG) approach: the author propose using the break-point gradient stepsize at which the projected one-hot encoding flips. The algorithm sorts these thresholds and does a successive assignments until we reach the regime where a single flip does not generate a sufficient decrease. The experiments compare the algorithm on runtime and performance on MMCut and Ncut objectives against Coordinate descent, FPC for Ncut, and Mcut for MMCut.

Critical strengths

The paper is easy to read and follow with detailed proof steps. The gradient step exploits the geometry of the problem. The guarantees of termination are useful.

Critical weaknesses

I found the main weakness of the current manuscript is the reported results. They reflect a running time advantage, but ACC and NMI is moderate to weak on the UCI datasets and is insufficient to show any gap.

The theory is not significant (for instance, Proposition 1 is trivial) and the paper has little added contribution compared to the extensive literature on discrete/combinatorial optimization. The termination guarantee is not enough to justify the usefulness of an iterative algorithm.

This assessment is made based on extensive literature that introduces more powerful heuristics for graph cuts (Dhillon, Guan, and Kulis (2004), Kernel k-means, Spectral Clustering and Normalized Cuts, which already connect normalized cut to weighted kernel k-means and derive an objective-decreasing algorithm under the positive-definite kernel condition. Dhillon, Guan, and Kulis (2007), Weighted Graph Cuts without Eigenvectors: A Multilevel Approach, in Section 5.4 explicitly discusses single-point moves and chains of moves. The paper should distinguish its contribution from these methods, especially experimentally.

We should keep in mind that minimizing NCut is NP-complete, so its difficulty has to be taken into consideration when presenting new heuristics (Shi and Malik (2000), Normalized Cuts and Image Segmentation). Unfortunately, the proposed method fails to find a good solution even in the following toy example: consider K = 2 and the adjacency WW:

W = [0  1  1  1
     1  0  1  2
     1  1  0  2
     1  2  2  0].

Initialize the clusters as A = {1, 2} and B = {3, 4}, then d = (3, 4, 4, 5). The Ncut objective: Φ(X)=−2/7−4/9=−46/63.\Phi(X) = -2/7 - 4/9 = -46/63.

For a cluster indicator x_k, the gradient of its objective term is

+ (x_k^T W x_k) d / (d^T x_k)^2.$$ Since there are only two clusters, each row has a unique alternative label. Equations (11) and (15) give the thresholds: $\rho = (528, 1376, 640, 1808) / 3969$. The unique descending order is **4, 2, 3, 1**. The actual objective values of all four one-flips: | Reassigned vertex | Resulting partition | Phi after the move | Change from the initial Phi | | --- | --- | --- | --- | | 4, the first trial | {1, 2, 4} / {3} | -2/3 | +4/63, worse | | 2 | {1} / {2, 3, 4} | -10/13 | -32/819, better | | 3 | {1, 2, 3} / {4} | -6/11 | +128/693, worse | | 1 | {2} / {1, 3, 4} | -2/3 | +4/63, worse | - Algorithm start with node 4, its objective increases, so Eq (17) fails for every c > 0. - The algorithm executes `break`, no accepted moves -> terminates at the initial partition. - It never examines node 2, whose improvement is ~ 0.03907 > c. - Exhaustive evaluation of all 14 nonempty two-cluster confirms that this is also globally optimal for this instance, up to exchanging cluster labels. The example also satisfies Theorem 2's assumption that the first trial belongs to the objective's domain. The limitation also extends beyond stopping at the first failure. If all four prefixes of the frozen threshold order are evaluated, their objective values are -2/3, -1/2, -2/3, and -46/63. None improves the initial objective. Thus, even exhaustively searching this particular projected-gradient path would miss the improving one-flip.
Questions for authors

First question is about addressing the points I raised, in addition to:

  • How does the one-flip optimality translate to the original Φ\Phi?
  • How much of the runtime advantage is attributed to TSPG early stopping and not its iteration efficiency? what if we start with TSPG and add CD on top?
  • How does the proposed method differ from Dhillon et al. 's work on single-point refinement?
  • How sensitive the speedups and the solutions to initializiation?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.