Vertex-reinforced Random Walk for Network Embedding
This addresses network embedding for tasks like link prediction and node classification, offering a novel approach to improve random walk methods.
The paper tackled the problem of network embedding by proposing a non-Markovian random walk variant with an exploitation-exploration mechanism to prevent getting stuck, resulting in reinforce2vec outperforming state-of-the-art methods by a large margin on benchmark datasets.
In this paper, we study the fundamental problem of random walk for network embedding. We propose to use non-Markovian random walk, variants of vertex-reinforced random walk (VRRW), to fully use the history of a random walk path. To solve the getting stuck problem of VRRW, we introduce an exploitation-exploration mechanism to help the random walk jump out of the stuck set. The new random walk algorithms share the same convergence property of VRRW and thus can be used to learn stable network embeddings. Experimental results on two link prediction benchmark datasets and three node classification benchmark datasets show that our proposed approach reinforce2vec can outperform state-of-the-art random walk based embedding methods by a large margin.