{"id":"67f0874b-b697-416d-b3b4-b61024b6f1e4","arxiv_id":"1908.10506","paper_version":1,"verdict":"REJECT","confidence":"HIGH","novelty_score":4.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"The authors propose the rpf-kernel, defined as the co-occurrence probability in a random projection forest, and use it for spectral clustering with mixed empirical gains over baselines.","lead":"This paper builds a similarity score between data points by counting how often they end up in the same leaf of a forest of random projection trees. The score is then used for clustering, and the paper claims a theoretical guarantee that similar points get high scores while distant points get low scores.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The low-similarity bound is not established: Theorem 3.1 treats a 2-D angular density in any dimension, and Eq. (2) applies it to a final node that need not contain both points.","rationale":"Read in good faith, the paper proposes a simple unsupervised kernel from random projection forests, notes it is PSD, and reports competitive clustering. The load-bearing part of the advertised contribution is the theorem that far-away points get low similarity. That theorem is not proved as written. The angular-density error is concrete and easily checked; the final-node conditioning gap is the one the reader identified. Either alone would prevent Eq. (2) from justifying the binomial bound in Eqs. (4) and (5). I do not claim the method is useless or that the property is false; a corrected proof may exist via a martingale or survival argument. But the paper as written has a high correctness risk on its central claim. The experimental section is plausible but also has unquantified parameter selection, so I do not see a reason to soften the reader's REJECT. Keeping the verdict at REJECT, not CONDITIONAL, because the advertised theoretical guarantee is a main contribution and the submitted proof does not support it.","tokens_in":15102,"tokens_out":5972,"duration_ms":66241,"concrete_test":"Monte Carlo test of Theorem 3.1: fix p=100, two points A,B with d=1, and a bounding set with principal stretch ρ. Sample N=10^5 isotropic random directions u, and for each compute the empirical probability that a uniform split point on [min_i u·x_i, max_i u·x_i] falls between u·A and u·B. Compare the estimate with 2d/(πρ). The simulated value will be about √(2/(πp))·(d/ρ), an order of magnitude below the claimed bound; repeating the same check for p=2 will recover 2/π. This directly falsifies the one-split lemma on which Eq. (2) relies.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim needs P(A,B separated in a tree) to be close to 1 for far-away points, so that rpf-kernel similarity is low. Two gaps in the proof destroy Eq. (2).\n\nFirst, Theorem 3.1 integrates θ, the angle between the random projection and AB, as if θ had density 2/π on [0,π/2]. That is correct only when the data dimension p=2. For an isotropic random projection direction in R^p, the density of the acute angle is c_p sin^{p-2}θ, so E|cosθ| = c_p/(p-1), which decays like 1/√p. Hence P(separated in one split) = (d/L)E|cosθ| is not bounded below by 2d/(πρ(Ω)) for p>2; for p=500 (Madelon) the claimed constant is off by a factor of about √p.\n\nSecond, Eq. (2) applies Theorem 3.1 to N_t^(J_t), a 'final node' in a sequence of nodes. If A and B were separated at an earlier split, no common final node exists; if N_t^(J_t) is defined only when they remain together, then the event 'separated when splitting N_t^(J_t)' is conditioned on survival to that node, and the unconditional probability is not what Theorem 3.1 bounds. The inequality P(union)≥P(last event) is true formally, but it does not give the stated lower bound unless the last-event probability is taken unconditionally with N_t^(J_t) guaranteed to contain both points.\n\nThus the proof that µ is close to 1 for far-away points, and hence the high-probability low-similarity claim, is unsupported. The kernel's PSD property and the empirical comparisons are not affected, but the central theoretical contribution is not established.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an unsupervised similarity kernel, rpf-kernel, obtained by averaging, over trees in a random projection forest, the indicator that two points fall in the same leaf. The kernel is claimed to have a desirable property: far-away points receive low similarity and nearby points receive high similarity, with similarity interpretable as the co-occurrence probability in tree leaves. The authors prove that the averaged matrix is positive semidefinite, then define rpfCluster by thresholding and exponentiating the kernel and applying spectral clustering. Experiments on 12 labeled real datasets compare rpfCluster with K-means, NJW spectral clustering, and Cluster Forests on clustering accuracy and co-cluster accuracy.","tokens_in":15517,"tokens_out":9436,"duration_ms":94948,"significance":"If the theoretical claim were established, the paper would contribute a simple, data-adaptive, unsupervised kernel with a clear probabilistic interpretation and a competitive clustering algorithm. The PSD argument in Section 2.2 is elementary and correct, and the co-occurrence interpretation follows immediately from Algorithm 2. However, the central theoretical result — that far-away points have low similarity with high probability — rests on Theorem 3.1 and Eq. (2), which contain load-bearing gaps: the angle distribution in Theorem 3.1 is only valid in two dimensions, and Eq. (2) ignores the conditioning implicit in the existence of a final common node. The empirical comparison, while broad, reports no variance and leaves the hyperparameter selection criterion unspecified. The main contribution is therefore not currently supported.","major_comments":[{"comment":"The proof uses the density 2/π for the angle θ between the random projection direction and AB, which is correct only when the data lie in R^2. For an isotropic random projection direction in R^p, the acute angle has density proportional to sin^{p-2}(θ), so E|cos θ| is roughly c/√p in high dimensions, not 2/π. Consequently the stated lower bound P(A and B separated by a random projection) ≥ 2d/(πρ(Ω)) does not hold for p > 2. Since Eq. (2) and the subsequent claim that µ is close to 1 for far-away points inherit this constant, the far-away low-similarity theorem is not established for the high-dimensional datasets used in Section 5, e.g., Madelon with p=500 in Table 1.","section":"Section 3, Theorem 3.1"},{"comment":"The inequality P(A,B separated in tree t) ≥ P(A,B separated when splitting node N_t^(J_t)) is applied as though N_t^(J_t) always contains both A and B. If the two points are separated at an earlier split, no such common final node exists; if N_t^(J_t) is defined only on the event that they remain together, then Theorem 3.1 bounds a conditional probability, and the unconditional probability of the final-node event is not bounded below by 2d/(πρ(N_t^(J_t))). The proof omits the probability of surviving to the final node, so the lower bound in Eq. (2) is not demonstrated. In fact, for sufficiently large J1 the right-hand side of Eq. (2) can exceed 1, which is impossible for a probability and signals that the marginalization is incorrect.","section":"Section 3, Eq. (2)"},{"comment":"The argument establishes, for a fixed pair (A,B), that the similarity is below δ with high probability as T grows. The paper then concludes that the rpf-kernel has the property that far-away points have low similarity. No union bound over the O(n^2) pairs in the data is provided, and the per-pair success probability is not quantified. Without such a bound, the global claim about the kernel matrix is not supported.","section":"Section 3, Eqs. (4)-(5)"},{"comment":"Figures 4 and 5 report only point estimates for each method, despite rpForests, K-means, and CF being randomized. No error bars, standard deviations, or repeated-run results are given, so the statement that rpfCluster 'outperforms' CF and NJW is not supported at the reported precision. In addition, the selection of β1 and β2 is described only by search ranges; the paper does not state whether the true labels were used to pick these parameters. If labels are used for tuning, the comparison is not an unsupervised clustering comparison, and if they are not, the selection rule should be specified.","section":"Section 5.2.2 and 5.2.3"}],"minor_comments":[{"comment":"The stopping threshold is written as both n_s and ns; please use one consistent symbol and state the stopping rule as 'stop splitting when the node size is less than ns'.","section":"Section 2.1, Algorithm 1"},{"comment":"The parameters J1, J2, γ1, γ2 are introduced informally; the assumptions about the number of splits and the uniform shrinkage of the principal stretch of child nodes should be stated as precise conditions under which the bounds hold.","section":"Section 3, Eq. (3)"},{"comment":"The description of the β2 search ('step size 0.01 within (0,1], 0.1 over (1,200]') should clarify whether the same grid is applied to every dataset and how a single value is selected from the grid.","section":"Section 5.2.2"},{"comment":"The heatmap comparison would be clearer with colorbars and a statement of how the Gaussian-kernel bandwidth was chosen for the left panel.","section":"Figure 3"},{"comment":"There are a number of typos and scanned ligature artifacts, e.g., 'eff' and 'fl' in the text and 'knowlwdge' in reference [64]; the manuscript should be proofread before a revised submission.","section":"References"}],"recommendation":"reject","confidential_remarks":"I agree with the reader's assessment. The two gaps identified in the theoretical argument are not local typographical issues: Theorem 3.1 requires a dimension-dependent constant, and Eq. (2) requires a new probabilistic treatment of survival along the tree path. Together they invalidate the main claimed property, and the empirical evaluation does not compensate because it lacks variance estimates and a clear tuning protocol."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First thing you should know: the rpf-kernel is a tree co-occurrence matrix, and the paper's central theorem—far-away points get low similarity—is not proven. The two gaps the stress-test found are real. Theorem 3.1 assumes the angle between the random projection and AB is uniform on [0, π/2], which is only true in R^2; in R^p, E|cosθ| ~ 1/√p, so the constant 2/(πρ(Ω)) is wrong for p>2 and off by a factor of √p on Madelon. And Eq. (2) applies that bound to a 'final node' N_t^(J_t) without handling the case where A and B are separated before that node; if the node is defined only when they are still together, the bound is conditional and does not give the claimed marginal lower bound. So the high-probability low-similarity claim rests on an invalid argument.\n\nWhat is genuinely new here is using random projection forests rather than coordinate-aligned trees or random-feature k-means ensembles to define a similarity kernel and then applying spectral clustering. That specific construction is not in the cited Cluster Forests or unsupervised RF literature. The PSD proof is correct, and the kernel's interpretation as a co-occurrence probability is true by construction. The empirical section is substantial—12 real datasets, two metrics, comparisons to K-means, NJW, and Cluster Forests—and rpfCluster is competitive, leading on 7 of 12 datasets for clustering accuracy. The method is simple and plausible.\n\nThe soft spots beyond the theorem: no error bars or variance estimates, and the tuning of β1 and β2 is not described as label-free; with labeled datasets, this smells like possible label-based parameter selection, which would inflate the results. The gains over Cluster Forests are modest and mixed across metrics. Also, the 'far-away' vs 'nearby' distinction is left informal; the bounds depend on application-dependent constants without a precise statement of when the separation probability becomes high.\n\nWho is this for? Someone working on unsupervised kernel learning or clustering ensembles might find the empirical recipe useful, but the theoretical promise in the abstract overstates what is actually shown. If you send it to peer review, the referees should focus on Theorem 3.1 and Eq. (2); those need fixing, or the claims need to be downgraded to empirical observations. My recommendation: it deserves a serious referee because the empirical work is real and the construction is plausible, but as it stands the paper should not be accepted without major revision.","headline":"The rpf-kernel is a tree co-occurrence matrix with a plausible empirical record, but the paper's central theorem that far-away points get low similarity is not proven—two real gaps in Theorem 3.1 and Eq. (2).","tokens_in":16004,"tokens_out":2501,"would_cite":false,"duration_ms":25910,"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":"The paper proposes rpf-kernel, a similarity kernel learned by random projection forests, and claims it assigns high similarity to nearby points and low similarity to far-away points, while the associated rpfCluster algorithm competes with…","keywords":["similarity kernel","random projection forests","unsupervised learning","clustering","spectral clustering","kernel methods","co-membership probability","random projection trees"],"falsifier":"Grow many forests on a fixed dataset with two chosen far-apart points, record every split along their paths, and compare the observed fraction of trees that separate them with the claimed lower bound based on the final enclosing node; an observed fraction below the bound would disprove the proof's key step.","tokens_in":14928,"feed_emoji":"🌲","tokens_out":11117,"duration_ms":99175,"temperature":0.7,"pith_summary":"Random projection forests are ensembles of trees that split data along randomly chosen directions. This paper proposes using them to learn a similarity kernel without labels: grow the forest, record how often each pair of points falls into the same leaf, and average over trees. The paper's central claim is that the resulting rpf-kernel has the desired ordering property—nearby points receive high similarity, far-away points low similarity—and that each kernel entry is interpretable as the probability that the two points stay together through tree growth. Because the kernel is positive semidefinite, it can feed directly into spectral clustering, yielding the rpfCluster algorithm. On 12 benchmark and real datasets, the paper reports that rpfCluster compares favorably with K-means, spectral clustering, and Cluster Forests, which matters because a label-free kernel that adapts to data geometry could replace hand-chosen kernels in clustering and semi-supervised learning.","feed_headline":"Same-leaf counts make a clustering kernel that separates near from far","feed_subtitle":"Nearby points share leaves, distant points rarely; this label-free kernel edges out three baselines on 12 datasets.","key_machinery":"The machinery is a random projection forest (rpForest): an ensemble of trees in which every node is split by projecting its points onto a random direction and cutting uniformly at random within the range of projected values. The rpf-kernel is the normalized co-leaf matrix produced by Algorithm 2, so $S_{ij}$ equals the fraction of trees in which points $i$ and $j$ land in the same leaf. The load-bearing geometric identity behind the theory is that, for two points $A,B$ at distance $d$, a randomly oriented split separates them with probability $|AB|\\cos\\theta / L$, where $L$ is the projected span of the node and $\\theta$ is the angle between the projection direction and $AB$; bounding $L$ by the principal stretch $\\rho(\\Omega)$—the largest possible spread of the node along any direction—gives the lower bound $2d/(\\pi\\rho)$. The principal stretch and its counterpart, the neck size, are the quantities that control, respectively, the separation of far-away points and the survival of nearby points, and these two opposing bounds are what the paper uses to establish the kernel's ordering property.","core_discovery":"On the paper's own terms, the rpf-kernel is the empirical co-membership matrix of an ensemble of random projection trees. The paper argues that this matrix is a valid kernel because each tree contributes a block-diagonal matrix with all-ones diagonal blocks, each block positive semidefinite, and averaging preserves positive semidefiniteness. The key theoretical claim is that far-away points are very likely to be separated during growth—the probability of separation at a split is at least $2d/(\\pi\\rho)$, with $d$ the distance between points and $\\rho$ the principal stretch of the data—while nearby points remain unseparated with high probability, using the neck-size bound from the rpForests analysis. Consequently, with enough trees and enough splits, the averaged kernel concentrates below any small threshold for dissimilar points and above a high value for similar points. The paper then assembles rpfCluster by thresholding the kernel, exponentiating it with a bandwidth, and running spectral clustering, and reports favorable comparisons to K-means, spectral clustering, and Cluster Forests on the 12 datasets tested.","pith_inferences":["Inference: because the rpf-kernel is nothing more than averaged leaf co-membership, it should be usable as an affinity input for other unsupervised tools such as hierarchical clustering, graph-based visualization, or outlier scoring, without additional training.","Inference: the lower-bound gap in the proof suggests a concrete empirical check: track separation times inside each tree; if pairs are often split before reaching a small final node, the proof's Eq. (2) needs a path-survival conditioning rather than a simple final-node bound.","Inference: the sharp contrast between diagonal and off-diagonal blocks on the Iris example suggests the kernel encodes local geometry rather than global distance; a testable extension is to compare rpf-kernel affinity with a learned Mahalanobis kernel on the same clustering tasks."],"forward_implications":["Because the rpf-kernel is positive semidefinite, it can be used wherever a kernel matrix is needed: spectral clustering, kernel PCA, kernel k-means, or semi-supervised regularization.","The native probabilistic reading of $S_{ij}$ gives practitioners a principled way to set thresholds: similarity values are co-membership chances, not arbitrary affinities.","The forest construction has log-linear cost, so the kernel remains computable for large datasets, and the ensemble structure parallelizes across trees.","If the theoretical property holds, rpfCluster should inherit resistance to the boundary effect: a close pair separated in one tree is likely reunited in another, while truly distant pairs rarely co-occur.","The paper's stated expectation is that the kernel can act as a regularizer in supervised or weakly supervised settings, since it captures latent structure without labels."],"supporting_citations":[{"why":"Supplies the rpForests construction and the nearby-points separation bound that the paper extends to far-away points.","marker":"[75]"},{"why":"Introduces random projection trees and the recursive random-direction splitting used to grow each forest.","marker":"[20]"},{"why":"Defines the ensemble clustering baseline and the threshold-then-spectral post-processing that rpfCluster adapts.","marker":"[70]"},{"why":"Provides normalized cuts, the graph-cut objective solved in the final spectral clustering stage.","marker":"[62]"},{"why":"Provides the NJW spectral clustering algorithm used both as a competitor and as the core of rpfCluster.","marker":"[54]"},{"why":"Establishes the random-projection cluster ensemble lineage against which the paper positions its tree-based iterative projections.","marker":"[26]"}],"fun_headline_variants":["Random projection forests yield a kernel that separates near and far","Tree co-membership yields a kernel that separates near from far","Same-leaf co-occurrence gives a kernel separating near and far","Far points split, near points stay: kernel from random forests","Forest co-membership kernel: far apart splits, near stays"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof that far-away points end up with low similarity rests on assuming that the chance they are separated at the final node on their path in a tree is a lower bound on the chance they are separated somewhere in that tree, even though they may have been separated in an earlier split.","fun_headline_variants_meta":{"raw":{"variants":["Random projection forests yield a kernel that separates near and far","Tree co-membership yields a kernel that separates near from far","Same-leaf co-occurrence gives a kernel separating near and far","Far points split, near points stay: kernel from random forests","Forest co-membership kernel: far apart splits, near stays"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001932,"raw_usage":{"total_tokens":7577,"prompt_tokens":976,"completion_tokens":6601,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":592,"completion_tokens_details":{"reasoning_tokens":6514}},"tokens_in":592,"tokens_out":6601,"duration_ms":46979,"temperature":1.0,"reasoning_tokens":6514,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T10:41:37.507503+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Grow many forests on a fixed dataset with two chosen far-apart points, record every split along their paths, and compare the observed fraction of trees that separate them with the claimed lower bound based on the final enclosing node; an observed fraction below the bound would disprove the proof's key step.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the rpForests construction and the nearby-points separation bound that the paper extends to far-away points."},{"cited_title":"Dasgupta and Y","cited_arxiv_id":null,"evidence_quote":"Introduces random projection trees and the recursive random-direction splitting used to grow each forest."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the ensemble clustering baseline and the threshold-then-spectral post-processing that rpfCluster adapts."},{"cited_title":"Shi and J","cited_arxiv_id":null,"evidence_quote":"Provides normalized cuts, the graph-cut objective solved in the final spectral clustering stage."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the NJW spectral clustering algorithm used both as a competitor and as the core of rpfCluster."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Establishes the random-projection cluster ensemble lineage against which the paper positions its tree-based iterative projections."}],"review_version":1}