Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors propose a graph signal sampling approach to matrix completion/recommendation systems. They propose regularization approaches for noise reduction, and also provide a Bayesian extension that takes into account model uncertainty. They show that their approaches are scalable and provide both theoretical guarantees as well as experimental evaluations.  
strength_and_weaknesses: Strengths: 

- The study cited many of the related prior art in a very comprehensive manner
- The core idea of the graph signal sampling approach + regularization is very natural, and admit simple closed form solutions
- reasonable error analysis is given for the method 
- extensive experiments, with good results obtained for the proposed method against competitors 


Weaknesses: 

- the paper jumps directly into describing the problem of inductive 1-bit matrix completion. The motivation is insufficient in my opinion given that this is a very specific problem. I suggest that the authors spend a paragraph at the beginning talking about WHY the 1-bit formulation is helpful and why inductive matrix completion is useful so a broader audience can be reached. 

- The "Bayesian" formulation, is not described clearly and sufficiently. The authors jump straight to describing a stochastic filtering problem and their prediction correction algorithm. There is minimal description of notation, and there is 0 discussion of model choice and why this model is sensible and as well as the choice of parameters such as Sigma_nu and Sigma_eta. For those who are not familiar with this model/literature, it can be very confusing what the prior is and why the proposed filtering algorithm works.

- Without more significant exposition for the Bayesian model, the current Bayesian model reads more like a distraction from the main theme of the paper.

I think the paper's readability and clarity would be greatly improved if the authors address the two issues above. 


Minor Typos:

I think in the first paragraph of the first page, "a subset of positive examples phi randomly sampled from {(i, j) | ... .}" I think inside the set, in addition to j \leq m, there should also be i \leq n

 
clarity,_quality,_novelty_and_reproducibility: - The paper is written moderately clearly. To a person with less experience in related areas, this paper could be very difficult to follow, given their very condensed style of presentation. I gave suggestions to the authors to improve their exposition. 

- the idea is original, in the sense that there is nothing ground-breaking that has been proposed, but the authors have managed to combine lots of different existing ideas from different sub-fields to come up with something reasonably new. 
summary_of_the_review: Overall, the authors proposed a reasonable and novel method for inductive 1-bit matrix completion using ideas from graph signal sampling. The main issue currently is their exposition. It could be a good paper if the authors improve their exposition, especially on their motivation of the inductive 1-bit matrix completion problem as well as their description of their "Bayesian" model.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper studies the problem of one-bit matrix completion. The paper claims to propose a unified graph signal sampling framework that enjoys the benefits of graph signal analysis and processing. The authors provide some theorems related to the quality of reconstruction.
strength_and_weaknesses: Due to either: the lack of my knowledge in this area, or: the writing of the paper, I cannot understand what problem this paper tries to solve. I understand what one-bit matrix completion is, but I do not understand, at least from the first three Sections, how it is "unified" with graph signals or graph Laplacians. This is reflected in my confidence rating. 

See Clarity, Quality, Novelty And Reproducibility for details.

- How should readers interpret the conditions in Theorem 3 and 4? Can the authors provide some examples in which they hold? Do these conditions hold in the experiments?
clarity,_quality,_novelty_and_reproducibility: It is hard to follow even the first paragraph. This is hurting the readability of the whole paper. 

- Why M has an extra column? What is the relationship between M and y? 

- Since s is just a noisy version of y by flipping digits, is it necessary to define \xi in this manner, instead os saying something simple as "s_i = y_i with probability 1-\rho, and 1 - y_i with probability \rho"? As a reference, [1] defines the same mechanism in a much clearer way.

- Despite of saying "It is obvious now that the problem of inductive 1-bit matrix completion is equivalent to recovering clean y from corrupted s", I don't see the formal definition of the problem. What is the relationship between y and M, R, \Phi? It should be self-contained for readers.

References:
- [1] Davenport, Mark A., et al. "1-bit matrix completion." Information and Inference: A Journal of the IMA 3.3 (2014): 189-223.
summary_of_the_review: The paper is hard to understand in the current shape.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: Authors extend graph signal processing techniques to cope with discrete random label noise. 

strength_and_weaknesses: Strength: Authors consider a useful application of graph signal processing to recommender systems. 

Weaknesses: 
* The main contributions of the paper are unclear. Is it a novel graph signal model ? Is it a novel graph signal recovery method (Eq. (5)) ? 

* At least in its application to recommender systems I would like to see a comparison of the proposed methods with existing network Lasso methods as proposed e.g. in 

N. Tran, H. Ambos and A. Jung, "Classifying Partially Labeled Networked Data VIA Logistic Network Lasso," ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), 2020, pp. 3832-3836, doi: 10.1109/ICASSP40776.2020.9054408.

A. Jung, "Networked Exponential Families for Big Data Over Networks," in IEEE Access, vol. 8, pp. 202897-202909, 2020, doi: 10.1109/ACCESS.2020.3033817.

* Theorem 3 needs more discussion. How to choose the parameter k ? How restrictive is the Poincare condition ? Is this condition satisfied in the numerical experiments ? 

* The problem formulation needs to be made more precise and placed earlier in the paper. Currently it seems only described in Section 4.1. which is too late. 

* What is \hat{y} in (9) ? 

* Pls explain more clearly the probability distribution underlying the expectation in Eq. (9). 

* Pls discuss more explicitly how the graph (Laplacian) has been obtained for the numerical experiments. 

* "The classical sampling theorem states that functions..." what is the "classical sampling theorem" ? 


minor errors: 

* "...the testing phrase,.." 

* "..experiments, we define the hypergraph using matrix R.." unclear what the matrix R is/how obtained. 

* "..methods are not well suited to our 1-bit matrix completion problem due to the issues of 1-bit quantization..." pls try to be more specific. what are these "issues" ? 


clarity,_quality,_novelty_and_reproducibility: see above
summary_of_the_review: see above
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper studies the problem of one-bit completion: the task is to recover a vector $y \in \\{0, 1\\}^n$ from the observation of a subset of its positive entries. The model assume that there exists a matrix $R \in \\{0, 1\\}^{m \times n}$ containing additional information about the model, e.g. $m$ previous partial observations of similar data.

The main idea is that this matrix $R$ can be turned into a graph on $n$ vertices, whose weights represent the similarity between vertices. The completion problem can thus be cast as a graph signal sampling problem using the laplacian $L$ of the graph: the general assumption is that $y$ is mostly concentrated on the low-frequency eigenvectors of $L$. 

Next, the authors study the on-line version of this problem, where the observations can be noisy. In this case, they propose a Bayesian algorithm that assumes the noise is Gaussian in the Fourier basis of $L$. This is an adaptation of prediction-correction-update algorithms to the case of (0, 1) observations.

Finally, they propose several experiments to gauge the performance of their algorithms. The first part compares it to other graph-based methods, and the second part to more complicated (e.g. transformer-based) sequential recommendation algorithms. In the first case, the Bayesian version BGS-IMC is shown to mostly outperform its counterparts, while in the second case, the performance is comparable (sometimes slightly worse) than other architectures but the runtime is much lower.
strength_and_weaknesses: The main strengths of the proposed algorithms are their scalability and explainability: since they are fairly simple to implement (the first one even has a closed-form solution), they are much faster than heavier neural network counterparts; and on the other hand even the learned elements of the algorithms (such as the covariance matrices of BGS-IMC) can have interesting interpretations. The algorithms are quite thoroughly studied, with ablation and scalability studies performed in the appendix.

On the other hand, the paper is very hermetic for people that are not familiar with the setting and state of the art; it took me quite a long time to grasp the exact setting of the original problem. The introduction to BGS-IMC suffers the same problem : it is hard to understand exactly what $\Delta s$ is, and why the model is setup that way. Overall, this paper needs significant work to make it accessible beyond non-experts of the field.
clarity,_quality,_novelty_and_reproducibility: **Novelty**: the GS-IMC algorithm seems to be a straightforward generalization of SGMC (Chen et al.), with very similar performance. There are however some novel consistency results (one on the effect of bandwidth limiting, and the other on the effect of noise). To the best of my knowledge, the BGS-IMC is completely novel in one-bit completion, and is the main innovation of the paper.

**Clarity/Reproducibility**: here are some more precise remarks on the clarity issues
- Model definition: the presentation at the beginning of the paper is very confusing; the link between $M, R, y$ and $s$ is hard to grasp, and would benefit from a much more formal presentation similar to the one of graph sampling. In particular, the noise model is unclear : are bits only flipped from 1 to 0, or can there be opposite flips ?
- BGS-IMC : the setup is again slightly confusing. I don't exactly understand why you introduce two variables $x$ and $z$, when the difference between them is simply some additive noise; in general I feel like Equations (11) and (12) need more explanation. On the other hand, once we accept the model, the rest is fairly straightforward and explained well.
- Experiments: again, the experimental setup may need more explanation; the metrics in Tables 3 and 4 are not defined, especially the `@50` or `@100` suffixes. I also didn't see which regularizer $R$ was used to produce the results in the tables. However, I really appreciate the effort to made the algorithms compared against as efficient as possible.

*Minor remarks**: 
- Figure 2 (and 4-6): the algorithm names are wrong
- throughout the paper (mainly in section 4, see e.g. Eq. 18 and below Eq. 15), $A^-$ instead of $A^{-1}$ is used for inverting matrices; or is that another operation ?
summary_of_the_review: This is a very interesting paper, that introduces a framework for one-bit completion that's both efficient and comparable to SOTA accuracy. However, it is for now not accessible beyond a very small subset of experts, and needs clarity changes to broaden its appeal.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The paper attacks the inductive one-bit matrix completion problem using a graph signal processing perspective, and presents algorithms for the offline and online settings. Both algorithms have closed form solutions, are scalable, and come with theoretical guarantees. The method compares favorably experimentally against competitors.
justification_for_why_not_higher_score: The approach applies GSP to inductive one-bit matrix completion. The methodology is sound and useful, but not novel enough to justify spotlight.
justification_for_why_not_lower_score: The methodology is sound and useful, comes with theoretical guarantees, and performs favorably compared to baselines.
Decision: Accept: poster