# Graph Vertex Embeddings: Distance, Regularization and Community Detection

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 58 references that are in the map.
- First posted on arXiv 9 Apr 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Distributed Representations of Words and Phrases and their Compositionality](https://mlsanity.com/paper/1310.4546/) (2013)
- [UMAP: Uniform Manifold Approximation and Projection for Dimension Reduction](https://mlsanity.com/paper/1802.03426/) (2018)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Distributed Representations of Sentences and Documents](https://mlsanity.com/paper/1405.4053/) (2014)
- [Representation Tradeoffs for Hyperbolic Embeddings](https://mlsanity.com/paper/1804.03329/) (2018)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Deep Subspace Clustering Networks](https://mlsanity.com/paper/1709.02508/) (2017)
- [Mean Shift for Self-Supervised Learning](https://mlsanity.com/paper/2105.07269/) (2021)
- [Graph Kernels: State-of-the-Art and Future Challenges](https://mlsanity.com/paper/2011.03854/) (2020)
- [A Comprehensive Survey on Community Detection with Deep Learning](https://mlsanity.com/paper/2105.12584/) (2021)
- [Neural Embeddings of Graphs in Hyperbolic Space](https://mlsanity.com/paper/1705.10359/) (2017)
- [Attraction-Repulsion Spectrum in Neighbor Embeddings](https://mlsanity.com/paper/2007.08902/) (2020)
- [Network Medicine Framework for Identifying Drug Repurposing Opportunities for COVID-19](https://mlsanity.com/paper/2004.07229/) (2020)
- [Minimum-Distortion Embedding](https://mlsanity.com/paper/2103.02559/) (2021)
- [Systematic comparison of graph embedding methods in practical tasks](https://mlsanity.com/paper/2106.10198/) (2021)

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

- [GeoGAE: Scalable Graph-Level Autoencoding via Hyperball Cloud Representations](https://mlsanity.com/paper/2609.35527/) (2026)

## Abstract (arXiv)

Graph embeddings have emerged as a powerful tool for representing complex network structures in a low-dimensional space, enabling the use of efficient methods that employ the metric structure in the embedding space as a proxy for the topological structure of the data. In this paper, we explore several aspects that affect the quality of a vertex embedding of graph-structured data. To this effect, we first present a family of flexible distance functions that faithfully capture the topological distance between different vertices. Secondly, we analyze vertex embeddings as resulting from a fitted transformation of the distance matrix rather than as a direct result of optimization. Finally, we evaluate the effectiveness of our proposed embedding constructions by performing community detection on a host of benchmark datasets. The reported results are competitive with classical algorithms that operate on the entire graph while benefitting from a substantially reduced computational complexity due to the reduced dimensionality of the representations.