<html><head><meta http-equiv="Content-Type" content="text/html; charset=utf-8"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" class=""><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">This is a reminder for Xifan Yu's MS Presentation. Xifan is a student in the Bx/MS program.</div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">Please note the updated day and time.</div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><font color="#000000" class="">—————————————————————————————————————————————————————————</font></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><span class=""><br class=""></span></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><span class=""><b class="">Date:</b> Wednesday, May 25, 2021</span></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><span class=""><br class=""></span></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><span class=""><b class="">Time:</b> 1 PM, CST</span></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><span class=""><br class=""></span></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><span class=""><b class="">Location:</b> remote via Zoom <</span><a href="https://uchicago.zoom.us/j/96293823778?pwd=VlBxRm1xQzZVb2tLc25SU3B2STE0dz09" class="">https://uchicago.zoom.us/j/96293823778?pwd=VlBxRm1xQzZVb2tLc25SU3B2STE0dz09</a>></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><span class=""><br class="">Meeting ID: 962 9382 3778<br class="">Passcode: 589243</span></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><b class="">M.S. Candidate:</b> Xifan Yu</div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><b class="">M.S. Paper Title:</b> Anomaly Detection on Connected Subgraphs via Constant-factor Approximation Algorithms for the Elevated Mean Problem</div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><b class="">Advisor:</b> Lorenzo Orecchia</div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><b class="">Committee Members:</b> Lorenzo Orecchia, Rebecca Willet, Laszlo Babai</div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><b class="">Abstract:</b></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">---------------------------------------------------------------------------------</div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">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.</div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br class="">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. </div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br class="">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.</div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);">—————————————————————————————————————————————</div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"><br class=""></div><div class="" style="caret-color: rgb(0, 0, 0); color: rgb(0, 0, 0);"></div></body></html>