  Statistical analysis of large and sparse graphs is a challenging problem in
data science due to the high dimensionality and nonlinearity of the problem.
This paper presents a fast and scalable algorithm for partitioning such graphs
into disjoint groups based on observed graph distances from a set of reference
nodes. The resulting partition provides a low-dimensional approximation of the
full distance matrix which helps to reveal global structural properties of the
graph using only small samples of the distance matrix. The presented algorithm
is inspired by the information-theoretic minimum description principle. We
investigate the performance of this algorithm for selected real data sets and
for synthetic graph data sets generated using stochastic block models and
power-law random graphs, together with analytical considerations for sparse
stochastic block models with bounded average degrees.
