{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:43:47Z","timestamp":1787017427029,"version":"build-2736575974"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T00:00:00Z","timestamp":1641600000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2022,8,31]]},"abstract":"<jats:p>\n                    Given a stream of graph edges from a dynamic graph, how can we assign anomaly scores to edges in an online manner, for the purpose of detecting unusual behavior, using constant time and memory? Existing approaches aim to detect\n                    <jats:italic>individually surprising<\/jats:italic>\n                    edges.\n                  <\/jats:p>\n                  <jats:p>\n                    In this work, we propose\n                    <jats:sc>Midas<\/jats:sc>\n                    , which focuses on detecting\n                    <jats:italic>microcluster anomalies<\/jats:italic>\n                    , or suddenly arriving groups of suspiciously similar edges, such as lockstep behavior, including denial of service attacks in network traffic data. We further propose\n                    <jats:sc>Midas<\/jats:sc>\n                    -F, to solve the problem by which anomalies are incorporated into the algorithm\u2019s internal states, creating a \u201cpoisoning\u201d effect that can allow future anomalies to slip through undetected.\n                    <jats:sc>Midas<\/jats:sc>\n                    -F introduces two modifications: (1) we modify the anomaly scoring function, aiming to reduce the \u201cpoisoning\u201d effect of newly arriving edges; (2) we introduce a conditional merge step, which updates the algorithm\u2019s data structures after each time tick, but only if the anomaly score is below a threshold value, also to reduce the \u201cpoisoning\u201d effect. Experiments show that\n                    <jats:sc>Midas<\/jats:sc>\n                    -F has significantly higher accuracy than\n                    <jats:sc>Midas<\/jats:sc>\n                    .\n                  <\/jats:p>\n                  <jats:p>In general, the algorithms proposed in this work have the following properties: (a) they detects microcluster anomalies while providing theoretical guarantees about the false positive probability; (b) they are online, thus processing each edge in constant time and constant memory, and also processes the data orders-of-magnitude faster than state-of-the-art approaches; and (c) they provides up to 62% higher area under the receiver operating characteristic curve than state-of-the-art approaches.<\/jats:p>","DOI":"10.1145\/3494564","type":"journal-article","created":{"date-parts":[[2022,1,8]],"date-time":"2022-01-08T15:51:00Z","timestamp":1641657060000},"page":"1-22","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Real-Time Anomaly Detection in Edge Streams"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4175-3565","authenticated-orcid":false,"given":"Siddharth","family":"Bhatia","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rui","family":"Liu","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bryan","family":"Hooi","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Minji","family":"Yoon","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kijung","family":"Shin","sequence":"additional","affiliation":[{"name":"KAIST, Yuseong-gu, Daejeon, Republic of Korea"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA, United States"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,1,8]]},"reference":[{"key":"e_1_3_2_2_2","volume-title":"SDM","author":"Aggarwal Charu C.","year":"2010","unstructured":"Charu C. Aggarwal, Yuchen Zhao, and Philip S. Yu. 2010. On clustering graph streams. In SDM."},{"key":"e_1_3_2_3_2","volume-title":"ICDE","author":"Aggarwal Charu C.","year":"2011","unstructured":"Charu C. Aggarwal, Yuchen Zhao, and Philip S. Yu. 2011. Outlier detection in graph streams. In ICDE."},{"key":"e_1_3_2_4_2","volume-title":"PAKDD","author":"Akoglu Leman","year":"2010","unstructured":"Leman Akoglu, Mary McGlohon, and Christos Faloutsos. 2010. Oddball: Spotting anomalies in weighted graphs. In PAKDD."},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0365-y"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2946966"},{"key":"e_1_3_2_7_2","volume-title":"IEEE Big Data","author":"Bahri Maroua","year":"2018","unstructured":"Maroua Bahri, Silviu Maniu, and Albert Bifet. 2018. A sketch-based naive Bayes algorithms for evolving data streams. In IEEE Big Data."},{"key":"e_1_3_2_8_2","volume-title":"KDD","author":"Belth Caleb","year":"2020","unstructured":"Caleb Belth, Xinyi Zheng, and Danai Koutra. 2020. Mining persistent activity in continually evolving networks. In KDD."},{"key":"e_1_3_2_9_2","volume-title":"WWW","author":"Beutel Alex","year":"2013","unstructured":"Alex Beutel, Wanhong Xu, Venkatesan Guruswami, Christopher Palow, and Christos Faloutsos. 2013. Copycatch: Stopping group attacks by spotting lockstep behavior in social networks. In WWW."},{"key":"e_1_3_2_10_2","volume-title":"AAAI","author":"Bhatia Siddharth","year":"2020","unstructured":"Siddharth Bhatia, Bryan Hooi, Minji Yoon, Kijung Shin, and Christos Faloutsos. 2020. MIDAS: Microcluster-based detector of anomalies in edge streams. In AAAI."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2017.11.023"},{"key":"e_1_3_2_12_2","volume-title":"SDM","author":"Bogdanov Petko","year":"2013","unstructured":"Petko Bogdanov, Christos Faloutsos, Misael Mongiov\u00ec, Evangelos E. Papalexakis, Razvan Ranca, and Ambuj K. Singh. 2013. NetSpot: Spotting significant anomalous regions on dynamic networks. In SDM."},{"key":"e_1_3_2_13_2","article-title":"Series2graph: Graph-based subsequence anomaly detection for time series","author":"Boniol Paul","year":"2020","unstructured":"Paul Boniol and Themis Palpanas. 2020. Series2graph: Graph-based subsequence anomaly detection for time series. Proceedings of the VLDB Endowment 13, 12 (2020), 1821\u20131834.","journal-title":"Proceedings of the VLDB Endowment"},{"key":"e_1_3_2_14_2","volume-title":"PKDD","author":"Chakrabarti Deepayan","year":"2004","unstructured":"Deepayan Chakrabarti. 2004. Autopart: Parameter-free graph partitioning and outlier detection. In PKDD."},{"key":"e_1_3_2_15_2","volume-title":"WSDM","author":"Chang Yen-Yu","year":"2021","unstructured":"Yen-Yu Chang, Pan Li, Rok Sosic, M. H. Afifi, Marco Schweighauser, and Jure Leskovec. 2021. F-FADE: Frequency factorization for anomaly detection in edge streams. In WSDM."},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.001"},{"key":"e_1_3_2_17_2","volume-title":"ICDM","author":"Eswaran Dhivya","year":"2018","unstructured":"Dhivya Eswaran and Christos Faloutsos. 2018. Sedanspot: Detecting anomalies in edge streams. In ICDM."},{"key":"e_1_3_2_18_2","volume-title":"KDD","author":"Eswaran Dhivya","year":"2018","unstructured":"Dhivya Eswaran, Christos Faloutsos, Sudipto Guha, and Nina Mishra. 2018. SpotLight: Detecting anomalies in streaming graphs. In KDD."},{"key":"e_1_3_2_19_2","article-title":"A survey of community search over big graphs","author":"Fang Yixiang","year":"2020","unstructured":"Yixiang Fang, Xin Huang, Lu Qin, Ying Zhang, Wenjie Zhang, Reynold Cheng, and Xuemin Lin. 2020. A survey of community search over big graphs. The VLDB Journal 29, 1 (2020), 353\u2013392.","journal-title":"The VLDB Journal"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cose.2014.05.011"},{"key":"e_1_3_2_21_2","volume-title":"KDD","author":"Gupta Manish","year":"2012","unstructured":"Manish Gupta, Jing Gao, Yizhou Sun, and Jiawei Han. 2012. Integrating community matching and outlier detection for mining evolutionary community outliers. In KDD."},{"key":"e_1_3_2_22_2","volume-title":"BIGCOMP","author":"He Liang","year":"2015","unstructured":"Liang He, Bin Shao, Yatao Li, and Enhong Chen. 2015. Distributed real-time knowledge graph serving. In BIGCOMP."},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/3056563"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746403"},{"key":"e_1_3_2_25_2","article-title":"Composite hashing for data stream sketches","volume":"1808","author":"Khan Arijit","year":"2018","unstructured":"Arijit Khan and Sixing Yan. 2018. Composite hashing for data stream sketches. ArXiv abs\/1808.06800 (2018).","journal-title":"ArXiv"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_3_2_27_2","volume-title":"SDM","author":"Koutra Danai","year":"2013","unstructured":"Danai Koutra, Joshua T. Vogelstein, and Christos Faloutsos. 2013. Deltacon: A principled massive-graph similarity function. In SDM."},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-010-0342-8"},{"key":"e_1_3_2_29_2","article-title":"Network-based anomaly detection for insider trading","volume":"1702","author":"Kulkarni Adarsh","year":"2017","unstructured":"Adarsh Kulkarni, Priya Mani, and Carlotta Domeniconi. 2017. Network-based anomaly detection for insider trading. ArXiv abs\/1702.05809 (2017).","journal-title":"ArXiv"},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3012608"},{"key":"e_1_3_2_31_2","volume-title":"Recent Advances in Intrusion Detection","author":"Lippmann Richard","year":"1999","unstructured":"Richard Lippmann, Robert K. Cunningham, David J. Fried, Isaac Graf, Kris R. Kendall, Seth E. Webster, and Marc A. Zissman. 1999. Results of the DARPA 1998 offline intrusion detection evaluation. In Recent Advances in Intrusion Detection."},{"key":"e_1_3_2_32_2","volume-title":"KDD","author":"Luo Wenjuan","year":"2020","unstructured":"Wenjuan Luo, Han Zhang, Xiaodi Yang, Lin Bo, Xiaoqing Yang, Zang Li, Xiaohu Qie, and Jieping Ye. 2020. Dynamic heterogeneous graph neural network for real-time event prediction. In KDD."},{"key":"e_1_3_2_33_2","volume-title":"MilCIS","author":"Moustafa Nour","year":"2015","unstructured":"Nour Moustafa and Jill Slay. 2015. UNSW-NB15: A comprehensive data set for network intrusion detection systems (UNSW-NB15 network data set). In MilCIS."},{"key":"e_1_3_2_34_2","volume-title":"AAAI","author":"Mu Xin","year":"2017","unstructured":"Xin Mu, Feida Zhu, Juan Du, Ee-Peng Lim, and Zhi-Hua Zhou. 2017. Streaming classification with emerging new class by class matrix sketching. In AAAI."},{"key":"e_1_3_2_35_2","volume-title":"ICDM","author":"Nakamura Takaaki","year":"2020","unstructured":"Takaaki Nakamura, Makoto Imamura, Ryan Mercer, and Eamonn Keogh. 2020. MERLIN: Parameter-free discovery of arbitrary length anomalies in massive time series archives. In ICDM."},{"key":"e_1_3_2_36_2","volume-title":"KDD","author":"Noble Caleb C.","year":"2003","unstructured":"Caleb C. Noble and Diane J. Cook. 2003. Graph-based anomaly detection. In KDD."},{"key":"e_1_3_2_37_2","volume-title":"SDM","author":"Ranshous Stephen","year":"2016","unstructured":"Stephen Ranshous, Steve Harenberg, Kshitij Sharma, and Nagiza F. Samatova. 2016. A scalable approach for outlier detection in edge streams using sketch-based approximations. In SDM."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/2890508"},{"key":"e_1_3_2_39_2","volume-title":"ICDE","author":"Rusu Florin","year":"2009","unstructured":"Florin Rusu and Alin Dobra. 2009. Sketching sampled data streams. In ICDE."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1140\/epjds\/s13688-020-00233-y"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-018-0602-x"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-017-1077-6"},{"key":"e_1_3_2_43_2","article-title":"DenseAlert: Incremental dense-subtensor detection in tensor streams","author":"Shin Kijung","year":"2017","unstructured":"Kijung Shin, Bryan Hooi, Jisu Kim, and Christos Faloutsos. 2017. DenseAlert: Incremental dense-subtensor detection in tensor streams. In KDD.","journal-title":"KDD"},{"key":"e_1_3_2_44_2","volume-title":"SIGMOD","author":"Sricharan Kumar","year":"2014","unstructured":"Kumar Sricharan and Kamalika Das. 2014. Localizing anomalous changes in time-evolving graphs. In SIGMOD."},{"key":"e_1_3_2_45_2","volume-title":"KDD","author":"Sun Jimeng","year":"2007","unstructured":"Jimeng Sun, Christos Faloutsos, Spiros Papadimitriou, and Philip S. Yu. 2007. GraphScope: Parameter-free mining of large time-evolving graphs. In KDD."},{"key":"e_1_3_2_46_2","volume-title":"KDD","author":"Sun Jimeng","year":"2006","unstructured":"Jimeng Sun, Dacheng Tao, and Christos Faloutsos. 2006. Beyond streams and graphs: Dynamic tensor analysis. In KDD."},{"key":"e_1_3_2_47_2","volume-title":"SDM","author":"Tong Hanghang","year":"2011","unstructured":"Hanghang Tong and Ching-Yung Lin. 2011. Non-negative residual matrix factorization with application to graph anomaly detection. In SDM."},{"key":"e_1_3_2_48_2","volume-title":"ICDE","author":"Yan Da","year":"2020","unstructured":"Da Yan, Guimu Guo, Md Mashiur Rahman Chowdhury, M. Tamer \u00d6zsu, Wei-Shinn Ku, and John C. S. Lui. 2020. G-thinker: A distributed framework for mining subgraphs in a big graph. In ICDE."},{"key":"e_1_3_2_49_2","volume-title":"KDD","author":"Yoon Minji","year":"2019","unstructured":"Minji Yoon, Bryan Hooi, Kijung Shin, and Christos Faloutsos. 2019. Fast and accurate anomaly detection in dynamic graphs with a two-pronged approach. In KDD."},{"key":"e_1_3_2_50_2","volume-title":"ICDM","author":"Yu Weiren","year":"2013","unstructured":"Weiren Yu, Charu C. Aggarwal, Shuai Ma, and Haixun Wang. 2013. On anomalous hotspot discovery in graph streams. In ICDM."}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494564","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3494564","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T15:31:16Z","timestamp":1750174276000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3494564"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,1,8]]},"references-count":49,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,8,31]]}},"alternative-id":["10.1145\/3494564"],"URL":"https:\/\/doi.org\/10.1145\/3494564","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,1,8]]},"assertion":[{"value":"2021-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}