Patent ID: 8538916

Claim:
A method executed by a data processing apparatus, comprising: receiving a first information instance, the first information instance being a first semantic object belonging to one or more first information classes, wherein the first semantic object is a word or a phrase; identifying second information instances related to the first information instance, each second information instance being a second semantic object belonging to one or more second information classes, wherein each second semantic object is a word or a phrase, and wherein each information class represents a particular semantic concept; identifying, in a graph stored in a memory and representing information instances and attributes describing the information instances, first attributes describing the first information instance and second attributes describing the second information instances, wherein the graph includes attribute nodes each representing a respective attribute, instance nodes each representing a respective information instance, and edges each connecting an attribute node and an instance node, each edge representing that a non zero likelihood exists that the attribute of the connected attribute is related to the information instance of the connected instance node, and wherein the graph further includes paths connecting pairs of instance nodes, wherein the existence of a path indicates that a semantic relationship exists between the information instances of the connected instance nodes; performing random walks in the graph from the first information instance to the second attributes through the second information instances and from the first information instance to the first attributes; calculating relatedness values that measure transition probabilities of the random walks from the first information instance to the first attributes, and from the first information instance to the second attributes, including calculating a first relatedness value that measures a first transition probability of a first random walk from the first information instance to a first attribute of the second attributes; and selecting at least a portion of the first and second attributes based on the relatedness values and storing data associating the selected attributes with the first information instance on a storage device, including: determining that the first relatedness value for the first random walk from the first information instance to a first attribute of the second attributes satisfies a threshold relatedness value; and associating the first attribute of the second attributes with the first information instance as an instance attribute of the first information instance by creating an edge between the first attribute of the second attributes and the first information instance in the graph.