Node graph traversal methods

This disclosure describes systems and methods that facilitate generating recommendations by traversing a node graph. For example, recommendations may be generated for a node in the node graph by running a plurality of walks through the node graph and tracking the nodes visited by the walks. For example, a visit count or score may be maintained and/or updated for each node as the walks traverse through the node graph. The walks may be terminated after a defined amount of nodes in the node graph have visit counts or scores that satisfy a criterion. Content corresponding to nodes with the highest visit counts or scores may be recommended.

BACKGROUND

The user experience provided by content discovery applications may depend on the applications' ability to quickly make personalized recommendations relevant to a user's interest. If a user expresses interest in particular content, a content discovery application should be able to react and make high-quality recommendations relevant to the particular content in which the user has expressed interest. If the content discovery application provides irrelevant recommendations to a user, the user experience may be negatively impacted and the user may ignore the recommendations.

The relevance or quality of recommendations provided by the content discovery application can be improved by increasing the complexity of algorithms used to make recommendations. However, increased algorithm complexity may increase the time and computing resources needed to make recommendations. This increased time may cause the user to lose interest in the application for which the recommendation is provided.

The amount of content being considered for potential recommendations and the amount of users handled by the content discovery application compounds the above problems. In addition, miscategorized or inconsistently categorized data may further compound these problems. For example, human users may save various unrelated images to a collection. For example, to save time, by mistake, or due to unfamiliarity, a human user may “save” an image of a classic car to a collection intended for recipes. The association of the car with a recipe collection may lead to the car being recommended to another user that has expressed interest in recipes. Such a recommendation may annoy the user or cause the user to ignore the recommendation. The complexity of the recommendation algorithm may be increased in order to reduce the likelihood that the image of the car will be provided as a recommendation result for a user that has expressed interest in recipes. However, the increased complexity of the algorithm may cause an increased time delay between a user expressing interest in recipes and a recommendation result being provided to the user. This delay may negatively impact the user experience.

In addition, maintaining and generating recommendations from inconsistent or erroneously categorized data may require increased computing resources (e.g., processing and memory). These problems may be compounded for large amounts of human categorized data, e.g., 1+ billion human categorized representations.

Systems and methods are desired that facilitate high-quality relevant recommendations to be provided from a large pool of human-categorized content to many users with minimal delay.

DETAILED DESCRIPTION

In one or more implementations disclosed herein, content recommendations may be determined by a recommendation service running a plurality of random walks through a node graph and tracking the nodes visited by the plurality of random walks. The plurality of random walks may be initiated from one or more query nodes in the node graph. Amounts of visits to nodes in the node graph may be tracked by visit count. In some implementations, proximity scores that indicate relevance of nodes with respect to query nodes may be determined based at least in part on the visit counts. In some implementations, content or a collection(s) of content to be recommended to a user may be determined based at least in part on the visit counts or proximity scores. For example, content corresponding to the nodes with the highest visit counts or proximity scores may be recommended to a user. Content may be sent for presentation on a user device, such as a laptop or other computing device.

In some implementations, a node graph may be constructed from a previously constructed node graph. In one or more implementations, the node graph may be constructed from data that includes collections of representations and associations between the collections and the representations. A node graph is constructed to have nodes corresponding to collections, nodes corresponding to representations, and edges corresponding to associations or connections between the collections and the representations.

Representations may include media objects, such as images, video files, sound files, etc. Each representation may be associated with one or more collection and each collection may be associated with one or more representations. Each collection may also be associated with a user. In some implementations, a collection may also be associated with one or more other collections and/or a representation may be associated with one or more other representations. Associations between collections and representation may be designated by users. For example, a user may create a collection for “French cooking” and select images of prepared French dishes and/or images of recipes to be associated with the French cooking collection.

A recommendation service may initiate a recommendation process by running a plurality of random walks through the node graph. The plurality of random walks may be initiated from one or more query nodes in the node graph. Each query node may correspond to a collection or representation in the node graph. A node in the node graph may be determined to be a query node based at least in part on a user for which a recommendation is to be provided expressing interest in a representation or a collection of representations that correspond to the node in the node graph. For example, a user may express interest in a representation or collection by viewing a representation or content associated with the collection, selecting the representation or collection, or adding the representation to a collection.

The quality of recommendations and the amount of computing resources (computing power, cache, memory, etc.) needed to formulate recommendations from a node graph may depend at least in part on topical similarities between representations and their associated collections or a topical diversity of the representations associated with the collection. In some implementations, the data from which the node is to be constructed may include representations and collections that have been erroneously categorized. For example, a user may select to associate a representation of a car with a collection that is associated with representations involving vegetarian food. Running a plurality of random walks through a node graph that models topically diverse collections, or collections that are associated with topically dissimilar representations, may produce inferior recommendations and/or may require additional computing resources (processing and/or memory) compared to running a plurality of random walks through a node graph that models collections that are associated with representations that have a high topical similarity and low topical diversity. To improve the topical similarity and/or topical diversity of a node graph, data from which the node graph is to be constructed may be analyzed and a portion of the data may be identified. The identified portion of the data may be excluded from being incorporated into the node graph. Excluding such data from being incorporated into a node graph may enable a node graph to be constructed that is capable of providing better quality recommendations while requiring fewer computing resources. Example pruning processes are discussed in greater detail below.

In some implementations, a pruning process for excluding data that is used to construct a node graph involves “diversity pruning.” Diversity pruning may include obtaining topic scores for representations included in data from which a node graph is to be constructed. Topic scores for representations may be determined, for example, based on textual descriptions or other information that is associated with each representation. A textual description for a representation may be provided, for example, by users and/or a source of the representation. A topic score for the representation may be a probabilistic topic vector for the representation. Diversity scores for collections may be determined based on the topic scores for representations that are associated with each collection. A diversity score for a collection may be an indication of an amount of topical diversity, topical variance, or topical entropy of the representations that are associated with the collection.

As discussed further below, a diversity score may be determined based on a variety of factors, including, but not limited to, topical variance between nodes and/or data represented by nodes, topical entropy between nodes and/or data represented by nodes, moment of distribution of topics between nodes and/or data represented by nodes, etc.

If a diversity score for a collection does not meet a criterion that is indicative of an acceptable amount of diversity for the collection, the collection and/or its associations may be excluded from being incorporated into a node graph that is constructed from the data. As a result, diversity pruning may reduce an amount of collections of topically diverse representations that are incorporated into a constructed node graph.

In some implementations, a pruning process for excluding a portion of data that is used to construct a node graph involves an edge pruning process. An edge pruning process may exclude data that is indicative of associations between collections and representations from being incorporated into a node graph. An edge pruning process may involve obtaining topic scores for collections that are included in the data. A topic score for a collection may be determined based at least in part by obtaining a topic score for each representation that is associated with the collection. Topic scores for representations may be determined, for example, based on textual descriptions and/or other information that are associated with the representations. A textual description that is associated with a representation may be provided by a user or by a source of the representation.

The edge pruning process may involve determining similarity scores that are indicative of topical similarities between collections and one or more representations that are associated with each collection. A similarity score between a collection and a representation may be determined, for example, by determining a cosine similarity of a topic score for the collection and a topic score for a representation that is associated with the collection. If the similarity score does not satisfy a criterion that is indicative of an amount of topical similarity, then an association between the collection and the representation is excluded from being incorporated into a node graph. For example, a node graph will not include an edge that corresponds to the association between the collection and the representation with a similarity score that does not satisfy the criterion. Excluding such edges from being incorporated into a node graph may allow a recommendation service to provide more relevant recommendations in less time and/or with fewer computing resources.

In implementations involving more than one query node from which random walks are initiated, a recommendation service may allocate different “weights” or levels of importance between some or all of the query nodes. Levels of importance between query nodes may be determined, for example, based at least in part on a date that a representation or a collection corresponding to a query node was added or modified, a date associated with the query nodes, or an amount of nodes that are connected to the query node. In some implementations, a date may be associated with each query node and more importance may be allocated to more recent query nodes. In one or more implementations, different weights may be assigned to the query nodes so that one or more query nodes may have a relatively higher or lower influence on the recommendations that are ultimately provided by running the plurality of random walks through the node graph. For example, amounts of walks may be allocated to query nodes so that different amounts of walks are initiated from some or all of the query nodes. In general, the greater the amount of walks that are initiated from a query node, the greater the influence of the query node on the recommendation. For example, given query nodes A and B, the recommendation service may determine that two walks are to be initiated from node A for every one walk initiated from node B. In this example, node A may have a greater influence than node B on the content that is ultimately recommended because nodes around node A may get more visits from random walks than nodes around node B because more walks are initiated from node A.

In some implementations, step lengths indicative of a maximum amount of edges that may be traversed by each random walk may be varied between query nodes. For example, given query nodes A and B, the recommendation service may determine that node A is to have a greater influence than node B on the content that is ultimately recommended. In this example, the recommendation service may allocate ten steps for every walk initiated from node A and five steps for every walk initiated from node B. In this example, node A may have a greater influence than node B on the content that is ultimately recommended because nodes around node A may get more visits from random walks than nodes around node B because the walks from node A may have a greater length.

In operation, individual walks may terminate once one or more conditions have been met. For example, each random walk may terminate after traversing through the node graph a defined amount of steps corresponding to a step length. In one or more implementations, a random walk may terminate after a determination that the random walk has traversed to an end point. An end point for a random walk may be determined where there is no node to traverse to other than a node that has already been visited by the particular random walk. In some implementations, the end point may be a query node. In some implementations, a random walk is restarted from a same query node once an individual random walk has terminated.

In some implementations, the process of running the plurality of random walks through the node graph may terminate once a defined amount of individual random walks have been initiated and terminated. In one or more implementations, the plurality of random walks through the node graph may terminate once a defined amount of nodes in the node graph have visit counts or proximity scores that meet defined criteria. For example, the process of running the plurality of random walks through the node graph may terminate subsequent to a determination that a defined amount of nodes in the node graph have visit counts or proximity scores that meet a defined visit count or a defined proximity score.

In some implementations, a running of a plurality of random walks through the node graph may be modified to favor traversing to certain nodes over other nodes. In such implementations, it will be appreciated that the random walks are not truly random. For example, random walks may traverse the node graph only along edges or to particular nodes that are associated with a defined characteristic. For example, the defined characteristic may include, for example, geographic location, language, a topic score, etc. In one or more implementations, edges that are connected to nodes in the node graph that have a defined characteristic are determined, and random walks may only traverse along these determined edges. For example, if only English language recommendations are desired, the defined characteristic may be English language content. Information, such as user-provided textual descriptions, associated with collections or representations corresponding to the nodes may be analyzed to determine nodes and/or edges that are associated with the English language. In this example, random walks traverse only to nodes or along edges associated with the English language.

The nodes visited by each step through the node graph by a random walk may be tracked and a visit count indicating an amount of visits by random walks to each node may be maintained. In some implementations, a query node of the random walk from which each visit originated may be tracked and maintained, for example, with the visit count. A visit count for a node may be indicative of a relevance of the node to a query. In one or more implementations, proximity scores for nodes in the node graph may be determined based at least in part on the visit counts for the nodes. A proximity score for a node may be indicative of an amount of relevance of the node to the query. In some implementations, the proximity score for a node may be equivalent to the visit count for the node.

In some implementations, a node that has been visited by random walks initiated from different query nodes may have a proximity score that is “boosted” or increased to an amount that is greater than the visit count for the node. This may be done because nodes that have been visited by random walks initiated from two or more different query nodes may be considered more relevant than a node that has only been visited by walks initiated from a single query node.

In some implementations, a cluster of nodes and a target node may be determined from the node graph. For each visit by a random walk to a node included in the cluster, the visit count and/or proximity score for the target node is increased. Clustering allows the visit count or proximity score to be increased for a node even if the node has not been visited by the plurality of random walks. The cluster may be determined based on proximity to the target node in the node graph. For example, for a target node that corresponds to a representation, the cluster may be determined by identifying all collections that are associated with the representation and then identifying a group of representations that are associated with those collections. The group or a subset of the group of representations may be the cluster. The target node may correspond to a representation or a collection that is to have greater priority or weight with respect to other representations or collections. For example, the target node may correspond to an advertisement.

Referring now toFIG. 1, which is a block diagram of an example recommendation environment100in which a collection management system103manages data101and a recommendation engine110of the collection management system103provides recommendation services. The collection management system103may include a network of computer servers. A computer network102, such as a local area network (LAN), wide area network (WAN), the Internet, or a combination thereof, connects the collection management system103, publisher websites104, and client devices106.

The client devices106may include electronic devices such as computers, laptops, tablets, mobile phones and the like that may be used by a plurality of users to interact (e.g., modify or add) with data101. For example, the client devices106may be used by a user to create a collection that is added to the data101and/or associate representations with the collection. Users may use the client devices106to add a representation from the client device106and/or from publisher websites104to data101, and/or to view representations provided by the collection management system103, other users, and/or other publisher websites104.

Publisher websites104provide representations (e.g., images) that are available via the network102. The data101may include links to representations that are provided by the publisher websites104. An example publisher website104is a collection of web pages formatted in hypertext markup language (HTML) that can contain text, graphic images, multimedia content, and programming elements, such as scripts. Each publisher website104may be maintained by an entity that manages and/or owns the website.

The collection management system103may include one or more servers that interact with client devices106over the network102. The collection management system103may maintain and modify the data101. The data101may include, for example, collection data112, one or more node graphs114, and/or user data116. The collection data112may include collections, representations, and related data that may indicate, among other things, associations between representations and collections.

The node graph114may be constructed from at least a portion of the collection data112. The node graph114may be a model of data in the collection data112. Each node of the node graph114may correspond to a collection or a representation from the collection data112. Edges of the node graph114that connect different nodes of the node graph correspond to associations between collections and representations. The edges may indicate that a particular representation is associated with particular collections in the collection data112or associated with other representations in the collection data112.

In some implementations, the node graph114may be constructed from another node graph. For example, the node graph114may be constructed from a previously constructed node graph that has been “pruned” to include fewer edges and/or nodes with respect to the previously constructed node graph. As discussed further below with respect toFIGS. 4-8, nodes and/or edges of a node graph114may be pruned from a node graph and, as a result, the collection data112represented by those pruned nodes will not be represented by the node graph114. In one or more implementations where the node graph114is constructed from the collection data112, some collection data112may be excluded from being represented by the node graph114. The node graph114may be saved to cache, for example, a cache of the collection management system103. Saving or storing the node graph114to cache may allow for recommendations to be formulated more quickly.

The collection management system103may maintain and/or update user data116. User data116may include information about users, such as user interests or information related to past interactions by individuals with the collection management system103. For example, user data116may indicate a history of a user's interactions with data in the collection data112, the recommendation engine110, and/or the collection management system103. For example, user data116may indicate representations or collections previously viewed or selected by a user. In one or more implementations, user data116may indicate representations that have been recommended to a user and the particular recommended representations that the user has included in the user's collections.

The collection management system103may maintain or update collection data112. The collection data112may include, for example, collections, representations, associations between collections and representations, textual descriptions for representations, textual descriptions for collections, and constraints, to name a few. In one or more implementations, data in collection data112may be created and/or modified by users or a source of the representation and/or collection. For example, users may create collections and/or modify collections by interacting with the collection management system103via client devices106. For example, users may cause associations to be added to or removed from representations and collections in the collection data112. In one or more implementations, the collection management system103may associate a representation with multiple different collections in response to users requesting to “save” the representation to the collections. In some implementations, users may use the collection management system103to create a collection. For example, a user may create a collection for cooking and save representations related to cooking (e.g., images of cooked items, ingredient lists, instructional videos, etc.) to the collection. As discussed in more detail herein with respect toFIG. 2, other data may be associated with representations or collections, such as an identification of a user that created the collection, a context, a textual description, a category, supplemental information, a topic score, and the like.

Representations (also referred to as “media objects”) may include word processing documents, portable document format (PDF) documents, images, video, audio, etc. Representations may include content, such as words, phrases, pictures, sounds, and so on, and have associated information such as a description, a link, and/or an image. Representations may be provided by a publisher website104, a user, another party, etc., and stored in the collection data112. If the representation is provided by a publisher website104, a link (e.g., URL) to the publisher website may be included in the collection data112.

As stated above, a client device106may be an electronic device that may be controlled by a user and is capable of interacting with the collection management system103over the network102. Example client devices106include personal computers, mobile communication devices, and other devices that can send and receive data over the network102. A client device106typically includes a user application, such as a web browser or “app,” to facilitate the sending and receiving of data over the network102. The user application can enable a user to display and interact with representations located on a web page at a website on the World Wide Web (WWW) or a local area network.

The recommendation engine110may obtain a query (also referred to as a “query set”)111that corresponds to nodes in the node graph114from which random walks are to be initiated. The query111may refer to objects in the data101, such as nodes, representations, users, collections, etc. In one or more implementations, the query111refers to one or more nodes in the node graph, or the query111may refer to one or more representations and/or one or more collections that are selected by a user.

In one or more implementations, the query111may be received from a client device106. For example, the query111may refer to one or more representations that are selected by a user of the client device106. If the query111refers to data in the collection data112, such as collections and/or representations, the nodes in the node graph114that correspond to the collections and/or representation may be determined by the recommendation engine110. In one or more implementations, the query111is determined, at least in part, on the user data116. For example, the query111may correspond to representations that the user has previously viewed or added to collections associated with the user, as indicated in the user data116. In some implementations, the query111may be based on an amount of times that a user has viewed particular representations or collections, as indicated by the user data116. For example, the query111may include the most frequently viewed representations for a user. In some implementations, the query111may be determined based at least in part on a user inputting a textual search string that is provided to the recommendation engine110. For example, a user may enter the text “strawberry milkshake” in a search box and client device106, and the recommendation engine110may determine the query111based on the entered text.

The recommendation engine110may use the node graph114to provide to a recommendation or “recommendation set”113for the query111. In particular, the recommendation engine110may run a plurality of random walks through the node graph114and track visit counts for nodes of the node graph114. A visit count for a node is indicative of the number of times the node was visited by the plurality of random walks.

The plurality of random walks may be initiated from nodes in the query111, referred to herein as query nodes. A relevance or proximity of nodes in the node graph with respect to the query111may be indicated or determined based on the visit counts for each node. A recommendation113may be determined by the recommendation engine110. The recommendation113may refer to content (e.g., representations) in the collection data112that corresponds to nodes in the node graph114. For example, representations in the collection data112corresponding to the nodes in the node graph with the highest visit counts may be included in the recommendation113. The recommendation113may be sent to the client devices106for presentation. The recommendation113may be provided to client devices106in various ways such as email, text message, news feed, and/or sending representations (e.g., images) of the recommendation113for display via an application, etc.

Still referring toFIG. 1, in one or more implementations, a first presentation120-1of a representation122-1is presented on a display of a client device106. The representation122-1may be selected by a user via a client device106and included in a query111that is provided to the recommendation engine110. For example, the user may select the first representation122-1to indicate that the user desires to view recommended content that is similar to the representation122-1. After receiving the query111, the recommendation engine110may determine a node in the node graph114that corresponds to the representation122-1. This node may be a query node from which a plurality of random walks through the node graph114may be initiated to formulate a recommendation113. Based on the results of the random walks, the recommendation engine110may then determine the recommendation113that is provided to the client device106for presentation. The recommendation113may include a first plurality of representations124-1that are included in a second presentation120-2by the client device106. The user may continue to refine the query or submit an addition query based on the recommendation. For example, a representation R3A125of the first plurality of representations124-1may be selected and included in a query111that is provided to the recommendation engine110. The recommendation engine110may determine a node in the node graph114that corresponds to the representation R3A125that is a query node from which a plurality of random walks through the node graph114may be initiated. Based on the results of the plurality of random walks, recommendation engine110may determine a recommendation113that is provided to the client device106and presented in third presentation120-3of a second plurality of representations124-2by the client device106. In some implementations, this process may continue with further queries111being provided to the recommendation engine110and recommendations113being determined by the recommendation engine110and sent to the client device106for presentation.

Referring now toFIG. 2, which is a block diagram representing example collection data200, such as collection data112ofFIG. 1. The collection data200may include at least one collection201and at least one representation220. The collection201and the representation220may be associated with each other.

The collection201may include or be associated with user data202that may indicate, for example, a user that created the collection201and/or any user(s) identified as allowed to add or remove representations to the collection201. In addition, the collection201may include context data204that may indicate a context for the collection201. The context data204may be selected by a user or determined by a collection management system, such as the collection management system103ofFIG. 1. The context data204may indicate a user-specific meaning for the collection201, for example, “birthday gifts2014.” In this example, the context data204indicates the collection is for items that the user has previously received. In another example, context data204may indicate gifts that are desired by a user.

The collection201may include or be associated with topic score data206indicating a topic or topics to which the collection pertains. The topic score data206may include probabilistic topic vectors that are indicative of topic scores of representations associated with the collection201. For example, the topic score data206for the collection201may indicate individual topic scores of one or more associated representations, such as representation220. The topic score data206for the collection201may be determined, for example, by analyzing data associated with the topic scores of representations associated with the collection201. In one or more implementations, the topic scores may be determined by running a (Latent Dirichlet Allocation) LDA topic model on a textual description for the collection and/or representations associated with the representation. In some implementations, the topic scores may be determined by identifying an object that is represented by the representation.

The topic score data206for the collection201may be based on topic scores for representations associated with the collection201. For example, the topic score data206for the collection201may indicate amounts of content categories that are included in the collection201. The topic score data206may indicate an amount of content in particular categories. For example, the topic score data206for the collection201may indicate amounts of content related to certain categories, such as animals, books, arts and entertainment, sports, food and drink, etc. The topic scores may be determined by a collection management system and may be independent of a category assigned to the collection201by the user. In some implementations, the representation(s) included in the collection201and/or data associated with the representation(s) are processed to determine content categories in the collection201. For example, if the collection201includes a representation of a milkshake and a representation of a horse, the topic score for the collection201may be 50% of a “food” content category and 50% of an “animals” content category. In one or more implementations, the topic score data206may include a diversity score for the collection or one or more similarity scores that represent topical similarities between the collection and representations associated with the collection201.

The collection201may include description data208that indicates a description of the collection201. The description data208may be from a user's perspective. For example, the description data208may be provided by a user that created the collection201. For example, the description data208may include a textual description provided by the user, e.g., “French Cooking” for a collection directed to cooking French cuisine. In one or more implementations, the description data208includes comments on the collection201as posted by users. The description data208may be used to determine topic score data206and/or context data204.

Static information210may also be associated with the collection201. Static information210may include information provided by the creator of the collection201and/or other users of the collection management system. A collection management system may automatically incorporate certain information into the static information210that is relevant to the collection201based on the selected category and, optionally, the provided description data208. For example, other users may view, comment and/or otherwise provide feedback with respect to the collection201. Comments and/or other feedback from the creator and/or other users may be associated with the collection201and maintained as static information210.

Supplemental information211may also be associated with the collection201. Supplemental information211may be any form of information or action provided by a source of one or more representations associated with the collection201, a source of the collection201, or any other external source. For example, if the description data208of the collection201is about Hawaii, supplemental information211for the collection201may include weather condition information for Hawaii that is provided from a weather service from Hawaii.

The collection201may include or be associated with representation information212that indicates representations that are associated with the collection201. A user may select to add or remove a representation to or from the collection201and the representation information212may be updated accordingly. Edges in a node graph generated from the collection data200may correspond to the representation information212.

Constraints214may also be associated with the collection201and used to control access, modification or other aspects of the collection201. The constraints214may indicate who can view the collection201, remove representations from the collection201, and/or whether users can comment on the collection201, etc. For example, the constraints214may be specified by a creator of the collection201or a source of a representation included in the collection201.

Collection data200may be associated with one or more representations220. Each representation(s)220may include, for example, one or more word processing documents, portable document format (PDF) documents, images, video, audio, to name just a few. Each representation220may include content, such as words, phrases, pictures, sounds, and so on, or a link to such content. Each representation220may be associated with information such as a description, a link, and/or an image. Representations220may be provided by a publisher website and may be stored in the collection data200. If the representation220is provided by a publisher, a link (e.g., URL) to the publisher website may be associated with the representation220.

The representation220may be associated with user data222that may indicate, for example, a user that created, saved, or uploaded the representation220, a user or users that are allowed to add or remove the representation220to a collection, and/or a user or users that are allowed to comment or add annotations to the representation.

The representation220may be associated with a topic score223indicating a topic or topics with which the representation pertains. For example, the topic score223may be determined by analyzing a textual description provided by a user or content of the representation220, and/or determined based at least in part on an identification of an object that is included in or represented by the representation220. The topic score223of the representation220may indicate relative amounts of content categories for the representation220. For example, the topic score223for the representation220may indicate amounts of content related to certain categories, such as animals, books, arts and entertainment, sports, food and drink, etc. For example, a representation of Halloween-themed milkshake with a user-provided description of “Halloween milkshake” may have a topic score223that indicates a 50% topic score for a “food” content category and a 50% topic score for a “Halloween” content category. In one or more implementations, the topic score223for the representation220may be determined by running an LDA topic model on data associated with the representation (e.g., description data226) to obtain a probabilistic topic vector that is maintained as the topic score223.

In addition, the representation220may be associated with context data224that may indicate a context for the representation220. The context data224may be selected by a user or determined by a collection management system, such as the collection management system103ofFIG. 1. The context data224may indicate a user-specific meaning for the representation220. For example, the context data224for a representation of a house may be “2018 personal goals” for a user who aspires to buy a house in the year 2017, or “architecture” for a user interested in the architecture of the house in the representation. The context data224may be determined, for example, by analyzing a textual description provided by a user for the representation220.

The representation220may be associated with description data226for the representation220that provides a description for the representation220. The description data226may be a textual description that is provided by a user or a source of the representation220. The description data226may be from a user's perspective and/or specific to a user indicated by the user data202. In one or more implementations, the description data226for the representation220includes comments regarding the representation220as posted by one or more users. The description data208may be used to determine topic score data223and/or context data224for the representation220.

The representation220may be associated with static information228. Similar to the static information210for the collection201, static information228for the representation220may be associated with the representation220by a collection management system. For example, if a user has selected a representation220of the collection data200that is already known to the collection management system, existing information about the representation may be included in the static information228. Other static information228about the representation220may include comments or textual descriptions provided by other users of a collection management system, a creator of the representation220, or a source of the representation220, etc.

In some implementations, supplemental information230may be associated with the representation220. Supplemental information230may be any form of information or action provided by a source of the representation220or an external source. For example, the source of the representation220may provide information about the representation220while other external sources may provide actions relevant to the representation220. For example, if the representation220is an image of a television, a source of the television may be the manufacturer, such as Sony, and that source may provide information about the television. In this example, the information about the television provided by the manufacturer may include the dimensions, resolution, weight, etc. Other external sources, such as sellers of the television, may provide supplemental information230that may be associated with the representation220. For example, sellers of objects depicted in the representation220may provide actions that allow a user viewing the representation220to obtain information or to initiate a purchase of an object depicted by the representation220, or to obtain information about an external source that is offering the object for sale, etc.

The representation220may also be associated with collection information232that indicates one or more collections in the collection data200that include or are associated with the representation220. In some implementations, the representation220is associated with multiple different collections. As users add or remove the representation220from collections, the collection information232may be updated by a recommendation service. In some implementations, the representation220may be included in hundreds of different collections, where each collection is associated with a different user.

The representation220may also be associated with source information234that indicates, for example, a source from which the representation220was obtained or a source of an object that is represented in the representation220. For example, the source information234may specify a website from which the representation220was retrieved or is currently available to be retrieved. In one or more implementations, the source information234includes a URL of a website where an image of the representation may be obtained. Parent data236may indicate a collection for which the representation was obtained, if the representation220was based upon and/or created from the collection. For example, if the representation was added to a first collection from a second collection, the parent data236for the representation may indicate the second collection.

The representation220may be associated with constraint238that may be used to control access, modification or other aspects of the representation220. For example, a creator of the representation220may specify whether the representation220can be viewed by other users, copied into other collections, whether users can comment on the representation220, etc.

Finally, an object240may be associated with the representation220and may be indicative of an object represented or included in the representation220. For example, the object240may be Sony 54-inch plasma television for a representation220that depicts such a television. In another example, the object240may be Eiffel Tower for a representation that is an image of the Eiffel Tower. In another example, the representation includes a video of Lake Tahoe, and the object240may be Lake Tahoe or coordinates that indicate a specific location of Lake Tahoe where the video was captured. The object240may be specified by a source of the representation220or a user, or determined by analyzing the content of the representation220or the description data226for the representation220.

In operation, a recommendation engine may use a node graph that is constructed from collection data200(collections and representations) to formulate recommendations in response to queries. The node graph may be a model of collections and representations from collection data200, and associations between the collections and the representations. For example, the node graph may be a bipartite graph model. The node graph may be traversed by a plurality of random walks that are initiated from one or more query nodes corresponding to a query. The nodes visited by the random walks may be tracked and a proximity score may be determined that is indicative of the relevance of nodes with respect to the query set. Recommended representations and/or collections may be determined based on visit counts or proximity scores. The recommended representations and/or collections may be provided to a user.

Referring now toFIG. 3, which illustrates an example of a portion of a node graph300that may be constructed from and that may model a portion of collection data, such as collection data200discussed above with respect toFIG. 2. The portion of the node graph300includes first nodes303-1,303-2, and303-3and second nodes304-1through304-10. In this example, first nodes303-1,303-2, and303-3correspond to collections in the collection data and second nodes304-1through304-10correspond to representations (e.g., images, video, audio, etc.) in the collection data.

In addition, the portion of the node graph300contains edges306-1through306-12that connect first nodes and second nodes. Edges in a node graph may be determined based on associations between first nodes and second nodes as indicated in collection information232or representation information212discussed in connection withFIG. 2. Edges connecting first nodes and second nodes may correspond to representations and collections as indicated in collection data, such as collection data200.

A second node304may be connected to multiple first nodes303. For example, second node304-4may be connected to first nodes303-1,303-2, and303-3. This indicates that the representation corresponding to second node304-4is included in the collections represented by first nodes303-1,303-2, and303-3. In one or more implementations, the node graph300may contain no edges that connect two first nodes to one another and/or two or more second nodes to one another.

In one or more implementations, representations are associated with (or “included in”) collections by user inputs. For example, a connection between a representation in the collection data and a collection in the collection data may be established by a human user “saving” or otherwise indicating that the representation is to be associated with the collection. Edge306-1is an example of a connection between a first node303-1for a collection and a second node304-1for a representation. Edge306-1may indicate that in the collection data from which node graph300is generated or constructed, there is an association between a representation and a collection, or the representation represented by second node304-1has been included in the collection represented by first node303-1.

Still referring toFIG. 3, edges306-1,306-2,306-3, and306-12connect first node303-1with second nodes304-1,304-2,304-4, and304-6, respectively. Edge306-1corresponds to an association between a representation in the collection data corresponding to second node304-1being associated with a collection in the collection data corresponding to the first node303-1. In addition, edges306-2,306-3, and306-12correspond to associations between representations in the collection data corresponding to second nodes304-2,304-4, and304-6being associated with the first node303-1corresponding to a collection in the collection data.

In addition, edges306-4,306-5,306-6,306-9,306-10, and306-11connect first node303-2to second nodes304-3,304-4,304-5,304-7,304-8, and304-9. Edges306-4,306-5,306-6,306-9,306-10, and306-11correspond to associations between representations in the collection data corresponding to second nodes304-3,304-4,304-5,304-9,304-8, and304-7being associated with in the first node303-2corresponding to a collection in the collection data.

Furthermore, edges306-7and306-8connect first node303-3to second nodes304-4and304-10, respectively. Edges306-7and306-8correspond to associations between representation in the collection data corresponding to second nodes304-4and304-10, respectively, being included in the first node303-3corresponding to a collection of the collection data.

In operation, a recommendation process that may be performed, for example, by a recommendation engine, such as the recommendation engine110ofFIG. 1, may simulate a plurality of random walks along the node graph300that are initiated from a second node that is included in a query Q and record a number of times (visit count) the simulated walks visit each of the second nodes X. In one or more implementations, the representations in the collection data that correspond to the second nodes X with the highest visit counts V may be output as recommendations. In one or more implementations, the representations in the recommendation may be sent to a client device for presentation.

If associations between collections and representations in the collection data from which a node graph is constructed are provided by human users, some collections may be associated with topically dissimilar or topically diverse representations due to human error or otherwise. For example, a user may include diverse and unrelated representations in a collection by accident or due to lack of familiarity with an object management system. For example, a user may inadvertently include a car in a collection for recipes, and the car may be recommended in response to a query that includes nodes corresponding to representations connected to the recipe collection. Some users may include various topically unrelated representations (recipe, straw hat, golf club, classic muscle car, and a hamburger) in a collection. Incorporating such a collection of topically diverse representations into a node graph would negatively impact the recommendations that may be provided using the node graph.

The relevance and quality of recommendations that may be generated by running random walks through the node graph may be improved if the collections included in node graph are associated with topically similar representations and/or representations with low topical diversity. Utilizing node graphs that include collections of topically dissimilar or topically diverse representations to formulate recommendations may lead to irrelevant or low quality recommendations being provided to the user. Because topical dissimilarity between collections and representations and collections of topically diverse representations may have negative impacts on recommendations and system performance, it may be desirable to generate a node graph with reduced topical dissimilarity, or reduced diversity, with respect to collections and associated representations.

FIG. 4illustrates an example of a portion of a node graph400that has been generated from data that has been “pruned” so that certain data is not incorporated into the node graph400. In the example illustrated byFIG. 4, the data from which the portion of the node graph400has been constructed may be a diversity pruned version of the data from which the portion of the node graph300ofFIG. 3is constructed. Therefore,FIG. 4may include similar first nodes, second nodes, and edges as those discussed in connection withFIG. 3and, for purposes of brevity the nodes and edges depicted inFIG. 4will not be described in detail with regard toFIG. 4. Specifically, first nodes403-1,403-2, and403-3correspond to first nodes303-1,303-2, and303-3ofFIG. 3, respectively. Second nodes404-1,404-2,404-3,404-4,404-5,404-6,404-7,404-8,404-9, and404-10correspond to second nodes304-1,304-2,304-3,304-4,304-5,304-6,304-7,304-8,304-9, and304-10ofFIG. 3, respectively. Edges406-1,406-2,406-3,406-4,406-5,406-6,406-7,406-8,406-9,406-10,406-11, and406-12correspond to edges306-1,306-2,306-3,306-4,306-5,306-6,306-7,306-8,306-9,306-10,306-11, and306-12ofFIG. 3, respectively.

Still referring toFIG. 4, first node403-2, second nodes404-3,404-7,404-8, and404-9, and edges406-4,406-5,406-6,406-9,406-10, and406-11are shown with dotted lines to indicate that these portions would have been incorporated into the portion of the node graph400but for a diversity pruning process being applied to the data from which the portion of the node graph400is constructed. Diversity pruning involves excluding topically diverse collections and their associations to representations from being incorporated into the construction of a node graph. Example diversity pruning processes that may result in the portion of the node graph400being constructed as shown inFIG. 4are discussed in detail in connection withFIG. 7. For example, the diversity pruning process may remove topically diverse first nodes and their edges or data corresponding to topically diverse first nodes and/or their edges. For example, a diversity score for a collection corresponding to first node403-2may be determined based at least in part on topic scores for representations corresponding to second nodes404-3,404-4,404-5,404-7,404-8and404-9that are connected to the first node403-2. The diversity score for the collection may be indicative of an overall topical diversity of representations that are associated with the collection. If the determined diversity score for the collection does not meet a criterion, then data corresponding to the collection and/or associations with representations is excluded from the construction of the node graph. For example, as part of the diversity pruning process, a collection corresponding to first node403-2may be determined to have a diversity score that does not meet a criterion and thus a collection corresponding to first node403-2and its associations to representations may be excluded from being incorporated into the node graph400. In the present example, first node403-2has been determined to have a diversity score that does not satisfy a diversity score criterion. In the example shown by dotted lines inFIG. 4, the first node403-2and edges406-4,406-5,406-6,406-9,406-10, and406-11are not included in the portion of the node graph400after a pruning process has been applied to the data shown inFIG. 3. In some implementations, collections or associations between collections and associations that are older than a defined age may be determined to not meet the criterion and be excluded from being incorporated into the node graph.

In some implementations, representations may be excluded from being incorporated into a node graph. For example, representations that were created prior to a defined date may be determined to not meet a criterion and may be excluded from being incorporated into a node graph. In one or more implementations, representations that are not associated with any collection are excluded from being incorporated into the node graph400. Such representations that are not associated with any representations that would be of little use in running random walks because there is no node to which to traverse. For example, second nodes404-3,404-7,404-8, and404-9are not included in the node graph400because the corresponding representations have been excluded from being incorporated into the portion of the node graph400. In comparison, second node404-4may remain in the node graph400even though the second node404-4is connected to the first node403-2. In this example, second node404-4is retained because second node404-4is also connected to first node403-1by edge406-3.

In comparison to the portion of the node graph300shown inFIG. 3, the portion of the node graph400may allow for faster and/or more relevant recommendations to be formulated from queries. In addition, the portion of the node graph400may have a reduced memory footprint compared to the portion of the node graph300shown inFIG. 3. For example, and as discussed, random walks through the pruned node graph400will return more relevant recommendations because nodes that do not satisfy a criterion have been removed (pruned).

FIG. 5illustrates a portion of a node graph500generated from data that has been pruned so that certain data is not incorporated into the node graph500. In the example illustrated byFIG. 5, the data from which the portion of the node graph500has been constructed may be an edge pruned version of the data from which the portion of the node graph300ofFIG. 3is constructed. Therefore,FIG. 5may include similar first nodes, second nodes, and edges as those discussed in connection withFIG. 3and, for purposes of brevity the nodes and edges depicted inFIG. 5will not be described in detail with regard toFIG. 5.

Dotted lines indicate an edge that would have been included in the node graph500but for the pruning process. Specifically, edge506-6between first node503-2and second node504-5has been excluded from the node graph500. Edge pruning involves excluding associations between collections and dissimilar representations from being incorporated into the construction of a node graph. Edge pruning involves obtaining a topic score for a collection and obtaining a topic score for a representation associated with the collection. A topical similarity for the collection and the representation may be determined, for example, based at least in part on a cosine similarity between the topic score for the collection and the topic score for the representation. If the determined topic similarity does not meet a criterion, then the association between the representation and the collection is excluded from being incorporated into a node graph. An example edge pruning process that may result in the node graph500is discussed in detail in connection withFIG. 8.

FIG. 6illustrates an example node graph generation process600, according to an implementation. The example process600and each of the other processes described herein are illustrated as a collection of blocks in a logical flow graph. Some of the blocks represent operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the blocks represent computer-executable instructions stored on one or more computer-readable media that, when executed by one or more processors, perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures, and the like that perform particular functions or implement particular abstract data types.

The example process600begins by identifying data, a data set, or a corpus from which a node graph is to be generated, as in604. In some implementations, the data from which a node graph is formed may include a collection data set, such as collection data200discussed in connection withFIG. 2. The data may include representations, collections, associations between the representations and collections, and data related to the collections and representations. In one or more implementations, the data may be a previously constructed node graph.

In some implementations, the example process600is initiated in response to an administrator of a collection management system, such as the collection management system103ofFIG. 1, submitting a request for a node graph to be constructed or updated. Alternatively, in one or more implementations, node graphs are automatically constructed on a periodic basis. For example, a node graph may be automatically generated each day from collection data or a previously constructed node graph in order to provide an updated node graph that incorporates changes made by users to the collection data subsequent to a node graph being constructed from the collection data.

Upon receiving the data (e.g., collection data) for constructing a node graph, the data may be pruned, as in608. Pruning the data may involve excluding collections with high diversity and/or associations between topically dissimilar collections and representations from being incorporated into a node graph that is constructed from the data. Example pruning processes that may be utilized with the disclosed implementations are described in more detail inFIGS. 7 and 8. The pruning processes may result in a pruned data set and/or pruned node graph, where one or more collections, representations, and/or associations between collections and representations are excluded from being incorporated into the node graph.

In some implementations, the data may be pruned by excluding collections, representations, or associations between collections and representations based on their creation date or modification dates. For example, collections, representations, or associations between collections and representations that were created or modified more than a defined time period before a present time may be excluded from being incorporated into a node graph. In some implementations, an association between a collection and a representation that was made greater than a defined amount of time (e.g. two years) may be excluded from a node graph.

A node graph may be generated from the pruned data, as in612. The pruned data is data other than the data that has been determined to be excluded from the node graph. The node graph that is generated from the pruned data may include first nodes that correspond to collections in the pruned data, second nodes that correspond to representations in the pruned data, and edges that correspond to associations between the collections and the representations.

The generated node graph may be stored in a cache, as in616. Storing the node graph in cache may allow for recommendations to be formulated in less time than if the node graph is stored in memory. The node graph generating process600may provide a node graph that is suitable for use in the recommendation environment100ofFIG. 1. Upon completion of the node graph being stored in a cache, the process may complete, as in620. In some implementations, the node graph generating process600may be performed on a periodic basis on collection data in order to generate a node graph that may incorporate changes to collection data (e.g., users adding representations to collections) since a previous node graph was generated.

Referring now toFIG. 7, which illustrates an example diversity pruning process700for pruning a collection data set, according to an implementation. The collection data set may include collection data such as collection data200described in connection withFIG. 2. The collection data set may include representations, collections, associations between the representations and collections, and user-provided textual descriptions for the collections and/or representations.

The example process700begins by determining topic scores for representations in the collection data set, as in708. Topic scores for representations in the collection data set may be previously determined and associated with the representations in the collection data set or determined by processing the representation and/or data associated with the representation to determine amounts of one or more topics to which the representation pertains, as discussed above. Such previously determined topic scores for representations may be maintained by a collection management system. Topic scores for representations may be topic vectors that are determined by applying a LDA topic model to the representations and/or data associated with the representations. For example, topic scores may be based at least in part on descriptions or other information associated with the representations. These descriptions may include textual descriptions that may be provided by human users that may be associated with the representation. The topic scores may indicate amounts of one or more particular topical categories for the representation. For example, a representation depicting a strawberry smoothie may be associated with a description “My favorite fruit breakfast.” A topic score for this representation with respect to the topics of “breakfast” and “fruit” may both be 50%. Topic scores determined for the representations may be maintained as topic vectors, for example, in the collection data, such as the collection data112of the data101ofFIG. 1or the collection data200ofFIG. 2.

At712a diversity score is determined for a collection. The diversity score for the collection may indicate an amount of topical diversity, topical entropy, and/or topical variance of the representations associated with the collection. Diversity scores for a collection may be based at least in part on topic scores of representations that are associated with the representation. For example, diversity scores for a collection may be determined by analyzing and/or comparing topic scores of the representations that are included or associated with the collection for topical diversity. In one or more implementations, diversity scores for each collection is determined by applying a diversity model to topic scores of the representations associated with the collection. The diversity score for a collection may be associated with the collection and maintained by a collection management system.

At716a determination is made as to whether the determined diversity score satisfies a diversity score criterion. For example, the diversity score criterion may be a threshold value that is indicative of a limit on an acceptable amount of diversity for the collection to be incorporated in a node graph that will be used by a recommendation engine to generate recommendations.

If it is determined that a diversity score for the collection does not meet the diversity score criterion, i.e., the topical diversity of the collection is too high, the collection and its associations to representations may be included in a subset of the collection data, as in720. The subset of the collection data is not included in the pruned collection data from which a node graph is generated or constructed. In one or more implementations, the diversity score criterion may be adjusted in order to increase or decrease the amount of collections that are incorporated into a node graph that is constructed from the collection data set.

If it is determined at716that the diversity score for a collection satisfies or meets the diversity score criterion, a determination is made at726as to whether the pruning of the collection data set should continue. For example, it may be determined that the pruning should continue if a diversity score is unknown for a collection in the collection data, one or more known diversity scores for collections in the data set have not yet been checked against the diversity score criterion, or data in the collection data has been modified in a way that may impact diversity score for the collection. For example, if a user modifies a description for a representation included in the collection data set, the topic score for the representation may change and such change may change the diversity score for a collection associated with the representation. In another example, a user adding an association between a collection and a representation may cause a change to a diversity score for the collection.

If it is determined that the pruning process should not continue at decision block726, a node graph may be generated from pruned collection data that excludes the collection data subset, as in728. The pruned collection data set may be, for example, a copy of the collection data set with at least the collection data subset removed. A recommendation engine may use the node graph generated from the pruned collection data to determine recommendations.

Returning to decision block726, if it is determined that the pruning process should continue, the example process700returns to block712where a diversity score for a different collection may be determined. A diversity score for a different collection of the data set may be determined each time the example process700transitions from block726to block712.

Referring now toFIG. 8, which illustrates an example edge pruning process800for pruning a collection data set, according to an implementation. The process800begins by determining a collection data set at804. For example, the collection data set may include representations, collections, associations between the representations and collections, and other data associated with the representations and/or collection, such as user-provided textual descriptions for the collections and/or representations.

A topic score for a representation associated with the collection may be determined, as in808. A topic score for the representation may be determined, for example, by running an LDA topic model on data (e.g. a textual description) associated with the representation. In some implementations, a previously determined topic score for some or all of the representations may be maintained in the collection data set by the collection management system. In such implementations, the topic score is retrieved from the collection data set and may not need to be recalculated. The topic score for the representation may be updated when the representation has recently been associated with the collection or a description associated with the representation has been modified, for example, by a user. For example, a user may change a description for a representation of the Grand Canyon from “I want to visit!” to “Visited on ABC Company retreat in 2017,” after the user has visited the Grand Canyon. Such changes to the description for a representation may cause the topic score for the representation to change.

At block816, a topic score for a collection may be determined. A topic score for the collection may be determined, for example, by taking an average of the topic scores of representations that are associated with the collection. In some implementations, the topic score for the collection may be maintained in the collection data set by a collection management system. In such implementations, the previously determined topic score for the collection may be retrieved if the topic score for the collection has not changed.

A similarity score may be determined between the collection and a representation associated with the collection, as in820. The similarity score may be determined, for example, at least in part on the topic score for the collection and the topic score for the representation. In one or more implementations, the topic score for the collection and the topic scores for the representations associated with the collection may be represented as topic vectors, and the similarity score is determined at least in part by determining the cosine similarity of the topic vector for the collection and the topic vector for the representation. In some implementations, the similarity score is an absolute value of the determined cosine similarity (|E|) with a pruning factor (δ) applied exponentially. In such implementations, the similarity score is |E|δ. The pruning factor δ may be adjusted up or down depending on the amount of pruning that is desired and/or the desired size of the constructed node graph. Other methods of determining a value that represents a topical similarity between the collection and the representation may be utilized.

At block824a determination is made as to whether the similarity score satisfies a similarity score criterion. The similarity score criterion may be a value that is indicative of a limit on an acceptable amount of topical dissimilarity between the collection and the representation for the association between the collection and the representation to be included in a node graph. In some implementations, the similarity score criterion may be adjusted up or down depending on the desired size of the node graph that is ultimately constructed from the collection data.

If it is determined at block824that the similarity score does not meet the similarity score criterion, the association between the collection and the representation corresponding to the determined similarity score may be included in a subset of data that is to be excluded from the generation of a node graph, as in828.

Associations between collections and representations may also be included in the subset of data that is to be excluded from the generation of the node graph based on other factors, such as age of the association. For example, all representations that were added to the collection data prior to a date or time may be determined and all associations to these determined representations may be added to the subset that is to be excluded from the generation of the node graph. In some implementations, associations between collections and representations that were created or last modified at least an amount of time in the past are determined and all the associations are added to a subset to be excluded from the node graph that is constructed. In some implementations, representations that are not associated with any collection are identified and added to the subset of data that is to be excluded from the node graph.

If it is determined at824that the similarity score between a collection and a representation satisfies a similarity score criterion, a decision is made whether to continue with the edge pruning process, as in832. If it is determined at832that the process should continue, the process returns to804where the next collection in the data set is determined and processed. For example, the process800may continue if it is determined that a topic score is unknown or needs to be updated for one or more collections and/or representations in the collection data set. In some implementations, the process800identifies all collections and/or representations in the collection data set with unknown topic scores or topic scores that need to be updated. A topic score for a representation or collection may be determined to need updating if it has been recently updated and a stored topic score for the representation or collection does not reflect the updates. In some implementations, similarity scores between collections and representations may be maintained by a collection management system. In these implementations, the similarity scores do not need to be recalculated if no significant change has occurred to the collection and the associated representation since the similarity score was determined. In these implementations, the similarity score may be retrieved.

If it is determined at block832that the process800should not continue, the process800may generate a node graph that does not include the associations and other data from the collection data that are included in the subset, as in836. In some implementation, the process800should not continue if it determined that all needed similarity scores have been determined. A pruned collection data set may be generated from the collection data set with the subset of data having been removed or excluded. The node graph may be generated from the pruned collection data set that does not include the associations in the subset of associations that are to be excluded from the node graph.

FIG. 9is a graph900that illustrates a relationship between a quality of recommendation results (F1) that may be provided by a recommendation system using a node graph generated from different pruning criteria, as indicated by pruning factor δ. As discussed above, decreasing the pruning factor δ may result in more pruning of a data set and correspondingly fewer edges being included in the node graph. A first axis910indicates an F1 score that is a measure of the quality of recommendations results provided by a recommendation service. A second axis920indicates a relative number of edges (%) of a node graph, and a third axis930indicates a pruning factor δ. A first plot950indicates a relative F1 score, and a second plot960indicates relative number of edges (%). As shown by the plots950and960, pruning may improve the quality of recommendations because the F1 score increases with increased pruning. Pruning data that is used to construct a node graph may improve the quality of the recommendations that may be provided by random walks through the node graph because pruning may identify associations between topically dissimilar collections and representations and prevent such associations from being incorporated into the node graph that is constructed from the data. In other words, pruning enables a node graph to be constructed with greater topical similarity between nodes corresponding to collections and nodes corresponding to representations because associations between dissimilar collections and representations in data are excluded from the node graph that is constructed from the data.

FIG. 10is a graph1000that illustrates a relationship between memory usage and random walk times for different pruning criteria, as indicated by a pruning factor δ. A first axis1010indicates memory usage, a second axis1020indicates a pruning factor δ for the graph, and a third axis1030indicates a time for each random walk (in milliseconds). A first plot1050indicates memory usage, and a second plot1060indicates a time for each random walk. As shown in the graph1000, increasing the pruning factor δ used to determine similarity scores, for example at block824in process800ofFIG. 8, so that an increased amount of connections between topically dissimilar collections and representations are excluded from being incorporated into a node graph that is constructed from the data results in decreased memory usage and reduced random walk times. By decreasing both memory usage and random walk times, the performance of the recommendation system is improved and the computation cost to generate recommendations is decreased.

FIG. 11illustrates an example of a random walk through a portion of a node graph1100. A random walk, as discussed herein, refers to a traversal of the node graph through nodes corresponding to collections and representations. A step, as discussed herein, refers to traversing from a node to another node that are connected by an edge. For example, a random walk having five steps will traverse along five edges to up to five nodes not including the node from which the walk was initiated. For purposes of explanation, a walk through a node graph that is performed with the described implementations, will be described as being performed by a walker that walks through the node graph along edges between nodes. In the example, first nodes1103-1through1103-3correspond to collections. Second nodes1104-1through1104-6correspond to representations. Edges1106-1through1106-10correspond to associations between collections and representations. Paths1111-1through1111-4represent a path of a walk through the node graph.

In some implementations, random walks may have a defined amount of steps or step length. The defined amount of steps may be a constant, or the defined amount of steps may vary depending on each individual random walk and/or for the query node from which the walks originate. In some implementations, the step length of each walk may be selected by a randomizing function. In other implementations, the walk length is not pre-determined. For example, the walk length may be determined during the random walk. For example, at each step a randomizing function may be used to determine whether the walk should terminate or continue. Once a walk terminates it, it may restart. A walk may restart by a new walk being initiated from the same or a different query node from which the terminated walk was initiated. In some implementations, a walk length for an individual walk may be determined prior to each restart.

According to one approach, a walk is performed on the node graph1100where the walker starts walking on a node corresponding to a representation or a collection. The walker walks from a current node to the next node by walking on an edge from a node representing a collection to a node representing a representation. When there are two or more such edges connected to the current node, the walker picks one of these edges for the next step. The walk may be “random” such that the probabilities that the walker will pick a particular edge of a plurality of edges connected to the current node may be substantially equal. In one or more implementations, such as implementations discussed in connection withFIGS. 14 and 16, the probabilities that the walker will pick a particular edge connected to the current node may be weighted or biased such that one edge connected to the current node has a higher probability than another edge connected to the current node. In some implementations, the walker cannot traverse to certain edges, or the probability of a walker traversing to an edge is zero. In one or more implementations, the walker cannot walk to a node that the walker has already visited on the particular walk. In some implementations, the walker cannot traverse to query nodes because query nodes would not be recommended to a user. As the walker steps between nodes in the graph, the visit counts for each node may be tracked in a visit count set, where each visit count in the visit count set corresponds to one of the nodes.

In the example shown inFIG. 11, the walker is on second node1104-1that corresponds to a representation and walks on a path1111-1along edge1106-2to first node1103-1that corresponds to a collection. At first node1103-1, there are four edges1106-1,1106-2,1106-3, and1106-4. Edges1106-2,1106-3, and1106-4connect to second nodes1104-1,1104-2, and1104-3that correspond to representations, respectively. An edge is chosen and the walker walks along the chosen edge in the next step. In this example, the walker follows path1111-2along edge1106-3to second node1104-2that represents a representation. At second node1104-2there are edges1106-5and1106-3. An edge is chosen and the walker walks along the chosen edge in the next step. From second node1104-2that corresponds to a representation the walker follows path1111-3along edge1106-5to first node1103-2that represents a collection. At first node1103-2that represents a collection there are three edges1106-5,1106-6, and1106-7. An edge is chosen and the walker walks along the chosen edge in the next step. At first node1103-2the walker follows path1111-4along edge1106-6to second node1104-4that corresponds to a representation. At second node1104-4there are edges1106-6and1106-8. In the present example, the visit counts of second node1104-1, first node1103-1, second node1104-2, first node1103-2, and second node1104-4are each incremented because the walker visits those nodes during the walk. As discussed, multiple random walks may be executed on the node graph and with each random walk, the visit count may be incremented for each node of the node graph each time a walk visits that node.

At second node1104-4the walk terminates. Individual walks may terminate in various different ways. In one or more implementations, a walk may terminate when a defined amount of steps through the node graph has occurred. In some implementations, an individual walk may terminate when it traverses to a node that is not connected to another node. In other implementations, an individual walk may terminate after a defined amount of steps has occurred through the node graph after the walk is initiated. In some implementations, an amount of steps for each walk is not constant or defined, i.e., it is randomly selected, for example, using a randomizing function. In some implementations, it may be randomly determined whether to terminate or continue the walk. Once a walk terminates, a new walk may restart from the node from which the previously terminated walk was initiated or another node, e.g., a query node.

The running of the plurality of random walks may terminate because certain visit count conditions of one or more nodes of the node graph have been met. In some implementations, the random walks through the node graph may terminate when a defined number of nodes have visit counts or proximity scores that are above a defined amount. For example, the plurality of random walks may terminate when 5% of the nodes have visit counts that are above 10. In some implementations, the visit counts may be used to determine proximity scores, which is indicative of a relevance of corresponding nodes with respect to a query.

FIG. 12illustrates an example early stopping process1200for ending random walks through a node graph, such as the portion of the node graph1100ofFIG. 11, according to an implementation. The node graph may include a first set of nodes that correspond to (or represent) collections, a second set of nodes that correspond to (or represent) representations (e.g., media objects), and a set of edges that correspond to (or represent) associations between nodes in the first set of nodes and nodes in the second set of nodes.

A plurality of random walks may be initiated in the node graph, as in1208. The random walks may be initiated from nodes of a query. The query may be determined, for example, based on a representation or collection being selected by a user or a user viewing the representation or collection. The query may include one or more representations or collections, or one or more nodes in the node graph that correspond to one or more representations or collections. If the query set is made up of one or more nodes, the plurality of random walks may be initiated from the one or more nodes. If the query set is made up of one or more representations and/or collections, the collection management system may identify one or more nodes in the node graph that correspond to the one or more representations in the query set and the random walks may be initiated from the one or more nodes in the query set. Once initiated, the plurality of random walks step through the node graph and visit nodes.

The nodes visited by the plurality of random walks may be tracked and a proximity score set for the nodes may be updated, as in block1212. Each visit to a node by a walk may cause the visit count for the node to be incremented. Once the plurality of walks have terminated, the visit counts indicate the total visits for each node that resulted from the plurality of random walks.

A proximity score for a node may indicate a relevance of the node with respect to the query set. Proximity scores for nodes may be determined, for example, based at least in part on the visit counts for corresponding nodes. In some implementations, the proximity scores are equivalent to visit counts. In other implementations, proximity scores for some or all nodes in the node graph are different from visit counts for other nodes. For example, a node that has been visited by multiple random walks that have originated from different query nodes may have a visit count that is indicative of the total number of visits. In this example, the proximity score for the node that has been visited by random walks originating from multiple different query nodes may be increased to an amount that is greater than the actual visits to that node. Similar implementations are discussed in connection withFIGS. 19 and 20. In some implementations, such as implementations discussed in connection withFIGS. 21 and 22, a proximity score for a node is increased if nodes in a designated “cluster” of nodes is visited by a random walk.

If it is determined at1216that at least a defined amount of nodes have corresponding proximity scores that meet a stopping criterion, the running of the random walks through the node graph may end, as in1224. The stopping criterion may be, for example, a visit count threshold or a proximity score threshold. This ending of the random walks may occur prior to another ending condition, such as completion of a defined amount of walks or an amount of steps, being satisfied. The defined amount of nodes and the stopping criterion may both be constants, or one or both may depend on, for example, one or more of an amount of nodes in the node graph that correspond to representations, an amount of nodes that correspond to collections in the node graph, or an amount of edges in the node graph. In implementations where a representation is to be recommended, the defined amount of nodes may be for a particular type of node. For example, the recommendation system may monitor the proximity score set to determine when at least 5% of nodes that correspond to representations have proximity scores above a particular score, e.g., 25. The recommendation engine may monitor sets of the visit counts and/or sets of proximity scores for the nodes in the node graph, and if it is determined at1216that a defined amount of nodes do not have corresponding proximity scores that meet a criterion, the process returns to1212and continues.

After ending the random walks, a recommendation may be determined based on the proximity scores or visit counts, as in1228. For example, the recommendation may include nodes corresponding to representations with the highest corresponding proximity scores or visit counts. At least a portion of the recommendation may be returned at1232and provided to a client device for presentation. A plurality of representations that correspond to nodes that are included in the recommendation may be provided to a client device. Some or all of these representations may be presented on the user device. Once at least a portion of the recommendation has been returned, the process1200terminates at1236.

Referring now toFIG. 13, which is a graph1300that illustrates a relationship between latency and a minimum number of nodes that are required to reach a stopping criterion of having a visit count that equals four (nv=4) for an early stopping process, such as process1200ofFIG. 12. A first axis1310indicates a relative latency with respect to a full walk that terminates once a defined amount of walks or steps have been performed, and a second axis1320indicates a minimum number of nodes that are required to reach the stopping criterion. As indicated by plot1330, early stopping may reduce the latency in determining a recommendation. Reducing the latency required to perform the plurality of random walks may enable recommendations to be provided more quickly and with fewer computing resources.

Referring now toFIG. 14, which is a graph1400that illustrates a relationship between overlap of results and minimum number of nodes reaching a stopping criterion of a visit count that equals four (nv=4) for an early stopping process, such as process1200ofFIG. 12. A first axis1410indicates an overlap of results with respect to a full walk, and a second axis1420indicates a minimum number of nodes that are required to reach the stopping criterion. As indicated by plot1430, an early stopping process may provide recommendations with a relatively high amount of overlap with respect to recommendations provided by a full walk.

The high amount of overlap indicated by the graph1400suggests that recommendations provided by a random walk process that uses an early stopping process that terminates after a defined amount of walks or steps have been reached may be comparable in quality to the recommendations that are provided by a full walk. Therefore, a random walk process that uses an early stopping process may provide recommendations that are comparable in quality to the recommendations that are provided by a full walk but with reduced computing resources because the random walk process is stopped early.

Referring now toFIG. 15, which illustrates an example of a biased walk through a portion of a node graph1500. First nodes1503-1,1503-2, and1503-3may represent collections and second nodes1504-1through1504-6may represent representations. In one or more implementations, different types of edges may be used to signify different edge properties or characteristics. First edges1506-1through1506-8represent connections between collections and representations having a first characteristic. Second edges1507-1,1507-2, and1507-3represent connections between collections and representations having a second characteristic. A characteristic of an edge may be determined, for example, by analyzing a description associated with a collection and/or a representation that corresponds to a node that is connected to the edge. The first characteristic may be a first language, e.g., Spanish, English, or French, of a node connected to the edge. The second characteristic may be a different language, for example. In this example, the walker only traverses edges with a particular characteristic. Various different types of characteristics may be utilized and indicated by the edges and/or data associated with the edges. In one or more implementations, edges may indicate or be associated with data that indicates one or more characteristics of a human user associated with a collection and/or a representation that is connected to each edge. For example, edges may indicate a gender, an age, a marital status, or an education level of a human user that is associated with a collection and/or a representation that is connected to the edge. In some implementations, the edge may indicate or be associated with data that indicates a domain or electronic address of a source of a representation that is connected to the edge. For example, an edge may indicate or be associated with data that indicates that a source of a representation connected to the edge is an electronic commerce web-site, in general, or a particular web-site.

Paths1511-1through1511-4represent a traversal route taken by the walker through the portion of the node graph1500. In this example, a walker starts on second node1504-1and walks to first node1503-1along path1511-1corresponding to edge1506-2. At first node1503-1there are four edges, i.e., first edges1506-1,1506-2,1506-3, and1506-4. An edge is chosen and the walker walks along the chosen edge in the next step. In this example, the walker follows path1511-2along first edge1506-3to second node1504-2. At second node1504-2there are three edges, i.e., first edges1506-3and1506-5, and one second edge1507-1. In this example, the walker may only step along a first edge because it is desirable to generate recommendations that have the first characteristic. The walker may not step along a second edge1507-1because the second edge does not have the first characteristic. Thus, in this example the walker may not step to second edge1507-1. In some implementations, a first edge is preferred over a second edge. In such implementations, the walker may traverse along a second edge if no first edge is available to traverse. At second node1504-2, an edge is chosen and the walker walks along the chosen edge in the next step. In this example, the walker follows path1511-3along edge1506-5to first node1503-3. At first node1503-3there are four potential edges for the walker to select, i.e., first edges1506-5,1506-6,1506-7, and1506-8. An edge is chosen and the walker walks along the chosen edge in the next step. In this example, the walker follows path1511-4along edge1506-6to second node1504-4, which is connected to first edge1506-6and second edge1507-2. In this example, the walker cannot traverse to a node that has already been traversed to by the current walk or step to a second edge. It may be desirable to restrict a walker from traversing to a node that has already been traversed to by the current walk because it could result in nodes that are not connected to many other nodes having increased visit counts from a random walk repeatedly traversing back and forth between several nodes. Likewise, as discussed above, in this example the walker cannot traverse along a second edge1507-2. As a result, there is no edge to which the walker may traverse and the walk terminates at node1504-4.

Referring now toFIG. 16, which illustrates an example biased walk process1600for performing random walks through a node graph, such as the portion of the node graph1500ofFIG. 15. A biased walk process may give preference to traversing along certain edges in the node graph and/or restrict the walker from traversing along particular edges. For example, a node graph may include nodes with a large variety of languages, and it is desirable to recommend content that is not only relevant but is also in the user's preferred local language, such as English. In such an example, the walk through the node graph will be biased toward nodes or edges that relate to the preferred local language (e.g., English).

The example process1600begins by a characteristic being identified, as in1606. In some implementations, the characteristic may be a country, a geographic location, or a language, etc. In one or more implementations, the characteristic may be an age or age range, a gender, an education level, an income level, a marital status, and/or an age of a user for which a recommendation is to be provided. The characteristic may be determined based on user inputs, or preferences, or data associated with a user. For example, if it is determined that a user is using a Japanese language browser or is associated with an Internet Protocol (IP) address for Japan, the characteristic may be determined to be Japanese language and/or Japanese geographic location. In some implementations, the characteristic is identified to be supplemental information (e.g., advertisements) because it is desired to provide advertisements as recommendations. In some implementations, the characteristic may be context, certain topic scores, or certain constraints. For example, the identified characteristic may be representations without restrictions on modification. In some implementations, the characteristic may be an age of a representation, an amount of associations for the representation, and/or a date that a representation was associated with a collection. In one or more implementations, two or more different characteristics are identified. In one example, Japanese language and merchant web-sites may be identified as characteristics in1606. In another example, the Japan geographic region and males age 25 and 38 may be identified as characteristics. Various characteristics from the collection data may be identified, such as those included in the collection data200ofFIG. 2.

A subset of edges in the node graph may be identified that are associated with the identified characteristic(s), as in1608. In one or more implementations, a collection data set corresponding to the node graph may be analyzed to identify collections and/or representations that have the identified characteristic. For example, the identified characteristic may be Japan. Each representation in a set of collection data may be associated with a geographic region. Second nodes corresponding to representations with the identified characteristic (Japan) may be identified and edges connected to the representations having the identified characteristic may be included in a subset of edges. In one or more implementations, each collection in a set of collection data may be associated with a geographic region, first nodes corresponding to collections having the identified characteristic (Japan) may be identified and edges connected to the collections having the identified characteristic may be included in the subset of edges. In some implementations, only edges that connect first nodes that correspond to collections that have the identified characteristic and second nodes that correspond to representations that have the identified characteristic are included in the subset of edges.

In some implementations, content of representations in the collection data set or data associated with representations in the collection data set may be processed to identify representations that have the identified characteristic. For example, descriptions associated with representations may be analyzed to determine a language of the description to determine a geographic region for a representation or collection. In another example, a geographic region for a representation may be determined by analyzing a language or an IP address of a website associated with the representation. If it is determined that one or both of a collection and an associated representation have the characteristic, then the edge that connects the collection and the representation is included in the subset of edges. The edges in the subset may be modified to indicate that they have or do not have the characteristic.

A plurality of random walks may be initiated from query nodes, as in1610. Each walk traverses to nodes that are associated with the characteristic, as in1614. The random walks may only traverse along edges that are included in the subset of edges. In such implementations, if an edge in the node graph is not included in the subset of edges, then the plurality of random walks cannot traverse along that edge. For example, if the identified characteristic is a first geographic location, the random walk traverses or walks only to nodes that are associated with the first geographic location by only traversing edges that are included in the subset. In some implementations, random walks favor traversing along edges in the subset of edges. For example, a random walk may be two times as likely to traverse along an edge in the subset of edges as an edge that is not included in the subset set of edges. In some implementations, a random walk will terminate and/or restart if there is no node associated with the characteristic available to which to traverse. Visit counts for nodes visited by random walks may be tracked, as in1618. In some implementations, a proximity score may be determined based on the tracked visit counts for the nodes.

In one or more implementations, the early stopping process discussed in connection withFIGS. 12 and 13may be used to terminate the plurality of random walks through the node graph. For example, if at block1622, it is determined that a defined amount of the visit counts satisfy a criterion, the random walks end, as in1626. For example, the defined amount may be based on a percentage of the nodes, collections, representations, etc. The defined amount may be modified because the walks are restricted to fewer nodes. If at block1622it is determined that the defined amount of visit counts do not satisfy the criterion, the process1600returns to block1610, and continues.

The random walks may end in other ways. In some implementations, the plurality of random walks may terminate once an amount of random walks through the node graph have been performed or an amount of steps have been performed by random walks through the node graph. After terminating the random walks, a recommendation may be returned, as in1630. The recommendation may be returned by being sent to a client device. The recommendation may be determined based on visit counts or proximity scores. For example, the recommendation may include representations or collections corresponding to the nodes in the node graph with the highest proximity scores or highest visit counts. Once the recommendation is returned, the process1600may complete, as in1634.

Referring now toFIG. 17, which illustrates an example of performing random walks through a portion of a node graph1700according to a weights on queries approach that may be utilized with a query set that includes more than one query node. A weights on queries approach involves placing different levels of importance on different query nodes in the query set in order for particular query nodes to have different levels of influence on the recommendations that are ultimately provided.

First nodes1703-1,1703-2, and1703-3represent collections. Second nodes1704-1through1704-5represent representations. Edges1706-1through1706-9represent associations between collections and representations. First paths1711-1and1711-2represent paths through the portion of the node graph1700by a first random walk. Second paths1712-1through1712-4represent paths through the portion of the node graph1700by a second random walk.

In this example, a query includes first node1703-3and second node1704-1because a user has selected or otherwise indicated a collection corresponding to the first node1703-3and a representation corresponding to the second node1704-1. Weights that are indicative of relative levels of importance may be determined for the first node1703-3and the second node1704-1. These weights for nodes in a query set (also referred to herein as “query nodes”) may indicate an amount of influence that walks initiated from the query node will have on the visit count, proximity scores, and/or recommendations that are ultimately provided. Weights for the query nodes may be determined by various data, such as creation dates that indicate a date that a corresponding collection was created or a date a representation was added to a collection data set, modification date indicating a date that a representation was associated with collection, number of edges connected to a query node, amount of times that a corresponding representation has been added to a collection in a given time period, etc. In this example, relatively more weight is allocated to first node1703-3with respect to second node1704-1. In one or more implementations, greater weight may be allocated to query nodes that have been selected more recently by the user because more recently selected query nodes may better indicate the user's current interests compared to older query nodes. In some implementations, greater weight may be allocated to query nodes that have been more recently created or updated because their content is fresher and may be associated with content that has not previously been presented to the user. In one or more implementations, greater weight may be allocated to query nodes that are connected to more edges because such nodes may provide more paths for random walks to traverse. In some implementations, it may be desirable for greater weight to be allocated to query nodes that have historically had low interaction because such nodes are more likely to be connected to nodes that correspond to content that is new and/or rare. A function may be used to inversely weigh query nodes in a query based on amounts of historical interaction. Low interaction may be indicated by the number of connections (i.e. edges) to a node, i.e., lower amounts of connections indicates a lower level of interaction. Low amounts of interaction may be indicated by tracking an amount of user views of content corresponding to a node. High interaction may be indicated by the number of connections (i.e. edges) to a node, i.e., higher amounts of connections indicates a higher level of interaction. Like low amounts of interaction, high amounts of interaction may be indicated by tracking an amount of user views of content corresponding to a node.

Different weights may be implemented in various ways. In some implementations, walk lengths (max amount of steps/walk) may be assigned to each node. More weight may be allocated to a query node by allocating longer walk lengths to the query node. Less weight may be allocated to a query node by allocating shorter walk lengths to the query node. Initiating random walks with longer walk lengths from a query node results in nodes around the query node getting more visits. In some implementations, different weights may be implemented by assigning different amounts of walks to query nodes. For example, a first query node that is desired to have a greater weight may be assigned twice the number of walks as a second query node that is desired to have a lesser weight. In this example, two random walks are initiated from the first query node1703-3for every one random walk that is initiated from the second query node1704-1. The query node from which more walks are initiated may have more influence on the recommendation that is ultimately provided because nodes around that query node get more visits and, thus, have higher visit counts and/or proximity scores.

Still referring toFIG. 17, in this example, first node1703-3, which in this example is a query node, has been assigned a walk length of up to two steps and second node1704-1, which in this example is also a query node has been assigned a walk length of up to four steps because it has been determined that first node1703-3should have less influence on the recommendation that is ultimately formulated than the second node1704-1.

In this example, a first random walk is initiated from second node1704-1. At second node1704-1there are two edges, i.e.,1706-1and1706-2. An edge is chosen and the walker walks along the chosen edge in the next step. In this example, the walker follows path1711-1along edge1706-2to first node1703-1and the visit count for the first node1703-1is increased accordingly. At first node1703-1there are three edges, i.e.,1706-2,1706-3, and1706-4. An edge is chosen and the walker walks along the chosen edge in the next step. In this example, the walker follows first path1711-2along edge1706-3to second node1704-2and the visit count for the second node1704-2is incremented accordingly. The first random walk terminates at the second node1704-2because the walk length (max amount of steps/walk) for the first walk, i.e., 2 steps, has been reached.

A second random walk is initiated from first node1703-3. Because the random walk is starting at first node1703-3, the max amount of steps for the walk is four. At first node1703-3there are three edges available, i.e.,1706-7,1706-8, and1706-9. An edge is chosen and the walker walks along the chosen edge in the next step. In this example, the walker follows path1712-1along edge1706-8to second node1704-5, and the visit count for the second node1704-5is incremented accordingly. At second node1704-5there are two edges, i.e.,1706-8and1706-6. An edge is chosen and the walker walks along the chosen edge in the next step. In this example, the walker follows path1712-2along edge1706-6to first node1703-2and the visit count for the first node1703-2is incremented accordingly. From1703-2, the walker follows path1712-3along edge1706-5to second node1704-3and the visit count for the second node1704-3is incremented accordingly. Next, the walker follows path1712-4along edge1706-4to first node1703-1. The second random walk terminates at the first node1703-1because the walk length (max amount of steps/walk) for the second random walk, i.e. 4 steps, has been reached. This process of random walks from the query node(s) may continue and visit counts for visited nodes incremented until one or more criterion are satisfied.

FIG. 18illustrates an example weight on queries process1800for performing random walks through a provided node graph, such as the portion of the node graph1700ofFIG. 17, according to an implementation. The provided node graph may include first nodes that represent collections, second nodes that correspond to representations (e.g., media objects), and a set of edges that represent associations between collections corresponding to first nodes and representations that correspond to second nodes.

The process1800may begin by weights for query nodes being determined, as in1808. The weights between respective query nodes may be unequal. As discussed above with respect toFIG. 17, weights for query nodes may be determined based on a relative creation date, modification date, number of nodes connected to the node coupled to the query, etc. For example, it may be desirable for nodes in the query set that have been created, added, or modified within a defined date or time to be given more weight because such nodes may be more likely to correspond to “fresher” content that has not yet been presented to the user. In addition, it may be desirable to add more weight to query nodes with relatively more connections because such query nodes may have more potential paths for random walks to visit. In some implementations, greater weight may be assigned to query nodes that are connected to relatively newer collections because such collections may be fresher and random walks around such nodes are more likely to lead to recommendations of content that has not yet been presented to the user.

Weights for query nodes may be implemented in multiple different ways. For example, weights may be implemented by allocating an unequal number of random walks from different query nodes. For example, if a query includes node1 and node2, x walks may be initiated from node1 and y walks may be initiated from node2. The query node with the higher number of walks is given greater weight because the query node allocated the higher number of walks may have a greater impact on the recommendation that is ultimately formulated. In some implementations, a substantially equal amount of random walks may be initiated from query nodes but they may be weighted by allocating different amounts of steps for random walks that are initiated from each query node. The walk length (max amount of steps/walk) for a walk from a query node is proportional to its weight on the recommendation because a greater amount of steps from a particular query node will likely lead to nodes around the query node getting more visits by the random walks. The amount of walks and/or steps assigned to each query node may be determined based on, for example, an age of the collection or representation corresponding to the query node, creation date of a collection or a representation corresponding to the query node, an amount of edges that are connected to the query node, etc.

In some implementations, a number of steps (N) may be distributed among query nodes according to a formula that takes into account a degree of the query node. The number of steps required to obtain meaningful visit counts may depend on the query node's degree, i.e., the amount of edges that are connected to the query node. For example, recommending from a “popular” second node that is connected to many first nodes may require a higher number of steps than a first node with a relatively smaller degree (less connections). Hence, it may be desirable to scale the number of steps allocated to each query node in proportion to its degree. In one or more implementations, the number of steps is assigned in linear proportion to the degree. For example, a first query node with a degree of four may be allocated twice as many steps as a second query node that has a degree of two. However, if the number of steps is assigned in linear proportion to the degree, some query nodes with low degrees may not be allocated any steps. In one or more implementations, the number of steps is allocated to query nodes based on a function that increases sub-linearly with the node degree and scales the per node weights by a scaling factor (sq). For example, following scaling factor sqfor each second node may be determined using the following equation.
sq=|E(q)|*(C−log |E(q)|)
Where sq is the scaling factor for a query node q, E(q) is the degree of the query node (q), and C is a maximum node degree. The number of steps may be allocated to a query node as follows:

Where Nq is the total number of steps assigned to the random walks that start from query node q.

In one or more implementations, a first amount of nodes that are associated with a first query node in query subset and a second amount of nodes that are associated with a second query node in a query subset may be determined. A first walk length may be determined for walks initiated from the first query node and based at least in part on the first amount, and a second walk length may be determined for walks initiated from the second query node and based at least in part on the second amount. For example, the first walk length may be proportional to the first amount, and the second walk length may be proportional to the second amount. Random walks initiated from the first query node may traverse no more nodes than the first walk length, and random walks initiated from the second query node may traverse no more nodes than the second walk length.

A plurality of random walks may be initiated from query nodes, as in1816. The plurality of random walks may be in accordance with the determined weights. For example, if query nodes are weighted by step count, the random walks may be performed from the query nodes, or more walks may be performed that are initiated from one query node compared to another.

The nodes in the node graph that are visited by the random walks may be tracked as visit counts for those nodes, as in1820. For example, visit counts for visited nodes may be tracked by a recommendation system. The visited nodes may be tracked by incrementing the visit count for the node. In one or more implementations, the visit counts may be used to determine a corresponding proximity score for each node, the proximity scores indicating a relevance of nodes in the node graph to the query.

A recommendation indicating one or more nodes may be returned, as in1824. The recommendation may be determined based on the visit counts or proximity scores. In one or more implementations, the recommendation is determined after the random walks are completed. The random walks may complete, for example, if a stopping condition is met. For example, the early stopping method discussed in connection withFIG. 12may be used to determine to end the random walks. Once the random walks have completed, the recommendation may be determined and include nodes with the highest proximity scores. Once the recommendation has been returned, the process1800completes as in1828.

Now referring toFIG. 19, which illustrates an example plurality of random walks through a portion of a node graph1900that use a multi-hit booster implementation to increase a proximity score of nodes that have been visited by random walks originating from multiple query nodes. Nodes that have been visited by random walks originating from multiple query nodes may be more relevant to a query than nodes that have only been visited by walks originating from a single query node.

As shown inFIG. 19, first nodes1903-1through1903-3may correspond to collections in a collection data set. Second nodes1904-1through1904-6may correspond to representations in a collection data set. Edges1906-1through1906-10represent associations between collections and representations in the collection data set. Paths1911-1and1911-2represent a path of a walker on a first walk through the node graph1900. Paths1912-1and1912-2represent a path of a walker on a second walk through the node graph1900.

In this example, a query includes second nodes1904-1and1904-4. The query set may be determined based at least in part on a user expressing interest in representations corresponding to second nodes1904-1and1904-4. A first random walk is initiated from second node1904-1. First node1903-1and second node1904-2are visited by the first random walk. A second random walk is initiated from second node1904-4. First node1903-2and second node1904-2are visited by the second random walk.

In this example, a visit count for second node1904-2may indicate a visit by the first random walk and a visit by the second random walk. For example, the visit count for the second node1904-2may be two, and the visit count for first nodes1903-1and1903-2may be one. In some implementations, the visit count for second node1904-2may be further incremented or increased beyond the two visits combined from the first random walk and the second random walk because both the first random walk and the second random walk visited the second node1904-2. In other implementations, visit counts for nodes may be used to determine proximity scores for nodes. For example, the proximity score for the second node1904-2may be a sum of the total visits and a number of random walks from different query nodes. In the present example, the proximity score for the second node1904-2may be four because the second node1904-2was visited by walks that originated from two different query nodes. Similarly, the proximity score for the first nodes1903-1and1903-2may be two because these nodes were each visited by one walk from one query node. As discussed in more detail with respect toFIG. 20, various formulas may be utilized to increase the visit count or proximity score for nodes visited by random walks originating from multiple query nodes.

FIG. 20illustrates an example multi-hit booster process2000for formulating content recommendations, according to an implementation. The example process2000may be utilized in situations where random walks are initiated from multiple different query nodes. The process2000begins by a plurality of random walks being initiated from a plurality of query nodes, as in2004. In one or more implementations, the random walks may have different walk lengths (maximum amount of steps/walk) and/or different amounts of walks may be allocated to different query nodes. The random walks may proceed until a stopping condition has been met. For example, aspects of an early stopping process1200discussed in connection withFIGS. 11 and 12may be incorporated into process2000.

Visit counts may be determined by tracking nodes in the node graph that have been visited by the plurality of random walks and the query node from which the visit was initiated, as in2008. As the random walks traverse the node graph, a recommendation service may track the nodes visited by the random walk and increment their visit counts accordingly.

Nodes in the node graph that have been visited by random walks initiated from different query nodes may be identified, as in2012. Nodes visited by random walks initiated from different query nodes may be more relevant to a query than nodes with an equivalent amount of visits initiated from walks from a single query node. For example, if there are two query nodes and random walks from those query nodes each cross through the same node, that node will be considered more relevant to the query than nodes crossed by random walks from only one of the query nodes. In some implementations, nodes that have been visited by random walks that have been initiated from different query nodes may be identified while random walks traverse the node graph. In some implementations, such nodes are identified after the random walks have terminated. It may be desirable to identify such nodes while random walks are being performed if an early stopping process is used to terminate the running of the random walks through the node graph, and the early stopping process relies on a real-time visit count and/or proximity score to determine whether a stopping condition is satisfied.

In some implementations, proximity scores for nodes in the node graph may be determined based on visit counts for nodes in the node graph and based on the amount of visits to the node by walks initiated from different query nodes, as in 2016. Nodes that are visited by walks initiated from two different query nodes may be more relevant than nodes that have been visited only by one or more walks initiated from a single query node. In one or more implementations, a proximity score function may be applied that provides an increased proximity score for nodes that are visited by walks initiated from different query nodes. In some implementations, a proximity score function may be applied that provides a decreased proximity score for nodes that are visited only by walks initiated from a single query node. For example a proximity score may be determined by taking a sum of a square root of a corresponding visit count and then applying an exponential function, e.g., base two. In one or more implementations, proximity scores for nodes may be determined based on the equation following:

v⁡[p]=(∑q∈Q⁢Vq⁡[p])2
In the above equation, V[p] is a proximity score for a node p, q is a query node, vq[p] is a visit count for the node, and Q is a set of query nodes. If a node in the node graph is visited by walks from only a single query node, then the proximity score V[p] for the node p may be the visit count vq[p] for the node p. Other formulas or methods may be used to determine proximity scores in a way that gives higher proximity scores to nodes that have been visited by random walks that have been initiated from different query nodes. For example, nodes that have only been visited by walks from a single node may be identified and a proximity score may be calculated for these nodes that is lower than the visit count for the node. In this example, proximity scores for nodes that have been visited by random walks from multiple query nodes may be equal to the visit count for the node. Proximity scores and visit counts for nodes in the node graph may be maintained in real-time by a collection management system as random walks traverse through the node graph.

After completion of the random walks, a recommendation may be output, as in2020. The recommendation may be determined based at least in part on an identification of nodes with the highest corresponding proximity scores or highest visit counts. Depending on the query, a recommendation may include only nodes that correspond to collections or only nodes that correspond to representations. For example, if the query includes only nodes that correspond to collections, then a recommendation may be limited to nodes that correspond to collections. The recommendation may be sent for presentation on a user device. Upon completion of the recommendation being output at2020, the process2000may complete, as in2024.

FIG. 21illustrates an example of a random walk through a portion of a node graph2100where proximity scores or visit counts for nodes in the node graph may be determined using a clustering process, according to an implementation. The clustering process may involve increasing a visit count or proximity score for one or more “target nodes” of the node graph2100for each visit to another node that is included in a “cluster” or a designated subset of nodes of the node graph2100. The clustering process may improve the likelihood that particular content corresponding to the target node will be recommended from the random walk process.

The node graph2100may be a model of at least a portion of a collection data set. The portion of the node graph2100includes first nodes2103-1through2103-3that represent collections of a collection data set and second nodes2104-1through2104-3that correspond to representations of the collection data set. The portion of the node graph2100also includes edges2106-1through2106-7that represent associations in the collection data set between collections corresponding to the first nodes and representations corresponding to the second nodes2104-1through2104-3. Paths2111-1through2111-3represent a route taken by a walker on a random walk through the portion of the node graph2100.

In this example, target node2105corresponds to a representation in the collection data set. In this example, cluster2115includes second nodes2104-2and2104-3. In other implementations, a target node may correspond to a collection, or may include multiple nodes that correspond to collections and representations. In one or more implementations, the cluster2115may include first nodes corresponding to collections.

A target node and a cluster may be selected or determined based on a variety of considerations. For example, the target node may be a representation that is an advertisement or content for which a provider of a recommendation service is paid a fee for each presentation of the representation to a user. The clustering process may increase the visit count for the target node or determine a proximity score using a method that favors the target node in order to increase the likelihood that content corresponding to the target node will be included in recommendations that are provided to the user. As another example, the clustering process may increase the likelihood that a target node will be returned as part of a recommendation with other nodes of the cluster. In some implementations, more than one target node may be selected, e.g., a subset of nodes (e.g., 0.1% or 5%) in the graph may be target nodes. For example, if it is desired to recommend advertisements, multiple nodes of a node graph that correspond to advertisements may be target nodes. Similarly, if it is desired to recommend content that is new, multiple newer nodes of the node graph may be specified as target nodes. Other characteristics, such as topic score, context, constraints, source, type of object, amount of views, description, etc., may be used to determine target nodes.

In some implementations, the nodes included in the cluster may be determined based on proximity or degrees to the target node. For example, each node that is connected by a defined amount of edges may be included in the cluster. In some implementations, the cluster may be independent of proximity to a target node. In some implementations, the cluster may be based at least in part on popularity. For example, nodes corresponding to the most popular content as indicated by user view may be included in the cluster. In some implementations, the cluster may be based on similar keyword pairs or topic scores with respect to the one or more target nodes. In some implementations, the cluster may be determined based on comparing URLs associated with content in the collection data set with a URL associated with the target node to identify nodes with URLs similar to the target node. Nodes corresponding to content associated with similar URLs may be included in the cluster. In some implementations where the nodes correspond to images, the cluster may be determined to be those nodes that correspond to images that are visually similar to a target node. Such determination may be made via image processing. Nodes may also be included in multiple different clusters and, in some implementations, multiple target nodes may be selected, each target node having a corresponding cluster.

In this example illustrated inFIG. 21, a random walk may be initiated from first node2103-1. At first node2103-1there are three edges, i.e., edges2106-1,2106-2, and2106-3. In this example, the walker follows path2111-1along edge2106-3to second node2104-2. From the second node2104-2, the walker follows path2111-2to first node2103-2and then follows path2111-3to second node2104-3where the walk terminates. In this example, a visit count for the target node2105may be incremented for each visit to nodes included in the cluster2115. Accordingly, the visit count for the target node2105for the random walk is two. In implementations, visit counts indicate only actual visits by the random walks to the node. In such implementations, one or more proximity scores corresponding to the target node may be incremented for visits to the cluster.

FIG. 22illustrates an example clustering process2200for identifying a recommendation for a query set, according to an implementation. The example clustering process2200may begin by determining a target node of the node graph and a cluster subset of the node graph for the target node, as in2204. Target nodes may correspond to representations that are to be promoted or given more weight. Target nodes may be determined, for example, based on one or more properties or characteristics as indicated in the collection data or by analyzing their content, e.g., processing a representation or description. For example, target nodes may be nodes that are trending, e.g., added to many collections, advertisements, and/or are old, new, have certain topic scores, etc. In some implementations, a target node may be a node from a particular source, such as an advertiser that desires to promote a particular representation. For example, a target node may be determined by analyzing the collection data for advertisements that have at least a defined age and that have at least a defined amount of associations with collections.

As discussed above with respect toFIG. 22, a cluster for the target node may be determined by degree and/or other factors. For example, the cluster may include all second nodes that are within two degrees of the target node. In one or more implementations, the cluster subset for a target node may include all second nodes in collections that include the target node. In other implementations, the cluster subset is determined by identifying second nodes that are associated with similar URLs or descriptions as the target node. In some implementations involving images, a cluster may be determined to be a set of nodes that are visually similar to a target node. Likewise, nodes in the cluster may be determined based at least in part on one or more of the nodes including a similar object or being associated with a particular language or geographic location of the target node. In some implementations, the cluster may be determined based on user characteristics. For example, if a target node is associated with married females aged 50-60, the cluster may include nodes that are associated with such users.

A plurality of random walks in the node graph may be initiated, as in2208. In one or more implementations, walks may be initiated from different query nodes. For example, some walks may be initiated from a first query node, and other walks may be initiated from a second query node. As discussed in detail in connection withFIGS. 17 and 18, the query nodes may be given different weights.

The number of times a node is visited by the plurality of random walks may be tracked as a visit count for the node, as in2212. In one or more implementations, proximity scores for each visited node may be derived based on the respective visit counts. The proximity scores may indicate a relevance of the visited nodes with respect to the query.

If it is determined at2216that a random walk has visited a node that is included in the cluster subset, in2224a visit count or proximity score corresponding to the target node is increased an amount corresponding to a visit, e.g., by one. If it is determined that a node of the cluster subset has not been visited by a random walk, the process2200proceeds to2212and the process continues.

If it is determined at2228that the random walks should not continue, a recommendation may be determined and output, as in2230. In one or more implementations, the random walks should not continue if an end condition has been met, e.g., a defined number of walks through the node graph has occurred, or early stopping, as discussed in connection withFIG. 12, has occurred. If it is determined at2228that the random walks should continue, the process2200returns to2212where the nodes visited by random walks are tracked.

The recommendation may be determined based on visit counts or proximity scores. For example, the recommendation may be determined as discussed in connection withFIG. 12. In implementations where proximity scores are based on the visit counts, the recommendation may be determined from the proximity scores. For example, the recommendation may include the nodes with the highest proximity scores. The recommendation set may be output to a user device for presentations. Once the recommendation set2230has been output, the process may complete as in2234.

As will be appreciated, one or more of the above implementations may be used alone or in combination to determine recommendations in response to a query. Likewise, by representing a data set as a node graph, pruning the node graph, and walking the graph to determine recommendations, the accuracy of returned recommendations is improved because potentially non-relevant nodes are removed (pruned). Likewise, because the node graph is reduced, the time and computation cost to determine the recommendations is decreased, thereby providing a technological improvement over existing systems.

While the above examples describe generating a node graph from a data set and then pruning the node graph, in other implementations, the data set may be pruned and then the node graph may be generated.

The concepts disclosed herein may be applied within a number of different devices and computer systems, including, for example, general-purpose computing systems, and distributed computing environments.