Node Embedding Accelerates Randoms Walk on a Graph

Graphs serve as powerful representations for various real-world systems such as social networks, biological networks, and communication networks. Random walk algorithms have gained popularity for graph-based data analysis and processing, finding applications across various domains. Understanding and enhancing these algorithms is crucial for ensuring high-quality protocols, controls, and services in large-scale communication networks. While conventional random walks typically rely on local information, there is potential to improve node search efficiency by incorporating information beyond the local context. Concurrently, there is growing interest in machine learning techniques that represent data as graphs rather than vectors, known as graph and node embedding algorithms. This paper investigates whether leveraging node embedding vectors generated by such techniques can enhance the efficiency and effectiveness of random walks on a graph. To address this, we propose EmbedRW (Embedded Random Walk), which integrates node embedding techniques with random walk design. Through simulation experiments, we demonstrate that utilizing node embeddings can significantly reduce the search time for the target node across a wide range of graphs.