Spectral clustering and its use in bioinformatics

https://doi.org/10.1016/j.cam.2006.04.026Get rights and content
Under an Elsevier user license
open archive

Abstract

We formulate a discrete optimization problem that leads to a simple and informative derivation of a widely used class of spectral clustering algorithms. Regarding the algorithms as attempting to bi-partition a weighted graph with N vertices, our derivation indicates that they are inherently tuned to tolerate all partitions into two non-empty sets, independently of the cardinality of the two sets. This approach also helps to explain the difference in behaviour observed between methods based on the unnormalized and normalized graph Laplacian. We also give a direct explanation of why Laplacian eigenvectors beyond the Fiedler vector may contain fine-detail information of relevance to clustering. We show numerical results on synthetic data to support the analysis. Further, we provide examples where normalized and unnormalized spectral clustering is applied to microarray data—here the graph summarizes similarity of gene activity across different tissue samples, and accurate clustering of samples is a key task in bioinformatics.

MSC

65F15
92C37

Keywords

Balancing threshold
Gene expression
Rayleigh–Ritz Theorem
Fiedler vector
Graph Laplacian
Random graph
Maximum likelihood
Microarray
Partitioning
Scaling

Cited by (0)

1

Supported by Engineering and Physical Sciences Research Council Grant GR/T19100 and by Research Fellowships from The Leverhulme Trust and The Royal Society of Edinburgh/Scottish Executive Education and Lifelong Learning Department.

2

Supported by Engineering and Physical Sciences Research Council Grant GR/T19100.

3

Supported by the Academy of Finland, under Grant number 53441.