Convex Optimization for the Densest Subgraph and Densest Submatrix Problems

Polina Bombina () and Brendan Ames ()
Additional contact information
Polina Bombina: University of Alabama
Brendan Ames: University of Alabama

SN Operations Research Forum, 2020, vol. 1, issue 3, 1-24

Abstract: 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 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s43069-020-00020-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:snopef:v:1:y:2020:i:3:d:10.1007_s43069-020-00020-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/43069

DOI: 10.1007/s43069-020-00020-5

Access Statistics for this article

SN Operations Research Forum is currently edited by Marco Lübbecke

More articles in SN Operations Research Forum from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().