期刊
ACM TRANSACTIONS ON KNOWLEDGE DISCOVERY FROM DATA
卷 10, 期 3, 页码 -出版社
ASSOC COMPUTING MACHINERY
DOI: 10.1145/2824443
关键词
Algorithms; Experimentation; Graph similarity; graph comparison; anomaly detection; network monitoring; graph classification; node attribution; edge attribution; culprit nodes and edges
资金
- U.S. Army Research Office (ARO)
- Defense Advanced Research Projects Agency (DARPA) [W911NF-11-C-0088]
- U.S. Department of Energy by Lawrence Livermore National Laboratory [DE-AC52-07NA27344, N66001-15-C-4041]
- Army Research Laboratory [W911NF-09-2-0053]
- IBM Faculty Award
- Google Focused Research Award
- Yahoo Research Alliance Gift
How much has a network changed since yesterday? How different is the wiring of Bob's brain (a left-handed male) and Alice's 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 DELTACON, 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 DELTACON-ATTR, 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 DELTACON and DELTACON-ATTR 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 (similar to 17M edges, up to 90M edges) for 21 subjects.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据