Abstract
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. As it turns out graph densification exhibits rich connections to a set of interesting and sometimes seemingly unrelated questions in graph theory and metric embeddings. In particular we show the following results: • A graph G has a multiplicative cut approximation with an asymptotically increased density if and only if it does not embed into l 1 under a weak notion of embeddability. We demonstrate that all planar graphs as well as random geometric graphs possess such embeddings and thus do not have densifiers. On the other hand, expanders do have densifiers (namely, the complete graph) and as a result do not embed into l 1 even under our weak notion of embedding. • An analogous characterization is true for multiplicative spectral approximations where the embedding is into l 22. Using this characterization we expose a surprisingly close connection between multiplicative spectral and multiplicative cut densifiers. • We also consider additive cut and spectral approximations. We exhibit graphs that do not possess non-trivial additive densifiers. Our results are mainly based on linear and semidefinite programs (and their duals) for computing the maximum weight densifier of a given graph. This also leads to efficient algorithms in the case of spectral densifiers and additive cut densifiers. © 2012 ACM.