Graph clustering based on structural/attribute similarities

TLDR

Graph clustering partitions vertices into groups based on connectivity or similarity, detecting densely connected subgraphs, but most existing methods focus only on topology and ignore heterogeneous vertex attributes. This work introduces SA‑Cluster, a graph clustering algorithm that jointly exploits structural and attribute similarities through a unified distance metric. SA‑Cluster partitions a graph with attributes into k clusters, each forming a dense subgraph with homogeneous attribute values, and learns the relative contributions of structural and attribute similarity automatically. Theoretical analysis proves convergence, and experiments show SA‑Cluster outperforms state‑of‑the‑art clustering and summarization methods.

Abstract

The goal of graph clustering is to partition vertices in a large graph into different clusters based on various criteria such as vertex connectivity or neighborhood similarity. Graph clustering techniques are very useful for detecting densely connected groups in a large graph. Many existing graph clustering methods mainly focus on the topological structure for clustering, but largely ignore the vertex properties which are often heterogenous. In this paper, we propose a novel graph clustering algorithm, SA-Cluster , based on both structural and attribute similarities through a unified distance measure. Our method partitions a large graph associated with attributes into k clusters so that each cluster contains a densely connected subgraph with homogeneous attribute values. An effective method is proposed to automatically learn the degree of contributions of structural similarity and attribute similarity. Theoretical analysis is provided to show that SA-Cluster is converging. Extensive experimental results demonstrate the effectiveness of SA-Cluster through comparison with the state-of-the-art graph clustering and summarization methods.