Learning Communities in the Presence of Errors
원문 초록
We study the problem of learning communities in the presence of modeling errors and give robust recovery algorithms for the Stochastic Block Model (SBM). This model, which is also known as the Planted Partition Model, is widely used for community detection and graph partitioning in various fields, including machine learning, statistics, and social sciences. Many algorithms exist for learning communities in the Stochastic Block Model, but they do not work well in the presence of errors. In this paper, we initiate the study of robust algorithms for partial recovery in SBM with modeling errors or noise. We consider graphs generated according to the Stochastic Block Model and then modified by an adversary. We allow two types of adversarial errors, Feige---Kilian or monotone errors, and edge outlier errors. Mossel, Neeman and Sly (STOC 2015) posed an open question about whether an almost exact recovery is possible when the adversary is allowed to add $o(n)$ edges. Our work answers this question affirmatively even in the case of $k>2$ communities. We then show that our algorithms work not only when the instances come from SBM, but also work when the instances come from any distribution of graphs that is $\epsilon m$ close to SBM in the Kullback---Leibler divergence. This result also works in the presence of adversarial errors. Finally, we present almost tight lower bounds for two communities.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
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)에 기반한 더 복잡한 모티프를 고려해야 합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.