Learning-free continuous-attribute graph embedding via locality-sensitive hashing

Graph embedding represents each graph in a low-dimensional space with similarity between graph pairs preserved. While the mainstream Graph Neural Networks (GNNs) achieve strong performance, they pose significant computational challenges and predominantly focus on discrete-attribute graphs. In this paper, we propose #WLS, a learning-free continuous-attribute graph embedding model that keeps a good trade-off between accuracy and efficiency by employing Locality-Sensitive Hashing (LSH) to preserve high-order node similarity. Experimental results on seven real-world datasets (405 to 41,127 graphs) show that #WLS achieves accuracy comparable to representative GNN methods in graph classification (e.g., 80.12% vs. 76.83% on OGBG_MOLHIV) while reducing runtime (up to 27,183× speedups in our experiments) and maintaining a low memory footprint (under 300MB on PROTEINS_full and AIDS). It also outperforms existing LSH-based methods on most datasets. In graph retrieval, #WLS attains MAP scores competitive with GNN methods (e.g., 74.27% vs. 72.25% on PROTEINS_full) and outperforms existing LSH-based methods across the evaluated datasets.