This paper presents an algorithm for recommending items using a diverse set of features. The items are recommended by performing a random walk on the k-partite graph constructed from the heterogenous features. To support personalized recommendation, the random walk must be initiated separately for each user, which is computationally demanding given the massive size of the graph. To overcome this problem, we apply multi-way clustering to group together the highly correlated nodes. A recommendation is then made by traversing the subgraph induced by clusters associated with a user's interest. Our experimental results on real data sets demonstrate the efficacy of the proposed algorithm.