Vertex-reinforced Random Walk for Network Embedding
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.
Code (1)
Tasks
Link PredictionNetwork EmbeddingNode ClassificationSimilar Papers 제목 키워드 기반
On Statistical Estimation of Edge-Reinforced Random Walks
Reinforced random walks (RRWs), including vertex-reinforced random walks (VRRWs) and edge-reinforced random walks (ERRWs), model random walks where the transition probabilities evolve based on prior visitation history~\c…
Representation LearningDelving Into Deep Walkers: A Convergence Analysis of Random-Walk-Based Vertex Embeddings
Graph vertex embeddings based on random walks have become increasingly influential in recent years, showing good performance in several tasks as they efficiently transform a graph into a more computationally digestible f…
Dynamic social learning under graph constraints
We introduce a model of graph-constrained dynamic choice with reinforcement modeled by positively $\alpha$-homogeneous rewards. We show that its empirical process, which can be written as a stochastic approximation recur…
Random Walks on Hypergraphs with Edge-Dependent Vertex Weights
Hypergraphs are used in machine learning to model higher-order relationships in data. While spectral methods for graphs are well-established, spectral theory for hypergraphs remains an active area of research. In this pa…
BIG-bench Machine LearningTNE: A Latent Model for Representation Learning on Networks
Network representation learning (NRL) methods aim to map each vertex into a low dimensional space by preserving the local and global structure of a given network, and in recent years they have received a significant atte…
Community DetectionLink PredictionNode ClassificationRepresentation Learning+1