Multicuts and Perturb & MAP for Probabilistic Graph Clustering