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

[Jessica Garza]

This is a reminder for Xifan Yu's MS Presentation. Xifan is a student in the Bx/MS program.

Please note the updated day and time.

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

Date: Wednesday, May 25, 2021

Time: 1 PM, CST

Location: remote via Zoom <https://uchicago.zoom.us/j/96293823778?pwd=VlBxRm1xQzZVb2tLc25SU3B2STE0dz09 <https://uchicago.zoom.us/j/96293823778?pwd=VlBxRm1xQzZVb2tLc25SU3B2STE0dz09>>

Meeting ID: 962 9382 3778
Passcode: 589243

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/20210524/7aa85743/attachment-0002.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: xifan_yu_MS_thesis_draft.pdf
Type: application/pdf
Size: 389261 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20210524/7aa85743/attachment-0001.pdf>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20210524/7aa85743/attachment-0003.html>