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.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Community and hyperedge inference in multiple hypergraphs
Communities in the Kuramoto Model: Dynamics and Detection via Path Signatures
VEC-SBM: Optimal Community Detection with Vectorial Edges Covariates
베테-헤시안을 이용한 커뮤니티 검출
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$일 때, 음의 이상치 고유값 위치의 집중성을 수립하며, 베테-헤시안 행렬에 기반한 스펙트럴 방법을 통해 약한 일치성을 달성할 수 있다.
다항 시간 내 준최적 노드-프라이빗 커뮤니티 추정
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)으로 증가할 때 정확 복원에 대한 미니맥스 수렴률을 달성할 수 있음을 보임으로써, 이 설정에서 프라이버시 비용에 관해 알려진 하한과 일치함을 증명한다.
$\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)에 기반한 더 복잡한 모티프를 고려해야 합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.