Semidefinite programs on sparse random graphs and their application to community detection

DOI10.1145/2897518.2897548MaRDI QIDQ5361882zbMATH OpenOpenAlexFDO

Authors Subhabrata Sen, Andrea Montanari

Publication date 29 September 2017

Published in Proceedings of the forty-eighth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

community detectionphase transitionssemidefinite programming relaxation

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Random graphs (graph-theoretic aspects) (05C80) Semidefinite programming (90C22) Programming involving graphs or networks (90C35)

Abstract: Denote by $A$ the adjacency matrix of an Erdos-Renyi graph with bounded average degree. We consider the problem of maximizing $langleA-EA,Xangle$ over the set of positive semidefinite matrices $X$ with diagonal entries $X_{ii}=1$. We prove that for large (bounded) average degree $d$, the value of this semidefinite program (SDP) is --with high probability-- $2nsqrtd+n,o(sqrtd)+o(n)$. For a random regular graph of degree $d$, we prove that the SDP value is $2nsqrtd-1+o(n)$, matching a spectral upper bound. Informally, Erdos-Renyi graphs appear to behave similarly to random regular graphs for semidefinite programming. We next consider the sparse, two-groups, symmetric community detection problem (also known as planted partition). We establish that SDP achieves the information-theoretically optimal detection threshold for large (bounded) degree. Namely, under this model, the vertex set is partitioned into subsets of size $n/2$, with edge probability $a/n$ (within group) and $b/n$ (across). We prove that SDP detects the partition with high probability provided $(a-b{)}^2/(4d)>1+o_d(1)$, with $d=(a+b)/2$. By comparison, the information theoretic threshold for detecting the hidden partition is $(a-b{)}^2/(4d)>1$: SDP is nearly optimal for large bounded average degree. Our proof is based on tools from different research areas: $(i)$ A new `higher-rank' Grothendieck inequality for symmetric matrices; $(ii)$ An interpolation method inspired from statistical physics; $(iii)$ An analysis of the eigenvectors of deformed Gaussian random matrices.

Recommendations

• Community detection in sparse networks via Grothendieck's inequality
• How well do local algorithms solve semidefinite programs?
• Community detection with a subsampled semidefinite program
• Phase transitions in semidefinite relaxations
• On semidefinite relaxations for the block model

Cited in

(50)

• Network models: structure and function. Abstracts from the workshop held December 10--16, 2017
• On semidefinite relaxations for the block model
• Convex relaxation methods for community detection
• Minimax rates in network analysis: graphon estimation, community detection and hypothesis testing
• Robust group synchronization via cycle-edge message passing
• Testing community structure for hypergraphs
• A likelihood-ratio type test for stochastic block models with bounded degrees
• Iterative algorithm for discrete structure recovery
• Community detection with a subsampled semidefinite program
• Hypothesis testing in sparse weighted stochastic block model
• Rate optimal Chernoff bound and application to community detection in the stochastic block models
• Mean estimation with sub-Gaussian rates in polynomial time
• Entrywise eigenvector analysis of random matrices with low expected rank
• TAP free energy, spin glasses and variational inference
• A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
• Phase transition in random tensors with multiple independent spikes
• Convexified modularity maximization for degree-corrected stochastic block models
• Exact recovery of community detection in k-partite graph models with applications to learning electric potentials in electric networks
• Phase transitions in semidefinite relaxations
• Community detection and stochastic block models: recent developments
• Optimal bipartite network clustering
• How well do local algorithms solve semidefinite programs?
• Strong consistency, graph Laplacians, and the stochastic block model
• Covariate regularized community detection in sparse graphs
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Semi-random Graphs with Planted Sparse Vertex Cuts: Algorithms for Exact and Approximate Recovery
• Graph powering and spectral robustness
• Disordered systems insights on computational hardness
• Optimal couplings between sparse block models
• Optimization of the Sherrington--Kirkpatrick Hamiltonian
• The Lovász theta function for random regular graphs and community detection in the hard regime
• The Ising Antiferromagnet and Max Cut on Random Regular Graphs
• Hidden Integrality and Semirandom Robustness of SDP Relaxation for Sub-Gaussian Mixture Model
• Local convexity of the TAP free energy and AMP convergence for \(\mathbb{Z}_2\)-synchronization
• Linear Programming and Community Detection
• Algorithms approaching the threshold for semi-random planted clique
• A review on quantum approximate optimization algorithm and its variants
• A polynomial-time approximation scheme for the maximal overlap of two independent Erdős-Rényi graphs
• Partial recovery and weak consistency in the non-uniform hypergraph stochastic block model
• Orthogonal symmetric non-negative matrix factorization under the stochastic block model
• Asymptotic mutual information in quadratic estimation problems over compact groups
• Optimization of the Sherrington-Kirkpatrick Hamiltonian
• Exact threshold for approximate ellipsoid fitting of random points
• Semi-supervised clustering of sparse graphs: crossing the information-theoretic threshold
• Information-theoretic limits for testing community structures in weighted networks
• Fair community detection and structure learning in heterogeneous graphical models
• A CLuP algorithm to practically achieve 0.76 SK-model ground state free energy
• New methods for testing community structures in general networks
• Triangles improve 0.878 approximation for Maxcut
• Community detection in sparse networks via Grothendieck's inequality

This page was built for publication: Semidefinite programs on sparse random graphs and their application to community detection

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