A Caltech Library Service

Finding Planted Subgraphs with Few Eigenvalues using the Schur-Horn Relaxation

Candogan, Utkan-Onur and Chandrasekaran, Venkat (2018) Finding Planted Subgraphs with Few Eigenvalues using the Schur-Horn Relaxation. SIAM Journal on Optimization, 28 (1). pp. 735-759. ISSN 1052-6234. doi:10.1137/16M1075144.

[img] PDF - Published Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


Extracting structured subgraphs inside large graphs---often known as the planted subgraph problem---is a fundamental question that arises in a range of application domains. This problem is NP-hard in general and, as a result, significant efforts have been directed towards the development of tractable procedures that succeed on specific families of problem instances. We propose a new computationally efficient convex relaxation for solving the planted subgraph problem; our approach is based on tractable semidefinite descriptions of majorization inequalities on the spectrum of a symmetric matrix. This procedure is effective at finding planted subgraphs that consist of few distinct eigenvalues, and it generalizes previous convex relaxation techniques for finding planted cliques. Our analysis relies prominently on the notion of spectrally comonotone matrices, which are pairs of symmetric matrices that can be transformed to diagonal matrices with sorted diagonal entries upon conjugation by the same orthogonal matrix.

Item Type:Article
Related URLs:
URLURL TypeDescription Paper
Candogan, Utkan-Onur0000-0003-3920-402X
Additional Information:© 2018 Society for Industrial and Applied Mathematics. Received by the editors May 13, 2016; accepted for publication (in revised form) October 24, 2017; published electronically March 15, 2018. Funding: The authors were supported in part by National Science Foundation grants CCF-1350590 and CCF-1637598, by Air Force Office of Scientific Research grants FA9550-14-1-0098 and FA9550-16-1-0210, and by a Sloan research fellowship.
Funding AgencyGrant Number
Air Force Office of Scientific Research (AFOSR)FA9550-14-1-0098
Air Force Office of Scientific Research (AFOSR)FA9550-16-1-0210
Alfred P. Sloan FoundationUNSPECIFIED
Subject Keywords:convex optimization, distance-regular graphs, induced subgraph isomorphism, majorization, orbitopes, semidefinite programming, strongly regular graphs
Issue or Number:1
Classification Code:AMS subject classifications: 90C25, 90C22, 90C90, 90C35
Record Number:CaltechAUTHORS:20170614-124916669
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:78210
Deposited By: Ruth Sustaita
Deposited On:14 Jun 2017 21:02
Last Modified:15 Nov 2021 17:37

Repository Staff Only: item control page