Resampled Mutual Information for Clustering and Community Detection
원문 초록
We introduce resampled mutual information (ResMI), a novel measure of clustering similarity that combines insights from information theoretic and pair counting approaches to clustering and community detection. Similar to chance-corrected measures, ResMI satisfies the constant baseline property, but it has the advantages of not requiring adjustment terms and being fully interpretable in the language of information theory. Experiments on synthetic datasets demonstrate that ResMI is robust to common biases exhibited by existing measures, particularly in settings with high cluster counts and asymmetric cluster distributions. Additionally, we show that ResMI identifies meaningful community structures in two real contact tracing networks.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
고정된 확산 없는 고정점: 수렴하는 테스트 시점 연산을 위한 암시적 신경 층
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회 반복까지 잔차가 감소하고 테스트 정확도가 유지됨을 확인하였으며, 지연 업데이트 실험에서는 유계된 통신 지연에 대해 낮은 민감도를 나타냈습니다.
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가 투영 행렬의 복원 정확도를 크게 향상시키며, 노이즈가 있는 환경에서 커뮤니티 탐지 및 클러스터링을 위한 기존 스펙트럴 투영 방법보다 일관되게 우수한 성능을 보임을 입증한다.
다항 시간 내 준최적 노드-프라이빗 커뮤니티 추정
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)으로 증가할 때 정확 복원에 대한 미니맥스 수렴률을 달성할 수 있음을 보임으로써, 이 설정에서 프라이버시 비용에 관해 알려진 하한과 일치함을 증명한다.
이종친화 그래프에서 비지도 커뮤니티 탐지를 위한 곡률 유도 시프 확산
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에 오픈소스로 공개되어 있다.
MRAEA: An Efficient and Robust Entity Alignment Approach for Cross-lingual Knowledge Graph
Using deep learning for community discovery in social networks
토론
이 논문과 연결된 포럼 글이 아직 없습니다.