Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of estimating bipartite graphs with low rank structures. The authors develop several simple estimators for estimating the connectivity matrix and its column and row space, based on singular value thresholding. The optimal rates are established by deriving the matching minimax lower bounds and upper bounds.
main_review: The main contributions of this paper focus on theoretical parts. More specifically, the authors establish the optimal rates for estimating the connectivity matrix and its column and row space. The minimax optimal rate is a fundamental problem in parameter estimation. To achieve this, the upper bound is derived by designing some estimators based on singular value thresholding. The minimax lower bound is obtained by applying Fano’s inequality in a subset of the parameter space. 

limitations_and_societal_impact: There are several points listed to be clarified.

1. The authors should make clear the motivation of estimating the connectivity matrix of a bipartite graph, as well as its column and row space. In particular, it is unclear the motivation of the setting of the problem considered, i.e., Eq. (1). Does there exist similar problem setting in the literature? Is the reason why the authors focus on bipartite graphs just that its connectivity matrix can be represented by an n_1 \times n_2 matrix?

2. The minimax lower bound and upper bound are usually provided in the expectation form. The authors are suggested to provide the bounds of the expectation of the estimation error in theorems.

3. There are four parameters, n_1, n_2, p, and r, in constructing the parameter space. The authors should clarify clearly the dependence of those parameters with each other in establishing the optimal rate, to make sure that all the dependence conditions are compatible.

4. In Theorem 3, the authors should provide the lower bound of n_1, but not just claim that n_1 is sufficiently large.

5. In Theorem 5, the authors claim that the constant C_0 should be sufficiently large. What is the condition on C_0? Is it compatible with another condition stated in the theorem, r \leq n_1 / C_0?

6. It is observed that some numbers stated in Theorem 3 are not consistent with the ones in its proof. In addition, the authors should provide more details in proving Lemma 1.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of learning a random bipartite graph with sparse connectivity matrix M. They show that the performance of estimating the matrix M depends on the sparsity, and focus on two types of performance: the error of estimating M and the error of estimating the column space of M. They show that the estimators achieve the minimax optimal rate.
main_review: The result of this paper is novel in that the authors uses algorithms similar to universal singular value thresholding and soft singular value thresholding, but provide the minimax lower bounds for the error estimation. I think the singular space estimation bounds are of great value to the statistics community, however for the larger NeurIPS audience, I find that more applications and experiments on applications, (such as clustering), should be discussed. Also, the paper is most probably confusing to read as the problem statement is not written clearly, hence it would be better if that was done, as well as a clear set of main contributions to be written out in the introduction of the paper in point form, that is distinct from the literature review. 
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors discuss the estimation of a connectivity matrix M \in [0,p]^{n_1 \times n_2} based on one instance of a generated random bipartite graph where node i of the one part is connected with node j of the other part with probability M_{i,j}. The authors discuss estimation of M in terms of operator and Frobenius norm, as we all estimation of the singular space of M.

The authors provide tight minimax results for all three notions of recovery. Their upper bounds are through a relatively (regularized) simple singular value thresholding (SVT) algorithm, not far from the well-known in the field universal singular value thresholding algorithm (USVT) by Chaterjee. 
main_review: ## Originality

I think the results in this work are original, but I could be missing some part of the literature. The results are definitely naturally highly overlapping with results/methods from literature of estimating SBMs and graphons but yet offer a new insight that I have not encountered before because of the bipartite structure. 

That being said, the bipartite structure appears to make many things more tractable from a mathematical point of view. This, for example, is obvious in the lower bounds for the Frobenius/operators norms (Appendix C) where the construction is far easier than similar lower bound construction in the context of graphons (see e.g. (Klopp, Tsybakov, Verzelen : Oracle inequalities for network models and sparse graphon
estimation, 2015) and (Mcmillan, Smith: When is nontrivial estimation possible for Graphons and Stochastic Block Models?, 2016)).

## Quality/Clarity

The paper is of good quality, the statements are clean and the proofs as far as I checked are clear and make sense. One aspect of the results that confused me it is that the lower bound for the singular space estimation (Theorem 5) is a lower bound in expectation, while the upper bound (Theorem 4), please explain more on why this is the case and how/whether it can be resolved.  
Presentation-wise, one aspect of the result that would help is an interpretation of the rates. For example, a natural rate appearing in parameter estimation problems is the so-called parametric rate (see for example the discussion in (Gao, Lu, Zhou Rate-optimal graphon estimation, 2014). My understanding is that in the case of the Frobenius norm the rate n_1pr indeed corresponds to the parametric rate and that explains a lot. Also, the dependence on p is not as surprising, as it is similar to the one appearing in Klopp, Tsybakov, Verzelen (2015) and Mcmillan, Smith (2016) for SBMs.

## Significance

If I am correct that the results are accurate, I think the results are significant. There is a large literature in rate-optimal estimation of various graphon structures, but the simpler bipartite case seems to be missing. The authors close this gap. Yet, I really think the authors should work more on positioning their paper in the literature.


## Missing literature

The authors seem to miss some important references that are similar to the present work, and a deep comparison between the results is necessary to appreciate the results. For a dense setting, (Gao, Lu, Zhou Rate-optimal graphon estimation, 2014) establish the tight rate for SBM with r blocks. This corresponds to the case where p=constant in the submitted paper. Of course in the submitted paper the model is not an SBM and it is bipartite. But how do the results compare? How are they different?

Similarly, the sparse case has been studied for SBM by Klopp, Tsybakov, Verzelen (2015) and Mcmillan, Smith (2016)). Please compare the results and highlight the significance and new insights.
limitations_and_societal_impact: I mentioned the limitations above. I see no potential negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study the problem of estimating the connectivity matrix $M \in [0,1]^{n_1 \times n_2}$ of a random bipartite graph (with $n_1 \times n_2$ vertices) given independent observations $A_{ij} \sim Bernoulli(M_{ij})$ for $(i,j) \in [n_1] \times [n_2]$. Assuming M is low rank, they consider algorithms based on singular value thresholding (Algs. 1, 2) and derive estimation error bounds (in the operator and Frobenius norms) in Theorems 1, 2. These bounds are shown to be optimal in Theorem 3. Moreover, the bounds in Theorem 1 are then used to bound the error in estimating the column space of M (Theorem 4), which are shown to be optimal in Theorem 5.
main_review: The paper studies an interesting problem which is important in practice since bipartite graphs appear in many applications. The results are in general presented in a clean manner. However, the quality of writing really needs to be improved throughout since there are quite a few grammatical mistakes. I also have some detailed remarks which I have listed below.

(1)	The regularization scheme used in Algos. 1, 2 is quite standard in the literature and is used, for instance, to show concentration of sparse inhomogeneous Erdos Renyi graphs [1]. It will be helpful to discuss this so that the reader has better perspective. 

(2)	Theorem 1 is under the setting $n_1 \geq n_2$ and it is mentioned at the beginning of Section 2 that this is w.l.o.g. Also, theorem 4 is written in a more general form without this assumption so it might be better to do the same for Theorem 1 as well, for consistency. It wasn’t clear to me why the lower bound in Theorem 5 requires $n_1 \geq n_2$, and although there is a discussion in Section 5, some additional discussion would be helpful.

(3)	Currently, there is no sketch of the proof ideas in the main text for any of the theorems. I made a brief pass of the appendix to go through the steps, but it will be good to add the main ideas within the main text.

(4)	In Section 3, the error definitions in lines 160,161 could be removed since eqs. (10), (11) clearly define the subspace error terms (these are standard). The bound in Theorem 4 should follow in a straightforward manner from Theorem 1 using the Davis-Kahan theorem or Wedin’s bound, the latter of which is specifically for Singular values/subspaces.

(5)	In Section 3.2, isn’t the definition of $P_M$ simply $U U^T$? The statement of Theorem 5 also seems to have an inaccuracy in the stated conditions since it requires $C_0 r \leq \frac{n_1 n_2p^2}{\sigma_{*}^2} \leq (5/2)^2$ which will typically not be satisfied.

(6)	In the experiments, there are currently no comparisons with other methods from the literature for similar low-rank matrix estimation problems. This would have helped us see how other methods fare in simulations against the proposed methods. 

References:

[1] Le, C.M., Levina, E. and Vershynin, R. (2017), Concentration and regularization of random graphs. Random Struct. Alg., 51: 538-561.

---------------------- Post author response -------------------------

I am reasonably satisfied with the response of the authors to my comments, and I will increase my score to 6. I hope the authors will provide a more detailed discussion on the significance of their results in relation to those for related problems in the literature (especially bipartite SBMs).
limitations_and_societal_impact: The authors have addressed the limitations of the results in Section 5.
review_title: null

Meta-review: The reviewers gave very coherent marks to this paper, generally recognizing its quality and the value of its contribution, in particular in filling the gap of identifying minimax optimal estimators for estimation of an average connectivity matrix and of its column space from an observed bipartite random graph with M as its expected adjacency matrix. 
The paper thus appears well suited for acceptance. We recommend that the authors take into account the reviewers' comments especially about positioning their results when preparing the final version.



Decision: Accept (Poster)