  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.
