{"id":"4ceeca1c-31bf-4510-aaa5-1a3aee213f47","arxiv_id":"2502.03405","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"PRCut optimizes an upper bound on the expected graph ratio-cut via probabilistic assignments and stochastic gradients, beating spectral relaxation and matching state-of-the-art deep clustering on image benchmarks.","lead":"This paper trains a neural network to split data into groups by minimizing a mathematical measure of how much similarity crosses group boundaries, using random assignments instead of eigenvectors. The method is competitive with classic spectral clustering and newer deep clustering methods, and can judge the quality of self-supervised representations.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The §4.2 'unbiased gradient' claim is the load-bearing assumption: Algorithm 1's estimator contains 1/p̄_ma and 1/p̄_ma² with p̄_ma a random moving average, so Jensen's inequality (E[1/Z] ≥ 1/E[Z]) makes it biased; asserted without proof, this leaves the online-learning guarantee unsupported.","rationale":"The paper contributes a probabilistic relaxation of ratio-cut: independent categorical assignment variables, an exact expected-ratio-cut expression (Thm 4.1 via Lemmas 4.1–4.2), an upper bound (Lemmas 4.4–4.5, eq. (7)), and an online SGD scheme claimed to have an unbiased gradient. I checked the derivation chain in good faith and it is largely sound: Lemma 4.1 follows from independence of the a_i; Lemma 4.2 is the standard Poisson-binomial integral identity; Lemma 4.4 is a valid Jensen bound; Lemma 4.5's constant e²/(2n) is valid, since the factor (n/(n−2))^{n−2}·n/(n−1) approaches e² from below, so the appendix's '≈' can be made rigorous. Credit is also due for releasing code. The load-bearing problem is exactly where the reader placed it: Section 4.2 asserts unbiasedness with no proof, and the claim is false as stated because the estimator evaluates eq. (8) at the random moving average p̄_ma, whose reciprocal is biased upward relative to the reciprocal of its mean (Jensen), and whose lag under β_t = β/t does not vanish during non-stationary training. This is not a disagreement with the community; it is an internal gap between the announced guarantee and the implemented estimator. Consequently the paper does not establish that PRCut optimizes eq. (7), and its theoretical headline is unsupported; the empirical tables (which lack error bars) can stand as heuristic evidence but cannot repair the dropped guarantee. My concrete test — comparing E[ĝ] with exact full-batch ∇Lrc, with and without the moving-average denominator — would settle the matter. Since this is the same weakest assumption the reader identified, my read does not move the verdict: the paper remains CONDITIONAL, requiring either a proof of unbiasedness under explicit assumptions, a quantitative bias bound, or removal of the claim.","tokens_in":1361,"tokens_out":1665,"duration_ms":301834,"concrete_test":"On a small problem (e.g., N=256 MNIST samples, k=10, a fixed softmax encoder θ, W the kNN kernel), compute the exact gradient ∇_θ Lrc(W,P(θ)) by full-batch automatic differentiation through the denominator p̄(θ). Then, maintaining p̄_ma exactly as in Algorithm 1 (β_t = β/t, β=0.8), average the algorithm's estimator ĝ over ~10^5 batch draws to estimate E[ĝ]. If ‖E[ĝ] − ∇Lrc‖/‖∇Lrc‖ exceeds a few percent, or cosine similarity falls below 0.99, the §4.2 unbiasedness claim is refuted as stated. Control: repeat with p̄_ma fixed at the exact p̄(θ); conditional on a constant denominator the estimator should be unbiased, isolating the Jensen/lag bias of the moving average. This settles directly whether the online loss being minimized is the stated upper bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The load-bearing premise is the abstract's claim of 'an unbiased estimate of its gradient.' The objective Lrc(W,P(θ)) in eq. (7) contains the factor 1/P̄_{:,ℓ}, and P̄_{:,ℓ} = (1/n)Σᵢ P_{i,ℓ}(θ) is itself a function of the network parameters, so the true chain-rule gradient includes a term from differentiating through this denominator. Algorithm 1 instead substitutes the moving average p̄_ma (line 7) and back-propagates Tr[P^l sg(Ṗ^l)ᵀ + P^r sg(Ṗ^r)ᵀ] (line 9), where Ṗ is evaluated from eq. (8) with p̄ := p̄_ma. Because p̄_ma is a random β_t-weighted average of batch means, the estimator depends on 1/p̄_ma and 1/p̄_ma². By Jensen's inequality, E[1/p̄_ma] ≥ 1/E[p̄_ma] and E[1/p̄_ma²] ≥ (1/E[p̄_ma])², strictly whenever p̄_ma has positive variance; hence E_batches[ĝ] ≠ ∇_θ Lrc(W,P(θ)). With β_t = β/t, the moving average also lags any drift of p̄ during training, adding a bias that need not vanish at finite t. No proof of unbiasedness is given in §4.2 or Appendix B; Appendix B.2 differentiates only the pointwise loss, and the footnote's replacement of 1/n by 1/b in eq. (8) rescales the denominator-gradient term by a batch-size-dependent factor, a further mismatch with eq. (7). A second premise — that minimizing the loose bound Lrc (with its e²/(2n) constant) yields low true expected ratio-cut — is also unanalyzed, since Lemma 4.5 proves only an inequality, not closeness of minimizers. The gradient claim is the linchpin: without it, the paper does not establish that SGD minimizes its stated objective, and the online-learning contribution rests on an unproven surrogate.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PRCut, a deep clustering method that models binary cluster assignments as random variables and optimizes an upper bound on the expected ratio-cut. The authors derive an exact integral expression for the expected ratio-cut, an upper bound via a Poisson-binomial argument, and a stochastic optimization procedure for learning the assignment probabilities with a neural network. They report experiments on MNIST, Fashion-MNIST, CIFAR-10, and CIFAR-100, comparing against spectral clustering and several deep clustering baselines, and they also evaluate PRCut as a tool for assessing self-supervised representations.","tokens_in":16838,"tokens_out":13346,"duration_ms":117427,"significance":"If the theoretical claims were fully sound, this would be a valuable contribution: it offers a parametric, online alternative to spectral clustering that avoids eigendecomposition, and the probabilistic derivation of the expected ratio-cut is an elegant and original starting point. The empirical study is reasonably broad, the code is released, and the use of the method to score representation quality is a useful idea. However, the central theoretical guarantee — an unbiased gradient estimator for the online objective — is not established and is mathematically suspect, and the displayed gradient formula in Equation (8) does not match the derivative of the stated objective. These issues compromise the paper's main claim and require substantial correction.","major_comments":[{"comment":"The claim that the stop-gradient moving-average estimator yields an unbiased gradient is not proved and is mathematically suspect. The objective Lrc contains the factor 1/p̄ with p̄ = (1/n)∑ p_i(θ), a parameter-dependent quantity. Algorithm 1 replaces p̄ by a moving average p̄_ma and stops the gradient, so the true chain-rule term arising from differentiating through the denominator is discarded. Moreover, because p̄_ma is itself random, Jensen's inequality gives E[1/p̄_ma] ≥ 1/E[p̄_ma] whenever p̄_ma has positive variance, so the reciprocal is generally a biased estimate. Appendix B.2 only differentiates the pointwise summand and does not address differentiation through the average p̄. The abstract's 'unbiased estimate of its gradient' is therefore unsupported; the claim must be either proven under explicit assumptions or withdrawn.","section":"Section 4.2 and Algorithm 1"},{"comment":"Equation (8) does not appear to be the correct derivative of Lrc as defined in Equation (7). For L = (1/p)∑_{a,b} W_ab(p_a+p_b−2p_ap_b) with p = (1/n)∑_m p_m, the derivative with respect to p_i is (1/p^2)[2p∑_j W_ij(1−2p_j) − S/n], where S = ∑_{a,b} W_ab(p_a+p_b−2p_ap_b). Equation (8) instead contains p∑_j W_ij(1−2p_j) (missing the factor 2) and, in the denominator term, only ∑_j W_ij(p_i+p_j−2p_ip_j) rather than the full S. As written, the update in Algorithm 1 is not the gradient of Lrc, so it is unclear what objective the online procedure actually minimizes. The authors should re-derive the gradient and correct Equation (8) and Appendix B.2.","section":"Equation (8) and Appendix B.2"},{"comment":"The proof contains an equality that is only an upper bound. After integrating (n/(n−2))^{n−2}(1−p̄t)^{n−2}, the exact value is (n/(n−2))^{n−2}[1−(1−p̄)^{n−1}]/((n−1)p̄), not (n/(n−2))^{n−2}/((n−1)p̄). The subsequent equality to (e^2−o(n))/(np̄) is also asymptotic rather than exact. These steps can likely be repaired while preserving the inequality, but the proof as printed is inaccurate and should be corrected.","section":"Appendix A.6, proof of Lemma 4.5"},{"comment":"The paper proves only an upper bound on the expected ratio-cut; it does not analyze how close the minimizers of Lrc are to the minimizers of the true expected ratio-cut, nor how the KL regularization in Section 4.3 affects this relationship. The claim that PRCut 'optimizes the graph ratio-cut' is therefore supported only empirically, not by the theory. The authors should state this limitation explicitly and, if possible, provide a quantitative gap analysis or at least an experimental sanity check on the tightness of the bound.","section":"Section 4.1 and Lemma 4.5"}],"minor_comments":[{"comment":"The equality between the double-sum expression and Tr(P^{-1}(1_{n,k}-P)^T W P) is off by a factor of 2 for symmetric W; please verify and clarify the intended scaling, since the gradient and the learning rate depend on this factor.","section":"Equation (7)"},{"comment":"The paper reports 'bach size' instead of 'batch size', and there is a spacing issue in 'F ashion-MNIST'. More substantively, the number of random seeds or repeated runs for PRCut is not reported; spectral clustering is explicitly reported as the best run, so a fair comparison should state the variance or number of runs for PRCut.","section":"Section 5, experimental setup"},{"comment":"The notation β_t = β/t is introduced in the moving-average update, but the hyperparameter table lists only a single β value; please clarify how β_t is computed in practice (e.g., whether t is reset each epoch or is the global step count).","section":"Algorithm 1 and Section 4.2"},{"comment":"The description of the k-nearest-neighbor graph says the kernel is set to 1 when one vertex is among the other's k nearest neighbors, but the experiments list k = 100 while the graph size k is also used as the number of clusters elsewhere; please disambiguate the two uses of k.","section":"Section 4.4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript appears to have been accepted at or submitted in connection with AISTATS 2025, but the present version's theoretical claims need careful reworking before journal publication. In particular, the 'unbiased gradient' assertion is a headline contribution and is not supportable as stated; the authors should either prove a corrected statement (perhaps under strong assumptions or with a different estimator) or remove the unbiasedness claim and replace it with an honest characterization of the estimator's bias. The factor-of-2 error in Equation (7) and the apparent error in Equation (8) suggest that the derivations were not carefully cross-checked; the authors should re-verify all algebra in Appendices A and B. The experimental results are valuable enough to warrant a revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the thing to know: this paper introduces a fresh way to sidestep spectral decomposition for ratio-cut clustering. The probabilistic relaxation is genuinely new—they treat cluster assignments as independent Bernoulli variables, derive the expected ratio-cut as a Poisson-binomial integral, and then upper-bound it into a form that is trainable by SGD. That part is worth reading. The empirical results are credible enough to take seriously: with label-based similarities, PRCut matches a supervised classifier; on self-supervised representations it gets state-of-the-art or competitive numbers on Fashion-MNIST and CIFAR-10. The method is scalable and uses a simple MLP with softmax, so it's practical.\n\nBut the paper overclaims its central theoretical statement. The abstract promises an unbiased estimate of the gradient. That is not true as written. The loss Lrc contains 1/P̄, where P̄ is the mean assignment probability—a function of the network parameters. The algorithm replaces P̄ with a moving average of batch means and then treats it as a constant via stop-gradient. Standard Jensen says E[1/Z] ≥ 1/E[Z], so the reciprocal of a noisy moving average is biased, and terms from differentiating through P̄ are dropped. No proof is offered; Appendix B.2 only differentiates the pointwise loss. The online-learning guarantee is therefore unsupported. The method may still work fine as a heuristic, but the paper should not claim unbiasedness without an argument.\n\nThere are smaller issues. The proof of Lemma 4.5 in Appendix A.6 makes an approximation that is not an upper bound, so the lemma is not rigorously established. The footnote swapping 1/n for 1/b in eq. (8) changes the gradient scaling. And the experiments would be more convincing with error bars and a spectral baseline on the same self-supervised representations; right now the comparison is only on raw features with 'SC (Best)' reporting.\n\nWho's this for? People who want a scalable, parametric alternative to spectral clustering, or an evaluation tool for SSL representations. They'll get a useful method and a clear direction. But they should not rely on the theoretical guarantee as it stands.\n\nRecommendation: send it to peer review—the idea is novel and the empirical work is promising—but the authors need to either prove the unbiasedness claim under precise conditions, or drop it and describe the estimator as biased but practical, and tighten the experiments with error bars and matched comparisons. A good referee could make this a solid paper.","headline":"Novel probabilistic ratio-cut relaxation with a real practical method, but the 'unbiased gradient' claim is unsupported and likely false; revise the theory and tighten the experiments.","tokens_in":17321,"tokens_out":7614,"would_cite":false,"duration_ms":65032,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A probabilistic relaxation of the graph ratio-cut, optimized by stochastic gradient descent, achieves lower ratio-cut and higher clustering accuracy than spectral relaxation across MNIST, Fashion-MNIST, and CIFAR-10.","keywords":["ratio-cut","spectral clustering","deep clustering","probabilistic relaxation","stochastic gradient descent","graph partitioning","self-supervised representations"],"falsifier":"Take a graph small enough to enumerate every cluster assignment (say $n = 12$), compute the exact expected ratio-cut, run PRCut's moving-average stop-gradient update for a step, and compare the direction it moves to the exact gradient of the true expectation; a mismatch on any instance would refute the unbiased-gradient claim.","tokens_in":16137,"feed_emoji":"📊","tokens_out":14049,"duration_ms":110881,"temperature":0.7,"pith_summary":"The paper tries to show that the combinatorial graph ratio-cut, a standard but NP-hard clustering objective, can be optimized directly in the probabilistic domain of cluster-assignment probabilities rather than through the spectral relaxation that solves a Laplacian eigenproblem. It proposes PRCut, an online algorithm that minimizes a smooth upper bound on the expected ratio-cut using stochastic gradient descent on a neural network that outputs cluster probabilities. If the method works as claimed, clustering can be trained end-to-end on similarity graphs without computing or storing the full Laplacian, and the resulting partitions reflect the similarity measure closely enough to match a supervised classifier when similarities come from the true labels. The paper further claims that the same machinery turns self-supervised representations into clusters of competitive quality, positioning PRCut as an evaluation tool for representation learning.","feed_headline":"Probabilistic ratio-cut clustering beats spectral relaxation online","feed_subtitle":"It turns ratio-cut into a smooth objective trainable by backprop, matching supervised accuracy on label similarities.","key_machinery":"The load-bearing object is the probabilistic assignment matrix $P \\in [0,1]^{n \\times k}$ with rows on the simplex, interpreted as Bernoulli parameters for each vertex's membership in each cluster; the ratio assignment for a cluster is $f^{(\\ell)} = a^{(\\ell)}/\\sqrt{|\\hat C_\\ell|}$. The derivation rests on an identity (Lemma 4.1) giving $E[(f_i - f_j)^2] = (p_i + p_j - 2p_i p_j) E[1/(1+|\\hat C_{\\perp(i,j)}|)]$, and on Lemma 4.2, which converts the reciprocal-size expectation into the integral $\\int_0^1 \\prod_{m\\neq i,j} (1 - p_m t) dt$. Lemma 4.4 bounds that integral by Jensen's inequality and produces the matrix surrogate $L_{rc}(W,P) = \\mathrm{Tr}(P^{-1}(1-P)^T W P)$. The final mechanism is an online training loop with a moving average $\\bar p_t$ and a stop-gradient operator, which the authors state gives an unbiased gradient of $L_{rc}$, plus a KL-divergence regularizer that prevents all probability mass from collapsing into one cluster.","core_discovery":"The central claim is that the expected ratio-cut of a random clustering has a tractable upper bound whose minimization is a faithful proxy for solving the original problem. For assignment probabilities $P$, the paper derives $L_{rc}(W,P) = \\mathrm{Tr}(P^{-1}(1-P)^T W P)$ as a surrogate objective (Equation 7), obtained by bounding an integral identity for the expected size-normalized cut. PRCut minimizes this surrogate plus a KL regularization term by backpropagating a stop-gradient estimate of $\\partial L_{rc}/\\partial P$ through a softmax network. The authors report that this online procedure lowers the actual ratio-cut below the spectral relaxation on MNIST, Fashion-MNIST, and CIFAR-10, and that with label-based similarities it clusters as accurately as a supervised MLP classifier.","pith_inferences":["Because $L_{rc}$ is a smooth function of $P$, it could serve directly as a training signal for the representation encoder itself, turning clustering and representation learning into a single end-to-end objective rather than a two-stage pipeline.","The unbiased-gradient issue is generic: any objective containing $1/E[Z]$ inherits bias from moving-average denominators, so a proof technique here would transfer to normalized-cut and other size-normalized graph objectives.","In the balanced-cluster offline setting, the Hessian of $L_{rc}$ is proportional to $-W$, so a Sinkhorn-Knopp-type projection could yield a deterministic offline mode without spectral decomposition, which the authors only mention as future work."],"forward_implications":["PRCut removes the eigendecomposition bottleneck: the entire training loop only needs batches of size $b$ and $O(b^2)$ memory, while still optimizing a ratio-cut objective.","With true-label similarities, PRCut's clustering accuracy tracks the supervised classifier on MNIST (0.987 vs 0.980), Fashion-MNIST (0.887 vs 0.885), and CIFAR-10 (0.571 vs 0.582), showing high fidelity between clustering and the similarity measure.","As a drop-in clustering module for self-supervised representations, PRCut evaluates representation quality and beats spectral clustering on all three datasets, and reaches the best reported Fashion-MNIST clustering among the compared deep methods (0.791 ACC).","Minimizing $L_{rc}$ directly targets the global ratio-cut rather than pairwise-only contrastive objectives, so the clusters reflect global similarity structure rather than local neighborhoods.","The surrogate objective can be computed for sparse $k$-NN graphs at $O((m/n) k b^2)$ per batch, making deep ratio-cut optimization practical for large graphs."],"supporting_citations":[{"why":"Defines the ratio-cut objective that the paper optimizes in probabilistic form.","marker":"(Hagen & Kahng, 1991)"},{"why":"Supplies the spectral clustering background and the Rayleigh-quotient relaxation used as the comparison point.","marker":"(von Luxburg, 2007)"},{"why":"Gives the k-means-on-Laplacian-eigenvectors spectral clustering algorithm that serves as the principal baseline.","marker":"(Ng et al., 2001)"},{"why":"SpectralNets, the parametric spectral network whose stability issues motivate the new probabilistic relaxation.","marker":"(Shaham et al., 2018)"},{"why":"Spin, the online spectral inference baseline that PRCut's stochastic optimization is designed to outperform.","marker":"(Pfau et al., 2020)"},{"why":"Introduces the equal-occupancy polytope that inspires the KL regularization against cluster collapse.","marker":"(Benamou et al., 2014)"},{"why":"Provides the DINOv2 self-supervised representations used in the representation-quality experiments.","marker":"(Oquab et al., 2024)"},{"why":"Provides the CLIP representations used in the representation-space experiments.","marker":"(Radford et al., 2021)"},{"why":"Turtle, the deep clustering baseline that PRCut matches or exceeds on Fashion-MNIST and CIFAR-10.","marker":"(Gadetsky et al., 2024)"}],"fun_headline_variants":["Random-variable assignments make ratio-cut trainable by backprop","PRCut: smooth probabilistic ratio-cut outperforms spectral relaxation","Online optimization of expected ratio-cut for deep clustering","Clustering via probabilistic ratio-cut equals supervised accuracy on labels"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The central premise is that the moving-average stop-gradient rule yields an unbiased gradient of the surrogate $L_{rc}$, and that minimizing $L_{rc}$ also lowers the true expected ratio-cut; the paper asserts both without proof, and the first is generally false because $1/E[Z]$ is not $E[1/Z]$.","fun_headline_variants_meta":{"raw":{"variants":["Random-variable assignments make ratio-cut trainable by backprop","PRCut: smooth probabilistic ratio-cut outperforms spectral relaxation","Online optimization of expected ratio-cut for deep clustering","Clustering via probabilistic ratio-cut equals supervised accuracy on labels"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000544,"raw_usage":{"total_tokens":2542,"prompt_tokens":824,"completion_tokens":1718,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":440,"completion_tokens_details":{"reasoning_tokens":1652}},"tokens_in":440,"tokens_out":1718,"duration_ms":12817,"temperature":1.0,"reasoning_tokens":1652,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T04:51:33.465884+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a graph small enough to enumerate every cluster assignment (say $n = 12$), compute the exact expected ratio-cut, run PRCut's moving-average stop-gradient update for a step, and compare the direction it moves to the exact gradient of the true expectation; a mismatch on any instance would refute the unbiased-gradient claim.","supporting_citations":[{"cited_title":"Spectralnet: Spectral clustering using deep neural networks","cited_arxiv_id":null,"evidence_quote":"SpectralNets, the parametric spectral network whose stability issues motivate the new probabilistic relaxation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Spin, the online spectral inference baseline that PRCut's stochastic optimization is designed to outperform."},{"cited_title":"Iterative bregman projections for regularized transportation problems, 2014","cited_arxiv_id":null,"evidence_quote":"Introduces the equal-occupancy polytope that inspires the KL regularization against cluster collapse."},{"cited_title":"Let go of your labels with unsupervised transfer, 2024","cited_arxiv_id":null,"evidence_quote":"Turtle, the deep clustering baseline that PRCut matches or exceeds on Fashion-MNIST and CIFAR-10."}],"review_version":1}