Active Community Detection with Maximal Expected Model Change
원문 초록
We present a novel active learning algorithm for community detection on networks. Our proposed algorithm uses a Maximal Expected Model Change (MEMC) criterion for querying network nodes label assignments. MEMC detects nodes that maximally change the community assignment likelihood model following a query. Our method is inspired by detection in the benchmark Stochastic Block Model (SBM), where we provide sample complexity analysis and empirical study with SBM and real network data for binary as well as for the multi-class settings. The analysis also covers the most challenging case of sparse degree and below-detection-threshold SBMs, where we observe a super-linear error reduction. MEMC is shown to be superior to the random selection baseline and other state-of-the-art active learners.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
다항 시간 내 준최적 노드-프라이빗 커뮤니티 추정
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)에 기반한 더 복잡한 모티프를 고려해야 합니다.
TabPFN: One Model to Rule Them All?
Making Language Model a Hierarchical Classifier and Generator
Implementing Adaptations for Vision AutoRegressive Model
Graph World Model
토론
이 논문과 연결된 포럼 글이 아직 없습니다.