Traditional image clustering methods mainly depends on visual features only. Due to the well-known “semantic gap”, visual features can hardly describe the semantics of the images independently. In the case of Web images, apart from visual features, there are rich metadata which could enhance the performance of image clustering, such as time information, GPS coordinate and initial annotations. This paper proposes an efficient Flickr photo clustering algorithm by simultaneous integration information of multiple types which are related to Flickr photos using k-partite graph partitioning. For a personal collection of Flickr, we firstly determine the value of k which means the number of data types we used. Secondly, these heterogeneous metadata are mapped to vertices of a k-partite graph, and relationship between the heterogeneous metadata is represented as edge weight. Finally, Flickr photos could be clustered by partitioning the k-partite graph. Experiments conducted on the photos in Flickr demonstrate the effectiveness of the proposed algorithm.