Soft Clustering on Graphs

We propose a simple clustering framework on graphs encoding pairwise data similarities. Unlike usual similarity-based methods, the approach softly assigns data to clusters in a probabilistic way. More importantly, a hierarchical clustering is naturally derived in this framework to gradually merge lower-level clusters into higher-level ones. A random walk analysis indicates that the algorithm exposes clustering structures in various resolutions, i. e. , a higher level statistically models a longer-term diffusion on graphs and thus discovers a more global clustering structure. Finally we provide very encouraging experimental results.

Authors

• Kai Yu Shanghai Jiao Tong University
• Shipeng Yu
• Volker Tresp Ludwig Maximilian University of Munich, Munich, Germany Munich Center for Machine Learning, Munich, Germany

Keywords

No keywords are indexed for this paper.