  We study the problem of recovering the latent ground truth labeling of a
structured instance with categorical random variables in the presence of noisy
observations. We present a new approximate algorithm for graphs with
categorical variables that achieves low Hamming error in the presence of noisy
vertex and edge observations. Our main result shows a logarithmic dependency of
the Hamming error to the number of categories of the random variables. Our
approach draws connections to correlation clustering with a fixed number of
clusters. Our results generalize the works of Globerson et al. (2015) and
Foster et al. (2018), who study the hardness of structured prediction under
binary labels, to the case of categorical labels.
