A Unified Optimization Framework for Event and Pattern Detection in Attributed Networks

Feng Chen, University at Albany, SUNY

Abstract:Big data are often created by aggregating multiple data sources and modeled as large-scale attributed networks. Many applications of big data analytics are concerned of discovering complex patterns (subnetworks) that are interesting or unexpected, such as the detection and forecasting of societal events (disasters, civil unrest), anomalous patterns (disease outbreaks, cyber-attacks), discriminative subnetworks (cancer diagnosis), knowledge patterns (new knowledge building), and storylines (intelligence analysis), among others. Despite considerable attention to the problem, most of the existing methods are either heuristic or computationally intractable for large-scale attributed networks. In this talk, I will present a unified graph-structured optimization framework for solving a broad class of such problems that runs in nearly-linear time and at the same time provides rigorous guarantees on quality. In particular, we frame the problem as a non-convex optimization problem subject to combinatorial constraints, in which the objective function is defined based on attribute data and the constraints are defined based on network topology (e.g., connected or dense subnetworks). The key idea is to iteratively search for a close-to-optimal solution by solving easier sub-problems in each iteration: (1) identification of the subnetwork(s) that maximizes the objective function in a sub-space determined by the gradient of the current solution and the topological constraints; and (2) approximate projection of the identified subnetwork(s) onto the feasible space that satisfies the topological constraints. We will demonstrate the effectiveness and efficiency of the proposed approach using several real-world datasets.

Biography: Dr. Feng Chen is currently an Assistant Professor in the Computer Science Department at the University at Albany - State University of New York, where he directs the Event and Pattern Detection Laboratory. Before joining UAlbany, he was a post-doctoral at the EPD Lab and the iLab at Carnegie Mellon University. He holds a Ph.D. in computer science from Virginia Tech in 2012. His research interests are in large-scale data mining, graph mining, and machine learning, with a specific focus on event and pattern detection in massive, complex, and high-dimensional network data. His research has been funded by NSF, NIH, ARO, IARPA, and the U.S. Department of transportation, and been reported in over 80 peer-reviewed journal and conference papers. He is the recipient of an NSF CAREER award in 2018 and a member of the IEEE and the ACM.