We propose a generalized framework for block-structured nonconvex
optimization, which can be applied to structured subgraph detection in
interdependent networks, such as multi-layer networks, temporal networks,
networks of networks, and many others. Specifically, we design an effective,
efficient, and parallelizable projection algorithm, namely Graph
Block-structured Gradient Projection (GBGP), to optimize a general non-linear
function subject to graph-structured constraints. We prove that our algorithm:
1) runs in nearly-linear time on the network size; 2) enjoys a theoretical
approximation guarantee. Moreover, we demonstrate how our framework can be
applied to two very practical applications and conduct comprehensive
experiments to show the effectiveness and efficiency of our proposed algorithm.

本文提出了一种广义块结构非凸优化框架，其中包括应用于多层网络，时间网络，网络网络等相互依赖网络中的结构子图检测。我们设计了一个有效，高效和可并行化的投影算法，即 Graph Block-structured Gradient Projection (GBGP)，用于优化满足图结构约束的一般非线性函数，并证明了我们的算法：1）在网络规模上近线性时间运行；2）具有理论上的近似保证。此外，我们演示了如何将我们的框架应用于两个非常实际的应用，并进行了全面的实验，以展示我们提出的算法的有效性和高效性。