Timezone: »

Connected Subgraph Detection with Mirror Descent on SDPs
Cem Aksoylar · Orecchia Lorenzo · Venkatesh Saligrama

Mon Aug 07 01:30 AM -- 05:00 AM (PDT) @ Gallery #78

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.

Author Information

Cem Aksoylar
Orecchia Lorenzo (Boston)
Venkatesh Saligrama (Boston University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors