# Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution

arXiv: https://arxiv.org/abs/2302.03933 · HTML: https://mlsanity.com/paper/2302.03933/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 77 references that are in the map.
- First posted on arXiv 8 Feb 2023.

## Builds on (most cited first, 29 of 29)

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Self-Attentive Sequential Recommendation](https://mlsanity.com/paper/1808.09781/) (2018)
- [LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation](https://mlsanity.com/paper/2002.02126/) (2020)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [BERT4Rec: Sequential Recommendation with Bidirectional Encoder Representations from Transformer](https://mlsanity.com/paper/1904.06690/) (2019)
- [Neural Graph Collaborative Filtering](https://mlsanity.com/paper/1905.08108/) (2019)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Variational Autoencoders for Collaborative Filtering](https://mlsanity.com/paper/1802.05814/) (2018)
- [Graph Neural Networks with convolutional ARMA filters](https://mlsanity.com/paper/1901.01343/) (2019)
- [Fusing Similarity Models with Markov Chains for Sparse Sequential Recommendation](https://mlsanity.com/paper/1609.09152/) (2016)
- [Fast Matrix Factorization for Online Recommendation with Implicit Feedback](https://mlsanity.com/paper/1708.05024/) (2017)
- [Inductive Matrix Completion Based on Graph Neural Networks](https://mlsanity.com/paper/1904.12058/) (2019)
- [Graph Spectral Image Processing](https://mlsanity.com/paper/1801.04749/) (2018)
- [Provable Inductive Matrix Completion](https://mlsanity.com/paper/1306.0626/) (2013)
- [Kernel-based Reconstruction of Graph Signals](https://mlsanity.com/paper/1605.07174/) (2016)
- [Total Variation Classes Beyond 1d: Minimax Rates, and the Limitations of Linear Smoothers](https://mlsanity.com/paper/1605.08400/) (2016)
- [Towards Open-World Recommendation: An Inductive Model-based Collaborative Filtering Approach](https://mlsanity.com/paper/2007.04833/) (2020)
- [A Class of Prediction-Correction Methods for Time-Varying Convex Optimization](https://mlsanity.com/paper/1509.05196/) (2015)
- [Future Data Helps Training: Modeling Future Contexts for Session-based Recommendation](https://mlsanity.com/paper/1906.04473/) (2019)
- [Dynamic Matrix Factorization with Priors on Unknown Values](https://mlsanity.com/paper/1507.06452/) (2015)
- [Markov Random Fields for Collaborative Filtering](https://mlsanity.com/paper/1910.09645/) (2019)
- [Temporal Graph Signal Decomposition](https://mlsanity.com/paper/2106.13517/) (2021)
- [Song Recommendation with Non-Negative Matrix Factorization and Graph Total Variation](https://mlsanity.com/paper/1601.01892/) (2016)
- [Matrix completion and extrapolation via kernel regression](https://mlsanity.com/paper/1808.00441/) (2018)

## Built on by (most cited first, 1 of 1)

- [EasyDGL: Encode, Train and Interpret for Continuous-time Dynamic Graph Learning](https://mlsanity.com/paper/2303.12341/) (2023)

## Abstract (arXiv)

Inductive one-bit matrix completion is motivated by modern applications such as recommender systems, where new users would appear at test stage with the ratings consisting of only ones and no zeros. We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph, then learn structural graph properties to recover the function from its values on certain vertices -- the problem of graph signal sampling. We propose a class of regularization functionals that takes into account discrete random label noise in the graph vertex domain, then develop the GS-IMC approach which biases the reconstruction towards functions that vary little between adjacent vertices for noise reduction. Theoretical result shows that accurate reconstructions can be achieved under mild conditions. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain and builds upon a prediction-correction update algorithm to obtain the unbiased and minimum-variance reconstruction. Both GS-IMC and BGS-IMC have closed-form solutions and thus are highly scalable in large data. Experiments show that our methods achieve state-of-the-art performance on public benchmarks.