arXiv:1710.00264

Bayesian estimation from few samples: community detection and related problems

Samuel B. Hopkins, David Steurer

제출 2017-09-30

원문 초록

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.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2411.02835v3math.ST공통 태그 Community Detection, Stochastic Block Model

베테-헤시안을 이용한 커뮤니티 검출

Community detection with the Bethe-Hessian

Saade, Krzakala, Zdeborov\'a (2014)가 도입한 베테-헤시안 행렬은 희소 네트워크에 스펙트럴 클러스터링 알고리즘을 적용하기 위해 고안된 에르미트 행렬이다. 비대칭이며 고차원인 비역추적 연산자를 사용하는 대신, 베테-헤시안 행렬에 기반한 스펙트럴 방법 역시 희소 확률적 블록 모형(SBM)에서 케스텐-스티검 검출 임계값에 도달할 것으로 추측된다. 우리는 유계 기대 차수와 증가하는 차수의 두 영역 모두에서 SBM의 베테-헤시안 스펙트럴 방법에 대한 최초의 엄밀한 분석을 제공한다. 구체적으로 다음을 보인다. (i) 기대 차수 $d\geq 2$일 때, 베테-헤시안 행렬의 음의 이상치 개수는 케스텐-스티검 임계값 이상에서 블록의 수를 일치적으로 추정할 수 있으며, 따라서 $d\geq 2$에 대한 Saade, Krzakala, Zdeborov\'a (2014)의 추측을 확인한다. (ii) 충분히 큰 $d$에 대해, 그 고유벡터를 이용하여 약한 복원을 달성할 수 있다. (iii) $d\to\infty$일 때, 음의 이상치 고유값 위치의 집중성을 수립하며, 베테-헤시안 행렬에 기반한 스펙트럴 방법을 통해 약한 일치성을 달성할 수 있다.

arXiv:2607.09441v1math.ST공통 태그 Community Detection, Stochastic Block Model

다항 시간 내 준최적 노드-프라이빗 커뮤니티 추정

Near-optimal node-private community estimation in polynomial-time

이 논문에서 우리는 Klopp & Zadik (2026)의 미해결 문제를 해결하여, 확률적 블록 모델(stochastic block model)에서의 정확 복원(exact recovery)에 대해 그들의 지수 시간 노드-프라이빗 알고리즘의 성능에 근접하는, 높은 확률을 보장하는 다항 시간 노드-프라이빗 알고리즘을 제시한다. 우리의 결과는 페널티 가능도 함수에 대해 명시적으로 구성된 립시츠 대리 함수(Lipschitz surrogate)와, 다항 시간 내에 지수 메커니즘(exponential mechanism)으로부터 커뮤니티 레이블을 샘플링하는 신중하게 고안된 수용-기각 알고리즘(accept-reject algorithm)을 포함한다. 우리는 제안 알고리즘의 프라이버시, 실행 시간, 유용성을 엄밀하게 분석하며, 커뮤니티 수 K가 노드 수 n에 대해 로그 수준으로 증가하는 경우에도 프라이버시 매개변수 epsilon이 log(n)으로 증가할 때 정확 복원에 대한 미니맥스 수렴률을 달성할 수 있음을 보임으로써, 이 설정에서 프라이버시 비용에 관해 알려진 하한과 일치함을 증명한다.

arXiv:2509.15822v3stat.ML공통 태그 Community Detection, Stochastic Block Model

$\sqrt{n}$보다 많은 커뮤니티를 가진 확률적 블록 모델의 상전이

Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities

통계 물리학의 예측은 고정된 개수 $K$의 커뮤니티를 가진 확률적 블록 모델(SBM)에서 커뮤니티 복구가 Kesten-Stigum (KS) 임계값보다 위에서만 다항 시간 내에 가능하다고 가정합니다. 이 추측은 KS 임계값 위의 SBM에서 자명하지 않은 커뮤니티 복구가 실제로 가능하다는 것을 증명하는 풍부한 연구로 이어졌습니다. 관측된 그래프의 노드 수를 $n$이라 할 때, $K\ll \sqrt{n}$인 한 KS 임계값 아래에서 저차 다항식(LDP)의 실패 또한 증명되었습니다. $K\geq \sqrt{n}$일 때, Chin et al.(2025)은 최근 희소(sparse) 영역에서 비역행 경로(non-backtracking paths)를 계수함으로써 KS 임계값 아래에서도 다항 시간 내 커뮤니티 복구가 가능하다는 것을 증명했습니다. 이 획기적인 발견은 그들이 $K\geq \sqrt{n}$인 다중 커뮤니티 영역에 대한 새로운 임계값을 가정하게 이끌었습니다. 본 연구에서는 그들의 추측을 뒷받침하는 증거를 제시합니다: 1- 임의의 그래프 밀도에 대해, Chin et al.(2025)이 가정한 임계값 아래에서 LDP가 커뮤니티를 복구하는 데 실패함을 증명합니다; 2- LDP 분석에서 영감을 받은 특정 모티프(motifs)의 발생 횟수를 계수함으로써, Chin et al.(2025)에서 고려된 희소(sparse) 영역뿐만 아니라 중간 희소(moderately sparse) 영역에서도 가정된 임계값 위에서 다항 시간 내 커뮤니티 복구가 가능함을 증명합니다. 특히, 비역행 연산자(Non-Backtracking operator)에 기반한 스펙트럴 알고리즘(spectral algorithms)과 밀접하게 관련된 길이 $\log(n)$의 자기 회피 경로(self-avoiding paths) 계수는 희소 영역에서만 최적입니다. 더 조밀한 영역에서는 사이클의 확대(blow-up)에 기반한 더 복잡한 모티프를 고려해야 합니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.