# A Broader Picture of Random-walk Based Graph Embedding

arXiv: https://arxiv.org/abs/2110.12344 · HTML: https://mlsanity.com/paper/2110.12344/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 70 references that are in the map.
- First posted on arXiv 24 Oct 2021.

## Builds on (most cited first, 23 of 23)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [Poincar'e Embeddings for Learning Hierarchical Representations](https://mlsanity.com/paper/1705.08039/) (2017)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [A Comprehensive Survey of Graph Embedding: Problems, Techniques and Applications](https://mlsanity.com/paper/1709.07604/) (2017)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Graph Embedding Techniques, Applications, and Performance: A Survey](https://mlsanity.com/paper/1705.02801/) (2017)
- [A Survey on Network Embedding](https://mlsanity.com/paper/1711.08752/) (2017)
- [Learning Structural Node Embeddings Via Diffusion Wavelets](https://mlsanity.com/paper/1710.10321/) (2017)
- [HARP: Hierarchical Representation Learning for Networks](https://mlsanity.com/paper/1706.07845/) (2017)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization](https://mlsanity.com/paper/1906.11156/) (2019)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [Random Walks, Markov Processes and the Multiscale Modular Organization of Complex Networks](https://mlsanity.com/paper/1502.04381/) (2015)
- [InfiniteWalk: Deep Network Embeddings as Laplacian Embeddings with a Nonlinearity](https://mlsanity.com/paper/2006.00094/) (2020)
- [Node Representation Learning for Directed Graphs](https://mlsanity.com/paper/1810.09176/) (2018)
- [Multiscale dynamical embeddings of complex networks](https://mlsanity.com/paper/1804.03733/) (2018)
- [Model of complex networks based on citation dynamics](https://mlsanity.com/paper/1303.5857/) (2013)
- [The stability of a graph partition: A dynamics-based framework for community detection](https://mlsanity.com/paper/1308.1605/) (2013)
- [A Graph-structured Dataset for Wikipedia Research](https://mlsanity.com/paper/1903.08597/) (2019)

## Built on by (most cited first, 16 of 16)

- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Global Counterfactual Explainer for Graph Neural Networks](https://mlsanity.com/paper/2210.11695/) (2022)
- [QGTC: Accelerating Quantized Graph Neural Networks via GPU Tensor Core](https://mlsanity.com/paper/2111.09547/) (2021)
- [TC-GNN: Bridging Sparse GNN Computation and Dense Tensor Cores on GPUs](https://mlsanity.com/paper/2112.02052/) (2021)
- [Subgraph Pooling: Tackling Negative Transfer on Graphs](https://mlsanity.com/paper/2402.08907/) (2024)
- [Learning Bi-typed Multi-relational Heterogeneous Graph via Dual Hierarchical Attention Networks](https://mlsanity.com/paper/2112.13078/) (2021)
- [GraphScale: A Framework to Enable Machine Learning over Billion-node Graphs](https://mlsanity.com/paper/2407.15452/) (2024)
- [Link Prediction without Graph Neural Networks](https://mlsanity.com/paper/2305.13656/) (2023)
- [Multiple Similarity Drug-Target Interaction Prediction with Random Walks and Matrix Factorization](https://mlsanity.com/paper/2201.09508/) (2022)
- [Disentangled and Self-Explainable Node Representation Learning](https://mlsanity.com/paper/2410.21043/) (2024)
- [Attribute-Enhanced Similarity Ranking for Sparse Link Prediction](https://mlsanity.com/paper/2412.00261/) (2024)
- [GLADformer: A Mixed Perspective for Graph-level Anomaly Detection](https://mlsanity.com/paper/2406.00734/) (2024)
- [Normalized Space Alignment: A Versatile Metric for Representation Analysis](https://mlsanity.com/paper/2411.04512/) (2024)
- [Learning Graph Node Embeddings by Smooth Pair Sampling](https://mlsanity.com/paper/2501.12884/) (2025)
- [Embedding Learning on Multiplex Networks for Link Prediction](https://mlsanity.com/paper/2602.01922/) (2026)
- [Mochi: Aligning Pre-training and Inference for Efficient Graph Foundation Models via Meta-Learning](https://mlsanity.com/paper/2604.22031/) (2026)

## Abstract (arXiv)

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%.