PU Learning for Matrix Completion

Abstract

In this paper, we consider the matrix completion problem when the observations are one-bit measurements of some underlying matrix M, and in particular the observed samples consist only of ones and no zeros. This problem is motivated by modern applications such as recommender systems and social networks where only "likes" or "friendships" are observed. The problem of learning from only positive and unlabeled examples, called PU (positive-unlabeled) learning, has been studied in the context of binary classification. We consider the PU matrix completion problem, where an underlying real-valued matrix M is first quantized to generate one-bit observations and then a subset of positive entries is revealed. Under the assumption that M has bounded nuclear norm, we provide recovery guarantees for two different observation models: 1) M parameterizes a distribution that generates a binary matrix, 2) M is thresholded to obtain a binary matrix. For the first case, we propose a "shifted matrix completion" method that recovers M using only a subset of indices corresponding to ones, while for the second case, we propose a "biased matrix completion" method that recovers the (thresholded) binary matrix. Both methods yield strong error bounds --- if M is n by n, the Frobenius error is bounded as O(1/((1-rho)n), where 1-rho denotes the fraction of ones observed. This implies a sample complexity of O(n\log n) ones to achieve a small error, when M is dense and n is large. We extend our methods and guarantees to the inductive matrix completion problem, where rows and columns of M have associated features. We provide efficient and scalable optimization procedures for both the methods and demonstrate the effectiveness of the proposed methods for link prediction (on real-world networks consisting of over 2 million nodes and 90 million links) and semi-supervised clustering tasks.

References in corpus (2)

• BPR: Bayesian Personalized Ranking from Implicit Feedback
• Prediction and Clustering in Signed Networks: A Local to Global Perspective

Cited by in corpus (32)

• Positive-Unlabeled Learning with Non-Negative Risk Estimator
• Efficient Training for Positive Unlabeled Learning
• Federated Learning with Only Positive Labels
• Semi-Supervised Classification Based on Classification from Positive and Unlabeled Data
• 1-bit Matrix Completion: PAC-Bayesian Analysis of a Variational Approximation
• Binary Optimization via Mathematical Programming with Equilibrium Constraints
• SQL-Rank: A Listwise Approach to Collaborative Ranking
• Learning Inter-Modal Correspondence and Phenotypes from Multi-Modal Electronic Health Records
• Distantly Supervised Named Entity Recognition using Positive-Unlabeled Learning
• Fairness-aware Model-agnostic Positive and Unlabeled Learning
• Negative Binomial Matrix Factorization for Recommender Systems
• GAN-based Recommendation with Positive-Unlabeled Sampling
• Robust Cost-Sensitive Learning for Recommendation with Implicit Feedback
• Graph DNA: Deep Neighborhood Aware Graph Encoding for Collaborative Filtering
• Non-linear Attributed Graph Clustering by Symmetric NMF with PU Learning
• Sampler Design for Implicit Feedback Data by Noisy-label Robust Learning
• Nonconvex One-bit Single-label Multi-label Learning
• SetRank: A Setwise Bayesian Approach for Collaborative Ranking from Implicit Feedback
• Binary Matrix Completion Using Unobserved Entries
• Regret Bounds for Non-decomposable Metrics with Missing Labels
• Positive-Unlabeled Classification under Class Prior Shift and Asymmetric Error
• LearningWord Embeddings for Low-resource Languages by PU Learning
• Scalable Unidirectional Pareto Optimality for Multi-Task Learning with Constraints
• Advances in Collaborative Filtering and Ranking
• IdeoTrace: A Framework for Ideology Tracing with a Case Study on the 2016 U.S. Presidential Election
• Fast Large-Scale Discrete Optimization Based on Principal Coordinate Descent
• Heterogeneous network-based drug repurposing for COVID-19
• Log-Normal Matrix Completion for Large Scale Link Prediction
• Binary matrix completion with nonconvex regularizers
• Multi-Label Learning from Single Positive Labels
• One-Bit Matrix Completion with Differential Privacy
• On the Unreported-Profile-is-Negative Assumption for Predictive Cheminformatics