  Clustering bipartite graphs is a fundamental task in network analysis. In the
high-dimensional regime where the number of rows $n_1$ and the number of
columns $n_2$ of the associated adjacency matrix are of different order,
existing methods derived from the ones used for symmetric graphs can come with
sub-optimal guarantees. Due to increasing number of applications for bipartite
graphs in the high dimensional regime, it is of fundamental importance to
design optimal algorithms for this setting. The recent work of Ndaoud et al.
(2022) improves the existing upper-bound for the misclustering rate in the
special case where the columns (resp. rows) can be partitioned into $L = 2$
(resp. $K = 2$) communities. Unfortunately, their algorithm cannot be extended
to the more general setting where $K \neq L \geq 2$. We overcome this
limitation by introducing a new algorithm based on the power method. We derive
conditions for exact recovery in the general setting where $K \neq L \geq 2$,
and show that it recovers the result in Ndaoud et al. (2022). We also derive a
minimax lower bound on the misclustering error when $K = L$ under a symmetric
version of our model, which matches the corresponding upper bound up to a
factor depending on $K$.
