# CiliaGraph: Enabling Expression-enhanced Hyper-Dimensional Computation in Ultra-Lightweight and One-Shot Graph Classification on Edge

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 28 of its 59 references that are in the map.
- First posted on arXiv 29 May 2024.

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

- [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)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding](https://mlsanity.com/paper/1510.00149/) (2015)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Graph Neural Networks for Social Recommendation](https://mlsanity.com/paper/1902.07243/) (2019)
- [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)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Self-supervised Learning on Graphs: Deep Insights and New Direction](https://mlsanity.com/paper/2006.10141/) (2020)
- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)
- [A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations](https://mlsanity.com/paper/2111.06077/) (2021)
- [How Powerful are K-hop Message Passing Graph Neural Networks](https://mlsanity.com/paper/2205.13328/) (2022)
- [Classification using Hyperdimensional Computing: A Review](https://mlsanity.com/paper/2004.11204/) (2020)
- [GraphHD: Efficient graph classification using hyperdimensional computing](https://mlsanity.com/paper/2205.07826/) (2022)
- [Message Passing Attention Networks for Document Understanding](https://mlsanity.com/paper/1908.06267/) (2019)
- [Understanding Hyperdimensional Computing for Parallel Single-Pass Learning](https://mlsanity.com/paper/2202.04805/) (2022)
- [Torchhd: An Open Source Python Library to Support Research on Hyperdimensional Computing and Vector Symbolic Architectures](https://mlsanity.com/paper/2205.09208/) (2022)
- [On-Device Unsupervised Image Segmentation](https://mlsanity.com/paper/2303.12753/) (2023)
- [Learning from Hypervectors: A Survey on Hypervector Encoding](https://mlsanity.com/paper/2308.00685/) (2023)
- [Optimizing Memory Efficiency of Graph Neural Networks on Edge Computing Platforms](https://mlsanity.com/paper/2104.03058/) (2021)
- [An Extension to Basis-Hypervectors for Learning from Circular Data in Hyperdimensional Computing](https://mlsanity.com/paper/2205.07920/) (2022)
- [HDLock: Exploiting Privileged Encoding to Protect Hyperdimensional Computing Models against IP Stealing](https://mlsanity.com/paper/2203.09681/) (2022)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are computationally demanding and inefficient when applied to graph classification tasks in resource-constrained edge scenarios due to their inherent process, involving multiple rounds of forward and backward propagation. As a lightweight alternative, Hyper-Dimensional Computing (HDC), which leverages high-dimensional vectors for data encoding and processing, offers a more efficient solution by addressing computational bottleneck. However, current HDC methods primarily focus on static graphs and neglect to effectively capture node attributes and structural information, which leads to poor accuracy. In this work, we propose CiliaGraph, an enhanced expressive yet ultra-lightweight HDC model for graph classification. This model introduces a novel node encoding strategy that preserves relative distance isomorphism for accurate node connection representation. In addition, node distances are utilized as edge weights for information aggregation, and the encoded node attributes and structural information are concatenated to obtain a comprehensive graph representation. Furthermore, we explore the relationship between orthogonality and dimensionality to reduce the dimensions, thereby further enhancing computational efficiency. Compared to the SOTA GNNs, extensive experiments show that CiliaGraph reduces memory usage and accelerates training speed by an average of 292 times(up to 2341 times) and 103 times(up to 313 times) respectively while maintaining comparable accuracy.