Finding Dense Subgraphs via Low-Rank Bilinear Optimization
Dimitris Papailiopoulos, Ioannis Mitliagkas, Alexandros G. Dimakis, Constantine Caramanis · 2014
Given a graph, the Densest k-Subgraph (DkS) problem asks for the subgraph on k vertices that contains the largest number of edges. In this work, we develop a new algorithm for DkS that searches a low-dimensional space for provably dense subgraphs. Our algorithm comes with novel performance bounds that depend on the graph spectrum. Our graph-dependent bounds are surprisingly tight for real-world graphs where we find subgraphs with density provably within 70 % of the optimum. These guarantees are sig-nificantly tighter than the best available worst case a priori bounds. Our algorithm runs in nearly linear time, un-der spectral assumptions satisfied by most graphs found in applications. Moreover, it is highly scalable and parallelizable. We demonstrate this by implementing it in MapReduce and execut-ing numerous experiments on massive real-world graphs that have up to billions of edges. We em-pirically show that our algorithm can find sub-graphs of significantly higher density compared to the previous state of the art. 1.