Bayesian estimation from few samples: community detection and related problems
We propose an efficient meta-algorithm for Bayesian estimation problems that is based on low-degree polynomials, semidefinite programming, and tensor decomposition. The algorithm is inspired by recent lower bound constructions for sum-of-squares and related to the method of moments. Our focus is on sample complexity bounds that are as tight as possible (up to additive lower-order terms) and often achieve statistical thresholds or conjectured computational thresholds. Our algorithm recovers the best known bounds for community detection in the sparse stochastic block model, a widely-studied class of estimation problems for community detection in graphs. We obtain the first recovery guarantees for the mixed-membership stochastic block model (Airoldi et el.) in constant average degree graphs---up to what we conjecture to be the computational threshold for this model. We show that our algorithm exhibits a sharp computational threshold for the stochastic block model with multiple communities beyond the Kesten--Stigum bound---giving evidence that this task may require exponential time. The basic strategy of our algorithm is strikingly simple: we compute the best-possible low-degree approximation for the moments of the posterior distribution of the parameters and use a robust tensor decomposition algorithm to recover the parameters from these approximate posterior moments.
Code (0)
등록된 구현이 없습니다.
Tasks
Community DetectionStochastic Block ModelTensor DecompositionSimilar Papers 제목 키워드 기반
Hierarchical Bayesian inference for community detection and connectivity of functional brain networks
Many functional magnetic resonance imaging (fMRI) studies rely on estimates of hierarchically organised brain networks whose segregation and integration reflect the dynamic transitions of latent cognitive states. However…
Bayesian InferenceCommunity DetectionUncertainty-Based Out-of-Distribution Detection in Deep Reinforcement Learning
We consider the problem of detecting out-of-distribution (OOD) samples in deep reinforcement learning. In a value based reinforcement learning setting, we propose to use uncertainty estimation techniques directly on the …
Bayesian InferenceDeep Reinforcement LearningOpen-Ended Question AnsweringOut-of-Distribution Detection+4Reliable data clustering with Bayesian community detection
From neuroscience and genomics to systems biology and ecology, researchers rely on clustering similarity data to uncover modular structure. Yet widely used clustering methods, such as hierarchical clustering, k-means, an…
Community DetectionFully Bayesian Wideband Direction-of-Arrival Estimation and Detection via RJMCMC
We propose a fully Bayesian approach to wideband, or broadband, direction-of-arrival (DoA) estimation and signal detection. Unlike previous works in wideband DoA estimation and detection, where the signals were modeled i…
Direction of Arrival EstimationBayesian community detection for networks with covariates
The increasing prevalence of network data in a vast variety of fields and the need to extract useful information out of them have spurred fast developments in related models and algorithms. Among the various learning tas…
Community DetectionStochastic Block Model