US 10,762,134 B1Granted

Node graph traversal methods

AssigneePinterest, Inc.

InventorsChantat Eksombatchai, Jurij Leskovec, Rahul Sharma, Charles Walsh Sugnet, Mark Bormann Ulrich

Life of this patent

Estimating the term…

Loading patent…

Abstract

This disclosure describes systems and methods that facilitate the generation of recommendations by traversing a graph. Walks that traverse the graph may be initiated from a plurality of different nodes in the node graph. In order to give greater or lesser weight to particular nodes, the walks may have different lengths depending on the nodes from which they are initiated, or an unequal amount of walks may be distributed between nodes from which walks are initiated. A plurality of walks through a node graph may be tracked, and visit counts or scores for nodes in the node graph may be determined. For example, scores may be increased for nodes that are visited by a walk initiated from a first node and a second walk initiated from a second node, or scores may be decreased for nodes that are not visited by a first walk initiated from a first node and a second walk initiated from a second node. Content corresponding to nodes may be recommended based on the scores or visit counts.

Claims20

Dependent claims

A computer-implemented method, comprising:

under control of one or more computing systems configured with executable instructions,
forming a graph that includes:
a first plurality of nodes, each node of the first plurality of nodes representing a collection;
a second plurality of nodes, each node of the second plurality of nodes representing a media object;
and
a plurality of edges, each edge of the plurality of edges representing an association between a node of the first plurality of nodes and a node of the second plurality of nodes;
determining a query that includes at least a first query node and a second query node,
determining, for the query, a respective walk length based at least in part on a first walk length of a first random walk, a second walk length of a second random walk, and a weighting factor for the query;
determining, for each of at least a portion of the second plurality of nodes, a visit count by at least:
performing a first plurality of random walks through the graph that are initiated from the first query node;
performing a second plurality of random walks through the graph that are initiated from the second query node;
and
tracking a number of times the node is visited by walks of the first plurality of random walks and walks of the second plurality of random walks;
determining, for each of the at least a portion of the second plurality of nodes, a proximity score indicative of a proximity of the node with respect to the first query node or the second query node, wherein:
each proximity score is determined at least in part by applying a proximity score function to a corresponding visit count such that at least one of:
the proximity score of each node of the second plurality of nodes that has been visited by both a first walk of a first plurality of random walks and a second walk of the second plurality of random walks is increased;
or
the proximity score of each node of the second plurality of nodes that has not been visited by both at least one walk of the first plurality of random walks and at least one walk of the second plurality of random walks is decreased;
determining, based at least in part on the proximity scores, a recommendation that indicates at least one of the at least a portion of the second plurality of nodes;
and
sending the recommendation to a user device for presentation.

18 more elements

A computer-implemented method, comprising:

under control of one or more computing systems configured with executable instructions,
forming a graph that includes:
a first plurality of nodes;
a second plurality of nodes, each node of the second plurality of nodes representing a media object;
and
a plurality of edges, each edge of the plurality of edges representing an association between at least one node of the first plurality of nodes and at least one node of the second plurality of nodes;
determining a query that indicates a first sub-plurality of nodes of the second plurality of nodes;
for each node of the second plurality of nodes, determining a visit count, wherein each visit count is determined based at least in part on:
a first plurality of random walks initiated from a first node of the first sub-plurality of nodes that traverse through the graph;
and
a second plurality of random walks initiated from a second node of the first sub-plurality of nodes that traverse through the graph;
determining, for each node of at least a portion of the second plurality of nodes, a proximity score at least in part applying a proximity score function to the visit count of the respective node such that at least one of:
the proximity score of each node of at least the portion of the second plurality of nodes that has been visited by both a first walk of the first plurality of random walks and a second walk of the second plurality of random walks is increased;
or
the proximity score of each node of at least the portion of the second plurality of nodes that has not been visited by both at least one walk of the first plurality of random walks and at least one walk of the second plurality of random walks is decreased;
determining, based at least in part on the proximity scores, a recommendation that indicates a second sub-plurality of the second plurality of nodes;
and
sending the recommendation to a user device.

15 more elements

A computer system, comprising:

one or more processors;
one or more non-transitory computer readable medium storing program instructions that when executed by the one or more processors cause the one or more processors to at least:
form a graph that includes:
a first plurality of nodes;
a second plurality of nodes;
and
a plurality of edges, wherein each edge of the plurality of edges represents an association between a node of the first plurality of nodes and a node of the second plurality of nodes;
and
determine at least one query node;
determine, for each of at least a portion of the second plurality of nodes, a visit count by at least counting a number of times the node is traversed by one or more of a plurality of random walks through the graph, wherein a length of each random walk is determined at least in part by:
determining a maximum amount of nodes in the first plurality of nodes that are associated with a node in the second plurality of nodes;
identifying an overall walk length for apportioning walk lengths for random walks initiated from each of the at least one query nodes;
allocating a scaled walk length to each of the at least one query nodes by:
determining a degree that is representative of an amount of nodes in the first plurality of nodes that are associated with the at least one query node;
and
determining the scaled walk length based at least in part on the degree, the maximum amount of nodes, and the overall walk length;
wherein each random walk of the plurality of random walks is performed in accordance with the scaled walk length of the at least one query node from which the random walk is initiated;
determine, for each of at least a portion of the second plurality of nodes, a proximity score, wherein each proximity score indicates a proximity of the node with respect to at least one query node;
determine, based at least in part on the proximity scores, a recommendation that indicates at least one node of the second plurality of nodes;
and
send the recommendation to a user device.

18 more elements

Dependencies are inferred from the claim text.

Facts

Application: 15/870,785Filed 12 Jan 2018 · us provisional application
Priority: 10 Nov 2017
Granted: 1 Sep 2020
Term ends: Not estimatedThe source records don’t support an estimate.

Classification10 codes

G06F 16/9024
Indexing; Data structures therefor; Storage structures: graphs; Linked lists
G06F 16/24578
With adaptation to user needs: using ranking
G06F 16/435
Querying: filtering based on additional data, e.g. user or group profiles
G06F 16/958
Retrieval from the web: organisation or management of web site content, e.g. publishing, maintaining pages or automatic linking