Abstract: The problem of clustering in multi-relation data mining was investigated, and an efficient multi-relational clustering algorithm called EMC was proposed. EMC aims at increasing the accuracy of clustering, and decreasing running time. First, EMC computed the similarity between two objects by taking advantage of tuple ID propagation approach. Then, EMC clustered the objects by K-medoids clustering algorithm. Performance results demonstrate that, EMC significantly decreases running time, and increases the accuracy of clustering.