# VS-Graph: Scalable and Efficient Graph Classification Using Hyperdimensional Computing

arXiv: https://arxiv.org/abs/2512.03394 · HTML: https://mlsanity.com/paper/2512.03394/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 44 references that are in the map.
- First posted on arXiv 3 Dec 2025.

## Builds on (most cited first, 25 of 25)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Are Graph Augmentations Necessary? Simple Graph Contrastive Learning for Recommendation](https://mlsanity.com/paper/2112.08679/) (2021)
- [Spherical Message Passing for 3D Graph Networks](https://mlsanity.com/paper/2102.05013/) (2021)
- [A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations](https://mlsanity.com/paper/2111.06077/) (2021)
- [A Survey of Graph Neural Networks for Social Recommender Systems](https://mlsanity.com/paper/2212.04481/) (2022)
- [In-memory hyperdimensional computing](https://mlsanity.com/paper/1906.01548/) (2019)
- [GraphHD: Efficient graph classification using hyperdimensional computing](https://mlsanity.com/paper/2205.07826/) (2022)
- [Graph Mixup with Soft Alignments](https://mlsanity.com/paper/2306.06788/) (2023)
- [Molecular Property Prediction Based on Graph Structure Learning](https://mlsanity.com/paper/2312.16855/) (2023)
- [Hyperdimensional Representation Learning for Node Classification and Link Prediction](https://mlsanity.com/paper/2402.17073/) (2024)
- [Survey on Characterizing and Understanding GNNs from a Computer Architecture Perspective](https://mlsanity.com/paper/2408.01902/) (2024)
- [ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion](https://mlsanity.com/paper/2504.15920/) (2025)
- [HyperGraphX: Graph Transductive Learning with Hyperdimensional Computing and Message Passing](https://mlsanity.com/paper/2510.23980/) (2025)
- [Molecular Classification Using Hyperdimensional Graph Classification](https://mlsanity.com/paper/2403.12307/) (2024)

## Built on by (most cited first, 1 of 1)

- [ConformalHDC: Uncertainty-Aware Hyperdimensional Computing with Application to Neural Decoding](https://mlsanity.com/paper/2602.21446/) (2026)

## Abstract (arXiv)

Graph classification is a fundamental task in domains ranging from molecular property prediction to materials design. While graph neural networks (GNNs) achieve strong performance by learning expressive representations via message passing, they incur high computational costs, limiting their scalability and deployment on resource-constrained devices. Hyperdimensional Computing (HDC), also known as Vector Symbolic Architectures (VSA), offers a lightweight, brain-inspired alternative, yet existing HDC-based graph methods typically struggle to match the predictive performance of GNNs. In this work, we propose VS-Graph, a vector-symbolic graph learning framework that narrows the gap between the efficiency of HDC and the expressive power of message passing. VS-Graph introduces a Spike Diffusion mechanism for topology-driven node identification and an Associative Message Passing scheme for multi-hop neighborhood aggregation entirely within the high-dimensional vector space. Without gradient-based optimization or backpropagation, our method achieves competitive accuracy with modern GNNs, outperforming the prior HDC baseline by 4-5% on standard benchmarks such as MUTAG and DD. It also matches or exceeds the performance of the GNN baselines on several datasets while accelerating the training by a factor of up to 450x. Furthermore, VS-Graph maintains high accuracy even with the hypervector dimensionality reduced to D=128, demonstrating robustness under aggressive dimension compression and paving the way for ultra-efficient execution on edge and neuromorphic hardware.