Bridging the Gap Between Hyperdimensional Computing and Kernel Methods via the Nystr\"om Method

# Bridging the Gap Between Hyperdimensional Computing and Kernel Methods via the Nyström Method
Source: [https://arxiv.org/html/2608.06860](https://arxiv.org/html/2608.06860)
###### Abstract

Hyperdimensional computing \(HDC\) is an approach from the cognitive science literature for solving information processing tasks using data represented as high\-dimensional random vectors\. The technique has a rigorous mathematical backing, and is easy to implement in energy\-efficient and highly parallel hardware like FPGAs and “processing\-in\-memory” architectures\. The effectiveness of HDC in machine learning largely depends on how raw data is mapped to high\-dimensional space\. In this work, we propose NysHD, a new method for constructing this mapping that is based on the Nyström method from the literature on kernel approximation\. Our approach provides a simple recipe to turn any user\-defined positive\-semidefinite similarity function into an equivalent mapping in HDC\. There is a vast literature on the design of such functions for learning problems\. Our approach provides a mechanism to import them into the HDC setting, expanding the types of problems that can be tackled using HDC\. Empirical evaluation against existing HDC encoding methods shows that NysHD can achieve, on average, 11% and 17% better classification accuracy on graph and string datasets respectively\.

Code—https://github\.com/QuanlingZhao/NysHD

## Introduction

Biological brains “compute” using data representations that are intrinsically fault\-tolerant, suitable for highly\-parallel circuitry, and reveal complex structures in an environment that are easy to learn\(Hertz[2018](https://arxiv.org/html/2608.06860#bib.bib5)\)\. Motivated by these desirable qualities, hyperdimensional computing \(HDC\) builds on theories of representation from cognitive science\(Kanerva[2009](https://arxiv.org/html/2608.06860#bib.bib8); Plate[1995](https://arxiv.org/html/2608.06860#bib.bib7)\)to develop novel hardware and algorithms for information processing tasks\. In HDC, all computation is performed using high\-dimensional, low\-precision, vector representations of data\. These representations can be manipulated using simple, element\-wise operators, so as to implement learning algorithms or other information processing tasks\.

In contrast to deep learning models, training HDC\-based models can typically be done in a single pass over the training data\(Hernández\-Canoet al\.[2021](https://arxiv.org/html/2608.06860#bib.bib25); Yuet al\.[2022](https://arxiv.org/html/2608.06860#bib.bib49)\)and does not require back\-propagation\. The operations used in HDC are lightweight and highly parallelizable, making them suitable for implementation on low\-energy and parallel hardware platforms\. This makes HDC an attractive alternative for implementing learning in resource constrained settings\. As a result, HDC has gained significant interest in recent years, especially in Internet of Things \(IoT\)\(Khaleghiet al\.[2022](https://arxiv.org/html/2608.06860#bib.bib10); Zhaoet al\.[2022](https://arxiv.org/html/2608.06860#bib.bib11); Morriset al\.[2021](https://arxiv.org/html/2608.06860#bib.bib12)\); and in the computer hardware community\(Duttaet al\.[2022](https://arxiv.org/html/2608.06860#bib.bib14); Kanget al\.[2022a](https://arxiv.org/html/2608.06860#bib.bib15)\)such as FPGAs\(Salamatet al\.[2019](https://arxiv.org/html/2608.06860#bib.bib38)\), GPUs\(Kanget al\.[2022b](https://arxiv.org/html/2608.06860#bib.bib39)\), ASICs\(Zhanget al\.[2023](https://arxiv.org/html/2608.06860#bib.bib40)\)and in\-memory computing\(Duttaet al\.[2022](https://arxiv.org/html/2608.06860#bib.bib14); Xuet al\.[2023](https://arxiv.org/html/2608.06860#bib.bib37)\)\.

The first stage in any HDC task is encoding, which maps data from its ambient representationx∈𝒳x\\in\\mathcal\{X\}, into a representationϕ​\(x\)\\phi\(x\)residing in a high\-dimensional inner product spaceℋ\\mathcal\{H\}\(Kleykoet al\.[2023](https://arxiv.org/html/2608.06860#bib.bib50)\)\. HDC uses addition and multiplication \(called ‘bundling” and “binding” in the HDC literature\), to build representations of complex structures from simple building blocks or to implement tasks like learning\. For instance, classification using HDC represents each class as a sum of the encodings of its training data, called a “prototype\.” Inference can then be performed by finding the closest prototype to a query\.

The crucial assumption underlying the success of this technique is that “similar” points in𝒳\\mathcal\{X\}are mapped to “similar” regions ofℋ\\mathcal\{H\}\. In practice, this desideratum typically means that dot\-products inℋ\\mathcal\{H\}should be reflective of some salient notion of similarity on𝒳\\mathcal\{X\}\. In HDC, one typically builds representations incrementally, by bundling and binding together the embeddings of simpler atoms\. In this work, we observe that one can also go in the opposite direction: starting from a known similarity function of interest, it is possible to generate an equivalent—up to some approximation factor—encoding function\.

The advantage of this “top down” approach is that there is a vast literature on designing good similarity functions for different kinds of learning problems\. In machine learning, similarity functions that work by computing inner products between high\-dimensional embeddings of data are called kernel functions, and are the basis of kernel methods, a vast area of research in theoretical and applied ML\(Shawe\-Taylor and Cristianini[2004](https://arxiv.org/html/2608.06860#bib.bib1); Smola and Schölkopf[1998](https://arxiv.org/html/2608.06860#bib.bib2)\)\. This literature has devoted substantial attention to the problem of designing good similarity functions, which are also potentially applicable to the kinds of problems encountered in HDC\. In this work, we study an approach, based on the Nyström method from the literature on kernel approximation\(Williams and Seeger[2000](https://arxiv.org/html/2608.06860#bib.bib41)\), which can take a user defined kernel and generate an low\-precision, randomized embedding, suitable for use in the kinds of learning algorithms employed in HDC\. In a nutshell, the contributions of this paper are as follows:

- •We propose NysHD, a new way to generate embeddings for HDC which can turn any user\-defined kernel function into an equivalent encodings\.
- •We analyze the kernel\-preserving properties of NysHD formally and show that the inner product between encoded samples preserves normalized kernel values\.
- •We perform an empirical evaluation against existing HDC encoding methods and various neural network architectures and show our method substantially improves the performance of HDC\-based learning, while preserving efficiency benefits relative to DNNs\.

From a practical standpoint, our work has the potential to expand the scope of tasks that can be effectively addressed using HDC by allowing practitioners to access the large repertoire of kernels that have been designed for them \(i\.e\. graph kernels, string kernels etc\.\)\.

## Background and Related Work

### Learning With HDC

![Refer to caption](https://arxiv.org/html/2608.06860v1/figs/HD_Overview.png)Figure 1:Overview of HDC training and inference for classification tasks\.In this work, we focus on using HDC to solve classification problems, which is a common practical application of the technique\(Imaniet al\.[2019](https://arxiv.org/html/2608.06860#bib.bib47); Rahimiet al\.[2018](https://arxiv.org/html/2608.06860#bib.bib3); Menonet al\.[2022](https://arxiv.org/html/2608.06860#bib.bib4)\)\. Fig[1](https://arxiv.org/html/2608.06860#Sx2.F1)demonstrates a typical HDC learning workflow for classification\(Morriset al\.[2021](https://arxiv.org/html/2608.06860#bib.bib12); Nuneset al\.[2022](https://arxiv.org/html/2608.06860#bib.bib26); Miranda and d’Aliberti[2022](https://arxiv.org/html/2608.06860#bib.bib43)\)\. Let𝒟=\{\(x1,y1\),…,\(xn,yn\)\}\{\\mathcal\{D\}\}=\\\{\(x\_\{1\},y\_\{1\}\),\.\.\.,\(x\_\{n\},y\_\{n\}\)\\\}be a set of training data, wherexi∈𝒳x\_\{i\}\\in\{\\mathcal\{X\}\}is an input, andyi∈\{1,…,c\}y\_\{i\}\\in\\\{1,\.\.\.,c\\\}is a class label\. The first step is to embed the training data into add\-dimensional inner product spaceℋ\{\\mathcal\{H\}\}under a map \(called the encoding function\)ϕ:𝒳→ℋ\\phi:\{\\mathcal\{X\}\}\\to\{\\mathcal\{H\}\}\. The “training” step then associates each class with a vector inℋ\{\\mathcal\{H\}\}, which is typically formed by summing \(bundling\) the training data corresponding to a particular class\. Specifically, classjjis represented asθj=∑i=1nαi​j​ϕ​\(xi\)\\theta\_\{j\}=\\sum\_\{i=1\}^\{n\}\\alpha\_\{ij\}\\phi\(x\_\{i\}\)whereαi​j=1​\(yi=j\)\\alpha\_\{ij\}=\{1\}\(y\_\{i\}=j\)\. In practice,θj\\theta\_\{j\}is sometimes quantized to reduce precision in some fashion, which is beneficial in some hardware settings\. The label of a queryxxis predicted by viay^=arg​maxj∈\{1,…,c\}⁡ϕ​\(x\)⋅θj\\hat\{y\}=\\operatorname\*\{arg\\,max\}\_\{j\\in\\\{1,\.\.\.,c\\\}\}\\phi\(x\)\\cdot\\theta\_\{j\}where the operands are sometimes normalized if appropriate\. In either case, this procedure can be interpreted as associating each class to a linear scoring function inℋ\{\\mathcal\{H\}\}and performing inference by picking the class of highest score \- a common paradigm in machine learning\. Fine\-tuning the class vectorsθj\\theta\_\{j\}is common, often achieved by running the Perceptron algorithm\(Rosenblatt[1958](https://arxiv.org/html/2608.06860#bib.bib48)\), referred to as “re\-training” in HDC literature\.

A number of HDC encoding methods have been proposed to encode different types of data\. For example, string or text data can be encoded through theNN\-gram encoding method\(Joshiet al\.[2017](https://arxiv.org/html/2608.06860#bib.bib42); Imaniet al\.[2018](https://arxiv.org/html/2608.06860#bib.bib21)\)\. Concretely, letS=\(a1​a2​a3​…​aN\)S=\(a\_\{1\}a\_\{2\}a\_\{3\}\.\.\.a\_\{N\}\)be a string ofNNcharacters drawn from some alphabet𝒜\{\\mathcal\{A\}\}\(say, the latin alphabet or\{A,T,G,C\}\\\{\\texttt\{A,T,G,C\}\\\}\)\. To encodeSS, we start by assigning eacha∈𝒜a\\in\{\\mathcal\{A\}\}an embeddingϕ​\(a\)\\phi\(a\)by sampling uniformly at random from\{±1/d\}d\\\{\\pm 1/\\sqrt\{d\}\\\}^\{d\}, after which, we representSSasa1∘ρ​\(a2\)∘ρ2​\(a3\)∘⋯∘ρN−1​\(aN\)a\_\{1\}\\circ\\rho\(a\_\{2\}\)\\circ\\rho^\{2\}\(a\_\{3\}\)\\circ\\dots\\circ\\rho^\{N\-1\}\(a\_\{N\}\)where∘\\circis element\-wise multiplication\(Joshiet al\.[2017](https://arxiv.org/html/2608.06860#bib.bib42)\)andρ\\rhois a permutation operation of the vector coordinates,ρn\\rho^\{n\}means same permutation appliednntimes in sequence\. If∘\\circis multiplication, the wayNN\-grams representations are constructed makes them almost mutually orthogonal inℋ\\mathcal\{H\}in the sense that𝔼​\[ϕ​\(S\)⋅ϕ​\(S′\)\]=1​\(S=S′\)\{\\mathbb\{E\}\}\[\\phi\(S\)\\cdot\\phi\(S^\{\\prime\}\)\]=1\(S=S^\{\\prime\}\)\. The deviation from this expectation can be controlled using concentration arguments\(Thomaset al\.[2021](https://arxiv.org/html/2608.06860#bib.bib9)\)\.

Finally, longer strings that contain multipleNN\-grams can be treated as a sum ofNN\-gram vectors\. This string encoding scheme can be viewed as a “compressed” version of the bag\-of\-words model\(Harris[1954](https://arxiv.org/html/2608.06860#bib.bib54)\)in the sense that allNN\-gram vectors are superimposed into one representation\. Intuitively, the inner product between two such encoded strings can measure how “similar” two strings are, as that value would be large if two strings shared many commonNN\-grams, and vice versa\. For general feature vectors \(or simple images\), techniques based on random projection are popular\(Morriset al\.[2021](https://arxiv.org/html/2608.06860#bib.bib12); Khaleghiet al\.[2022](https://arxiv.org/html/2608.06860#bib.bib10)\)\.

Existing HDC encoding methods tend to capture fairly simple notions of similarity based on the L1/L2 or angular distance\. However, the design of good encoding functions for complex forms of data like graphs and time\-series remains an important area of research\. For inspiration, we turn to another area of machine learning that has thought extensively about how to measure similarities between data points using high\-dimensional vectors\.

### Kernel Methods

Kernel methods are a wide ranging area of research in statistics and machine learning that shares many similarities with HDC\(Shawe\-Taylor and Cristianini[2004](https://arxiv.org/html/2608.06860#bib.bib1); Meantiet al\.[2020](https://arxiv.org/html/2608.06860#bib.bib34); Hofmannet al\.[2008](https://arxiv.org/html/2608.06860#bib.bib19)\)\. Much like in HDC, kernel methods work by embedding data into a high\-dimensional space wherein similarities are measured using inner products\. That is to say, kernel methods measure similarities between data pointsx,x′∈𝒳x,x^\{\\prime\}\\in\\mathcal\{X\}via a functionK​\(x,x′\)=ψ​\(x\)⋅ψ​\(x′\)K\(x,x^\{\\prime\}\)=\\psi\(x\)\\cdot\\psi\(x^\{\\prime\}\), called a “kernel function,” whereψ:𝒳→ℋ\\psi:\{\\mathcal\{X\}\}\\to\{\\mathcal\{H\}\}is an embedding into an inner product space\. For many types of kernel functions used in practice, it is possible to computeK​\(x,x′\)K\(x,x^\{\\prime\}\)directly on the ambient representation of the data without materializing the embeddings\. Notable examples include the Gaussian kernelK​\(x,x′\)∝exp⁡\(−‖x−x′‖22\)K\(x,x^\{\\prime\}\)\\propto\\exp\(\-\\\|x\-x^\{\\prime\}\\\|\_\{2\}^\{2\}\), and thepp\-th order polynomial kernelK​\(x,x′\)=\(1\+x⋅x′\)pK\(x,x^\{\\prime\}\)=\(1\+x\\cdot x^\{\\prime\}\)^\{p\}\. Both of these kernels can be evaluated in closed form on the ambient representation of the data, allowing kernel methods to*implicitly*compute a similarity based on a high\-dimensional embedding\. HDC, however, always explicitly materializes the embeddings, hence the need for an encoding functionϕ\\phi\.

Kernel\-based learning methods make predictions using functions taking the formf​\(x\)=∑i=1nai​k​\(xi,x\)f\(x\)=\\sum\_\{i=1\}^\{n\}a\_\{i\}k\(x\_\{i\},x\), wherex1,…,xnx\_\{1\},\.\.\.,x\_\{n\}are training data points, andα1,…,αn\\alpha\_\{1\},\.\.\.,\\alpha\_\{n\}are weights that are learned by a training algorithm\. Noting thatf​\(x\)=∑i=1nαi​k​\(x,xi\)=ψ​\(x\)⋅θf\(x\)=\\sum\_\{i=1\}^\{n\}\\alpha\_\{i\}k\(x,x\_\{i\}\)=\\psi\(x\)\\cdot\\thetawhereθ=∑i=1nai​ψ​\(xi\)\\theta=\\sum\_\{i=1\}^\{n\}a\_\{i\}\\psi\(x\_\{i\}\), in this way we can interpret such functions as*linear models*in the embedding space associated with the kernel, much like in the previous paragraph on HDC\. One significant difference between kernel methods and HDC, is that in the former the embeddings are implicit, and similarities are evaluated using the kernel function\. This property is appealing because it allows one to efficiently work with infinite\-dimensional embeddings, which can have desirable properties for learning\(Steinwart[2001](https://arxiv.org/html/2608.06860#bib.bib6)\)\.

### Kernel Methods and HDC

There is a large body of theoretical and applied literature on kernel methods that has developed kernel functions applicable to many settings of practical interest\(Neumannet al\.[2016](https://arxiv.org/html/2608.06860#bib.bib17); Leslieet al\.[2001](https://arxiv.org/html/2608.06860#bib.bib18); Shimodairaet al\.[2001](https://arxiv.org/html/2608.06860#bib.bib52); Shawe\-Taylor and Cristianini[2004](https://arxiv.org/html/2608.06860#bib.bib1)\)\. To provide a concrete example of how the literature on kernel methods can offer insights for the HDC community, we first consider the encoding of time\-series data in HDC\. Similar to the previously discussedNN\-gram encoding, the permutation operation is applied to encode the temporal information of time\-series data\(Joshiet al\.[2017](https://arxiv.org/html/2608.06860#bib.bib42); Asgarinejadet al\.[2020](https://arxiv.org/html/2608.06860#bib.bib22)\)\. However, such encoding schemes can fail if the events in two time\-series do not align exactly\. Since each time step is associated with a unique permutation during encoding, even a small shift in events between time\-series can cause existing HDC encoding methods to map the two time\-series to nearly orthogonal vectors\. In practice, however, if two time\-series reflect the same underlying activity or nature, one would expect their similarity to be preserved after encoding, even if some event misalignment exists\. On this issue, the literature on kernel methods suggests a solution: the dynamic\-time\-warping kernel\(Gudmundssonet al\.[2008](https://arxiv.org/html/2608.06860#bib.bib20)\), which can handle time\-series sequences with misalignment or time\-stretching/compression\.

For graphs, GraphHD\(Nuneset al\.[2022](https://arxiv.org/html/2608.06860#bib.bib26)\)proposes to encode graph topology induced by PageRank centrality metric\(Brin and Page[1998](https://arxiv.org/html/2608.06860#bib.bib27)\)\. However, this process does not utilize crucial information such as node labels or node attributes \(where each node in the graph is associated with a feature vector or a label\)\. Such limitations have been addressed by kernel methods\. For example, the propagation kernell\(Neumannet al\.[2016](https://arxiv.org/html/2608.06860#bib.bib17)\)works with graphs that include node labels or node attributes, therefore is capable of capturing a potentially richer notion of similarity\.

In this work, our goal is to devise a procedure that can translate any kernel into an equivalent HDC encoding, thereby allowing practitioners to exploit the wealth of kernel functions that have been designed for practical problems while continuing to reap the benefits of computing with HDC representations\.

### Related Work

The connection between HDC and kernel approximation is generally well known\(Yuet al\.[2022](https://arxiv.org/html/2608.06860#bib.bib49); Thomaset al\.[2021](https://arxiv.org/html/2608.06860#bib.bib9); Paxon Fradyet al\.[2021](https://arxiv.org/html/2608.06860#bib.bib23); Voelker[2020](https://arxiv.org/html/2608.06860#bib.bib78)\), mostly through the lens of random Fourier features \(RFF\)\(Rahimi and Recht[2007](https://arxiv.org/html/2608.06860#bib.bib24)\)\. RFF is a sampling based scheme that generates a vector of featuresϕ​\(x\)∈ℝd\\phi\(x\)\\in\{\\mathbb\{R\}\}^\{d\}with the property thatϕ​\(x\)⋅ϕ​\(x′\)≈K​\(x,x′\)\\phi\(x\)\\cdot\\phi\(x^\{\\prime\}\)\\approx K\(x,x^\{\\prime\}\), whereKKis a shift\-invariant kernel \(kernel function that depends only on the relative distance between inputs, e\.g\. the Gaussian kernel and Laplacian kernels\)\. Closely related methods arise in the HDC literature under the names “nonlinear\-encoding”\(Miranda and d’Aliberti[2022](https://arxiv.org/html/2608.06860#bib.bib43); Imaniet al\.[2020](https://arxiv.org/html/2608.06860#bib.bib44)\)and “fractional power encoding”\(Paxon Fradyet al\.[2021](https://arxiv.org/html/2608.06860#bib.bib23)\)\. Using RFF in the context of HDC means that inner products in HD space approximate some shift\-invariant kernel, usually the Gaussian or Sinc kernels\. However, a limitation of RFF is that it can only work with shift\-invariant kernels, which many useful kernels do not satisfy, such as kernels on graphs and strings\. The Nyström method provides a way to generate approximations for a larger class of kernels that do not need to be translation invariant\.

## HDC Encoding via Nyström Approximation

In this section, we describe our new encoding algorithm, NysHD, for HDC using the Nyström method for kernel approximation\. We also demonstrate that the inner product between encoded samples, in expectation, preserves normalized kernel values\.

Given a suitable kernel functionKK, our goal is to generate an encoding functionϕ:𝒳→ℋ\\phi:\\mathcal\{X\}\\rightarrow\\mathcal\{H\}such thatϕ​\(x\)⋅ϕ​\(x′\)≈K​\(x,x′\)∀x,x′∈𝒟\\phi\(x\)\\cdot\\phi\(x^\{\\prime\}\)\\approx K\(x,x^\{\\prime\}\)\\quad\\forall x,x^\{\\prime\}\\in\\mathcal\{D\}, where𝒟\\mathcal\{D\}is some subset of𝒳\\mathcal\{X\}\. This property is useful for learning algorithms that are widely employed in HDC as it enables them to exploit more useful similarities captured by the kernel\.

### Nyström Method

Conventional realizations of kernel\-based learning algorithms commonly require storing all pairwise evaluations of the kernel function in a large matrixGGdefined element\-wise byGi​j=K​\(xi,xj\)G\_\{ij\}=K\(x\_\{i\},x\_\{j\}\), which is problematic whennnis large\. The Nyström method is a low\-rank matrix approximation technique widely employed to speed up kernel machines by avoiding the need to store the entire kernel matrix\(Williams and Seeger[2000](https://arxiv.org/html/2608.06860#bib.bib41); Drineaset al\.[2005](https://arxiv.org/html/2608.06860#bib.bib16); Kumaret al\.[2012](https://arxiv.org/html/2608.06860#bib.bib36)\)\. In this way, the Nyström method is similar to RFF since they are both sampling\-based schemes and can be used to approximate kernel functions\. The key difference between RFF and the Nyström method is that the Nyström method can work with a larger class of kernels than RFF, many of which are useful for applications involving discrete structures such as string and graph\.

Intuitively, the Nyström method works by sub\-sampling the kernel matrix and reconstructing the full kernel matrix from the sampled one\. This is possible because the kernel matrix is typically close to low\-rank in practice\. Concretely, suppose we have a dataset𝒟=\{x1,x2,…,xn\}\\mathcal\{D\}=\\\{x\_\{1\},x\_\{2\},\.\.\.,x\_\{n\}\\\}, from which we sample a set of landmarks𝒵=\{z1,…,zs\}\\mathcal\{Z\}=\\\{z\_\{1\},\.\.\.,z\_\{s\}\\\}, wheres≪ns\\ll n\. LetG∈ℝn×nG\\in\\mathbb\{R\}^\{n\\times n\}be the full kernel matrix defined element\-wise byGi​j=K​\(xi,xj\)G\_\{ij\}=K\(x\_\{i\},x\_\{j\}\), and letH𝒵∈ℝs×sH\_\{\\mathcal\{Z\}\}\\in\\mathbb\{R\}^\{s\\times s\}be the sub\-sampled kernel matrix defined element\-wise by\(H𝒵\)i​j=K​\(zi,zj\)\(H\_\{\\mathcal\{Z\}\}\)\_\{ij\}=K\(z\_\{i\},z\_\{j\}\)\. The Nyström method yields the following approximation\(Drineaset al\.[2005](https://arxiv.org/html/2608.06860#bib.bib16)\):

G^=C​H𝒵\+​CT≈G\\hat\{G\}=CH\_\{\\mathcal\{Z\}\}^\{\+\}C^\{T\}\\approx G\(1\)WhereCCis ann×sn\\times smatrix such thatCi​j=K​\(xi,zj\)C\_\{ij\}=K\(x\_\{i\},z\_\{j\}\)for some kernel functionKKandHZ\+H\_\{Z\}^\{\+\}denotes the pseudo\-inverse ofH𝒵H\_\{\\mathcal\{Z\}\}\. There is a robust theoretical literature on the Nyström method, providing bounds on approximation error based on the number of selected landmarks and various sampling strategies\(Kumaret al\.[2012](https://arxiv.org/html/2608.06860#bib.bib36)\)\. LetQQandΛ\\Lambdabe the eigenvectors and eigenvalues ofH𝒵H\_\{\\mathcal\{Z\}\}then:

HZ\+=Q​Λ−1​QTH\_\{Z\}^\{\+\}=Q\\Lambda^\{\-1\}Q^\{T\}This allows one to generate encodings explicitly viaϕnys​\(xi\)=Λ−12​QT​C\(i\)\\phi\_\{\\text\{nys\}\}\(x\_\{i\}\)=\\Lambda^\{\-\\frac\{1\}\{2\}\}Q^\{T\}C^\{\(i\)\}, which approximates the kernel:

ϕnys​\(xi\)⋅ϕnys​\(xj\)=\(Λ−12​QT​C\(i\)\)⋅\(Λ−12​QT​C\(j\)\)=G^i​j\\begin\{split\}&\\phi\_\{\\text\{nys\}\}\(x\_\{i\}\)\\cdot\\phi\_\{\\text\{nys\}\}\(x\_\{j\}\)\\\\ &=\\left\(\\Lambda^\{\-\\frac\{1\}\{2\}\}Q^\{T\}C^\{\(i\)\}\\right\)\\cdot\\left\(\\Lambda^\{\-\\frac\{1\}\{2\}\}Q^\{T\}C^\{\(j\)\}\\right\)=\\hat\{G\}\_\{ij\}\\end\{split\}\(2\)Wherexi,xj∈𝒟x\_\{i\},x\_\{j\}\\in\\mathcal\{D\}andC\(i\)C^\{\(i\)\}denotes theit​hi^\{th\}row ofCCin a column vector\. While the encodings produced by Nyström method directly satisfy the desired kernel approximation property, they are, in general, of high\-precision which is undesirable in some settings of interest in HDC\(Khaleghiet al\.[2022](https://arxiv.org/html/2608.06860#bib.bib10)\)\. Our method rectifies this issue by composing the features extracted using the Nyström method with another encoding technique that preserves angular similarities which we discuss in detail in the next section\.

Due to the data\-dependent nature of the Nyström method, the quality of its approximation and computational complexity depends on the size and composition of𝒵\\mathcal\{Z\}\. As an initial step, in this paper we simply use uniform sampling without replacement\(Williams and Seeger[2000](https://arxiv.org/html/2608.06860#bib.bib41); Kumaret al\.[2012](https://arxiv.org/html/2608.06860#bib.bib36)\)as our sampling strategy\. However, more sophisticated strategies such as ensemble and adaptive sampling\(Kumaret al\.[2012](https://arxiv.org/html/2608.06860#bib.bib36)\)for constructing landmark sets can potentially lead to better performance and warrant further exploration in future work\.

### Encoding Process

To achieve the aforementioned goals, we compose random hyperplane rounding\(Charikar[2002](https://arxiv.org/html/2608.06860#bib.bib57)\)with the Nyström method to generate HDC embeddings that approximate a desired kernel\. Alg\.[1](https://arxiv.org/html/2608.06860#alg1)describes the process for generating the Nyström embedding matrix, followed by data point encoding in Alg\.[2](https://arxiv.org/html/2608.06860#alg2)\.

Algorithm 1Generate the Nyström embedding matrix0:kernel

KKover

𝒳\\mathcal\{X\}, dataset

𝒟\\mathcal\{D\}, number of landmarks

s\>0s\>0, HDC dimension

d\>0d\>0
𝒵←\\mathcal\{Z\}\\leftarrowsample

sspoints from

𝒟\\mathcal\{D\}without replacement/\*Landmarks\*/

\(H𝒵\)i​j=K​\(zi,zj\)∀0≤i,j≤s\(H\_\{\\mathcal\{Z\}\}\)\_\{ij\}=K\(z\_\{i\},z\_\{j\}\)\\quad\\forall\\quad 0\\leq i,j\\leq s/\*Partial kernel Matrix over landmarks\*/

Q​Λ​QT=H𝒵Q\\Lambda Q^\{T\}=H\_\{\\mathcal\{Z\}\}/\*Symmetric Eigen\-decomposition\*/

PrpP\_\{\\text\{rp\}\}=

\[w1,w1,⋯,wd\]T∈ℝd×s\[w\_\{1\},w\_\{1\},\\cdots,w\_\{d\}\]^\{T\}\\in\\mathbb\{R\}^\{d\\times s\}/\*wiw\_\{i\}sampled from s dimensional unit sphere\*/

Pnys=Prp​Λ−12​QTP\_\{\\text\{nys\}\}=P\_\{\\text\{rp\}\}\\Lambda^\{\-\\frac\{1\}\{2\}\}Q^\{T\}

return

PnysP\_\{\\text\{nys\}\},

𝒵\\mathcal\{Z\}

Algorithm 2Encode one data point from𝒟\\mathcal\{D\}0:

xi∈𝒟x\_\{i\}\\in\\mathcal\{D\}, Nyström embedding matrix

PnysP\_\{\\text\{\\text\{nys\}\}\}, Landmarks

𝒵\\mathcal\{Z\}and kernel function

KK
C\(i\)=\[K​\(xi,z1\)K​\(xi,z2\)⋯K​\(xi,zs\)\]T∈ℝsC^\{\(i\)\}=\\begin\{bmatrix\}K\(x\_\{i\},z\_\{1\}\)&K\(x\_\{i\},z\_\{2\}\)&\\cdots&K\(x\_\{i\},z\_\{s\}\)\\end\{bmatrix\}^\{T\}\\in\\mathbb\{R\}^\{s\}

return

π2​d\\sqrt\{\\frac\{\\pi\}\{2d\}\}sign

\(Pnys​C\(i\)\)\\left\(P\_\{\\text\{nys\}\}C^\{\(i\)\}\\right\)

The rows ofPrp∈ℝd×sP\_\{\\text\{rp\}\}\\in\\mathbb\{R\}^\{d\\times s\}are sampled from the uniform distribution over thess\-dimensional unit sphere\. This enables the following result regarding sign\-thresholded random projection: supposev,v′∈ℝnv,v^\{\\prime\}\\in\\mathbb\{R\}^\{n\}are unit vectors, with respect to randomness in the sampling ofPrpP\_\{\\text\{rp\}\}, the following result holds with randomness in the sampling ofPrpP\_\{\\text\{rp\}\}\(see for instance\(Charikar[2002](https://arxiv.org/html/2608.06860#bib.bib57)\)\):

𝔼​\[1d​sign​\(Prp​v\)⋅sign​\(Prp​v′\)\]=\(1−2​cos−1⁡\(v⋅v′\)/π\)\\begin\{split\}&\\mathbb\{E\}\\left\[\\frac\{1\}\{d\}\\text\{sign\}\(P\_\{\\text\{rp\}\}v\)\\cdot\\text\{sign\}\(P\_\{\\text\{rp\}\}v^\{\\prime\}\)\\right\]=\(1\-2\\cos^\{\-1\}\(v\\cdot v^\{\\prime\}\)/\\pi\)\\end\{split\}\(3\)NysHD generates encodings for which the similarity induced by the kernelKKis preserved by dot product between the encodings inℋ\\mathcal\{H\}\. We summarize this result in the following theorem:

###### Theorem 1\.

LetKKbe a positive\-definite kernel and, using the notation of Algorithms[1](https://arxiv.org/html/2608.06860#alg1)and[2](https://arxiv.org/html/2608.06860#alg2), and recalling thatϕnys​\(xi\)=Λ−12​QT​C\(i\)\\phi\_\{\\text\{nys\}\}\(x\_\{i\}\)=\\Lambda^\{\-\\frac\{1\}\{2\}\}Q^\{T\}C^\{\(i\)\}, define:

ϕ​\(xi\)=π2​d​sign​\(Prp​ϕnys​\(xi\)\)\\phi\(x\_\{i\}\)=\\sqrt\{\\frac\{\\pi\}\{2d\}\}\\text\{sign\}\(P\_\{\\text\{rp\}\}\\phi\_\{\\text\{nys\}\}\(x\_\{i\}\)\)Then, for allxi,xj∈𝒟x\_\{i\},x\_\{j\}\\in\\mathcal\{D\}:

𝔼​\[ϕ​\(xi\)⋅ϕ​\(xj\)\]=π2−cos−1⁡\(G^i​jG^i​i​G^j​j\)\\mathbb\{E\}\\left\[\\phi\\left\(x\_\{i\}\\right\)\\cdot\\phi\\left\(x\_\{j\}\\right\)\\right\]=\\frac\{\\pi\}\{2\}\-\\cos^\{\-1\}\\left\(\\frac\{\\hat\{G\}\_\{ij\}\}\{\\sqrt\{\\hat\{G\}\_\{ii\}\\hat\{G\}\_\{jj\}\}\}\\right\)\(4\)WhereG^i​j\\hat\{G\}\_\{ij\}is estimated kernel value betweenxix\_\{i\}andxjx\_\{j\}produced by Nyström method\. The expectation is taken with respect to randomness in the sampling of landmarks andPrpP\_\{\\text\{rp\}\}\.

Proof:Letϕ¯nys​\(xi\)\\bar\{\\phi\}\_\{\\text\{nys\}\}\(x\_\{i\}\)denote normalization:ϕnys​\(xi\)‖ϕnys​\(xi\)‖\\frac\{\\phi\_\{\\text\{nys\}\}\(x\_\{i\}\)\}\{\|\|\\phi\_\{\\text\{nys\}\}\(x\_\{i\}\)\|\|\}\. Noting thatsign​\(c​v\)=sign​\(v\)\\text\{sign\}\(cv\)=\\text\{sign\}\(v\)for anyvvifc≥0c\\geq 0:

ϕ​\(xi\)⋅ϕ​\(xj\)=π2​d​\(sign​\(Prp​ϕnys​\(xi\)\)⋅sign​\(Prp​ϕnys​\(xj\)\)\)=π2​\(1d​sign​\(Prp​ϕ¯nys​\(xi\)\)⋅sign​\(Prp​ϕ¯nys​\(xj\)\)\)\\begin\{split\}&\\phi\\left\(x\_\{i\}\\right\)\\cdot\\phi\\left\(x\_\{j\}\\right\)\\\\ &=\\frac\{\\pi\}\{2d\}\\left\(\\text\{sign\}\\left\(P\_\{\\text\{rp\}\}\\phi\_\{\\text\{nys \}\}\\left\(x\_\{i\}\\right\)\\right\)\\cdot\\text\{sign\}\\left\(P\_\{\\text\{rp\}\}\\phi\_\{\\text\{nys \}\}\(x\_\{j\}\)\\right\)\\right\)\\\\ &=\\frac\{\\pi\}\{2\}\\left\(\\frac\{1\}\{d\}\\text\{sign\}\\left\(P\_\{\\text\{rp\}\}\\bar\{\\phi\}\_\{\\text\{nys\}\}\(x\_\{i\}\)\\right\)\\cdot\\text\{sign\}\\left\(P\_\{\\text\{rp\}\}\\bar\{\\phi\}\_\{\\text\{nys\}\}\(x\_\{j\}\)\\right\)\\right\)\\\\ \\end\{split\}\(5\)Using result regarding sign\-thresholded random projection in equation[3](https://arxiv.org/html/2608.06860#Sx3.E3), we have:

𝔼​\[ϕ​\(xi\)⋅ϕ​\(xj\)\]=π2​\(1−2​cos−1⁡\(ϕ¯nys​\(xi\)⋅ϕ¯nys​\(xj\)\)π\)\\begin\{split\}&\\mathbb\{E\}\\left\[\\phi\(x\_\{i\}\)\\cdot\\phi\(x\_\{j\}\)\\right\]\\\\ &=\\frac\{\\pi\}\{2\}\\left\(1\-\\frac\{2\\cos^\{\-1\}\\left\(\{\\bar\{\\phi\}\_\{\\text\{nys\}\}\(x\_\{i\}\)\}\\cdot\\bar\{\\phi\}\_\{\\text\{nys\}\}\(x\_\{j\}\)\\right\)\}\{\\pi\}\\right\)\\\\ \\end\{split\}\(6\)Recalling the Nyström method in equationLABEL:nys\_approxand the fact that‖ϕnys​\(xi\)‖=ϕnys​\(xi\)⋅ϕnys​\(xi\)=G^i​i\|\|\{\\phi\_\{\\text\{nys\}\}\(x\_\{i\}\)\}\|\|=\\sqrt\{\{\\phi\_\{\\text\{nys\}\}\(x\_\{i\}\)\}\\cdot\{\\phi\_\{\\text\{nys\}\}\(x\_\{i\}\)\}\}=\\sqrt\{\\hat\{G\}\_\{ii\}\}:

ϕ¯nys​\(xi\)⋅ϕ¯nys​\(xj\)=G^i​jG^i​i​G^j​j\\begin\{split\}\\bar\{\\phi\}\_\{\\text\{nys\}\}\(x\_\{i\}\)\\cdot\\bar\{\\phi\}\_\{\\text\{nys\}\}\(x\_\{j\}\)=\\frac\{\\hat\{G\}\_\{ij\}\}\{\\sqrt\{\\hat\{G\}\_\{ii\}\\hat\{G\}\_\{jj\}\}\}\\end\{split\}\(7\)Finally:

𝔼​\[ϕ​\(xi\)⋅ϕ​\(xj\)\]=π2−cos−1⁡\(G^i​jG^i​i​G^j​j\)​■\\begin\{split\}\\mathbb\{E\}\\left\[\\phi\(x\_\{i\}\)\\cdot\\phi\(x\_\{j\}\)\\right\]&=\\frac\{\\pi\}\{2\}\-\\cos^\{\-1\}\\left\(\\frac\{\\hat\{G\}\_\{ij\}\}\{\\sqrt\{\\hat\{G\}\_\{ii\}\\hat\{G\}\_\{jj\}\}\}\\right\)\\blacksquare\\end\{split\}\(8\)
To make the relationship with kernel approximation more explicit, consider the first order Taylor expansion ofcos−1\\cos^\{\-1\}\. Since‖ϕ¯nys​\(xi\)‖=‖ϕ¯nys​\(xj\)‖=1\|\|\\bar\{\\phi\}\_\{\\text\{nys\}\}\(x\_\{i\}\)\|\|=\|\|\\bar\{\\phi\}\_\{\\text\{nys\}\}\(x\_\{j\}\)\|\|=1, it follows that−1≤ϕ¯nys​\(xi\)⋅ϕ¯nys​\(xj\)≤1\-1\\leq\{\\bar\{\\phi\}\_\{\\text\{nys\}\}\(x\_\{i\}\)\}\\cdot\\bar\{\\phi\}\_\{\\text\{nys\}\}\(x\_\{j\}\)\\leq 1, which meansG^i​jG^i​i​G^j​j\\frac\{\\hat\{G\}\_\{ij\}\}\{\\sqrt\{\\hat\{G\}\_\{ii\}\\hat\{G\}\_\{jj\}\}\}is within the domain ofcos−1\\cos^\{\-1\}, So:

𝔼​\[ϕ​\(xi\)⋅ϕ​\(xj\)\]≈π2−\(π2−G^i​jG^i​i​G^j​j\)=G^i​jG^i​i​G^j​j\\begin\{split\}\\mathbb\{E\}\\left\[\\phi\(x\_\{i\}\)\\cdot\\phi\(x\_\{j\}\)\\right\]&\\approx\\frac\{\\pi\}\{2\}\-\\left\(\\frac\{\\pi\}\{2\}\-\\frac\{\\hat\{G\}\_\{ij\}\}\{\\sqrt\{\\hat\{G\}\_\{ii\}\\hat\{G\}\_\{jj\}\}\}\\right\)\\\\ &=\\frac\{\\hat\{G\}\_\{ij\}\}\{\\sqrt\{\\hat\{G\}\_\{ii\}\\hat\{G\}\_\{jj\}\}\}\\end\{split\}\(9\)
Note that this is called normalized kernel\(Ah\-Pine[2010](https://arxiv.org/html/2608.06860#bib.bib80)\)\. As shown above, NysHD preserves the kernel inℋ\\mathcal\{H\}\(up to the first order approximation\) in the sense that the inner product between any pair of encoded data points approximates the normalized kernel value of some user\-defined kernelKK\. Since HDC relies on the inner product inℋ\\mathcal\{H\}for inference, as described in Section “Learning with HD”[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1), the similarity metric captured by the kernelKKis preserved, which benefits subsequent HDC learning algorithms\.

### Encoding Complexity

The proposed encoding method differs from existing HDC methods because generating embeddings using the Nyström method requires computing a partial kernel matrix\. For this reason, similar to kernel machines, the efficiency of our algorithm depends heavily on the number of kernel computations, which is related to the size of landmarks setss\.

In this section, we provide an asymptotic runtime analysis of the encoding algorithm\. Assuming that evaluating the kernel functionKKtakes𝒪​\(m\)\\mathcal\{O\}\(m\), that is to say the complexity of kernel function is linear in the dimension of the input \(e\.g\., the Gaussian kernel\) \- the complexity of running the encoding algorithm over a dataset ofnnsamples withsslandmarks todddimensional embedding isO​\(max⁡\(s3,s​n​m,s​n​d\)\)O\(\\max\{\(s^\{3\},snm,snd\)\}\)\. The first term corresponds to the symmetric eigen\-decomposition of the matrixH𝒵H\_\{\\mathcal\{Z\}\}, the second term reflects the number of kernel evaluations, and the last term represents the sign\-thresholded random projection, as discussed previously\. In a typical Nyström kernel approximation setting wheres≪ns\\ll n, depending on the nature of the kernel function being used, the second term is likely to be the dominant term, which is why the choice ofssandKKis crucial\. Moreover, the analysis we provided here assumes the complexity of the kernel is linear in the number of features \(for example, the Gaussian kernel\); however, this is not always the case for kernel functions\. For example, the spectrum kernel\(Leslieet al\.[2001](https://arxiv.org/html/2608.06860#bib.bib18)\), which compares theNN\-gram composition between two input strings, has𝒪​\(m​log⁡\(m\)\)\\mathcal\{O\}\(m\\log\(m\)\)in the length of the input sequences\.

## Evaluation

We conduct an empirical evaluation of NysHD\. First, we validate[1](https://arxiv.org/html/2608.06860#Thmtheorem1)and then evaluate the practicality of our method in terms of accuracy and efficiency against both HDC and non\-HDC baselines\.

### Datasets and Kernel Functions

Taskdataset\# training\# testing\# classDescriptionGraphENZYMES\(Borgwardtet al\.[2005](https://arxiv.org/html/2608.06860#bib.bib31)\)4801206Graph with attributed nodesNCI1\(Waleet al\.[2008](https://arxiv.org/html/2608.06860#bib.bib30)\)32888222Graph with labeled nodesD&D\(Dobson and Doig[2003](https://arxiv.org/html/2608.06860#bib.bib63)\)9432352Graph with labeled nodesBZR\(Sutherlandet al\.[2003](https://arxiv.org/html/2608.06860#bib.bib64)\)324812Graph with attributed nodesMUTAG\(Debnathet al\.[1991](https://arxiv.org/html/2608.06860#bib.bib65)\)150382Graph with labeled nodesCOX2\(Sutherlandet al\.[2003](https://arxiv.org/html/2608.06860#bib.bib64)\)373942Graph with attributed nodesNCI109\(Waleet al\.[2008](https://arxiv.org/html/2608.06860#bib.bib30)\)33018262Graph with labeled nodesMutagenicity\(Riesen and Bunke[2008](https://arxiv.org/html/2608.06860#bib.bib67)\)34698682Graph with labeled nodesStringProtein\(Selvarajet al\.[2023](https://arxiv.org/html/2608.06860#bib.bib29)\)7211816Protein sequenceSMS\(Almeida,Tiago and Hidalgo,Jos[2012](https://arxiv.org/html/2608.06860#bib.bib28)\)445911152Nautral LanguageSplice\(Towellet al\.[1992](https://arxiv.org/html/2608.06860#bib.bib81)\)25526283DNA sequencePromoter\(Harleyet al\.[1990](https://arxiv.org/html/2608.06860#bib.bib62)\)84222DNA sequenceTable 1:Summary of tasks and datasetsThe proposed encoding method is general\-purpose and applicable to various data and tasks, provided a suitable kernel function is available\. To confirm its versatility, we conduct assessments across two distinct tasks:GraphsandStringsclassification\. In total, we have chosen 8 graph datasets from TUDataset\(Morriset al\.[2020](https://arxiv.org/html/2608.06860#bib.bib77)\), a well\-known standardized repository for graph classification benchmarking datasets, and 4 string datasets for bio\-sequence and text classification\. More information on datasets can be found in Table\.[1](https://arxiv.org/html/2608.06860#Sx4.T1)\.

The main advantage of our method is that it generates embeddings for HDC learning algorithms that preserve any user\-defined positive\-semidefinite kernel function\. As such, the choice of kernel function is crucial for achieving the best accuracy and efficiency\. For our method, we use the gappy kernel\(Leslieet al\.[2004](https://arxiv.org/html/2608.06860#bib.bib71)\)for string classification\. The gappy kernel is a variant of the spectrum kernel\(Leslieet al\.[2001](https://arxiv.org/html/2608.06860#bib.bib18)\)that allows a small amount of gap within theNN\-grams\. The propagation kernel\(Neumannet al\.[2016](https://arxiv.org/html/2608.06860#bib.bib17)\)is used for graph classification for its ability to work with labeled or attributed graphs, as discussed in the section “kernel methods”[Kernel Methods](https://arxiv.org/html/2608.06860#Sx2.SSx2)\. We chose the aforementioned kernels for their relatively low computation complexity and effectiveness on respective tasks\.

### Experimental Setup and Baselines

We benchmark our method against the existing HDC encoding baselines within each domain:Graph classificationusing the encoding scheme from introduced in GraphHD\(Nuneset al\.[2022](https://arxiv.org/html/2608.06860#bib.bib26)\)andString classificationusesNN\-gram HDC encoding approach\(Joshiet al\.[2017](https://arxiv.org/html/2608.06860#bib.bib42)\)\. The details of both HDC encoding methods are discussed in the background section\.

In addition to HDC\-baselines, we also include comparisons with popular state\-of\-the\-art deep neural network architectures\. For graph classification, we useDGCNN\(Zhanget al\.[2018](https://arxiv.org/html/2608.06860#bib.bib68)\),GCN\(Chenet al\.[2019](https://arxiv.org/html/2608.06860#bib.bib55)\),GIN\(Xuet al\.[2018](https://arxiv.org/html/2608.06860#bib.bib69)\),GIUNet\(Amouzadet al\.[2024](https://arxiv.org/html/2608.06860#bib.bib70)\)\. On string datasets, following the recent trend of applying large models for bio\-sequence and language modeling\(Qiuet al\.[2020](https://arxiv.org/html/2608.06860#bib.bib74); Raffelet al\.[2020](https://arxiv.org/html/2608.06860#bib.bib75)\), we fine\-tune Large protein model \(ESM\-2\-8m\(Riveset al\.[2021](https://arxiv.org/html/2608.06860#bib.bib72)\)\) for for bio\-sequence datasets, and large language model \(BERT\(Devlinet al\.[2018](https://arxiv.org/html/2608.06860#bib.bib73)\)\) for natural language dataset\.

For our method, we set the number of landmarks:ss=m​a​xmax\(300, 2% of training data\) on each dataset, and kernel specific hyperparamters are chosen empirically\. To ensure the fairness of comparison, we use an identical HDC learning pipeline adapted from OnlineHD\(Hernández\-Canoet al\.[2021](https://arxiv.org/html/2608.06860#bib.bib25)\)when evaluating different HDC encoding methods\. The Perceptron algorithm\(Rosenblatt[1958](https://arxiv.org/html/2608.06860#bib.bib48)\)is used to fine\-tune class prototypes\. In all of our experiments, 20 epochs of fine\-tuning have been found to be sufficient\.

All experiments were run on an Intel i5\-11400 CPU \(except for large models fine\-tuning, which required an Nvidia RTX 3050 GPU is used due to long training time on CPU\)\. We evaluate different methods by their training efficiency \(time in seconds\) and classification accuracy\. Each experiment was run 10 times, and we report the mean and standard deviation of the results\.

### Approximating Normalized Kernel Matrix

![Refer to caption](https://arxiv.org/html/2608.06860v1/figs/spectral_norm.png)Figure 2:Numerical difference of spectral norm between normalized kernel matrices compute directly from kernel function and approximated kernel matrices with our encoding\.The classification accuracy of HDC\-based models hinges on the capability of encodings to capture some salient notion of similarity via inner product\. A straightforward way to verify our encodings preserve the kernel is to compare the spectral norm of the normalized kernel matrix \(computed using the kernel function\) with the pairwise inner products of the encodings\. Using different percentages of the training samples as landmarks, the results for selected datasets \(ENZYMES, NCI1, Protein, Promoter\) are shown in Fig\.[2](https://arxiv.org/html/2608.06860#Sx4.F2)\. In line with Theorem[1](https://arxiv.org/html/2608.06860#Thmtheorem1), our method preserves the normalized kernel value, whose quality is positively correlated with the number of landmarks \(a less noisy approximation can be achieved with a larger number of landmarks\)\. The results here indicate that our method is effective in transferring similarity functions in kernel methods to HDC settings\.

### Accuracy and Efficiency Results

Table 2:Experimental results\. The best accuracy result for each dataset arehightedand second best areunderlined\.Table 3:Accuracy and training time on string datasetsThe accuracy results for graph and string datasets are summarized in Table[2](https://arxiv.org/html/2608.06860#Sx4.T2)and Table[3](https://arxiv.org/html/2608.06860#Sx4.T3)\. In comparison with the GraphHD, NysHD achieves, on average, 11% better accuracy on graph datasets\. The improvement is especially significant on the ENZYMES dataset, which shows a 38% accuracy improvement\. This is because the previous HDC encoding method on graph\(Nuneset al\.[2022](https://arxiv.org/html/2608.06860#bib.bib26)\)could not utilize node attributes in attributed graphs, whereas our method can\. On string datasets, our method again consistently achieves better accuracy compared toNN\-gram based HDC encoding, with an average improvement of 17%\. Efficiency\-wise, our method is comparable to previous HDC encoding methods, although it is slightly slower than GraphHD\(Nuneset al\.[2022](https://arxiv.org/html/2608.06860#bib.bib26)\)on graph datasets due to kernel computation\.

Despite the efficiency and implementation simplicity of HDC learning algorithms, there remains an accuracy gap between HDC\-based models and deep neural network \(DNN\) models for more complex classification tasks\. We hope this work will help reduce that gap\. To that end, we also include several state\-of\-the\-art DNN approaches on both graph and string classification in our comparison\. On graph datasets, NysHD achieved the best accuracy in 3 out of 8 graph datasets\. On average, NysHD outperforms DGCNN by 3%, GIN and GIUNet by 6% for graph classification\. Although graph convolutional network \(GCN\) still yield the best accuracy for some datasets, our method is on average 52% faster than GCN\. On string datasets, our method with the gappy kernel achieves better accuracy on 2 out of 3 bio\-sequence datasets\. For SMS and Splice dataset, the LM fine\-tune method achieves better classification accuracy, but their training time is 6 to 83 times longer than our method\.

Overall, the strength of NysHD becomes most apparent when dealing with data with complex structures or attributes that existing HDC encoding methods do not exploit\.

## Overhead & Scalability

This work allows future HDC works to exploit the power of kernel methods while still conforming to the general formalism and benefits of HDC\. We recognize that the improvements in NysHD also come with additional computation costs in the form of kernel evaluation\. How to minimize such cost for HDC applications are non\-trivial problems that need further investigations\. The main scalability challenge is to obtain a set of landmarks that is as small as possible, while still providing a good approximation to the true kernel matrix\. There is a large body of work on more sophisticated sampling schemes for the Nyström method that could help make our methods scalable to larger datasets\(Kumaret al\.[2012](https://arxiv.org/html/2608.06860#bib.bib36); Musco and Musco[2017](https://arxiv.org/html/2608.06860#bib.bib58)\)\. We would be interested in studying these in future work\.

## Conclusion

The success of HDC\-based learning methods is contingent upon identifying an encoding function that preserves a suitable notion of similarity \(kernel\) for the task at hand\. In this paper, we leverage the connection between the kernel method and HDC through the lens of Nyström method for kernel estimation\. Particularly, we propose NysHD, a new HDC encoding method that constructs encoding functions using suitable kernel functions for specific tasks\. As a result, compared with previous HDC encoding methods, NysHD achieves substantial improvements \- on average, 11% accuracy improvement on graph datasets and 17% on string datasets\. There are many situations in which methods from the kernel literature outperform existing HDC\-based solutions, therefore, our approach can be expected to lead to performance improvements in many HDC applications\.

## Acknowledgements

This work was supported in part by National Science Foundation under Grants \#2003279, \#1826967, \#2100237, \#2112167, \#1911095, \#2112665, and in part by SRC under task \#3021\.001\. This work was also supported in part by PRISM and CoCoSys, centers in JUMP 2\.0, an SRC program sponsored by DARPA\.

## References

- J\. Ah\-Pine \(2010\)Normalized kernels as similarity indices\.InPAKDD 2010, Hyderabad, India, June 21\-24, 2010\. Proceedings\. Part II 14,pp\. 362–373\.Cited by:[Encoding Process](https://arxiv.org/html/2608.06860#Sx3.SSx2.p5.4)\.
- Almeida,Tiago and Hidalgo,Jos \(2012\)SMS Spam Collection\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5CC84Cited by:[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.11.11.2)\.
- A\. Amouzad, Z\. Dehghanian, S\. Saravani, M\. Amirmazlaghani, and B\. Roshanfekr \(2024\)Graph isomorphism u\-net\.Expert Systems with Applications236,pp\. 121280\.Cited by:[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p2.1)\.
- F\. Asgarinejad, A\. Thomas, and T\. Rosing \(2020\)Detection of epileptic seizures from surface eeg using hyperdimensional computing\.InEMBC,pp\. 536–540\.Cited by:[Kernel Methods and HDC](https://arxiv.org/html/2608.06860#Sx2.SSx3.p1.1)\.
- K\. M\. Borgwardt, C\. S\. Ong, S\. Schönauer, S\. Vishwanathan, A\. J\. Smola, and H\. Kriegel \(2005\)Protein function prediction via graph kernels\.Bioinformatics21\.Cited by:[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.2.2.2)\.
- S\. Brin and L\. Page \(1998\)The anatomy of a large\-scale hypertextual web search engine\.Computer networks and ISDN systems30\(1\-7\),pp\. 107–117\.Cited by:[Kernel Methods and HDC](https://arxiv.org/html/2608.06860#Sx2.SSx3.p2.1)\.
- M\. S\. Charikar \(2002\)Similarity estimation techniques from rounding algorithms\.InProceedings of the thiry\-fourth annual ACM symposium on Theory of computing,pp\. 380–388\.Cited by:[Encoding Process](https://arxiv.org/html/2608.06860#Sx3.SSx2.p1.1),[Encoding Process](https://arxiv.org/html/2608.06860#Sx3.SSx2.p2.5)\.
- T\. Chen, S\. Bian, and Y\. Sun \(2019\)Are powerful graph neural nets necessary? a dissection on graph classification\.arXiv preprint arXiv:1905\.04579\.Cited by:[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p2.1)\.
- A\. K\. Debnath, R\. L\. Lopez de Compadre, G\. Debnath, A\. J\. Shusterman, and C\. Hansch \(1991\)Structure\-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds\. correlation with molecular orbital energies and hydrophobicity\.Journal of medicinal chemistry34\(2\),pp\. 786–797\.Cited by:[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.6.6.2)\.
- J\. Devlin, M\. Chang, K\. Lee, and K\. Toutanova \(2018\)Bert: pre\-training of deep bidirectional transformers for language understanding\.arXiv preprint arXiv:1810\.04805\.Cited by:[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p2.1)\.
- P\. D\. Dobson and A\. J\. Doig \(2003\)Distinguishing enzyme structures from non\-enzymes without alignments\.Journal of molecular biology330\(4\),pp\. 771–783\.Cited by:[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.4.4.2)\.
- P\. Drineas, M\. W\. Mahoney, and N\. Cristianini \(2005\)On the nyström method for approximating a gram matrix for improved kernel\-based learning\.\.JMLR6\(12\)\.Cited by:[Nyström Method](https://arxiv.org/html/2608.06860#Sx3.SSx1.p1.3),[Nyström Method](https://arxiv.org/html/2608.06860#Sx3.SSx1.p2.7)\.
- A\. Dutta, S\. Gupta, B\. Khaleghi, R\. Chandrasekaran, W\. Xu, and T\. Rosing \(2022\)Hdnn\-pim: efficient in memory design of hyperdimensional computing with feature extraction\.InGLSVLSI,pp\. 281–286\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p2.1)\.
- S\. Gudmundsson, T\. P\. Runarsson, and S\. Sigurdsson \(2008\)Support vector machines and dynamic time warping for time series\.In2008 IEEE International Joint Conference on Neural Networks,pp\. 2772–2776\.Cited by:[Kernel Methods and HDC](https://arxiv.org/html/2608.06860#Sx2.SSx3.p1.1)\.
- C\. Harley, R\. Reynolds, and M\. Noordewier \(1990\)Molecular Biology \(Promoter Gene Sequences\)\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5S01DCited by:[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.13.13.2)\.
- Z\. S\. Harris \(1954\)Distributional structure\.Word10\(2\-3\),pp\. 146–162\.Cited by:[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p3.4)\.
- A\. Hernández\-Cano, N\. Matsumoto, E\. Ping, and M\. Imani \(2021\)Onlinehd: robust, efficient, and single\-pass online learning using hyperdimensional system\.InDATE,pp\. 56–61\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p2.1),[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p3.2)\.
- J\. A\. Hertz \(2018\)Introduction to the theory of neural computation\.Crc Press\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p1.1)\.
- T\. Hofmann, B\. Schölkopf, and A\. J\. Smola \(2008\)Kernel methods in machine learning\.Cited by:[Kernel Methods](https://arxiv.org/html/2608.06860#Sx2.SSx2.p1.8)\.
- M\. Imani, J\. Morris, J\. Messerly, H\. Shu, Y\. Deng, and T\. Rosing \(2019\)Bric: locality\-based encoding for energy\-efficient brain\-inspired hyperdimensional computing\.InDAC,pp\. 1–6\.Cited by:[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p1.15)\.
- M\. Imani, T\. Nassar, A\. Rahimi, and T\. Rosing \(2018\)Hdna: energy\-efficient dna sequencing using hyperdimensional computing\.InBHI,pp\. 271–274\.Cited by:[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p2.19)\.
- M\. Imani, S\. Pampana, S\. Gupta, M\. Zhou, Y\. Kim, and T\. Rosing \(2020\)Dual: acceleration of clustering algorithms using digital\-based processing in\-memory\.InMICRO,pp\. 356–371\.Cited by:[Related Work](https://arxiv.org/html/2608.06860#Sx2.SSx4.p1.3)\.
- A\. Joshi, J\. T\. Halseth, and P\. Kanerva \(2017\)Language geometry using random indexing\.InQuantum Interaction: 10th International Conference, QI 2016, San Francisco, CA, USA, July 20\-22, 2016, Revised Selected Papers 10,pp\. 265–274\.Cited by:[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p2.19),[Kernel Methods and HDC](https://arxiv.org/html/2608.06860#Sx2.SSx3.p1.1),[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p1.1)\.
- P\. Kanerva \(2009\)Hyperdimensional computing: an introduction to computing in distributed representation with high\-dimensional random vectors\.Cognitive computation1,pp\. 139–159\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p1.1)\.
- J\. Kang, B\. Khaleghi, Y\. Kim, and T\. Rosing \(2022a\)Xcelhd: an efficient gpu\-powered hyperdimensional computing with parallelized training\.InASP\-DAC,pp\. 220–225\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p2.1)\.
- J\. Kang, B\. Khaleghi, T\. Rosing, and Y\. Kim \(2022b\)Openhd: a gpu\-powered framework for hyperdimensional computing\.IEEE Transactions on Computers71\(11\),pp\.\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p2.1)\.
- B\. Khaleghi, J\. Kang, H\. Xu, J\. Morris, and T\. Rosing \(2022\)GENERIC: highly efficient learning engine on edge using hyperdimensional computing\.InDAC,pp\. 1117–1122\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p2.1),[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p3.4),[Nyström Method](https://arxiv.org/html/2608.06860#Sx3.SSx1.p2.21)\.
- D\. Kleyko, D\. Rachkovskij, E\. Osipov, and A\. Rahimi \(2023\)A survey on hyperdimensional computing aka vector symbolic architectures, part ii: applications, cognitive models, and challenges\.ACM Computing Surveys55\(9\),pp\. 1–52\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p3.3)\.
- S\. Kumar, M\. Mohri, and A\. Talwalkar \(2012\)Sampling methods for the nyström method\.JMLR13\(1\),pp\. 981–1006\.Cited by:[Nyström Method](https://arxiv.org/html/2608.06860#Sx3.SSx1.p1.3),[Nyström Method](https://arxiv.org/html/2608.06860#Sx3.SSx1.p2.16),[Nyström Method](https://arxiv.org/html/2608.06860#Sx3.SSx1.p3.1),[Overhead & Scalability](https://arxiv.org/html/2608.06860#Sx5.p1.1)\.
- C\. Leslie, E\. Eskin, and W\. S\. Noble \(2001\)The spectrum kernel: a string kernel for svm protein classification\.InBiocomputing 2002,pp\. 564–575\.Cited by:[Kernel Methods and HDC](https://arxiv.org/html/2608.06860#Sx2.SSx3.p1.1),[Encoding Complexity](https://arxiv.org/html/2608.06860#Sx3.SSx3.p2.12),[Datasets and Kernel Functions](https://arxiv.org/html/2608.06860#Sx4.SSx1.p2.1)\.
- C\. Leslie, R\. Kuang, and K\. Bennett \(2004\)Fast string kernels using inexact matching for protein sequences\.\.JMLR5\(9\)\.Cited by:[Datasets and Kernel Functions](https://arxiv.org/html/2608.06860#Sx4.SSx1.p2.1)\.
- G\. Meanti, L\. Carratino, L\. Rosasco, and A\. Rudi \(2020\)Kernel methods through the roof: handling billions of points efficiently\.NeurIPS33,pp\. 14410–14422\.Cited by:[Kernel Methods](https://arxiv.org/html/2608.06860#Sx2.SSx2.p1.8)\.
- A\. Menon, D\. Sun, S\. Sabouri, K\. Lee, M\. Aristio, H\. Liew, and J\. M\. Rabaey \(2022\)A highly energy\-efficient hyperdimensional computing processor for biosignal classification\.TBCAS\.Cited by:[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p1.15)\.
- V\. Miranda and O\. d’Aliberti \(2022\)Hyperdimensional computing encoding schemes for improved image classification\.InHST,pp\. 1–9\.Cited by:[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p1.15),[Related Work](https://arxiv.org/html/2608.06860#Sx2.SSx4.p1.3)\.
- C\. Morris, N\. M\. Kriege, F\. Bause, K\. Kersting, P\. Mutzel, and M\. Neumann \(2020\)Tudataset: a collection of benchmark datasets for learning with graphs\.arXiv preprint arXiv:2007\.08663\.Cited by:[Datasets and Kernel Functions](https://arxiv.org/html/2608.06860#Sx4.SSx1.p1.1)\.
- J\. Morris, K\. Ergun, B\. Khaleghi, M\. Imani, B\. Aksanli, and T\. Rosing \(2021\)Hydrea: towards more robust and efficient machine learning systems with hyperdimensional computing\.InDATE,pp\. 723–728\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p2.1),[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p1.15),[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p3.4)\.
- C\. Musco and C\. Musco \(2017\)Recursive sampling for the nystrom method\.NeurIPS30\.Cited by:[Overhead & Scalability](https://arxiv.org/html/2608.06860#Sx5.p1.1)\.
- M\. Neumann, R\. Garnett, C\. Bauckhage, and K\. Kersting \(2016\)Propagation kernels: efficient graph kernels from propagated information\.Machine learning102,pp\. 209–245\.Cited by:[Kernel Methods and HDC](https://arxiv.org/html/2608.06860#Sx2.SSx3.p1.1),[Kernel Methods and HDC](https://arxiv.org/html/2608.06860#Sx2.SSx3.p2.1),[Datasets and Kernel Functions](https://arxiv.org/html/2608.06860#Sx4.SSx1.p2.1)\.
- I\. Nunes, M\. Heddes, T\. Givargis, A\. Nicolau, and A\. Veidenbaum \(2022\)GraphHD: efficient graph classification using hyperdimensional computing\.InDATE,pp\. 1485–1490\.Cited by:[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p1.15),[Kernel Methods and HDC](https://arxiv.org/html/2608.06860#Sx2.SSx3.p2.1),[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p1.1),[Accuracy and Efficiency Results](https://arxiv.org/html/2608.06860#Sx4.SSx4.p1.1)\.
- E\. Paxon Frady, D\. Kleyko, C\. J\. Kymn, B\. A\. Olshausen, and F\. T\. Sommer \(2021\)Computing on functions using randomized vector representations\.,pp\. arXiv–2109\.Cited by:[Related Work](https://arxiv.org/html/2608.06860#Sx2.SSx4.p1.3)\.
- T\. A\. Plate \(1995\)Holographic reduced representations\.IEEE Transactions on Neural networks6\(3\),pp\. 623–641\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p1.1)\.
- X\. Qiu, T\. Sun, Y\. Xu, Y\. Shao, N\. Dai, and X\. Huang \(2020\)Pre\-trained models for natural language processing: a survey\.Science China technological sciences63\(10\),pp\. 1872–1897\.Cited by:[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p2.1)\.
- C\. Raffel, N\. Shazeer, A\. Roberts, K\. Lee, S\. Narang, M\. Matena, Y\. Zhou, W\. Li, and P\. J\. Liu \(2020\)Exploring the limits of transfer learning with a unified text\-to\-text transformer\.JMLR21\(140\),pp\. 1–67\.Cited by:[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p2.1)\.
- A\. Rahimi, P\. Kanerva, L\. Benini, and J\. M\. Rabaey \(2018\)Efficient biosignal processing using hyperdimensional computing: network templates for combined learning and classification of ExG signals\.Proceedings of the IEEE107\(1\),pp\. 123–143\.Cited by:[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p1.15)\.
- A\. Rahimi and B\. Recht \(2007\)Random features for large\-scale kernel machines\.NeurIPS20\.Cited by:[Related Work](https://arxiv.org/html/2608.06860#Sx2.SSx4.p1.3)\.
- K\. Riesen and H\. Bunke \(2008\)IAM graph database repository for graph based pattern recognition and machine learning\.InSSPR & SPR 2008, Orlando, USA, December 4\-6, 2008\. Proceedings,pp\. 287–297\.Cited by:[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.9.9.2)\.
- A\. Rives, J\. Meier, T\. Sercu, S\. Goyal, Z\. Lin, J\. Liu, D\. Guo, M\. Ott, C\. L\. Zitnick, J\. Ma,et al\.\(2021\)Biological structure and function emerge from scaling unsupervised learning to 250 million protein sequences\.Proceedings of the National Academy of Sciences118\(15\),pp\. e2016239118\.Cited by:[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p2.1)\.
- F\. Rosenblatt \(1958\)The perceptron: a probabilistic model for information storage and organization in the brain\.\.Psychological review65\(6\),pp\. 386\.Cited by:[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p1.15),[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p3.2)\.
- S\. Salamat, M\. Imani, B\. Khaleghi, and T\. Rosing \(2019\)F5\-hd: fast flexible fpga\-based framework for refreshing hyperdimensional computing\.InProceedings of the 2019 ACM/SIGDA International Symposium on Field\-Programmable Gate Arrays,pp\. 53–62\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p2.1)\.
- M\. K\. Selvaraj, A\. Thakur, M\. Kumar, A\. K\. Pinnaka, C\. R\. Suri, B\. Siddhardha, and S\. P\. Elumalai \(2023\)Ion\-pumping microbial rhodopsin protein classification by machine learning approach\.BMC bioinformatics24\(1\),pp\. 29\.Cited by:[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.10.10.2)\.
- J\. Shawe\-Taylor and N\. Cristianini \(2004\)Kernel methods for pattern analysis\.Cambridge university press\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p5.1),[Kernel Methods](https://arxiv.org/html/2608.06860#Sx2.SSx2.p1.8),[Kernel Methods and HDC](https://arxiv.org/html/2608.06860#Sx2.SSx3.p1.1)\.
- H\. Shimodaira, K\. Noma, M\. Nakai, and S\. Sagayama \(2001\)Dynamic time\-alignment kernel in support vector machine\.NeurIPS14\.Cited by:[Kernel Methods and HDC](https://arxiv.org/html/2608.06860#Sx2.SSx3.p1.1)\.
- A\. J\. Smola and B\. Schölkopf \(1998\)Learning with kernels\.Vol\.4,Citeseer\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p5.1)\.
- I\. Steinwart \(2001\)On the influence of the kernel on the consistency of support vector machines\.JMLR2\(Nov\)\.Cited by:[Kernel Methods](https://arxiv.org/html/2608.06860#Sx2.SSx2.p2.5)\.
- J\. J\. Sutherland, L\. A\. O’brien, and D\. F\. Weaver \(2003\)Spline\-fitting with a genetic algorithm: a method for developing classification structure\- activity relationships\.Journal of chemical information and computer sciences43\(6\),pp\. 1906–1915\.Cited by:[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.5.5.2),[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.7.7.2)\.
- A\. Thomas, S\. Dasgupta, and T\. Rosing \(2021\)A theoretical perspective on hyperdimensional computing\.JAIR72,pp\. 215–249\.Cited by:[Learning With HDC](https://arxiv.org/html/2608.06860#Sx2.SSx1.p2.19),[Related Work](https://arxiv.org/html/2608.06860#Sx2.SSx4.p1.3)\.
- G\. Towell, M\. Noordewier, and J\. Shavlik \(1992\)Primate splice\-junction gene sequences \(dna\) with associated imperfect domain theory\.Cited by:[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.12.12.2)\.
- A\. R\. Voelker \(2020\)A short letter on the dot product between rotated fourier transforms\.arXiv preprint arXiv:2007\.13462\.Cited by:[Related Work](https://arxiv.org/html/2608.06860#Sx2.SSx4.p1.3)\.
- N\. Wale, I\. A\. Watson, and G\. Karypis \(2008\)Comparison of descriptor spaces for chemical compound retrieval and classification\.Knowledge and Information Systems14,pp\. 347–375\.Cited by:[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.3.3.2),[Table 1](https://arxiv.org/html/2608.06860#Sx4.T1.1.8.8.2)\.
- C\. Williams and M\. Seeger \(2000\)Using the nyström method to speed up kernel machines\.NeurIPS13\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p5.1),[Nyström Method](https://arxiv.org/html/2608.06860#Sx3.SSx1.p1.3),[Nyström Method](https://arxiv.org/html/2608.06860#Sx3.SSx1.p3.1)\.
- K\. Xu, W\. Hu, J\. Leskovec, and S\. Jegelka \(2018\)How powerful are graph neural networks?\.arXiv preprint arXiv:1810\.00826\.Cited by:[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p2.1)\.
- W\. Xu, J\. Kang, and T\. Rosing \(2023\)FSL\-hd: accelerating few\-shot learning on reram using hyperdimensional computing\.InDATE,pp\. 1–6\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p2.1)\.
- T\. Yu, Y\. Zhang, Z\. Zhang, and C\. D\. Sa \(2022\)Understanding hyperdimensional computing for parallel single\-pass learning\.InNeurIPS,A\. H\. Oh, A\. Agarwal, D\. Belgrave, and K\. Cho \(Eds\.\),External Links:[Link](https://openreview.net/forum?id=8ON84BdnSn)Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p2.1),[Related Work](https://arxiv.org/html/2608.06860#Sx2.SSx4.p1.3)\.
- M\. Zhang, Z\. Cui, M\. Neumann, and Y\. Chen \(2018\)An end\-to\-end deep learning architecture for graph classification\.InAAAI,Vol\.32\.Cited by:[Experimental Setup and Baselines](https://arxiv.org/html/2608.06860#Sx4.SSx2.p2.1)\.
- T\. Zhang, J\. Morris, K\. Stewart, H\. W\. Lui, B\. Khaleghi, A\. Thomas, T\. Goncalves\-Marback, B\. Aksanli, E\. O\. Neftci, and T\. Rosing \(2023\): Accelerating event\-based workloads with hyperdimensional computing and spiking neural networks\.TCAD\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p2.1)\.
- Q\. Zhao, K\. Lee, J\. Liu, M\. Huzaifa, X\. Yu, and T\. Rosing \(2022\)FedHD: federated learning with hyperdimensional computing\.InMobiCom,pp\. 791–793\.Cited by:[Introduction](https://arxiv.org/html/2608.06860#Sx1.p2.1)\.