On the Interplay between Strong Regularity and Graph Densification