I have a classification problem, with the following structure. There is a fully-connected graph, and each node needs be assigned a class label. Every pair of nodes in the graph has a probability distribution over class labels. So in this distribution, the value for each class represents the probability that the two nodes themselves are both assigned to that class. Every node must then be assigned to the same class.

My knowledge of graphical models is pretty limited. I have some knowledge of Markov Random fields, and it seems similar. The differences are that (i) everything is fully-connected, (ii) the unary terms for each node is represented by multiple distributions, one for each of its adjacent nodes, and (iii) the cost of adjacent nodes being assigned to different classes (pairwise terms) is infinite.

Is this a standard problem? Can it be solved?



1 Answer 1


If you have a small number of states, you could evaluate the likelihood for each of them and choose the configuration with the highest likelihood.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.