Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: In the given paper, the authors propose a novel biclustering algorithm for dyadic data based on optimal transport (OT) and the block seriation problem. Their main contribution can be summarized as the formulation of the optimization problem BCOT, an indefinite bilinear program, whose solution can be used to obtain biclusters, i.e., a simultaneous clustering of rows and columns. In special cases, the solution of BCOT allows for the computation of an approximation of the optimal transport map with bounded rank for the discrete Kantorovich OT formulation. In addition to BCOT, the authors also introduce the fuzzy variant BCOT$_{\lambda}$, which is an adaptation of BCOT with entropic regularization, and connect BCOT to existing biclustering algorithms. To empirically evaluate the proposed method, the authors perform experiments with six document-term datasets and compare their results with four other OT based biclustering approaches.
strengths_and_weaknesses: **Strengths**

_Originality_: The concept to combine the block seriation problem and optimal transport to obtain block diagonal biclusters for dyadic data is a novel idea.

_Quality_: In the presented work, I did not see any major technical issues and the authors provide proofs for the propositions in the appendix.

_Clarity_: The overall structuring of the paper is good, especially section 3 (_Connections to Existing Work_), as it helps to contextualize the proposed method with respect to related work. Concerning reproducibility, the authors publicly released their code. The application of a statistical test to quantify the significance of the experimental results is a nice addition.

_Significance_: The presented results show that the proposed method is superior to existing OT based biclustering methods with respect to document-term clustering.

**Weaknesses**

_Originality_: Although the presented method is novel, it heavily relies on previous work (i.e., [19, 21, 26]) and provides comparably little conceptual originality. The contribution's main novelty seems to be that it works better for dyadic data compared to other OT based biclustering methods. As it is conceptually not that convincing, I would consider it more of an empirical paper, and for that it lacks sufficient experimental evaluation with SOTA biclustering methods for dyadic data. 

_Quality_: While there are no obvious major technical errors, there are some vague statements and (suspected) smaller errors in some of the formulas. Moreover, instead of using bicluster-specific metrics, such as e.g., the co-clustering error (CCE), the authors only assessed the resulting clusters using standard clustering metrics. Overall, I am also missing a clear motivation, other than the fact that optimal transport is a trending topic in the machine learning community.

_Clarity_: One of my main concerns is that the paper (in the given version) is not sufficiently self-contained. It was difficult to understand the presented content without consistently referring to [19] and [26] and further referenced literature. Also, a clear train of thought is missing throughout the paper (e.g., in Section 2.2 we switch from inducing a biclustering based on the optimal transport block seriation problem to an approximation of the Kantorovich OT formulation without much transition), which is especially evident in the introduction. I would suggest starting with a more general motivation before going into detail about bipartite graphs as well as applications. While contextualizing the work in section 3 is helpful, this section is, again, not fully self-contained and comprehensible, and related work needs to be frequented. Concerning language and grammar, there is room for improvement. Language is oftentimes repetitive, somewhat colloquial, and not always precise.

_Significance_: While the BCOT performs much better to identify document and term clusters in comparison to existing OT based biclustering methods, the overall significance of these results is not (yet) clear to me. I have multiple questions/concerns about the methodology of the empirical evaluation, which includes, among others, the choice of datasets, baselines, and metrics (please see **Questions 4.x** for more details).

Please see below for a more detailed feedback.

**Minor remarks & suggestions**

* References:
    - Please consider citing the peer-reviewed version instead of the arXiv version in the references (e.g. reference [24])
    - Lines 30-31: Please consider adding references that support your statement ("Optimal Transport (OT) took the machine learning community by storm and was used in the resolution of various data mining problems and biclustering was not an exception")
    - Lines 42-43: Please consider adding references for the previous biclustering approaches, which your method generalizes
    - Lines 61-63: Please consider adding a reference for the the Kantorovich formulation of OT
    - Line 225: Please consider adding a reference for the Davies-Bouldin index
    - Line 233: Please consider adding references for the employed clustering metrics

* Structure: 
    - Please consider restructuring your introduction, starting with a more general motivation and introduction to biclustering and OT. Also, pointers to sections would be much appreciated (e.g., "In Section 2, we propose our method...").
    - Lines 25-29: Some more high-level classification of biclustering algorithms might be helpful for the reader (e.g., there exist probabilistic approaches, etc.) in addition to enumerating applications.

* Language/Grammar:
    - Please consider refraining from very long sentences (e.g., lines 32-35, 140-143)
    - Lines 103-104 is not a proper sentence
    - Line 145: mentionned -> mentioned
    - Line 170: "proposed to fuzzy variant" -> "proposed a fuzzy variant"
    - Line 171: traditionanal -> traditional
    - Line 191: in -> is
    - Line 194: "algorithm available" -> "algorithm is available"
    - Line 198: "in a way that make" -> "in a way that makes"
    - Line 223: $\lambda$ is not in subscript
    - Line 282: "certain types dyadic data" -> "certain types of dyadic data"
    
* Examples for vague language:
    - Lines 43-44: "We propose two efficient methods for solving this problem [...]" -> What problem?
    - Line 98: "Now let its [...]" -> What is _it_?
    - Line 107: "[...] we are interested in inducing a couple of _almost-hard clustering_ [...]" -> What does _a couple_ refer to?
    - Lines 117-118: "[...] this should not significantly change the structure of the solution [...]"
    - Lines 130-131: "[...] row exemplars (or representatives or centroids)" -> Please consider using one of these terms consistently
    - Line 134: "Biclustering is the main purpose of the approach we proposed [...]" -> Could you be more precise what is meant by _the approach we proposed_
    - Line 200: "[...] the computation of [...] is quite efficient [...]"
    - Line 209: "[...] our model should be faster in most cases [...]"
    - Line 286: "[...] the proposed approach does a good job of finding clusters [...]"

* (Suspected) minor errors:
    - Line 70: Is $\mathbf{K}=-\texttt{diag}(\mathbf{a})\exp(\mathbf{M}/\lambda)\texttt{diag}(\mathbf{b})$ correct, cf. [4], Lemma 2? Should it be a negative exponential, i.e., $\exp(-\mathbf{M}/\lambda)$?
     - Lines 78-79: "The block seriation problem is an integer programming problem and is consequently NP-hard" -> Please consider adding a reference which contains a proof for NP-hardness for the block seriation problem
    - Line 99: Is $\mathbf{Z}$ a typo?   
    - Line 158: $\sum_{h=1}^r p(\mathbf{b}_i, \mathbf{b}'_j \in h)$ -> Should it be "$=$" instead of "$\in$"?
questions: 1. Could you please elaborate on the row exemplar and column exemplar distributions? How do they relate to the row and column weights? In [26] these are distributions from the second data matrix, but what are their purpose in your work?

2. Could you give more details on the approximation of the optimal transport map (lines 136-139)? Also, what do we know about the rank of $Z$ and $W$?

3. Table 1: How did you compute the time complexities for CCOT, CCOT-GW [19], COOT and COOT$_{\lambda}$ [26]? Why do they differ from the time complexities reported in [19] and [26], respectively? What restricted class of cost functions is considered?

4. Empirical evaluation

    4.1. Have you considered using simulated data to have ground truth biclusters, which you can use to assess your method? This is quite common for the evaluation of novel biclustering methods, and is also done in [19] and [26]. If it is due to the page limit, you could also consider including this in the appendix or supplementary material.
    
    4.2. What is the reasoning for the choice of datasets? Why mainly document-term matrices and not e.g., gene expression data?
    
    4.3. It would be beneficial to include the majority of baselines also used in [19] and [26]: ITCC, Double K-Means, Orthogonal Nonnegative Matrix, Tri-Factorizations (ONTMF), the Gaussian Latent Block Models (GLBM) and Residual Bayesian Co-Clustering (RBC).
    
    4.4. Why did you choose to compare your method, which is specifically designed to work well for dyadic data, with methods which are not? Have you considered including common biclustering methods for dyadic data as baselines?
    
    4.5. Why did you look at document and term clusters separately, and not evaluate your obtained biclusters using e.g., the CCE (see point 4.4)? If you lack ground truth data, please consider point 4.1.  It might be beneficial to compare your method with CCOT, CCOT-GW [19], COOT, COOT$_{\lambda}$ [26] with respect to the CCE as well.

5. Applications

    5.1. Reference [30]: What applications of biclustering do the authors discuss in this book? Could you please give some pointer to specific pages?

    5.2. As the main novelty in this contribution seems to be the focus on dyadic datasets, could you give an outlook on other areas of application (in addition to document-term matrices) and elaborate on the significance of your contributions?
limitations: The authors addressed the limitations of their work pertaining to the type of data suitable for their proposed method.
review_title: null

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes a generic framework for biclustering using optimal transport. Two methods are developed in this framework and usually result in an almost hard biclustering and a fuzzy biclustering accordingly. The computational efficiency and accuracy are validated through six benchmark datasets.
strengths_and_weaknesses: originality
Strength
This paper leverages the low-rank optimal transport to solve the biclustering problem for the dyadic data.

quality
The paper is generally well written in grammar. However, the technical discussion lacks clarity in some respects. Such as Page 1 line 27, the “summary matrix” is mentioned yet without further explanation. 

clarity
Weaknesses
(1)	It is unclear what’s the major advantage makes the proposed methods perform better than the others in the experiments. 
(2)	A lot of details of the experiment seem to be missing. Such as, how are the parameters r and c selected. There are lots of existing works introduced in section 3 seems can solve the discussed problem also and what they are not compared.
significance
This paper leverages the optimal transport to solve the biclustering problem for the dyadic data. The computational efficiency and estimation accuracy are achieved through the low-rank assumption of the solution matrix.  

questions: 1. The introduction of the relevant is unclear and would need more details and formalization. I fail to grasp exactly what causes the weakness of the these introduced methods CCOT, CCOT-GW, COOT and COOT-GW.

2. When the authors say integrating the constraint $rank(C) \leq k$ to (4) and finally get (5), 
are the three constraints (binarity, assignment, impossible triads) included or ignored?

3. The definition of anti-adjacency matrix seems a little arbitrary since it is defined based on the “discrepancy” between two nodes, which seems to be a concept without any rigorous mathematical statement in the paper. 

4. Page 3 line 95. It seems that the dimension of r and c and be different. How can that be achieved considering Z should be a matrix with n row r columns and W should be a matrix with d row and c columns.

5. It would be better to replace the notation for the assignment matrix since it is duplicated with the solution matrix C. This causes some confusions during the reading.

6. Page 5, is there a connection between (8) and (9) or they are two different objective functions?

7. Page 7. The time complexity of CCOT reported in the paper “Coclustering through optimal transport” seems do not match with the order in the Table 1.  What causes the extra computational burden in this paper?

8. In the implementation, it seems the algorithm needs r and c as input. The details about how to choose these two parameters and decide the rank k seems to be missing.

9. In the experiment, the repeat times seems to be small (only 10 runs are conducted). In some settings, the standard deviation of the results is 0. How does that come?

limitations: The authors mention about the limitation that the method is specifically tailored to datasets consisting in dyadic data for biclustering and can not be applied on other data types such as images directly.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a new approach to bi-clustering, BICOT, and its entropic regularization BICOT_{\lambda}. The proposed BICOT  model is quite general. In primis, it can be reduced to a low-rank solution for optimal transport under specific distribution conditions. Secondly, it can be reduced to several bi-clustering models in the literature. 
 
The authors also prove that the computational complexity of BICOT is the same as that of previous Co-Clustering work COOT [26] and inferior to the versions of CCOT [19]. To support their claims, parallel to the theoretical demonstrations, the authors conduct an accurate analysis of their algorithm by comparing their method with state of the art for different dyadic data sets with increasing size. In particular, besides better accuracy, adjusted random index and normalized mutual information, BICOT_{\lambda} performs best in all the experiments.
 
From a theoretical point of view, this work introduces the problem in a more general and straightforward form that can be traced back through appropriate choices to several models previously introduced in the literature. The main idea is to formulate the bi-clustering problem by using two building blocks: block seriation and optimal transport.

strengths_and_weaknesses: The strength of this work is mainly based on three aspects:
1.	The proposed approach generalizes many already present algorithms that can be obtained as special cases.
2.	The presented algorithm is more efficient both in terms of complexity and in terms of memory usage.
3.	The authors provide evidence of the effectiveness of their approach both theoretically and experimentally.
The paper conducts extended analysis over several data-set showing great performance compared to other existing approaches. The results are well exposed, and the paper is well written and easy to follow. 
 
A possible weakness is that determining the number of clusters requires resorting to external metrics. Furthermore, it is unclear if the authors set the hyper-parameters by performing cross-validation on a data set independently from the validation set. Also, there is no reference to the hyper-parameters used in the methods that serve as the baseline. Finally, concerning the term clustering experiment, it seems that the best performances are due to the fact that some methods have not been optimized.

questions: -  In (9) L is not used; it is not well explained in which sense (9) is related to (8).
-  In [26] is proved that COOT is a distance. Some discussion comparing L in COOT and BICOT would be appreciated. Comparisons with [26] are done on documents and terms, and in the paper it is said that it would not be possible on images. On the other hand, COOT has shown experiments on MNIST and USPS (see Figure 1 in [26] (on Neurips)), simply normalizing pixel magnitude to [0,1].
Computational complexity of [26] is O(min{(n + n’)dd’ + n’^2n; (d + d’)nn’ + d’^2d})
-    The performance of the proposed approach strongly relies on the choice of the function $L$. How much will the results change when changing $L$?
-    Is there a way to define an optimal $L$ for a given quality measure?
-    How the algorithm asymptotic complexity will change if one uses a dense function $L$?
-    How much do the results depend on the regularization function $\Omega$ in $BCOT_{\lambda}$?
-    How have been chosen the hyper-parameters of k-means clustering?
 
Typos:
 -Line 99:  L(b)_{ij}    remove Z
 -Line 101: two times “between”
- (12) L(b_{ij})
- Line 191: in --> is
- Line 194 is available
 -Line 280: till—>still
 
Proof of proposition 3:
Line 445 twice L(B)W -->  L(B)W and L(B)^TZ

limitations: The limitations of the proposed approach are not fully explained. For example, it seems that the asymptotic low cost of the algorithm is largely due to the sparseness of the cost matrix. Although one has the freedom to choose this matrix, for some applications a sparse matrix may not give satisfactory results. However, the use of dense matrices could considerably slow down the algorithm making it de facto uncompetitive.
review_title: null

Meta-review: metareview: The reviewers discussed strengths and weaknesses of the paper. One potential issue (to which the author's answer was rather unhelpful) was resolved by a reviewer running the experiments with higher precision output. Reviewers were mostly convinced by the strong empirical improvements. 

confidence: Certain
Decision: Accept