Block spectral clustering for multiple graphs with inter-relation

Chuan Chen, Michael Kwok Po Ng*, Shuqin Zhang

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

5 Citations (Scopus)


Clustering methods for multiple graphs explore and exploit multiple graphs simultaneously to obtain a more accurate and robust partition of the data than that using single graph clustering methods. In this paper, we study the clustering of multiple graphs with inter-relation among vertices in different graphs. The main contribution is to propose and develop a block spectral clustering method for multiple graphs with inter-relation. Our idea is to construct a block Laplacian matrix for multiple graphs and make use of its eigenvectors to perform clustering very efficiently. Global optimal solutions are obtained in the proposed method and they are solutions of relaxation of multiple graphs ratio cut and normalized cut problems. In contrast, existing clustering methods cannot guarantee optimal solutions and their solutions are dependent on initial guesses. Experimental results on both synthetic and real-world data sets are given to demonstrate that the clustering accuracy achieved and computational time required by the proposed block clustering method are better than those by the testing clustering methods in the literature.

Original languageEnglish
Article number8
JournalNetwork Modeling and Analysis in Health Informatics and Bioinformatics
Issue number1
Early online date26 Apr 2017
Publication statusPublished - Dec 2017

Scopus Subject Areas

  • Urology

User-Defined Keywords

  • Block Laplacian matrix
  • Eigenvectors
  • Multiple graphs clustering
  • Optimal solutions


Dive into the research topics of 'Block spectral clustering for multiple graphs with inter-relation'. Together they form a unique fingerprint.

Cite this