arXiv:1511.00546

An Impossibility Result for Reconstruction in a Degree-Corrected Planted-Partition Model

Lennart Gulikers, Marc Lelarge, Laurent Massoulié

제출 2015-11-02

원문 초록

We consider the Degree-Corrected Stochastic Block Model (DC-SBM): a random graph on $n$ nodes, having i.i.d. weights $(\phi_u)_{u=1}^n$ (possibly heavy-tailed), partitioned into $q \geq 2$ asymptotically equal-sized clusters. The model parameters are two constants $a,b > 0$ and the finite second moment of the weights $\Phi^{(2)}$. Vertices $u$ and $v$ are connected by an edge with probability $\frac{\phi_u \phi_v}{n}a$ when they are in the same class and with probability $\frac{\phi_u \phi_v}{n}b$ otherwise. We prove that it is information-theoretically impossible to estimate the clusters in a way positively correlated with the true community structure when $(a-b)^2 \Phi^{(2)} \leq q(a+b)$. As by-products of our proof we obtain $(1)$ a precise coupling result for local neighbourhoods in DC-SBM's, that we use in a follow up paper [Gulikers et al., 2017] to establish a law of large numbers for local-functionals and $(2)$ that long-range interactions are weak in (power-law) DC-SBM's.

함께 살펴볼 논문

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

arXiv:2209.00546v5stat.ML공통 태그 Stochastic Block Model공식 코드 · Papers with Code

MSGNN: 새로운 자기 부호 라플라시안 기반의 스펙트럼 그래프 신경망

MSGNN: A Spectral Graph Neural Network Based on a Novel Magnetic Signed Laplacian

부호가 있고 방향성이 있는 네트워크는 실제 응용 분야 도처에 존재합니다. 그러나 이러한 네트워크를 위한 스펙트럼 그래프 신경망(GNN)을 제안한 연구는 비교적 적었습니다. 본 논문에서는 부호 그래프에서의 부호 라플라시안과 방향성 그래프에서의 자기 라플라시안(magnetic Laplacian)을 자연스럽게 일반화한, 자기 부호 라플라시안(magnetic signed Laplacian)이라 부르는 부호 방향 라플라시안 행렬을 도입합니다. 이어 이 행렬을 사용하여 새로운 효율적인 스펙트럼 GNN 아키텍처를 구축하고, 노드(node) 클러스터링 및 링크 예측 태스크 모두에서 광범위한 실험을 수행합니다. 이 실험들에서는 부호 정보 관련 태스크, 방향 정보 관련 태스크, 그리고 부호 및 방향 정보 모두와 관련된 태스크를 다룹니다. 제안된 스펙트럼 GNN이 부호 및 방향 정보를 모두 반영하는 데 효과적이며 광범위한 데이터셋에서 최고 수준의 성능을 달성함을 입증합니다. 추가로, 부호 방향 확률적 블록 모델(Signed Directed Stochastic Block Model)이라 부르는 새로운 합성 네트워크 모델(model)과 금융 시계열의 리드-래그(lead-lag) 관계에 기반한 다수의 새로운 실제 데이터셋을 제공합니다.

토론

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