Research map / Learning theory and algorithms / Kernels and regression theory
Bridging the Gap Between Hyperdimensional Computing and Kernel Methods via the Nyström Method
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes NysHD, an HDC encoder that uses the Nyström kernel approximation plus sign-thresholded random projection to turn any positive-semidefinite kernel into hyperdimensional encodings, improving over GraphHD and N-gram HDC encoders on graph and string classification.
Problem
Existing HDC encoders capture only simple similarities (L1/L2, angular) and cannot exploit rich kernels for complex data such as graphs with node attributes, strings, and time series.
Approach
Use the Nyström method to build explicit low-precision features from any user-defined PSD kernel over landmark points, then apply random hyperplane rounding so that HDC dot products approximate the normalized kernel.
Key results
- NysHD improves graph classification accuracy over GraphHD by about 11% on average and by 38% on ENZYMES.
- On string datasets NysHD improves over N-gram HDC by about 17% on average, reaching 98% on Protein and 89% on Promoter.
- NysHD outperforms DGCNN by about 3% and GIN and GIUNet by about 6% on average over graph datasets, and is on average 52% faster than GCN.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use NysHD instead of GraphHD encoding | HDC graph classification · Graph datasets | classification accuracy: 11% better accuracy | Helped |
| Use NysHD instead of N-gram HDC encoding | HDC string classification · String datasets | classification accuracy: 17% | Helped |
Surprising findings
- On SMS and Splice, fine-tuned language model (LM) baselines achieve better accuracy than NysHD, though NysHD trains 6 to 83 times faster.
Limitations
- Encoding cost depends on number of kernel evaluations, scaling with number of landmarks, and kernel choice is empirical.
- Uniform landmark sampling only; more sophisticated sampling is left for future work.
- Still trails GCN on several graph datasets and LM fine-tuning on SMS and Splice.
Experimental setup
Datasets: ENZYMES NCI1 D&D BZR MUTAG COX2 NCI109 Mutagenicity Protein SMS Splice Promoter
Benchmarks: ENZYMES NCI1 D&D BZR MUTAG COX2 NCI109 Mutagenicity Protein SMS Splice Promoter
Metrics: classification accuracy training time (s) spectral norm difference of normalized kernel matrix
Baselines: GraphHD N-gram HDC DGCNN GCN GIN GIUNet ESM-2-8m fine-tuning BERT fine-tuning
Builds on: hyperdimensional computing Nyström method random Fourier features OnlineHD GraphHD
Closest papers by meaning
- Understanding Hyperdimensional Computing for Parallel Single-Pass Learning (NeurIPS 2022 · similarity 0.89)
- Nyström Kernel Mean Embeddings (ICML 2022 · similarity 0.85)
- Hyperdimensional Computing as a Framework for Systematic Aggregation of Image Descriptors (CVPR 2021 · similarity 0.85)
- Incremental Nyström-based Multiple Kernel Clustering (AAAI 2025 · similarity 0.84)
- Random features for Grassmannian kernel approximation with bounded rank-one projections (NeurIPS 2026 · similarity 0.83)
- Hyperbolic Category Discovery (CVPR 2025 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.