Node graph pruning and fresh content
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.
1. A computer-implemented method, comprising:
determining, for each collection of a plurality of collections, a respective plurality of media objects that are associated with the collection;
determining a diversity score for each collection based at least in part on the respective plurality of media objects;
determining, based at least in part on the diversity scores, a first sub-plurality of collections from the plurality of collections;
forming a graph that includes a plurality of nodes representing the first sub-plurality of collections and media objects associated with the first sub-plurality of collections;
determining a target node in the plurality of nodes;
determining a cluster that includes a first sub-plurality of nodes of the plurality of nodes and the target node;
initiating a first plurality of random walks through the graph, wherein at least one node in the cluster is visited by at least one random walk of the first plurality of random walks;
determining, for the target node, a target node visit count based at least in part on a number of times the target node or a node of the first sub-plurality of nodes is visited by a random walk of the first plurality of random walks; and
determining, based at least in part on the target node visit count, a recommendation that indicates at least one node of the plurality of nodes.
2. The computer-implemented method of claim 1 , further comprising:
receiving a selection of a first media object associated with a first node of the at least one node indicated by the recommendation;
initiating a second plurality of random walks from the first node; and
determining, based at least in part on nodes visited during the second plurality of random walks, a refinement recommendation that indicates at least one second node of the plurality of nodes.
3. The computer-implemented method of claim 1 , wherein:
the first plurality of random walks are initiated from a plurality of query nodes; and
the computer-implemented method further comprises:
determining a multi-hit node that was visited via a first random walk from the first plurality of random walks and a second random walk from the first plurality of random walks; and
assigning a higher relative visit count to the multi-hit node in determining the recommendation.
4. The computer-implemented method of claim 1 , wherein:
the first plurality of random walks are initiated from a plurality of query nodes;
each of the plurality of query nodes are assigned a respective weight indicating an importance of each query node; and
the first plurality of random walks are performed in accordance with the respective weights.
5. The computer-implemented method of claim 1 , wherein:
the first plurality of random walks are performed in accordance with a defined characteristic.
6. A computer-implemented method, comprising:
accessing a dataset including a first plurality of media objects that form a first plurality of collections;
generating, based at least in part on the first plurality of collections and the first plurality of media objects, a reduced dataset from the dataset, the reduced dataset including a second plurality of media objects that form a second plurality of collections;
generating a first graph that includes a first plurality of nodes representing the second plurality of collections and the second plurality of media objects;
determining, based at least in part on a query, at least one query node of the first graph that is associated with the query;
performing a plurality of random walks through the first graph that each originate from the at least one query node and visit a second plurality of nodes of the first plurality of nodes;
determining a plurality of node visit counts for the plurality of random walks based at least in part on a number of times nodes of the second plurality of nodes of the first graph were visited during the plurality of random walks;
determining, based at least in part on the plurality of node visit counts, a plurality of proximity scores for nodes of the second plurality of nodes of the first graph that were visited during the plurality of random walks; and
determining, based at least in part on the plurality of proximity scores, a first node from the nodes of the second plurality of nodes as a recommendation responsive to the query.
7. The computer-implemented method of claim 6 , wherein generating the reduced dataset from the dataset includes:
determining, for a first collection of the first plurality of collections, a respective topic score for each media object of the first plurality of media objects included in the first collection;
determining, based at least in part on the respective topic scores, a diversity score for the first collection, the diversity score being indicative of an overall topical diversity of the media objects included in the first collection;
determining that the diversity score for the first collection does not satisfy a diversity score criterion; and
excluding the first collection from the dataset in generating the reduced dataset.
8. The computer-implemented method of claim 6 , wherein generating the reduced dataset from the dataset includes:
determining, for a first collection of the first plurality of collections, a respective media object topic score for each media object of the first plurality of media objects included in the first collection;
determining, based at least in part on the respective media object topic scores, a collection topic score for the first collection;
determining, for a first media object included in the first collection and based at least in part on a first respective media object topic score associated with the first media object and the collection topic score, a first similarity score;
determining that the first similarity score does not satisfy a similarity score criterion; and
excluding the first media object from the reduced dataset.
9. The computer-implemented method of claim 6 , further comprising:
determining a defined characteristic that specifies a first characteristic associated with at least one of an edge of the first graph or at least one node of the first plurality of nodes of the first graph; and
performing the plurality of random walks based at least in part on the defined characteristic.
10. The computer-implemented method of claim 6 , wherein:
the at least one query node includes a plurality of query nodes;
the plurality of random walks are initiated from one or more of the plurality of query nodes; and
the computer-implemented method further comprises:
determining a multi-hit node that was visited via a first random walk from the plurality of random walks and a second random walk from the plurality of random walks; and
assigning a higher relative proximity score to the multi-hit node in determining the recommendation.
11. The computer-implemented method of claim 6 , wherein:
the at least one query node includes a plurality of query nodes;
the plurality of random walks are initiated from the plurality of query nodes;
each of the plurality of query nodes are assigned a respective weight indicating an importance of each query node; and
the plurality of random walks are performed based at least in part on the respective weights assigned to the plurality of query nodes.
12. The computer-implemented method of claim 11 , wherein the respective weights may determine at least one of:
a number of random walks originating from each of the plurality of query nodes; or
a walk length of the plurality of random walks originating from each of the plurality of query nodes.
13. The computer-implemented method of claim 6 , further comprising:
determining a target node from the first plurality of nodes; and
determining, based at least in part on the target node, a cluster of nodes from the first plurality of nodes,
wherein:
a target node visit count of the plurality of node visit counts that corresponds to the target node is based at least in part on a number of visits to the cluster of nodes.
14. The computer-implemented method of claim 6 , wherein:
the dataset is maintained in a second graph having a third plurality of nodes corresponding to the first plurality of collections and the first plurality of media objects; and
the reduced dataset and the first graph are generated by pruning at least one node of the third plurality of nodes from the second graph.
15. The computer-implemented method of claim 6 , further comprising:
receiving a selection of the first node;
initiating a second plurality of random walks from the first node; and
determining, based at least in part on nodes visited during the second plurality of random walks, a refinement recommendation that indicates at least one second node of the second plurality of nodes.
16. A computing system, comprising:
one or more processors; and
a memory storing program instructions that, when executed by the one or more processors, cause the one or more processors to at least:
access a first dataset including a first plurality of media objects that form a first plurality of collections;
determine, based at least in part on the first plurality of collections and the first plurality of media objects, a reduced dataset from the first dataset, the reduced dataset including a second plurality of media objects that form a second plurality of collections, wherein determining the reduced dataset includes using at least one of a diversity pruning technique or an edge pruning technique;
form a graph that includes a plurality of nodes representing the second plurality of collections and the second plurality of media objects;
receive a query associated with a query node of the plurality of nodes;
initiate a plurality of random walks from the query node;
determine a plurality of node visit counts for the plurality of random walks based at least in part on a number of times nodes of the plurality of nodes was visited during the plurality of random walks;
determine, based at least in part on the plurality of node visit counts, a plurality of proximity scores for the nodes of the plurality of nodes were visited during the plurality of random walks; and
determine, based at least in part on the plurality of proximity scores, at least one first node from the nodes of the plurality of nodes as a recommendation responsive to the query.
17. The computing system of claim 16 , wherein the program instructions that, when executed by the one or more processors, further cause the one or more processors to at least:
determine a defined characteristic that specifies a first characteristic associated with at least one of an edge of the graph or at least one node of the plurality of nodes of the graph; and
perform the plurality of random walks based at least in part on the defined characteristic.
18. The computing system of claim 16 , wherein:
the query node includes a plurality of query nodes;
the plurality of random walks are initiated from the plurality of query nodes; and
the program instructions that, when executed by the one or more processors, further cause the one or more processors to at least:
determine a multi-hit node that was visited via a first random walk from the plurality of random walks and a second random walk from the plurality of random walks; and
assign a higher relative proximity score to the multi-hit node in determining the recommendation.
19. The computing system of claim 16 , wherein:
the query node includes a plurality of query nodes;
the plurality of random walks are initiated from the plurality of query nodes;
each of the plurality of query nodes are assigned a respective weight indicating an importance of each query node; and
the plurality of random walks are performed based at least in part on the respective weights assigned to the plurality of query nodes.
20. The computing system of claim 16 , wherein:
the program instructions that, when executed by the one or more processors, further cause the one or more processors to at least:
determine a target node from the plurality of nodes; and
determine, based at least in part on the target node, a cluster of nodes from the plurality of nodes; and
a target node visit count of the plurality of node visit counts that corresponds to the target node is based at least in part on a number of visits to the cluster of nodes.