Finding planted subgraphs with few eigenvalues using the Schur-Horn relaxation
From MaRDI portal
Publication:4609470
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.
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
Cites work
- scientific article; zbMATH DE number 428989 (Why is no real title available?)
- scientific article; zbMATH DE number 3884175 (Why is no real title available?)
- scientific article; zbMATH DE number 3884178 (Why is no real title available?)
- scientific article; zbMATH DE number 3982880 (Why is no real title available?)
- scientific article; zbMATH DE number 3733985 (Why is no real title available?)
- scientific article; zbMATH DE number 1380608 (Why is no real title available?)
- scientific article; zbMATH DE number 3304766 (Why is no real title available?)
- A low-dimensional semidefinite relaxation for the quadratic assignment problem
- Clustering Social Networks
- Convex graph invariants
- Exact matrix completion via convex optimization
- Finding and certifying a large hidden clique in a semirandom graph
- GRAPHS WITH A SMALL NUMBER OF DISTINCT EIGENVALUES
- Graph implementations for nonsmooth convex programs
- Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Multiplicative cones - a family of three eigenvalue graphs
- Nuclear norm minimization for the planted clique and biclique problems
- ORBITOPES
- On characterizing certain graphs with four eigenvalues by their spectra
- On graphs with three eigenvalues
- Optimally sparse representation in general (nonorthogonal) dictionaries via ℓ 1 minimization
- Pseudo-random graphs
- Reducibility among combinatorial problems
- Regular graphs with four eigenvalues
- SDPT3 — A Matlab software package for semidefinite programming, Version 1.3
- Sharp nonasymptotic bounds on the norm of random matrices with independent entries
- Small regular graphs with four eigenvalues
- Spectra of graphs
- Spreads in strongly regular graphs
- Strongly regular graphs, partial geometries and partially balanced designs
- Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics
Cited in
(5)- Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation
- 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
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)
