Block spectral clustering methods for multiple graphs

Chuan Chen*, Michael Kwok Po Ng, Shuqin Zhang

*Corresponding author for this work

Research output: Contribution to journalJournal articlepeer-review

21 Citations (Scopus)


In data science, data are often represented by using an undirected graph where vertices represent objects and edges describe a relationship between two objects. In many applications, there can be many relations arising from different sources and/or different types of models. Clustering of multiple undirected graphs over the same set of vertices can be studied. Existing clustering methods of multiple graphs involve costly optimization and/or tensor computation. In this paper, we study block spectral clustering methods for these multiple graphs. The main contribution of this paper is to propose and construct block Laplacian matrices for clustering of multiple graphs. We present a novel variant of the Laplacian matrix called the block intra-normalized Laplacian and prove the conditions required for zero eigenvalues in this variant. We also show that eigenvectors of the constructed block Laplacian matrix can be shown to be solutions of the relaxation of multiple graphs cut problems, and the lower and upper bounds of the optimal solutions of multiple graphs cut problems can also be established. Experimental results are given to demonstrate that the clustering accuracy and the computational time of the proposed method are better than those of tested clustering methods for multiple graphs.

Original languageEnglish
Article numbere2075
JournalNumerical Linear Algebra with Applications
Issue number1
Early online date13 Nov 2016
Publication statusPublished - Jan 2017

Scopus Subject Areas

  • Algebra and Number Theory
  • Applied Mathematics

User-Defined Keywords

  • clustering of multiple graphs
  • eigenvalues
  • eigenvectors
  • multiple graphs cut
  • spectral clustering


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

Cite this