Centroid-based clustering for graph datasets

Due to the absence of nodes and edges correspondence between graphs, the existing central clustering algorithms usually perform graph clustering in some embedded spaces, or confine the cluster centers to the set median graphs. In this paper, a centroid-based algorithm is proposed for directly clustering on the graphs, based on a newly defined dissimilarity measure via structure matching. The resulting node correspondences are used to rearrange the graph structures, such that the cluster centroids, i.e., the generalized median graphs, can be defined directly on the graphs and subsequently be optimized in a k-means type process. The experimental results on four real-world graph datasets demonstrate that the new algorithm significantly improves the clustering accuracy, and is able to discover the meaningful generalized median graphs.