Efficient and Effective Optimal Transport-Based Biclustering
Authors: Chakib Fettal
lazhar labiod
Mohamed Nadif
Venue: NeurIPS 2022 Accept (2022)
Keywords: biclustering
optimal transport

Abstract: Bipartite graphs can be used to model a wide variety of dyadic information such as user-rating, document-term, and gene-disorder pairs. Biclustering is an extension of clustering to the underlying bipartite graph induced from this kind of data. In this paper, we leverage optimal transport (OT) which has gained momentum in the machine learning community to propose a novel and scalable biclustering model that generalizes several classical biclustering approaches. We perform extensive experimentation to show the validity of our approach compared to other OT biclustering algorithms along both dimensions of the dyadic datasets.

Efficient and Effective
Optimal Transport-Based Biclustering
Chakib Fettal
Centre Borelli UMR 9010
Université Paris Cité
Informatique Caisse des Dépôts et Consignations
Shakib..ettaa@eer u-paris.fr
Lazhar Labiod
Mohamed Nadif'
Centre Borelli UMR 9010
Centre Borelli UMR 9010 Université Paris Cité mohamed nadif madif@u-paris fr
Université Paris Cité
lazhar. labioduu-pariss
Abstract
Bipartite graphs can be used to model a wide variety dyadic information such as aser-rating, document-term, and gene-disorder pairs. Biclustering is extension clustering to the underlying bipartite graph induced from this kind data. this paper, leverage optimal transport (OT) which has gained momentum in the machine learning community to propose novel and scalable biclustering model that generalizes several classical biclustering approaches. We perform extensive experimentation to show the validity of our approach compared to other OT biclustering algorithms along both dimensions of the dyadic datasets.
Introduction
Let G (U, be a bipartite graph, which is a graph whose vertices can be divided into two
disjoint sets U [1,2, ..., [U]} with [0]] n, V = (1,2, ...., [V]} with [V| d and the set of
edges E where each edge connects a vertex of U to a vertex V. The adjacency matrix for this type
of graph has the following structure
O nXX B
B
A
(I)
Oaxd
where B of size x is called the biadjacency matrix of G, its rows and columns corresponding to the sets of vertices; each entry represents an edge between a row and column. Biclustering (or Co-clustering) is the extention of clustering to this type of graph. Following [21], several biclustering models have attempted solve the problem by viewing as two-mode matrix and searching for simultaneous partition of its rows and columns 9 In this way, biclustering seeks to reveal subsets of which exhibit a similar behaviour across subset of in matrix B.
Biclustering has been used a number of different contexts. 112 used microarray data to find relations between genes and conditions, finding that genes with similar functions often cluster together. (20) applied this paradigm to data from the US Food and Drug Administration reporting system in order to identify groups of drugs with adverse effects. [ used it to find market segments among tourists so as to enable more effective targeted marketing. There have been various other applications g 33
Several solutions to the biclustering problem have been proposed the literature (see I7]) used information-theerrete approach solve the problem by minimizing the difference in mutual
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

information between B and summary matrix; they implicitly assume that the data points are generated from Poisson latent block model [T8]. 3 adapted classical modularity to bipartite networks and then used it to identify modules within them. 35 proposed a biclustering paradigm based on nonnegative matrix trrffactorization the biadjacency matrix.
Recently, Optimal Transport (OT) has taken the machine learning community by storm. OT has helped solve a variety of data mining problems, and biclustering no exception. [25] proposed two models for biclustering: a first model, CCOT, which does co-clustering based on the scaling vectors obtained by applying the Fankhom-Knoop algorithm on a square subsampled version of matrix B, and second model, CCOT-GW, which uses scaling vectors obtained by computing entropic Wassserteen barycenters, and which does not require subsampling. Then came 34 where the authors did biclustering by minimizing a new metric, COOT, which generalizes the Boomov-Wasserstein distance between B and summary matrix, similarly to what was done in [10] More specifically, they proposed two new metrics: COOT, together with an entropically regularized metric COOT,. However, both [25] and 34 have certain drawbacks. First, both algorithms do not tackle the biclustering from the beginning; the co-clusters are deduced at the convergence. Thereby biclustering is a consequence and not a main goal. Secondly, they suffer from high computational complexity; CCOT and CCOT-GW also consume large amounts of memory. Finally, we will see that these algorithms are not suited to dyadic sparse data.
In this paper. while integrating the biclustering objective from the beginning, we propose generic framework for biclustering through optimal transport, which generalizes some previous biclustering approaches. We propose two efficient methods for solving this problem: one that gives an almost hard biclustering. and another that gives a fuzzy or soft biclustering through entropic regularization. These methods outperform other optimal transport biclustering models, in terms of both document and term clustering, on several regular and large scale datasets, while being more computationally and memory efficient. We emphasize once again that the approach we propose is specifically tailored to datasets consisting of dyadic data.
2 Methodology
Notations. In what follows, A = (p E R Σ P: = denotes the n-dimennsionl standard simplex. II(w, v) {Z E R Zz1 w, w E A and A are the marginals of the joint distribution and 1,, is vector of ones. Matrices are denoted with uppercase boldface letters, and vectors with lowercase boldface letters. For matrix M, its i-th row is m; and its j-th column is m', We have that |l-Ilo is the O-norm which returns the number of nonzero elements of its argument.
v) denotes the transportation polytope, where
2.1 Preliminaries
We first need to introduce exact discrete OT and its entropically regularized counterpart, and show how biclustering can posed as an integer program.
Discrete OT as a linear program. The goal of discrete optimal transport to find minimal cost transport plan between a source probability distribution w and target distribution v. Here we are interested in the discrete case of the Kantorovich formulation of OT, that is
OT(M, w, v)
min Zell(w,v)
(M, Z)
(2)
where M E BRakk is the cost matrix, and my quantifies the effort needed to transport a probability mass from w, V...
Discrete entropy regularized OT. It has been suggested in the literature 6 5 that the use of a regularization such as entropic regularization can lead to better computational and statistical efficiency.
(M, w, v)
min (M, Z)- - AV (Z)
(3)
Zw.l(

---

where H is the entropy defined as (Z) - ization. The computational efficiency comes from the fact that the unique solution of this problem is of the structure Z == diag(a) a) exp(-MMAJdiag")) of the cost M, where a and b are scaling vectors. These vectors can be found efficiently using the Sinkhorn- Sinkhorn-Knopp algorithm.
2ij log 2ij and À controls the strength of regular-
a rescaled elementwise negative exponential
Biclustering as an integer program. The Block seriation problem [27 consists in finding two permutation matrices, one for the rows and one for the columns s.t. dense blocks appear along the diagonal of the permuted matrix. A possible definition of the block seriation problem is as follows: given matrix B RRx s.t bij gives the strength of the association between row and column (such as in the case of a biadjacency matrix, for example), we have
max
Σ 1
buj
(4)
subject to
Vi,j
{0,1} Cij
Vi,j&',J
Cij + Gij' + cyy -3) Crj 2
Vj Σ c321
cay + Ges Gjj Gy' 1
Crj + Cij + Cif Cryy S
iA Σ, cs 21 21
Cay' + cey cty Cjj S
A solution C is a block diagonal matrix up to a permutation of its rows and columns. The block seriation problem an integer programming problem that is NP-hard. One approach for solving this problem uses simplified version where rank constraint rank (C) S k is added for k the number of desired biclusters. Integrating this constraint into (4), we can define new problem by low-rank factorization of C, i.e. C = ZWT, which we formulate as
Σ
ZEi( (d.k)
(5)
where I'nnk) 2Z E 10, 11= 1} is the set of hard partitions of dimension n X k. A simple heuristic for solving this problem involves alternatingly solving for Z given W, and vice-versa, using classical clustering algorithms, before identifying biclusters through the rearranged matrix C, which displays block diagonal structure, as shown figure Ia The biclusters are identified by grouping together the rows and columns that form block along the diagonal.
2.2 Biclustering using Optimal Transport
Here we propose new biclustering problem based on block seriation and optimal transport. For this purpose we first define what we term an anti-adjacency matrix. Note that similar concept has been discussed in [36].
Definition (Anti-adjacency matrix) Given a graph characterized by an adjacency matrix A. we have a corresponding anti-adjacency matrix A s.t. Tig quantifies the discrepancy between nodes i and j.
We consider a bipartite graph characterized by its biadjacency matrix = (bbj) E guxd The rows of are endowed with weights w A and its columns with weights v E Ad, We also consider row exemplar distribution E A" and column exemplar distribution e E A Depending on the availability of a priori information about the data, these weight vectors can be set to uniform distributions.
Now let midjaaeayyy matrix be B I(B),, where I. Ra Ra means that byy. the association between node and node j. is transformed into discrepancy measure L(B) Thus, we define the optimal transport block seriation problem as the following bilinear program
BCOT(W, v, c)
min zell(w.r)
Σ ([B)ijzzul
min Zell(w.r)
(L(B), ZWT)
(6)
Well(v.e) 4.J.k
Well(v.e)
where Z is a transport plan (or coupling) between between the row distribution w and the row
exemplar distribution r, and similarly for W w.r.t. the column distribution v and the column exemplar distribution c.

---

(a) Block Seriation.
(b) BCOT.
(c) BCOTx.
Figure 1:
Biclusters formed using three different methods on the Pubmed dataset. Classical block seriation results biclustering that hard. BCOT results in a biclustering that is almost hard with few nonzero entries outside the main block diagonal. BCOT, results in soft biclustering with many nonzero elements outside the block diagonal.
Inducing biclustering via BCOT. We will now show how to obtain a partition of the rows and the columns given solution pair (Z, W). In what follows aim is to identify an almostthard clustering couple for rows and columns from the couplings and W.
Definition (h-almost hard clustering) We define an h-almost hard clustering as a clustering whose assignment matrix is C E Rax s.t. ||C||o = n + h and for each row с of C we have that ||c||o O. When
we obtain a standard hard clustering with one non-zero element per row.
Proposition 1 For w, v, and e containing zeros, there exists an optimal puir of coupling matrices and W that are h-almost hard clusterings with .0....,k 1}. -..,,.,,,,, Furthermore, when k (resp. d k) and E ['n, n) (resp. W ('d,d] d)).
(resp. v = c), this Z (resp. W) becomes hard clustering, i.e.,
This means that the solutions already almost hard partition of the data, since h << n, d. To obtain a final hard clustering in the strict sense, we assign each row (resp. column) to the one corresponding the row of Z (resp. W) with the largest value. This should not significantly change the structure of the solution. Figure lb provides an illustration: here we see the block diagonal structure generated by the product of the two coupling matrices C C= ZWT. with its similarity in appearance to the biclustering produced by the hard block seriation la apart from few nonzero entries off the block diagonal that hard to see immediately.
Intuition for BCOT. To explain the intuition behind the proposed approach we need to look at how the problem solved. The optimization procedure as described in algorithm [onsssss in alternating between the computation of an optimal transport plan Z given W and vice versa. As regards solving for Z given W, the problem can be rewritten
BCOT(W, V, v,r,c)= = min (L(B)W,22 Z) ZelI(w.r)
This is optimal transport problem with L(B) the cost matrix. The resulting transport plan Z can be seen as a kind of row cluster assignment matrix: if Zi > 0, then row assigned to cluster The same holds for W. which can be seen column cluster assignment matrix. This also means that since L(B) the dissimilarity between the rows and the columns, then the cost matrix L(B) W represents the dissimilarity between rows and row exemplars (or representatives particular, L L(B), w,, is the dissimilarity or cost probability mass transportation between row and row cluster exemplar h. The reasoning is the same for the columns and the optimal coupling W.
centroids). In
Low-rank optimal transport. Biclustering is the main purpose of the approach we proposed, but there is another interesting use case.
Proposition 2 For equal target row and colunn representative distributions, i.e., c, and contain-
ing no zero entries, then given solution pair Z and W to BCOT, the matrix Q Z diag(1 WT an approximation of the optimal transport plan that is solution to problem 2 and whose rank at most min( (aak Z), rank( W)).
Proof's for the propositions given in the appendix.

---

Some recent works [16 31 have suggested that this kind of low-rank regularization is preferable entropic regularization as regards certain aspects. For example, the rank parameter easier to select, since it has simple bounds (an integer between and n). This may be contrasted with the regularization strength in the Sinkhorn algorithm, which continuous.
2.3 Fuzzy Biclustering via Regularized Optimal Transport
As previously mentioned, using entropic regularization may be interesting because its various useful features including statistical and computational efficiency. However, another feature of entropic regularization is that the optimal couplings Z and W are dense matrices as a consequence of the structure of the optimal solution of entropically regularized OT problems. We formulate the problem as follows
BCOTX v,
min Zell(w.r) Well(v.e)
(I()),WT)) AzH (Z) AwH (W)
(8)
where \z and Aw are the regularization parameters.
Fuzzy block seriation. We propose a fuzzy variant of the block seriation problem that allows us by extension to define fuzzy variant for BCOT using entropic regularization. Let the fuzzy block seriation problem be defined as
ZEr, (n. bigthhyyh OZZ, W)
Σ
WET
where (Z W) is some regularization term introduced to make the partition matrices Z and W dense (for example, entropic regularization or low-rank constraints), and I [n,n,, k) is the set of fuzzy partitions. Intuitively, for a solution pair (Z, W), up to constant factor, each entry in the block seriation matrix ZWT can be seen as the probability its corresponding row and column belonging to the same bicluster i.e. Cij z.W, D ZshW0ih p(b;, by) Σx=1 b/g E h).
{Z E x /i 1)
is easy to see how problem 9 is related to problem 8 and that the couplings corresponding to solutions of the problem give the probability that the different rows and columns belong to the same biclusters. Figure Ic shows biclusters produced by the solutions of BCOT,- Similarly to BCOT, block diagonal structure is formed. However, there also several off-block diagonal nonzero entries that represent the probabilities of the row-column pairs belonging to the same biclusters.
3 Links to Existing Work
3.1 Modularity Maximization in Bipartite Graphs 3
This model is able to co-cluster binary and contingency matrices by directly maximizing an adapted version of the modularity measure traditionally used for networks. The criterion that optimizes
bybb b.
max (m)(
2hhWigh
bij
(10)
W wer R.
By setting
B11 B), this problem becomes equivalent to ours; the difference is
in the constraints on and W.
3.2 Modularity-Based Sparse Soft Graph Clustering
23
Here the authors proposed a fuzzy variant of the above problem (although the context traditional clustering rather than biclustering). Solving the problem gives, for each element of the dataset, probability of that element belonging to given cluster. Our proposed entropic regularization variant represents a kind of extension of this problem to bipartite graphs.
5

---

3.3 Directional Co-clustering with a Conscience 30 a.
This model makes use of the block von Mises-Fisher mixture model for co-clustering directional data on the unit-sphere. It optimizes the following criterion:
max ZEI(n.k) (el(d.)) &...
Σ
2sh Bybj...
(11)
V V.WWW
In our formulation, we define L(B) = and apply cluster size normalization on the optimal transport plans Ž = Zdiag(Z Z ( and w = Wdiag(W 1) 1)-1/2 after computing Z and w respectively in algorithm authors for solving problem 11
obtain
general version of the algorithm proposed by the
3.4 Bipartite Correlation Clustering
In the case where the cost function results in complete bipartite graph with '+' and '.' edges with function
if bij > otherwise
L(B)
(12)
we get what is known as Bipartite Correlation Clustering. The solution to this problem maximizes the number of agreements, i.e. the number of all "+' edges within clusters plus all "-" edges distributed across clusters.
Optimization and Complexity
Optimization. Since the block seriation problem is NP-hard, computing an exact solution is prohibitive. An efficient and widely used heuristic for solving these kinds of problems involves the use of block coordinate descent, where row assignments are computed for fixed column assignments, and then vice versa, in alternation. We express the proposed algorithm pseudo-code as algorithm [ At each iteration we solve two intermediate optimal transport problems with cost matrices of dimensions n x and d x k. since B is generally sparse, and L can be defined such that L(B) retains similarly sparse structure. The computation of the intermediate cost matrices L(B) W and L(B) Z is reasonably efficient. We also observed that the algorithm does not need many iterations to converge, as shown in figure 2 be it for BCOT or B
-0014
Figure Loss for BCOT and BCOT, on Pubmed.
Algorithm 1: BCOT
Input :B bi-adjacency matrix, w and v row and column weights, r and c row and column exemplar distributions
Output:"". nr row and column partitions
W + W inits
while not converged do
Z arg OT (L(B)W, w)r);
W arg OT (LB Tz, c).);
end
Generate n", nt from Z and W:
Proposition 3 The computational complexity of the BCOT algorithm 7 when using exact OT solver is O (Ik| Ink(n k.) log(n + k) + tdk(dd + k) log(d + k])), and when using entropic regularization the complexity is Otk) B + tkn + Ikd), where is the number of iterations.
In table T we report the computational and spatial complexities the different biclustering ap- proaches. Our model has the same spatial complexity the COOT variants and better complexity

---

Table 1: Computational and spatial complexity the different OT biclustering approaches. For COOT variants. we report complexities for an euclidean cost matrix. For generic cost, the time complexity greater. For simplicity, we suppose that d E O(n) and that we want biclustering with the same number of row and column clusters for COOT and CCOT. denotes the number of iterations and for CCOT, 8 denotes the number of necessary samplings.
Method
Spatial complexity
Time complexity
CCOT
(nn²)
O
CCOT-GW
(nn))
(
COOT
((nk)
O((n+ + k)nk + 2 + t(n + k))kllg(() + k))
COOT
(mkk)
( + k k)nk + k tnk)
BCOT
((nk)
B + t(n + k)nk + k))
BCOTX
O(nk)
O 3 tnk)
than CCOT variants. As regards the computational complexity, our model should in most cases be faster with sparse data, and our experiments support this conjecture. For reproducibility, we publicly release our code
5 Experiments
We ran experiments using term-document matrices. The benefit of using biclustering this kind of data is that the resulting biclusters contain both documents and the words that characterize them, which is helpful in interpreting the clustering of the documents. Additional experiments over synthetic and gene expression data are available the appendix.
5.1 Datasets
We evaluate BCOT in relation to six benchmark document-term datasets: ACM, DBLP, PubMed, Wiki, Ohscal, and 20 Newsgroups. Their characteristics are shown in Table 2 ACM, DBLP, Pubmed and Wiki are attributed networks from which we use only the node-level features that correspond to term-document matrices. We also selected the Ohscal collection and 20 Newsgroups as large-scale tecument-term matrices to serve as computational efficiency benchmarks.
Table 2: Characteristics of the datasets.
Dataset
#Documents
#Terms
#Document clusters
Sparsity (%)
ACM
13
3025
1870
95.52
DBLP
4057
334
96.4
PubMed
32
19717
500
3
89.98
Wiki
2405
4973
86.99
Ohscal 22
11162
11465
10
99.47
Newsgroups
[26
18846
14390
20
99.41
5.2 Experimental Setup
In our experiments we define the loss function as = where c selected from k1, d, n). For BCOTA, the regularization parameter lambda is selected from {10-1, 10-3 10 10-1 10). The best hyper-parameter. are those that minimize the number of empty clusters. In the case of ties, select according the value of the Davies-Bouldin index of the partition 77]. Random restarts not used for any of the algorithms, including k-means. We use the implementation provided by the authors for CCOT, CCOT x and CCOT-GW. The code for CCOT was not available, and so we had to implement it based on the code for CCOT-GW. All the reported figures are the averages of 10 runs.
htstp:://github.ccom/ttaee
7

---

All the experiments were performed on the same machine with an Intel(R) Xeon(R) CPU and 12GB RAM. For OT solvers we made use of the POT package [[5]
5.3 Document Clustering
Metrics.
Here, the evaluation is straightforward, we adopt three popular clustering metrics: clus-
tering accuracy (CA), normalized mutual information (NMI) [ adjusted rand index (ARI) [24]
Table 3: Document clustering performance the four datasets. OOM denotes out of memory.
Method
ACM
DBLP
PubMed
Wiki
k-Means
$1,121133
13.7+11.2
14.0+10.6]
36,942.4
10.422.0
4.3+2.0
552.34477
18.21005
15.3e10.1
2660466.
18.6+9.3
3,342.9
CCOT
124420
1.040.2
0.480.2
28.6400.5
0.640.0
0.4000
32.740.2
3,040.0
3.140.1
10.640.5
4.940.1
0.640.15
CCOT-GW
8.120.0
1.540.0
0.340.0
9.440.0
1.700.0
0.3g0.0
0OM
10.910.0
4.340.0
0,4840.0
00OT
39.0:0.0
1.940.0
2.000.0
30.5+1.4
1440.3
1.250.3
43.2+1.5
1.750.6
13215
25.9&1.8
28.752.2
12.3
COOT
41.5+022
1.900.1
2.2+0.0
30.6+0.0
0.740.0
0.6400
42.4+1.5
1,750.5
1.0+13
17.2+0.0
1,740.0
0.31+0.0
BCOT
76.621.5
38.342.2
43,3=2.6
61.516.2
27.444.3
28.345.5
53.614.5
15.9119
12.9a2.4
49.8&1.5
47.9&1.0
30.61100
BCOT,
76.240.6
37.640.8
42.421.0
59.429.9
26.627.6
27.249.5
56.5+3.1
1844:13
154:1.
50.8+1.5
49.4:0.9
31.9.0.
Performance. Document clustering results on ACM, DBLP, PubMed and Wiki are given in table for the three metrics. In all cases the best result is obtained either by BCOT or by BCOT,, Moreover, on Wiki, BCOT, gives competitive results when compared with state-of-the- clustering methods presented in [14), despite not having access to the graph structure information in the Wiki citation network.
attributed graph
Efficiency. Figure plots the document clustering performance (accuracy against training time) of the different methods on the two large-scale document- matrices 20 Newsgroup and Ohscal. BCOT offers the best accuracy while BCOT, fastest method on both datasets. We see that for both BCOT and COOT, the entropie-regularized versions outspeed their exact counterparts and that CCOT suffers from very high computation times, due mainly to the fact that this method requires pairwise distance matrices to be computed on the rows and columns.
BCOT x1.1
BCOT x4.5
40
DCOT,
30
Clusteting Nos 100
k-Means x2.2
Anc
25
15
BCOT,
CDOT
10
C
COOT x19.2
15
CO0T x1.7
M-Mans x1.3
CCOT 9464
10
CCOT x97.6
22
28
26
20
240
Averag Run Time
Avemge
(a) 20 Newsgroups.
(b) Ohscal.
Figure Accuracy against training time on NG20 and Ohscal. BCOT, is the fastest and has competitive level of accuracy. BCOT gives the best accuracy while remaining relatively efficient. The multiplication factors shown for the training times take BCOT, as the reference (and so, for example, x4.5 shown for BCOT means that it is approximately 4.5 times slower than BCOT,). We were not able to benchmark CCOT-GW since failed to scale these datasets.
5.4 Term Clustering
Metrics. Unlike document clustering, there is no ground truth partition for terms, so we need to find another way of evaluating term clustering results. One generally acceptable technique to analyse the semantic coherence of the clusters obtained. To this end we introduce metric

---

based on point mutual information (PMI). PMI is frequently used information thhooreti metric for quantifying the relationship between pairs of discrete random variable outcomes. The PMI measure was chosen because prior research [29] has shown that it is closely associated with human judgements in determining word relatedness. The PMI between the terms Wi and W calculated
w,; wz) = log p(w,,
(13)
p(w; ((w))(()))
In the context term clustering, given the word co-occurrence matrix K = B B the PMI is estimated as in
k. kij
PMI w;) log kgg k.j
(14)
To evaluate a partition of terms P, we propose a metric based on intra and inter PMI metrics as follows:
PMI intra (P) EiEp Ejep
(15)
PMIinter (P) EiEP Ejep kij
(16)
In this way, a good clustering should reveal high intra-cluster semantic relatedness, corresponding higher PMI values. Using the intra and inter PMIs, we propose the following coherence index
coherence (P)
1
Σ PEP
IP| (PMInntra PMIInter (P)).
(17)
PEP
Our reasoning is this: the greater the semantic proximity between terms in the same clusters, and the greater the sematic distance between terms different clusters, the higher the value of coherence.
Results. Since there no ground truth number of term clusters, we use the cluster number estima- tions produced by CCOT-GW for all the other models so that it is easy to compare coherence values between them. Comparisons based on different numbers of clusters would favor the model using the larger number of clusters. Table[[show the coherences obtained across the different datasets using our approach, along with those of the baselines. It is clear that BCOT succeeds in capturing more semantics than the other approaches since, whatever the dataset, one or other of the two BCOT variants gives the highest coherence.
Table 4: Term clustering performance on the four datasets. OOM denotes out of memory.
Method
ACM
DBLP
PubMed
Wiki
Ng20
Ohscal
k-Means
0.19=0.01
0.05+0.03
0.31
0.28+0.02
0.28+0.04
0.01+0.02
CCOT 0.03+0.00
-0.07+0.06
0.02+0.01
0.02+0.00
0.05+0.00
0.06+0.00
CCOT-GW
0.08=0.00
0,03#0.00
OOM
0.01#0.00
0OM
OOM
COOT
0.12+0.01
0.07=0.00
0.14#0.01
0.40#0.00
0.43+0.02
0.23+0.01
COOT
0.21#0.00
0.04#0.00
-0.00+0.00
-0.08+0.00
-0.02+0.00
-0.13+0.00
BCOT
0.27=0.01
0.22+0.04
0.54
0.6420.01
0.7920.01
0.44+0.00
BCOT
0.24+0.00
0.1620.02
0.57+0.01
0.62+0.01
0.27+0.01
0.35+0.00
5.5
Statistical Significance
We performed a Nemenyi post-hoc test (28 8 with a confidence level of 90% on the document
and term clustering results that we obtained, to determine whether our model outperforms other OT biclustering approaches in statistically significant way. To conduct this test we generated 20 performance rankings of the OT biclustering models based on their performance for each dataset and quality metric pair for both document and term clustering. Figure 4 shows the results of the test. We see that two differently performing groups were identified, one comprising BCOT and BCOT, and giving better results than the other group comprising the remaining COOT and CCOT variants. This indicates that with this specific number of datasets and metrics the test was unable tell COOT and CCOT apart in a statistically significant way.

---

CD
2
3
CCOT-GW
BCOT;
CCOT
COOT
COOT
Figure 4: Result of the Nemenyi post hoc test.
Conclusion
Clustering and biclustering through optimal transport is still at a nascent stage, with many challenges remaining unsolved. This paper introduces a novel problem for biclustering using optimal transport that takes into account the sparse nature of certain types of dyadic data such document-tern matrices, to enable more computationally efficient resolution. The problem is posed as a bilinear program that solve using efficient block coordinate descent algorithm to find vertex solution. Experiments on a number of document-temm datasets suggest that the proposed approach does a good job finding clusters that correspond ground truth document classes, while generating semantically coherent partitions for the terms. In this setting, our model outperforms recent OT biclustering methods by significant margin, while being computationally efficient.
Acknowledgments and Disclosure of Funding
This work has been funded by Informatique Caisse des Dépôts et Consignations (ICDC), Association Nationale de la Recherche et de la Technologie (ANRT), and Idex- Idex-Spectrans of Université Paris Cité.
References
[1] Séverine Affeldt, Lazhar Labiod, and Mohamed Nadif. Regularized bi-directional co-clustering. Statistics and Computing, 31(3):1-17, 2021.
[2] Nir Ailon, Noa Avigdor-Elgrabli Edo Liberty, and Anke Van Zuylen. Improved approximation algorithms for bipartite correlation clustering, SIAM Journal on Computing, 110-)1110--111,, 2012.
[3] Michael Barber. Modularity and community detection in bipartite networks. Physical Review E, 76(6):066102, 2007.
[4] Deng Cai, Xiaofei He, Xiaoyun Wu, and Jiawei Han. Non-negative matrix factorization on manifold. In 2008 eighth IEEE international conference on data mining, pages 63-72. IEEE, 2008.
[5) Lenaic Chizat, Pierre Roussillon, Flavien Léger, François-Xavier Vialard, and Gabriel Peyré. Faster wasserstein distance estimation with the sinkhorn divergence. Advances in Neural Information Processing Systems, 33:2257-2269, 2020.
[6] Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.
[7] David L Davies and Donald W Bouldin. A cluster separation measure. IEEE transactions pattern analysis and machine intelligence, (2):224-22) 227, 1979.
[8] Janez Demšar. Statistical comparisons of classifiers over multiple data sets. The Journal of Machine Learning Research, 7:1-30, 2006.
[9] Inderjit S Dhillon. Co-clustering documents and words using bipartite spectral graph partitioning. In Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, pages 269-274, 2001.
10

---

[10] Inderjit S Dhillon, Subramanyam Mallela, and Dharmendra S Modha. Coormation-theoretii co- clustering. In Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 89-98, 2003.
[11] Sara Dolnicar, Sebastian Kaiser, Katie Lazarevski, and Friedrich Leisch. Biclustering: Over- coming data dimensionality problems in market segmentation. Journal of Travel Research, 51 (1):41 11:41-49,20 2012.
[12] Michael B Eisen, Paul T Spellman, Patrick O Brown, and David Botstein, Cluster analysis and display of genome-wide expression patterns. Proceedings of the National Academy of Sciences, (5(25):44633-44800 1998.
[13] Shaohua Fan, Xiao Wang, Chuan Shi, Emiao Lu, Ken Lin, and Bai Wang. One2multi graph autoencoder for multi-view graph clustering. In Proceedings of The Web Conference 2020, pages 3070-3076, 2020.
[14] Chakib Fettal, Lazhar Labiod, and Mohamed Nadif. Efficient graph convolution for joint node representation learning and clustering. In Proceedings of the Fifteenth ACM International Conference Web Search and Data Mining, pages 289-297, 2022.
[15] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Alaya, Aurélic Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, al. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78):1-8, 2021.
[16] Aden Forrow, fan-Christian Hütter, Mor Nitzan, Philippe Rigollet, Geoffrey Schiebinger, and Jonathan Weed. Statistical optimal transport via factored couplings. In The 22nd International Conference Artificial Intelligence and Statistics, pages 2454 2465. PMLR, 2019.
[17] Gérard Govaert and Mohamed Nadif. Co-clustering: models, algorithms and applications. John Wiley & Sons, 2013.
[18] Gérard Govaert and Mohamed Nadif. Mutual information, phi-squared and model-based co- clustering for contingency tables. Advances in data analysis and classification, 12(3):455-488, 2018.
[19] Jiajun Gu and Jun S Liu. Bayesian biclustering of gene expression data. BMC genomics, 9(1): 1-10, 2008.
[20] Rave Harpaz, Hector Perez, Herbert S Chase, Raul Rabadan, George Hripesak, and Carol Friedman. Biclustering of adverse drug events in the fda's spontaneous reporting system. Clinical Pharmacology Therapeutics, 2952)2243-250, 2011.
[21] John A Hartigan. Direct clustering of data matrix. Journal of the american statistical association, 67(337):123 129, 1972.
[22] William Hersh, Chris Buckley. TJ Leone, and David Hickam. Ohsumed: An interactive retrieval evaluation and new large test collection for research. In SIGIR 194, pages 192-201. Springer, 1994.
[23] Alexandre Hollocou, Thomas Bonald, and Mare Lelarge. Modularity- based sparse soft graph clustering. In The 22nd International Conference on Artificial Intelligence and Statistics, pages 323-332. PMLR, 2019.
[24] Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2(1): 193-218, 1985.
[25] Charlotte Laclau, levgen Redko, Basarab Matei, Younes Bennani, and Vincent Brault. Co- clustering through optimal transport. In International Conference on Machine Learning, pages 1955-1964. PMIR, 2017.
[26) Ken Lang. Newsweeder: Learning to filter netnews. Proceedings of the Twelfth International Conference Machine Learning, pages 331-339, 1995.

---

[27] Jean François Marcotorchino. Block seriation problems: A unified approach. reply to the problem of h. garcia and jm proth (applied stochastic models and data analysis, 1,(1). 25-34 (1985)). Applied Stochastic Models and Data Analysis, 3(2):73-91, 1987.
[28] Peter Bjorn Nemenyi. Distribution-free multiple comparisons. Princeton University, 1963.
[29] David Newman, Sarvnaz Karimi, and Lawrence Cavedon. External evaluation of topic models. In in Australasian Doc. Comp. Symp., 2009. Citeseer, 2009.
[30] Aghiles Salah and Mohamed Nadif. Model-based von mises-fisher co-clustering with a con- science. Proceedings of the 2017 SIAM International Conference on Data Mining, pages 246-254, SIAM, 2017.
[31] Meyer Scetbon, Marco Cuturi, and Gabriel Peyré. Low-rank sinkhorn factorization. In International Conference on Machine Learning, pages 9344-9354 PMLR, 2021.
[32] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93 9319999-93,-93 2008.
[33] Jonathan Templin, Robert A Henson, al. Diagnostic measurement: Theory, methods, and applications. Guilford Press, 2010.
[34] Vayer Titouan, Ievgen Redko, Rémi Flamary, and Nicolas Courty. Co-optimal transport. Advances in Neural Information Processing Systems, 33:17559-17570, 2020.
[35] Hua Wang, Feiping Nie, Heng Huang, and Fillia Makedon. Fast nonnegative matrix tri- factorization for large-scale data co-clustering. In Twenty-Second International Joint Conference on Artificial Intelligece, 2011.
[36] Jianfeng Wang, Mei Lu, Francesco Belardo, and Milan Randić, The anti-adjacency matrix of graph: Eccentricity matrix. Discrete Applied Mathematics, 251:299-3099 2018.
[37] Cheng Yang, Zhiyuan Liu, Deli Zhao, Maosong Sun, and Edward Y. Chang. Network represen- tation learning with rich text information. In IJCAI 2015.
12


Reviews:
[{"review_id": "n4CVQsoDHSg", "reviewer": "Reviewer_Piwj", "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.", "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.\n\n2. When the authors say integrating the constraint $rank(C) \\leq k$ to (4) and finally get (5), \nare the three constraints (binarity, assignment, impossible triads) included or ignored?\n\n3. 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. \n\n4. 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.\n\n5. 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.\n\n6. Page 5, is there a connection between (8) and (9) or they are two different objective functions?\n\n7. 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?\n\n8. 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.\n\n9. 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?\n", "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.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "originality\nStrength\nThis paper leverages the low-rank optimal transport to solve the biclustering problem for the dyadic data.\n\nquality\nThe 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. \n\nclarity\nWeaknesses\n(1)\tIt is unclear what’s the major advantage makes the proposed methods perform better than the others in the experiments. \n(2)\tA 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.\nsignificance\nThis 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.  \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Wa8it9NLGTe", "reviewer": "Reviewer_c4gm", "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. \n \nThe 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.\n \nFrom 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.\n", "questions": "-  In (9) L is not used; it is not well explained in which sense (9) is related to (8).\n-  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].\nComputational complexity of [26] is O(min{(n + n’)dd’ + n’^2n; (d + d’)nn’ + d’^2d})\n-    The performance of the proposed approach strongly relies on the choice of the function $L$. How much will the results change when changing $L$?\n-    Is there a way to define an optimal $L$ for a given quality measure?\n-    How the algorithm asymptotic complexity will change if one uses a dense function $L$?\n-    How much do the results depend on the regularization function $\\Omega$ in $BCOT_{\\lambda}$?\n-    How have been chosen the hyper-parameters of k-means clustering?\n \nTypos:\n -Line 99:  L(b)_{ij}    remove Z\n -Line 101: two times “between”\n- (12) L(b_{ij})\n- Line 191: in --> is\n- Line 194 is available\n -Line 280: till—>still\n \nProof of proposition 3:\nLine 445 twice L(B)W -->  L(B)W and L(B)^TZ\n", "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. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of this work is mainly based on three aspects:\n1.\tThe proposed approach generalizes many already present algorithms that can be obtained as special cases.\n2.\tThe presented algorithm is more efficient both in terms of complexity and in terms of memory usage.\n3.\tThe authors provide evidence of the effectiveness of their approach both theoretically and experimentally.\nThe 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. \n \nA 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.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Bk5mX_8U7VO", "reviewer": "Reviewer_3Scn", "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.", "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?\n\n2. 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$?\n\n3. 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?\n\n4. Empirical evaluation\n\n    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.\n    \n    4.2. What is the reasoning for the choice of datasets? Why mainly document-term matrices and not e.g., gene expression data?\n    \n    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).\n    \n    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?\n    \n    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.\n\n5. Applications\n\n    5.1. Reference [30]: What applications of biclustering do the authors discuss in this book? Could you please give some pointer to specific pages?\n\n    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.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n_Originality_: The concept to combine the block seriation problem and optimal transport to obtain block diagonal biclusters for dyadic data is a novel idea.\n\n_Quality_: In the presented work, I did not see any major technical issues and the authors provide proofs for the propositions in the appendix.\n\n_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.\n\n_Significance_: The presented results show that the proposed method is superior to existing OT based biclustering methods with respect to document-term clustering.\n\n**Weaknesses**\n\n_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. \n\n_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.\n\n_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.\n\n_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).\n\nPlease see below for a more detailed feedback.\n\n**Minor remarks & suggestions**\n\n* References:\n    - Please consider citing the peer-reviewed version instead of the arXiv version in the references (e.g. reference [24])\n    - 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\")\n    - Lines 42-43: Please consider adding references for the previous biclustering approaches, which your method generalizes\n    - Lines 61-63: Please consider adding a reference for the the Kantorovich formulation of OT\n    - Line 225: Please consider adding a reference for the Davies-Bouldin index\n    - Line 233: Please consider adding references for the employed clustering metrics\n\n* Structure: \n    - 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...\").\n    - 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.\n\n* Language/Grammar:\n    - Please consider refraining from very long sentences (e.g., lines 32-35, 140-143)\n    - Lines 103-104 is not a proper sentence\n    - Line 145: mentionned -> mentioned\n    - Line 170: \"proposed to fuzzy variant\" -> \"proposed a fuzzy variant\"\n    - Line 171: traditionanal -> traditional\n    - Line 191: in -> is\n    - Line 194: \"algorithm available\" -> \"algorithm is available\"\n    - Line 198: \"in a way that make\" -> \"in a way that makes\"\n    - Line 223: $\\lambda$ is not in subscript\n    - Line 282: \"certain types dyadic data\" -> \"certain types of dyadic data\"\n    \n* Examples for vague language:\n    - Lines 43-44: \"We propose two efficient methods for solving this problem [...]\" -> What problem?\n    - Line 98: \"Now let its [...]\" -> What is _it_?\n    - Line 107: \"[...] we are interested in inducing a couple of _almost-hard clustering_ [...]\" -> What does _a couple_ refer to?\n    - Lines 117-118: \"[...] this should not significantly change the structure of the solution [...]\"\n    - Lines 130-131: \"[...] row exemplars (or representatives or centroids)\" -> Please consider using one of these terms consistently\n    - 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_\n    - Line 200: \"[...] the computation of [...] is quite efficient [...]\"\n    - Line 209: \"[...] our model should be faster in most cases [...]\"\n    - Line 286: \"[...] the proposed approach does a good job of finding clusters [...]\"\n\n* (Suspected) minor errors:\n    - 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)$?\n     - 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\n    - Line 99: Is $\\mathbf{Z}$ a typo?   \n    - Line 158: $\\sum_{h=1}^r p(\\mathbf{b}_i, \\mathbf{b}'_j \\in h)$ -> Should it be \"$=$\" instead of \"$\\in$\"?", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept