Convex Optimization for the Densest Subgraph and Densest Submatrix Problems
- PDF / 1,670,328 Bytes
- 24 Pages / 439.642 x 666.49 pts Page_size
- 79 Downloads / 210 Views
Convex Optimization for the Densest Subgraph and Densest Submatrix Problems Polina Bombina1 · Brendan Ames1 Received: 12 March 2020 / Accepted: 23 July 2020 / © Springer Nature Switzerland AG 2020
Abstract We consider the densest k-subgraph problem, which seeks to identify the k-node subgraph of a given input graph with maximum number of edges. This problem is well-known to be NP-hard, by reduction to the maximum clique problem. We propose a new convex relaxation for the densest k-subgraph problem, based on a nuclear norm relaxation of a low-rank plus sparse decomposition of the adjacency matrices of k-node subgraphs to partially address this intractability. We establish that the densest k-subgraph can be recovered with high probability from the optimal solution of this convex relaxation if the input graph is randomly sampled from a distribution of random graphs constructed to contain an especially dense k-node subgraph with high probability. Specifically, the relaxation is exact when the edges of the input graph are added independently at random, with edges within a particular k-node subgraph added with higher probability than other edges in the graph. We provide a sufficient condition on the size of this subgraph k and the expected density under which the optimal solution of the proposed relaxation recovers this k-node subgraph with high probability. Further, we propose a first-order method for solving this relaxation based on the alternating direction method of multipliers, and empirically confirm our predicted recovery thresholds using simulations involving randomly generated graphs, as well as graphs drawn from social and collaborative networks. Keywords Densest subgraph · Submatrix localization · Nuclear norm relaxation · Maximum clique · Alternating direction method of multipliers
Brendan Ames
[email protected] Polina Bombina [email protected] 1
Department of Mathematics, University of Alabama, Tuscaloosa, AL, USA
23
Page 2 of 24
SN Operations Research Forum
(2020) 1:23
1 Introduction We consider the densest k-subgraph problem: given graph G = (V , E), identify the k-node subgraph of G of maximum density, i.e., maximum average degree. Equivalently, the problem reduces to finding the k-node subgraph of G with maximum number of edges. It is easy to see that the densest k-subgraph problem is NP-hard by reduction to the maximum clique problem, well-known to be NP-hard [1]. Indeed, if G contains a clique of size k, it would induce the densest k-subgraph of G; any polynomial-time algorithm for densest k-subgraph would immediately provide a polynomial-time algorithm for maximum clique. Moreover, it has been shown by [2–4] that the densest k-subgraph problem does not admit polynomial-time approximation schemes in general. Despite this intractability, the identification of dense subgraphs plays a significant role in many practical applications, especially in the analysis of web graphs, and social and biological networks [5–10]. We propose a new convex relaxation for the densest k-subgraph problem to add
Data Loading...
