{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,22]],"date-time":"2026-08-22T08:47:47Z","timestamp":1787388467199,"version":"build-2736575974"},"reference-count":43,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-14-1-0098"],"award-info":[{"award-number":["FA9550-14-1-0098"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1350590"],"award-info":[{"award-number":["CCF-1350590"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1137\/16m1075144","type":"journal-article","created":{"date-parts":[[2018,3,15]],"date-time":"2018-03-15T15:21:59Z","timestamp":1521127319000},"page":"735-759","source":"Crossref","is-referenced-by-count":6,"title":["Finding Planted Subgraphs with Few Eigenvalues using the Schur--Horn Relaxation"],"prefix":"10.1137","volume":"28","author":[{"given":"Utkan Onur","family":"Candogan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Venkat","family":"Chandrasekaran","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,3,15]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199810\/12)13:3\/4<457::AID-RSA14>3.0.CO;2-W"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0459-x"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1006\/jmbi.1994.1657"},{"key":"atypb4","doi-asserted-by":"publisher","DOI":"10.1214\/15-AOP1025"},{"key":"atypb5","unstructured":"E. Bannai and T. Ito,\n                      Algebraic Combinatorics\n                      , Benjamin\/Cummings, Menlo Park, CA, 1984."},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"A. Ben-Tal and A. Nemirovski,\n                      Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications\n                      , MPS-SIAM Ser. Optim. 2, SIAM, Philadelphia, 2001.","DOI":"10.1137\/1.9780898718829"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.2140\/pjm.1963.13.389"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02190180"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"A. E. Brouwer and W. H. Haemers,\n                      Distance-Regular Graphs\n                      , Springer, Berlin, 2012.","DOI":"10.1007\/978-1-4614-1939-6_12"},{"key":"atypb10","first-page":"85","author":"Brouwer A. E.","year":"1984","journal-title":"London"},{"key":"atypb11","first-page":"337","author":"Cameron P. J.","year":"1978","journal-title":"London"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-009-9045-5"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1137\/100816900"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0419"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-5-10"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0437847100"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1111\/j.1749-6632.1970.tb56460.x"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(70)90037-6"},{"key":"atypb19","unstructured":"M. Fazel,\n                      Matrix Rank Minimization with Applications\n                      , Ph.D. thesis, Stanford University, Stanford, CA, 2002."},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A"},{"key":"atypb21","first-page":"61","author":"Finke G.","year":"2011","journal-title":"Amsterdam"},{"key":"atypb22","unstructured":"C. Godsil,\n                      Algebraic Combinatorics\n                      , Chapman & Hall Math. Ser. 6, CRC Press, New York, 1993."},{"key":"atypb23","unstructured":"M. C. Grant and S. P. Boyd,\n                      CVX: Matlab Software for Disciplined Convex Programming\n                      ,http:\/\/cvxr.com\/cvx\/(2017)."},{"key":"atypb24","first-page":"95","author":"Grant M. C.","year":"2008","journal-title":"London"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1007\/BF00130574"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"R. M. Karp,\n                      Reducibility Among Combinatorial Problems\n                      , University of California, Berkeley, CA, 1972.","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"atypb27","first-page":"199","author":"Krivelevich M.","year":"2006","journal-title":"Berlin"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/0024-3795(77)90069-6"},{"key":"atypb29","first-page":"631","author":"Leskovec J.","year":"2010","journal-title":"New York"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1049\/iet-syb:20060038"},{"key":"atypb31","first-page":"56","author":"Mishra N.","year":"2007","journal-title":"Berlin"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00084-3"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0400054101"},{"key":"atypb34","doi-asserted-by":"publisher","DOI":"10.1137\/070697835"},{"key":"atypb35","unstructured":"R. T. Rockafellar,\n                      Convex Analysis\n                      , Princeton University Press, Princeton, NJ, 2015."},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1112\/S002557931100132X"},{"key":"atypb37","first-page":"185","author":"Seidel J. J.","year":"1969","journal-title":"London"},{"key":"atypb38","doi-asserted-by":"publisher","DOI":"10.1080\/10556789908805762"},{"key":"atypb39","first-page":"139","volume":"226","author":"E.","year":"1995","journal-title":"Linear Algebra Appl."},{"key":"atypb40","unstructured":"E. R. van Dam,\n                      Graphs with few eigenvalues. An Interplay between Combinatorics and Algebra\n                      , Ph.D. thesis, Tilburg University, Tilburg, The Netherlands, 1996."},{"key":"atypb41","doi-asserted-by":"publisher","DOI":"10.1016\/S0012-365X(98)00085-5"},{"key":"atypb42","first-page":"210","author":"Vershynin R.","year":"2012","journal-title":"Cambridge"},{"key":"atypb43","first-page":"286","volume":"1","author":"J","year":"1937","journal-title":"Tomsk Univ. Rev"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/16M1075144","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:15:49Z","timestamp":1787336149000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/16M1075144"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":43,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/16M1075144"],"URL":"https:\/\/doi.org\/10.1137\/16m1075144","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}