{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T21:10:13Z","timestamp":1778188213216,"version":"3.51.4"},"reference-count":84,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2016,2,24]],"date-time":"2016-02-24T00:00:00Z","timestamp":1456272000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"U.S. Department of Energy by Lawrence Livermore National Laboratory","award":["DE-AC52-07NA27344, N66001-15-C-4041, DARPA (SIMPLEX) and DARPA (GRAPHS)"],"award-info":[{"award-number":["DE-AC52-07NA27344, N66001-15-C-4041, DARPA (SIMPLEX) and DARPA (GRAPHS)"]}]},{"name":"Yahoo Research Alliance Gift"},{"name":"U.S. Army Research Office (ARO) and Defense Advanced Research Projects Agency","award":["W911NF-11-C-0088"],"award-info":[{"award-number":["W911NF-11-C-0088"]}]},{"name":"IBM Faculty Award"},{"name":"Army Research Laboratory","award":["W911NF-09-2-0053"],"award-info":[{"award-number":["W911NF-09-2-0053"]}]},{"name":"Google Focused Research Award"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2016,2,24]]},"abstract":"<jats:p>\n                    How much has a network changed since yesterday? How different is the wiring of Bob\u2019s brain (a left-handed male) and Alice\u2019s brain (a right-handed female), and how is it different? Graph similarity with given node correspondence, i.e., the detection of changes in the connectivity of graphs, arises in numerous settings. In this work, we formally state the axioms and desired properties of the graph similarity functions, and evaluate when state-of-the-art methods fail to detect crucial connectivity changes in graphs. We propose D\n                    <jats:sc>elta<\/jats:sc>\n                    C\n                    <jats:sc>on<\/jats:sc>\n                    , a principled, intuitive, and scalable algorithm that assesses the similarity between two graphs on the same nodes (e.g., employees of a company, customers of a mobile carrier). In conjunction, we propose D\n                    <jats:sc>elta<\/jats:sc>\n                    C\n                    <jats:sc>on<\/jats:sc>\n                    -A\n                    <jats:sc>ttr<\/jats:sc>\n                    , a related approach that enables attribution of change or dissimilarity to responsible nodes and edges. Experiments on various synthetic and real graphs showcase the advantages of our method over existing similarity measures. Finally, we employ D\n                    <jats:sc>elta<\/jats:sc>\n                    C\n                    <jats:sc>on<\/jats:sc>\n                    and D\n                    <jats:sc>elta<\/jats:sc>\n                    C\n                    <jats:sc>on<\/jats:sc>\n                    -A\n                    <jats:sc>ttr<\/jats:sc>\n                    on real applications: (a) we classify people to groups of high and low creativity based on their brain connectivity graphs, (b) do temporal anomaly detection in the who-emails-whom Enron graph and find the top culprits for the changes in the temporal corporate email graph, and (c) recover pairs of test-retest large brain scans ( \u223c17M edges, up to 90M edges) for 21 subjects.\n                  <\/jats:p>","DOI":"10.1145\/2824443","type":"journal-article","created":{"date-parts":[[2016,2,26]],"date-time":"2016-02-26T09:29:03Z","timestamp":1456478943000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":121,"title":["D\n                    <scp>elta<\/scp>\n                    C\n                    <scp>on<\/scp>"],"prefix":"10.1145","volume":"10","author":[{"given":"Danai","family":"Koutra","sequence":"first","affiliation":[{"name":"Computer Science and Engineering, University of Michigan, Ann Arbor"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Neil","family":"Shah","sequence":"additional","affiliation":[{"name":"Computer Science Department, Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joshua T.","family":"Vogelstein","sequence":"additional","affiliation":[{"name":"Department of Biomedical Engineering &amp; Institute of Computational Medicine, Johns Hopkins University Child Mind Institute"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Brian","family":"Gallagher","sequence":"additional","affiliation":[{"name":"Lawrence Livermore National Laboratory, Livermore, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Faloutsos","sequence":"additional","affiliation":[{"name":"Computer Science Department, Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,2,24]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213836.2213941"},{"key":"e_1_2_1_2_1","volume-title":"27th Army Science Conference. 77--79","author":"Akoglu Leman","year":"2010","unstructured":"Leman Akoglu and Christos Faloutsos. 2010. Event detection in time series of mobile communication graphs. In 27th Army Science Conference. 77--79."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-014-0365-y"},{"key":"e_1_2_1_4_1","volume-title":"Reversible Markov Chains and Random Walks on Graphs. (2002). Unfinished monograph, recompiled","author":"Aldous David","year":"2014","unstructured":"David Aldous and James Allen Fill. 2002. Reversible Markov Chains and Random Walks on Graphs. (2002). Unfinished monograph, recompiled 2014. Retrieved from http:\/\/www.stat.berkeley.edu\/&sim;aldous\/ RWG\/book.html."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2470654.2470724"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/IV.2009.108"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2435209.2435212"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2492517.2492582"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488388.2488400"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2005.132"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1209\/0295-5075\/89\/37009"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1196438"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDMW.2011.165"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 11th SIAM International Conference on Data Mining (SDM)","author":"Chau Duen Horng","year":"2011","unstructured":"Duen Horng Chau, Carey Nachenberg, Jeffrey Wilhelm, Adam Wright, and Christos Faloutsos. 2011. Large scale graph mining and inference for malware detection. In Proceedings of the 11th SIAM International Conference on Data Mining (SDM), Mesa, AZ, 131--142."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/1577069.1577096"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218001404003228"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 26th International Conference on Machine Learning. Omnipress, 255--262","author":"Costa Fabrizio","year":"2010","unstructured":"Fabrizio Costa and Kurt De Grave. 2010. Fast neighborhood subgraph pairwise distance kernel. In Proceedings of the 26th International Conference on Machine Learning. Omnipress, 255--262."},{"key":"e_1_2_1_19_1","volume-title":"Random Walks and Electric Networks","author":"Doyle Peter","unstructured":"Peter Doyle and James Laurie Snell. 1984. Random Walks and Electric Networks. Vol. 22. Mathematical Association America, New York."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69812-8_51"},{"key":"e_1_2_1_21_1","volume-title":"Proceedings of the 11th International Symposium in Graph Drawing (GD)","volume":"2912","author":"Erten Cesim","year":"2003","unstructured":"Cesim Erten, Philip J. Harding, Stephen G. Kobourov, Kevin Wampler, and Gary Yee. 2003. GraphAEL: graph animations with evolving layouts. In Proceedings of the 11th International Symposium in Graph Drawing (GD), Perugia, Italy, Vol. 2912. 98--110."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.21136\/CMJ.1973.101168"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.2307\/3033543"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45167-9_11"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735479.2735490"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1177\/1473871611416549"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/MPUL.2011.2181023"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/988672.988727"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2254556.2254654"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1208999"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835828"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014072"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014102"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-06608-0_29"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972825.71"},{"key":"e_1_2_1_37_1","unstructured":"G. Karypis and V. Kumar. 1995. METIS: unstructured graph partitioning and sparse matrix ordering system. The University of Minnesota (1995)."},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 20th International Conference on Machine Learning. AAAI Press, 321--328","author":"Kashima Hisashi","year":"2003","unstructured":"Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. 2003. Marginalized kernels between labeled graphs. In Proceedings of the 20th International Conference on Machine Learning. AAAI Press, 321--328."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(76)90102-3"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13672-6_41"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043932.2043945"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/324133.324140"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the 1st Conference on Email and Anti-Spam.","author":"Klimt Bryan","year":"2004","unstructured":"Bryan Klimt and Yiming Yang. 2004. Introducing the enron corpus. In Proceedings of the 1st Conference on Email and Anti-Spam."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.11"},{"key":"e_1_2_1_45_1","volume-title":"Statistical Analysis and Data Mining","author":"Koutra Danai","unstructured":"Danai Koutra, U. Kang, Jilles Vreeken, and Christos Faloutsos. 2015. Summarizing and understanding large graphs. In Statistical Analysis and Data Mining. John Wiley & Sons, Inc."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23783-6_16"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/PCi.2012.60"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-37453-1_17"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.152"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972832.18"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2487886"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.5555\/3121445.3121464"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1739041.1739098"},{"key":"e_1_2_1_55_1","volume-title":"Proceedings of the 9th International Workshop on Mining and Learning with Graphs (MLG).","author":"Li Geng","unstructured":"Geng Li, Murat Semerci, Bulent Yener, and Mohammed J. Zaki. 2011. Graph classification via topological and label attributes. In Proceedings of the 9th International Workshop on Mining and Learning with Graphs (MLG)."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/SocialCom.2010.35"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-008-5086-2"},{"key":"e_1_2_1_58_1","doi-asserted-by":"crossref","unstructured":"Ching-Hao Mao Chung-Jung Wu Evangelos E Papalexakis Christos Faloutsos and Tien-Cheu Kao. 2014. MalSpot: multi2 malicious network behavior patterns analysis. In PAKDD. 1--14.","DOI":"10.1007\/978-3-319-06608-0_1"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2011.80"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557155"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2004.11.009"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956831"},{"key":"e_1_2_1_63_1","unstructured":"OCP. 2014. Open Connectome Project. Retrieved from http:\/\/www.openconnectomeproject.org."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13174-010-0003-x"},{"key":"e_1_2_1_65_1","volume-title":"Finding Groups of Graphs in Databases. Master\u2019s thesis","author":"Peabody Mitchell","unstructured":"Mitchell Peabody. 2003. Finding Groups of Graphs in Databases. Master\u2019s thesis. Drexel University, Philadelphia, PA."},{"key":"e_1_2_1_66_1","volume-title":"Proceedings of the 1st International Workshop on Mining Graphs, Trees and Sequences. 65--74","author":"Ramon Jan","year":"2003","unstructured":"Jan Ramon and Thomas G\u00e4rtner. 2003. Expressivity versus efficiency of graph kernels. In Proceedings of the 1st International Workshop on Mining Graphs, Trees and Sequences. 65--74."},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1002\/wics.1347"},{"key":"e_1_2_1_68_1","volume-title":"Proceedings of the IEEE Global Conference on Signal and Information Processing (GlobalSIP).","author":"Roncal William Gray","unstructured":"William Gray Roncal, Zachary H. Koterba, Disa Mhembere, Dean Kleissas, Joshua T. Vogelstein, Randal C. Burns, Anita R. Bowles, Dimitrios K. Donavos, Sephira Ryman, Rex E. Jung, Lei Wu, Vince D. Calhoun, and R. Jacob Vogelstein. 2013. MIGRAINE: MRI graph reliability analysis and inference for connectomics. In Proceedings of the IEEE Global Conference on Signal and Information Processing (GlobalSIP)."},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783321"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.5555\/2984093.2984279"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2078187"},{"key":"e_1_2_1_72_1","volume-title":"Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS","volume":"5","author":"Shervashidze Nino","year":"2009","unstructured":"Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. 2009. Efficient graphlet kernels for large graph comparison. In Proceedings of the 12th International Conference on Artificial Intelligence and Statistics (AISTATS 2009), Vol. 5. Journal of Machine Learning Research, 488--495."},{"key":"e_1_2_1_73_1","unstructured":"SNAP. 2016. Retrieved http:\/\/snap.stanford.edu\/data\/index.html#web. Last accessed: 2016."},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612184"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396795"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03658-3_47"},{"key":"e_1_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1859891"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1145\/1592665.1592675"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/TSP.2013.2294594"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767852"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.patcog.2008.03.011"},{"key":"e_1_2_1_82_1","doi-asserted-by":"crossref","unstructured":"\u00d6mer Nebil Yavero\u011flu No\u00ebl Malod-Dognin Darren Davis Zoran Levnaji\u0107 Vuk Janjic Rasa Karapandza Aleksandar Stojmirovic and Nata\u0161a Pr\u017eulj. 2014. Revealing the hidden language of complex networks. Scientific Reports 4 Article number: 4547.","DOI":"10.1038\/srep04547"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","unstructured":"Jonathan S. Yedidia William T. Freeman and Yair Weiss. 2003. Understanding belief propagation and its generalizations. Exploring Artificial Intelligence in the New Millennium 239--269.","DOI":"10.5555\/779343.779352"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732219.2732221"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2824443","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2824443","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2824443","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T09:43:49Z","timestamp":1763459029000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2824443"}},"subtitle":["Principled Massive-Graph Similarity Function with Attribution"],"short-title":[],"issued":{"date-parts":[[2016,2,24]]},"references-count":84,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2016,2,24]]}},"alternative-id":["10.1145\/2824443"],"URL":"https:\/\/doi.org\/10.1145\/2824443","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,2,24]]},"assertion":[{"value":"2014-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-09-01","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-02-24","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}