1. A method performed by one or more computers, the method comprising: maintaining data representing a junction tree of a relationship graph, wherein the relationship graph includes nodes, directed edges, and undirected edges, wherein each node in the relationship graph represents a respective object category of a plurality of object categories; wherein each directed edge in the relationship graph connects a respective pair of nodes that represent object categories that have a subsumption relationship, wherein each undirected edge in the relationship graph connects a respective pair of nodes that represent object categories that have an exclusion relationship, and wherein the junction tree comprises a plurality of cliques that each include a respective subset of connected nodes from the relationship graph; maintaining data specifying a respective state space for each of the cliques of the junction tree, wherein the state space for each of the cliques includes assignments that each define a respective combination of object categories that can be assigned to an object without violating any of the exclusion or subsumption relationships defined by the relationship graph between the connected nodes in the clique, receiving input image data for an input image; processing the input image data using a deep neural network, wherein the deep neural network is configured to process the input image data to generate a respective raw image score for each of the object categories, wherein the raw image score for each of the object categories represents an initial estimate of a likelihood that the input image depicts an object that belongs to the object category; generating a respective final score for each of the object categories from the raw image scores by performing message passing on the junction tree using the raw image scores, wherein the final score for each of the object categories represents an updated estimate of the likelihood that the input image depicts an object that belongs to the object category, whereby the message passing modifies the raw image scores according to the respective state spaces for the cliques of the junction tree; and determining a classification for the input image based on the final scores for the object categories.