On the Interplay between Strong Regularity and Graph Densification
This work addresses metric preservation in large graphs for applications like network analysis, but it appears incremental as it builds on existing regularity lemma concepts.
The paper tackled the problem of preserving metric information in large graphs using Szemerédi's regularity lemma, and found that a heuristic algorithm for regular partitions is robust to sparsification, with robustness enhanced by graph densification.
In this paper we analyze the practical implications of Szemerédi'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.