{"id":"57fcef10-32be-4d73-8f38-aa404797a6dc","arxiv_id":"2412.04082","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A symmetric nonnegative matrix factorization variant that learns weights over nearest-neighbor slices for similarity and dissimilarity, plus a column-wise orthogonality regularizer, improves clustering on eight benchmarks.","lead":"This paper proposes a clustering method that learns how much to trust each level of a nearest-neighbor graph, instead of picking one fixed neighbor count. It also adds a new orthogonality penalty to make clusters more distinct, and reports gains over nine baselines on eight datasets.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The column-wise orthogonality regularizer R(V) is not a well-defined global objective, so the claimed KKT guarantee for (22) is not established.","rationale":"Read in good faith, the paper proposes a plausible clustering objective and a practical alternating algorithm, with released code and extensive empirical comparisons. The strongest claim, however, is theoretical: the variables converge to a stationary point that satisfies the KKT conditions of problem (22). For that claim to hold, (22) must be a well-defined optimization problem and the alternating updates must be coordinate-wise minimizations of that same objective. The R(V) term fails both conditions: it is never defined globally, and the per-column update (33) omits the dependence of other regularization terms on the currently updated column. The proof of Theorem 2 depends on Lemma 1 from the PHALS paper [29], which applies to standard SymNMF but does not account for the coupling created by this particular regularization, and on the unproven condition w*^T p*=0 in Section IV-B. The reader's weakest assumption correctly identifies the latter gap; I agree that the w^T p condition is unsupported and needs proof. But the R(V) issue is more fundamental because it invalidates the stationarity claim for the V-block itself, independent of the (w,p) relaxation. The empirical results and the reproducible code are real evidence that the method may work in practice, but the theoretical contribution as stated is not supported. A major revision could repair this by defining R(V) as an explicit global function and deriving the true KKT conditions, or by recasting the algorithm as optimizing a well-defined surrogate and proving convergence for that surrogate. In the current form, the central claim is unsubstantiated, so the verdict should move from CONDITIONAL to REJECT.","tokens_in":22725,"tokens_out":14995,"duration_ms":143338,"concrete_test":"Independently define R(V)=Σ_j v_j^T(I - V_{-j}V_{-j}^†)v_j and analytically compute the gradient of the full objective (22) w.r.t. v_j. Check whether the KKT conditions (47) equal the full-gradient stationarity. Concretely: run Algorithm 1 on SEEDS (or a small r=2 synthetic dataset) and, at the final iterate, compute the full gradient by automatic differentiation and compare the KKT residual of (47) with the projected full-gradient norm. If the full-gradient norm is not near zero while (47) holds, the algorithm has converged to a stationary point of the surrogate, not of (22).","verdict_should_be":"REJECT","load_bearing_attack":"The most load-bearing gap is the orthogonality regularizer. Model (22) is written with a global -αR(V), but Section III-C and Remark 1 define only per-column R(v_j)=v_j^T(I - V_{-j}V_{-j}^†)v_j and state that R(V) cannot be explicitly expressed as a function of V. If R(V) is taken to be Σ_j R(v_j), then the column subproblem (33) is not the restriction of (22) to v_j: the terms R(v_i) for i≠j depend on v_j through V_{-i}^†, so the PHALS update does not monotonically decrease the true objective. The KKT conditions (47) are derived for the surrogate (34), not for (22). Lemma 1 is invoked from [29] for standard SymNMF and does not cover the coupling introduced by the regularization. Hence Theorem 2's claim that the variables converge to a KKT point of (22) is unsupported even before considering the unproven w*^T p*=0 condition in Section IV-B. If R(V) is instead not meant to be a single function, then (22) is not a well-posed optimization problem and Theorem 1's monotone-decrease statement is vacuous. This is a structural issue with the central theoretical claim, not merely a missing proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a SymNMF-based clustering model in which the similarity matrix is a weighted sum of k-NN slices, S(w)=Σ_k w_k A(k), with learnable nonnegative weights w summing to one, and a dual dissimilarity matrix D(p) built from the same slices with weights p. The model also includes a new column-wise orthogonality regularizer R(v_j)=v_j^T(I - V_{-j}V_{-j}^†)v_j, which the authors argue is more stable than log-det regularization. An alternating algorithm (Algorithm 1) is proposed: V is updated column-wise by a rank-one PHALS step, and (w,p) is updated by solving a strongly convex relaxation of the simplex-constrained problem. The paper claims that the variables converge to a KKT point of the constrained model (22) (Theorem 2) and reports state-of-the-art clustering ACC/NMI on 13 of 16 benchmark comparisons, with code released.","tokens_in":23016,"tokens_out":5962,"duration_ms":60082,"significance":"If the theoretical claims were correct, the paper would make a useful contribution: reparameterizing similarity learning in an n-1 dimensional space is an elegant way to reduce the search complexity relative to O(n^2) adaptive graph methods, and the column-wise orthogonality regularizer has a clear geometric interpretation and is potentially more practical than log-det variants. The experimental study is reasonably broad (eight datasets, nine baselines) and the ablations show consistent gains from the dissimilarity term and the orthogonality regularizer. The release of code and the reproducibility-oriented experimental description are strengths. However, the convergence and KKT guarantees -- a central advertised selling point -- are not rigorously established as written, and one of the two equivalence steps (Proposition 2) relies on an unproven empirical condition. The practical method may still be sound, but the paper's main theoretical contribution needs substantial repair.","major_comments":[{"comment":"The regularizer R(V) is never defined as a global function of V. Remark 1 states that R(V) cannot be explicitly expressed as a function of V, and the subproblem (33) only contains R(v_j) with V_{-j} fixed. If one interprets R(V) as Σ_j R(v_j), then the column subproblem (33) is not the restriction of (22)/(32) to v_j, because the terms R(v_i) for i≠j depend on v_j through V_{-i} (and specifically through the projection V_{-i}V_{-i}^†). Lemma 1 is cited from [29] for the standard SymNMF objective, where no such coupling is present, so it does not imply monotone decrease of the full objective (22). Thus Theorem 1's claim that the objective of (22) decreases monotonically, and Theorem 2's claim that the iterates converge to a KKT point of (22), are unsupported. The authors need to either define a proper global regularizer and prove descent for it, or explicitly state that the convergence guarantee applies only to the surrogate column-wise problem (34) and analyze the discrepancy.","section":"Section III-C, Remark 1; Eqs. (32)-(34); Theorems 1-2"},{"comment":"The algorithm solves the relaxed problem (37), and Proposition 2 states that its global optimum (w*, p*) is also a global optimum of the constrained problem (36) only under condition (38), namely Σ_k w*_k p*_k = 0. The authors write that this condition 'almost always holds' and that 'the reason for which needs further study', which is not a proof. Section V-C provides only a post-hoc empirical observation that the learned w and p appear to have disjoint supports. If (38) fails, the algorithm solves a penalized surrogate, not the constrained model, and the KKT claim for (w,p) in Theorem 2 is not justified. The paper should either prove (38) under explicit assumptions or replace the KKT statement with a convergence result for the penalized problem (37).","section":"Section IV-B, Proposition 2; Section V-C"},{"comment":"The KKT conditions (47) are derived for the rank-one surrogate (34), not for the coupled objective (22). The proof that the PHALS update drives a stationarity gap to zero (Eq. (50)) is a restatement of the convergence result for the surrogate; it does not establish joint stationarity of (V, w, p) for the original constrained problem (22), because the V-update is not an exact minimization of (22) (the column subproblem ignores the couplings in R(V)), and the (w,p)-update solves a relaxed problem. A standard block-coordinate-descent KKT argument requires exact or sufficiently faithful subproblem solutions for the same objective, and that condition is not verified here. Consequently, the strong claim in the abstract and Theorem 2 is not supported by the presented analysis.","section":"Section IV-C, Theorem 2 proof; Eq. (47)-(50)"}],"minor_comments":[{"comment":"Several entries in Tables II and III appear garbled, with values repeated or concatenated (e.g., the RBSMF and S3NMF rows). Please ensure the final version renders each cell exactly once with the correct values, since the current formatting makes it difficult to verify the reported '13/16 best' claim.","section":"Table II and Table III"},{"comment":"The per-iteration complexity statement is inconsistent: line 8 computes V_{-j}^† by reduced SVD for each j in O(n(r-1)^2), which summed over j gives O(n r^3), not O(n r^2) as claimed in the summary 'O(n^2 r + n r^2)'. The complexity analysis should be corrected or the SVD computed more efficiently.","section":"Section IV-D, computational complexity"},{"comment":"The equivalence between (22)'s V-subproblem and (24) holds only up to additive constants independent of V (specifically the term -β<S,D> + (β^2/2)||D||^2). Please state this explicitly to avoid confusion.","section":"Eq. (24)"},{"comment":"The hyper-parameter tuning protocol is not fully specified: it is not stated whether the 'best' hyper-parameters were selected on a validation set or on the test data, and whether the reported metrics are from the same runs used for selection. Clarifying this would strengthen the reproducibility of the comparisons.","section":"Section V-A"},{"comment":"The paper introduces D as a 'k-farthest neighbor graph' (Section I) but then defines D(p) using the same nearest-neighbor slices A(k) in Eq. (20). Since A(k) are ordered by nearest-neighbor rank, the term 'farthest' is confusing; consider clarifying that the dissimilarity weights p are learned over the same slices, with larger k acting as far-neighbor relations.","section":"Section I and III-A"}],"recommendation":"major_revision","confidential_remarks":"The paper has a solid empirical core and the low-dimensional reparameterization idea is attractive, but the theoretical guarantees are overstated. The R(V) definition problem and the unproven condition in Proposition 2 are structural, not cosmetic, and they affect the main convergence claim. I recommend major revision rather than rejection because the issues are potentially fixable: the authors could redefine the regularizer to make the objective well-posed, provide a valid block-coordinate descent proof, or temper the claims to a surrogate objective without losing the practical contribution. The experimental tables also need careful cleanup before the paper can be accepted."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the method is worth knowing about, but the main theoretical claim needs to be retracted or rewritten. The weighted k-NN slice idea is neat: instead of learning an n×n similarity matrix, you learn n weights on fixed slices, cutting the search space to n−1 and giving a clean story about why later slices are less reliable. The dissimilarity dual is natural, and the experiments are extensive—eight datasets, nine baselines, ablations, and released code. The reported gains are consistent, so the empirical side deserves credit.\n\nWhere it falls apart is the theory. Model (22) has a term -αR(V), but the paper never defines R(V) as a function of V. Remark 1 says explicitly that it cannot be expressed as a function of V; you only get R(v_j) with V_{-j} fixed. If you take R(V) to be Σ_j R(v_j), then updating v_j changes R(v_i) for i≠j through V_{-j}†, so the column subproblem (33) is not a restriction of (22). The PHALS monotonicity from Lemma 1 applies to the surrogate, not to the original objective, and the KKT conditions in (47) are for the column-wise surrogate too. Thus Theorem 2's claim that the variables converge to a KKT point of (22) is unsupported. Theorem 1's monotone decrease has the same problem. This is not a minor missing proof; it is a structural gap in the central theoretical claim.\n\nA second, softer issue is Proposition 2's bridge from the relaxed (37) to the constrained (36). It only works if w*^T p* = 0, which the authors say \"almost always holds\" without proof. Their experiments (Fig. 4) do show zero overlap, so empirically it works, but the guarantee is not established.\n\nMinor: the performance comparisons lack significance tests, so the \"best in 13/16 cases\" claim is weaker than it looks.\n\nI would not cite the convergence theorem. I would cite the method and the empirical results, since those are concrete and reproducible. A serious referee should engage with the paper, but the authors should be asked to either prove monotonicity and KKT claims for a well-defined global objective, or downgrade the theory to a weaker statement about the column-wise surrogate.","headline":"The empirical recipe is solid and reproducible, but the paper's headline convergence guarantee does not hold as written because R(V) is never defined as a global objective.","tokens_in":23510,"tokens_out":3192,"would_cite":true,"duration_ms":33918,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that symmetric nonnegative matrix factorization can be made robust to unreliable large-k nearest-neighbor graphs by learning one weight per neighbor slice for a similarity graph and a second weight vector for a dual…","keywords":["symmetric nonnegative matrix factorization","adaptive similarity learning","weighted k-nearest-neighbor graph","dissimilarity learning","orthogonality regularization","clustering","KKT stationarity"],"falsifier":"Run Algorithm 1 with η=0.99μ on a dataset where later neighbor slices are not predominantly wrong-class (e.g., periodic or interleaved clusters), and measure Σ_k w*_k p*_k after convergence; a clearly positive value, together with a nonzero KKT residual for (22), would refute the claimed stationarity of the original model.","tokens_in":22510,"feed_emoji":"📊","tokens_out":11205,"duration_ms":100876,"temperature":0.7,"pith_summary":"The paper argues that the standard fixed k-nearest-neighbor similarity matrix in symmetric nonnegative matrix factorization (SymNMF) is both wasteful and unreliable, since later neighbor slices are mostly noise. It replaces that fixed matrix with a weighted sum of the k-th neighbor slices, learning one nonnegative weight per slice; this collapses the graph search space from O($n^{2}$) entries to n-1 weights. A second learned weight vector builds a dual dissimilarity graph from the same slices, telling the factorization which pairs are actively dissimilar rather than merely unobserved, and a new orthogonality regularizer keeps the cluster-indicator columns well separated. The paper claims an alternating algorithm with monotone convergence to a KKT point and reports the best ACC/NMI on 13 of 16 benchmark comparisons against nine clustering methods.","feed_headline":"Weighted k-NN similarity wins 13 of 16 clustering benchmarks","feed_subtitle":"Symmetric NMF learns n-1 weights for similarity and a dual dissimilarity graph, avoiding quadratic search.","key_machinery":"The load-bearing object is the k-th-nearest-neighbor slice matrix A(k), with unit Frobenius norm after normalization and disjoint support from every other slice, so ⟨A(k), A(t)⟩=0 and S(w), D(p) decompose into sums of weights. That orthogonality turns the whole graph-learning task into a low-dimensional simplex problem: updating w and p is a strongly convex quadratic with simplex constraints, solved by O(n log n) projection, and the density penalties ∥w∥^2, ∥p∥^2 come directly from ∥S(w)∥^2_F=Σ $w_k^{2}$. On the factor side, the argument runs through the identity det(V^T V)=det(V_{-j}^T V_{-j}) v_j^T(I-V_{-j}V_{-j}^†)v_j, which supplies the regularizer R(v_j), the geometric reading of R(v_j) as the squared distance from column v_j to the span of the other columns, the bound 0≤R(v_j)≤∥v_j∥^2, and a column-wise update that fits the progressive hierarchical alternating least-squares (PHALS) scheme with monotone decrease and KKT convergence. Proposition 2 is the bridge between the relaxed (w,p) problem and the original nonconvex constraint w^T p=0: the relaxed global optimum is also optimal for the constrained problem whenever Σ_k w_k p_k=0, a condition the authors observe to hold in their experiments but state needs further study.","core_discovery":"The paper's core assertion is that the k-th-nearest-neighbor slices A(k) of a kernel matrix are normalized, mutually orthogonal building blocks, so a weighted combination S(w) = Σ_k w_k A(k) spans every useful similarity graph in only n-1 dimensions. Learning those weights instead of every entry of S makes adaptive similarity practical, and the learned weights concentrate on early slices whose neighbor relations agree with true clusters. The same slices with a second weight vector p build a dual dissimilarity graph D(p), with w^T p=0 forcing every slice to serve exactly one role; a large entry of D(p) tells the factor matrix VV^T that a pair is dissimilar rather than merely unobserved. For discrimination, the paper introduces the column-wise orthogonality regularizer R(v_j)=v_j^T(I-V_{-j}V_{-j}^†)v_j, the squared length of the component of v_j orthogonal to the space spanned by the other columns, which follows from det(V^T V)=det(V_{-j}^T V_{-j})R(v_j), is bounded, and cannot vanish even when a column is driven to zero. With alternating updates — rank-one SymNMF steps for each column of V and simplex projections for w and p — the paper claims every variable reaches a stationary point satisfying the KKT conditions of the relaxed model, and empirically the method records the best ACC/NMI on 13 of 16 comparisons.","pith_inferences":["If the slice decomposition carries the same benefit outside SymNMF, the weighted k-NN parameterization could replace full similarity-matrix learning in spectral clustering or graph-based semi-supervised learning, inheriting the same n-1 dimensional search space.","The paper's own open condition — Σ_k w*_k p*_k = 0 almost always holds — invites a stress test: datasets with non-monotone neighbor reliability curves (e.g., periodic cluster layouts) are exactly where the relaxation and the original model may diverge, and plotting the overlap across such datasets would show how much the unproven condition matters.","A direct check of the surrogate gap (compare the objective of the original problem (36) at the relaxed solution against a locally optimized feasible solution of (36)) would quantify how much the relaxation changes the model, something the paper does not report."],"forward_implications":["The search for an adaptive similarity matrix in clustering drops from O(n^2) free entries to n-1 learned weights, so adaptive graph learning becomes feasible at larger sample sizes.","The learned coefficient vector w automatically assigns high weight to reliable early neighbor slices and near-zero weight to unreliable later ones, which removes the need to hand-tune the k in k-NN for the similarity graph; p learns the opposite pattern for the dissimilarity graph.","Because each column update of V is a rank-one SymNMF step with a monotone objective and the (w,p) updates are global optima of a strongly convex problem, the whole algorithm has a convergence guarantee and an O(n^2 r + n r^2 + n log n) per-iteration cost.","The orthogonality regularizer R(v_j) is bounded and cannot collapse a column to zero, avoiding the all-zero-cluster failure mode of off-diagonal orthogonality penalties while retaining a geometric meaning as squared distance to the other columns' span."],"supporting_citations":[{"why":"Defines the SymNMF objective and k-NN graph baseline that the paper generalizes with weighted slices.","marker":"[7]"},{"why":"Supplies the self-tuning kernel κ used to build every k-th neighbor slice A(k).","marker":"[12]"},{"why":"Provides the log2(n)+1 heuristic for k that the paper uses for initialization and for baselines.","marker":"[13]"},{"why":"Defines the off-diagonal orthogonality regularizer that the proposed R(V) is compared against in the ablation study.","marker":"[27]"},{"why":"Introduces the log-determinant orthogonality regularization and the volume interpretation that Proposition 1 adapts into a column-wise form.","marker":"[28]"},{"why":"Supplies the rank-one SymNMF update with monotone decrease and KKT convergence that Theorem 1 and Theorem 2 rely on.","marker":"[29]"},{"why":"Provides the O(n log n) simplex projection solving the w and p subproblems in each inner iteration.","marker":"[33]"}],"fun_headline_variants":["Learnable k-NN weights cut similarity search to n-1 dims","Symmetric NMF with dual graphs wins 13 of 16 clustering tests","SymNMF learns weights for k-NN slices, not full matrix","Orthogonality regularized SymNMF learns both similarity and dissimilarity","Dual dissimilarity graph guides SymNMF to 13 benchmark wins"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the relaxed weight problem (37) returns a pair (w*,p*) with Σ_k w*_k p*_k = 0, which the paper asserts \"almost always holds\" without proof, because if it fails the algorithm has solved a penalized surrogate and the claimed KKT stationarity for the original model (22) does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Learnable k-NN weights cut similarity search to n-1 dims","Symmetric NMF with dual graphs wins 13 of 16 clustering tests","SymNMF learns weights for k-NN slices, not full matrix","Orthogonality regularized SymNMF learns both similarity and dissimilarity","Dual dissimilarity graph guides SymNMF to 13 benchmark wins"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000992,"raw_usage":{"total_tokens":4276,"prompt_tokens":1087,"completion_tokens":3189,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":703,"completion_tokens_details":{"reasoning_tokens":3091}},"tokens_in":703,"tokens_out":3189,"duration_ms":22548,"temperature":1.0,"reasoning_tokens":3091,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T21:46:40.566642+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Algorithm 1 with η=0.99μ on a dataset where later neighbor slices are not predominantly wrong-class (e.g., periodic or interleaved clusters), and measure Σ_k w*_k p*_k after convergence; a clearly positive value, together with a nonzero KKT residual for (22), would refute the claimed stationarity of the original model.","supporting_citations":[{"cited_title":"Symnmf: nonnegative low-rank approximation of a similarity matrix for graph clustering,","cited_arxiv_id":null,"evidence_quote":"Defines the SymNMF objective and k-NN graph baseline that the paper generalizes with weighted slices."},{"cited_title":"Self-tuning spectral clustering,","cited_arxiv_id":null,"evidence_quote":"Supplies the self-tuning kernel κ used to build every k-th neighbor slice A(k)."},{"cited_title":"Two efficient algorithms for ap- proximately orthogonal nonnegative matrix factorization,","cited_arxiv_id":null,"evidence_quote":"Defines the off-diagonal orthogonality regularizer that the proposed R(V) is compared against in the ablation study."},{"cited_title":"Large-cone nonnegative matrix factor- ization,","cited_arxiv_id":null,"evidence_quote":"Introduces the log-determinant orthogonality regularization and the volume interpretation that Proposition 1 adapts into a column-wise form."},{"cited_title":"A progressive hierarchical alternating least squares method for symmetric nonnegative matrix factorization,","cited_arxiv_id":null,"evidence_quote":"Supplies the rank-one SymNMF update with monotone decrease and KKT convergence that Theorem 1 and Theorem 2 rely on."}],"review_version":1}