# Block-Structured Optimization for Subgraph Detection in Interdependent Networks

arXiv: https://arxiv.org/abs/2210.02702 · HTML: https://mlsanity.com/paper/2210.02702/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 6 of its 20 references that are in the map.
- First posted on arXiv 6 Oct 2022.

## Builds on (most cited first, 6 of 6)

- [Accelerated, Parallel and Proximal Coordinate Descent](https://mlsanity.com/paper/1312.5799/) (2013)
- [A Primer on Coordinate Descent Algorithms](https://mlsanity.com/paper/1610.00040/) (2016)
- [Gradient Hard Thresholding Pursuit for Sparsity-Constrained Optimization](https://mlsanity.com/paper/1311.5750/) (2013)
- [Technical Report: A Generalized Matching Pursuit Approach for Graph-Structured Sparsity](https://mlsanity.com/paper/1612.03364/) (2016)
- [Technical Report: Graph-Structured Sparse Optimization for Connected Subgraph Detection](https://mlsanity.com/paper/1609.09864/) (2016)
- [A Generic Framework for Interesting Subspace Cluster Detection in Multi-attributed Networks](https://mlsanity.com/paper/1709.05246/) (2017)

## Abstract (arXiv)

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.