Graph densification
Moritz Hardt, Nikhil Srivastava, Madhur Tulsiani · 2012
We initiate a principled study of graph densification. Given a graph G the goal of graph densification is to come up with another graph H that has significantly more edges than G but nevertheless approximates G well with respect to some set of test functions. In this paper we focus on the case of cut and spectral approximations.