# A Hierarchical Block Distance Model for Ultra Low-Dimensional Graph Representations

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 100 references that are in the map.
- First posted on arXiv 12 Apr 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [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)
- [Network Embedding as Matrix Factorization: Unifying DeepWalk, LINE, PTE, and node2vec](https://mlsanity.com/paper/1710.02971/) (2017)
- [Network Representation Learning: A Survey](https://mlsanity.com/paper/1801.05852/) (2017)
- [Neural Embeddings of Graphs in Hyperbolic Space](https://mlsanity.com/paper/1705.10359/) (2017)
- [HARP: Hierarchical Representation Learning for Networks](https://mlsanity.com/paper/1706.07845/) (2017)
- [NetSMF: Large-Scale Network Embedding as Sparse Matrix Factorization](https://mlsanity.com/paper/1906.11156/) (2019)
- [Hierarchical Block Structures and High-resolution Model Selection in Large Networks](https://mlsanity.com/paper/1310.4377/) (2013)
- [Latent Space Models for Dynamic Networks](https://mlsanity.com/paper/2005.08808/) (2020)
- [Billion-scale Network Embedding with Iterative Random Projection](https://mlsanity.com/paper/1805.02396/) (2018)
- [Scalable Link Prediction in Dynamic Networks via Non-Negative Matrix Factorization](https://mlsanity.com/paper/1411.3675/) (2014)
- [Node Embeddings and Exact Low-Rank Representations of Complex Networks](https://mlsanity.com/paper/2006.05592/) (2020)
- [A Review of Dynamic Network Models with Latent Variables](https://mlsanity.com/paper/1711.10421/) (2017)
- [Hierarchical community detection by recursive partitioning](https://mlsanity.com/paper/1810.01509/) (2018)
- [The Geometry of Continuous Latent Space Models for Network Data](https://mlsanity.com/paper/1712.08641/) (2017)
- [Modeling heterogeneity in random graphs through latent space models: a selective review](https://mlsanity.com/paper/1402.4296/) (2014)
- [BiasedWalk: Biased Sampling for Representation Learning on Graphs](https://mlsanity.com/paper/1809.02482/) (2018)
- [A Review of Latent Space Models for Social Networks](https://mlsanity.com/paper/2012.02307/) (2020)
- [Exponential Family Graph Embeddings](https://mlsanity.com/paper/1911.09007/) (2019)
- [The Infinite Degree Corrected Stochastic Block Model](https://mlsanity.com/paper/1311.2520/) (2013)

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

- [Piecewise-Velocity Model for Learning Continuous-time Dynamic Node Representations](https://mlsanity.com/paper/2212.12345/) (2022)
- [Characterizing Polarization in Social Networks using the Signed Relational Latent Distance Model](https://mlsanity.com/paper/2301.09507/) (2023)
- [Continuous-time Graph Representation with Sequential Survival Process](https://mlsanity.com/paper/2312.13068/) (2023)
- [How Low Can You Go? Searching for the Intrinsic Dimensionality of Complex Networks using Metric Node Embeddings](https://mlsanity.com/paper/2503.01723/) (2025)
- [Aitchison Embeddings for Learning Compositional Graph Representations](https://mlsanity.com/paper/2605.00716/) (2026)
- [Rank Is Not Capacity: Spectral Occupancy for Latent Graph Models](https://mlsanity.com/paper/2605.11142/) (2026)
- [A Hybrid Membership Latent Distance Model for Unsigned and Signed Integer Weighted Networks](https://mlsanity.com/paper/2308.15293/) (2023)
- [Time to Cite: Modeling Citation Networks using the Dynamic Impact Single-Event Embedding Model](https://mlsanity.com/paper/2403.00032/) (2024)
- [Archetypal Graph Generative Models: Explainable and Identifiable Communities via Anchor-Dominant Convex Hulls](https://mlsanity.com/paper/2602.21342/) (2026)

## Abstract (arXiv)

Graph Representation Learning (GRL) has become central for characterizing structures of complex networks and performing tasks such as link prediction, node classification, network reconstruction, and community detection. Whereas numerous generative GRL models have been proposed, many approaches have prohibitive computational requirements hampering large-scale network analysis, fewer are able to explicitly account for structure emerging at multiple scales, and only a few explicitly respect important network properties such as homophily and transitivity. This paper proposes a novel scalable graph representation learning method named the Hierarchical Block Distance Model (HBDM). The HBDM imposes a multiscale block structure akin to stochastic block modeling (SBM) and accounts for homophily and transitivity by accurately approximating the latent distance model (LDM) throughout the inferred hierarchy. The HBDM naturally accommodates unipartite, directed, and bipartite networks whereas the hierarchy is designed to ensure linearithmic time and space complexity enabling the analysis of very large-scale networks. We evaluate the performance of the HBDM on massive networks consisting of millions of nodes. Importantly, we find that the proposed HBDM framework significantly outperforms recent scalable approaches in all considered downstream tasks. Surprisingly, we observe superior performance even imposing ultra-low two-dimensional embeddings facilitating accurate direct and hierarchical-aware network visualization and interpretation.