Consensus similarity graph construction for clustering


Pattern Analysis and Applications, vol.26, no.2, pp.703-733, 2023 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 26 Issue: 2
  • Publication Date: 2023
  • Doi Number: 10.1007/s10044-022-01116-w
  • Journal Name: Pattern Analysis and Applications
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, PASCAL, Applied Science & Technology Source, Computer & Applied Sciences, Index Islamicus, zbMATH
  • Page Numbers: pp.703-733
  • Keywords: Similarity graph, Clustering, Ensemble approaches, Bagging
  • Bursa Uludag University Affiliated: Yes


© 2022, The Author(s), under exclusive licence to Springer-Verlag London Ltd., part of Springer Nature.A similarity graph represents the local characteristics of a data set, and it is used as input to various clustering methods including spectral, graph-based, and hierarchical clustering. Several similarity graphs exist in the literature; however, there is not a single similarity graph that can handle all kinds of cluster shapes and structures. In this study, motivated by the successful applications of ensemble approaches to clustering, a generic method for consensus similarity graph construction is proposed. The proposed approach first constructs multiple similarity graphs using bootstrap aggregating (bagging). Then, these graphs are fused into a consensus similarity graph using the normalized co-association matrix. We use k-nearest neighbor, ε-neighborhood, fully connected graph, and proximity graphs as the base similarity graphs. Moreover, the proposed approach is coupled with various clustering algorithms including spectral, graph-based, and hierarchical clustering. The experimental results with various spatial and real data sets demonstrate the effectiveness of the consensus similarity graphs in clustering. The proposed approach is also robust to local noise.