{"id":"1c1ce835-cc3b-4af6-9baf-be3ca58980da","arxiv_id":"2608.06860","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"NysHD uses the Nyström method to map any positive-definite kernel into a low-precision hyperdimensional encoding, preserving normalized kernel values and improving HDC accuracy on graph and string benchmarks.","lead":"Hyperdimensional computing (HDC) stores data as high-dimensional random vectors; how raw data is turned into those vectors largely determines accuracy. This paper proposes NysHD, an encoding that uses the Nyström kernel-approximation method to import any user-defined similarity kernel into HDC, improving classification accuracy on graphs and strings by 11% and 17% on average over existing HDC encodings.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 'up to first order' kernel preservation is a Taylor expansion of arccos at r=0, not a global approximation; for high-similarity pairs the expected HDC inner product is far from the normalized kernel, so the equivalence claim is unsupported.","rationale":"I read the paper as trying to (1) give a principled way to convert a user-specified PSD kernel into an HDC-compatible encoding, and (2) show empirically that this encoding beats existing HDC encodings. The most load-bearing piece of (1) is Theorem 1 and the surrounding claim that inner products in HDC space approximate the normalized kernel. Uniform landmark sampling is important but explicitly acknowledged as a limitation, and the empirical results suggest it works on the tested datasets. The omitted kernel-method baseline is a fair empirical critique but does not attack the theoretical construction.\n\nThe first-order Taylor step is more central because it is the exact point where the paper converts a true but nonlinear identity into a kernel-preservation claim. The identity E[phi_i·phi_j] = pi/2 - arccos(r) is correct, but it is not approximately r for large r. The Taylor expansion of arccos at 0 gives pi/2 - arccos(r) = r + r^3/6 + ..., so the error is O(r^3) and becomes large for r close to 1. In graph and string classification, normalized kernel values between similar inputs can easily exceed 0.5, so the claimed 'up to first order' preservation is not a safe justification for the mapping. This does not invalidate the method as a heuristic, nor does it contradict the empirical accuracy gains; it means the central theoretical assertion needs to be restated as preserving a monotone transform of the normalized kernel, or augmented with a bound on when the linear approximation is accurate.\n\nThe reader's weakest assumption focused on uniform landmark sampling, which is a different concern; however, both concerns point to the theorem not delivering exactly what the abstract promises. I therefore mark agreement as partial. The verdict should remain conditional: the empirical contribution is plausible and reproducible in principle, but the theoretical claim and the evaluation protocol (especially kernel hyperparameter selection and the missing kernel baseline) need revision before acceptance.","tokens_in":14358,"tokens_out":11757,"duration_ms":127377,"concrete_test":"Fix a landmark set and two points with normalized kernel value r = 0.99. Draw P_rp independently 100,000 times and compute the sample mean of phi(x_i)·phi(x_j). The theorem predicts pi/2 - arccos(0.99) ≈ 1.430, not 0.99, so the 'first-order' approximation fails in a regime relevant to classification. Additionally, on the actual ENZYMES or Protein kernel matrices, compute max relative error |(pi/2 - arccos(r_ij)) - r_ij| / |r_ij| over pairs with r_ij > 0.5; if it exceeds 10%, the paper should either replace the kernel-preservation claim with preservation of the monotone transform f(r) or provide a regime/error analysis justifying the approximation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The theorem itself is correct as a conditional statement: for a fixed landmark set, E[phi(x_i)·phi(x_j)] = pi/2 - arccos(r), where r = Ghat_ij / sqrt(Ghat_ii Ghat_jj). The load-bearing weakness is the next step: the paper approximates arccos(r) ≈ pi/2 - r, concluding E ≈ r, and calls this 'preserving the normalized kernel up to first order.' That Taylor expansion is valid only near r = 0. It is not uniform on [-1,1], and normalized kernel values in the classification regime are often near 1. For r = 0.9 the predicted inner product is about 1.12, an error of 0.22; for r = 0.99 it is about 1.43, an error of 0.44. Since HDC classification compares a query against class prototypes formed by summing encodings, predictions depend on sums of f(r_ij) = pi/2 - arccos(r_ij), not on sums of r_ij. Monotonicity of f does not make the HDC linear model equivalent to the kernel's linear model. Thus the abstract's claim of an 'equivalent mapping' and the theorem discussion's 'first-order kernel preservation' overstate what is actually established. The exact nonlinear relationship is a real result, but it is a different claim.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes NysHD, an HDC encoding that composes Nyström embeddings of a user-supplied positive-semidefinite kernel with random hyperplane rounding (sign random projections), producing low-precision high-dimensional vectors. The main theoretical result, Theorem 1, states that the expected inner product of two encoded points equals π/2 − arccos of the normalized Nyström kernel value, and the authors use a first-order Taylor expansion of arccos to claim that normalized kernel values are approximately preserved. The paper further reports empirical gains over existing HDC encodings on graph and string datasets, alongside comparisons with deep learning baselines.","tokens_in":14629,"tokens_out":8701,"duration_ms":89534,"significance":"If the claims are properly qualified, this is a useful contribution to the HDC literature: it provides a clean recipe for importing non-translation-invariant kernels into HDC, and the proof of the exact conditional identity in Eq. (4) is straightforward and correct, relying only on Charikar's rounding result and the Nyström embedding identity. The empirical study covers several standard graph and string benchmarks and reports meaningful average accuracy improvements of 11% and 17% over GraphHD and N-gram HDC. These strengths are tempered by an overstatement in the 'equivalent mapping' language, a formal inconsistency in the statement of Theorem 1 regarding the expectation, and a reproducibility issue in the landmark-count configuration for two small datasets.","major_comments":[{"comment":"The statement of Theorem 1 says the expectation in Eq. (4) is taken over both landmark sampling and P_rp, but the right-hand side contains Ĝ_ij, which depends on the randomly sampled landmark set. The proof only averages over P_rp for a fixed landmark set (Eqs. (5)-(8)). This is not merely a notational issue: because arccos is nonlinear, E_Z[π/2 − arccos(Ĝ_ij/sqrt(Ĝ_ii Ĝ_jj))] is not equal to π/2 − arccos(E_Z[Ĝ_ij]/sqrt(E_Z[Ĝ_ii]E_Z[Ĝ_jj])) in general. The theorem should be restated as a conditional statement for a fixed landmark set, or the right-hand side of Eq. (4) must be written with the expectation over landmark sets applied to the whole expression. As written, the theorem is not correct.","section":"HDC Encoding via Nyström Approximation, Theorem 1 and Eq. (4)-(8)"},{"comment":"Equation (9) is a Taylor expansion of arccos around r=0, and it is not a global approximation on the domain [-1,1]. For r=0.9 the predicted inner product is about 1.12 instead of 0.9, and for r=0.99 it is about 1.43 instead of 0.99. Since HDC classification scores are sums of f(r_ij)=π/2 − arccos(r_ij) over class prototypes, monotonicity of f does not make the HDC linear model equivalent to the kernel's linear model. The abstract's phrase 'equivalent mapping in HDC' and the contribution statement that inner products 'preserve normalized kernel values' therefore overstate what is established. The exact identity in Eq. (4) is a legitimate and interesting result; the paper should present it as a fixed monotone nonlinear relationship between HDC inner products and normalized Nyström kernel values, and should avoid claiming global first-order equivalence without further bounds.","section":"Encoding Process, Eq. (9) and abstract/contributions"},{"comment":"The landmark count is set to s=max(300, 2% of training data). For MUTAG and Promoter the training sets have 150 and 84 samples, respectively, so s=300 cannot be sampled without replacement as Algorithm 1 requires. The reported results for these two datasets in Tables 2 and 3 are therefore not reproducible under the stated configuration. The authors should clarify whether s was capped at the dataset size, whether sampling was with replacement for small datasets, or whether a different rule was actually used.","section":"Experimental Setup and Baselines"}],"minor_comments":[{"comment":"The line 'Prp = [w1, w1, ..., wd]^T' appears to duplicate w1; it should be [w1, w2, ..., wd]^T or an equivalent enumeration of the sampled rows.","section":"Algorithm 1"},{"comment":"The sentence 'we validate 1' is missing a reference; it should read 'we validate Theorem 1'.","section":"Evaluation, first paragraph"},{"comment":"The entry 'Nautral Language' is a typo for 'Natural Language'.","section":"Table 1"},{"comment":"The phrase 'for for bio-sequence' contains a duplicated word, and the sentence about the GPU is ungrammatical ('required an Nvidia RTX 3050 GPU is used').","section":"Experimental Setup and Baselines"},{"comment":"The caption 'Numerical difference of spectral norm between normalized kernel matrices compute directly from kernel function and approximated kernel matrices with our encoding' is ambiguous; please specify whether the plotted quantity is ||K − K̂||_2, |σ(K) − σ(K̂)|, or some other norm, and describe how the approximated matrix is formed from the encodings.","section":"Figure 2"},{"comment":"The choice s=max(300, 2% of training data) is not justified, and since the number of landmarks is a free parameter, reporting sensitivity to s on at least one dataset would help the reader understand the accuracy/efficiency trade-off.","section":"Experimental Setup and Baselines"}],"recommendation":"major_revision","confidential_remarks":"The core derivation is sound and the empirical study is useful, so rejection is not warranted. The main issues are the incorrect expectation statement in Theorem 1 as written, the overclaimed 'equivalent mapping' language, and a reproducibility problem in the landmark count for MUTAG and Promoter. These are fixable within the scope of the manuscript, but they require substantive revision of the theoretical statement and the experimental configuration description."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a real new combination—Nyström kernel approximation composed with sign-random-projection rounding to make low-precision HDC encodings—and the core theorem is true if you read it as a statement conditional on the landmark set. The problem is the paper's own gloss on that theorem. It says the inner product 'preserves normalized kernel values up to first order,' but the first-order Taylor expansion of arccos is only valid near zero. For normalized kernel values near 1, which is the regime that matters for classification, the expected HDC inner product is far from the kernel value: at r = 0.9 the approximation error is about 0.22, and at r = 0.99 it's about 0.44. The exact relationship is a monotone transform, not the identity. That means the abstract's 'equivalent mapping' and the 'kernel-preserving' language overstate what is shown. HDC prototype scores are sums of these transformed similarities, and sums of a convex function of r are not the same as sums of r. This should be reworded and, ideally, the analysis should be framed around the exact monotone relationship rather than the first-order approximation.\n\nAlso, Theorem 1 as written says the expectation over both landmark sampling and P_rp equals an expression that depends on the random landmark set. The proof only gives the equality conditional on the landmarks. That's an easy fix—state the conditional version or properly integrate—but it needs fixing.\n\nThe empirical study is reasonably solid: eight graph datasets, four string datasets, ten runs, code provided, and the gains over GraphHD and N-gram HDC are plausible. But the missing baseline is the obvious one: a kernel SVM (or kernel ridge) with the same gappy or propagation kernel. Without that, you can't tell whether the HDC encoding is preserving enough of the kernel for learning, or whether the whole pipeline is just a complicated way to lose information relative to standard kernel machines. The paper also says kernel hyperparameters were 'chosen empirically' without a validation protocol, which matters for reproducibility.\n\nNone of this kills the contribution. The combination is new to HDC, the theorem is a clean application of Charikar's rounding to the Nyström embedding, and the paper opens up a useful design space. It deserves a serious referee, but the authors need to fix the theorem statement, temper the equivalence claim, and add the kernel baseline. For an audience of HDC researchers and edge-hardware folks, this is a useful read; kernel methods people will be frustrated by the overclaiming. I'd bring it to a reading group to argue about the exact versus approximate relationship.","headline":"Real new combination and a correct conditional theorem, but the paper overstates what 'preserving the kernel' means and skips the SVM baseline.","tokens_in":15192,"tokens_out":4306,"would_cite":false,"duration_ms":42963,"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":"NysHD composes the Nyström method with random hyperplane rounding so that any positive-semidefinite kernel becomes a low-precision HDC encoding whose inner products approximate normalized kernel values.","keywords":["hyperdimensional computing","Nyström method","kernel approximation","positive-semidefinite kernels","graph kernels","string kernels","random hyperplane rounding","low-precision embeddings"],"falsifier":"Take a dataset where the kernel matrix has high numerical rank or contains rare clusters that uniform landmarks are unlikely to cover, then compare the spectral-norm error $\\|G - C H_Z^+ C^T\\|$ with the gap between the HDC inner-product matrix and the true normalized kernel matrix; if the error is large and the accuracy advantage over the existing HDC baseline disappears, the practical claim would be refuted.","tokens_in":14142,"feed_emoji":"🧠","tokens_out":11607,"duration_ms":95740,"temperature":0.7,"pith_summary":"Hyperdimensional computing (HDC) represents data as high-dimensional random vectors, but its accuracy depends on how raw inputs are encoded. This paper proposes NysHD, an encoding that starts from a user-chosen positive-semidefinite kernel (a similarity measure that behaves like an inner product in a high-dimensional space) and produces HDC vectors whose inner products approximate the normalized kernel values. The payoff is that the mature literature on graph, string, and other specialized kernels can be imported into HDC, which previously relied on simpler L1/L2 or angular similarity encodings. In experiments, NysHD improves HDC classification accuracy by an average of 11% on graph datasets and 17% on string datasets, and it is competitive with or faster than several deep neural network baselines on the tasks tested.","feed_headline":"Any kernel becomes an HDC encoding via Nyström landmarks","feed_subtitle":"NysHD lifts HDC classification accuracy by 11% on graphs and 17% on strings while keeping single-pass training.","key_machinery":"The load-bearing machinery is the composition of the Nyström method and random hyperplane rounding. The Nyström method approximates the kernel matrix $G$ by $C H_Z^+ C^T$, where $C$ holds kernel values from each point to $s$ sampled landmarks, and it gives explicit features $\\phi_{nys}(x_i)=\\Lambda^{-1/2}Q^T C^{(i)}$ whose inner products reproduce the approximate matrix. Sign-thresholded random projection then converts these high-precision features into low-precision HDC vectors while preserving angular similarity: for unit vectors $v$ and $v'$, the expected normalized inner product of their signs is $1 - 2\\cos^{-1}(v\\cdot v')/\\pi$. The composition turns a kernel value into an angle, and the HDC inner product tracks that angle.","core_discovery":"The paper's central claim is that composing the Nyström low-rank approximation with sign-thresholded random projection produces an HDC encoding that tracks a user-defined kernel. For a positive-definite kernel $K$, landmarks $Z$, and Nyström approximation $\\hat{G} = C H_Z^+ C^T$, the encoding $\\phi(x_i)=\\sqrt{\\pi/(2d)}\\,\\operatorname{sign}(P_{rp}\\Lambda^{-1/2}Q^T C^{(i)})$ satisfies $E[\\phi(x_i)\\cdot\\phi(x_j)] = \\pi/2 - \\cos^{-1}\\big(\\hat{G}_{ij}/\\sqrt{\\hat{G}_{ii}\\hat{G}_{jj}}\\big)$. Because $\\cos^{-1}(t)$ expands as $\\pi/2 - t$ to first order, this expected inner product equals the normalized kernel value $\\hat{G}_{ij}/\\sqrt{\\hat{G}_{ii}\\hat{G}_{jj}}$ up to first order. The theorem thus gives a general recipe: any positive-semidefinite similarity function can be realized as an equivalent low-precision, randomized HDC mapping, provided the Nyström approximation of the kernel matrix is accurate.","pith_inferences":["Uniform landmark sampling is the weakest practical link: if the landmark set misses important regions of the data, the Nyström error dominates and the formal guarantee says nothing useful; adaptive landmark selection, which the paper leaves to future work, is the natural next step and could be tested by comparing spectral approximation error across sampling strategies.","Because the kernel choice is now the main design lever, progress in kernel design, such as alignment-tolerant kernels for time series, should transfer directly to HDC accuracy; this is a testable corollary the paper motivates but does not evaluate.","The sign-thresholding step is one of several possible low-precision quantizers, and replacing it with binary or ternary rounding may trade a small accuracy loss for larger hardware gains; the paper's identity gives a quantitative baseline for such experiments.","The result suggests a broader bridge: other kernel-approximation schemes beyond the Nyström method could be imported into HDC as long as they produce explicit finite-dimensional embeddings, though the paper only establishes the Nyström route."],"forward_implications":["Any positive-semidefinite kernel can be plugged into HDC classification by computing kernel values to a small landmark set, so HDC inherits the large existing library of graph, string, and time-series kernels.","HDC's single-pass training and low-precision hardware advantages remain intact, because the encoding step is a one-time kernel evaluation plus sign operations.","On the evaluated graph benchmarks NysHD raises average HDC accuracy by 11% over GraphHD, and on string benchmarks by 17% over N-gram HDC.","NysHD matches or exceeds several deep graph and string models on some datasets while training much faster, indicating that HDC can close part of the accuracy gap with deep learning.","The first-order approximation means HDC inner products track normalized, not raw, kernel values, so scale information in the kernel is discarded and classification is driven by angular similarity."],"supporting_citations":[{"why":"It introduces the Nyström method for speeding up kernel machines, which NysHD builds on.","marker":"(Williams and Seeger 2000)"},{"why":"It supplies the low-rank approximation formula $\\hat{G}=C H_Z^+ C^T$ and the resulting explicit Nyström features.","marker":"(Drineas, Mahoney, and Cristianini 2005)"},{"why":"It gives the sign-thresholded random projection identity that converts the Nyström features into low-precision HDC vectors while preserving angles.","marker":"(Charikar 2002)"},{"why":"It analyzes Nyström sampling strategies, justifying the uniform landmark scheme the paper uses and motivating the adaptive sampling it defers to future work.","marker":"(Kumar, Mohri, and Talwalkar 2012)"},{"why":"It defines the gappy string kernel used in the string classification experiments.","marker":"(Leslie, Kuang, and Bennett 2004)"},{"why":"It defines the propagation graph kernel used in the graph classification experiments.","marker":"(Neumann et al. 2016)"},{"why":"It provides GraphHD, the graph HDC encoding baseline NysHD is compared against and improves by 11% on average.","marker":"(Nunes et al. 2022)"},{"why":"It provides the N-gram HDC string encoding baseline NysHD is compared against and improves by 17% on average.","marker":"(Joshi, Halseth, and Kanerva 2017)"}],"fun_headline_variants":["NysHD: any kernel becomes an HDC encoding via Nyström","Kernels into hypervectors: NysHD closes the gap","Nyström bridges hyperdimensional computing and kernels","HDC with any kernel: NysHD lifts graph and string accuracy","From kernels to hypervectors: NysHD's Nyström recipe"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that uniform random sampling of $s$ landmarks from the training set gives a Nyström approximation accurate enough for classification, because the formal kernel-preservation guarantee inherits whatever approximation error the Nyström step makes.","fun_headline_variants_meta":{"raw":{"variants":["NysHD: any kernel becomes an HDC encoding via Nyström","Kernels into hypervectors: NysHD closes the gap","Nyström bridges hyperdimensional computing and kernels","HDC with any kernel: NysHD lifts graph and string accuracy","From kernels to hypervectors: NysHD's Nyström recipe"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000326,"raw_usage":{"total_tokens":1847,"prompt_tokens":991,"completion_tokens":856,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":607,"completion_tokens_details":{"reasoning_tokens":762}},"tokens_in":607,"tokens_out":856,"duration_ms":7983,"temperature":1.0,"reasoning_tokens":762,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T19:23:08.387332+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take a dataset where the kernel matrix has high numerical rank or contains rare clusters that uniform landmarks are unlikely to cover, then compare the spectral-norm error $\\|G - C H_Z^+ C^T\\|$ with the gap between the HDC inner-product matrix and the true normalized kernel matrix; if the error is large and the accuracy advantage over the existing HDC baseline disappears, the practical claim would be refuted.","supporting_citations":[{"cited_title":"Sampling methods for the Nystr","cited_arxiv_id":null,"evidence_quote":"It analyzes Nyström sampling strategies, justifying the uniform landmark scheme the paper uses and motivating the adaptive sampling it defers to future work."}],"review_version":1}