Block-Structured Optimization for Anomalous Pattern Detection in Interdependent Networks
Block-Structured Optimization for Anomalous Pattern Detection in Interdependent Networks
复制标题
DOI：
10.1109/icdm.2019.00137
复制
发表时间：
2019-11
期刊：
影响因子：
--
通讯作者：
Fei Jie;Chunpai Wang;Feng Chen;Lei Li;Xindong Wu
中科院分区：
文献类型：
--
作者：
Fei Jie;Chunpai Wang;Feng Chen;Lei Li;Xindong Wu
我们提出了一个通用的优化框架，用于检测相互依赖的网络中的异常模式(有趣或意外的子图)，例如多层网络、时态网络、网络网络等。我们将该问题描述为一个非凸优化问题，该优化问题具有一个一般的非线性得分函数和一组块结构的非凸约束。为了解决这一问题，我们提出了一种有效的、高效的、可并行的基于投影的算法--图块结构梯度投影算法。证明了我们的算法1)在网络规模上几乎是线性的，2)具有理论上的逼近保证。此外，我们还演示了我们的框架如何应用到两个非常实际的应用中，并进行了全面的实验，以证明我们所提出的算法的有效性和高效性。
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.