arXiv:1609.02487

Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models

Lennart Gulikers, Marc Lelarge, Laurent Massoulié

제출 2016-09-08

원문 초록

Motivated by community detection, we characterise the spectrum of the non-backtracking matrix $B$ in the Degree-Corrected Stochastic Block Model. Specifically, we consider a random graph on $n$ vertices partitioned into two equal-sized clusters. The vertices have i.i.d. weights $\{ \phi_u \}_{u=1}^n$ with second moment $\Phi^{(2)}$. The intra-cluster connection probability for vertices $u$ and $v$ is $\frac{\phi_u \phi_v}{n}a$ and the inter-cluster connection probability is $\frac{\phi_u \phi_v}{n}b$. We show that with high probability, the following holds: The leading eigenvalue of the non-backtracking matrix $B$ is asymptotic to $\rho = \frac{a+b}{2} \Phi^{(2)}$. The second eigenvalue is asymptotic to $\mu_2 = \frac{a-b}{2} \Phi^{(2)}$ when $\mu_2^2 > \rho$, but asymptotically bounded by $\sqrt{\rho}$ when $\mu_2^2 \leq \rho$. All the remaining eigenvalues are asymptotically bounded by $\sqrt{\rho}$. As a result, a clustering positively-correlated with the true communities can be obtained based on the second eigenvector of $B$ in the regime where $\mu_2^2 > \rho.$ In a previous work we obtained that detection is impossible when $\mu_2^2 < \rho,$ meaning that there occurs a phase-transition in the sparse regime of the Degree-Corrected Stochastic Block Model. As a corollary, we obtain that Degree-Corrected Erd\H{o}s-R\'enyi graphs asymptotically satisfy the graph Riemann hypothesis, a quasi-Ramanujan property. A by-product of our proof is a weak law of large numbers for local-functionals on Degree-Corrected Stochastic Block Models, which could be of independent interest.

함께 살펴볼 논문

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

arXiv:2607.09441v1math.ST공통 태그 Clustering, 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:2609.30277v2cs.LG공통 태그 Clustering, Community Detection

고정된 확산 없는 고정점: 수렴하는 테스트 시점 연산을 위한 암시적 신경 층

Fixed Points Without Fixed Diffusion: Implicit Neural Sheaves for Convergent Test-Time Computation

암시적 그래프 신경망(IGNN)은 노드 표현을 그래프 신경 연산자의 고정점(fixed point)으로 정의하여 실질적으로 무한한 깊이의 전파, 반복(iteration) 독립적인 매개변수화, 유연한 테스트 시점 연산(test-time computation)을 가능하게 합니다. 그러나 이러한 이점은 평형점이 유일하며 고정점 반복을 통해 도달할 수 있는지 여부에 달려 있습니다. 기존의 구조들은 이러한 보장을 얻기 위해 순환 업데이트에 제약을 가하는 경우가 많아 평형 상태에서 사용 가능한 변환을 제한했습니다. 이는 핵심적인 질문을 제기합니다: IGNN이 평형 정식화의 고유한 강점을 유지하면서 더 풍부한 엣지 의존적 변환을 통해 표현력을 얻을 수 있을까요? 본 논문에서는 적응형 신경 층(neural-sheaf) 전파를 갖춘 준동차(subhomogeneous) 심층 평형 아키텍처인 SheafDEQ를 소개합니다. 학습된 행렬 값 층 제한 사상(sheaf restriction map)은 이웃한 표현들을 정렬, 혼합 또는 반전시킬 수 있습니다. 완만한 정칙성 조건 하에서, SheafDEQ가 임의의 양의 초기 상태로부터 고정점 반복을 통해 전역적으로 도달 가능한 유일한 평형점을 가짐을 증명합니다. 나아가 축약성(contractivity)은 유계된 통신 지연(staleness) 하에서도 수렴을 보장합니다. 본 연구는 반복적인 비국소적 집계가 필요한 분산 추론(inference) 태스크와 연결 재구성이 점차 커뮤니티 간 상호작용을 선호하게 되는 커뮤니티 탐지 태스크에서 SheafDEQ를 평가합니다. SheafDEQ는 Sums, MNIST Terrain, Coordinates 태스크 및 연결성이 점차 이종친화적(heterophilic)으로 변하는 커뮤니티 탐지에서 암시적 베이스라인보다 향상된 성능을 보입니다. 또한 SheafDEQ는 평형 보장이 없는 순환 모델들과 비교해도 경쟁력을 유지합니다. 연속 반복 진단 결과 유한 구간(finite-horizon) 대조군과 달리 100회 반복까지 잔차가 감소하고 테스트 정확도가 유지됨을 확인하였으며, 지연 업데이트 실험에서는 유계된 통신 지연에 대해 낮은 민감도를 나타냈습니다.

arXiv:2607.21039v1cs.LG공통 태그 Clustering, Community Detection

Grassmann 다양체 상의 정규화 최적화: 이론, 알고리즘 및 응용

Regularized Optimization on Grassmann Manifold: Theory, Algorithm and Applications

스펙트럴 방법은 커뮤니티 탐지, 클러스터링, 그래프 학습에서 가장 널리 사용되는 기법 중 하나이다. 그러나 그 성능은 근본적인 스펙트럴 부분공간의 정확한 추정에 크게 의존하며, 노이즈, 이상치, 또는 모델 교란이 존재할 경우 상당히 악화될 수 있다. 이 한계를 해결하기 위해, 우리는 rank-$K$ 투영 행렬의 강건한 추정을 위한 정규화 투영 행렬 근사(Regularized Projection Matrix Approximation, RPMA) 프레임워크를 제안한다. RPMA는 정규화 항을 통합하여 고전적인 스펙트럴 투영을 확장하며, 더 강건하고 희소하며 해석 가능한 투영 추정치를 생성한다. 우리는 제안된 모델을 rank-$K$ 투영 행렬의 다양체 상의 최적화 문제로 공식화하고, Grassmann 다양체와의 기하학적 동등성을 활용한다. 이 다양체 특성화를 바탕으로, 1차 및 2차 최적성 조건을 유도하고, 정규화된 선행 고유공간의 국소 안정성을 확립하며, 충분히 작은 정규화 하에서 임계점 경관의 안정성을 특성화한다. 결과적인 비볼록 최적화 문제를 효율적으로 풀기 위해, 역추적 선 탐색(backtracking line search)을 갖춘 Riemann 그래디언트 투영 알고리즘과, 반복적인 고유값 분해를 피하는 보다 효율적인 Cayley--Sherman--Morrison--Woodbury(Cayley--SMW) 그래디언트 방법을 개발한다. 합성 및 실제 데이터셋에 대한 광범위한 실험은 RPMA가 투영 행렬의 복원 정확도를 크게 향상시키며, 노이즈가 있는 환경에서 커뮤니티 탐지 및 클러스터링을 위한 기존 스펙트럴 투영 방법보다 일관되게 우수한 성능을 보임을 입증한다.

arXiv:2606.30249v1cs.LG공통 태그 Clustering, Community Detection

이종친화 그래프에서 비지도 커뮤니티 탐지를 위한 곡률 유도 시프 확산

Curvature-Guided Sheaf Diffusion for Unsupervised Community Detection on Heterophilic Graphs

연결된 노드가 서로 다른 클래스에 속하는 경우가 많은 이종친화(heterophilic) 그래프에서의 커뮤니티 탐지는 비지도 방법에 있어 어려운 문제이다. 고전적인 모듈성(modularity) 및 스펙트럼 방법은 특징(feature)에 무관하고, 심층 그래프 클러스터링 방법은 불투명한 대조적(contrastive) 또는 생성적(generative) 메커니즘에 의존한다. 본 논문에서는 각 에지의 이산 Forman--Ricci 곡률을 단일 위상 신호로 활용하여 엔드투엔드 파이프라인의 모든 단계에 전파하는 완전 비지도 커뮤니티 탐지 알고리즘인 Curvature-Guided Sheaf Diffusion(CGSD)을 제안한다. CGSD는 세 가지 구체적인 기여를 한다: (i) 에지 메시지를 $σ(κ_e)$로 게이팅하고 세 가지 레이블 없는 구조적 손실(모듈성, 반붕괴, 곡률 가중 재구성)로 학습되는 곡률 게이팅 시프 확산 인코더; (ii) Ng--Jordan--Weiss 적용 전 임베딩의 $k$-NN 친화도를 $σ(ακ_{e^*})$로 재가중하는 곡률 인식 스펙트럴 클러스터러(CSpec); (iii) 9개의 완전 비지도 기준선(baseline)에 대한 통합 레이블 없는 평가. 다섯 개의 이종친화 벤치마크(Cora, Cornell, Texas, Wisconsin, Chameleon)에서 CGSD는 Wisconsin과 Chameleon에서 1위를 차지하고 나머지 세 개에서도 9개의 비지도 기준선(baseline)과 경쟁력 있는 성능을 보인다. 최강 기준선(baseline) 대비 성능 향상은 인코더가 아닌 클러스터러에서 비롯된다: 동일한 임베딩에서 CSpec은 $K$-Means의 평균 NMI $0.091$을 $0.107$로 개선한다($+15\%$, 대응 $t$-검정 $p=0.008$). 그 메커니즘은 해석 가능하다: 커뮤니티 내부 및 커뮤니티 간 곡률 분포가 시각적으로 뚜렷하게 분리된다. 코드는 https://github.com/woodywff/cgsd에 오픈소스로 공개되어 있다.

토론

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