Block-Structured Optimization for Anomalous Pattern Detection in Interdependent Networks
| Autor: | Feng Chen, Lei Li, Xindong Wu, Fei Jie, Chunpai Wang |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Pattern detection
Nonlinear system Parallelizable manifold Interdependent networks Computer science 020204 information systems 0202 electrical engineering electronic engineering information engineering Graph (abstract data type) 020201 artificial intelligence & image processing 02 engineering and technology Algorithm Graph |
| Zdroj: | ICDM |
| DOI: | 10.1109/icdm.2019.00137 |
| Popis: | We propose a generalized optimization framework for detecting anomalous patterns (subgraphs that are interesting or unexpected) in interdependent networks, such as multi-layer networks, temporal networks, networks of networks, and many others. We frame the problem as a non-convex optimization that has a general nonlinear score function and a set of block-structured and non-convex constraints. We develop an effective, efficient, and parallelizable projection-based algorithm, namely Graph Block-structured Gradient Projection (GBGP), to solve the problem. It is proved that our algorithm 1) runs in nearly-linear time on the network size, and 2) enjoys a theoretical approximation guarantee. Moreover, we demonstrate how our framework can be applied to two very practical applications, and we conduct comprehensive experiments to show the effectiveness and efficiency of our proposed algorithm. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|