[Colloquium] Xifan Yu MS Presentation/May 26, 2021

[Jessica Garza]

This is an announcement of Xifan Yu's MS Presentation. Xifan is a student in the Bx/MS program.

Zoom details will follow.

————————————————————————————————————————————————————————————————————

Date: Wednesday, May 26, 2021

Time: 10 AM, CST

Location: remote via Zoom

M.S. Candidate: Xifan Yu

M.S. Paper Title: Anomaly Detection on Connected Subgraphs via Constant-factor Approximation Algorithms for the Elevated Mean Problem

Advisor: Lorenzo Orecchia

Committee Members: Lorenzo Orecchia, Rebecca Willet, Laszlo Babai


Abstract:
---------------------------------------------------------------------------------
In this paper, we study the Elevated Mean problem and the anomaly detection problem. In the anomaly detection problem,  there is a network with a certain measure of behaviors of the nodes, and the task is to distinguish whether the nodes behave as usual or an anomalous cluster exists based on observations of the nodes in the network. The anomaly detection problem has a wide range of applications such as sensor network intrusion detection and disease outbreak detection. For concreteness, we formulate the anomaly detection problem as a hypothesis testing problem, and assume the potential anomalous cluster forms a connected induced subgraph of the network.

The paper is structured into two parts. In the first part, we study the Elevated Mean problem, which is closely related to designing decision rules for the anomaly detection problem. We present two constant-factor approximation algorithms for the Elevated Mean problem and the k-Elevated Mean problem via black-box reductions to the Quota Prize-Collecting Steiner Tree problem and the Budget Prize-Collecting Steiner Tree problem. 

Using the constant-factor approximations for the Elevated Mean problem and the k-Elevated Mean problem in the first part, we show a polynomial time decision rule T_EM following the generalized likelihood ratio test schema based on the scan statistics of the Elevated Mean problem in the second part. Besides being polynomial time solvable, the strength of this decision rule also lies in its generality of detecting anomalous clusters among the class of connected induced subgraphs, without assuming parameters such as the shape or the internal conductance of the anomalous cluster as the previous work did. We also prove separability results using the rule T_EM.
------------------------------------------------------------------------------------------



Jessica Garza
Assistant Director of Undergraduate Studies
Department of Computer Science
The University of Chicago
Covid-19 Resources <https://cs.uchicago.edu/remote2020/>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20210512/7d03db25/attachment.html>