{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T12:07:50Z","timestamp":1777637270662,"version":"3.51.4"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,1,12]],"date-time":"2024-01-12T00:00:00Z","timestamp":1705017600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100007631","name":"Canadian Institute for Advanced Research","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007631","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Natural Sciences and Engineering Research Council of Canada (NSERC) Postgraduate Scholarship-Doctoral (PGS D) Award"},{"name":"Fonds de recherche du Qu\u00e9bec \u2013 Nature et Technologies (FRQNT) Doctoral Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2024,4,30]]},"abstract":"<jats:p>Dynamic graphs are rich data structures that are used to model complex relationships between entities over time. In particular, anomaly detection in temporal graphs is crucial for many real-world applications such as intrusion identification in network systems, detection of ecosystem disturbances, and detection of epidemic outbreaks. In this article, we focus on change point detection in dynamic graphs and address three main challenges associated with this problem: (i) how to compare graph snapshots across time, (ii) how to capture temporal dependencies, and (iii) how to combine different views of a temporal graph. To solve the above challenges, we first propose Laplacian Anomaly Detection (LAD) which uses the spectrum of graph Laplacian as the low dimensional embedding of the graph structure at each snapshot. LAD explicitly models short-term and long-term dependencies by applying two sliding windows. Next, we propose MultiLAD, a simple and effective generalization of LAD to multi-view graphs. MultiLAD provides the first change point detection method for multi-view dynamic graphs. It aggregates the singular values of the normalized graph Laplacian from different views through the scalar power mean operation. Through extensive synthetic experiments, we show that (i) LAD and MultiLAD are accurate and outperforms state-of-the-art baselines and their multi-view extensions by a large margin, (ii) MultiLAD\u2019s advantage over contenders significantly increases when additional views are available, and (iii) MultiLAD is highly robust to noise from individual views. In five real-world dynamic graphs, we demonstrate that LAD and MultiLAD identify significant events as top anomalies such as the implementation of government COVID-19 interventions which impacted the population mobility in multi-view traffic networks.<\/jats:p>","DOI":"10.1145\/3631609","type":"journal-article","created":{"date-parts":[[2023,11,6]],"date-time":"2023-11-06T11:27:36Z","timestamp":1699270056000},"page":"1-32","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":11,"title":["Laplacian Change Point Detection for Single and Multi-view Dynamic Graphs"],"prefix":"10.1145","volume":"18","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4526-7097","authenticated-orcid":false,"given":"Shenyang","family":"Huang","sequence":"first","affiliation":[{"name":"Mila, McGill University, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6061-3501","authenticated-orcid":false,"given":"Samy","family":"Coulombe","sequence":"additional","affiliation":[{"name":"McGill University, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2003-9338","authenticated-orcid":false,"given":"Yasmeen","family":"Hitti","sequence":"additional","affiliation":[{"name":"Mila, McGill University, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2348-0353","authenticated-orcid":false,"given":"Reihaneh","family":"Rabbany","sequence":"additional","affiliation":[{"name":"Mila, McGill University - CIFAR AI chair, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8090-2810","authenticated-orcid":false,"given":"Guillaume","family":"Rabusseau","sequence":"additional","affiliation":[{"name":"Mila and DIRO, Universit\u00e9 de Montr\u00e9al- CIFAR AI chair, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,1,12]]},"reference":[{"key":"e_1_3_3_2_2","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2006.881199"},{"key":"e_1_3_3_3_2","volume-title":"Proceedings of the Army Science Conference","author":"Akoglu Leman","year":"2010","unstructured":"Leman Akoglu and Christos Faloutsos. 2010. Event detection in time series of mobile communication graphs. In Proceedings of the Army Science Conference."},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.286.5439.509"},{"key":"e_1_3_3_5_2","first-page":"1880","volume-title":"Proceedings of the IEEE International Conference on Computer Vision Workshops","author":"Erichson N. Benjamin","year":"2017","unstructured":"N. Benjamin Erichson, Steven L. Brunton, and J. Nathan +Kutz. 2017. Compressed singular value decomposition for image and video processing. In Proceedings of the IEEE International Conference on Computer Vision Workshops. 1880\u20131888."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.1086\/228631"},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335388"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7439(97)00032-4"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-019-08746-5"},{"key":"e_1_3_3_10_2","volume-title":"Spectral Graph Theory","author":"Chung Fan RK","year":"1997","unstructured":"Fan RK Chung and Fan Chung Graham. 1997. Spectral Graph Theory. Number 92. American Mathematical Soc."},{"issue":"4","key":"e_1_3_3_11_2","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1080\/02722011.2011.623237","article-title":"Legislative activity in the canadian house of commons: Does majority or minority government matter?","volume":"41","author":"Conley Richard S.","year":"2011","unstructured":"Richard S. Conley. 2011. Legislative activity in the canadian house of commons: Does majority or minority government matter? American Review of Canadian Studies 41, 4 (2011), 422\u2013437.","journal-title":"American Review of Canadian Studies"},{"issue":"4","key":"e_1_3_3_12_2","doi-asserted-by":"crossref","first-page":"601","DOI":"10.1017\/S0008423916000962","article-title":"The importance of local party activity in understanding canadian politics: Winning from the ground up in the 2015 federal election: Presidential address to the canadian political science association calgary, 31 may 2016","volume":"49","author":"Cross William","year":"2016","unstructured":"William Cross. 2016. The importance of local party activity in understanding canadian politics: Winning from the ground up in the 2015 federal election: Presidential address to the canadian political science association calgary, 31 may 2016. Canadian Journal of Political Science\/Revue Canadienne De Science Politique 49, 4 (2016), 601\u2013620.","journal-title":"Canadian Journal of Political Science\/Revue Canadienne De Science Politique"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330891"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0900282106"},{"issue":"1","key":"e_1_3_3_15_2","first-page":"17","article-title":"On the evolution of random graphs","volume":"5","author":"Erd\u0151s Paul","year":"1960","unstructured":"Paul Erd\u0151s and Alfr\u00e9d R\u00e9nyi. 1960. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci 5, 1 (1960), 17\u201360.","journal-title":"Publ. Math. Inst. Hung. Acad. Sci"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220040"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220040"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2005.11.003"},{"issue":"1","key":"e_1_3_3_19_2","first-page":"1","article-title":"The multilayer temporal network of public transport in Great Britain","volume":"2","author":"Gallotti Riccardo","year":"2015","unstructured":"Riccardo Gallotti and Marc Barthelemy. 2015. The multilayer temporal network of public transport in Great Britain. Scientific Data 2, 1 (2015), 1\u20138.","journal-title":"Scientific Data"},{"issue":"2","key":"e_1_3_3_20_2","doi-asserted-by":"crossref","first-page":"463","DOI":"10.1017\/S0008423905040461","article-title":"Party structure and backbench dissent in the Canadian and British Parliaments","volume":"38","author":"Garner Christopher","year":"2005","unstructured":"Christopher Garner and Natalia Letki. 2005. Party structure and backbench dissent in the Canadian and British Parliaments. Canadian Journal of Political Science\/Revue Canadienne De Science Politique 38, 2 (2005), 463\u2013482.","journal-title":"Canadian Journal of Political Science\/Revue Canadienne De Science Politique"},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.278701"},{"key":"e_1_3_3_22_2","first-page":"134","volume-title":"Proceedings of the Linear Algebra","author":"Golub Gene H.","year":"1971","unstructured":"Gene H. Golub and Christian Reinsch. 1971. Singular value decomposition and least squares solutions. In Proceedings of the Linear Algebra. Springer, 134\u2013151."},{"key":"e_1_3_3_23_2","first-page":"2712","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Guha Sudipto","year":"2016","unstructured":"Sudipto Guha, Nina Mishra, Gourav Roy, and Okke Schrijvers. 2016. Robust random cut forest based anomaly detection on streams. In Proceedings of the International Conference on Machine Learning. PMLR, 2712\u20132721."},{"key":"e_1_3_3_24_2","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","author":"Guo Jun","year":"2018","unstructured":"Jun Guo and Wenwu Zhu. 2018. Partial multi-view outlier detection based on collective learning. In Proceedings of the AAAI Conference on Artificial Intelligence."},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1109\/43.159993"},{"issue":"1","key":"e_1_3_3_26_2","first-page":"1","article-title":"Localization of laplacian eigenvectors on random networks","volume":"7","author":"Hata Shigefumi","year":"2017","unstructured":"Shigefumi Hata and Hiroya Nakao. 2017. Localization of laplacian eigenvectors on random networks. Scientific Reports 7, 1 (2017), 1\u201311.","journal-title":"Scientific Reports"},{"key":"e_1_3_3_27_2","doi-asserted-by":"publisher","DOI":"10.1016\/0378-8733(83)90021-7"},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313730"},{"key":"e_1_3_3_29_2","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1007\/978-3-031-33374-3_2","volume-title":"Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining","author":"Huang Shenyang","year":"2023","unstructured":"Shenyang Huang, Jacob Danovitch, Guillaume Rabusseau, and Reihaneh Rabbany. 2023. Fast and attributed change detection on dynamic graphs with density of states. In Proceedings of the Pacific-Asia Conference on Knowledge Discovery and Data Mining. Springer, 15\u201326."},{"key":"e_1_3_3_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/3394486.3403077"},{"key":"e_1_3_3_31_2","first-page":"440","volume-title":"Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"Id\u00e9 Tsuyoshi","year":"2004","unstructured":"Tsuyoshi Id\u00e9 and Hisashi Kashima. 2004. Eigenspace-based anomaly detection in computer systems. In Proceedings of the 10th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 440\u2013449."},{"key":"e_1_3_3_32_2","unstructured":"Alexandra Kerr. 2020. A Historical Timeline of COVID-19 in New York City. (2020). Retrieved from https:\/\/www.investopedia.com\/historical-timeline-of-covid-19-in-new-york-city-5071986. Accessed April 5th 2021."},{"key":"e_1_3_3_33_2","unstructured":"Niko Kiukkonen Jan Blom Olivier Dousse Daniel Gatica-Perez and Juha Laurila. 2010. Towards rich mobile phone datasets: Lausanne data collection campaign. Proc. ICPS Berlin Vol. 68."},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.5555\/3322706.3322732"},{"key":"e_1_3_3_35_2","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1109\/PCi.2012.60","volume-title":"Proceedings of the 2012 16th Panhellenic Conference on Informatics","author":"Koutra Danai","year":"2012","unstructured":"Danai Koutra, Evangelos E. Papalexakis, and Christos Faloutsos. 2012. Tensorsplat: Spotting latent anomalies in time. In Proceedings of the 2012 16th Panhellenic Conference on Informatics. IEEE, 144\u2013149."},{"key":"e_1_3_3_36_2","doi-asserted-by":"publisher","DOI":"10.1145\/2824443"},{"key":"e_1_3_3_37_2","volume-title":"The Renewed Canadian Senate: Organizational Challenges and Relations with the Government","author":"Macfarlane Emmett","year":"2019","unstructured":"Emmett Macfarlane. 2019. The Renewed Canadian Senate: Organizational Challenges and Relations with the Government. Institute for Research on Public Policy."},{"key":"e_1_3_3_38_2","volume-title":"Proceedings of the Annual Meeting of the Canadian Communication Association and the Canadian Political Science Association, University of Victoria, British Columbia","author":"Marland Alex","year":"2013","unstructured":"Alex Marland. 2013. What is a political brand?: Justin Trudeau and the theory of political branding. In Proceedings of the Annual Meeting of the Canadian Communication Association and the Canadian Political Science Association, University of Victoria, British Columbia."},{"key":"e_1_3_3_39_2","first-page":"1828","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics","author":"Mercado Pedro","year":"2018","unstructured":"Pedro Mercado, Antoine Gautier, Francesco Tudisco, and Matthias Hein. 2018. The power mean laplacian for multilayer graph clustering. In Proceedings of the International Conference on Artificial Intelligence and Statistics. 1828\u20131838."},{"key":"e_1_3_3_40_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0231035"},{"issue":"1","key":"e_1_3_3_41_2","first-page":"1","article-title":"Structure and inference in annotated networks","volume":"7","author":"Newman Mark EJ","year":"2016","unstructured":"Mark EJ Newman and Aaron Clauset. 2016. Structure and inference in annotated networks. Nature Communications 7, 1 (2016), 1\u201311.","journal-title":"Nature Communications"},{"key":"e_1_3_3_42_2","volume-title":"The Pagerank Citation Ranking: Bringing Order to the Web.","author":"Page Lawrence","year":"1999","unstructured":"Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The Pagerank Citation Ranking: Bringing Order to the Web.Technical Report. Stanford InfoLab."},{"key":"e_1_3_3_43_2","doi-asserted-by":"publisher","DOI":"10.5555\/1543767.1543769"},{"key":"e_1_3_3_44_2","first-page":"899","volume-title":"Proceedings of the 16th International Conference on Information Fusion","author":"Papalexakis Evangelos E.","year":"2013","unstructured":"Evangelos E. Papalexakis, Leman Akoglu, and Dino Ience. 2013. Do more views of a graph help? community detection and clustering in multi-graphs. In Proceedings of the 16th International Conference on Information Fusion. IEEE, 899\u2013905."},{"key":"e_1_3_3_45_2","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078195"},{"key":"e_1_3_3_46_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v29i1.9574"},{"key":"e_1_3_3_47_2","doi-asserted-by":"publisher","DOI":"10.1002\/wics.1347"},{"key":"e_1_3_3_48_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.dsp.2013.09.008"},{"key":"e_1_3_3_49_2","first-page":"4894","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","author":"Sheng Xiang-Rong","year":"2019","unstructured":"Xiang-Rong Sheng, De-Chuan Zhan, Su Lu, and Yuan Jiang. 2019. Multi-view anomaly detection: Neighborhood in locality matters. In Proceedings of the AAAI Conference on Artificial Intelligence. 4894\u20134901."},{"key":"e_1_3_3_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"issue":"2","key":"e_1_3_3_51_2","doi-asserted-by":"crossref","first-page":"164","DOI":"10.1017\/nws.2017.13","article-title":"Bayesian approach to multilayer stochastic blockmodel and network changepoint detection.","volume":"5","year":"2017","unstructured":"Yunkyu Sohn and Jonghee Park. 2017. Bayesian approach to multilayer stochastic blockmodel and network changepoint detection. Netw. Sci. 5, 2 (2017), 164\u2013186.","journal-title":"Netw. Sci."},{"key":"e_1_3_3_52_2","volume-title":"Community Detection in Multi-Dimensional Networks","author":"Tang Lei","year":"2010","unstructured":"Lei Tang, Xufei Wang, and Huan Liu. 2010. Community Detection in Multi-Dimensional Networks. Technical Report. Arizona State University, Department of Computer Science and Engineering."},{"key":"e_1_3_3_53_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.125"},{"key":"e_1_3_3_54_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132964"},{"key":"e_1_3_3_55_2","doi-asserted-by":"crossref","unstructured":"Renato Vizuete Federica Garin and Paolo Frasca. 2021. The Laplacian spectrum of large graphs sampled from graphons. IEEE Transactions on Network Science and Engineering 8 2 (2021) 1711\u20131721.","DOI":"10.1109\/TNSE.2021.3069675"},{"key":"e_1_3_3_56_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-007-9033-z"},{"key":"e_1_3_3_57_2","unstructured":"Junhao Wang Sacha Levy Ren Wang Aayushi Kulshrestha and Reihaneh Rabbany. 2019. SCG: Spotting Coordinated Groups in Social Media . arXiv preprint arXiv:1910.07130."},{"key":"e_1_3_3_58_2","doi-asserted-by":"crossref","unstructured":"Yu Wang Aniket Chakrabarti David Sivakoff and Srinivasan Parthasarathy. 2017. Fast change point detection on dynamic social networks. In Proceedings of the 26th International Joint Conference on Artificial Intelligence 2992\u20132998.","DOI":"10.24963\/ijcai.2017\/417"},{"key":"e_1_3_3_59_2","unstructured":"Keyulu Xu Weihua Hu Jure Leskovec and Stefanie Jegelka. 2018. How powerful are graph neural networks? In International Conference on Learning Representations ."},{"key":"e_1_3_3_60_2","first-page":"126","volume-title":"Proceedings of the 2017 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics.","author":"Zamani Sina","year":"2017","unstructured":"Sina Zamani, Tejaswi Nanjundaswamy, and Kenneth Rose. 2017. Frequency domain singular value decomposition for efficient spatial audio coding. In Proceedings of the 2017 IEEE Workshop on Applications of Signal Processing to Audio and Acoustics. IEEE, 126\u2013130."},{"key":"e_1_3_3_61_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2017.2673241"},{"key":"e_1_3_3_62_2","unstructured":"Xiao-Dong Zhang. 2011. The Laplacian eigenvalues of graphs: A survey. arXiv preprint arXiv:1111.2897."},{"issue":"2","key":"e_1_3_3_63_2","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1198\/tech.2001.s620","article-title":"Standard probability and statistics tables and formulae","volume":"43","author":"Ziegel Eric R.","year":"2001","unstructured":"Eric R. Ziegel. 2001. Standard probability and statistics tables and formulae. Technometrics 43, 2 (2001), 249.","journal-title":"Technometrics"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3631609","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3631609","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:53Z","timestamp":1750291433000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3631609"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,1,12]]},"references-count":62,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,4,30]]}},"alternative-id":["10.1145\/3631609"],"URL":"https:\/\/doi.org\/10.1145\/3631609","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,1,12]]},"assertion":[{"value":"2023-01-31","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-10-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-01-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}