SEQUENTIAL ITEM RETRIEVAL USING CO-ACTON GRAPHSBACKGROUNDListing platforms, such as e-commerce websites, are online platforms that offer products, services, digital content (e.g., music, videos, etc. ) , or other items to users. Such platforms typically offer a vast number of items. While some items are relevant to any given user, the majority is not. As a result, item retrieval for listing platforms is a particular Internet-centric problem that has proven to be difficult to fully address. That is, given a large number of items available on a listing platform, what items should be retrieved and presented to a user and in what order.
Given the vast number of items available, listing platforms include functionality, such as search and recommendation, to assist users in finding items of interest on the platforms. For instance, listing platforms often provide search capabilities that receive user queries and return search results identifying items relevant to the user queries. Listing platforms also often leverage recommendation systems to recommend items that are likely of interest to users based on a variety of information, such as an item currently being viewed by a user, user attributes, and user behavior on the listing platforms (e.g., previous item views, purchases, etc. ) .
SUMMARYSome aspects of the present technology relate to, among other things, performing item retrieval on a listing platform using a two tower machine learning model that leverages sequential user behavior information and co-action items. The model includes an item tower for generating item representation embeddings for items on a listing platform. To generate an item representation for a target item, the item tower generates an item embedding for the target item and item embeddings for co-action items for the target item. Each co-action item comprises an item in which a same user has performed a same action (e.g., click, purchase, etc. ) for both the target item and the co-action item. An attention mechanism is employed to provide an aggregated co-action embedding for the co-action items, and the item representation embedding for the target item is generated by combining the aggregated co-action embedding and the target item embedding.
The model also includes a user tower for generating item interest embeddings for users. An item interest embedding for a user represents a user interest exhibited based on sequential behavior information for the user –i.e., a sequence of interactions with items by the user. The user tower generates an item embedding for each item with which the user has interacted and constructs a graph with the item embeddings as nodes and edges with edge embeddings generated based on pair-wise relationship information between nodes. A graph neural network (GNN) generates enhanced node embeddings from the nodes using the graph, and one or more item interest embeddings are generated for the user based on the enhanced node embeddings.
Given an item interest embedding for a user, item retrieval can be performed for a listing platform by determining similarity measures (e.g., cosine similarity) between the item interest embedding and item representation embeddings for items on the listing platform, and providing an indication of items for presentation to the user based on the similarity measures.
This summary is provided to introduce a selection of concepts in a simplified form that are further described below in the Detailed Description. This summary is not intended to identify key features or essential features of the claimed subject matter, nor is it intended to be used as an aid in determining the scope of the claimed subject matter.
BRIEF DESCRIPTION OF THE DRAWINGSThe present technology is described in detail below with reference to the attached drawing figures, wherein:
FIG. 1 is a block diagram illustrating an exemplary system in accordance with some implementations of the present disclosure;
FIG. 2 is a block diagram showing an example model architecture including a user tower and item tower in accordance with some implementations of the present disclosure;
FIG. 3 is a block diagram showing an example coaction aggregation module of an item tower that generates an item representation embedding for a target item in accordance with some implementations of the present disclosure;
FIG. 4A is an edge matrix showing edge relationships between nodes for graph construction in accordance with some implementations of the present disclosure;
FIG. 4B is a block diagram showing an example generation of an edge embedding by a graph construction module of a user tower in accordance with some implementations of the present disclosure;
FIG. 5 is a block diagram showing an example explicit interaction module of a user tower that generates enhanced node embeddings in accordance with some implementations of the present disclosure;
FIG. 6 is a diagram showing an example set of user actions and three example sets of item recommendations selected based on item interests of the user determined based on the example set of user actions in accordance with some implementations of the present disclosure;
FIG. 7 is a flow diagram showing a method for generating an item representation embedding for an item in accordance with some implementations of the present disclosure;
FIG. 8 is a flow diagram showing a method for generating one or more item interest embeddings for a user in accordance with some implementations of the present disclosure;
FIG. 9 is a flow diagram showing a method for training a model in accordance with some implementations of the present disclosure;
FIG. 10 is a flow diagram showing a method for performing item retrieval in accordance with some implementations of the present disclosure; and
FIG. 11 is a block diagram of an exemplary computing environment suitable for use in implementations of the present disclosure.
DETAILED DESCRIPTIONOverview
While item retrieval systems are useful tools for locating items on listing platforms, shortcomings in existing search and recommendation technologies used by conventional item retrieval systems often result in the consumption of an unnecessary quantity of computing resources (e.g., I/O costs, network packet generation costs, throughput, memory consumption, etc. ) . For instance, item retrieval systems often leverage behavior data of users to attempt to provide items relevant to each user. However, sparsity is a common phenomenon in behavioral data of item retrieval systems. Due to this sparsity, item retrieval systems often lack sufficient collaborative filtering signals to accurately calculate the relevance between a given user and an item. As a result, existing search and recommendation technologies on listing platforms can fail to efficiently return items of interest to users. In the context of search, this causes users to submit multiple queries before finding desired item listings. For example, a user may issue a first query to a search engine of a listing platform that returns a set of search results. The user may browse the search results and select certain search results to access the corresponding item listings. Selection of search results causes retrieval of the corresponding item listings. Additionally, in some cases, applications are launched in order to render data associated with the item listings. In the context of recommendation, when recommended item listings are insufficient, users may select to view certain item listings and discover the listings are not what the user is seeking. This often results in the users turning to query-based searching, which can involve issuing numerous queries in an attempt to identify relevant item listings as discussed above.
These repetitive inputs result in increased computing resource consumption, among other things. For instance, repetitive user queries result in packet generation costs that adversely affect computer network communications. Each time a user issues a query, the contents or payload of the query is typically supplemented with header information or other metadata within a packet in TCP/IP and other protocols. Accordingly, when this functionality is multiplied by all the inputs needed to obtain the desired data, there are throughput and latency costs by repetitively generating this metadata and sending it over a computer network. In some instances, these repetitive inputs (e.g., repetitive clicks, selections, or queries) increase storage device I/O (e.g., excess physical read/write head movements on non-volatile disk) because each time a user inputs unnecessary information, such as inputting several queries, the computing system often has to reach out to the storage device to perform a read or write operation, which is time consuming, error prone, and can eventually wear on components, such as a read/write head. Further, if users repetitively issue queries, it is expensive because processing queries consumes a lot of computing resources. For example, for some item retrieval systems, a query execution plan may need to be calculated each time a query is issued, which could require a system to find the least expensive query execution plan to fully execute the query. This decreases throughput and increases network latency, and can waste valuable time.
Aspects of the technology described herein improve the functioning of the computer itself in light of these shortcomings in existing search and recommendation technologies by providing a solution in which an item retrieval system employs a two-tower machine learning model utilizing co-action and sequential user behavior graph layers. The model includes an item tower for generating representations of items available on a listing platform and a user tower for generating representations of each user’s interests in items. For the item tower, item representation embeddings are generated that represent each item using its co-action items to capture collaborative signals in a co-action graph that is fully leveraged by a graph neural network (GNN) . For the user tower, a graph of a user’s behavior sequence is generated based on the user’s interactions with items on the listing platform with edges encoding pairwise relationships, and item interest embeddings are generated that represent the user interests by capturing behavior interactions. At runtime, an item interest embedding for the user can be employed to identify similar item representation embeddings in order to provide an indication of items to the user that are likely relevant to the user interest encoded by the item interest embedding.
In some aspects, to generate an item representation embedding for a target item, the item tower takes as input information regarding a target item and its co-action items. Co-action items refer to item pairs in which users have interacted with both items. As such, co-action items for a target item refer to items in which a same user (e.g., any user of the listing platform) has performed a same type of action on the target item and the co-action items. For instance, a co-click item is an item that a same user has clicked (i.e., viewed) both the target item and the co-click item. Similarly, a co-purchase item is an item that a same user has purchased both the target item and the co-purchase item. An embedding module generates item embeddings for the target item and each of its co-action items. A GNN then employs an attention mechanism to aggregate information from the co-action items to provide an item representation embedding for the target item. When there are multiple different types of co-action items (e.g., co-click items, co-purchase items , etc. ) , the process could include employing an attention mechanism to provide an aggregated co-action embedding for each type of co-action items, and the item representation embedding can be generated by combining the aggregated co-action embeddings and the target item embedding.
For the user tower, the input comprises information regarding a user’s behavior sequence, which can be represented by a sequence of behavior items –items on the listing platform with which the user has interacted. The information for each behavior item can include features of the item (e.g., title, category, price, etc. ) , an action type (e.g., click, purchase, etc. ) , and a time stamp. To achieve explicit pairwise modeling, the user tower builds a graph of the user’s behavior sequence, with nodes corresponding to item embeddings of behavior items for the user and edges between any two nodes comprising an edge embedding that encodes their relationship. Using this sequence graph, the user tower employs another GNN to learn an enhanced node embedding for each node, capturing interactions between behaviors with pairwise edge information. One or more item interest embeddings are then generated for the user based on the enhanced node embeddings.
Aspects of the technology described herein provide a number of improvements over existing item retrieval technologies. For example, on the item tower side, user co-action data is added in the form of a GNN component, which improves on the limitations of previous models that only added user behavioral data to the user tower side. For the user tower side, the model learns the pairwise interaction relationships (similarity, complementary, etc. ) of user behavior. Additionally, a novel explicit interaction algorithm is employed that expands on the standard GNN aggregation style and leverages the edge information as part of the aggregation source. Testing has demonstrated the effectiveness of the approach described hererin, with results showing improved performance over state-of-the-art methods on operational metrics.
Among other things, this enhanced performance provides for improved computing resource consumption relative to existing technologies. The relevance of item listings returned using aspects of the technology described herein eliminates (or at least reduces) the repetitive user queries, search result selections, and rendering of item listings relative to conventional techniques because relevant item listings are provided without the need for users to continuously input various search queries to access search results and/or continuously make item selections to obtain further information around presented item listings. Accordingly, aspects of the technology described herein decrease computing resource consumption, such as packet generation costs. For instance, a user query (e.g., an HTTP request) , would only need to traverse a computer network once (or fewer times relative to existing technologies) . Specifically, the contents or payload of the user query is supplemented with header information or other metadata within a packet in TCP/IP and other protocols once for the initial user query. Such packet for a user query is only sent over the network once or fewer times. Thus, there is no repetitive generation of metadata and continuous sending of packets over a computer network.
In like manner, aspects of the technology described herein improve storage device or disk I/O and query execution functionality, as they only need to go out to disk a single time (or fewer times relative to existing search technologies) . As described above, the inadequacy of existing search and recommendation technologies results in repetitive user queries, search result selections, and item listing renderings. This causes multiple traversals to disk. In contrast, aspects described herein reduce storage device I/O because the user provides only minimal inputs and so the computing system does not have to reach out to the storage device as often to perform a read or write operation. Accordingly, there is not as much wear on components, such as a read/write head, because disk I/O is substantially reduced.
Example System for Sequential Item Retrieval using Co-Action Graphs
With reference now to the drawings, FIG. 1 is a block diagram illustrating an exemplary system 100 for performing item retrieval on a listing platform using a two-two machine learning model that utilizes co-action and sequential user behavior graph layers in accordance with implementations of the present disclosure. It should be understood that this and other arrangements described herein are set forth only as examples. Other arrangements and elements (e.g., machines, interfaces, functions, orders, and groupings of functions, etc. ) can be used in addition to or instead of those shown, and some elements may be omitted altogether. Further, many of the elements described herein are functional entities that may be implemented as discrete or distributed components or in conjunction with other components, and in any suitable combination and location. Various functions described herein as being performed by one or more entities may be carried out by hardware, firmware, and/or software. For instance, various functions may be carried out by a processor executing instructions stored in memory.
The system 100 is an example of a suitable architecture for implementing certain aspects of the present disclosure. Among other components not shown, the system 100 includes a user device 102, a listing platform 104, and an item retrieval system 106. Each of the user device 102, the listing platform 104, and the item retrieval system 106 shown in FIG. 1 can comprise one or more computer devices, such as the computing device 1100 of FIG. 11, discussed below. As shown in FIG. 1, the user device 102, the listing platform 104, and the item retrieval system 106 can communicate via a network 110, which may include, without limitation, one or more local area networks (LANs) and/or wide area networks (WANs) . Such networking environments are commonplace in offices, enterprise-wide computer networks, intranets, and the Internet. It should be understood that any number of user devices and servers may be employed within the system 100 within the scope of the present technology. Each may comprise a single device or multiple devices cooperating in a distributed environment. For instance, the listing platform 104 and the item retrieval system 106 could each be provided by multiple server devices collectively providing the functionality of the listing platform 104 and the item retrieval system 106 as described herein. Additionally, other components not shown may also be included within the network environment.
The user device 102 can be a client device on the client-side of operating environment 100, while the listing platform 104 and the item retrieval system 106 can be on the server-side of operating environment 100. The listing platform 104 and/or the item retrieval system 106 can each comprise server-side software designed to work in conjunction with client-side software on the user device 102 so as to implement any combination of the features and functionalities discussed in the present disclosure. For instance, the user device 102 can include an application 108 for interacting with the listing platform 104 and/or the item retrieval system 106. The application 108 can be, for instance, a web browser or a dedicated application for providing functions, such as those described herein. This division of operating environment 100 is provided to illustrate one example of a suitable environment, and there is no requirement for each implementation that any combination of the listing platform 104 and the item retrieval system 106 remain as separate entities. For instance, in some aspects, the item retrieval system 106 is a part of the listing platform 104. While the operating environment 100 illustrates a configuration in a networked environment with a separate user device, listing platform, and item retrieval system, it should be understood that other configurations can be employed in which aspects of the various components are combined.
The user device 102 may comprise any type of computing device capable of use by a user. For example, in one aspect, a user device may be the type of computing device 1100 described in relation to FIG. 11 herein. By way of example and not limitation, the user device 102 may be embodied as a personal computer (PC) , a laptop computer, a mobile or mobile device, a smartphone, a tablet computer, a smart watch, a wearable computer, a personal digital assistant (PDA) , an MP3 player, global positioning system (GPS) or device, video player, handheld communications device, gaming device or system, entertainment system, vehicle computer system, embedded system controller, remote control, appliance, consumer electronic device, a workstation, or any combination of these delineated devices, or any other suitable device. A user may be associated with the user device 102 and may interact with the listing platform 104 and/or the item retrieval system 106 via the user device 102.
The listing platform 104 can be implemented using one or more server devices, one or more platforms with corresponding application programming interfaces, cloud infrastructure, and the like. The listing platform 104 generally provides, to user devices such as the user device 102, item listings describing items (physical or digital) available for purchase, rent, streaming, download, etc. For instance, the listing platform 104 could comprise an e-commerce platform, in which listed products or services are available for purchase by users of the user device 102 upon navigation to the listing platform 104. As other examples, the listing platform 104 could comprise a rental platform listing various items for rent (e.g., equipment, tools, real estate, vehicles, contract employees) or a media platform listing digital content items (e.g., digital content for streaming/download) .
The functionality of the listing platform 104 includes provision of interfaces enabling surfacing of item listings for items to users of the listing platform 104. Item listings for items available for sale/rent/consumption via the listing platform 104 are stored by the item listings data store 112. Each item listing may include a description relating to an item comprising one or more of a price in a currency, reviews, images of the item, shipment options, a rating, a condition of the item, a size of the item, a color of the item, etc. In aspects, each item is associated with one or more categories including meta-categories and leaf categories. For example, the meta-categories are each divisible into subcategories (or branch categories) , whereas leaf categories are not divisible.
The listing platform 104 also tracks information regarding user interactions with items and stores the information in a user interaction data store 114. Among other information, the user interaction data store 114 may store information for each user interaction that identifies: a user (e.g., via a user identifier) who performed the user interaction, an item (e.g., via an item identifier) with which the user interacted, an action performed by the user for the item (e.g., view, add to cart, add to wish list, purchase, etc. ) , and a time stamp indicative of a point in time when the user interaction occurred.
The item retrieval system 106 generally performs item retrieval for the listing platform 104, including providing search and/or recommendation functions that return items to users relevant to each user’s interests. As shown in FIG. 1, the item retrieval system 106 includes an item retrieval component 116, training component 118, and a user interface component 120. The components of the item retrieval system 106 may be in addition to other components that provide further additional functions beyond the features described herein. The item retrieval system 106 can be implemented using one or more server devices, one or more platforms with corresponding application programming interfaces, cloud infrastructure, and the like. While the item retrieval system 106 is shown separate from the listing platform 104 and the user device 102 in the configuration of FIG. 1, it should be understood that in other configurations, some of the functions of the item retrieval system 106 can be provided on the listing platform 104 and/or the user device 102. Additionally, while the components are shown as part of the item retrieval system 106, in other configurations, one or more of the components can be provided by the listing platform 104 or another location not shown in FIG. 1. The components can be provided by a single entity or multiple entities.
In some aspects, the functions performed by components of the item retrieval system 106 are associated with one or more applications, services, or routines. In particular, such applications, services, or routines may operate on one or more user devices, servers, may be distributed across one or more user devices and servers, or be implemented in the cloud. Moreover, in some aspects, these components of the item retrieval system 106 may be distributed across a network, including one or more servers and client devices, in the cloud, and/or may reside on a user device. Moreover, these components, functions performed by these components, or services carried out by these components may be implemented at appropriate abstraction layer (s) such as the operating system layer, application layer, hardware layer, etc., of the computing system (s) . Alternatively, or in addition, the functionality of these components and/or the aspects of the technology described herein can be performed, at least in part, by one or more hardware logic components. For example, and without limitation, illustrative types of hardware logic components that can be used include Field-programmable Gate Arrays (FPGAs) , Application-specific Integrated Circuits (ASICs) , Application-specific Standard Products (ASSPs) , System-on-a-chip systems (SOCs) , Complex Programmable Logic Devices (CPLDs) , etc. Additionally, although functionality is described herein with regards to specific components shown in example system 100, it is contemplated that in some aspects, functionality of these components can be shared or distributed across other components.
The item retrieval component 116 employs a machine learning model 122 to perform item retrieval for users. The model 122 includes a user tower 124 that generates one or more item interest embeddings for a user that take into account a sequence of user interactions with items on the listing platform 104 performed by the user. The sequence of user interactions by the user can be identified from the user interaction data store 114, for instance, by retrieving user interaction data having a user identifier for the user. Each item interest embedding generated for a given user can be a vector representation of a user interest for the user based on the sequence of user interactions. In some aspects, item interest embeddings generated for a user can be stored, for instance, in an item interest embedding data store (not shown) . For instance, the item interest embeddings can be stored in association with a user identifier, such that the item interest embeddings can subsequently be accessed from the data store when performing item retrieval for the user. This process can be performed for any number of users such that the item interest embedding data store stores item interest embeddings for each user with a corresponding user identifier.
The model 122 also includes an item tower 126 that generates item representation embeddings for items on the listing platform that take into account co-actions for each item. A co-action item for a given target item can be identified from the user interaction data store 114 by identifying instances in which a same user has performed a same action on both the target item and the co-action item. Given a target item and co-action items for the target item, the item tower 126 generates an item representation embedding, which can comprise a vector representation of the target item. In some aspects, an item representation embedding generated for a target item can be stored, for instance, in an item representation embedding data store (not shown) . For instance, the item representation embedding can be stored in association with an identifier for the target item, such that the item representation embedding can subsequently be accessed from the data store when performing item retrieval for a user. This process can be performed for each item available on the listing platform 104 such that the item representation embedding data store stores an item representation embedding for each item with an item identifier associated with each item representation embedding.
Given one or more item interest embeddings for a user generated by the user tower 124 and item representation embeddings of items generated by the item tower 126, the item retrieval component 116 selects one or more items for presentation to the user (e.g., via the user device 102) . For instance, the item retrieval component 116 can use a similarity measure (e.g., cosine similarity) to identify item representation embeddings that are similar to an item interest embedding for a user. In some instances, the item retrieval component 116 selects items based on the similarity measure and provides those items to the user. In other instances, the item retrieval component 116 selects items as candidates (i.e., candidate generation) and then performs ranking of the candidate items to select and/or order items that are provided to the user. The item retrieval component 116 can perform the item retrieval operations in the context of search (e.g., where the user has explicitly provided some search input) or recommendation (e.g., when the user has not explicitly provided some search input) .
By way of example to illustrate, FIG. 6 shows a sequence of user actions 602, which represents a sequence of actions a user has performed with items on a listing platform, including a bag, pants, and shows. Based on the user actions 602, the system generates item interest embeddings representing interests for the user. The system selects item representation embeddings similar to each item interest embeddings, and provides item recommendations for each interest. As shown in FIG. 2, the system provides a first set of item recommendations 604 corresponding to the user’s interest in athletic shoes, a second set of item recommendations 606 corresponding to the user’s interest in men’s bags, and a third set of item recommendations 608 corresponding to the user’s interest in pants.
FIG. 2 provides a block diagram showing a model architecture 200 that could be employed for the model 122 of FIG. 1. For the purpose of the description provided herein, a set of usersand each user u has a sequence of actionswhere represents the item of ith action, is the behavior type (i.e., action type) of ith action, andis the behavior timestamp of ith action. While any of a variety of different types of actions can be employed, two types will be discussed herein for illustration purposes: co-click actions where a same user has clicked on two items; and co-purchase actions where a same user has purchased two items. Accordingly, given an item xq, two types of co-action items can provided as follows: (1) xqc∈Cq when there is at least one user that has clicked on both xq and xqc, which is referred to herein as co-click items; and (2) when there is at least user that has purchased both xq and xqp, which is referred to herein as co-purchase items. In some aspects, a goal of the model is to predict the next action of the user from a set of items i∈I.
The model architecture 200 includes an item tower 202 and a user tower 204. With initial reference to the item tower 202, the full set of item-to-item relationships on a listing platform (e.g., the listing platform 104 of FIG. 1) can be considered as a co-action graph. The item tower 202 constructs a localized subgraph by considering the co-action items of the neighbors of a target item. In some configurations, a graph neural network (GNN) is then used to aggregate information within this subgraph and obtain an embedding representation for the target item.
As shown in FIG. 2, the input to the item tower 202 comprises a target item 206 and a set of co-action items 208 for the target item 206. In some aspects, the input for each item can comprise a collection of textual information describing the item, based on, for instance, a title, a description, and/or structured data (e.g., a set of features (attribute-value pairs) ) for the item. The information for each item can also identify an action type (e.g., click, add to cart, purchase, etc. ) . In some aspects, the input for each item could include one or more images of the item.
Each item x (i.e., the target item 206 and each of the co-action items 208) is fed into an embedding module 210, which generates an embedding representation e for each item, thereby providing a set of embeddings 212. In the configuration of FIG. 2, the embedding module 210 is shared by the item tower 202 and the user tower 204. However, in other configurations, separate embedding modules can be used by the towers. The embedding module 210 can employ an embedding model (e.g., a neural network model) that is a pre-trained model, a model built and trained from scratch, or a pre-trained model that is fine-tuned.
A coaction aggregation module 214 aggregates the embeddings 212 for the target item and its co-action items to generate a final item representation 216 for the target item. FIG. 3 provides a block diagram showing an example coaction aggregation module 300 that could be employed as the coaction aggregation module 214 in the item tower 202 of FIG. 2. The coaction aggregation module 300 generally comprises two steps. In a first step, an attention mechanism is used to aggregate neighboring nodes. For instance, given each co-click item embedding (e.g., coaction items 304A and 304B) , a coaction aggregation model 308 calculates its attention with target item eq and generates a weighted sumto provide an aggregated co-click embedding 310, which can be denoted as zqc. Similarly, for each co-purchase item embedding (e.g., coaction items 306A and 306B) , a coaction aggregation model 312 calculates its attentionwith target item eq and generates a weighted sumto provide an aggregated co-purchase embedding 314, which can be denoted as zqp. In a second step, the aggregated embeddings 310 and 314 are combined (e.g., concatenated) and transformed with a linear layer (e.g., using a multilayer perceptron) to obtain a final item representation embedding 318, which can be represented as zq, wherein zq=Wzq·CONCAT (eq, zqz, zqp) + bzq, where Wzq and bzq are model weights.
With reference again to FIG. 2, the user tower 204 will now be described. As shown in FIG. 2, the input to the user tower 204 comprises a set of behavior items 218 that represent items from a listing platform (e.g., the listing platform 104 of FIG. 1) with which the user has interacted. In some aspects, the input for each item can comprise a collection of textual information describing the item, based on, for instance, a title, a description, and/or structured data (e.g., a set of features (attribute-value pairs) ) for the item. The information for each item can also identify an action type (e.g., click, add to cart, purchase, etc. ) indicative of the type of user interaction the user had with the item and a time stamp indicative of a specific point in time when the user interacted with the item. In some aspects, the input for each item could include one or more images of the item. The behavior items 218 can be viewed as an action sequence for the user –i.e., a sequence of items in which the items are ordered based on the time stamp associated with each item.
Each item x (i.e., each of the behavior items 218) is fed into an embedding module 210, which generates an embedding representation e for each item, thereby providing a set of embeddings 220. As discussed above, in the configuration of FIG. 2, the embedding module 210 is shared by the item tower 202 and the user tower 204. However, in other configurations, separate embedding modules can be used by the towers. The embedding module 210 can employ an embedding model (e.g., a neural network model) that is a pre-trained model, a model built and trained from scratch, or a pre-trained model that is fine-tuned.
A graph construction module 222 converts the user’s action sequence into a graph 224, which comprises a fully connected graph in some aspects. In the graph, each node represents a user action (e.g., click, add to watchlist, add to cart, purchase, etc. ) on a specific item. In particular, the nodes comprise the embeddings 220. Each edge in the graph 224 connects two embeddings capture the temporal relationships between the actions represented by the embeddings based on the user’s sequential behavior. In some aspect, the graph 224 is directed as early-occurring actions can affect later occurring actions but not vice versa, so the direction of information aggregation is one-way.
The graph construction module 222 generates the representation for each node and edge on the graph 224. As noted above, the graph construction module 22 use the embeddings 220 as node representations. For each edge, the graph construction module 222 usesto denote an edge which connects the i-th and j-th action (i.e., behavior item) of user u.
FIGs. 4A and 4B provide diagrams illustrating construction of the edge information by the graph construction module 222 of FIG. 2. FIG. 4A provides an edge matrix showing the edges that are generated between source nodes and target nodes in accordance with some aspects employing a fully connected graph. FIG. 4B provides a block diagram illustrating generation of an edge representation 410 for two nodes 402A and 402B. The edge representation 410 is mainly built from pairwise relationship information. This type of information is calculated based on the features of the given node pair 402A and 402B –i.e., a first set of features 404A for the first node 402A and a second set of features 404B for the second node 402B. Calculating pairwise level information provides an explicit way to represent the behavior interaction. The example of FIG. 4B employs several different types of functions based on the different characteristics of item features. In particular, FIG. 4B shows a feature builder 406A for behavior type, a feature builder 406B for time stamps, a feature builder 406C for one-hot features, a feature builder 406D for numerical features, and a feature builder 406E for ordinal features. It should be understood that the features and functions provided in FIG. 4B are provided by way of example only and some features/functions shown may be omitted and features/functions not shown may be included.
For one-hot features contained in items, such as item ID, category ID, parent category ID, seller ID, etc., the function I is defined to compare if they are the same between the two nodes:
For numerical value features contained in items, such as processed price information, the function G is defined to measure the gap between them for the two nodes:
For ordinal features that can represent relative relationships, such as the seller’s level, or bucketized numerical feature like price range level, the function H is defined to compare and return their order relationship for the two nodes:
Besides the pairwise information from item features, the behavior type bu and timestamp tu are considered as one-hot and numerical features separately, applying the above functions to them. The process can also convertandinto embedding representationsandand include them directly as part of the edge information.
Based on the feature builders, for each item x, the feature index is arranged and features with the same type appearing in a row. x (1) , …, x (g) are one-hot features, x (g+1) , …, x (h) are numerical features, and x (h+1) , …, xN are ordinal features. The corresponding pairwise features are calculated based on above functions and the results are concatenated by an embedding layer 408 to provide an edge representation 410. The edge representation can be defined as:
In instances in which the graph is directed, the edge embedding representation only makes sense when the inputandhas the order i≥j. For the case when i＜j, the edge embedding can be defined as 0.
Based on these operations, a sequence graphis constructed, where the set of nodesand the set of edges εu have the corresponding embedding representations as follows:
With reference again to FIG. 2, after constructing the graph 224, an explicit interaction module 226 learns the explicit interaction between user behaviors based on the constructed sequence graph 224 to generate a set of enhanced node embeddings 228. The process performed by the explicit interaction module 226 is described below in Algorithm 1. The algorithm can be seen as an L-layer GNN.
FIG. 5 provides a block diagram showing operation 500 of an explicit interaction module (e.g., the explicit interaction module 226 of FIG. 2) . The initial input is obtained from the graph output by the graph construction module (e.g., the graph 224 output by the graph construction module 222 of FIG. 2) –i.e., a node matrix 502 with the nodes (i.e., item embeddings) from the graph and an edge matrix 504 with the edges (i.e., edge embeddings) from the graph.
For a particular layer 1, the explicit interaction module performs an attention based graph layer for each node. The attention here is an attention mechanism 512 that considers both node and edge information. Some aspects employ an attention calculation method from both Graph Attention Network (GAT) (additive attention) and Transformer (dot product attention) . More particularly, the explicit interaction module generates, for each node from the node matrix 502: a query embedding to provide a set of query embeddings 506, a key embedding to provide a set of key embeddings 508, and a value embedding to provide a set of value embeddings 510. An attention mechanism 512 calculates attention for each pair of connected nodes from the graph to provide a set of attentions 514. In particular, for a given pair of nodes the attention mechanism 512 generates the attention using the query embedding for the first nodethe key embedding for the second nodeand the edge embedding between the two nodesIn some aspects, the attention is overall in an additive attention style, and for the input, the edge embedding is included for explicit pairwise information, as well as the node dot product to ensure that the model can learn the bit-wise relevance from nodes.
Aggregation 518 is performed for each node to generate an enhanced node embeddingthereby providing a set of enhanced node embeddings 518, which can be viewed as a behavior representation matrixIn some aspects, for a given node, the aggregation 518 updates the enhanced node embedding from a previous layer with the attentions for the edges associated with the given node and value embeddings of nodes connected to the given node in the graph.
Turning again to FIG. 2, the explicit interaction module 226 provides a set of enhanced node embeddings 228, which can be viewed as a behavior representation matrix Given the enhanced node embeddings 228, an interest extraction module 230 extracts item interest embeddings 232 for the user. The output of the interest extraction module 230 is a set of item interest embeddings 232, which can be viewed as the user’s interest representation matrix, denoted aswhereis the item interest embedding (e.g., representation vector) for the i-th interest of the user, and K is a preset parameter representing the number of interests. While the model architecture 200 provides an example in which three item interest embeddings are generated, it should be understood that a model could be configured to generate any number of item interest embeddings for a user in accordance with aspects of the technology described herein.
In some aspects, the interest extraction module 230 employs a self-attentive method to generate the item interest embeddings 232. For instance, given the enhanced node embeddings 228 (represented as Hu) , attention weights can be generated, for instance, as:
where W1 and W2 are trainable parameters, and T indicates the transpose. A can comprise a matrix with size based on the K number of interests. The user’s interest representation matrix can then be generated as follows:
Ou=AHu (8)
With reference again to FIG. 1, the item retrieval system 106 also includes a training component 118 that trains the model 122 using a dual-objective loss to tune the importance of collaborative aspects. In some aspects, given an interest representation matrix Ou for a given user, as well as the item representation embedding zq for any target item, the training component 118 selects the item interest embeddingthat generates the highest dot product score (e.g., the affinity score 234 shown in FIG. 2) among the user’s item interest embeddings, i.e. A first lossis defined as the sampled softmax loss where the target item is positive and random selected items are negatives. In addition, the training component 118 computes a score between the item interest embedding and the item embedding eq of the target item as an auxiliary score (e.g., the auxiliary score 236 shown in FIG. 2) and selects the activated user interest embeddingin a similar manner. Witha corresponding lossis defined, which is also the sampled softmax loss. While co-action items make full use of collaborative signals, they can introduce some noise. Therefore, in some aspects, the auxiliary loss is defined to allow for intervention in the importance ratio between collaborative signals and the item itself during training, guiding the model to learn better embeddings. Thus, the final loss function (e.g., the sample softmax loss 238 of FIG. 2) is:
where λ is a hyperparameter to balance the ratio betweenand
The learned item interest embeddings Ou and item embedding zq based on the given user u and item q can be used for calculating the user’s score for the item:
The item retrieval system 106 further includes a user interface component 120 that provides one or more user interfaces for interacting with the listing platform 104 and/or the item retrieval service 106. While shown as part of the item retrieval service 106 in FIG. 1, in some configurations, the user interface component 120 can be part of the listing platform 104. The user interface component 120 provides one or more user interfaces to a user device, such as the user device 102. In some instances, the user interfaces can be presented on the user device 102 via the application 108, which can be a web browser or a dedicated application for interacting with the listing platform 104 and/or the recommendation service. For instance, the user interface component 120 can provide user interfaces for, among other things, providing search results and/or recommendations identifying item listings selected by the item retrieval system 106 using item interest embeddings generated for the user by the user tower 124 and item embeddings generated for items by the item tower 126.
Example Methods for Sequential Item Retrieval using Co-Action Graphs
With reference now to FIG. 7, a flow diagram is provided that illustrates a method 700 for generating an item interest embedding for a target item in accordance with some aspects. The method 700 may be performed at least in part, for instance, by the item tower 126 of FIG. 1. Each block of the method 700 and any other methods described herein comprises a computing process performed using any combination of hardware, firmware, and/or software. For instance, various functions can be carried out by a processor executing instructions stored in memory. The methods can also be embodied as computer-usable instructions stored on computer storage media. The methods can be provided by a standalone application, a service or hosted service (standalone or in combination with another hosted service) , or a plug-in to another product, to name a few.
As shown at block 702, information regarding a target item and its co-action items is accessed. An item embedding is generated for the target item at block 704. Additionally, an item embedding is generated for each co-action item at block 706. An aggregation mechanism is employed to generate an aggregated co-action embedding using the item embeddings for the target item and the co-action items, as shown at block 708. This could include employing the attention mechanism to calculate an attention for each co-action item with the target item and aggregating the attentions for the co-action items to provide the aggregated co-action embedding. In some instances, the co-action items correspond to different action types (e.g., co-click items, co-purchase items, etc. ) . In such instances, an aggregated co-action embedding can be generated for each action type using the item embeddings of co-action items for each action type. An item representation embeddings for the target item is generated by combining the item embedding for the target item with the generated aggregated co-action embedding (s) , as shown at block 710. In some aspects, the item representation embedding for the target item can be stored in association with an item identifier for the target item, for instance, to facilitate item retrieval using the item representation embedding.
Turning next to FIG. 8, a flow diagram is provided showing a method 800 for generating one or more item interest embeddings for a user in accordance with some aspects. The method 800 may be performed at least in part, for instance, by the user tower 124 of FIG. 1. As shown at block 802, sequential behavior information for a user is accessed. The sequential behavior information can include information regarding a sequence of items on a listing platform with which the user has interacted. An item embedding is generated for each of the items, as shown at block 804, and a graph is constructed to represent the sequential behavior information, as shown at block 806. The graph is constructed with nodes corresponding to the item embeddings and edges corresponding to edge embeddings based on relationships between the nodes. In some aspects, the graph is fully connected and directed based on temporal relationships (e.g., based on time stamps indicative of when the user interacted with each item) . In some aspects, the edge embedding between each pair of nodes can be generated based on pair-wise relationship information between items corresponding to nodes. The pair-wise relationship information can correspond to a variety of different features associated with each item, such as, for instance: action type (indicative of the type of action the user performed for the item) , time stamp (indicative of a point in time at which the user interacted with the item) , one-hot features, numerical features, and ordinal features.
A GNN generates an enhanced node embedding for each node in the graph using the item embeddings and the edge embeddings, as shown at block 808. For instance, the enhanced node embeddings could be generated using Algorithm 1 provided above. As shown at block 810, one or more item interest embeddings are generated using the enhanced node embeddings, for instance, using a self-attentive method. Each item interest embedding represents an interest for the user based on the sequential behavior information for the user. In some aspects, each item interest embedding can be stored in associated with a user identifier for the user, for instance, to facilitate subsequent use for item retrieval for the user.
FIG. 9 provides a flow diagram showing a method 900 for training a model in accordance with some aspects. The method 900 can be performed at least in part, for instance, using the model 122 and the training component 118 of FIG. 1. As shown at block 902, one or more item interest embeddings are generated for a user based on sequential behavior information for the user (e.g., using the method 800 of FIG. 8) . Additionally, as shown at block 904, an item representation embedding is generated for a target item using an item embedding for the target item and item embeddings for co-action items (e.g., using the method 700 of FIG. 7) . A first loss is generated at block 906 using an affinity score based on an item interest embedding and the item representation embedding. A second loss is generated at block 908 using an auxiliary score based on the item interest embedding and the item embedding for the target item. A total loss is generated at block 910 by combining the first and second losses. As shown at block 912, model parameters (e.g., weights) are updated (e.g., using backpropagation) based on the total loss.
With reference now to FIG. 10, a flow diagram is provided showing a method 1000 for performing item retrieval in accordance with some aspects. The method 1000 can be performed at least in part, for instance, using the item retrieval component 116 of FIG. 1. As shown at block 1002, an item interest embedding is accessed for a user. The item interest embedding can be generated, for instance, using a graph neural network (GNN) operating on a graph constructed from sequential behavior information for the user (e.g., using the method 800 of FIG. 8) . As shown at block 1004, a similarity measure (e.g., cosine similarity) is determine for each of a plurality of items on a listing platform based on the item interest embedding and an item representation embedding for each item. The item representation embedding could be generated for each item using co-action items for each item (e.g., using the method 700 of FIG. 7) . As shown at block 1006, an indication of one or more items is provided based on the similarity measures. For instance, one or more items can be selected and/or ordered as search results or item recommendations that can be provided to a user device for presentation to the user.
Exemplary Operating Environment
Having described implementations of the present disclosure, an exemplary operating environment in which embodiments of the present technology may be implemented is described below in order to provide a general context for various aspects of the present disclosure. Referring initially to FIG. 11 in particular, an exemplary operating environment for implementing embodiments of the present technology is shown and designated generally as computing device 1100. Computing device 1100 is but one example of a suitable computing environment and is not intended to suggest any limitation as to the scope of use or functionality of the technology. Neither should the computing device 1100 be interpreted as having any dependency or requirement relating to any one or combination of components illustrated.
The technology may be described in the general context of computer code or machine-useable instructions, including computer-executable instructions such as program modules, being executed by a computer or other machine, such as a personal data assistant or other handheld device. Generally, program modules including routines, programs, objects, components, data structures, etc., refer to code that perform particular tasks or implement particular abstract data types. The technology may be practiced in a variety of system configurations, including hand-held devices, consumer electronics, general-purpose computers, more specialty computing devices, etc. The technology may also be practiced in distributed computing environments where tasks are performed by remote-processing devices that are linked through a communications network.
With reference to FIG. 11, computing device 1100 includes bus 1110 that directly or indirectly couples the following devices: memory 1112, one or more processors 1114, one or more presentation components 1116, input/output (I/O) ports 1118, input/output components 1120, and illustrative power supply 1122. Bus 1110 represents what may be one or more busses (such as an address bus, data bus, or combination thereof) . Although the various blocks of FIG. 11 are shown with lines for the sake of clarity, in reality, delineating various components is not so clear, and metaphorically, the lines would more accurately be grey and fuzzy. For example, one may consider a presentation component such as a display device to be an I/O component. Also, processors have memory. The inventors recognize that such is the nature of the art, and reiterate that the diagram of FIG. 11 is merely illustrative of an exemplary computing device that can be used in connection with one or more embodiments of the present technology. Distinction is not made between such categories as “workstation, ” “server, ” “laptop, ” “hand-held device, ” etc., as all are contemplated within the scope of FIG. 11 and reference to “computing device. ”
Computing device 1100 typically includes a variety of computer-readable media. Computer-readable media can be any available media that can be accessed by computing device 1100 and includes both volatile and nonvolatile media, removable and non-removable media. By way of example, and not limitation, computer-readable media may comprise computer storage media and communication media. Computer storage media includes both volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information such as computer-readable instructions, data structures, program modules or other data.
Computer storage media includes, but is not limited to, RAM, ROM, EEPROM, flash memory or other memory technology, CD-ROM, digital versatile disks (DVD) or other optical disk storage, magnetic cassettes, magnetic tape, magnetic disk storage or other magnetic storage devices, or any other medium which can be used to store the desired information and which can be accessed by computing device 1100. The terms “computer storage media” and “computer storage medium” do not comprise signals per se.
Communication media typically embodies computer-readable instructions, data structures, program modules or other data in a modulated data signal such as a carrier wave or other transport mechanism and includes any information delivery media. The term “modulated data signal” means a signal that has one or more of its characteristics set or changed in such a manner as to encode information in the signal. By way of example, and not limitation, communication media includes wired media such as a wired network or direct-wired connection, and wireless media such as acoustic, RF, infrared and other wireless media. Combinations of any of the above should also be included within the scope of computer-readable media.
Memory 1112 includes computer storage media in the form of volatile and/or nonvolatile memory. The memory may be removable, non-removable, or a combination thereof. Exemplary hardware devices include solid-state memory, hard drives, optical-disc drives, etc. Computing device 1100 includes one or more processors that read data from various entities such as memory 1112 or I/O components 1120. Presentation component (s) 1116 present data indications to a user or other device. Exemplary presentation components include a display device, speaker, printing component, vibrating component, etc.
I/O ports 1118 allow computing device 1100 to be logically coupled to other devices including I/O components 1120, some of which may be built in. Illustrative components include a microphone, joystick, game pad, satellite dish, scanner, printer, wireless device, etc. The I/O components 1120 may provide a natural user interface (NUI) that processes air gestures, voice, or other physiological inputs generated by a user. In some instance, inputs may be transmitted to an appropriate network element for further processing. A NUI may implement any combination of speech recognition, touch and stylus recognition, facial recognition, biometric recognition, gesture recognition both on screen and adjacent to the screen, air gestures, head and eye-tracking, and touch recognition associated with displays on the computing device 1100. The computing device 1100 may be equipped with depth cameras, such as, stereoscopic camera systems, infrared camera systems, RGB camera systems, and combinations of these for gesture detection and recognition. Additionally, the computing device 1100 may be equipped with accelerometers or gyroscopes that enable detection of motion.
The present technology has been described in relation to particular embodiments, which are intended in all respects to be illustrative rather than restrictive. Alternative embodiments will become apparent to those of ordinary skill in the art to which the present technology pertains without departing from its scope.
Having identified various components utilized herein, it should be understood that any number of components and arrangements may be employed to achieve the desired functionality within the scope of the present disclosure. For example, the components in the embodiments depicted in the figures are shown with lines for the sake of conceptual clarity. Other arrangements of these and other components may also be implemented. For example, although some components are depicted as single components, many of the elements described herein may be implemented as discrete or distributed components or in conjunction with other components, and in any suitable combination and location. Some elements may be omitted altogether. Moreover, various functions described herein as being performed by one or more entities may be carried out by hardware, firmware, and/or software, as described below. For instance, various functions may be carried out by a processor executing instructions stored in memory. As such, other arrangements and elements (e.g., machines, interfaces, functions, orders, and groupings of functions) can be used in addition to or instead of those shown.
Embodiments described herein may be combined with one or more of the specifically described alternatives. In particular, an embodiment that is claimed may contain a reference, in the alternative, to more than one other embodiment. The embodiment that is claimed may specify a further limitation of the subject matter claimed.
The subject matter of embodiments of the technology is described with specificity herein to meet statutory requirements. However, the description itself is not intended to limit the scope of this patent. Rather, the inventors have contemplated that the claimed subject matter might also be embodied in other ways, to include different steps or combinations of steps similar to the ones described in this document, in conjunction with other present or future technologies. Moreover, although the terms “step” and/or “block” may be used herein to connote different elements of methods employed, the terms should not be interpreted as implying any particular order among or between various steps herein disclosed unless and except when the order of individual steps is explicitly described.
For purposes of this disclosure, the word “including” has the same broad meaning as the word “comprising, ” and the word “accessing” comprises “receiving, ” “referencing, ” or “retrieving. ” Further, the word “communicating” has the same broad meaning as the word “receiving, ” or “transmitting” facilitated by software or hardware-based buses, receivers, or transmitters using communication media described herein. In addition, words such as “a” and “an, ” unless otherwise indicated to the contrary, include the plural as well as the singular. Thus, for example, the constraint of “a feature” is satisfied where one or more features are present. Also, the term “or” includes the conjunctive, the disjunctive, and both (a or b thus includes either a or b, as well as a and b) .
For purposes of a detailed discussion above, embodiments of the present technology are described with reference to a distributed computing environment; however, the distributed computing environment depicted herein is merely exemplary. Components can be configured for performing novel embodiments of embodiments, where the term “configured for” can refer to “programmed to” perform particular tasks or implement particular abstract data types using code. Further, while embodiments of the present technology may generally refer to the technical solution environment and the schematics described herein, it is understood that the techniques described may be extended to other implementation contexts.
From the foregoing, it will be seen that this technology is one well adapted to attain all the ends and objects set forth above, together with other advantages which are obvious and inherent to the system and method. It will be understood that certain features and subcombinations are of utility and may be employed without reference to other features and subcombinations. This is contemplated by and is within the scope of the claims.