Using Tripartite Graphs to Make Long Tail Recommendations

While current state-of-the-art recommendation systems perform fairly well, they generally do better at recommending the popular subset of all products available rather than matching consumers with the vast amount of niche products in what has been termed the "Long Tail". In their seminal work, "Challenging the Long Tail Recommendation", Yin et al. make an eloquent argument that the long tail is where organizations can create the most value for their consumers. They also argue that existing recommender systems operate fundamentally different for long tail products than for mainstream goods. While matrix factorization, nearest-neighbors, and clustering work well for the "head" market, the long tail is better represented by a graph; specifically a bipartite graph that connects a set of users to a set of goods. In this paper, we show the algorithms presented by Yin et al., as well as a set of similar algorithms proposed by Shang et al., which traverse the bipartite graphs through a random walker in order to identify similar users and products. We build on elements from each work, as well as elements from a Markov process, to facilitate the random walker's traversal of the graph into the long tail regions. This method specifically constructs paths into regions of the long tail that are favorable to users.