PathMining: A Path-Based User Profiling Algorithm for Heterogeneous Graph-Based Recommender Systems

In a heterogeneous graph-based recommender system, relationships among various entities are used to predict the rating or preference that a user would give to an item. By modeling user’s selection behavior as a path in the heterogeneous graph, we can capture each user’s unique selection behaviors as a set of paths with specific types of nodes and edges. Since these paths capture selection behaviors unique to each user, these can then be used to perform personalized profiling and recommendation for each user. In this paper, we introduce PathMining, an algorithm which constructs personalized user profile and make recommendations based on Monte Carlo sampling of graph traversal. PathMining predicts preferable items by emulating user’s selection processes. The performance and potential value of our method is validated by using HetRec 2011 dataset. Traditionally, recommendation has been considered as a problem of finding an utility function that best predicts a user’s unknown ratings given the user’s known ratings as found in User×Item rating matrix (Adomavicius and Tuzhilin 2005). In the past, most recommender systems, based on this problem formulation, focused on increasing recommendation accuracy by minimizing differences between the predicted recommendations and the known ratings in the matrix as exemplified by the Netflix prize (Bennett and Lanning 2007). However, with the observation that decrease in the errors in the matrix alone does not necessarily increase the quality of the recommendations, the current trend is to incorporate other external types of information into the problem. A heterogeneous graph-based recommender system is an approach to integrate user ratings with other types of information following their semantic relationships, and represent them as a single graph. The types of entities in a graph are denoted as a node or an edge. Examples of nodes and edges for a movie rating system may be (e.g., USER, MOVIE, ACTOR, DIRECTOR, TAG, . . .) and edges (e.g., USER liked −−→ MOVIE, MOVIE directedBy −−−−−→ DIRECTOR, MOVIE starring −−−−→ ACTOR, . . .). The advantage of the heterogeneous  graph model is that a recommendation can be inferred by considering these heterogeneous entities and their relationships together, thus offering rooms for applying different types of recommendation approaches such as content-based filtering, collaborative filtering, or hybrid approaches that combine the two. Generally, a user’s process of finding his or her preferable items can be represented as a set of paths in a heterogeneous graph. For instance, let us consider a case that a user finds next favorable movies by examining the directors who directed some movies the user already likes, and see how this would be represented in a heterogeneous graph. Let us assume Ma and Mb, and Da are of type MOVIE and DIRECTOR, respectively, and liked −−→ and directedBy −−−−−→ are of edge types between the USER and the MOVIE, and the MOVIE and DIRECTOR. Then starting from the user U , a path (U liked −−→ Ma directedBy −−−−−→ Da directedBy− −−−−−−→Mb) would denote how the user comes to find a next favorable movie, if Mb was found attractive to the user. Correspondingly, such a selection behavior of the user can be represented as USER liked −−→ MOVIE directedBy −−−−−→ DIRECTOR directedBy − −−−−−−→MOVIE, which we call a path type. In practice, a user’s selection process should involve more node and edge types resulting in longer path types. We postulate that a user’s unique selection behaviors can be probabilistically extracted in terms of path types from a heterogeneous graph. More formally put, between a user U and a set of his favorable movies {M1,M2, . . . ,Mn} in a graph, path types that are dominantly found in paths between U and {M1,M2, . . . ,Mn} will faithfully represent the user’s selection behaviors. Note, however, a path type found to represent a behavior of a user may not necessarily represents that of another user. For instance, a user may have many favorite actors, so he tends to prefer movies starring those actors. In this case, following a path whose path type is USER liked −−→MOVIE actedIn −1 −−−−−→ ACTOR actedIn −−−−→MOVIE, starting from the node representing the user in the graph, has more potential of reaching at the user’s preferable movies than following the other types of paths. On the other hand, another user may have preference for movies attached by the 519 Proceedings of the Twenty-Eighth International Florida Artificial Intelligence Research Society Conference