Finding planted subgraphs with few eigenvalues using the Schur-Horn relaxation

DOI10.1137/16M1075144zbMATH Open1395.90199arXiv1605.04008WikidataQ130122118 ScholiaQ130122118MaRDI QIDQ4609470FDOQ4609470

Authors: Utkan Onur Candogan, Venkat Chandrasekaran 

Publication date: 3 April 2018

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Abstract: 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.

Full work available at URL: https://arxiv.org/abs/1605.04008

Recommendations

• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
• Convex optimization for the densest subgraph and densest submatrix problems
• Convex optimization for the planted \(k\)-disjoint-clique problem
• Nuclear norm minimization for the planted clique and biclique problems
• Convex graph invariants

zbMATH Keywords

convex optimizationsemidefinite programmingmajorizationstrongly regular graphsdistance-regular graphsorbitopesinduced subgraph isomorphism

Mathematics Subject Classification ID

Convex programming (90C25) Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90) Semidefinite programming (90C22)

Cites Work

• SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
• Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ ¹ minimization
• Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
• Exact matrix completion via convex optimization
• Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
• Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
• Sharp nonasymptotic bounds on the norm of random matrices with independent entries
• Title not available (Why is that?)
• Reducibility among combinatorial problems
• Nuclear norm minimization for the planted clique and biclique problems
• Spectra of graphs
• Graph implementations for nonsmooth convex programs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Multiplicative cones - a family of three eigenvalue graphs
• On graphs with three eigenvalues
• Convex graph invariants
• Spreads in strongly regular graphs
• Pseudo-random graphs
• Small regular graphs with four eigenvalues
• Regular graphs with four eigenvalues
• GRAPHS WITH A SMALL NUMBER OF DISTINCT EIGENVALUES
• On characterizing certain graphs with four eigenvalues by their spectra
• Finding and certifying a large hidden clique in a semirandom graph
• Title not available (Why is that?)
• Strongly regular graphs, partial geometries and partially balanced designs
• Clustering Social Networks
• ORBITOPES
• Title not available (Why is that?)
• A low-dimensional semidefinite relaxation for the quadratic assignment problem
• Title not available (Why is that?)

Cited In (5)

• Convex graph invariant relaxations for graph edit distance
• Tensor clustering with planted structures: statistical optimality and computational limits
• A note on convex relaxations for the inverse eigenvalue problem
• Convex optimization for the densest subgraph and densest submatrix problems
• Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation

Uses Software

• SDPT3
• CVX

This page was built for publication: Finding planted subgraphs with few eigenvalues using the Schur-Horn relaxation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4609470)