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.
1. A system comprising:
at least one processor formed in a substrate;
memory storing a graph that includes nodes connected by edges, each edge connecting a first node and a second node and representing a similarity measure between the first node and the second node, at least some nodes in the graph being labeled nodes, each labeled node having at least one label selected from m possible labels and, for each label, an original weight; and
memory storing instructions that, when executed by the at least one processor, cause the system to:
generate a respective semantic embedding in a semantic embedding space for each node in the graph using deep learning on a large corpus of text,
apply locality sensitive hashing to each respective semantic embedding to generate a respective signature for each node,
add an edge to the graph between a pair of nodes having respective signatures that meet a similarity threshold, and
using the added edges to propagate labels from the labeled nodes to unlabeled nodes based on similarity with and distance from the labeled nodes.
2. The system of claim 1 , wherein adding edges to the graph increases an accuracy of the propagated labels.
3. The system of claim 1 , wherein each signature is represented by D bits and generating a respective signature for each node includes:
for each bit d in D, generating a hyperplane in the semantic embedding space using random spherical coordinates; and
for each of the nodes, setting each bit din D by:
determining a product of the semantic embedding for the node and the random spherical coordinates for the bit d,
responsive to the product being greater than zero, setting the bit d to one, and
responsive to the product not being greater than zero, setting the bit d to zero.
4. The system of claim 3 , wherein the system generates a plurality of signatures for each node, each signature having a different randomization procedure, and wherein the similarity of any two nodes is determined by the most similar signature of the plurality of signatures for the two nodes.
5. A system comprising:
at least one processor formed in a substrate;
memory storing a graph that includes nodes connected by edges, each edge connecting a first node and a second node and representing a similarity measure between the first node and the second node, at least some nodes being seed nodes, each seed node having an original weight for at least one label selected from m possible labels and wherein each node in the graph has a respective learned label structure, each learned label structure identifying a quantity k of the m labels, each of the k labels without an original weight having an associated weight with an initial value; and
memory storing instructions that, when executed by the at least one processor, cause the system to:
for each node, update the k labels and weights in the respective learned label structure using propagation based on similarity and distance from the seed nodes, and
automatically update a source data set with at least some of the updated labels based on the weights.
6. The system of claim 5 , wherein k is equal to m.
7. The system of claim 5 , wherein k is at least an order of magnitude smaller than m.
8. The system of claim 7 , wherein the propagating uses a sparsity approximation.
9. The system of claim 5 , wherein k is smaller than m and each leaned label structure further includes an average probability mass value for the respective node.
10. The system of claim 9 , wherein the average probability mass is based on a sum of the weights for the k labels and a difference between m and k.
11. The system of claim 5 , wherein the memory further stores instructions that, when executed by the at least one processor, causes the system to augment the graph by:
learning a respective semantic embedding for each node in the graph using deep learning on a large corpus of text;
applying locality sensitive hashing to each respective semantic embedding to generate a respective signature for each node; and
adding an edge to the graph between a pair of nodes having respective signatures that meet a similarity threshold.
12. The system of claim 5 , wherein updating each label l of a node v is based on the sum of neighbor components of nodes connected to node v, a neighbor component for a neighbor node u being a product of the weight of the edge between v and u, a similarity measure between the label l and a label l′ of neighbor node u and a weight of l′ for node u from a preceding propagation.
13. The system of claim 12 , wherein propagating includes devaluing neighbor nodes u with respective learned label structures having skewed weights.
14. A non-transitory computer-readable medium including instructions that, when executed by at least one processor, cause a system to perform operations including:
repeating, for a quantity of iterations:
sending a first learned label structure from a first node in a graph to each neighboring node in the graph, a neighboring node being a node connected to the first node by a weighted edge in the graph, the weight representing a similarity measure between the first node and the neighboring node, wherein at least one of the neighboring nodes is a seed node having an original weight for at least one label selected from m possible labels, and wherein each node in the graph has a respective learned label structure identifying a quantity k of the m labels, each of the k labels without an original weight in the learned label structure having an associated learned weight,
receiving a set of learned label structures, each learned label structure in the set bring from a respective neighboring node of the neighboring nodes, and
updating the learned weights in the first label structure based on an aggregation of weights from the set of learned label structures; and
automatically updating a source data set to incorporate the first label responsive to determining that a learned label weight for a first label in the first learned label structure meets a threshold.
15. The non-transitory computer-readable medium of claim 14 , wherein k is equal to m.
16. The non-transitory computer-readable medium of claim 14 , wherein k is at least an order of magnitude smaller than m.
17. The non-transitory computer-readable medium of claim 16 , wherein each leaned label structure further includes an average probability mass value for the respective node, the average probability mass being based on a sum of the weights for the k labels and a difference between m and k.
18. The non-transitory computer-readable medium of claim 16 , wherein the updating uses a sparsity approximation.
19. The non-transitory computer-readable medium of claim 14 , wherein the instructions further cause a system to add edges the graph before the iterations by:
generating a respective semantic embedding for each node in the graph using deep learning on a large corpus of text;
applying locality sensitive hashing to each respective semantic embedding to generate a respective signature for each node; and
adding an edge to the graph between a pair of nodes having respective signatures that meet a similarity threshold.
20. The non-transitory computer-readable medium of claim 14 , wherein updating each label l of the first node is based on the sum of neighbor components of the neighboring nodes, a neighbor component for a neighbor node u being a product of the weight of the edge between the first node and u, a similarity measure between the label l and a label l′ of neighbor node u and a weight of l′ for node u from the preceding iteration.