# InfiniteWalk: Deep Network Embeddings as Laplacian Embeddings with a Nonlinearity

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2020.

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

- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Generalizable Cross-Graph Embedding for GNN-based Congestion Prediction](https://mlsanity.com/paper/2111.05941/) (2021)
- [A Broader Picture of Random-walk Based Graph Embedding](https://mlsanity.com/paper/2110.12344/) (2021)
- [Learning Graph Meta Embeddings for Cold-Start Ads in Click-Through Rate Prediction](https://mlsanity.com/paper/2105.08909/) (2021)
- [A Graph is Worth K Words: Euclideanizing Graph using Pure Transformer](https://mlsanity.com/paper/2402.02464/) (2024)
- [Node Proximity Is All You Need: Unified Structural and Positional Node and Graph Embedding](https://mlsanity.com/paper/2102.13582/) (2021)
- [Spectral Augmentations for Graph Contrastive Learning](https://mlsanity.com/paper/2302.02909/) (2023)
- [DeepWalking Backwards: From Embeddings Back to Graphs](https://mlsanity.com/paper/2102.08532/) (2021)
- [Learning Based Proximity Matrix Factorization for Node Embedding](https://mlsanity.com/paper/2106.05476/) (2021)
- [GraphScale: A Framework to Enable Machine Learning over Billion-node Graphs](https://mlsanity.com/paper/2407.15452/) (2024)
- [From Anchors to Answers: A Novel Node Tokenizer for Integrating Graph Structure into Large Language Models](https://mlsanity.com/paper/2410.10743/) (2024)
- [Multiple Kernel Representation Learning on Networks](https://mlsanity.com/paper/2106.05057/) (2021)
- [Free Energy Node Embedding via Generalized Skip-gram with Negative Sampling](https://mlsanity.com/paper/2105.09182/) (2021)
- [TANGNN: a Concise, Scalable and Effective Graph Neural Networks with Top-m Attention Mechanism for Graph Representation Learning](https://mlsanity.com/paper/2411.15458/) (2024)
- [On the Use of Unrealistic Predictions in Hundreds of Papers Evaluating Graph Representations](https://mlsanity.com/paper/2112.04274/) (2021)
- [Disentangled and Self-Explainable Node Representation Learning](https://mlsanity.com/paper/2410.21043/) (2024)
- [A flexible PageRank-based graph embedding framework closely related to spectral eigenvector embeddings](https://mlsanity.com/paper/2207.11321/) (2022)
- [Towards Deeper Understanding of PPR-based Embedding Approaches: A Topological Perspective](https://mlsanity.com/paper/2405.19649/) (2024)
- [Convergence Guarantees for the DeepWalk Embedding on Block Models](https://mlsanity.com/paper/2410.20248/) (2024)

## Abstract (arXiv)

The skip-gram model for learning word embeddings (Mikolov et al. 2013) has been widely popular, and DeepWalk (Perozzi et al. 2014), among other methods, has extended the model to learning node representations from networks. Recent work of Qiu et al. (2018) provides a closed-form expression for the DeepWalk objective, obviating the need for sampling for small datasets and improving accuracy. In these methods, the "window size" T within which words or nodes are considered to co-occur is a key hyperparameter. We study the objective in the limit as T goes to infinity, which allows us to simplify the expression of Qiu et al. We prove that this limiting objective corresponds to factoring a simple transformation of the pseudoinverse of the graph Laplacian, linking DeepWalk to extensive prior work in spectral graph embeddings. Further, we show that by a applying a simple nonlinear entrywise transformation to this pseudoinverse, we recover a good approximation of the finite-T objective and embeddings that are competitive with those from DeepWalk and other skip-gram methods in multi-label classification. Surprisingly, we find that even simple binary thresholding of the Laplacian pseudoinverse is often competitive, suggesting that the core advancement of recent methods is a nonlinearity on top of the classical spectral embedding approach.