Rate-Optimal Subspace Estimation on Random Graphs
Authors: Zhixin Zhou
Fan Zhou
Ping Li
Cun-Hui Zhang
Venue: NeurIPS 2021 Poster (2021)
Keywords: bipartite graph
network analysis
singular value thresholding
minimax theory

Abstract: We study the theory of random bipartite graph whose adjacency matrix is generated according to a connectivity matrix $M$. We consider the bipartite graph to be sparse, i.e., the entries of $M$ are upper bounded by certain sparsity parameter. We show that the performance of estimating the connectivity matrix $M$ depends on the sparsity of the graph. We focus on two measurement of performance of estimation: the error of estimating $M$ and the error of estimating the column space of $M$. In the first case, we consider the operator norm and Frobenius norm of the difference between the estimation and the true connectivity matrix. In the second case, the performance will be measured by the difference between the estimated projection matrix and the true projection matrix in operator norm and Frobenius norm. We will show that the estimators we propose achieve the minimax optimal rate.

Rate-Optimal Subspace Estimation on Random Graphs
Zhixin Zhou', Fan Zhou', Ping Li,, and Cun-Hui Zhang
Department of Management Sciences, City University of Hong Kong 2Cognitive Computing Lab, Baidu Research Department of Statistics, Rutgers University Ahhizzhou@cityu..co (zfyyde001, pingli98 @gmail.com, cunnhui @ @sta@ sttt.rutgers.edu
Abstract
We study the theory of random bipartite graph whose adjacency matrix is generated according to a connectivity matrix M. We consider the bipartite graph to be sparse, i.e., the entries of M are upper bounded by certain sparsity parameter. We show that the performance of estimating the connectivity matrix M depends on the measurement of performance of estimation:
sparsity of the graph. We focus the error of estimating M and the error of estimating the column space of M. the first case, consider the operator norm and Frobenius norm of the difference between the estimation and the true connectivity matrix. In the second case, the performance will be measured by the difference between the estimated projection matrix and the true projection matrix in operator norm and Frobenius norm. We will show that the estimators we propose achieve the minimax optimal rate.
Introduction
There have been many fruitful results subspace estimation principal component analysis. Re- searchers have been considering random matrix with Gaussian and sub-Gaussian noise. the present work, focus on random bipartite graph, which have been a popular model in machine learning and data mining [26, 11. 19). A bipartite graph is a graph whose vertices can be divided into two disjoint sets, 2/ and V. such that every edge connects a vertex in 24 graph, an edge connecting node E lf to node j E V exists with probability M,j independently. Suppose [24] = nj and [ n2, a bipartite graph can be represented by an adjacency matrix A. whose elements Aij, (i,j) E [R1] x [122] are independent Bernoulli random variables with latent parameters Mj.. In other words, we can focus on the random adjacency matrix with entries
in V. In random bipartite
Aij ~ Bernoulli(M,,) for (i,j) E [n1] x [na] independently.
M with elements M,j is called the connectivity matrix. The goal of this paper is to find the rate optimal estimation of the latent connectivity matrix M and its singular space, under the assumption that M follows certain low-rank structure.
Formally speaking, for the task of estimating matrix M, we consider the following parameter space:
(M1, n22, P. (M E [0, x rank(M) sr} for positive integers 71, 12, r. (2)
In other words, ( T22, r) consists of all ny x n2 matrices with entries between O and p and rank at most To avoid empty parameter space, we always assume min n2). The parameter controls the sparsity of the bipartite graph.
The work of Zhixin Zhou was conducted as postdoctoral rescarcher Baidu Research Bellevue WA. The work Cun-Hui Zhang was conducted as a consulting researcher at Baidu Research Bellevue WA.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

Matrix estimation has been studied under different assumptions. In [7], the author assumes the random matrix has bounded entries. The universal singular value thresholding (USVT) algorithm is proved to be optimal in the parameter space with bounded nuclear norm. In [15], the authors consider a more general parameter space with subexponential random matrices with bounded means. However, their approach is not optimal under our random graph assumption. One-bit matrix completion is considered in [5, 9I, but parameters therein are not necessarily of low rank matrices, so the minimax error is not comparable with that of the family (2) in the present paper. In network analysis problems, the density of network is expected to be sparse. The upper bound of connection probability p in our model (2) plays key role in error rates of the estimation.
When we consider the singular space estimation problem, an extra assumption about the smallest non-zero singular value is required. We define the corresponding parameter space as follows:
p0. (2 P,,, o.) = {M "0.p)" x*2 rran((M) r, (M 2 3..,
(3)
where or (r(M) is the rth largest singular value of M. It is clear that @2 n2, p. p.r, o.) C (n1, n2, p.r). In other words, in the singular space estimation problem, eters in @ (n,, n2, r) whose smallest nonzero singular value is bounded below by 0..
consider param-
Singular space estimation in the Gaussian case has been considered in [4]. To show the optimality of their estimation, they use packing number of Grassmanian manifold provided in [21]. In the random bipartite graph model that consider in this paper, the connectivity matrix M in (3) is a merely
proper subset of the Grassmanian manifold because the entries of M are contained in the interval [0. pl. As consequence, the previous approach fails to calculate the lower bound of the packing number of the parameter space (n n2,, p. r, o.). In the literature of community detection, spectral methods have been applied in clustering tasks random graphs [17, 8, 13, 28, 29, 30J. The authors in the paper [27] consider this problem under information diffusion. However, these works have not focused the optimality of singular space estimation. With the help of recent development in non-asymptotic analysis of random matrices, we propose stochastic approach to compute the minimax lower bound of subspace estimation over the parameter space (3).
Here are some notations we will use in this paper. For real numbers a and b, a V b- = max fa, b) and A b min(a, 6). o, (M) is the rth largest singular value of matrix M. || = (M), i.c., the largest singular value, is the spectral norm of M. ||M]| (E Ef M2,) 1/2 is the Frobenius norm of M. We note that |M f = E Anz 0, (M) Col(M) is the column space of M. Suppose (a1, (2,,02,.... .g...., an) E R", then diag(a) is
X n diagonal matrix with entries 01, 0g, ..... an on the diagonal. For positive integer n, [n] := {1, ...,.....i, n). For positive sequence an and bns if there exists a constant C such that a, S Cb2 for all n, then we write On O(ba) or an S bn If a, = (br,) and bn = O(a,), ), then we write a, = (br)) If on /b, - 0 as n -> co, then we write a, = o(b,) a, < bn- When discuss asymptotic properties, consider min minfn1, n2) -> oc, iee, the size the bipartite graph tends to infinity.
The rest of this paper is organized as follows. In Section 2, we introduce the algorithm for matrix estimation problem and also provide theoretical analysis for the error rate and minimax lower bound of this problem. Applying the result of matrix estimation, we propose the algorithm for column and row space estimation in Section 3. Then we show that the algorithm outputs estimator with minimax optimal error rate. Numerical experiments discuss some possible future works in Section 5. The proofs of the thcorems can be found in the supplementary material.
the algorithms appear in Section 4. We
2 Low Rank Matrix Estimation of Random Graph
Given a matrix assuming that the connectivity matrix has low rank. To be more specific, in this section, consider the task of low rank matrix estimation parameters belong to the space
random bipartite graph, we aim to estimate true connecting probability of the adjacency
+ (11, T2, P, r) {M E [0. [0.p]" p]" rank((M= S <r}
from (2). Without loss of generality, we assume n, 2 mz in this section. We recall that a random bipartite graph with adjacency matrix A is observed, and Aij ~ Bernoull((M,)) independently for (i,j) E [n]] x [n2]. We will first proposed the algorithm to estimate M. then we will show the optimality of this estimator in the minimax sense.

---

2.1 Hard Singular Value Thresholding
We first introduce the algorithm to compute the estimator M. The hard thresholding procedure is similar as universal singular value thresholding proposed [7]. However, our algorithm specifically designed for random graph, which leads to tighter enror rate. The algorithm first applies degree truncation on bipartite adjacency matrix A, then compute the best low rank approximation on the resulting matrix by singular value decomposition (SVD). For ny x n2 matrix X, and recall that we assume 1 2 n2,, the SVD of X defined by
X=
U.V. UAVT
where
U U= U2., Und); =
Tnz); and V (V1, 2,...., V.)
with singular values 01 2 02 2 ... Ons Now we are ready to present Algorithm | for estimating M by hard singular value thresholding.
Algorithm 1 Hard Singular Value Thresholding
1: Input: adjacency matrix A, sparsity parameter rank r.
2: Output: the estimate of M, M.
3: Set r'
[nzp]-
4: If the degree of any row or column of A is greater than 2n,p, replace a subset of I's in such rows and columns by 0 so that the column-degrees and the row degrees of the resulting matrix are bounded by 2n ip. We call this regularized matrix Are-
5: Let M be the best rank-r' approximation of Aşe composed of the first r' SVD components with the largest singular values. (More details of this step will be discussed later in this section.
Remark 1. Suppose the rank of the connectivity matrix M is as large as the maximal expected row degree n2p, then it is not sufficient propose low rank approximation. In this case, the rate of the estimation error will be the same trivial estimation with M A. Step 3 in this algorithm plays role as checking if r is sufficiently small.
Remark 2. We note that the regularization in step 4 is necessary to achieve the optimal error rate. See experimental and theoretical result in [16]. is worth noting that the regularization method presented in the algorithm is the unique one. Besides replacing the entries by zeroes, we can multilyy the columns and rows by a small constant so that the degree is bounded by 2n1p. Applying this method, the regularized adjacency matrix loses less information, so the estimation more accurate. The threshold of regularization can be replaced by cn,p rather than 2n.p. In most cases, the best e can be smaller than 2, though the theoretical estimation error rate cannot be improved by choosing the optimal c. We will discuss the choice of e by simulation in Section 4.
We will describe more details in finding best rank-r' approximation in step 5. Suppose the regularized adjacency matrix Are from step has SVD
n2
Ax
,.V.V.
with singular values 01 2 02 2 2 Ongy then we define the estimator M to be the best rank-r' approximation A
M Σ T.U.V.
We note that M does not necessarily belong to the parameter space (1,,,, but there is no further operation that can improve the error rate in the next theorem.
Now we are ready to present the high probability bounds for estimation of M. The error will be measured by both operator norm ||M Ml and Frobenius norm ||M Ml]r. The upper bounds of the error rate are shown in the following theorem.
3

---

Theorem 1. Given the adjacency matrix A generated by parameter M from space n2, P,, and assuming n2, the estimator M obtained from Algorithm I satisfies
sup
P( P[ M Z (nip) A (minzp²)) S nni;
(4)
sup M (n (2....)
P [I M z (nipr) A (min2p²)) S n2 1
(5)
This theorem shows that if we consider the average loss of estimating entries of M.
M
M|
Ap²
n2
holds with high probability long as the dimension of the matrix tends to infinity, p² is trivial upper bound since this can obtained by letting M = long as r o(n2p), the low rank structure of M leads to better bound in entrywise loss. This coincides with the discussion in Remark 1.
This upper bound has also been studied in [13, 28). The authors applied their result for community detection when the number of communities are sufficiently smaller than the average degree of the graph. However, the term n. n2pp is missing in previous works.
Without the Step in Algorithm 1, (4) can still achieve the error rate (mip) V (log n1)] (nin2p²) with high probability. One can check the technical reason from the concentration of random graph without regularization in [10, 17, 16]. However, this error rate cannot achieve the minimax lower bound in Theorem 3.
Remark 3.
2.2 Soft Singular Value Thresholding
Soft singular value thresholding [3, 15, 6] can also be applied to estimate the connectivity matrix M. Hard thresholding truncates the smallest r' singular value to O, where r' is defined in step 3 of Algorithm 1. In the soft thresholding approach, Algorithm shrinks all singular values towards zero.
Algorithm 2 Soft Singular Value Thresholding
Input: adjacency matrix A, sparsity parameter p. rank
2: Output: the estimate of M, M.
3: Set r' A [n2p]]
4: Apply regularization (step of Algorithm 1) on to obtain Are- UAV V be the SVD of Are where A 02, ong). 6: Let Å diag( 0r++1) V 0,,, (02 0141) VO,..., (OnyAnz ax++1) V 0)-
5: Let A,e
7: Let M UÁVT.
Theorem 2. Under the same assumptions in Theorem 1, the estimator M obtained from Algorithm 2 satisfies (4) and (5).
Theorem and Theorem show that both hard and soft singular value thresholding methods provide consistent estimation of M to a constant factor. Essentially, the estimator M in each algorithm is a low rank matrix satisfying || 2 & (Mip) A (minzp?) with high probability.
2.3 Minimax Lower Bound
Theorem and Theorem provide high-probability upper bound for the estimation in M. We now establish lower bounds for the estimation error measured by operator norm and Frobenius distance. We will show that the high probability bounds in (4) and (5) are minimax optimal in the next theorem. Theorem 3. Suppose nı 2 n2 and nı is sufficiently large, then
P(IM - M 2 (mip) (m1n2p?)
1
inf sup
(6)
M McOI(mL
inf sup M 1
P P(IM M 2 (mipr) A (min2p²)
2 2

---

Here, the infimum is over all estimators depending on A. and r. (6) shows that there is no estimator can achieve a high probability bound better than (((pp) A (ninep²)) when we measure the estimation error by operator norm. This lower bound can be extended to random tensor [31]. Similarly; (7) shows the minimax optimality in Frobenius norm. We note that the numerical constants hidden in the notation Z is smaller the ones hidden in the notation S in (4) and (5).
These lower bounds are comparable with [15, Theorem 5]. Although in their paper, the authors consider Gaussian noise rather than Bernoulli random variables, the construction of packing number in the proofs are similar. Nevertheless, the upper bound and lower bound in their paper does not match if the entrywise standard deviation and max.,j [Mayl are not asymptotically equivalent. In the situation of random graph, we assume that max,,j |M4yl p. then p < pp(l p) if the random graph is sparse, i.e., p & 1. In this case, the minimax lower bound in [15] is suboptimal. Theorem resolves this issue and show that Algorithm and Algorithm 2 return optimal estimator in the random bipartite graph problem.
2.4 Comparison with Stochastic Block Models and Graphon Models
Popular models on random graphs including stochastic block models (SBM) and graphon models have been investigated in previous work. There have been wonderful results on these models in literature. We will discuss the relationship of the previous results with our current work.
In SBM, the probability of the existence of an edge only depends on the membership of its incident nodes. We consider the SBM on bipartite graph in [29]. Suppose there are K communities in U and L communities in V. then the connectivity matrix M consists of most KL many distinct entries. The rank of M is at most K A L. To simplify the discussion. we assume r K L. SBM can be considered as a low-rank model, but the parameter space of SBM is much smaller than ① (m1, 12. P.r). r). There are about (n1 + 722)r parameters in the low-rank model, while there are only 22 parameters in SBM, i.e., one parameter for each block. Given the size of the random bipartite graph is the same, average, there are less random Bernoulli observations for estimating each parameter the low-rank model. Therefore, the error rate in matrix estimation on SBM [12, 14] is tighter than low-rank model. Since SBM is low-rank model, spectral methods have been applied to SBM. The spectral clustering SBM typically applies K K-means type algorithms on M to obtain consistent community labels [20, 8, 25, 17, 13, 28).
The parameter space of graphon models is characterized by smoothness conditions on continuous function. The details can be found in [12, 14]. In these papers, the authors use the connectivity matrix in SBM to estimate the function in the graphon model. The number of the blocks in SBM depends on the smoothness assumption of the graphon. It worth noting that estimating graphon by a connectivity matrix in SBM is not computationally feasible. In another paper [23], spectral methods are applied to graphon estimation, but they fail to achieve the optimal rate.
Singular Space Estimation
In this section, we will study the estimation of column and row spaces of parameter M. This task is closely related to the estimation M which has been studied in the previous section. Compared with the parameter space O (f1, 12, p. )), it additionally requires o (M) to be bounded away from zero, where o, (M) is the rth largest singular value of M. This is a necessary condition to distinguish the subspace associated with top singular values from its normal space. We recall the parameter space from (3);
o.) = {M E [0 rank(M) = r. r.o,((M) 2 J.}.
For M E (0,1,, o.), M M E [0, n2p" 2 m1x1, Therefore.
A1Anz
ninapp tr
(M M
Σ
Of o2..
(8)
Hence, a. S Ri3e p is necessary condition for the parameter space @2(n1, m2, r,., being nonempty. Recall that we assume the observed bipartite adjacency matrix follows the distribution
Ai ~ Bernouli((M,;) for (i, E [m x [12]] independently.
5

---

We aim to recover the top-r left and right singular vectors. Due to the symmetry of the column and row space, we will focus left singular vectors the following discussion. Let
M Σ (M)U.V
be the singular value decomposition of M. Our goal is recover the subspace spanned by {Ul,..., Let U = (U1)-U,,,. (UI,..., U,). Since the columns of U are singular vectors of M, U has orthogonal columns. Suppose the estimator Ü also has orthogonal columns, then the projection matrices onto columns spaces of U and Ü are UUT and ÜÙ respectively. The loss in operator norm and Frobenius norm are defined by
Lop U) = - UUTIC l and LF(U,U) = HÜU -U lr.
(9)
We similarly define the loss of row space estimator by Lop(V, V) and LF(V, V).
Remark 4. Due to the identifiability issue, we cannot directly compare the true basis of the column space M with the estimator U. In this paper, we use the difference between the projection matrices corresponding to different subspaces measure the estimation error. There are other norms using in literature, for instance, the sin O distance
sin ( U) -
where Ú1 has orthonormal columns which spans the normal space of Col(U). Another possible measurement of distance between U and Ú
inf | -U-
OEO,
Here, the norm || can be either the operator norm or the Frobenius norm, and O, represents the set of r orthogonal matrix. It is shown in [4] that these two norms are equivalent the metric on the difference between projection matrices defined in (9).
3.1 Singular Subspace Estimation and Upper Bound
We consider rank truncation algorithm. Algorithm we first obtain the estimator M from Algorithm or Algorithm 2, then we collect the top singular vectors of M. The subspace spanned by these singular vectors is the estimation of the column space of M. Similarly ,the algorithm can output the row space of M.
Algorithm 3 Singular space estimation
Input: adjacency matrix A, sparsity parameter p. rank r.
2: Output: the estimate of the column space and row space of M.
3: Let M be the output of Algorithm or Algorithm 2.
4: Let Ü = (u.,..., u,) where u;'s are the left singular vectors of M corresponding to top-r
singular values.
5: Let V (V1,...,,y, v,) where v, are the right singular vectors of M corresponding to top-r
singular values.
6: Output Ü and V.
We combine the upper bound in Theorem I with Davis- Kahan theorem, then obtain the upper bound of loss in subspace estimation given by Algorithm 3.
Theorem 4. Given the adjacency matrix A generated by connectivity matrix M from parameter space O2 (n,, n2 p.r. O.). the outputs of Ü and V from Algorithum satisfy
(n1 nz)p
max (Ū, Lop (V. V)) N
11) S (ni V vn2 (10)
sup ME
0²
(n + n22
sup M
P
V))
o²
Ar) s v1 (11)

---

The upper bound shows that if we obtain better a estimation M or if the spectral gap a² is larger, then we can get more accurate estimation in singular space of M. Since the operator norm of a projection matrix is 1, the estimation error in operator norm cannot exceed 2. Therefore, 2 is trivial upper bound (10). Similarly, 2r is trivial upper bound in (11).
3.2 Minimax Lower Bound
In this section, we introduce the lower bound for the estimation in Theorem 4. Let us denote the projection matrix of the left singular space of M by
PM UUT.
where the columns of U are top-r singular vector of M. the next theorem, we will show that under regularity conditions on the parameter space, the estimation error rate of PM in the previous theorem is minimax optimal.
Theorem 5. Let 1 ST n2 S n1. Suppose that for some positive constant Co. and assume
(a) m1n2(4p/10)² S r < mmn266p110 (6)/ when
(b) S nI/Co. ro? S "in2p" /Co when 1. Then, for sufficiently large Co there exist prior nt" succ that
P.. {M E [0.3p, 0.7p) xn2, or (M) 2 o., rank =r]=
(12)
and the risk of the Bayes estimator P ET [PM A] under x- bounded from below by
E
p
PM lop
TuP o
^
(13)
50
and
E
|PP
PM
r
n1P
^1
(14)
50
o²
The assumptions on the parameters are mild and necessary (up to the choice of constants). r/n, has to be sufficiently small so that the parameter M is low-rank. In (8), we have shown that n1nep" (ro²] is sufficiently large so that the parameter space nonempty. It requires the parameter
Remark 5.
space to be large enough to construct the prior n. We need slightly different regularity conditions because of the different construction of I. each case.
for = 1 and
Theorem 5 presents the lower bound of the Bayes error rate. By the fact that a minimax estimator should be a Bayes estimator with respect to the least favorable prior of the parameter space, it is straightforward to obtain
1 nip
inf sup P ME
P
PMIla
A1
50
o²
and
inf
sup p2.p.r...)
E
p PM
n4 ^ 11
P MM02(1) (E
50
from (13) and (14). We have been focus the lower bound of the left subspace estimation in the discussion so far. The result of Theorem can be extended to the right subspace estimation. We skip the presentation of this similar result.
Proof Sketch Theorem We only discuss the case > here. The case has a different
but simpler proof. As in the proofs of many other minimax lower bounds, we firstly construct finite
subset of the parameter space. Let H E [-v3, v3) m2 x(r-1) such that (H, 1,, ( 1,, \/ni =
I,. Let i i = I,..., N, be distinct matrices in 1-1,1]mmx( with N = (r-(r-)), W, =
VI H + ,X, with 0 μ 1, and
P I,, -nnxnn Xng + W. W..... W. -W.W,, O),
M,
(15)
2
10
where (W,, W.) is repeated I times. This alternating structure can help to provide sufficiently
large spectral gap. The parameters μ and & can control the distinguishability between distinct M, and My. We require X;
7

---

(a) has almost orthogonal columns;
(b) has columns almost orthogonal to the columns of (H, 1,,),
(c) is sufficiently different from X, for j #
There are sufficient amount of such X; when nı is large. We assign uniform prior on the remaining M. The minimax error is bounded below by the Bayesian error. addition, the lower bound of [|PM PM, F can be controlled by | X; Therefore, the problem can be reduced to find the lower bound on Bayes error for estimating X, The Bayes error is lower bounded by the Hellinger distance between the probability space with parameter M, and My. Mcasuring the Hellinger distance between Bernoulli random variables becomes standard problem.
4 Numerical Experiments
In previous sections, we have shown that the algorithms returns rate optimal estimation in different tasks. The choice of hyperparameter does not affect the rate in the theorems, but it can change the performance the algorithms in practice. In this section, each experiment will repeat 100 times. In each iteration, the randomization procedure follows these steps:
1. Randomly generate matrices MI E x= M2 ((r-1)xna so that each entries follows normal distribution independently.
2. M3 M, M2 is an n1 n2 matrix with rank 1-
3. Scale M3 that all entries belongs to the interval [0, p]. We note that this step increases the rank the matrix by 1. The resulting rank-rmatrix the connectivity matrix M the current iteration.
4. Generate the adjacency matrix of the random bipartite graph with connectivity matrix M.
4.1 Simulation on Matrix Estimation
Algorithm 1 and Algorithm 2 have the same theoretical error rate. However, their performances in simulation are significant different. The experimental results of both algorithms will appear in this section for comparison. We consider the following parameters in O 1 122, p.p n1 12 1000, r = 3, 0.01, 0.03, 0.05. In the following experiments, we vary the regularization constant from 0.2 1, where the default constant equals 2 in Algorithm 1. When apply regularization on the adjacency matrix, we scale the columns and the rows so that the maximal degree is at most en1p, as described in Remark
From the simulation results in Figure 1, we can conclude following observations:
1. Compared with soft singular value thresholding in Algorithm 2, the performance of hard singular value thresholding in Algorithm more heavily relies on the choice of regularization parameter. If we are able to choose a good regularization parameter, Algorithm outperforms Algorithm when the error is measured by operator norm. On the other hand, if we consider the Frobenius loss, Algorithm performs relatively better. Suppose we unable choose a good regularization constant, Algorithm performs better in most cases.
2. Since the density parameter p = 0.01, 0.03 and 0.05 on different columns from left to right, compare the plots in the first row and observe that regularization has smaller effect the density of the random bipartite graph increases. This phenomenon indeed coincides with the theoretical background described in Remark 3. Even if we do not apply regularization on the adjacency matrix, the loss rate can be bounded above by (mip) V (log ni)). As increases, log n1 can take on the role of the upper bound.
3. Regularization has little affect on soft singular value thresholding (Algorithm 2). When p 0.01, regularization constant = 0.8 works slightly better than 0.7 and 0.9. For p = 0.03 and 0.05, the performances are almost identical when the regularization constant is greater than 0.6. The performance of Algorithm 2 in this experiment is slightly different from our expectation, but it does not violate any theorems in the previous sections. It could be an interesting future work to explain why regularization does not substantially improve the soft singular value thresholding method.
8

---

Loss of Algoritim in Operator Norm
Loss of Algorithm in Operator Norm
Loss of Algorithm Operator Norm
+
operater norm"
140
Ioos operator normatt norm"
20
120
800
loss operator
15
80
200
88
100
0.2 033 0.4 0.5 0.5 0.7
0.8
0.9
0.2
0.8
0.4
0.5
0.5
0.7
08
0.8
0.2
0.3
0.4
0.5
055
0.7
088
0.9
regularization
regularization
regularization
Loss of Algorithm in Frobenius Norm
Loss Algorithm Frobenius
Algorithm Frobenius
Frobenius nom?
Freberius norm?
loss in Frobenius norm?
460
400
30
360
120
300
30
100
250
200
80
160
0.2
0.3
0.4
0.5
0.5
0.7
0.8
0.9
0.2
0.3
0.4
0.5
0.7
0.8
0.2
0.3
0.4
0.5
08
0.7
08
0.9
regularization
regularization constant
rogularization constant
Loss Algorithm in Operator Norm
Algorithm Operator
Algorithm Operator
loss operator nomm
22
nom?
loos operator namm?
20
180
400
18
300
100
16
200
100
12
0.2 03 0.5
0.9
0.2
0.5
08
regularization constant
rogularization constant
regularization constant
Loss Algorithm 2 in Frobenius Norm
Loss of Algorithm 2 in Frobenius Norm
Loss of Algorithm in Frobenius Norm
28
Frobenius nore!
124
Froberius norm?
200
lass In Freberius norm?
22
160
400
20
300
18
100
16
04
0.0
regularization constant
regularization constant
regularization constant
Figure 1: Numerical experiments of Algorithm and Algorithm 2. The probability matrix M's are generated
from the parameter space (1 T,) with m = 1000, = 3. p = 0.01, 0.03, 0.05 on different columns (from left to right). The horizontal axis represents the choice of regularization parameter.
4.2 Simulation on Subspace Estimation
The simulation results of Algorithm are presented in Figure 2. The parameters in this experiment the same as those used in Section 4.1. Due to the simulation procedure, it is difficult to control the smallest nonzero singular value of the connectivity matrix M. Therefore, we plot the loss measured by Lop Ü, U) and (U, U). We observe that the regularization constant does not have significant effect the performance, but we can still conclude that the algorithm performs slightly better we set the constant to around 0.5 when we measure the loss in Frobenius norm.
Discussion
In this section, we will discuss some possible future works. We have proposed and analyzed the estimators given the parameters such as and r. In Section 3, we study the loss in estimating the column row spaces simultaneously. We are wondering if we can extend these algorithms and emor rates in more general settings.

---

Loss of Algorithm 3 in Operator Norm
Loss of Algorithm in Operator Norm
Loss of Algorithm Operator Norm
1.3
lossin (operator nommee.
loas (aper storr norm"e.
1,2
28
(operator
1.1
28
22
20
0.8
0.2
0.3
0.4
0.8
0.7
0.9
0.2
0.4
0.5
0.6
0.7
0.8
0.8
0.2
0.8
0.4
0.5
0.7
0.8
0.9
regularization constant
reguierization constant
regularization constant
Algorithm Frobenius Norm
Loss of Algorithm 3 in Frobenius Norm
Loss Algorithm in Frobenius Norm
in (Froberius norm
lses (Friteeessus nomn
loss in (Fieberius narm'e.
110
-35
80
70
0.2
0.3
0.4
0.5
0.7
0.9
0.9
0.2
0.3
0.4
0.5
0.7
0.9
regularization constant
regurarization constant
regufarization constant
Figure 2: Numerical experiments of Algorithm 3. The probability matrix M's are generated from the parameter space (21, 12, T, P, a) with = 2000, r = 3. 0.01, 0.03, 0.05 on different columns (from left right). The horizontal axis represents the choice of regularization parameter.
5.1 Bipartite Graphs with Unbalanced Parts
Suppose the bipartite graphs has unbalanced parts, i.e., 71 n2 for the dimension of the adjacency matrix, then the upper bound in Theorem 4 may not be optimal for Lop Ú). Intuitively, suppose there are more columns than rows in the adjacency matrix, then we are able to collect more information about the column space of the connectivity matrix M. It is not clear how the assumption n m2 affects the error rate of Lap U, Ú) in our theorem. On the other hand, increasing number of rows also changes the spectral gap Some recent works [18, 2] have focused on unbalanced random matrix, but the authors have not shown their results are optimal in the random bipartite graph setting. The generalized theorem in [4] enable us to find tight bound for random matrix with Gaussian entries, but the application on sparse random graphs not straightforward. still an open problem to find the minimax error rate Lop U, Ú) and (U, Ú).
5.2 Unspecified Parameters
To establish the minimax lower bound, we specify the sparsity parameter p and the rank However, these parameters are unknown in general in practice. A possible approach is to tune these parameters by cross validation. We randomly partition the bipartite graph into training subgraph and validation subgraph, then we apply the algorithms in the present paper with various parameters and compute the likelihood the validation subgraph. We can generalize this procedure to cross validation and find the parameters so that the average likelihood on validation subgraphs are maximized. The implementation of cross validation should be straightforward, while the risk of estimation without specified parameters can be an interesting future work.
Conclusion
In this paper, we study bipartite graphs with underlying low rank structures. We have introduced the algorithms for finding the connectivity matrix and its column and row space, using the techniques of regularization, hard and soft singular value thresholding. We provide theoretical analysis in Theorem 1, Theorem 2 and Theorem for the algorithms we proposed. In addition, minimax lower bounds in Theorem 3 and Theorem 5 show that the algorithms return rate optimal estimators for corresponding tasks. In addition, simulation studies in Section 4 investigate the effect of regularization parameters the algorithms. Finally, we discuss some possible future works Section 5.
10

---

References
[1] Rajendra Bhatia. Matrix analysis, volume 169. Springer Science & Business Media, 2013.
[2] Changxiao Cai, Gen Li, Yuejie Chi, H Vincent Poor, and Yuxin Chen. Subspace estimation from unbalanced and incomplete data matrices: f2 statistical guarantees. Annals of Statistics, 49(2):944 967, 2021.
[3] Jian-Feng Cai, Emmanuel J. Candès, and Zuowei Shen. A singular value thresholding algorithm for matrix completion. SIAM Optim., 20(4):1956-199) 1982, 2010.
[4] Tony Cai and Anru Zhang. Rate-optimal perturbation bounds for singular subspaces with applications to high-dimensional statistics. Annals of Statistics, 46(1):60-89 2018.
[5] Tony Cai and Wen Zhou. A max-norm constrained minimization approach to 1-bit matrix completion. J. Mach. Learn. Res., 14(():3619-3647, 2013.
[6] Emmanuel Candes, Carlos A Sing-Long, and Joshua D) Trzasko. Unbiased risk estimates for singular value thresholding and spectral estimators. IEEE transactions signal processing, 61(19):4643-466 2013.
[7] Sourav Chatterjee. Matrix estimation by universal singular value thresholding. Annals of Statistics, 43(1):177-214, 2015.
[8] Peter Chin, Anup Rao, and Van Vu. Stochastic block model and community detection in sparse graphs: A spectral algorithm with optimal rate of recovery. In Proceedings The 28th Conference on Learning Theory (COLT), pages 391-423, Paris, France, 2015.
[9] Mark A Davenport, Yaniv Plan, Ewout Van Den Berg, and Mary Wootters. 1-bit matrix completion. Information and Inference: A Journal of the IMA, 3(3):189-22) 223, 2014.
[10] Uriel Feige and Eran Ofek. Spectral techniques applied to sparse random graphs. Random Struct. Algorithms, 27(2)251-275, 2005.
[11] Xiaoli Zhang Fern and Carla E. Brodley. Solving cluster ensemble problems by bipartite graph partitioning. Proceedings of the Twenty-first International Conference on Machine Learning (ICML), Banff, Alberta, Canada, 2004.
[12] Chao Gao, Yu Lu, and Harrison H Zhou. Rate-optimal graphon estimation. The Annals of Statistics, 43(6):2624-266 2652, 2015.
[13] Chao Gao, Zongming Ma, Anderson Y Zhang, and Harrison H Zhou. Community detection in degree-corrected block models. Annals of Statistics, 46(5):2153-211 21885555-15,--- 2018.
[14] Olga Klopp, Alexandre Tsybakov, and Nicolas Verzelen. Oracle inequalities for network models and sparse graphon estimation. The Annals of Statistics, 45(1):316-354, 2017.
[15] Vladimir Koltchinskii, Karim Lounici, and Alexandre B Tsybakov. Nuclear-now penalization and optimal rates for noisy low-rank matrix completion. Annals of Statistics, 39(5):2302-2322) 2011.
[16] Can M. Le, Elizaveta Levina, and Roman Vershynin. Concentration and regularization of random graphs. Random Struct. Algorithms, 51(3):538-561) 11.53386611,1177 2017.
[17] Jing Lei and Alessandro Rinaldo. Consistency of spectral clustering in stochastic block models. Annals of Statistics, (3(1):215-237 2015.
[18] Mohamed Ndaoud, Suzanne Sigalla, and Alexandre B Tsybakov. Improved clustering algorithms for the bipartite stochastic block model. arXiv preprint arXiv:1911.079977 2019.
[19] Kaspar Riesen and Horst Bunke. Approximate graph edit distance computation by means of bipartite graph matching. Image Vis. Comput., 27(7):950-95) 959, 2009.
[20] Karl Rohe, Sourav Chatterjee, and Bin Yu. Spectral clustering and the high-dimensional stochastic blockmodel. The Annals of Statistics, 39(4):1878-19155 2011.

---

[21] Stanislaw J Szarek. Nets of grassmann manifold and orthogonal group. In Proceedings of research workshop on Banach space theory (lowa City, lowa, 1981), volume 169, page 185, 1982.
[22] James H Wilkinson. Elementary proof of the hielandt-hofffman theorem and of its generalization. Technical report, Stanford University, Department of Computer Science, 1970.
[23] Jiaming Xu. Rates of convergence of spectral methods for graphon estimation. International Conference Machine Learning, pages 5433 54422 PMLR, 2018.
[24] Bin Yu. Assouad, Fano, and Le Cam. In Festschrift for Lucien Le Cam, pages 423-435. Springer, 1997.
[25] Se- Young Yun and Alexandre Proutiere. Accurate community detection in the stochastic block model via spectral algorithms. arXiv preprint arXiv: 1141.7333, 2014.
[26] Hongyuan Zha, Xiaofeng He, Chris H. Q. Ding, Ming Gu, and Horst D. Simon. Bipartite graph partitioning and data clustering. In Proceedings of the 2001 ACM CIKM International Conference on Information and Knowledge Management (CIKM), pages 25-32, Atlanta, GA, 2001.
[27] Fan Zhou, Ping Li, and Zhixin Zhou. Principal subspace estimation under information diffusion. In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 3205-3213, Virtual Event, 2021.
[28] Zhixin Zhou and Arash Amini. Analysis of spectral clustering algorithms for community detection: the general bipartite setting. J. Mach. Learn. Res., 20:47:1 17:447,, 2019.
[29] Zhixin Zhou and Arash A Amini. Optimal bipartite network clustering. J. Mach. Learn. Res., 21:40-1, 2020.
[30] Zhixin Zhou and Ping Li. Rate optimal chernoff bound and application to community detection in the stochastic block models. Electronic Journal of Statistics, 14(1):1302-134) 2020.
[31] Zhixin Zhou and Yizhe Zhu. Sparse random tensors: Concentration, regularization and applica- tions. Electronic Journal of Statistics, 15(3)2243,, 2021.
12


Reviews:
[{"review_id": "olOloQi7SRW", "reviewer": "Reviewer_vRfR", "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.\n\nThe 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. ", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "## Originality\n\nI 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. \n\nThat 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\nestimation, 2015) and (Mcmillan, Smith: When is nontrivial estimation possible for Graphons and Stochastic Block Models?, 2016)).\n\n## Quality/Clarity\n\nThe 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.  \nPresentation-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.\n\n## Significance\n\nIf 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.\n\n\n## Missing literature\n\nThe 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?\n\nSimilarly, 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I mentioned the limitations above. I see no potential negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "I see no ethical concern. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "IHK4v0D1cyc", "reviewer": "Reviewer_iUnH", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "There are several points listed to be clarified.\n\n1. 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?\n\n2. 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.\n\n3. 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.\n\n4. In Theorem 3, the authors should provide the lower bound of n_1, but not just claim that n_1 is sufficiently large.\n\n5. 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?\n\n6. 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.\n\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "6T5S554rAZ", "reviewer": "Reviewer_f1zZ", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"ethical_concerns": "No", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "7"}, "extra_text": {}}, {"review_id": "38w34aMM5kp", "reviewer": "Reviewer_MzEw", "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.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "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.\n\n(1)\tThe 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. \n\n(2)\tTheorem 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.\n\n(3)\tCurrently, 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.\n\n(4)\tIn 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.\n\n(5)\tIn 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.\n\n(6)\tIn 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. \n\nReferences:\n\n[1] Le, C.M., Levina, E. and Vershynin, R. (2017), Concentration and regularization of random graphs. Random Struct. Alg., 51: 538-561.\n\n---------------------- Post author response -------------------------\n\nI 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).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have addressed the limitations of the results in Section 5.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "around 12 hours"}, "extra_text": {}}]

Author rebuttal:

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)