On the Interplay between Strong Regularity and 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.

In Graph-Based Representations in Pattern Recognition
Alessandro Torcinovich
Alessandro Torcinovich
Postdoc in Machine Learning

My research interests include Game Theoretic, Deep and Weakly Supervised Learning