This paper introduces a new method for solving clustering ensembles, that is, combining multiple clusterings over a common dataset into a final better one. The ensemble is reduced to a graph that simultaneously models as vertices the original clusters in the ensemble and the joint clusters derived from them. Only edges linking vertices from different types are considered. The resulting graph can be partitioned efficiently to produce the final clustering. Finally, the proposed method is evaluated against two graph formulations commonly used.