Convex Optimization for the Densest Subgraph and Densest Submatrix Problems

Karp R (1972) Reducibility among combinatorial problems. Complexity of Computer Computations 40(4):85–103

Alon N, Arora S, Manokaran R, Moshkovitz D, Weinstein O (2011) Inapproximability of densest κ-subgraph from average case hardness. Unpublished manuscript 1

Feige U (2002) Relations between average case complexity and approximation complexity. In: Proceedings of the thiry-fourth annual ACM symposium on theory of computing. ACM, pp 534–543

Khot S (2006) Ruling out PTAS for graph min-bisection, dense k-subgraph, and bipartite clique. SIAM J Comput 36(4):1025–1071

Henzinger MR, Motwani R, Silverstein C (2002) Challenges in web search engines. In: ACM SIGIR forum, vol 36. ACM, pp 11–22

Gibson D, Kumar R, Tomkins A (2005) Discovering large dense subgraphs in massive graphs. In: Böhm K, Jensen C S, Haas L M, Kersten M L, Larson P, Ooi BC (eds) Proceedings of the 31st International Conference on Very Large Data Bases, Trondheim, Norway, August 30 - September 2, 2005. ACM, pp 721–732

Angel A, Koudas N, Sarkas N, Srivastava D (2012) Dense subgraph maintenance under streaming edge weight updates for real-time story identification. Proc. VLDB Endow. 5(6):574–585

Gajewar A, Das Sarma A (2012) Multi-skill collaborative teams based on densest subgraphs. In: Proceedings of the 2012 SIAM international conference on data mining. SIAM, pp 165–176

Tsourakakis C (2015) The k-clique densest subgraph problem. In: Proceedings of the 24th international conference on world wide web. International World Wide Web Conferences Steering Committee, pp 1122–1132

Tsourakakis C, Bonchi F, Gionis A, Gullo F, Tsiarli M (2013) Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. In: Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, pp 104–112

Abbe E, Bandeira A, Hall G (2016) Exact recovery in the stochastic block model. IEEE Trans Inf Theory 62(1):471–487

Ailon N, Chen Y, Xu H (2013) Breaking the small cluster barrier of graph clustering. In: International conference on machine learning, pp 995–1003

Ames B, Vavasis S (2014) Convex optimization for the planted k-disjoint-clique problem. Math Program 143(1-2):299–337

Ames B (2014) Guaranteed clustering and biclustering via semidefinite programming. Math Program 147(1-2):429–465

Amini A, Levina E (2018) On semidefinite relaxations for the block model. Ann Stat 46(1):149– 179

Cai T, Li X (2015) Robust and computationally feasible community detection in the presence of arbitrary outlier nodes. Ann Stat 43(3):1027–1059

Chen Y, Jalali A, Sanghavi S, Xu H (2014) Clustering partially observed graphs via convex optimization. The Journal of Machine Learning Research 15(1):2213–2238

Chen Y, Sanghavi S, Xu H (2014) Improved graph clustering. IEEE Trans Inf Theory 60(10):6440–6455

Chen Y, Xu J (2014) Statistical-computational phase transitions in planted models: the high-dimensional setting. In: International conference on machine learning, pp 244–252

Guédon O, Vershynin R (2015) Community detection in sparse networks via Grothendieck’s inequality. Probab Theory Relat Fields, pp 1–25

Hajek B, Wu Y, Xu J (2015) Achieving exact cluster recovery threshold via semidefinite programming. In: IEEE international symposium on information theory. IEEE, pp 1442–1446

Lei J, Rinaldo A (2015) Consistency of spectral clustering in stochastic block models. Ann Stat 43(1):215–237

Mathieu C, Schudy W (2010) Correlation clustering with noisy input. In: ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, pp 712–728

Nellore A, Ward R (2015) Recovery guarantees for exemplar-based clustering. Inf Comput 245:165–180

Oymak S, Hassibi B (2011) Finding dense clusters via “low rank + sparse” decomposition. arXiv:1104.5186

Rohe K, Chatterjee S, Yu B (2011) Spectral clustering and the high-dimensional stochastic blockmodel. Ann Stat 39(4):1878–1915

Qin T, Rohe K (2013) Regularized spectral clustering under the degree-corrected stochastic blockmodel. In: Advances in neural information processing systems, pp 3120–3128

Vinayak R, Oymak S, Hassibi B (2014) Sharp performance bounds for graph clustering via convex optimization. In: IEEE international conference on acoustics, speech and signal processing (ICASSP). IEEE, pp 8297–8301

Holland PW, Laskey KB, Leinhardt S (1983) Stochastic blockmodels: first steps. Social networks 5(2):109–137

Li X, Chen Y, Xu J (2018) Convex relaxation methods for community detection. arXiv:1810.00315

Ames B, Vavasis SA (2011) Nuclear norm minimization for the planted clique and biclique problems. Mathematical Programming 129(1):69–89

Ames B (2015) Guaranteed recovery of planted cliques and dense subgraphs by convex relaxation. J Optim Theory Appl 167(2):653–675

Bomze IM, Budinich M, Pardalos PM, Pelillo M (1999) The maximum clique problem. In: Handbook of combinatorial optimization. Springer, pp 1–74

Pardalos PM, Xue J (1994) The maximum clique problem. Journal of global Optimization 4(3):301–328

Deshpande Y, Montanari A (2015) Finding hidden cliques of size $\sqrt {N/e}$ in nearly linear time. Found Comput Math 15(4):1069–1128

Montanari A (2015) Finding one community in a sparse graph. J Stat Phys 161(2):273–299

Hajek B, Wu Y, Xu J (2017) Information limits for recovering a hidden community. IEEE Trans Inf Theory 63(8):4729–4745

Hajek B, Wu Y, Xu J (2016) Semidefinite programs for exact recovery of a hidden community. In: Conference on learning theory, pp 1051–1095

Saad H, Nosratinia A (2018) Belief propagation with side information for recovering a single community. In: 2018 IEEE international symposium on information theory (ISIT). IEEE, pp 1271–1275

Hajek B, Wu Y, Xu J (2018) Recovering a hidden community beyond the Kesten–Stigum threshold in O(|E|log∗|V |) time. J Appl Probab 55(2):325–352. https://doi.org/10.1017/jpr.2018.22. ISSN:0021-9002, 62H12 (60C05) 3832891 https://doi.org/10.1017/jpr.2018.22

Hajek B, Wu Y, Xu J (2017) Submatrix localization via message passing. J Machine Learn Res 18(1):6817–6868

Banks J, Moore C, Vershynin R, Verzelen N, Xu J (2018) Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization. IEEE Trans Inform Theory

Brennan M, Bresler G, Huleihel W (2019) Universality of computational lower bounds for submatrix detection. arXiv:1902.06916

Chen Y, Sanghavi S, Xu H (2012) Clustering sparse graphs. In: Advances in neural information processing systems, pp 2204–2212

Recht B, Fazel M, Parrilo PA (2010) Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev 52 (3):471–501

Alon N, Krivelevich M, Sudakov B (1998) Finding a large hidden clique in a random graph. Random Structures and Algorithms 13(3-4):457–466

Feige U, Ron D (2010) Finding hidden cliques in linear time. In: 21st international meeting on probabilistic, combinatorial, and asymptotic methods in the analysis of algorithms (AofA’10). Discrete Mathematics and Theoretical Computer Science, pp 189–204

Dekel Y, Gurel-Gurevich O, Peres Y (2014) Finding hidden cliques in linear time with high probability. Comb Probab Comput 23(1):29–49

Juels A, Peinado M (2000) Hiding cliques for cryptographic security. Des Codes Crypt 20(3):269–280

Golub G, Van Loan C (1996) Matrix computations. Johns Hopkins University Press

Boucheron S, Lugosi G, Massart P (2013) Concentration inequalities: a nonasymptotic theory of independence. Oxford University Press

Bandeira AS, van Handel R (2014) Sharp nonasymptotic bounds on the norm of random matrices with independent entries. Annals of Probability to appear

Boyd S, Parikh N, Chu E, Peleato B, Eckstein J, et al. (2011) Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends®;, in Machine learning 3(1):1–122

Bader DA, Meyerhenke H, Sanders P, Wagner D (2012) Graph partitioning and graph clustering. In: 10th DIMACS implementation challenge workshop

Bader DA, Meyerhenke H, Sanders P, Schulz C, Kappes A, Wagner D (2014) Benchmarking for graph clustering and partitioning. Encyclopedia of Social Network Analysis and Mining, pp 73–82

Gleiser P, Danoni L (2003) Community structure in jazz. Advances in Complex Systems 6(4):565–573

Bastian M, Heymann S, Jacomy M (2009) Gephi: an open source software for exploring and manipulating networks. In: Third international AAAI conference on weblogs and social media

Jacomy M, Venturini T, Heymann S, Bastian M (2014) ForceAtlas2, a continuous graph layout algorithm for handy network visualization designed for the Gephi software. PloS one 9(6):e98,679

Tsourakakis C, Bonch F (2013) Denser than the densest subgraph: extracting optimal quasi-cliques with quality guarantees. KDD ’13 Proceedings of the 19th ACM SIGKDD international conference on Knowledge discovery and data mining, pp 104–112

Sotirov R (2019) On solving the densest k-subgraph problem on large graphs. arXiv:1901.06344

Tropp JA, et al. (2015) An introduction to matrix concentration inequalities. Foundations and Trends®;, in Machine Learning 8(1-2):1–230

Tropp JA (2012) User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics 12(4):389–434