  In this paper we analyze the practical implications of Szemer\'edi's
regularity lemma in the preservation of metric information contained in large
graphs. To this end, we present a heuristic algorithm to find regular
partitions. Our experiments show that this method is quite robust to the
natural sparsification of proximity graphs. In addition, this robustness can be
enforced by graph densification.
