# DeepWalking Backwards: From Embeddings Back to Graphs

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 31 references that are in the map.
- First posted on arXiv 17 Feb 2021.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [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)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method](https://mlsanity.com/paper/1402.3722/) (2014)
- [Quantifying Privacy Leakage in Graph Embedding](https://mlsanity.com/paper/2010.00906/) (2020)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [The impossibility of low rank representations for triangle-rich complex networks](https://mlsanity.com/paper/2003.12635/) (2020)
- [Node Embeddings and Exact Low-Rank Representations of Complex Networks](https://mlsanity.com/paper/2006.05592/) (2020)
- [InfiniteWalk: Deep Network Embeddings as Laplacian Embeddings with a Nonlinearity](https://mlsanity.com/paper/2006.00094/) (2020)
- [Scalable Graph Embeddings via Sparse Transpose Proximities](https://mlsanity.com/paper/1905.07245/) (2019)
- [Privacy Attacks on Network Embeddings](https://mlsanity.com/paper/1912.10979/) (2019)
- [Learning Networks from Random Walk-Based Node Similarities](https://mlsanity.com/paper/1801.07386/) (2018)

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

- [On Strengthening and Defending Graph Reconstruction Attack with Markov Chain Approximation](https://mlsanity.com/paper/2306.09104/) (2023)
- [Model Inversion Attacks: A Survey of Approaches and Countermeasures](https://mlsanity.com/paper/2411.10023/) (2024)
- [Finding MNEMON: Reviving Memories of Node Embeddings](https://mlsanity.com/paper/2204.06963/) (2022)
- [On provable privacy vulnerabilities of graph representations](https://mlsanity.com/paper/2402.04033/) (2024)
- [AI Security in the Foundation Model Era: A Comprehensive Survey from a Unified Perspective](https://mlsanity.com/paper/2603.24857/) (2026)
- [Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective](https://mlsanity.com/paper/2405.19649/) (2024)

## Abstract (arXiv)

Low-dimensional node embeddings play a key role in analyzing graph datasets. However, little work studies exactly what information is encoded by popular embedding methods, and how this information correlates with performance in downstream machine learning tasks. We tackle this question by studying whether embeddings can be inverted to (approximately) recover the graph used to generate them. Focusing on a variant of the popular DeepWalk method (Perozzi et al., 2014; Qiu et al., 2018), we present algorithms for accurate embedding inversion - i.e., from the low-dimensional embedding of a graph G, we can find a graph H with a very similar embedding. We perform numerous experiments on real-world networks, observing that significant information about G, such as specific edges and bulk properties like triangle density, is often lost in H. However, community structure is often preserved or even enhanced. Our findings are a step towards a more rigorous understanding of exactly what information embeddings encode about the input graph, and why this information is useful for learning tasks.