Scalable and Explainable 1-Bit Matrix Completion via Graph Signal Learning

Authors

  • Chao Chen MoE Key Lab of Artificial Intelligence, AI Institute, Shanghai Jiao Tong University, Shanghai, China
  • Dongsheng Li School of Computer Science, Fudan University, Shanghai, China Microsoft Research Asia, Shanghai, China
  • Junchi Yan MoE Key Lab of Artificial Intelligence, AI Institute, Shanghai Jiao Tong University, Shanghai, China Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China
  • Hanchi Huang MoE Key Lab of Artificial Intelligence, AI Institute, Shanghai Jiao Tong University, Shanghai, China
  • Xiaokang Yang MoE Key Lab of Artificial Intelligence, AI Institute, Shanghai Jiao Tong University, Shanghai, China

Keywords:

Learning Preferences or Rankings, Recommender Systems & Collaborative Filtering, Matrix & Tensor Methods

Abstract

One-bit matrix completion is an important class of positive-unlabeled (PU) learning problems where the observations consist of only positive examples, e.g., in top-N recommender systems. For the first time, we show that 1-bit matrix completion can be formulated as the problem of recovering clean graph signals from noise-corrupted signals in hypergraphs. This makes it possible to enjoy recent advances in graph signal learning. Then, we propose the spectral graph matrix completion (SGMC) method, which can recover the underlying matrix in distributed systems by filtering the noisy data in the graph frequency domain. Meanwhile, it can provide micro- and macro-level explanations by following vertex-frequency analysis. To tackle the computational and memory issue of performing graph signal operations on large graphs, we construct a scalable Nystrom algorithm which can efficiently compute orthonormal eigenvectors. Furthermore, we also develop polynomial and sparse frequency filters to remedy the accuracy loss caused by the approximations. We demonstrate the effectiveness of our algorithms on top-N recommendation tasks, and the results on three large-scale real-world datasets show that SGMC can outperform state-of-the-art top-N recommendation algorithms in accuracy while only requiring a small fraction of training time compared to the baselines.

Downloads

Published

2021-05-18

How to Cite

Chen, C., Li, D., Yan, J., Huang, H., & Yang, X. (2021). Scalable and Explainable 1-Bit Matrix Completion via Graph Signal Learning. Proceedings of the AAAI Conference on Artificial Intelligence, 35(8), 7011-7019. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/16863

Issue

Section

AAAI Technical Track on Machine Learning I