Connected subgraph detection with mirror descent on SDPs

Files
aksoylar17a.pdf(614.23 KB)
Published version
Date
2017
DOI
Authors
Aksoylar, Cem
Orecchia, Lorenzo
Saligrama, Venkatesh
Version
OA Version
Published version
Citation
Cem Aksoylar, Lorenzo Orecchia, Venkatesh Saligrama. 2017. "Connected Subgraph Detection with Mirror Descent on SDPs." International Conference on Machine Learning. International Conference on Machine Learning
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.
Description
License