Semi-supervised learning via deep label propagation

1. A method comprising:

by a computing device, accessing a graph data structure comprising a plurality of nodes and connections between the nodes, each of the nodes being associated with one of a plurality of users of an online social network, each of the connections between two of the nodes representing a relationship between the associated users and establishing a single degree of separation between those users, each of the nodes being either labeled or unlabeled with respect to a label type;

by the computing device, for each of the labeled nodes, propagating a label of the label type of that labeled node to one or more other nodes in the graph data structure through one or more connections connecting the labeled node and the one or more other nodes;

by the computing device, for each of the nodes, storing a first label distribution information associated with the label type based on the propagated labels reaching the node;

by the computing device, training a machine-learning model using (1) the labels associated with a set of the labeled nodes, (2) the first label distribution information of the set of the labeled nodes, and (3) features associated with the labeled nodes, the machine-learning model being trained to predict a label for a node based on the first label distribution information and features of the node, wherein the features of the node are different from labels associated with the node and are known prior to the training and label propagation; and

by the computing device, generating a predicted label for each of the unlabeled nodes using the trained machine-learning model by providing as inputs the first label distribution information associated with the unlabeled node and one or more features associated with the unlabeled node.

2. The method of claim 1 , further comprising:

by the computing device, for each of the unlabeled nodes, propagating the predicted label of the unlabeled node to one or more other nodes in the graph data structure through one or more connections connecting the unlabeled node and the one or more other nodes; and

by the computing device, for each of the nodes, storing a second label distribution information associated with the label type based on the propagated predicted labels reaching the node.

3. The method of claim 2 , further comprising:

by the computing device, training a second machine-learning model using the labels, the first label distribution information, the features, and the second label distribution information of a second set of the labeled nodes, the second machine-learning model being trained to predict a label for a node based on the first label distribution information, the features, and the second label distribution information of the node; and

by the computing device, generating a revised predicted label for each of the unlabeled nodes using the trained second machine-learning model, the first label distribution information associated with the unlabeled node, the one or more features associated with the unlabeled node, and the second label distribution information associated with the unlabeled node.

4. The method of claim 1 ,

wherein the predicted label for each of the unlabeled nodes is iteratively revised;

wherein the machine-learning model is iteratively retrained;

wherein during each iteration of an iteration process:

the machine-learning model is retrained using the predicted labels generated in the previous iteration; and

the predicted labels are revised using the machine-learning model retrained in the current iteration.

5. The method of claim 4 , wherein the iteration process terminates upon satisfaction of a convergence condition.

6. The method of claim 4 , wherein the iteration process terminates when a predetermined number of iterations complete.

7. The method of claim 1 , wherein the features of the node comprise one or more of demographic or location information associated with a user represented by the node.

8. One or more computer-readable non-transitory storage media comprising software that is operable when executed to:

access a graph data structure comprising a plurality of nodes and connections between the nodes, each of the nodes being associated with one of a plurality of users of an online social network, each of the connections between two of the nodes representing a relationship between the associated users and establishing a single degree of separation between those users, each of the nodes being either labeled or unlabeled with respect to a label type;

for each of the labeled nodes, propagate a label of the label type of that labeled node to one or more other nodes in the graph data structure through one or more connections connecting the labeled node and the one or more other nodes;

for each of the nodes, store a first label distribution information associated with the label type based on the propagated labels reaching the node;

train a machine-learning model using (1) the labels associated with a set of the labeled nodes, (2) the first label distribution information of the set of the labeled nodes, and (3) features associated with the labeled nodes, the machine-learning model being trained to predict a label for a node based on the first label distribution information and features of the node, wherein the features of the node are different from labels associated with the node and are known prior to the training and label propagation; and

generate a predicted label for each of the unlabeled nodes using the trained machine-learning model by providing as inputs the first label distribution information associated with the unlabeled node and one or more features associated with the unlabeled node.

9. The media of claim 8 , wherein the software is further operable when executed to:

for each of the unlabeled nodes, propagate the predicted label of the unlabeled node to one or more other nodes in the graph data structure through one or more connections connecting the unlabeled node and the one or more other nodes; and

for each of the nodes, store a second label distribution information associated with the label type based on the propagated predicted labels reaching the node.

10. The media of claim 9 , wherein the software is further operable when executed to:

train a second machine-learning model using the labels, the first label distribution information, the features, and the second label distribution information of a second set of the labeled nodes, the second machine-learning model being trained to predict a label for a node based on the first label distribution information, the features, and the second label distribution information of the node; and

generate a revised predicted label for each of the unlabeled nodes using the trained second machine-learning model, the first label distribution information associated with the unlabeled node, the one or more features associated with the unlabeled node, and the second label distribution information associated with the unlabeled node.

11. The media of claim 8 ,

wherein the predicted label for each of the unlabeled nodes is iteratively revised;

wherein the machine-learning model is iteratively retrained;

wherein during each iteration of an iteration process:

the machine-learning model is retrained using the predicted labels generated in the previous iteration; and

the predicted labels are revised using the machine-learning model retrained in the current iteration.

12. The media of claim 11 , wherein the iteration process terminates upon satisfaction of a convergence condition.

13. The media of claim 11 , wherein the iteration process terminates when a predetermined number of iterations complete.

14. The media of claim 8 , wherein the features of the node comprise one or more of demographic or location information associated with a user represented by the node.

15. A system comprising:

one or more processors; and

one or more computer-readable non-transitory storage media coupled to one or more of the processors and comprising instructions operable when executed by one or more of the processors to cause the system to:

access a graph data structure comprising a plurality of nodes and connections between the nodes, each of the nodes being associated with one of a plurality of users of an online social network, each of the connections between two of the nodes representing a relationship between the associated users and establishing a single degree of separation between those users, each of the nodes being either labeled or unlabeled with respect to a label type;

for each of the labeled nodes, propagate a label of the label type of that labeled node to one or more other nodes in the graph data structure through one or more connections connecting the labeled node and the one or more other nodes;

for each of the nodes, store a first label distribution information associated with the label type based on the propagated labels reaching the node;

train a machine-learning model using (1) the labels associated with a set of the labeled nodes, (2) the first label distribution information of the set of the labeled nodes, and (3) features associated with the labeled nodes, the machine-learning model being trained to predict a label for a node based on the first label distribution information and features of the node, wherein the features of the node are different from labels associated with the node and are known prior to the training and label propagation; and

generate a predicted label for each of the unlabeled nodes using the trained machine-learning model by providing as inputs the first label distribution information associated with the unlabeled node and one or more features associated with the unlabeled node.

16. The system of claim 15 , wherein the instructions are further operable when executed by one or more of the processors to cause the system to:

for each of the unlabeled nodes, propagate the predicted label of the unlabeled node to one or more other nodes in the graph data structure through one or more connections connecting the unlabeled node and the one or more other nodes; and

for each of the nodes, store a second label distribution information associated with the label type based on the propagated predicted labels reaching the node.

17. The system of claim 16 , wherein the instructions are further operable when executed by one or more of the processors to cause the system to:

train a second machine-learning model using the labels, the first label distribution information, the features, and the second label distribution information of a second set of the labeled nodes, the second machine-learning model being trained to predict a label for a node based on the first label distribution information, the features, and the second label distribution information of the node; and

generate a revised predicted label for each of the unlabeled nodes using the trained second machine-learning model, the first label distribution information associated with the unlabeled node, the one or more features associated with the unlabeled node, and the second label distribution information associated with the unlabeled node.

18. The system of claim 15 ,

wherein the predicted label for each of the unlabeled nodes is iteratively revised;

wherein the machine-learning model is iteratively retrained;

wherein during each iteration of an iteration process:

the machine-learning model is retrained using the predicted labels generated in the previous iteration; and

the predicted labels are revised using the machine-learning model retrained in the current iteration.

19. The system of claim 18 , wherein the iteration process terminates upon satisfaction of a convergence condition.

20. The system of claim 15 , wherein the features of the node comprise one or more of demographic or location information associated with a user represented by the node.