Scalable graph propagation for knowledge expansion

Systems and methods for adding labels to a graph are disclosed. One system includes a plurality of computing devices including processors and memory storing an input graph generated based on a source data set, where an edge represents a similarity measure between two nodes in the input graph, the input graph being distributed across the plurality of computing devices, and some of the nodes are seed nodes associated with one or more training labels from a set of labels, each training label having an associated original weight. The memory may also store instructions that, when executed by the processors, cause the plurality of distributed computing devices to propagate the training labels through the input graph using a sparsity approximation for label propagation, resulting in learned weights for respective node and label pairs, and automatically update the source data set using node and label pairs selected based on the learned weights.

BACKGROUND

Data sets reflect knowledge about entities. Some data sets are graph-based and may model knowledge, social, communication, and information networks. A graph G(V, E) consists of a set of nodes V, and a set of edges E where each edge connects two nodes in the graph. Each edge represents a particular piece of knowledge about the nodes it connects, for example membership in a group, a particular type of relationship, existence of an attribute, a similarity between nodes, etc. Other data sets can be normalized databases or object-oriented data stores that store attributes or properties for an entity. As a particular data set grows, reflecting additional knowledge, the data set may become too large to fit on one machine. But even very large data sets are often incomplete. For example, a graph-based data set may include nodes with no edges or only a few edges. However, it can be a challenge to identify and add the additional knowledge to a large data set due to the size of the data set, which causes conventional knowledge propagation methods to run out of memory or run too long.

SUMMARY

Implementations provide scalable systems and methods for expanding knowledge in a large graph-based data store. The methods may use an input graph of nodes connected by edges, where the weight of an edge represents a similarity measure between the nodes. The input graph includes seed nodes that have labels. The labels can represent relationships or attributes captured in a source data set. As one example, the nodes in the input graph can represent entities and the labels can represent properties or attributes of the entity. As another example, the nodes in the input graph can represent two nodes from a source graph and the label can represent a relationship between the two nodes. The similarity measure, represented by a weight of an edge in the input graph, may be based on information in the source data set. The system propagates the labels of the seed nodes through the graph, generating likely labels for an unlabeled node based on similarity with and distance from seed nodes. After propagating the labels, the system can automatically update the source data set using the likely labels. The method uses a novel semi-supervised learning method to learn the likely labels. The semi-supervised learning method includes a streaming sparsity approximation to reduce the time and complexity of the propagation, making implementations scalable to very large graphs. In some implementations, the system may augment the input graph prior to propagating the existing labels, which increases the quality and quantity of the learned labels. In some implementations, the system may factor in weights for learned labels that account information from more reliable neighbors more heavily.

According to certain aspects of the disclosure, a method includes initializing, for nodes in a distributed graph comprising labeled nodes and unlabeled nodes, wherein an edge between two nodes in the distributed graph represents a similarity measure between the two nodes, learned label weights for at least a non-zero quantity k of labels per node. The method also includes, for a first node in the distributed graph, sending the learned label weights for the node to each neighbor in the distributed graph, receiving a set of at least k learned label weights from each neighbor, determining top-ranked labels for the first node based on a probability-based sparsity approximation using the received sets of learned label weights, and calculating learned label weights for top-ranked labels of the first node based on an aggregation of the received sets of learned label weights from the neighbors. The method also includes repeating the sending, receiving, determining, and calculating for a quantity of iterations, determining, from the learned label weights for the first node, a first label with a weight that meets or exceeds a threshold, and automatically updating a source data set with the first label, responsive to the determining.

According to an aspect of the disclosure, a system includes a plurality of computing devices including processors formed in a substrate and memory storing: an input graph of nodes connected by edges, an edge representing a similarity measure between two nodes, the graph being distributed across the plurality of computing devices, wherein at least some of the nodes are seed nodes associated with one or more training labels from a set of labels, each training label having an associated original weight, the input graph being generated based on a source data set. The memory may also store instructions that, when executed by the processors, cause the plurality of distributed computing devices to perform operations. The operations may include propagating the training labels through the input graph using a sparsity approximation for label propagation, resulting in learned weights for respective node and label pairs, and automatically updating the source data set using node and label pairs selected based on the learned weights.

According to one aspect of the disclosure, a method includes initializing, for nodes in an input graph comprising labeled nodes and unlabeled nodes, learned label weights for a non-zero quantity q of labels per node, wherein an edge between two nodes in the input graph represents a similarity measure between the two nodes and adding additional edges between nodes in the input graph based on deep learning of a large corpus of text. The method may also include, for a first node in the input graph, sending the learned label weights for the first node to each neighbor in the input graph, receiving a set of q learned labels and respective learned label weights from each neighbor, updating the learned weights of labels for the first node based on an aggregation of the received learned label weights from the neighbors, and repeating the sending, receiving, and updating for a quantity of iterations. The method may further include determining, from the updated learned label weights for the first node, a first label with a learned label weight that meets or exceeds a threshold, and automatically updating a source data set with the first label, responsive to the determining.

Another aspect of the disclosure can be embodied on a computer-readable medium having recorded and embodied thereon instructions that, when executed by a processor of a computer system, cause the computer system to perform any of the methods disclosed herein.

One or more of the implementations of the subject matter described herein can be implemented so as to realize one or more of the following advantages. As one example, implementations easily add additional knowledge into a source dataset using a semi-supervised learning model. Some implementations may use a streaming sparsity approximation of the label distribution, which allows the system to efficiently propagate the labels even with the graph is large (e.g. millions of nodes and edges) or when the set of labels is large (e.g., thousands or even millions). In some implementations, the processing is parallelized so that the graph and processing is distributed across multiple computing devices. Implementations increase the quality of label propagation by augmenting the input graph with additional edges when the nodes in the input graph represent textual information. Augmentation includes learning latent semantic embeddings associated with the nodes using raw text and deep learning techniques.

DETAILED DESCRIPTION

FIG. 1is a block diagram of a distributed graph system100in accordance with an example implementation. The system100may be used to learn additional labels for an input graph, effectively adding knowledge to a source graph using the techniques described herein. The graph system100may include root120and graph cluster160. Root120and graph cluster160may be computing devices that take the form of a number of different devices, for example a standard server, a group of such servers, or a rack server system. In some implementations, the root120and the graph cluster160may be distributed systems implemented in a series of computing devices, such as a group of servers. In some implementations, the servers may be organized into a tree structure, with at least a root server120and leaf servers150A to150n. In some implementations (not shown), the tree may include intermediate servers, so that there are one or more layers between the root120and the leaf servers150A to150n. The root120and graph cluster160may be examples of computer device1000, as depicted inFIG. 10.

The graph system100illustrated inFIG. 1can operate over a large graph with, for example, billions of nodes. The root120may include one or more hardware processors142for one or more computing devices, such as servers, that operate with the graph cluster160to perform operations on the input data graph represented by nodes and edges154. The root120may include one or more servers that receive commands or requests from a requester, such as client170. The root120may initiate and monitor calculations performed on the graph and may manage the results of the calculations. In some implementations, the root120may receive and disseminate messages between nodes assigned to disparate leaves150in the graph cluster160.

System100may also include a graph cluster160. Graph cluster160may be a collection of distributed computing devices each with its own hardware processor and memory. The number of computing devices that comprise graph cluster160can vary. The graph cluster160may be divided into one or more leaf servers, such as leaf150A, leaf150B, leaf150n, with n representing any positive integer. A leaf server may be associated with a logical division of nodes in the graph, with each graph node being assigned to a leaf server. Thus, a leaf server may correspond to one computing device, or a leaf server may be a logical computing device and may share a physical computing device with other leaves. In some implementations, a node's assigned leaf may change as the graph is updated, making leaf assignments flexible. The root120may determine which nodes are assigned to each leaf as the nodes are added to the graph or updated. The root120may also store label similarities144, such as a matrix or paired list, that records and stores the similarity of one label to another label. The similarity of the labels may be based on any conventional similarity measure, such as cosine or other similar distance measures, etc. In some implementations, the root120may calculate label similarities144via random walks from seed nodes in the input graph, as explained herein.

The root120may route processing requests or messages to the leaf servers and act as the primary means of coordination between the leaves at processing time. Of course, leaves may send messages directly to each other, and nodes in the graph may send messages to each other as part of graph processing. In addition to the leaf servers, the graph cluster160may include one or more layers or intermediate servers between the root120and the leaf servers, but are not shown inFIG. 1for the sake of brevity. Thus, for example, an intermediate server may be associated with, for example, 20 leaf servers. The intermediate server may be connected directly to the root, or there may be one or more additional layers between the intermediate server and the root120. Thus, althoughFIG. 1shows communications directly between the root and leaf servers, it is to be understood that intermediate devices may be used to direct communications and aggregate results using known methods, such as remote procedure calls. The root, intermediate, and leaf servers that make up the tree may, collectively, be referred to as the input graph.

Each of the leaf servers that make up graph cluster160can include node nodes and edges154and learned label structures156. The nodes and edges154represent a partition of the input graph. Each node in the nodes and edges154may be assigned to a partition, e.g., a leaf. The nodes in the nodes and edges154may be labeled or unlabeled. A labeled node has one or more labels that are used as training labels. The labels of a labeled node each have an original weight that is a positive number. In some implementations, the original weights may be normalized so that the total of the original weights for a node sum to one. A labeled node is also referred to as a seed node. If a node in the nodes and edges154does not have a particular label l, the weight of label l for the node is zero. Thus, for unlabeled nodes, all original weights are zero for the node, while only labels not associated with a seed node have an original weight of zero for the seed node.

Learned label structures156may be used in propagating the training labels to other nodes in the graph. Each node in the input graph may have a respective learned label structure156. In some implementations, the learned label structure156may have a learned label weight for each label in the set of possible labels. In some implementations, the learned label structure156may track label weights for a non-zero quantity k of labels, for example k=5 or k=10, using a sparsity approximation. The tracked k labels in a learned label structure156for a node represents the top-ranked, or most likely, labels for the node. In such an implementation, the system may store, as part of the learned label structure156, an average probability mass of the remaining labels for the node. In other words, rather than storing an exact learned label weight for each label, the system may store an approximation of the learned label weight for labels that are not top-ranked. The average probability mass may be based on the sum of the weights for the top-ranked labels. For example, the average probability mass for a node v may be represented as 1.0−Σi=1kŶvli/m−k where k is the quantity of top-ranked labels tracked by the learned label structure, m is the quantity of labels in the set of labels for the input graph, and Σi=1kŶvliis the sum of the learned label weights of the top-ranked labels for node v. As a round of aggregation completes, the system100may update the top-ranked labels for each node v, the learned label weights of the top-ranked labels for node v, and average probability mass for node v, so that the learned label structure reflects the top k labels for the node for any particular round of aggregation.

The learned label structures156may be initialized using the original weights of the training labels. For example, a learned label structure156for a seed node would include data for the labels associated with the seed node in the input graph, e.g., the training labels of the seed node. The learned label weight in the learned label structure156may be the original weight of the label-node pair in the input graph. Any remaining weights may be set to the uniform distribution for the labels, e.g., l/m where m is the quantity of labels in the set of labels. In some implementations, the system may initialize the average probability mass for seed nodes using the training labels as the top k labels. The remaining labels each have an equal learned label weight (e.g., l/m), and the system may randomly select labels with this weight to fill the learned label structure with k labels, and then calculate the average probability mass. For an unlabeled node, the system may select k labels for the learned label structure for the node and set the average probability mass is l/m.

To propagate the training labels the system100may utilize a Jacobi iterative algorithm, which defines the approximate solution at the (i+1)thiteration given the solution at the ithiteration. The initialized learned label structures156represent iteration zero (0), or i=0. The first iteration of the Jacobi iterative algorithm is thus provided with the initialized structures. The iterative algorithm aggregates the learned label weights of its neighbors based on how similar the neighbor is. The aggregation for label l of node v at iteration i may be represented by the following:

In the aggregation above, the first component is a seed component. In the seed component μ1is a component weight, svvis one (1) when the node v is a labeled node (e.g., has at least one label in the input graph) and zero otherwise, and Yvlis the original weight of the label in the input graph. The weight of the label l in the input graph is zero when the node v is not associated with label l before propagation begins. If label l has a non-zero weight in the input graph it is considered training data and propagated through the graph via the aggregation. In some implementations, the weight parameter μ1may be set to 1. This ensures that a training label for a seed node retains its original weight.

The second component in the aggregation is a total neighbor component. In the total neighbor component μ2is a component weight, wvuis a similarity measure between the node v and the neighbor u (e.g., it is the weight of the edge connecting nodes v and u in the input graph), cll′is a similarity measure between label l and label l′, Ŷul′(i−1)is the weight of label l′ in the learned label structure for node u at the previous or i−1 iteration. In other words, a node v receives the learned label structure from its neighbors and the received learned label structures represent values from a previous iteration, which are used to calculate the learned label weights of a current iteration at node v.

The label similarity measure cll′may be any conventional similarity measure, including cosine, Jaccard, etc. The label similarity measure may be stored, for example, as label similarities144. Label similarities may be stored as an m×m matrix, as a paired list, or in some other manner. Label similarities144may be accessible by each node, e.g., stored at the root120or at each leaf150. In some implementations, the similarity measure between two labels may be provided. In some implementations the system100may obtain the similarity between two labels by taking a random walk starting from each seed node. For each random walk starting from seed node v, the terminate probability is Ptand the probability of choosing a node u is Pc(u), which can be represented by 1/(1+exp(∝duv)) where duvis the distance from the node u to the seed node v. The system may record all the numerical counts of the labels of the seeds along the path of the random walk, normalize the count, and compute the cosine similarity between each pair of labels based on the normalized matrix.

In some implementations, the total neighbor component may include a label distribution entropy parameter. The entropy parameter may enable the aggregation to devalue the contribution of an uncertain neighbor. A neighbor node may be uncertain because it did not receive much useful information in the previous iteration. The system100may calculate the entropy parameter eufor each neighbor u according to the following: eu(i−1)=1.0−H(Ŷu(i−1)) where H represents the skewness of the distribution. The system may normalize the entropy parameter to [0,1]. When the label distribution entropy parameter eu(i−1)for a node u is low, this indicates the node u is either far away from seed nodes or the node u itself is ambiguous (e.g., not very similar to any neighbors). Such a node may be considered untrustworthy and the system decreases its contribution to the total neighbor component. In an implementation that accounts for label distribution entropy, the total neighbor component may be expressed as μ2ΣuεN(v)eu(i−1)wvuΣl′cll′Ŷul′(i−1).

The last component of the aggregation is a uniform distribution component. In the uniform distribution component, μ3is a component weight and Ulis a uniform distribution of label l (e.g., l/m where m is the number of labels. To ensure that the weight does not exceed 1, the aggregation may divide the sum of the three components by a normalization constant, Mvl, for node v and edge l. The normalization constant may be expressed as μ1svv+μ2ΣuεN(v)wvuΣl′cll′+μ3. In implementations that account for label distribution entropy, the entropy parameter may be included in the normalization constant, which can be expressed as follows:
μ1svv+μ2ΣuεN(v)eu(i−1)wvuΣl′cll′+μ3.

The component weights μ1, μ2and μ3can be set to weight the various components. For example, μ1may have a value of one (1) so that the original weight of a training label remains unchanged and highly weighted. The other parameters μ2and μ3can have small values, e.g., 0.01 or some other value much smaller than the value of μ1, so that to place a higher emphasis on the seed information. In some implementations, the component weights can be left out of the aggregation.

Graph system100may be in communication with clients170over network180. Network180may be for example, the Internet or the network180can be a wired or wireless local area network (LAN), wide area network (WAN), etc., implemented using, for example, gateway devices, bridges, switches, and/or so forth. Via the network180, the system100may communicate with and transmit data to/from clients170or other computing devices. The system100represents one example configuration, and implementations may incorporate other configurations.

Although not illustrated inFIG. 1, it is understood that the input graph, represented by the nodes and edges154on the leaves of the graph cluster160, may be generated based on a source data set. The source data set may take on various forms. For example, one type of source data set is a public knowledge base, such as FREEBASE. A knowledge base may represent an entity, such as a person, place, item, idea, topic, abstract concept, concrete element, other suitable thing, or any combination of these, as a node in a graph. Entities in the knowledge base may be related to each other by edges, which represent relationships between entities. For example, in the knowledge base the nodes “Maryland” and “United States” may be linked by the edges of in country and/or has state. The system100, or another system, may generate the input graph based on the nodes and/or edges in the knowledge base. As an example, a node in the input graph may represent a node or a node pair in the knowledge base. A label of a node pair may represent a relationship (e.g., labeled edge) from the knowledge base between the pair of nodes. For example, the knowledge base may have a node for “Paris” and a node for “France,” and a labeled edge between the Paris node and the France node that represents a capital of relationship. Thus, the label capital of may be assigned to the <Paris, France> node in the input graph. Labels may also represent attributes of a node. For example, the node “Paris” may have an entity type of “City”, which may be considered an attribute of the “Paris” node. Thus, “City” may be a label in the input graph for the node that represents the “Paris” entity. After the system100determines learned label weights for the nodes in the input graph, the learned label weights may be used to augment the knowledge base. For example, the system100may learn that the previously unlabeled “London” node has a high likelihood (e.g. a high learned label weight) of having a capital of relationship with and “England” node and reflect this in the knowledge base. As one example, overlap of entities contained in the capital of relationship could be used to compute the edge similarity.

Other data sets may be used to generate the input graph. For example, a classification data set may be used as the source for the input graph. A classification data set may classify entities into categories. For example, one classification data set may include grammars (e.g. rules to identify certain types of strings) associated with certain tasks. Such a data set may have the strings (e.g., any text input) “buy milk”, “get bread” and “toothpaste” that satisfy the grammars for a “Grocery Purchase” task. The strings may become nodes in the input graph and the category may become the label. Thus, a “buy milk” node in the input graph may have a “Grocery Purchase” label, as well as additional labels. Any strings that have not yet been assigned to a category may be unlabeled nodes in the input graph. The system100(or another system) may generate an edge in the input graph when a string shares a word or matches a pattern or a rule with another string. The weight of the edge may be based on a similarity measure between the two strings, such as cosine or Jaccard, etc. After the system100determines learned label weights for the nodes in the input graph, the learned label weights may be used to augment the source data set. For example, the system100may learn that the previously unlabeled “buy bread” node has a high likelihood (e.g. a high learned label weight) of being a “Grocery Purchase” and reflect this in the source data set. Of course the classification data set may classify other entities, such as movies, documents, etc. using other grammars.

FIG. 2illustrates a flow diagram of an example process200for propagating labels of seed nodes to unlabeled nodes in an input graph, according to an implementation. The process200shown inFIG. 2may be performed by a graph system distributed across multiple computing devices, such as graph system100ofFIG. 1. The process200is an iterative process that propagates seed labels through an input graph in a semi-supervised manner. The result of the propagation is learned label weights for the nodes of the input graph. The learned weight for a specific label-node pair represents a probability that the node can be appropriately associated with the label. Therefore, the system may use learned label weights to automatically add knowledge to a source data set. The process may begin with the system augmenting the edges in an input graph when the nodes and labels represent textual information (202). The augmentation may be based on deep learning applied to a large text corpus, as explained with regard toFIG. 3.

The system may then initialize a learned label structure Ŷvfor each node v in the input graph (205). The initialized learned label structures represent iteration 0 (or i=0). Thus, in the first iteration of propagating labels (e.g., i=1), the previous iteration is the initialized learned label structures. In some implementations, the learned label structure may track a learned label weight for each node for each label. In such an implementation, for each unlabeled node, the system may set the learned label weight of each label to l/m, where m is the quantity of labels in the label set for the input graph. For each labeled node, the system may set the learned label weight of a training label (e.g., a label associated with the node) to the original weight of the label in the input graph. For all other labels in the learned label structure for the seed, the system may set the label weight to l/m. In some implementations, the learned label structure for a node may be an array, with each entry in the array representing a learned label weight for a label. The notation Ŷvlcan be used to refer to an entry in the array, or in other words, the learned label weight of label l for node v.

In some implementations, the learned label structure Ŷvmay track only the top k labels for each node v, where k is a non-zero integer much smaller than m (the total number of labels in the set). For example, k may be five or 10 where m may be over 1000. The learned label structure for a node may thus include a label identifier and an associated learned label weight for k labels. Such an implementation uses a steaming sparsity approximation to improve scalability. In initializing the learned label structures for a seed node in a sparsity approximation implementation, the system may include all training labels for the seed node in the learned label structure, setting the learned label weight to the training label weight for the node (e.g., the original weight in the input graph). If the seed node does not have k total training labels, the system may randomly select from the remaining set of labels to fill the learned label structure with k labels, setting the label weight of the randomly selected labels to l/m. For unlabeled nodes, the system may select the first k labels or may select k random labels and set the label weight to l/m. In sparsity approximation implementations, the learned label structure may optionally include an average probability mass for the node. The system may use the average probability mass as a dynamic threshold that changes for each node for each iteration. The system may initialize the average probability mass to (1−the sum of the label weights in the top k labels for the node) divided by (m−k). For unlabeled nodes, this will always be l/m initially. For seed nodes, the average probability mass will depend on the training label weights and the number of training labels. Setting the average probability mass may be represented as

Once the learned label structures are initialized, the system may begin iterations, starting with the first iteration, or i=1 (210). As a first step in each iteration, each node may send its learned label structure to each of its neighbors (215). Of course, if the input graph is not distributed (e.g., is running on a single computing device), the system may omit this step, as each node has access to every other nodes' learned label structure. The sending of learned label structures occurs in parallel, for example using Pregel, Giraph, MapReduce, or another message-based distributed processing system. In such a system, a programmer provides the instructions or method that each node executes during each round (or iteration). Step215may thus be considered a first round in the message-based distributed system.

In implementations that use sparsity approximation, each node determines its own top-ranking labels using the received learned label structures from its neighbors (220). The top-ranking labels may be based on the frequency with which a label is seen from a node's neighbors and the learned label weights for the label, as discussed in more detail herein with regard toFIG. 4. Each node then updates its own learned label structure using the received structures of its neighbors (225). In some implementations, the node v updates the learned label weight for every label. In implementations that use sparsity approximation, the system updates the label weights of the top-ranked labels for this round, e.g., determined in step220. In doing so, the system may discards any entries in the learned label structure from the previous round that are no longer top-ranked for the node. In such an implementation, the system may also re-calculate the average probability mass for the node based on the updated label weights. This may be done the same way the average probability mass was initially calculated, but using the recently determined top-ranking labels (e.g., the ones determined in step220).

The system may determine whether to perform another iteration (230). In some implementations, the system may perform a predetermined number of iterations. In some implementations, the system may tie the number of iterations to a percentage or quantity of unlabeled nodes that have labels with a label weight meeting a threshold. Of course the system may use some other method of determining whether to perform another iteration. If another iteration is performed (230, Yes), the system increases the iteration count and the nodes send their updated learned label structure to their neighbors and use received learned label structures from neighbors (which represent a prior iteration) to update the learned label structure again. In other words, the system repeats steps215to230. When the system determines no additional iterations are to be performed (230, No), the system may use the learned label structures for each node to update the source data set (240). For example, when a learned label weight for a label-node pair meets a threshold the system may automatically associate the label with the node. In some implementations, this may include assigning a node to a category, where labels represent categories, in the source data set. In some implementations, this may include adding a relationship between two nodes, where the label represents the relationship and the node v represents a pair of nodes from a source graph. Process200then ends.

FIG. 3illustrates a flow diagram of an example process300for adding additional edges to an input graph, according to an implementation. The process300shown inFIG. 3may be performed as part of step202ofFIG. 2. The process300augments the edges of the input graph using deep learning to generate semantic embeddings using a large corpus of raw text to identify similar nodes. The additional edges may increase the quality of the learned label weights during the iterative aggregation described above with regard toFIG. 2. To begin, the system may learn semantic embeddings for each node using deep learning on a large corpus of text (305) using conventional techniques. The system uses the semantic embeddings to calculate a similarity measure between each pair of nodes in the graph. But in a large graph computing the similarity of the semantic embeddings over each pair of nodes is computationally infeasible. Accordingly, the system may use locality sensitive hashing (LSH) to approximate similarity. The system may generate a signature for each node by applying locality sensitive hashing on the semantic embedding of the node (310). The system may hash each embedding vector point into a signature in such a way that similar vectors share the same signature with a high probability. The system may use the signatures to find similar nodes (315). For example, for each signature, the system may use D bits, and for each bit d in D, generate a hyperplane in the embedding space using a random spherical coordinates rd. For node v, if the product of the embedding vector and the random spherical coordinates is greater than zero, the system may set the dthbit as 1, otherwise zero. Increasing D can reduce the amount of time to compute similarity (e.g., cosine) but leads to misstating the pair of nodes whose similarity are larger than θsim. Accordingly, the system may repeat the randomization procedure W times, maintaining W hash tables (each with D independently chosen random hyperplanes). This increases the chance that similar embedding vectors share the same signature. The system may then compute the similarity (e.g., cosine) between a pair of nodes, if they are at least one signature in common (among the W×D hash tables). When the similarity meets a threshold, the system creates an edge in the input graph between the pair of nodes. The weight of the edge will be the similarity measure. Process300then ends, having augmented the edges in the input graph.

FIG. 4illustrates a flow diagram of an example process400for determining top-ranked learned labels for a node during an iteration of the propagating, according to an implementation. The process400may be performed as part of step220ofFIG. 2. The process400is an example of a streaming sparsity approximation that enables the system to determine and track the top ranking k labels in each iteration of a label propagation method rather than tracking all m labels. Process400represents a streaming sparsity approximation at one node, labeled v in theFIG. 4. It is understood that each node in the input graph may perform process400simultaneously. In some implementations, a node may perform process400as it receives a learned label structure from a neighbor. Prior to performing process400as part of an iteration (e.g., once per iteration), the node v initializes a list of probability-estimations, making the list empty. In other words, at the beginning of each iteration, before any learned label structures from neighbors are received, the node v may have no probability-estimation entries. A probability-estimation entry includes three components. The first component is the label identifier. The second component is a frequency component representing a frequency-based weighted probability for the label and the last component is an error component, representing a maximum error of the frequency component.

Process400begins when the node v selects a first label in a received learned label structure for neighbor u (405). The received label structure includes a learned label weight for k different labels (k>1 and <<number of labels in the set of labels) and may also include an average probability mass for the neighbor u. The system may determine if the selected label l has an entry in the probability-estimation list for the node v (410). If this is the first neighbor the node v has seen label l in a neighbor's learned label structure there will no entry for the label. If there is an entry for label l in the probability-estimation list (410, Yes), the system may add the product of the similarity between node n and neighbor u and the learned label weight for the label l in the learned label structure of neighbor u to the frequency component of the entry (415). The product may also be represented by wvuŶul(i−1), where i represents the current iteration and i−1 represents the previous iteration and wvuis the weight of the edge between node v and u in the input graph. If there are other labels in the learned label structure for u that have not been selected (430, Yes), the system may select the next label (435) and repeat steps410to425for the next label.

If there is no entry (410, No), the system may create or generate a probability-estimation entry for the label. The system may set the frequency component of the probability-estimation entry to the product of a similarity between node n and neighbor u and the learned label weight for the label l in the learned label structure of neighbor u (420). The product may also be represented by wvuŶul(i−1), where i represents the current iteration and i−1 represents the previous iteration and wvuis the weight of the edge between node v and u in the input graph. The system may also set the error component of the new entry in the probability-estimation list (425). In some implementations, the error component may be a product of a probability threshold and the sum of the similarities between node n and the previously seen neighbors. In other words, if node n has t neighbors, the first learned label structure the node n selects is for neighbor to. When the node n has finished steps405to445for neighbor to, the node n moves on to neighbor u2. At this point, u1is a previously seen neighbor. When node n moves to neighbor u2, neighbors u1, u2, and u3are previously seen neighbors, etc. Thus, the error component may be represented as Σi=1t-1δwvui, where the current neighbor u is ut. The probability threshold δ may be a dynamic threshold or a static threshold. For example, the probability threshold δ may be set to a uniform distribution of the labels (e.g., l/m). This is a static threshold because it is the same for all neighbors. In some implementations, the probability threshold δ may be dynamic, in that it changes for each neighbor. The dynamic threshold may be the average probability mass for neighbor u, which can be provided in the learned label structure for neighbor u or can be calculated from the learned label structure. For example, the average probability mass for neighbor u (δu) may be expressed as

As discussed above, in an implementation that uses a sparsity approximation, the learned label structure of a neighbor may have k labels. Thus, Σi=1kŶuli(i−1)represents the sum of the learned label weights in the learned label structure of neighbor u. After setting the error component, the system determines if there is another label to process (430). If there is another label to process (430, Yes), the next label from the learned label structure for u is selected (435) and steps410to430are repeated for the next label.

If all k labels in the learned label structure for neighbor u have been selected (430, No), the system may add the probability δ to the frequency component of each probability-estimation entry for a label that is not in the learned label structure of node u (440). In other words, if label l identified in an entry of the probability-estimation list does not exist in Ŷu, the system may add δ to the frequency component of the entry for label l. The probability threshold may be static or dynamic, as discussed above.

The system may then inspect each entry in the probability-estimation list and discard entries that do not meet a total error threshold. The total error threshold may be a sum of the product of the probability threshold and the similarity of the current neighbor (e.g., ut) and each previous neighbor (e.g., u1to u(t-1)). The total error threshold may be expressed as Σi=1tδwvui, where the probability threshold δ is either dynamic (e.g., specific to the neighbor) or static, as described above. An entry in the probability-estimation list does not meet the threshold when the sum of the frequency component and the error component are less than the threshold.

If the node v has another neighbor (450, Yes), the system may repeat steps405to445for the next neighbor. Otherwise (450, No), the system may determine the k top-ranked probability-estimation entries based on the sum of the frequency component and the error component (455). Any entries that are not in the top k can be deleted. The labels of the remaining entries are the top-ranked labels for node v and the system will update the learned label weight for these labels, as described in more detail with regard toFIG. 6. Process400then ends, having identified the top k labels for the node v. It is understood that each node in the input graph may perform process400and the processing may be concurrent.

FIG. 5illustrates a flow diagram of an example process500for updating label weights, according to an implementation. The process500may be performed as part of step225ofFIG. 2. The process500is illustrated for a single node v, but it is understood that each node may independently perform process500. Process500(along with optional process400) may be considered a second round in a message-based distributed system using, for example, Pregel, Giraph, MapReduce, etc. Process500may select a first label for the node v (505). In a sparsity approximation implementation, the first label may be selected from the probability-estimation list for the node v, as discussed above with regard to step455ofFIG. 4. In other implementations, the label may be selected from the learned label structure for node v. The system may then update the learned label weight of the selected label l by aggregating the learned label weights of neighbor nodes (510). The learned label weights for neighbors represent label weights from a prior iteration, which were received in this iteration round from the neighbors, as described with regard toFIG. 2. The learned label weights for a neighbor may be represented by the notation Ŷu(iteration−1)The updated learned label weight for the label l and node v may be represented by the notation Ŷvl(iteration).

The system may determine if the node v has any additional labels to be updated (515). In some implementations, the additional labels may be in the probability-estimation list for the node and process500may update leaned label weights for at most k labels (where k>0 and <<m, the total number of labels in the label set). In some implementations, the system may update learned label weights for all labels for node v (e.g., m labels). If there is another label (515, Yes), the system may select the next label and perform step510for the next label. Once the system has updated the learned label weight for the top-ranked k labels or all m labels, depending on the implementation, (515, No), the system may optionally calculate an average probability mass for the node v based on the updated learned label weights of the top-ranked k labels (525). The average probability mass may be calculated as

(1.0-∑i=1k⁢Y^vli(i))/m-k,
where Ŷvli(i)represents the updated learned label weights for the top-ranked k labels for node v and m is the number of labels in the label set. In some implementations, the average probability mass for node v may be stored, for example in the learned label structure for node v and may be passed to neighbors with the learned label structure. In some implementations, the average probability mass is calculated, when needed, from the learned label structure. Process500then ends for node v. It is understood that each node may perform process500to update its own respective learned label structure. It is also understood that process500may be performed by each node in a concurrent manner (e.g., the nodes do not need to wait for another node to perform process500).

FIG. 6illustrates a flow diagram of an example process600for updating a learned label weight for a node by aggregating the learned label weights of neighbor nodes, according to an implementation. The process600may be performed as part of step510ofFIG. 5. The process600is illustrated for a single node v and label l, but it is understood that node v may perform process600for at least k labels and as many as m labels. The updated label weight includes the sum of three components: a seed component, a total neighbor component, and a uniform distribution component. Process600determine whether the node v is a seed, or labeled, node (605). A seed node is a node that has at least one associated label (e.g., training label) in the input graph. If the node v is a seed node (605, Yes), the system may set the seed component (610) according to the following: μ1Yvl, where Yvlrepresents the original weight of label l for node v in the input graph (e.g., before propagation began), and μ1is a first component weight. In some implementations, μ1may have a value of one (1) and, therefore, the seed component is equal to the original weight of label l for node v. It is noted that if label l is not a training label for node v it will have an original weight of zero. If the node v is not a seed node (605, No), the system sets the seed component to zero (615).

The system next calculates a neighbor component for each neighbor u of the node v (620). The neighbor component may be expressed as wvuΣl′cll′Ŷul′(i−1)where wvuis a similarity measure between node v and neighbor u, cll′, is a similarity measure between label l and l′ (which is 1 if label l′ is label l), Ŷul′(i−1)is the learned label weight of label l′ in the learned label structure for node u (which was sent to node v). In other words, the neighbor component for neighbor u is the sum of the products of the weight of each label l′ in the received learned label structure of the neighbor u and a similarity between the l′ and l multiplied by a similarity measure between the neighbor u and the node v.

The system may calculate a total neighbor component for the node v by adding the neighbor components together and multiplying the sum by a second component weight (630). The second component weight is a weight assigned for the total neighbor component. In some implementations this weight may be small, for example 0.01. The system may calculate a label weight for the label l of node v by adding the seed component, the total neighbor component, and a uniform distribution component (635), This sum may be divided by a normalization constant for the node v and the label l to ensure that the calculated weight does not exceed one, which represents a 100% probability. The uniform distribution component may be the product of a third component weight and the uniform distribution of the labels (e.g., l/m). The third component weight may be small, for example 0.01. The uniform distribution component may be expressed as μ3Ul, where Ulis the uniform distribution of label l, or l/m. The normalization constant for label l and node v may be expressed as μ1svv+μ2ΣuεN(v)wvuΣl′cll′+μ3, where svvis one (1) if the node v is a seed node and zero (0) otherwise.

The system may update the learned label weight for label l in the learned label structure of node v with the calculated label weight (640). Process600then ends for this label and the node v may perform process600for another label. It is understood that each node in the input graph will perform process600for at least k different labels and as many as m labels. Process600may also be represented by the following (which uses notation described above):

Mvli=μ1⁢svv+μ2⁢∑u∈N⁡(v)⁢eui-1⁢wvu⁢∑l′⁢cll′+μ3l
Performance Evaluation

Processing times for propagating labels using various implementations described above were evaluated and found to be much faster and more scalable than conventional semi-supervised learning techniques, such as MAD and MAD-SKETCH. MAD has been shown to outperform traditional graph-based semi-supervised learning algorithms (e.g., “Experiments in graph-based semi-supervised learning methods for class-instance acquisition,” Proceedings of the 48thAnnual Meeting of the Association for Computational Linguistics, ACL 2010, pp. 1473-1481, 2010). MAD-SKETCH is similar to MAD but further approximates the label distribution on each node using Count-min Sketch to reduce the space and complexity. The size of the graphs tested appear in Table 1 below:

For the tables below, EXPANDER refers to implementations that do not use a sparsity approximation, do not augment edges, and does not consider entropy of each neighbor; EXPANDER-W refers to implementations that do consider entropy of each neighbor, EXPANDER-A refers to implementations that augment edges based on deep learning. Table 2 illustrates the comparison of mean-reciprocal rank (MMR) and precision scores between MAD and various implementations using the Freebase-Entity data set as the source data set. Precision measures the accuracy of the top-ranking learned labels at each iteration, e.g., P@5 is the precision at the 5thiteration. In Table 2, the input graph included 5 seeds per label and in Table 3 it is 10 seeds per label.

Table 4 illustrates a scalability comparison that takes into account running time and space usage. The more time the label propagation takes to complete, the less scalable it is because increased labels can make the propagation too slow to be useful. Similarly, the more memory a label propagation method uses the less likely the method will be to work for larger graphs. In Table 4, the input graph includes 5 seeds per label and used the Freebase-Entity data set as the source data set. As indicated above, EXPANDER-S represents implementations with a sparsity approximation as discussed herein (where k is the quantity of top-ranked labels tracked per node). MAD-Sketch uses a Count-min Sketch. A Count-min Sketch approximation approximates the whole label distribution for each node. MAD and EXPANDER do not use sparsity approximation or Count-min sketch.

Table 5 is similar to table 4, except the source data set is the Freebase-Relationship Subset. Table 5 does not include MAD-Sketch (w=109, d=3) row because it runs out of memory running on a single machine.

FIG. 7illustrates memory usage enhancements that result from the sparsity approximation of various implementations. As illustrated inFIG. 7, implementations using the sparsity approximation to compactly store labels and their learned weights use almost constant memory, regardless of the number of labels in the set of labels.FIG. 8demonstrates the scalability of implementations using the sparsity approximation as the input graph size increases. As demonstrated by the graphs ofFIG. 8, when the graph is large and cannot fit on one machine, the sparsity approximation still uses consistent memory and completes in a relatively short amount of time. As tables 2-5 andFIGS. 7 and 8demonstrate, implementations provide high-quality results using less memory than other semi-supervised learning methods.

FIG. 9shows an example of a generic computer device900, which may be system100or client170ofFIG. 1, which may be used with the techniques described here. Computing device900is intended to represent various example forms of computing devices, such as laptops, desktops, workstations, personal digital assistants, cellular telephones, smart phones, tablets, servers, and other computing devices, including wearable devices The components shown here, their connections and relationships, and their functions, are meant to be exemplary only, and are not meant to limit implementations of the inventions described and/or claimed in this document.

Computing device900includes a hardware (e.g., silicone-based) processor902, memory904, a storage device906, and expansion ports910connected via an interface908. In some implementations, computing device900may include transceiver946, communication interface944, and a GPS (Global Positioning System) receiver module948, among other components, connected via interface908. Device900may communicate wirelessly through communication interface944, which may include digital signal processing circuitry where necessary. Each of the components902,904,906,908,910,940,944,946, and948may be mounted on a common motherboard or in other manners as appropriate.

The processor902can process instructions for execution within the computing device900, including instructions stored in the memory904or on the storage device906to display graphical information for a GUI on an external input/output device, such as display916. Display916may be a monitor or a flat touchscreen display. In some implementations, multiple processors and/or multiple buses may be used, as appropriate, along with multiple memories and types of memory. Also, multiple computing devices900may be connected, with each device providing portions of the necessary operations (e.g., as a server bank, a group of blade servers, or a multi-processor system).

The memory904stores information within the computing device900. In one implementation, the memory904is a volatile memory unit or units. In another implementation, the memory904is a non-volatile memory unit or units. The memory904may also be another form of computer-readable medium, such as a magnetic or optical disk. In some implementations, the memory904may include expansion memory provided through an expansion interface.

The storage device906is capable of providing mass storage for the computing device900. In one implementation, the storage device906may be or contain a computer-readable medium, such as a floppy disk device, a hard disk device, an optical disk device, or a tape device, a flash memory or other similar solid state memory device, or an array of devices, including devices in a storage area network or other configurations. A computer program product can be tangibly embodied in such a computer-readable medium. The computer program product may also contain instructions that, when executed, perform one or more methods, such as those described above. The computer- or machine-readable medium is a storage device such as the memory904, the storage device906, or memory on processor902.

The interface908may be a high speed controller that manages bandwidth-intensive operations for the computing device900or a low speed controller that manages lower bandwidth-intensive operations, or a combination of such controllers. An external interface940may be provided so as to enable near area communication of device900with other devices. In some implementations, controller908may be coupled to storage device906and expansion port914. The expansion port, which may include various communication ports (e.g., USB, Bluetooth, Ethernet, wireless Ethernet) may be coupled to one or more input/output devices, such as a keyboard, a pointing device, a scanner, or a networking device such as a switch or router, e.g., through a network adapter.

The computing device900may be implemented in a number of different forms, as shown in the figure. For example, it may be implemented as a standard server930, or multiple times in a group of such servers. It may also be implemented as part of a rack server system. In addition, it may be implemented in a personal computer such as a laptop computer922, or smart phone936. An entire system may be made up of multiple computing devices900communicating with each other. Other configurations are possible.

FIG. 10shows an example of a generic computer device1000, which may be system100ofFIG. 1, which may be used with the techniques described here. Computing device1000is intended to represent various example forms of large-scale data processing devices, such as servers, blade servers, datacenters, mainframes, and other large-scale computing devices. Computing device1000may be a distributed system having multiple processors, possibly including network attached storage nodes, that are interconnected by one or more communication networks. The components shown here, their connections and relationships, and their functions, are meant to be exemplary only, and are not meant to limit implementations of the inventions described and/or claimed in this document.

Distributed computing system1000may include any number of computing devices1080. Computing devices1080may include a server or rack servers, mainframes, etc. communicating over a local or wide-area network, dedicated optical links, modems, bridges, routers, switches, wired or wireless networks, etc.

In some implementations, each computing device may include multiple racks. For example, computing device1080aincludes multiple racks1058a-1058n. Each rack may include one or more processors, such as processors1052a-1052nand1062a-1062n. The processors may include data processors, network attached storage devices, and other computer controlled devices. In some implementations, one processor may operate as a master processor and control the scheduling and data distribution tasks. Processors may be interconnected through one or more rack switches1058, and one or more racks may be connected through switch1078. Switch1078may handle communications between multiple connected computing devices1000.

Each rack may include memory, such as memory1054and memory1064, and storage, such as1056and1066. Storage1056and1066may provide mass storage and may include volatile or non-volatile storage, such as network-attached disks, floppy disks, hard disks, optical disks, tapes, flash memory or other similar solid state memory devices, or an array of devices, including devices in a storage area network or other configurations. Storage1056or1066may be shared between multiple processors, multiple racks, or multiple computing devices and may include a computer-readable medium storing instructions executable by one or more of the processors. Memory1054and1064may include, e.g., volatile memory unit or units, a non-volatile memory unit or units, and/or other forms of computer-readable media, such as a magnetic or optical disks, flash memory, cache, Random Access Memory (RAM), Read Only Memory (ROM), and combinations thereof. Memory, such as memory1054may also be shared between processors1052a-1052n. Data structures, such as an index, may be stored, for example, across storage1056and memory1054. Computing device1000may include other components not shown, such as controllers, buses, input/output devices, communications modules, etc.

An entire system, such as system100, may be made up of multiple computing devices1000communicating with each other. For example, device1080amay communicate with devices1080b,1080c, and1080d, and these may collectively be known as system100. As another example, system100ofFIG. 1may include one or more computing devices1000as graph system100, a separate computing device1000as root120, and one or more computing devices1000as graph cluster160. Furthermore, some of the computing devices may be located geographically close to each other, and others may be located geographically distant. The layout of system1000is an example only and the system may take on other layouts or configurations.

According to certain aspects of the disclosure, a method includes initializing, for nodes in a distributed graph comprising labeled nodes and unlabeled nodes, wherein an edge between two nodes in the distributed graph represents a similarity measure between the two nodes, learned label weights for at least a non-zero quantity k of labels per node. The method also includes, for a first node in the distributed graph, sending the learned label weights for the node to each neighbor in the distributed graph, receiving a set of at least k learned label weights from each neighbor,

determining top-ranked labels for the first node based on a probability-based sparsity approximation using the received sets of learned label weights, and calculating learned label weights for top-ranked labels of the first node based on an aggregation of the received sets of learned label weights from the neighbors. The method also includes repeating the sending, receiving, determining, and calculating for a quantity of iterations, determining, from the learned label weights for the first node, a first label with a weight that meets or exceeds a threshold, and automatically updating a source data set with the first label, responsive to the determining.

These and other aspects can include one or more of the following features. For example, the nodes in the distributed graph may represent textual information and the method may also include, prior to initializing the learned label weights, adding additional edges between nodes in the distributed graph based on deep learning of a large corpus of text. In some implementations, adding the additional edges can include learning a semantic embedding for each node in the distributed graph using the deep learning, generating a signature for each node by applying locality sensitive hashing on the semantic embedding for the node, using the signature of a third node and the signature of a second node to determine a similarity metric between the third node and the second node, and adding an edge between the third node and the second node when the similarity metric meets a second threshold.

As another example, determining the top-ranked labels for the first node can include, for each of the labels in the sets of labels from the neighbors, determining a probability for the label based on a weighted frequency with which the label is encountered and determining a maximum error of the weighted frequency for the label, wherein the sum of the probability and the maximum error is used to determine the top-ranked labels. In some implementations, determining the probability and the maximum error includes, as the set of learned label weights for a tthneighbor utare received: determining whether a probability-estimation entry exists for a label l for the first node, the probability-estimation entry including a label identifier for the label l, a frequency component, and an error component; when the probability-estimation entry exists, adding the product of the learned label weight for the label l and a similarity measure between the neighbor utand the first node to the frequency component; and when the probability-estimation entry does not exist, creating a new probability-estimation entry for the label l, and repeating the determining, adding and creating for each label l with a learned label weight for the neighbor ut. Creating the new probability-estimation entry for the label l may include setting the frequency component of the new probability-estimation entry to the product of the learned label weight for label l and a similarity measure between the neighbor utand the first node, and setting the error component of the new probability-estimation entry to a probability threshold. In some implementations, the probability threshold may be a dynamic threshold calculated by adding the product, calculated for each previously received neighbor u, of a similarity measure between the previously received neighbor u and first node and an average probability mass for neighbor u. In some such implementations, the method may also include discarding probability-estimation entries for labels where the sum of the frequency component and the error component is less than the sum of, for each of the t neighbors u, the similarity measure between the first node and the neighbor u and the average probability mass for neighbor u.

As another example, calculating the learned weights of top-ranked labels for the first node includes, for a label l of the top-ranked labels, determining a seed component for the label l that maintains an original weight for labels of labeled nodes, for each neighbor, determining a neighbor component for the label l, the neighbor component being based on similarity of the neighbor to the first node and similarity of the k labels for the neighbor to the label l, calculating a total neighbor component for the label l by adding the neighbor components and multiplying the sum by a component weight, calculating a uniform distribution component for the label l, and setting the learned label weight for the label l to a sum of the seed component, the total neighbor component, and the uniform distribution component, the sum being divided by a normalization component for the first node and the label l.

As another example, aggregating the received sets of learned label weights from neighbors of the first node includes, for each neighbor u: determining a product by multiplying a sum of learned label weights for neighbor u by a similarity measure between the first node and the neighbor u, adding the products together, and normalizing the added products. In some implementations, the similarity measure is multiplied by an entropy parameter for the neighbor u, the entropy parameter being based on an entropy of label distribution in neighbor u. As another example, the source data set may include entities and attributes, a node in the distributed graph may represent an entity in the source data set, a label for the node may represent an attribute of the entity in the source data set, and updating the source data set includes adding, in the source data set, the attribute represented by the first label to the entity represented by the first node.

According to an aspect of the disclosure, a system includes a plurality of computing devices including processors formed in a substrate and memory storing: an input graph of nodes connected by edges, an edge representing a similarity measure between two nodes, the graph being distributed across the plurality of computing devices, wherein at least some of the nodes are seed nodes associated with one or more training labels from a set of labels, each training label having an associated original weight, the input graph being generated based on a source data set. The memory may also store instructions that, when executed by the processors, cause the plurality of distributed computing devices to perform operations. The operations may include propagating the training labels through the input graph using a sparsity approximation for label propagation, resulting in learned weights for respective node and label pairs, and automatically updating the source data set using node and label pairs selected based on the learned weights.

These and other aspects can include one or more of the following features. For example, the source data set may be a knowledge base and a node in the input graph may represent a pair of entities in the knowledge base and a label for the node may represent a relationship between the pair of entities in the knowledge base. As another example, the source data set may be a graph-based data store, a node in the graph represents an entity in the graph-based data store, a label for the node represents an attribute of the entity in the graph-based data store, and updating the source data set includes, for a first node-first label pair, associating, in the graph-based data store, an attribute corresponding to the first label with an entity corresponding to the first node.

As another example, propagating the labels can occur in a quantity of iterations that update learned label weights for respective nodes. In some implementations, propagating the labels uses a learned label structure for a first node of the input graph, the learned label structure including, for a non-zero quantity k of the labels in the input graph: a label identifier and a learned label weight, where k is less than a total quantity of unique labels in the input graph. In some implementations, updating the learned label weights for a first node in a first iteration includes receiving learned label weights for k labels from neighbor nodes, where k is a non-zero integer, ranking labels for the first node based on the received learned label weights to identify top-ranked labels, and for k of the top-ranked labels for the first node, calculating a label weight for the label using a similarity measure between the first node and the neighbor u. In some implementations, calculating the label weight for the label also uses a similarity measure between each label l′ that has a learned label weight for the neighbor u and label l and the learned label weight of label l′ for neighbor u. In some implementations, the similarity between label l and label l′ is taken from a similarity matrix generated from random walks from the seed nodes in the graph. In some implementations, calculating the label weight for the label also uses a similarity measure between each label l′ that has a learned label weight for the neighbor u and label l and the learned label weight of label l′ for neighbor u and an entropy parameter for neighbor u based on a label distribution for neighbor u. In some implementations, calculating the label weight for the label also uses a uniform distribution of label l, a normalization constant for the first node and label l, and similarity measure between each label l′ that has a learned label weight for the neighbor u and label l and the learned label weight of label l′ for neighbor u.

According to one aspect of the disclosure, a method includes initializing, for nodes in an input graph comprising labeled nodes and unlabeled nodes, learned label weights for a non-zero quantity q of labels per node, wherein an edge between two nodes in the input graph represents a similarity measure between the two nodes and adding additional edges between nodes in the input graph based on deep learning of a large corpus of text. The method may also include, for a first node in the input graph, sending the learned label weights for the first node to each neighbor in the input graph, receiving a set of q learned labels and respective learned label weights from each neighbor, updating the learned weights of labels for the first node based on an aggregation of the received learned label weights from the neighbors, and repeating the sending, receiving, and updating for a quantity of iterations. The method may further include determining, from the updated learned label weights for the first node, a first label with a learned label weight that meets or exceeds a threshold, and automatically updating a source data set with the first label, responsive to the determining.

These and other aspects can include one or more of the following features. For example, q may be a quantity smaller than the unique set of labels in the input graph and the method may also include determining top-ranked labels for the first node based on a probability-based sparsity approximation using the received learned label weights, wherein updating the learned weights includes updating q of the top ranked labels for the first node. In some implementations, adding the additional edges cab include learning a semantic embedding for each node in the input graph using the deep learning, generating a signature for each node by applying locality sensitive hashing on the semantic embedding for the node, using the signature of a third node and the signature of a second node to determine a similarity metric between the third node and the second node, and adding an edge between the third node and the second node when the similarity metric meets a second threshold. As another example, aggregating the received learned label weights includes using an entropy parameter for each neighbor u to minimize the contribution of neighbors with high label distribution entropy.

A number of implementations have been described. Nevertheless, various modifications may be made without departing from the spirit and scope of the invention. In addition, the logic flows depicted in the figures do not require the particular order shown, or sequential order, to achieve desirable results. In addition, other steps may be provided, or steps may be eliminated, from the described flows, and other components may be added to, or removed from, the described systems. Accordingly, other implementations are within the scope of the following claims.