2009 RecommendationAsLinkPrediction

• (Li & Chen, 2009) ⇒ Xin Li, Hsinchun Chen. (2009). “Recommendation as Link Prediction: A graph kernel-based machine learning approach.” In: Proceedings of the 9th ACM/IEEE-CS joint conference on Digital libraries. doi:10.1145/1555400.1555433

Subject Headings: Link Prediction Algorithm, Kernel-based Learning Algorithm, Recommender System.

Cited By

• Cited by ~1 http://scholar.google.com/scholar?cites=8396875918671135117

Quotes

Abstract

• Recommender systems have demonstrated commercial success in multiple industries. In digital libraries they have the potential to be used as a support tool for traditional information retrieval functions. Among the major recommendation algorithms, the successful collaborative filtering (CF) methods explore the use of user-item interactions to infer user interests. Based on the finding that transitive user-item associations can alleviate the data sparsity problem in CF, multiple heuristic algorithms were designed to take advantage of the user-item interaction networks with both direct and indirect interactions[. However, the use of such graph representation was still limited in learning-based algorithms. In this paper, we propose a graph kernel-based recommendation framework. For each user-item pair, we inspect its associative interaction graph (AIG) that contains the users, items, and interactions [math]\displaystyle{ n }[/math] steps away from the pair. We design a novel graph kernel to capture the AIG structures and use them to predict possible user-item interactions. The framework demonstrates improved performance on an online bookstore dataset, especially when a large number of suggestions are needed.

2.1 Graph-based Recommendation Algorithms

• Previous recommendation algorithm studies fall into two main types according to the data used. The first type focuses on the use of user/item local features and the statistical characteristics of user usage histories[. The[ heuristic algorithm]]s using such local features usually define user/item similarity measures and cross-recommend similar items between similar users [4]. The learning-based algorithms on local features tend to capture hidden classes of users/items and estimate possibilities of user-item interactions from usage statistics [5].
• The second type of recommendation algorithms focuses on the indirect user-item interactions extracted from user usage history and views them as a network. Such graph-based recommendation algorithms, including both heuristics and learning-based methods, are grounded in graph theory and use the topologies of user-item interaction networks to predict possible links between users and items. There are three major classes of graph-based heuristics in previous research. First, some studies propose to use eigenvector-based node ranking algorithms that are similar to PageRank [2,6] and HITS [3,7] to rank items and conduct recommendations according to item ranks. Second, some studies aim to include the effect of the network structure in user/item similarity measures. They iteratively propagate node similarities defined on local features through the links on the network. The converged node similarities reflect both individual node features and features from their neighbors, which can better measure the user/item similarities in the interaction network context [8,9]. Third, some heuristics are designed based on the positions of users and items on the network. For example, closer users and items (measured by conducting random walks on the network) can be predicted to have a higher probability to interact [10].
• In addition to the heuristic methods that use graph representation, some researchers proposed machine learning algorithms to build models based on the topological patterns of user-item interaction networks. For example, Huang et al. [11] have extended the Probabilistic Relational Model (PRM) framework [12] and proposed to define features on directly or indirectly connected nodes. These features can be used in Bayes models to predict possible user-item interactions. Hasan et al. [13] proposed a supervised framework and used node similarity features, aggregated features on direct indirect interactions, and global topological features of the network for link prediction.
• While several efforts have been made to use graph-based heuristics, the heuristic algorithms suffered from unstable performances on different datasets, due to the fact that the models are not built based on the data. On the other hand, the studies on learning-based recommendation algorithms that used a graph representation are still limited. The existing learning-based algorithms usually need explicitly defined features, which require intensive domain knowledge. In addition, it is computationally expensive to specify the graph-related features in user-item interaction networks, due to the fan-out characteristic of graph-structured data. Such difficulties have hindered the development of graph-based machine learning recommendation algorithms.

5. CONCLUSIONS

• In this paper we present a graph kernel-based approach for recommendation. Treating the recommendation task as a link prediction problem in user-item interaction networks, we define an associative interaction graph for each user-item pair and use its structure to infer whether or not the user-item pair may have a link. We propose a novel graph kernel that can effectively capture graph features from the AIGs. Using data of an online bookstore, our experiment results show improved recommendation performances with our graph kernel-based approach.
• We propose that this graph kernel-based approach may be extended to various digital library settings, especially on multimedia contents where traditional information retrieval tasks are difficult to conduct. At the methodology level, we are in the process of extending our work in the following directions: a) utilizing other types of graphs, such as user social networks or book citation networks, to improve recommendation; b) exploring the effect of different types of node information and link information in this graph kernel-based framework. We will also generalize the proposed framework to address other link prediction problems.

References

• 1. Michael J. Pazzani, A Framework for Collaborative, Content-based and Demographic Filtering, Artificial Intelligence Review, v.13 n.5-6, p.393-408, Dec. 1999 doi:10.1023/A:1006544522159.
• 2. Zan Huang, Hsinchun Chen, Daniel Zeng, Applying associative retrieval techniques to alleviate the sparsity problem in collaborative filtering, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.116-142, January 2004 doi:10.1145/963770.963775
• 3. Zhou, T., Ren, J., Medo, M. and Zhang, Y.C. 2007 Bipartite network projection and personal recommendation. Phys Rev E 76.
• 4. Hyung Jun Ahn, A new similarity measure for collaborative filtering to alleviate the new user cold-starting problem, Information Sciences: an International Journal, v.178 n.1, p.37-51, January, 2008 doi:10.1016/j.ins.2007.07.024.
• 5. Thomas Hofmann, Latent semantic models for collaborative filtering, ACM Transactions on Information Systems (TOIS), v.22 n.1, p.89-115, January 2004 doi:10.1145/963770.963774
• 6. Gori, M. and Pucci, A. 2007 ItemRank: A Random-Walk Based Scoring Algorithm for Recommender Engines. International Joint Conference on Artificial Intelligence.
• 7. Zan Huang, Daniel Zeng, Hsinchun Chen, A Comparison of Collaborative-Filtering Recommendation Algorithms for E-commerce, IEEE Intelligent Systems, v.22 n.5, p.68-78, September 2007 doi:10.1109/MIS.2007.80
• 8. David Liben-Nowell, Jon Kleinberg, The link-prediction problem for social networks, Journal of the American Society for Information Science and Technology, v.58 n.7, p.1019-1031, May 2007 doi:10.1002/asi.v58:7
• 9. Kubica, J., Goldenberg, A., Komarek, P., Moore, A. and Schneider, J. 2003 A comparison of statistical and machine learning algorithms on the task of link completion. KDD Workshop on Link Analysis for Detecting Complex Behavior, 8.
• 10. Francois Fouss, Alain Pirotte, Jean-Michel Renders, Marco Saerens, Random-Walk Computation of Similarities between Nodes of a Graph with Application to Collaborative Recommendation, IEEE Transactions on Knowledge and Data Engineering, v.19 n.3, p.355-369, March 2007 doi:10.1109/TKDE.2007.46
• 11. Huang, Z., Zeng, D. and Chen, H. 2004 A Unified Recommendation Framework Based on Probabilistic Relational Models. 4th Annual Workshop on Information Technologies and Systems.
• 12. Getoor, L. and Sahami, M. 1999 Using Probabilistic Relational Models for Collaborative Filtering. WebKDD.
• 13. Hasan, M.A., Chaoji, V., Salem, S. and Zaki, M. 2006 Link Prediction Using Supervised Learning. Workshop on Link Analysis, Counter-terrorism and Security.
• 14. Karsten M. Borgwardt, Cheng Soon Ong, Stefan Schönauer, S. V. N. Vishwanathan, Alex J. Smola, Hans-Peter Kriegel, Protein function prediction via graph kernels, Bioinformatics, v.21 n.1, p.47-56, January 2005 doi:10.1093/bioinformatics/bti1007.
• 15. Xin Li, Hsinchun Chen, Zhu Zhang, Jiexun Li, Automatic patent classification using citation network information: an experimental study in nanotechnology, Proceedings of the 7th ACM/IEEE-CS joint conference on Digital libraries, June 18-23, 2007, Vancouver, BC, Canada doi:10.1145/1255175.1255262
• 16. Scholkopf, B., Platt, J.C., Shawe-Taylor, J., Smola, A.J. and Williamson, R.C. 1999 Estimating the support of a high--dimensional distribution. MSR-TR-99-87, Microsoft Research.
• 17. Ting-Fan Wu, Chih-Jen Lin, Ruby C. Weng, Probability Estimates for Multi-class Classification by Pairwise Coupling, The Journal of Machine Learning Research, 5, p.975-1005, 12/1/2004,

	Author	volume	Date Value	title	type	journal	titleUrl	doi	note	year
2009 RecommendationAsLinkPrediction	Xin Li Hsinchun Chen			Recommendation as Link Prediction: A graph kernel-based machine learning approach		Proceedings of the 9th ACM/IEEE-CS joint conference on Digital libraries		10.1145/1555400.1555433		2009