  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.
