NodeSig: Binary Node Embeddings via Random Walk Diffusion

Motivation

As the scale of networks increases, most of the widely used learning-based graph representation models also face computational challenges. While there is a recent effort toward designing algorithms that solely deal with scalability issues, most of them behave poorly in terms of accuracy on downstream tasks. In this paper, we aim to study models that balance the trade-off between efficiency and accuracy. In particular, we propose \textsc{\modelabbrv}, a scalable model that computes binary node representations. \textsc{\modelabbrv} exploits random walk diffusion probabilities via stable random projections towards efficiently computing embeddings in the Hamming space. Our extensive experimental evaluation on various networks has demonstrated that the proposed model achieves a good balance between accuracy and efficiency compared to well-known baseline models on the node classification and link prediction tasks.

Schematic representation of the NodeSig model.

Code

An implementation of the project in C++ can be reached at the Github repository.

A. Celikkanat, A. N. Papadopoulos and F. D. Malliaros, NodeSig: Binary Node Embeddings via Random Walk Diffusion, The 2022 IEEE/ACM International Conference on Advances in Social Network Analysis and Mining (ASONAM-22), Istanbul, Turkey, 2022.