# LoNe Sampler: Graph node embeddings by coordinated local neighborhood sampling

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 33 references that are in the map.
- First posted on arXiv 28 Nov 2022.

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

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [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)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models](https://mlsanity.com/paper/2005.07959/) (2020)
- [VERSE: Versatile Graph Embeddings from Similarity Measures](https://mlsanity.com/paper/1803.04742/) (2018)
- [On Sampling from Massive Graph Streams](https://mlsanity.com/paper/1703.02625/) (2017)

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

- [Learning Graph Node Embeddings by Smooth Pair Sampling](https://mlsanity.com/paper/2501.12884/) (2025)
- [ffstruc2vec: Flat, Flexible and Scalable Learning of Node Representations from Structural Identities](https://mlsanity.com/paper/2504.01122/) (2025)

## Abstract (arXiv)

Local graph neighborhood sampling is a fundamental computational problem that is at the heart of algorithms for node representation learning. Several works have presented algorithms for learning discrete node embeddings where graph nodes are represented by discrete features such as attributes of neighborhood nodes. Discrete embeddings offer several advantages compared to continuous word2vec-like node embeddings: ease of computation, scalability, and interpretability. We present LoNe Sampler, a suite of algorithms for generating discrete node embeddings by Local Neighborhood Sampling, and address two shortcomings of previous work. First, our algorithms have rigorously understood theoretical properties. Second, we show how to generate approximate explicit vector maps that avoid the expensive computation of a Gram matrix for the training of a kernel model. Experiments on benchmark datasets confirm the theoretical findings and demonstrate the advantages of the proposed methods.