Label propagation in a distributed system

A system comprising:

• one or more computers and one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising:
• maintaining data in a distributed computing system, the data describing a graph representing relationships among items, the graph having a plurality of vertices representing the items, and having a plurality of edges connecting the plurality of vertices representing the relationships among the items;
• obtaining, during a first iteration and by a first vertex of the graph, a value for a first label that indicates a strength of association between the first vertex of the graph and a characteristic for a first item represented by the first vertex;
• providing, by the first vertex of the graph and to a second vertex of the graph during the first iteration, a weighted value for the first label that indicates the strength of association between the first vertex of the graph and the characteristic for the first item represented by the first vertex weighted by a value of a third label that indicates a degree to which an edge that connects the first vertex and the second vertex affects the effect of the value of the third label on the value of a second label of the second vertex;
• obtaining, during the first iteration and by a third vertex of the graph, a value for a fourth label that indicates a strength of association between the third vertex of the graph and a characteristic for a third item represented by the third vertex;
• providing in parallel with weighted value for the first label being provided to the second vertex by the first vertex, by the third vertex of the graph and to the second vertex of the graph during the first iteration, a weighted value for the fourth label that indicates the strength of association between the third vertex of the graph and the characteristic for the third item represented by the third vertex weighted by a value of a fifth label that indicates a degree to which an edge that connects the third vertex and the second vertex affects the effect of the value of the fourth label on the value of the second label of the second vertex;
• determining, by the second vertex and during a second iteration after the first iteration, that the second vertex does not include a label that corresponds to the weighted value received from the first vertex for the first label and the weighted value received from the third vertex for the fourth label;
• in response to determining, by the second vertex, that the second vertex does not include a label that corresponds to the weighted value received from the first vertex for the first label and the weighted value received from the third vertex for the fourth label, determining a value for the second label that indicates a strength of association between the second vertex of the graph and a characteristic for a second item represented by the second vertex based at least on an aggregation of the weighted value received from the first vertex for the first label and the weighted value received from the third vertex for the fourth label instead of based on an aggregation of the value for the second label during the first iteration, the weighted value received from the first vertex for the first label, and the weighted value received from the third vertex for the fourth label;
• and
• providing the value for the second label that indicates the strength of association between the second vertex of the graph and the characteristic for the second item represented by the second vertex.

A non-transitory computer-readable storage medium storing instructions executable by one or more computers which, upon such execution, cause the one or more computers to perform operations comprising:

• maintaining data in a distributed computing system, the data describing a graph representing relationships among items, the graph having a plurality of vertices representing the items, and having a plurality of edges connecting the plurality of vertices representing the relationships among the items;
• obtaining, during a first iteration and by a first vertex of the graph, a value for a first label that indicates a strength of association between the first vertex of the graph and a characteristic for a first item represented by the first vertex;
• providing, by the first vertex of the graph and to a second vertex of the graph during the first iteration, a weighted value for the first label that indicates the strength of association between the first vertex of the graph and the characteristic for the first item represented by the first vertex weighted by a value of a third label that indicates a degree to which an edge that connects the first vertex and the second vertex affects the effect of the value of the third label on the value of a second label of the second vertex;
• obtaining, during the first iteration and by a third vertex of the graph, a value for a fourth label that indicates a strength of association between the third vertex of the graph and a characteristic for a third item represented by the third vertex;
• providing in parallel with weighted value for the first label being provided to the second vertex by the first vertex, by the third vertex of the graph and to the second vertex of the graph during the first iteration, a weighted value for the fourth label that indicates the strength of association between the third vertex of the graph and the characteristic for the third item represented by the third vertex weighted by a value of a fifth label that indicates a degree to which an edge that connects the third vertex and the second vertex affects the effect of the value of the fourth label on the value of the second label of the second vertex;
• determining, by the second vertex and during a second iteration after the first iteration, that the second vertex does not include a label that corresponds to the weighted value received from the first vertex for the first label and the weighted value received from the third vertex for the fourth label;
• in response to determining, by the second vertex, that the second vertex does not include a label that corresponds to the weighted value received from the first vertex for the first label and the weighted value received from the third vertex for the fourth label, determining a value for the second label that indicates a strength of association between the second vertex of the graph and a characteristic for a second item represented by the second vertex based at least on an aggregation of the weighted value received from the first vertex for the first label and the weighted value received from the third vertex for the fourth label instead of based on an aggregation of the value for the second label during the first iteration, the weighted value received from the first vertex for the first label, and the weighted value received from the third vertex for the fourth label;
• and
• providing the value for the second label that indicates the strength of association between the second vertex of the graph and the characteristic for the second item represented by the second vertex.