Paper deep dive
Bridging the Gap Between Hyperdimensional Computing and Kernel Methods via the Nyström Method
Quanling Zhao, Anthony Hitchcock Thomas, Ari Brin, Xiaofan Yu, Tajana Rosing
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 89%
Last extracted: 8/10/2026, 3:26:19 AM
Summary
The paper introduces NysHD, a method for Hyperdimensional Computing (HDC) that utilizes the Nyström method to map user-defined positive-semidefinite kernel functions into high-dimensional random vector encodings. This approach bridges kernel methods and HDC, allowing the use of diverse similarity functions (e.g., graph and string kernels) within the HDC framework. Empirical results demonstrate that NysHD improves classification accuracy by 11% on graph datasets and 17% on string datasets compared to existing HDC encoding methods.
Entities (8)
Relation Signals (7)
NysHD → appliedto → Hyperdimensional Computing
confidence 95% · In this work, we propose NysHD, a new method for constructing this mapping... for HDC
NysHD → uses → Nyström Method
confidence 95% · we propose NysHD, a new method for constructing this mapping that is based on the Nyström method
NysHD → enables → Kernel Methods
confidence 90% · Our approach provides a mechanism to import them [kernel functions] into the HDC setting
NysHD → outperforms → Existing HDC encoding methods
confidence 90% · Empirical evaluation against existing HDC encoding methods shows that NysHD can achieve... better classification accuracy
NysHD → improvesaccuracyon → Graph Datasets
confidence 85% · 11%... better classification accuracy on graph datasets
NysHD → improvesaccuracyon → String Datasets
confidence 85% · 17%... better classification accuracy on... string datasets
Hyperdimensional Computing → implementedon → FPGAs
confidence 80% · easy to implement in energy-efficient and highly parallel hardware like FPGAs
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.06860v1
- Canonical: https://arxiv.org/abs/2608.06860v1
Trouble viewing inline? Open PDF directly →
Full Text
53,271 characters extracted from source content.
Expand or collapse full text
Bridging the Gap Between Hyperdimensional Computing and Kernel Methods via the Nyström Method Quanling Zhao, Anthony Hitchcock Thomas, Ari Brin, Xiaofan Yu, Tajana Rosing 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). Motivated by these desirable qualities, hyperdimensional computing (HDC) builds on theories of representation from cognitive science (Kanerva 2009; Plate 1995) 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-Cano et al. 2021; Yu et al. 2022) 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) (Khaleghi et al. 2022; Zhao et al. 2022; Morris et al. 2021); and in the computer hardware community (Dutta et al. 2022; Kang et al. 2022a) such as FPGAs (Salamat et al. 2019), GPUs (Kang et al. 2022b), ASICs (Zhang et al. 2023) and in-memory computing (Dutta et al. 2022; Xu et al. 2023). The first stage in any HDC task is encoding, which maps data from its ambient representation x∈x , into a representation ϕ(x)φ(x) residing in a high-dimensional inner product space ℋH (Kleyko et al. 2023). 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 X are mapped to “similar” regions of ℋH. In practice, this desideratum typically means that dot-products in ℋH should be reflective of some salient notion of similarity on 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; Smola and Schölkopf 1998). 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), 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 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 (Imani et al. 2019; Rahimi et al. 2018; Menon et al. 2022). Fig 1 demonstrates a typical HDC learning workflow for classification (Morris et al. 2021; Nunes et al. 2022; Miranda and d’Aliberti 2022). Let =(x1,y1),…,(xn,yn)D=\(x_1,y_1),...,(x_n,y_n)\ be a set of training data, where xi∈x_i∈X is an input, and yi∈1,…,cy_i∈\1,...,c\ is a class label. The first step is to embed the training data into a d-dimensional inner product space ℋH under a map (called the encoding function) ϕ:→ℋφ:X→H. The “training” step then associates each class with a vector in ℋH, which is typically formed by summing (bundling) the training data corresponding to a particular class. Specifically, class j is represented as θj=∑i=1nαijϕ(xi) _j= _i=1^n _ijφ(x_i) where αij=1(yi=j) _ij=1(y_i=j). In practice, θj _j is sometimes quantized to reduce precision in some fashion, which is beneficial in some hardware settings. The label of a query x is predicted by via y^=argmaxj∈1,…,cϕ(x)⋅θj y= *arg\,max_j∈\1,...,c\φ(x)· _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 ℋH and performing inference by picking the class of highest score - a common paradigm in machine learning. Fine-tuning the class vectors θj _j is common, often achieved by running the Perceptron algorithm (Rosenblatt 1958), 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 the N-gram encoding method (Joshi et al. 2017; Imani et al. 2018). Concretely, let S=(a1a2a3…aN)S=(a_1a_2a_3...a_N) be a string of N characters drawn from some alphabet A (say, the latin alphabet or A,T,G,C\ A,T,G,C\). To encode S, we start by assigning each a∈a∈A an embedding ϕ(a)φ(a) by sampling uniformly at random from ±1/dd\± 1/ d\^d, after which, we represent S as a1∘ρ(a2)∘ρ2(a3)∘⋯∘ρN−1(aN)a_1 ρ(a_2) ρ^2(a_3) … ρ^N-1(a_N) where ∘ is element-wise multiplication (Joshi et al. 2017) and ρ is a permutation operation of the vector coordinates, ρnρ^n means same permutation applied n times in sequence. If ∘ is multiplication, the way N-grams representations are constructed makes them almost mutually orthogonal in ℋH in the sense that [ϕ(S)⋅ϕ(S′)]=1(S=S′)E[φ(S)·φ(S )]=1(S=S ). The deviation from this expectation can be controlled using concentration arguments (Thomas et al. 2021). Finally, longer strings that contain multiple N-grams can be treated as a sum of N-gram vectors. This string encoding scheme can be viewed as a “compressed” version of the bag-of-words model (Harris 1954) in the sense that all N-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 common N-grams, and vice versa. For general feature vectors (or simple images), techniques based on random projection are popular (Morris et al. 2021; Khaleghi et al. 2022). 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; Meanti et al. 2020; Hofmann et al. 2008). 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 points x,x′∈x,x via a function K(x,x′)=ψ(x)⋅ψ(x′)K(x,x )=ψ(x)·ψ(x ), called a “kernel function,” where ψ:→ℋψ:X→H is an embedding into an inner product space. For many types of kernel functions used in practice, it is possible to compute K(x,x′)K(x,x ) directly on the ambient representation of the data without materializing the embeddings. Notable examples include the Gaussian kernel K(x,x′)∝exp(−‖x−x′‖22)K(x,x ) (-\|x-x \|_2^2), and the p-th order polynomial kernel K(x,x′)=(1+x⋅x′)pK(x,x )=(1+x· x )^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 ϕφ. Kernel-based learning methods make predictions using functions taking the form f(x)=∑i=1naik(xi,x)f(x)= _i=1^na_ik(x_i,x), where x1,…,xnx_1,...,x_n are training data points, and α1,…,αn _1,..., _n are weights that are learned by a training algorithm. Noting that f(x)=∑i=1nαik(x,xi)=ψ(x)⋅θf(x)= _i=1^n _ik(x,x_i)=ψ(x)·θ where θ=∑i=1naiψ(xi)θ= _i=1^na_iψ(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). 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 (Neumann et al. 2016; Leslie et al. 2001; Shimodaira et al. 2001; Shawe-Taylor and Cristianini 2004). 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 discussed N-gram encoding, the permutation operation is applied to encode the temporal information of time-series data (Joshi et al. 2017; Asgarinejad et al. 2020). 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 (Gudmundsson et al. 2008), which can handle time-series sequences with misalignment or time-stretching/compression. For graphs, GraphHD (Nunes et al. 2022) proposes to encode graph topology induced by PageRank centrality metric (Brin and Page 1998). 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 (Neumann et al. 2016) 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 (Yu et al. 2022; Thomas et al. 2021; Paxon Frady et al. 2021; Voelker 2020), mostly through the lens of random Fourier features (RFF) (Rahimi and Recht 2007). RFF is a sampling based scheme that generates a vector of features ϕ(x)∈ℝdφ(x)∈R^d with the property that ϕ(x)⋅ϕ(x′)≈K(x,x′)φ(x)·φ(x )≈ K(x,x ), where K is 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; Imani et al. 2020) and “fractional power encoding” (Paxon Frady et al. 2021). 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 function K, our goal is to generate an encoding function ϕ:→ℋφ:X such that ϕ(x)⋅ϕ(x′)≈K(x,x′)∀x,x′∈φ(x)·φ(x )≈ K(x,x ) ∀ x,x , where D is some subset of 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 matrix G defined element-wise by Gij=K(xi,xj)G_ij=K(x_i,x_j), which is problematic when n is 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; Drineas et al. 2005; Kumar et al. 2012). 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,…,xnD=\x_1,x_2,...,x_n\, from which we sample a set of landmarks =z1,…,zsZ=\z_1,...,z_s\, where s≪ns n. Let G∈ℝn×nG ^n× n be the full kernel matrix defined element-wise by Gij=K(xi,xj)G_ij=K(x_i,x_j), and let H∈ℝs×sH_Z ^s× s be the sub-sampled kernel matrix defined element-wise by (H)ij=K(zi,zj)(H_Z)_ij=K(z_i,z_j). The Nyström method yields the following approximation (Drineas et al. 2005): G^=CH+CT≈G G=CH_Z^+C^T≈ G (1) Where C is an n×sn× s matrix such that Cij=K(xi,zj)C_ij=K(x_i,z_j) for some kernel function K and HZ+H_Z^+ denotes the pseudo-inverse of H_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 (Kumar et al. 2012). Let Q and Λ be the eigenvectors and eigenvalues of H_Z then: HZ+=QΛ−1QTH_Z^+=Q ^-1Q^T This allows one to generate encodings explicitly via ϕnys(xi)=Λ−12QTC(i) _nys(x_i)= ^- 12Q^TC^(i), which approximates the kernel: ϕnys(xi)⋅ϕnys(xj)=(Λ−12QTC(i))⋅(Λ−12QTC(j))=G^ij split& _nys(x_i)· _nys(x_j)\\ &= ( ^- 12Q^TC^(i) )· ( ^- 12Q^TC^(j) )= G_ij split (2) Where xi,xj∈x_i,x_j and C(i)C^(i) denotes the ithi^th row of C in 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 (Khaleghi et al. 2022). 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 Z. As an initial step, in this paper we simply use uniform sampling without replacement (Williams and Seeger 2000; Kumar et al. 2012) as our sampling strategy. However, more sophisticated strategies such as ensemble and adaptive sampling (Kumar et al. 2012) 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) with the Nyström method to generate HDC embeddings that approximate a desired kernel. Alg. 1 describes the process for generating the Nyström embedding matrix, followed by data point encoding in Alg. 2. Algorithm 1 Generate the Nyström embedding matrix 0: kernel K over X, dataset D, number of landmarks s>0s>0, HDC dimension d>0d>0 ←Z← sample s points from D without replacement /*Landmarks*/ (H)ij=K(zi,zj)∀0≤i,j≤s(H_Z)_ij=K(z_i,z_j) ∀ 0≤ i,j≤ s /*Partial kernel Matrix over landmarks*/ QΛQT=HQ Q^T=H_Z /*Symmetric Eigen-decomposition*/ PrpP_rp = [w1,w1,⋯,wd]T∈ℝd×s[w_1,w_1,·s,w_d]^T ^d× s /*wiw_i sampled from s dimensional unit sphere*/ Pnys=PrpΛ−12QTP_nys=P_rp ^- 12Q^T return PnysP_nys , Z Algorithm 2 Encode one data point from D 0: xi∈x_i , Nyström embedding matrix PnysP_ nys, Landmarks Z and kernel function K C(i)=[K(xi,z1)K(xi,z2)⋯K(xi,zs)]T∈ℝsC^(i)= bmatrixK(x_i,z_1)&K(x_i,z_2)&·s&K(x_i,z_s) bmatrix^T ^s return π2d π2d sign (PnysC(i)) (P_nysC^(i) ) The rows of Prp∈ℝd×sP_rp ^d× s are sampled from the uniform distribution over the s-dimensional unit sphere. This enables the following result regarding sign-thresholded random projection: suppose v,v′∈ℝnv,v ^n are unit vectors, with respect to randomness in the sampling of PrpP_rp, the following result holds with randomness in the sampling of PrpP_rp (see for instance (Charikar 2002)): [1dsign(Prpv)⋅sign(Prpv′)]=(1−2cos−1(v⋅v′)/π) split&E [ 1dsign(P_rpv)·sign(P_rpv ) ]=(1-2 ^-1(v· v )/π) split (3) NysHD generates encodings for which the similarity induced by the kernel K is preserved by dot product between the encodings in ℋH. We summarize this result in the following theorem: Theorem 1. Let K be a positive-definite kernel and, using the notation of Algorithms 1 and 2, and recalling that ϕnys(xi)=Λ−12QTC(i) _nys(x_i)= ^- 12Q^TC^(i), define: ϕ(xi)=π2dsign(Prpϕnys(xi))φ(x_i)= π2dsign(P_rp _nys(x_i)) Then, for all xi,xj∈x_i,x_j : [ϕ(xi)⋅ϕ(xj)]=π2−cos−1(G^ijG^iiG^jj)E [φ (x_i )·φ (x_j ) ]= π2- ^-1 ( G_ij G_i G_j ) (4) Where G^ij G_ij is estimated kernel value between xix_i and xjx_j produced by Nyström method. The expectation is taken with respect to randomness in the sampling of landmarks and PrpP_rp. Proof: Let ϕ¯nys(xi) φ_nys(x_i) denote normalization: ϕnys(xi)‖ϕnys(xi)‖ _nys(x_i)|| _nys(x_i)||. Noting that sign(cv)=sign(v)sign(cv)=sign(v) for any v if c≥0c≥ 0: ϕ(xi)⋅ϕ(xj)=π2d(sign(Prpϕnys (xi))⋅sign(Prpϕnys (xj)))=π2(1dsign(Prpϕ¯nys(xi))⋅sign(Prpϕ¯nys(xj))) split&φ (x_i )·φ (x_j )\\ &= π2d (sign (P_rp _nys (x_i ) )·sign (P_rp _nys (x_j) ) )\\ &= π2 ( 1dsign (P_rp φ_nys(x_i) )·sign (P_rp φ_nys(x_j) ) )\\ split (5) Using result regarding sign-thresholded random projection in equation 3, we have: [ϕ(xi)⋅ϕ(xj)]=π2(1−2cos−1(ϕ¯nys(xi)⋅ϕ¯nys(xj))π) split&E [φ(x_i)·φ(x_j) ]\\ &= π2 (1- 2 ^-1 ( φ_nys(x_i)· φ_nys(x_j) )π )\\ split (6) Recalling the Nyström method in equation LABEL:nys_approx and the fact that ‖ϕnys(xi)‖=ϕnys(xi)⋅ϕnys(xi)=G^ii|| _nys(x_i)||= _nys(x_i)· _nys(x_i)= G_i: ϕ¯nys(xi)⋅ϕ¯nys(xj)=G^ijG^iiG^jj split φ_nys(x_i)· φ_nys(x_j)= G_ij G_i G_j split (7) Finally: [ϕ(xi)⋅ϕ(xj)]=π2−cos−1(G^ijG^iiG^jj)■ splitE [φ(x_i)·φ(x_j) ]&= π2- ^-1 ( G_ij G_i G_j ) split (8) To make the relationship with kernel approximation more explicit, consider the first order Taylor expansion of cos−1 ^-1. Since ‖ϕ¯nys(xi)‖=‖ϕ¯nys(xj)‖=1|| φ_nys(x_i)||=|| φ_nys(x_j)||=1, it follows that −1≤ϕ¯nys(xi)⋅ϕ¯nys(xj)≤1-1≤ φ_nys(x_i)· φ_nys(x_j)≤ 1, which means G^ijG^iiG^jj G_ij G_i G_j is within the domain of cos−1 ^-1, So: [ϕ(xi)⋅ϕ(xj)]≈π2−(π2−G^ijG^iiG^jj)=G^ijG^iiG^jj splitE [φ(x_i)·φ(x_j) ]&≈ π2- ( π2- G_ij G_i G_j )\\ &= G_ij G_i G_j split (9) Note that this is called normalized kernel (Ah-Pine 2010). As shown above, NysHD preserves the kernel in ℋ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 kernel K. Since HDC relies on the inner product in ℋH for inference, as described in Section “Learning with HD” Learning With HDC, the similarity metric captured by the kernel K is 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 set s. In this section, we provide an asymptotic runtime analysis of the encoding algorithm. Assuming that evaluating the kernel function K takes (m)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 of n samples with s landmarks to d dimensional embedding is O(max(s3,snm,snd))O( (s^3,snm,snd)). The first term corresponds to the symmetric eigen-decomposition of the matrix H_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 where s≪ns 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 of s and K is 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 (Leslie et al. 2001), which compares the N-gram composition between two input strings, has (mlog(m))O(m (m)) in the length of the input sequences. Evaluation We conduct an empirical evaluation of NysHD. First, we validate 1 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 Task dataset # training # testing # class Description Graph ENZYMES (Borgwardt et al. 2005) 480 120 6 Graph with attributed nodes NCI1 (Wale et al. 2008) 3288 822 2 Graph with labeled nodes D&D (Dobson and Doig 2003) 943 235 2 Graph with labeled nodes BZR (Sutherland et al. 2003) 324 81 2 Graph with attributed nodes MUTAG (Debnath et al. 1991) 150 38 2 Graph with labeled nodes COX2 (Sutherland et al. 2003) 373 94 2 Graph with attributed nodes NCI109 (Wale et al. 2008) 3301 826 2 Graph with labeled nodes Mutagenicity (Riesen and Bunke 2008) 3469 868 2 Graph with labeled nodes String Protein (Selvaraj et al. 2023) 721 181 6 Protein sequence SMS (Almeida,Tiago and Hidalgo,Jos 2012) 4459 1115 2 Nautral Language Splice (Towell et al. 1992) 2552 628 3 DNA sequence Promoter (Harley et al. 1990) 84 22 2 DNA sequence Table 1: Summary of tasks and datasets The 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: Graphs and Strings classification. In total, we have chosen 8 graph datasets from TUDataset (Morris et al. 2020), 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. 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 (Leslie et al. 2004) for string classification. The gappy kernel is a variant of the spectrum kernel (Leslie et al. 2001) that allows a small amount of gap within the N-grams. The propagation kernel (Neumann et al. 2016) is used for graph classification for its ability to work with labeled or attributed graphs, as discussed in the section “kernel methods” Kernel Methods. 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 classification using the encoding scheme from introduced in GraphHD (Nunes et al. 2022) and String classification uses N-gram HDC encoding approach (Joshi et al. 2017). 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 use DGCNN (Zhang et al. 2018), GCN (Chen et al. 2019), GIN (Xu et al. 2018), GIUNet (Amouzad et al. 2024). On string datasets, following the recent trend of applying large models for bio-sequence and language modeling (Qiu et al. 2020; Raffel et al. 2020), we fine-tune Large protein model (ESM-2-8m (Rives et al. 2021)) for for bio-sequence datasets, and large language model (BERT (Devlin et al. 2018)) for natural language dataset. For our method, we set the number of landmarks: s = maxmax(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-Cano et al. 2021) when evaluating different HDC encoding methods. The Perceptron algorithm (Rosenblatt 1958) 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 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. In line with Theorem 1, 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 Method NCI1 ENZYMES D&D BZR MUTAG COX2 NCI109 Mutagenicity DGCNN Acc. 70.2 ± 2.2% 36.9 ± 4.6% 74.5 ± 3.4% 81.5 ± 4.4% 82.9 ± 4.1% 78.3 ± 2.7% 71.1 ± 2.2% 75.0 ± 1.3% Time 37.5 ± 1.2s 5.6 ± 0.5s 59.2 ± 3.0s 4.0 ± 0.0s 1.0 ± 0.0s 4.1 ± 0.3s 36.2 ± 0.9s 44.8 ± 1.3s GCN Acc. 79.9 ± 1.1% 60.7 ± 2.1% 74.8 ± 1.6% 84.2 ± 2.2% 85.5 ± 3.8% 83.1 ± 3.7% 80.2 ± 1.1% 79.9 ± 1.0% Time 74.3 ± 0.6s 15.9 ± 0.5s 262.3 ± 9.2s 7.9 ± 0.3s 3.0 ± 0.0s 11.0 ± 0.0s 73.5 ± 0.7s 75.3 ± 0.5s GIN Acc. 73.4 ± 1.7% 28.8 ± 4.2% 67.5 ± 5.9% 76.4 ± 8.4% 76.8 ± 9.6% 78.1 ± 4.3% 70.8 ± 2.6% 78.0 ± 1.7% Time 66.8 ± 1.0s 9.0 ± 0.0s 63.6 ± 0.7s 6.0 ± 0.0s 2.0 ± 0.0s 7.2 ± 0.4s 67.1 ± 0.5s 70.5 ± 0.5s GIUNet Acc. 72.4 ± 1.4% 29.9 ± 4.0% 63.4 ± 6.9% 78.3 ± 10.7% 85.0 ± 4.7% 77.4 ± 7.0% 68.8 ± 4.3% 76.5 ± 0.8% Time 89.0 ± 0.4s 13.0 ± 0.0s 96.2 ± 0.7s 9.0 ± 0.0s 3.0 ± 0.0s 11.0 ± 0.0s 89.5 ± 0.5s 94.6 ± 0.5s GraphHD Acc. 60.0 ± 2.1% 23.2 ± 2.3% 67.6 ± 1.3% 74.9 ± 2.1% 85.3 ± 10.2% 81.9 ± 3.9% 59.9 ± 2.1% 59.8 ± 1.7% Time 30.0 ± 0.7s 6.0 ± 0.0s 32.9 ± 0.3s 3.0 ± 0.0s 1.0 ± 0.0s 3.0 ± 0.0s 30.0 ± 0.0s 31.3 ± 0.4s NysHD Acc. 73.8 ± 2.2% 61.3 ± 2.5% 76.2 ± 2.8% 82.0 ± 3.3% 85.5 ± 3.4% 74.6 ± 3.7% 71.8 ± 2.0% 75.2 ± 0.9% Time 43.8 ± 0.8s 7.2 ± 0.6s 35.4 ± 1.6s 3.4 ± 0.5s 2.0 ± 0.0s 5.5 ± 0.8s 44.4 ± 0.8s 35.7 ± 1.0s Table 2: Experimental results. The best accuracy result for each dataset are highted and second best are underlined. Method Protein SMS Promoter Splice LM 96 ± 0% 99 ± 0% 82 ± 2.7% 92 ± 1.4% Finetune 2003 ± 193s 2846 ± 31s 6 ± 3.0s 142 ± 1.9s N-gram 96 ± 0.8% 97 ± 0.3% 52 ± 4.0% 43 ± 4.9% HDC 13 ± 0.0s 43 ± 0.4s 1 ± 0.0s 25 ± 0.8s NysHD 98 ± 0.3% 97 ± 0.2% 89 ± 3.4% 72 ± 1.7% 19 ± 0.7s 34 ± 0.0s 1 ± 0.0s 21 ± 0.3s Table 3: Accuracy and training time on string datasets The accuracy results for graph and string datasets are summarized in Table 2 and Table 3. 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 (Nunes et al. 2022) could not utilize node attributes in attributed graphs, whereas our method can. On string datasets, our method again consistently achieves better accuracy compared to N-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 (Nunes et al. 2022) 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 (Kumar et al. 2012; Musco and Musco 2017). 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. In PAKDD 2010, Hyderabad, India, June 21-24, 2010. Proceedings. Part I 14, p. 362–373. Cited by: Encoding Process. Almeida,Tiago and Hidalgo,Jos (2012) SMS Spam Collection. Note: UCI Machine Learning RepositoryDOI: https://doi.org/10.24432/C5C84 Cited by: Table 1. A. Amouzad, Z. Dehghanian, S. Saravani, M. Amirmazlaghani, and B. Roshanfekr (2024) Graph isomorphism u-net. Expert Systems with Applications 236, p. 121280. Cited by: Experimental Setup and Baselines. F. Asgarinejad, A. Thomas, and T. Rosing (2020) Detection of epileptic seizures from surface eeg using hyperdimensional computing. In EMBC, p. 536–540. Cited by: Kernel Methods and HDC. K. M. Borgwardt, C. S. Ong, S. Schönauer, S. Vishwanathan, A. J. Smola, and H. Kriegel (2005) Protein function prediction via graph kernels. Bioinformatics 21. Cited by: Table 1. S. Brin and L. Page (1998) The anatomy of a large-scale hypertextual web search engine. Computer networks and ISDN systems 30 (1-7), p. 107–117. Cited by: Kernel Methods and HDC. M. S. Charikar (2002) Similarity estimation techniques from rounding algorithms. In Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, p. 380–388. Cited by: Encoding Process, Encoding Process. 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. 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 chemistry 34 (2), p. 786–797. Cited by: Table 1. 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. P. D. Dobson and A. J. Doig (2003) Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology 330 (4), p. 771–783. Cited by: Table 1. P. Drineas, M. W. Mahoney, and N. Cristianini (2005) On the nyström method for approximating a gram matrix for improved kernel-based learning.. JMLR 6 (12). Cited by: Nyström Method, Nyström Method. 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. In GLSVLSI, p. 281–286. Cited by: Introduction. S. Gudmundsson, T. P. Runarsson, and S. Sigurdsson (2008) Support vector machines and dynamic time warping for time series. In 2008 IEEE International Joint Conference on Neural Networks, p. 2772–2776. Cited by: Kernel Methods and HDC. C. Harley, R. Reynolds, and M. Noordewier (1990) Molecular Biology (Promoter Gene Sequences). Note: UCI Machine Learning RepositoryDOI: https://doi.org/10.24432/C5S01D Cited by: Table 1. Z. S. Harris (1954) Distributional structure. Word 10 (2-3), p. 146–162. Cited by: Learning With HDC. A. Hernández-Cano, N. Matsumoto, E. Ping, and M. Imani (2021) Onlinehd: robust, efficient, and single-pass online learning using hyperdimensional system. In DATE, p. 56–61. Cited by: Introduction, Experimental Setup and Baselines. J. A. Hertz (2018) Introduction to the theory of neural computation. Crc Press. Cited by: Introduction. T. Hofmann, B. Schölkopf, and A. J. Smola (2008) Kernel methods in machine learning. Cited by: Kernel Methods. 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. In DAC, p. 1–6. Cited by: Learning With HDC. M. Imani, T. Nassar, A. Rahimi, and T. Rosing (2018) Hdna: energy-efficient dna sequencing using hyperdimensional computing. In BHI, p. 271–274. Cited by: Learning With HDC. 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. In MICRO, p. 356–371. Cited by: Related Work. A. Joshi, J. T. Halseth, and P. Kanerva (2017) Language geometry using random indexing. In Quantum Interaction: 10th International Conference, QI 2016, San Francisco, CA, USA, July 20-22, 2016, Revised Selected Papers 10, p. 265–274. Cited by: Learning With HDC, Kernel Methods and HDC, Experimental Setup and Baselines. P. Kanerva (2009) Hyperdimensional computing: an introduction to computing in distributed representation with high-dimensional random vectors. Cognitive computation 1, p. 139–159. Cited by: Introduction. J. Kang, B. Khaleghi, Y. Kim, and T. Rosing (2022a) Xcelhd: an efficient gpu-powered hyperdimensional computing with parallelized training. In ASP-DAC, p. 220–225. Cited by: Introduction. J. Kang, B. Khaleghi, T. Rosing, and Y. Kim (2022b) Openhd: a gpu-powered framework for hyperdimensional computing. IEEE Transactions on Computers 71 (11), p. . Cited by: Introduction. B. Khaleghi, J. Kang, H. Xu, J. Morris, and T. Rosing (2022) GENERIC: highly efficient learning engine on edge using hyperdimensional computing. In DAC, p. 1117–1122. Cited by: Introduction, Learning With HDC, Nyström Method. D. Kleyko, D. Rachkovskij, E. Osipov, and A. Rahimi (2023) A survey on hyperdimensional computing aka vector symbolic architectures, part i: applications, cognitive models, and challenges. ACM Computing Surveys 55 (9), p. 1–52. Cited by: Introduction. S. Kumar, M. Mohri, and A. Talwalkar (2012) Sampling methods for the nyström method. JMLR 13 (1), p. 981–1006. Cited by: Nyström Method, Nyström Method, Nyström Method, Overhead & Scalability. C. Leslie, E. Eskin, and W. S. Noble (2001) The spectrum kernel: a string kernel for svm protein classification. In Biocomputing 2002, p. 564–575. Cited by: Kernel Methods and HDC, Encoding Complexity, Datasets and Kernel Functions. C. Leslie, R. Kuang, and K. Bennett (2004) Fast string kernels using inexact matching for protein sequences.. JMLR 5 (9). Cited by: Datasets and Kernel Functions. G. Meanti, L. Carratino, L. Rosasco, and A. Rudi (2020) Kernel methods through the roof: handling billions of points efficiently. NeurIPS 33, p. 14410–14422. Cited by: Kernel Methods. 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. V. Miranda and O. d’Aliberti (2022) Hyperdimensional computing encoding schemes for improved image classification. In HST, p. 1–9. Cited by: Learning With HDC, Related Work. 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. 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. In DATE, p. 723–728. Cited by: Introduction, Learning With HDC, Learning With HDC. C. Musco and C. Musco (2017) Recursive sampling for the nystrom method. NeurIPS 30. Cited by: Overhead & Scalability. M. Neumann, R. Garnett, C. Bauckhage, and K. Kersting (2016) Propagation kernels: efficient graph kernels from propagated information. Machine learning 102, p. 209–245. Cited by: Kernel Methods and HDC, Kernel Methods and HDC, Datasets and Kernel Functions. I. Nunes, M. Heddes, T. Givargis, A. Nicolau, and A. Veidenbaum (2022) GraphHD: efficient graph classification using hyperdimensional computing. In DATE, p. 1485–1490. Cited by: Learning With HDC, Kernel Methods and HDC, Experimental Setup and Baselines, Accuracy and Efficiency Results. E. Paxon Frady, D. Kleyko, C. J. Kymn, B. A. Olshausen, and F. T. Sommer (2021) Computing on functions using randomized vector representations. , p. arXiv–2109. Cited by: Related Work. T. A. Plate (1995) Holographic reduced representations. IEEE Transactions on Neural networks 6 (3), p. 623–641. Cited by: Introduction. 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 sciences 63 (10), p. 1872–1897. Cited by: Experimental Setup and Baselines. 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. JMLR 21 (140), p. 1–67. Cited by: Experimental Setup and Baselines. 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 IEEE 107 (1), p. 123–143. Cited by: Learning With HDC. A. Rahimi and B. Recht (2007) Random features for large-scale kernel machines. NeurIPS 20. Cited by: Related Work. K. Riesen and H. Bunke (2008) IAM graph database repository for graph based pattern recognition and machine learning. In SSPR & SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings, p. 287–297. Cited by: Table 1. 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 Sciences 118 (15), p. e2016239118. Cited by: Experimental Setup and Baselines. F. Rosenblatt (1958) The perceptron: a probabilistic model for information storage and organization in the brain.. Psychological review 65 (6), p. 386. Cited by: Learning With HDC, Experimental Setup and Baselines. S. Salamat, M. Imani, B. Khaleghi, and T. Rosing (2019) F5-hd: fast flexible fpga-based framework for refreshing hyperdimensional computing. In Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays, p. 53–62. Cited by: Introduction. 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 bioinformatics 24 (1), p. 29. Cited by: Table 1. J. Shawe-Taylor and N. Cristianini (2004) Kernel methods for pattern analysis. Cambridge university press. Cited by: Introduction, Kernel Methods, Kernel Methods and HDC. H. Shimodaira, K. Noma, M. Nakai, and S. Sagayama (2001) Dynamic time-alignment kernel in support vector machine. NeurIPS 14. Cited by: Kernel Methods and HDC. A. J. Smola and B. Schölkopf (1998) Learning with kernels. Vol. 4, Citeseer. Cited by: Introduction. I. Steinwart (2001) On the influence of the kernel on the consistency of support vector machines. JMLR 2 (Nov). Cited by: Kernel Methods. 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 sciences 43 (6), p. 1906–1915. Cited by: Table 1, Table 1. A. Thomas, S. Dasgupta, and T. Rosing (2021) A theoretical perspective on hyperdimensional computing. JAIR 72, p. 215–249. Cited by: Learning With HDC, Related Work. G. Towell, M. Noordewier, and J. Shavlik (1992) Primate splice-junction gene sequences (dna) with associated imperfect domain theory. Cited by: Table 1. A. R. Voelker (2020) A short letter on the dot product between rotated fourier transforms. arXiv preprint arXiv:2007.13462. Cited by: Related Work. N. Wale, I. A. Watson, and G. Karypis (2008) Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems 14, p. 347–375. Cited by: Table 1, Table 1. C. Williams and M. Seeger (2000) Using the nyström method to speed up kernel machines. NeurIPS 13. Cited by: Introduction, Nyström Method, Nyström Method. 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. W. Xu, J. Kang, and T. Rosing (2023) FSL-hd: accelerating few-shot learning on reram using hyperdimensional computing. In DATE, p. 1–6. Cited by: Introduction. T. Yu, Y. Zhang, Z. Zhang, and C. D. Sa (2022) Understanding hyperdimensional computing for parallel single-pass learning. In NeurIPS, A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho (Eds.), External Links: Link Cited by: Introduction, Related Work. M. Zhang, Z. Cui, M. Neumann, and Y. Chen (2018) An end-to-end deep learning architecture for graph classification. In AAAI, Vol. 32. Cited by: Experimental Setup and Baselines. 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. Q. Zhao, K. Lee, J. Liu, M. Huzaifa, X. Yu, and T. Rosing (2022) FedHD: federated learning with hyperdimensional computing. In MobiCom, p. 791–793. Cited by: Introduction.