Connected Subgraph Detection with Mirror Descent on SDPs

Cem Aksoylar, Lorenzo Orecchia, Venkatesh Saligrama
Proceedings of the 34th International Conference on Machine Learning, PMLR 70:51-59, 2017.

Abstract

We propose a novel, computationally efficient mirror-descent based optimization framework for subgraph detection in graph-structured data. Our aim is to discover anomalous patterns present in a connected subgraph of a given graph. This problem arises in many applications such as detection of network intrusions, community detection, detection of anomalous events in surveillance videos or disease outbreaks. Since optimization over connected subgraphs is a combinatorial and computationally difficult problem, we propose a convex relaxation that offers a principled approach to incorporating connectivity and conductance constraints on candidate subgraphs. We develop a novel efficient algorithm to solve the relaxed problem, establish convergence guarantees and demonstrate its feasibility and performance with experiments on real and very large simulated networks.

Cite this Paper

BibTeX
@InProceedings{pmlr-v70-aksoylar17a, title = {Connected Subgraph Detection with Mirror Descent on {SDP}s}, author = {Cem Aksoylar and Lorenzo Orecchia and Venkatesh Saligrama}, booktitle = {Proceedings of the 34th International Conference on Machine Learning}, pages = {51--59}, year = {2017}, editor = {Precup, Doina and Teh, Yee Whye}, volume = {70}, series = {Proceedings of Machine Learning Research}, month = {06--11 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v70/aksoylar17a/aksoylar17a.pdf}, url = {https://proceedings.mlr.press/v70/aksoylar17a.html}, abstract = {We propose a novel, computationally efficient mirror-descent based optimization framework for subgraph detection in graph-structured data. Our aim is to discover anomalous patterns present in a connected subgraph of a given graph. This problem arises in many applications such as detection of network intrusions, community detection, detection of anomalous events in surveillance videos or disease outbreaks. Since optimization over connected subgraphs is a combinatorial and computationally difficult problem, we propose a convex relaxation that offers a principled approach to incorporating connectivity and conductance constraints on candidate subgraphs. We develop a novel efficient algorithm to solve the relaxed problem, establish convergence guarantees and demonstrate its feasibility and performance with experiments on real and very large simulated networks.} }
Endnote
%0 Conference Paper %T Connected Subgraph Detection with Mirror Descent on SDPs %A Cem Aksoylar %A Lorenzo Orecchia %A Venkatesh Saligrama %B Proceedings of the 34th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2017 %E Doina Precup %E Yee Whye Teh %F pmlr-v70-aksoylar17a %I PMLR %P 51--59 %U https://proceedings.mlr.press/v70/aksoylar17a.html %V 70 %X We propose a novel, computationally efficient mirror-descent based optimization framework for subgraph detection in graph-structured data. Our aim is to discover anomalous patterns present in a connected subgraph of a given graph. This problem arises in many applications such as detection of network intrusions, community detection, detection of anomalous events in surveillance videos or disease outbreaks. Since optimization over connected subgraphs is a combinatorial and computationally difficult problem, we propose a convex relaxation that offers a principled approach to incorporating connectivity and conductance constraints on candidate subgraphs. We develop a novel efficient algorithm to solve the relaxed problem, establish convergence guarantees and demonstrate its feasibility and performance with experiments on real and very large simulated networks.
APA
Aksoylar, C., Orecchia, L. & Saligrama, V.. (2017). Connected Subgraph Detection with Mirror Descent on SDPs. Proceedings of the 34th International Conference on Machine Learning, in Proceedings of Machine Learning Research 70:51-59 Available from https://proceedings.mlr.press/v70/aksoylar17a.html.

Related Material