A Broader Picture of Random-walk Based Graph Embedding
arXiv:2110.12344 · doi:10.1145/3447548.3467300
Abstract
Graph embedding based on random-walks supports effective solutions for many graph-related downstream tasks. However, the abundance of embedding literature has made it increasingly difficult to compare existing methods and to identify opportunities to advance the state-of-the-art. Meanwhile, existing work has left several fundamental questions -- such as how embeddings capture different structural scales and how they should be applied for effective link prediction -- unanswered. This paper addresses these challenges with an analytical framework for random-walk based graph embedding that consists of three components: a random-walk process, a similarity function, and an embedding algorithm. Our framework not only categorizes many existing approaches but naturally motivates new ones. With it, we illustrate novel ways to incorporate embeddings at multiple scales to improve downstream task performance. We also show that embeddings based on autocovariance similarity, when paired with dot product ranking for link prediction, outperform state-of-the-art methods based on Pointwise Mutual Information similarity by up to 100%.
arXiv commentAccepted to KDD 2021
References in corpus (13)
- Community structure in social and biological networks
- DeepWalk: Online Learning of Social Representations
- Hierarchical Organization in Complex Networks
- Stochastic blockmodels and community structure in networks
- Graph Embedding Techniques, Applications, and Performance: A Survey
- Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks
- Laplacian Dynamics and Multiscale Modular Structure in Networks
- Learning Structural Node Embeddings Via Diffusion Wavelets
- VERSE: Versatile Graph Embeddings from Similarity Measures
- A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications
- Multiscale dynamical embeddings of complex networks
- The impossibility of low rank representations for triangle-rich complex networks
- A Graph-structured Dataset for Wikipedia Research