Learning multiple graphs for document recommendations

ABSTRACT

The Web offers rich relational data with different semantics. In this paper, we address the problem of document recommendation in a digital library, where the documents in question are networked by citations and are associated with other entities by various relations. Due to the sparsity of a single graph and noise in graph construction, we propose a new method for combining multiple graphs to measure document similarities, where different factorization strategies are used based on the nature of different graphs. In particular, the new method seeks a single low-dimensional embedding of documents that captures their relative similarities in a latent space. Based on the obtained embedding, a new recommendation framework is developed using semi-supervised learning on graphs. In addition, we address the scalability issue and propose an incremental algorithm. The new incremental method significantly improves the efficiency by calculating the embedding for new incoming documents only. The new batch and incremental methods are evaluated on two real world datasets prepared from CiteSeer. Experiments demonstrate significant quality improvement for our batch method and significant efficiency improvement with tolerable quality loss for our incremental method.

REFERENCES

• 1: F. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
• 2: F. Chung. Laplacians and the cheeger inequality for directed graphs. Annals of Combinatorics, 9, 2005.
• 3: David Cohn , Huan Chang, Learning to Probabilistically Identify Authoritative Documents, Proceedings of the Seventeenth International Conference on Machine Learning, p.167-174, June 29-July 02, 2000
• 4: D. Cohn and T. Hofmann. The missing link - a probabilistic model of document content and hypertext connectivity. In T. K. Leen, T. G. Dietterich, and V. Tresp, editors, Advances in Neural Information Processing Systems 13, pages 430--436. MIT Press, 2001.
• 5: S. C. Deerwester, S. T. Dumais, T. K. Landauer, G. W. Furnas, and R. A. Harshman. Indexing by latent semantic analysis. Journal of the American Society of Information Science, 41(6):391--407, 1990.
• 6: M. Fazel, H. Hindi, and S. P. Boyd. Log-det heuristic for matrix rank minimization with applications to hankel and euclidean distance matrices. In Proceedings of American Control Conference, 2003.
• 7: R. Guha , Ravi Kumar , Prabhakar Raghavan , Andrew Tomkins, Propagation of trust and distrust, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA [doi>10.1145/988672.988727]
• 8: X. He, H. Zha, C. H. Q. Ding, and H. D. Simon. Web document clustering using hyperlink structures. Computational Statistics & Data Analysis, 41(1):19--45, November 2002.
• 9: Thomas Hofmann, Unsupervised learning by probabilistic latent semantic analysis, Machine Learning, v.42 n.1/2, p.177-196, Jan. 2001 [doi>10.1023/A:1007617005950]
• 10: 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]
• 11: Badrul Sarwar , George Karypis , Joseph Konstan , John Reidl, Item-based collaborative filtering recommendation algorithms, Proceedings of the 10th international conference on World Wide Web, p.285-295, May 01-05, 2001, Hong Kong, Hong Kong [doi>10.1145/371920.372071]
• 12: Fei Wang , Sheng Ma , Liuzhong Yang , Tao Li, Recommendation on Item Graphs, Proceedings of the Sixth International Conference on Data Mining, p.1119-1123, December 18-22, 2006 [doi>10.1109/ICDM.2006.133]
• 13: Jun Wang , Arjen P. de Vries , Marcel J. T. Reinders, Unifying user-based and item-based collaborative filtering approaches by similarity fusion, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148257]
• 14: Kai Yu , Anton Schwaighofer , Volker Tresp , Xiaowei Xu , Hans-Peter Kriegel, Probabilistic Memory-Based Collaborative Filtering, IEEE Transactions on Knowledge and Data Engineering, v.16 n.1, p.56-69, January 2004 [doi>10.1109/TKDE.2004.1264822]
• 15: H. Zha, C. Ding, M. Gu, X. He, and H. Simon. Spectral relaxation for k-means clustering. In Neural Information Processing Systems, volume 14, 2001.
• 16: Dengyong Zhou , Christopher J. C. Burges, Spectral clustering and transductive learning with multiple views, Proceedings of the 24th international conference on Machine learning, p.1159-1166, June 20-24, 2007, Corvalis, Oregon [doi>10.1145/1273496.1273642]
• 17: D. Zhou, I. Councill, H. Zha, and C. L. Giles. Discovering temporal communities from social network documents. In ICDM?07: Proceedings of the 7th IEEE International Conference on Data Mining, 2007.
• 18: Dengyong Zhou , Jiayuan Huang , Bernhard Schölkopf, Learning from labeled and unlabeled data on a directed graph, Proceedings of the 22nd international conference on Machine learning, p.1036-1043, August 07-11, 2005, Bonn, Germany [doi>10.1145/1102351.1102482]
• 19: Ding Zhou , Eren Manavoglu , Jia Li , C. Lee Giles , Hongyuan Zha, Probabilistic models for discovering e-communities, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland [doi>10.1145/1135777.1135807]
• 20: Shenghuo Zhu , Kai Yu , Yun Chi , Yihong Gong, Combining content and link for classification using matrix factorization, Proceedings of the 30th annual international ACM SIGIR conference on Research and development in information retrieval, July 23-27, 2007, Amsterdam, The Netherlands [doi>10.1145/1277741.1277825]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Information filtering

General Terms:
Algorithms, Experimentation

Keywords:
collaborative filtering, recommender systems, semi-supervised learning, social network analysis, spectral clustering