Efficient Pattern Detection in Web-Scale Graphs by Subcore-Tree Decomposition and Subset Scanning

• Activity Number: 439 - Scan Statistics in Networks and Graphs
• Type: Invited
• Date/Time: Wednesday, August 2, 2017 : 8:30 AM to 10:20 AM
• Sponsor: Section on Statistics in Defense and National Security
• Author(s): Daniel Bertrand Neill* and Chunpai Wang and Feng Chen and Daniel Hono
• Companies: Carnegie Mellon University and University at Albany and University at Albany and University at Albany
• Keywords: event detection ; graph mining ; subset scanning ; graph decompositions ; scalable algorithms

Abstract

Detection of anomalous patterns in web-scale graphs, such as online social networks, is a critical but challenging problem. While existing techniques such as burst detection, topic modeling, clustering, or the non-parametric heterogeneous graph scan can be used to find patterns in online social network data, these techniques do not scale to very large graphs without approximations resulting in substantial loss of accuracy. Our solution, the web-scale subset scan (WSSS), exploits the natural core-periphery structure inherent in many web-scale graphs to detect patterns accurately and efficiently. WSSS combines a novel "subcore-tree" graph decomposition, which separates the graph into a set of dense communities and a low-treewidth component, with an efficient non-parametric subset scan, which exploits the additive linear-time subset scanning property to enable efficient search over connected subgraphs for both the core and tree components. We compare WSSS to existing methods on multiple web-scale datasets and demonstrate improvements in computational efficiency, scalability, and the accuracy of the detected subgraphs. This work was partially supported by NSF grant IIS-0953330.