NodeSig: Binary Node Embeddings via Random Walk Diffusion
This work addresses scalability challenges in graph representation learning for network analysis applications, offering a solution that balances computational efficiency with task performance, though it appears incremental as it builds on existing methods like random walks and binary embeddings.
The paper tackles the trade-off between efficiency and accuracy in graph representation learning for large-scale networks by proposing NodeSig, a scalable model that computes binary node embeddings using random walk diffusion and stable random projections. The model achieves a good balance between accuracy and efficiency in node classification and link prediction tasks, as demonstrated through extensive experiments on various networks.
Graph Representation Learning (GRL) has become a key paradigm in network analysis, with a plethora of interdisciplinary applications. 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 NodeSig, a scalable model that computes binary node representations. NodeSig 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.