Finding Dense Subgraphs via Low-Rank Bilinear Optimization

Dimitris Papailiopoulos, Ioannis Mitliagkas, Alexandros Dimakis, Constantine Caramanis
; Proceedings of the 31st International Conference on Machine Learning, PMLR 32(2):1890-1898, 2014.

Abstract

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 novel algorithm for \DkS that searches a low-dimensional space for provably good solutions. We obtain provable performance bounds that depend on the graph spectrum. One of our results is that if there exists a k-subgraph that contains a constant fraction of all the edges, we can approximate \DkS within a factor arbitrarily close to two in polynomial time. Our algorithm runs in nearly linear time, under 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 executing numerous experiments on massive real-world graphs that have up to billions of edges. We empirically show that our algorithm can find subgraphs of significantly higher density compared to the previous state of the art.

Cite this Paper


BibTeX
@InProceedings{pmlr-v32-papailiopoulos14, title = {Finding Dense Subgraphs via Low-Rank Bilinear Optimization}, author = {Dimitris Papailiopoulos and Ioannis Mitliagkas and Alexandros Dimakis and Constantine Caramanis}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1890--1898}, year = {2014}, editor = {Eric P. Xing and Tony Jebara}, volume = {32}, number = {2}, series = {Proceedings of Machine Learning Research}, address = {Bejing, China}, month = {22--24 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v32/papailiopoulos14.pdf}, url = {http://proceedings.mlr.press/v32/papailiopoulos14.html}, abstract = {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 novel algorithm for \DkS that searches a low-dimensional space for provably good solutions. We obtain provable performance bounds that depend on the graph spectrum. One of our results is that if there exists a k-subgraph that contains a constant fraction of all the edges, we can approximate \DkS within a factor arbitrarily close to two in polynomial time. Our algorithm runs in nearly linear time, under 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 executing numerous experiments on massive real-world graphs that have up to billions of edges. We empirically show that our algorithm can find subgraphs of significantly higher density compared to the previous state of the art.} }
Endnote
%0 Conference Paper %T Finding Dense Subgraphs via Low-Rank Bilinear Optimization %A Dimitris Papailiopoulos %A Ioannis Mitliagkas %A Alexandros Dimakis %A Constantine Caramanis %B Proceedings of the 31st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2014 %E Eric P. Xing %E Tony Jebara %F pmlr-v32-papailiopoulos14 %I PMLR %J Proceedings of Machine Learning Research %P 1890--1898 %U http://proceedings.mlr.press %V 32 %N 2 %W PMLR %X 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 novel algorithm for \DkS that searches a low-dimensional space for provably good solutions. We obtain provable performance bounds that depend on the graph spectrum. One of our results is that if there exists a k-subgraph that contains a constant fraction of all the edges, we can approximate \DkS within a factor arbitrarily close to two in polynomial time. Our algorithm runs in nearly linear time, under 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 executing numerous experiments on massive real-world graphs that have up to billions of edges. We empirically show that our algorithm can find subgraphs of significantly higher density compared to the previous state of the art.
RIS
TY - CPAPER TI - Finding Dense Subgraphs via Low-Rank Bilinear Optimization AU - Dimitris Papailiopoulos AU - Ioannis Mitliagkas AU - Alexandros Dimakis AU - Constantine Caramanis BT - Proceedings of the 31st International Conference on Machine Learning PY - 2014/01/27 DA - 2014/01/27 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-papailiopoulos14 PB - PMLR SP - 1890 DP - PMLR EP - 1898 L1 - http://proceedings.mlr.press/v32/papailiopoulos14.pdf UR - http://proceedings.mlr.press/v32/papailiopoulos14.html AB - 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 novel algorithm for \DkS that searches a low-dimensional space for provably good solutions. We obtain provable performance bounds that depend on the graph spectrum. One of our results is that if there exists a k-subgraph that contains a constant fraction of all the edges, we can approximate \DkS within a factor arbitrarily close to two in polynomial time. Our algorithm runs in nearly linear time, under 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 executing numerous experiments on massive real-world graphs that have up to billions of edges. We empirically show that our algorithm can find subgraphs of significantly higher density compared to the previous state of the art. ER -
APA
Papailiopoulos, D., Mitliagkas, I., Dimakis, A. & Caramanis, C.. (2014). Finding Dense Subgraphs via Low-Rank Bilinear Optimization. Proceedings of the 31st International Conference on Machine Learning, in PMLR 32(2):1890-1898

Related Material