Effective and Scalable Clustering on Massive Attributed Graphs
원문 초록
Given a graph G where each node is associated with a set of attributes, and a parameter k specifying the number of output clusters, k-attributed graph clustering (k-AGC) groups nodes in G into k disjoint clusters, such that nodes within the same cluster share similar topological and attribute characteristics, while those in different clusters are dissimilar. This problem is challenging on massive graphs, e.g., with millions of nodes and billions of edges. For such graphs, existing solutions either incur prohibitively high costs, or produce clustering results with compromised quality. In this paper, we propose ACMin, an effective approach to k-AGC that yields high-quality clusters with cost linear to the size of the input graph G. The main contributions of ACMin are twofold: (i) a novel formulation of the k-AGC problem based on an attributed multi-hop conductance quality measure custom-made for this problem setting, which effectively captures cluster coherence in terms of both topological proximities and attribute similarities, and (ii) a linear-time optimization solver that obtains high-quality clusters iteratively, based on efficient matrix operations such as orthogonal iterations, an alternative optimization approach, as well as an initialization technique that significantly speeds up the convergence of ACMin in practice. Extensive experiments, comparing 11 competitors on 6 real datasets, demonstrate that ACMin consistently outperforms all competitors in terms of result quality measured against ground-truth labels, while being up to orders of magnitude faster. In particular, on the Microsoft Academic Knowledge Graph dataset with 265.2 million edges and 1.1 billion attribute values, ACMin outputs high-quality results for 5-AGC within 1.68 hours using a single CPU core, while none of the 11 competitors finish within 3 days.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
RAMP: 엣지 CPU 비전 모델을 위한 강건한 적응형 혼합 정밀도 양자화
RAMP: Robust Adaptive Mixed-Precision Quantization for Edge CPU Vision Models
엣지 CPU에 심층 학습 모델을 배포할 때는 계산 및 메모리 제약이 병목이 된다. 혼합 정밀도 양자화는 정확도를 유지하면서 추론 지연을 줄일 수 있다고 기대된다. 그러나 양자화는 층 유형마다 서로 다르게 영향을 미치므로, 정확도 손실이 최소화되고 지연 감소가 최대화되는 위치를 찾는 것이 중요하며, 그 효과는 전체 배포에 걸쳐 누적되어 상당한 이득 또는 허용 불가능한 과제 성능 저하로 이어진다. 이러한 식별은 민감도 지표, 즉 모든 후보 정책의 과제 정확도를 평가하지 않고 층별 열화를 추정하는 대리 지표에 의존한다. 그럼에도 널리 쓰이는 지표는 최신 아키텍처에서 체계적으로 실패한다. 우리는 서로 뚜렷이 다른 네 개의 신경망에 걸친 층별 INT8 양자화에 대한 13개 민감도 지표의 체계적 실증 연구를 제시하고, 그로부터 얻은 정책을 두 ARM64 플랫폼에서 검증한다. 그래디언트 기반 민감도 방법은 8개 모델-하드웨어 구성 중 4개에서 실패하고, 가중치 기반 통계는 2개에서 실패한다. 반면 Jensen-Shannon Divergence는 치명적 실패가 전혀 없으며, 안전하게 양자화할 수 없는 층을 안정적으로 분리한다. 민감도 지표만으로는 정책이 정의되지 않으며, 그 단계에 흔히 쓰이는 고정 임계값은 최신 아키텍처의 고도로 치우친 분포에서 취약하다. 우리는 K-Means 클러스터링으로 이를 해결하여 거의 무손실 정확도와 전체 정밀도 모델 대비 평균 $1.81\times$ 속도 향상을 달성한다. 마지막으로, 민감도와 관계없이 속도 향상이 미미한 층을 양자화에서 제외하는 것이 역효과를 낼 수 있음을 밝힌다. 이는 계산 그래프 단편화를 유발하고 연산자 융합(operator fusion)을 비활성화하기 때문이다. 우리 결과는 GPU 접근이나 그래디언트 계산 없이 이질적 엣지 CPU에 양자화된 비전 모델을 배포하는 실무자와 연구자에게 구체적인 할당 정책을 제공한다.
텍스트 조건 변환을 통한 임베딩 공간 제어
Controlling Embedding Spaces with Text-Conditioned Transformations
CLIP과 같은 모델의 멀티모달 임베딩 공간은 의미적 유사도 검색 및 교차 모달 제로샷 분류와 같은 강력한 기능을 가능하게 한다. 이러한 임베딩은 고수준 의미를 단일 벡터로 압축하는데, 이는 주요 객체와 같은 지배적 의미를 주로 표현하면서 카메라 각도나 색조와 같은 다른 중요한 속성을 억제하는 대가를 치른다. 우리는 이러한 속성을 명시적으로 접근 가능하게 만드는 시각적 임베딩의 텍스트 조건 변환(text-conditioned transformation)을 제안한다. 속성 카테고리에 대한 자연어 설명(예: "색상" 또는 "예술 스타일")이 주어지면, 네트워크는 지정된 속성을 강조하는 아핀 변환(affine transformation)을 생성한다. 텍스트 조건화를 통해 많은 속성을 동시에 학습할 수 있으며, 추론 시 직관적인 인터페이스를 통해 이에 접근할 수 있다. 네트워크는 변환된 임베딩을 고정된 잠재 공간(latent space)과 정렬하도록 학습되어, 재인코딩 없이 기존 대규모 임베딩을 사용한 검색을 가능하게 한다. 전체 집합에 적용할 때, 동일한 메커니즘은 다중 클러스터링(multi-clustering)과 같은 속성 분리(attribute disentanglement) 작업을 위해 잠재 공간을 변환한다. 잠재 공간에서 직접 동작함으로써, 본 방법은 임베딩 공간을 제어하기 위한 통합적이고 효율적인 프레임워크를 제공하며, 거의 제로에 가까운 추론 비용으로 속성 기반 검색 및 다중 속성 조직화 작업 모두에서 최신(state-of-the-art) 성능을 보여준다. 프로젝트 페이지: https://joefioresi718.github.io/ControlEmbed_webpage/
명목형 및 순서형 속성을 포함한 범주형 데이터 클러스터링을 위한 속성 내 거리의 학습 가능한 가중치 부여
Learnable Weighting of Intra-Attribute Distances for Categorical Data Clustering with Nominal and Ordinal Attributes
범주형 데이터 클러스터링의 성공은 일반적으로 두 객체 간의 비유사도를 측정하는 거리 메트릭에 크게 의존한다. 그러나 기존의 클러스터링 방법 대부분은 비유사도를 계산할 때 순서형 값의 상대적 순서 정보를 고려하지 않은 채, 두 가지 범주형 하위 유형인 명목형(nominal) 속성과 순서형(ordinal) 속성을 동일한 방식으로 처리한다. 또한 명목형 속성과 순서형 속성 사이에는 비유사도를 나타내는 데 있어 탐구할 가치가 있는 상호 의존성이 존재할 수 있다. 이에 본 논문은 그래프와 유사한 관점에서 명목형 및 순서형 속성 값의 본질적인 차이와 연결성을 연구한다. 이를 바탕으로, 순서형 값 간의 순서 관계를 보존하면서 명목형 및 순서형 속성의 속성 내 거리를 통합된 방식으로 측정하는 새로운 거리 메트릭을 제안한다. 나아가, 속성 내 거리 가중치 학습과 데이터 객체의 분할을 두 개의 별도 단계가 아닌 단일 학습 패러다임으로 통합함으로써 준최적 해(suboptimal solution)를 회피하는 새로운 클러스터링 알고리즘을 제안한다. 실험 결과는 기존의 유사 방법들과의 비교에서 제안된 알고리즘의 효과를 입증한다.
구조적 고립 극복: 커뮤니티 인식 샘플링과 구조적 엔트로피를 통한 확장 가능한 그래프 클러스터링
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)와 강건성 분석을 통해 실세계 대규모 그래프에서의 효과성과 신뢰성을 추가로 검증한다.
Simultaneous Linear Multi-view Attributed Graph Representation Learning and Clustering
Efficient graph convolution for joint node representation learning and clustering
토론
이 논문과 연결된 포럼 글이 아직 없습니다.