Belief propagation and affinity measure techniques are described. In one or more implementations, beliefs may be formed to solve a labeling problem for a node, such as to perform image processing. An affinity measure may be calculated that describes how similar the node is to another node. This affinity measure may then be used as a basis to determine whether the share the belief formed for the node with the other node to solve a labeling problem for the other node.