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 = {Papailiopoulos, Dimitris and Mitliagkas, Ioannis and Dimakis, Alexandros and Caramanis, Constantine}, booktitle = {Proceedings of the 31st International Conference on Machine Learning}, pages = {1890--1898}, year = {2014}, editor = {Xing, Eric P. and Jebara, Tony}, 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 = {https://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 %P 1890--1898 %U https://proceedings.mlr.press/v32/papailiopoulos14.html %V 32 %N 2 %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 DA - 2014/06/18 ED - Eric P. Xing ED - Tony Jebara ID - pmlr-v32-papailiopoulos14 PB - PMLR DP - Proceedings of Machine Learning Research VL - 32 IS - 2 SP - 1890 EP - 1898 L1 - http://proceedings.mlr.press/v32/papailiopoulos14.pdf UR - https://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 Proceedings of Machine Learning Research 32(2):1890-1898 Available from https://proceedings.mlr.press/v32/papailiopoulos14.html.

Related Material