arXiv:1908.02096

Hermitian matrices for clustering directed graphs: insights and applications

Mihai Cucuringu, Huan Li, He Sun, Luca Zanetti

제출 2019-08-06

원문 초록

Graph clustering is a basic technique in machine learning, and has widespread applications in different domains. While spectral techniques have been successfully applied for clustering undirected graphs, the performance of spectral clustering algorithms for directed graphs (digraphs) is not in general satisfactory: these algorithms usually require symmetrising the matrix representing a digraph, and typical objective functions for undirected graph clustering do not capture cluster-structures in which the information given by the direction of the edges is crucial. To overcome these downsides, we propose a spectral clustering algorithm based on a complex-valued matrix representation of digraphs. We analyse its theoretical performance on a Stochastic Block Model for digraphs in which the cluster-structure is given not only by variations in edge densities, but also by the direction of the edges. The significance of our work is highlighted on a data set pertaining to internal migration in the United States: while previous spectral clustering algorithms for digraphs can only reveal that people are more likely to move between counties that are geographically close, our approach is able to cluster together counties with a similar socio-economical profile even when they are geographically distant, and illustrates how people tend to move from rural to more urbanised areas.

함께 살펴볼 논문

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

arXiv:2607.09441v1math.ST공통 태그 Clustering, 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:2607.05469v1cs.LG공통 태그 Clustering, Graph Clustering

구조적 고립 극복: 커뮤니티 인식 샘플링과 구조적 엔트로피를 통한 확장 가능한 그래프 클러스터링

Breaking Structural Isolation: Scalable Graph Clustering via Community-Aware Sampling and Structural Entropy

비지도 그래프 클러스터링은 대규모 네트워크에서 내재된 의미적 패턴을 발견하기 위한 핵심 기법이다. 그래프 대조 학습(Graph Contrastive Learning)이 유망한 성능을 보여주었음에도 불구하고, 기존 방법들은 미니배치 학습 과정에서 흔히 "구조적 고립(structural isolation)" 문제를 겪으며, 이로 인해 전역 위상 분포를 특징짓는 응집력 있는 커뮤니티 구조를 포착하기 어렵다. 이러한 문제를 해결하기 위해, 우리는 커뮤니티 인식 샘플링과 제약된 구조적 엔트로피(Structural Entropy)를 결합하여 구조적 무결성을 보존하는 확장 가능한 비지도 그래프 클러스터링 프레임워크인 SCISE를 제안한다. 구체적으로, 먼저 구조적 엔트로피 커뮤니티 제약 연산자(SECC)를 도입하여 제약된 해 공간 내에서 구조 정보를 최적화함으로써 커뮤니티 단편화를 완화하고 파티션 응집도를 향상시킨다. 다음으로, 배치 학습 중 전역 정보 손실을 방지하기 위해, 대상 노드의 커뮤니티 컨텍스트를 샘플링 배치에 통합하는 커뮤니티 인식 샘플링 확장(CSampE) 메커니즘을 설계하여 구조적 장벽을 효과적으로 극복하고 위상적 무결성을 보존한다. 마지막으로, 배치 내 구조적 유사도에 기반하여 에지 가중치를 정제하는 구조적 대조 학습(StructCL) 모듈을 고안하여 인코더가 고차 구조 공간에서 표현을 학습하도록 유도한다. 6개의 주류 벤치마크 데이터셋에 대한 광범위한 실험을 통해 SCISE가 최신 알고리즘들을 크게 능가함을 입증하며, 소거 연구(ablation studies)와 강건성 분석을 통해 실세계 대규모 그래프에서의 효과성과 신뢰성을 추가로 검증한다.

토론

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