arXiv:1407.5924

Resolution-limit-free and local Non-negative Matrix Factorization quality functions for graph clustering

Twan van Laarhoven, Elena Marchiori

제출 2014-07-22

원문 초록

Many graph clustering quality functions suffer from a resolution limit, the inability to find small clusters in large graphs. So called resolution-limit-free quality functions do not have this limit. This property was previously introduced for hard clustering, that is, graph partitioning. We investigate the resolution-limit-free property in the context of Non-negative Matrix Factorization (NMF) for hard and soft graph clustering. To use NMF in the hard clustering setting, a common approach is to assign each node to its highest membership cluster. We show that in this case symmetric NMF is not resolution-limit-free, but that it becomes so when hardness constraints are used as part of the optimization. The resulting function is strongly linked to the Constant Potts Model. In soft clustering, nodes can belong to more than one cluster, with varying degrees of membership. In this setting resolution-limit-free turns out to be too strong a property. Therefore we introduce locality, which roughly states that changing one part of the graph does not affect the clustering of other parts of the graph. We argue that this is a desirable property, provide conditions under which NMF quality functions are local, and propose a novel class of local probabilistic NMF quality functions for soft graph clustering.

함께 살펴볼 논문

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

arXiv:2607.13218v1cs.DS공통 태그 Clustering, graph partitioning

수요가 있는 그래프 분할: 일반화된 컨던턴스와 그 응용

Graph Partitioning with Demands: Generalized Conductance and its Applications

본 논문에서는 일반적인 수요 모델 하에서 다양한 그래프 분할 문제를 연구한다. 각 문제에서 용량 함수 $c\colon E\to \mathbb{N}$와 수요 함수 $w\colon V\times V\to \mathbb{N}$가 주어진 그래프 $G=(V,E,c,w)$가 주어진다. 우리의 주요 관심사는 컷 $(S, \bar{S})$를 찾아 다음 양을 최소화하는 문제이다. \[ ψ_w( S ) = \frac{c( S, \bar{S} )}{w( S, V )\cdot w( \bar{S}, V )}. \] 여기서 $c( S, \bar{S} )$는 $S$와 $S$의 여집합 $\bar{S}$ 사이의 간선 비용이며, $w( S, V )=w( S )+w( S, \bar{S} )$는 $S$ 내부의 내부 수요 $w( S )$와 $S$의 꼭짓점과 $\bar{S}$의 꼭짓점 사이의 수요 $w( S, \bar{S} )$의 합이다. $ψ_w( S )$를 컷 $(S, \bar{S})$의 \emph{generalized conductance}(일반화된 컨던턴스)라 하고, $ψ_w( S )$를 최소화하는 과제를 Generalized Conductance Problem(일반화된 컨던턴스 문제)라 부른다. 주요 기여는 이 목적함수에 대해 $\mathcal{O}(\log n)$-근사 보장을 갖는 알고리즘을 제시하는 것이다. 이 결과는 양방향 환원을 통해 달성된다. 먼저 잘 알려진 Generalized $k$-Multicut Problem으로 환원하고, 이어서 잘릴 수 있는 수요량에 대한 추가 상한 제약이 있는 고전 Sparsest-Cut Problem의 제약 변형으로 환원한다. 더 나아가, 위 절차가 수요가 있는 그래프 분할(Graph Partitioning with Demands)에 대해 $\mathcal{O}(\log n)$-이기준 근사를 얻는 데 사용될 수 있음을 보인다. 여기서 목표는 $G\setminus C$의 모든 연결 성분 $H$에 대해 $w( H )\leq ρ\cdot w( V )$를 만족하는 최소 비용의 간선 부분집합 $C$를 찾는 것이다. 이는 차례로 수요가 있는 계층적 클러스터링(Hierarchical Clustering with Demands)—그래프를 점점 더 세분화된 클러스터로 분할하는 컷의 계층을 찾는 문제—에 대한 $\mathcal{O}(\log n)$-근사를 제공한다. 곱셈형 수요 함수(multiplicative demand functions)의 경우 이러한 보장을 $\mathcal{O}(\sqrt{\log n})$로 개선하며, 트리(tree)의 경우 모든 목적함수에 대해 $\mathcal{O}(1)$-근사를 얻는다.

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)와 강건성 분석을 통해 실세계 대규모 그래프에서의 효과성과 신뢰성을 추가로 검증한다.

토론

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