# One-step Bipartite Graph Cut: A Normalized Formulation and Its Application
to Scalable Subspace Clustering

Si-Guo Fang, Dong Huang, Chang-Dong Wang, and Jian-Huang Lai S.-G. Fang and D.
Huang are with the College of Mathematics and Informatics, South China
Agricultural University, Guangzhou, China.
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
(Corresponding author: Dong Huang) C.-D. Wang and J.-H. Lai are with the
School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou,
China, and also with Guangdong Key Laboratory of Information Security
Technology, Guangzhou, China, and also with Key Laboratory of Machine
Intelligence and Advanced Computing, Ministry of Education, China.
E-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The bipartite graph structure has shown its promising ability in facilitating
the subspace clustering and spectral clustering algorithms for large-scale
datasets. To avoid the post-processing via $k$-means during the bipartite
graph partitioning, the constrained Laplacian rank (CLR) is often utilized for
constraining the number of connected components (i.e., clusters) in the
bipartite graph, which, however, neglects the distribution (or normalization)
of these connected components and may lead to imbalanced or even ill clusters.
Despite the significant success of normalized cut (Ncut) in general graphs, it
remains surprisingly an open problem how to enforce a one-step normalized cut
for bipartite graphs, especially with linear-time complexity. In this paper,
we first characterize a novel one-step bipartite graph cut (OBCut) criterion
with normalized constraints, and theoretically prove its equivalence to a
trace maximization problem. Then we extend this cut criterion to a scalable
subspace clustering approach, where adaptive anchor learning, bipartite graph
learning, and one-step normalized bipartite graph partitioning are
simultaneously modeled in a unified objective function, and an alternating
optimization algorithm is further designed to solve it in linear time.
Experiments on a variety of general and large-scale datasets demonstrate the
effectiveness and scalability of our approach.

###### Index Terms:

Data clustering, Bipartite graph learning, Bipartite Graph cut, Subspace
clustering, Spectral clustering.

##  1 Introduction

Data clustering is one of the most fundamental topics in knowledge discovery
and data mining, which aims to partition a set of data samples into a number
of disjoint subsets, each referred to as a cluster. Among the clustering
techniques that have been developed, the subspace clustering technique has
been gaining increasing attention in recent years [1, 2, 3, 4], due to its
ability to explore the topological relationship between data samples while
tackling the so-called “curse of dimensionality” for high-dimensional data.

The goal of subspace clustering is to pursue a self-representation matrix
based on the self-expressive property [5, 6]. Specifically, there have been
several classical subspace clustering methods in the literature, including the
sparse subspace clustering (SSC) [7], the low-rank representation (LRR) [8],
and the least squares regression (LSR) [9]. These subspace clustering methods
[7, 8, 9] typically perform two separate steps, i.e., (i) the similarity graph
learning (via subspace learning) and (ii) the spectral partitioning, to obtain
the clustering result, yet lack the ability to adaptively and jointly achieve
the graph learning and graph partitioning. To bridge this gap, Li et al. [10]
proposed a subspace clustering method which is able to jointly learn the
similarity graph and the segmentation. In spite of the efforts to (partially)
address the unified formulation problem, another common limitation to most of
previous subspace clustering methods [7, 8, 9, 10, 11] is that they typically
suffer from the cubic computational complexity, which significantly restricts
their application in large-scale datasets.

Note that the subspace clustering is generally associated with the spectral
clustering, where the spectral clustering is often adopted to partition the
learned similarity matrix (via subspace learning) for the final clustering. To
make the subspace/spectral clustering feasible for large-scale datasets, the
bipartite graph formulation has recently emerged as a promising strategy to
greatly reduce the computational complexity of subspace/spectral clustering
[12, 13, 14]. Typically, it first generates $M$ anchors (also known as
representatives or landmarks) to represent the entire dataset with $k\leq M\ll
N$, where $k$ is the desired number of clusters. Then it constructs (or
learns) a bipartite graph that connects the $N$ original samples and the $M$
anchors, which can be regarded as encoding the full sample-wise relationships
through a small number of anchors [15] and is able to significantly alleviate
the time and space complexity of subspace clustering and spectral clustering.
Specifically, the Nyström approximation method [12] randomly selects a certain
number of anchors to construct the bipartite graph. Cai et al. [13] proposed
the landmark-based spectral clustering (LSC) method, which selects the anchors
by performing the $k$-means clustering and then constructs a sparse affinity
matrix (corresponding to a bipartite graph) for later spectral partitioning.
Huang et al. [14] presented the ultra-scalable spectral clustering (U-SPEC)
method, where a hybrid anchor selection strategy and a fast $K$-nearest
neighbor approximation technique are devised to efficiently construct the
bipartite graph and then the transfer cut [16] is utilized to partition the
bipartite graph.

Although the bipartite graph based subspace/spectral clustering methods [12,
13, 14] have achieved significant progress in reducing the computational
complexity, yet most of them rely on some heuristic combinations of multiple
separate steps, and are especially faced with two critical issues.

  * •

In the bipartite graph construction process, the bipartite graphs in previous
works [12, 13, 14] are mostly predefined, which are separated from the later
partitioning process and lack the desired ability of adaptive graph learning.

  * •

In the bipartite graph partitioning process, they mostly require an additional
$k$-means step to construct the clustering from the spectral embedding, which
fail to directly learn the discrete clustering structure and may be influenced
by the instability of the $k$-means discretization.

Recently some efforts have been made to deal with the direct (or one-step)
graph partitioning problem. A popular technique to directly learn the discrete
clustering structure is the constrained Laplacian rank (CLR) strategy [17, 18,
3]. It obtains the final clustering labels from the graph connectivity
perspective by constraining the rank of the Laplacian matrix. More
specifically, it typically learns a graph with a certain number of connected
components, where each connected component naturally forms a final cluster.
For example, Nie et al. [18] proposed a graph-based clustering method based on
the CLR strategy, which directly learns a similarity graph with a certain
number of connected components. Li et al. [19] employed a rank-constrained
similarity graph to recover the block-diagonal structure of an initial graph,
where the learned embedding and the low-dimensional projection are jointly
optimized. Zhong et al. [20] imposed a rank constraint on the self-
representation matrix, and took into consideration both the global and local
structures in subspace learning and graph regularization. Note that the above-
mentioned CLR-based methods [18, 19, 20] are designed for the general graph
(typically with a $N\times N$ similarity matrix), which may not be feasible
for very large datasets. To alleviate the computational bottleneck, Nie et al.
[21] further proposed a co-clustering method, where the CLR constraint is
imposed on the bipartite graph and thus the computational complexity can be
significantly reduced. Kang et al. [3] proposed a bipartite graph learning
method with a connectivity constraint, where a structured bipartite graph can
be adaptively learned in a subspace clustering framework.

These existing CLR-based clustering methods [18, 19, 20, 21, 3] aim to build a
similarity graph with a desired number of connected components (or clusters),
which, however, neglect the distribution (or normalization) of these connected
components. In the conventional spectral clustering algorithms, such as the
normalized cut (Ncut) [22], the normalization of clusters plays an important
role in avoiding the generation of some heavily imbalanced or even ill
clusters (e.g., a cluster with a few or a single data sample). Yet
surprisingly, under the bipartite graph setting, it remains an open problem
how to simultaneously enforce bipartite graph learning and normalized (or
balanced) partitioning without requiring additional post-processing, while
maintaining high efficiency for large-scale datasets.

To address this, this paper presents a novel one-step bipartite graph cut
(OBCut) approach, which for the first time, to our knowledge, formulates and
solves the one-step bipartite graph learning and partitioning problem with
normalized constraints. Particularly, we theoretically characterize a novel
bipartite graph cut criterion, which can be equivalently transformed into a
matrix trace form and is capable of balancing both the node size and the edge
volume of each cluster. Theoretical analysis reveals the connection between
the proposed bipartite graph cut criterion and two classical cut criteria
(i.e., the RatioCut and the Ncut). Then, we integrate the bipartite graph cut
criterion into an anchor-based subspace clustering framework, which
simultaneously enforces adaptive anchor learning, bipartite graph learning,
and normalized bipartite graph partitioning in a unified objective function.
Further, an efficient optimization algorithm is designed to directly learn the
discrete cluster indicator matrix without additional post-processing, which
notably has linear time complexity in sample size. Extensive experiments are
conducted on eight real-world general-scale and large-scale datasets, whose
data sizes range from 832 to 195,537 and dimensions range from 7 to 30,000.
The experimental results demonstrate the superiority of our OBCut approach
over the state-of-the-art subspace/spectral clustering approaches.

The main contributions of this paper are summarized as follows.

  * •

A new normalized bipartite graph cut criterion is theoretically characterized,
which can be equivalently transformed into a trace maximization problem and is
featured by its ability to achieve one-step graph cut with the node size and
the edge volume of each cluster simultaneously balanced.

  * •

A scalable subspace clustering approach is proposed based on the new bipartite
graph cut criterion, which formulates the adaptive anchor learning, the
bipartite graph learning, and the one-step normalized bipartite graph
partitioning into a unified optimization framework.

  * •

An alternating minimization algorithm is designed to solve this optimization
problem in linear time. Experiments on a variety of datasets have confirmed
the advantageous performance of our approach over the state-of-the-art.

The remainder of this paper is organized as follows. The related works on
spectral clustering, subspace clustering, and one-step clustering are reviewed
in Section 2. The proposed OBCut approach is described in Section 3. The
optimization algorithm and its theoretical analysis are provided in Section 4.
The experimental results are reported in Section 5. Finally, this paper is
concluded in Section 6.

##  2 Related Work

In this section, the related works on spectral clustering, subspace
clustering, and one-step clustering will be reviewed in Sections 2.1, 2.2, and
2.3, respectively.

###  2.1 Spectral Clustering

Spectral clustering has shown its advantage in discovering clusters with
nonlinearly separable shapes. But the conventional spectral clustering
typically suffers from its cubic time complexity, which restricts its
applications in large-scale datasets.

In recent years, some fast approximation methods (e.g., the bipartite graph
based methods) have gained increasing popularity for alleviating the huge
computational burden of spectral clustering [23, 13, 24, 25, 14, 26, 27]. For
example, Liu et al. [23] constructed a small set of supernodes from the
original nodes in the similarity graph, and connected these supernodes with
the original nodes to form a bipartite graph, based on which an efficient
spectral clustering method is presented. Cai et al. [13] selected a set of
landmarks (or anchors) via the $k$-means clustering, and proposed the
landmark-based representation for large-scale spectral clustering. He et al.
[24] designed a fast large-scale spectral clustering method with the explicit
feature mapping leveraged to speed up the eigenvector approximation. Wu et al.
[25] utilized a positive Euler kernel to generate a non-negative similarity
matrix and further developed an Euler spectral clustering method, which can be
optimized by an efficient Stiefel-manifold-based gradient algorithm. Huang et
al. [14] proposed an ultra-scalable spectral clustering (U-SPEC) method based
on hybrid anchor selection and fast $K$-nearest neighbor approximation. Cheng
et al. [27] designed an approximate spectral clustering method via dense cores
and density peaks, which constructs a decision graph by computing the geodesic
distances between the dense cores and then expands the partitioning result of
the dense cores to the data samples in the entire dataset.

###  2.2 Subspace Clustering

Subspace clustering aims to learn a subspace representation matrix, upon which
the similarity matrix can be derived and thus the final clustering can be
obtained by partitioning this similarity matrix (typically via spectral
clustering) [28, 3]. In subspace clustering, it is generally assumed that all
data samples lie in multiple low-dimensional subspaces and can be expressed as
a linear combination of the other samples in the same subspace [28, 3].

Many subspace clustering works have been developed in the literature. For
example, You et al. [11] proposed a sparse subspace clustering method via the
orthogonal matching pursuit algorithm. Peng et al. [29] utilized a sparse
L2-Graph to alleviate the potentially negative effects of the errors from the
subspace representation. Lu et al. [30] designed a block diagonal matrix
induced regularizer to learn the self-representation for subspace clustering.
Chang et al. [31] employed the low-rank representation to learn a structured
bipartite graph for subspace clustering, which can avoid the extra post-
processing when obtaining the final clustering labels. Nie et al. [28]
introduced a rank minimization problem, where a subspace indicator (i.e., the
cluster indicator) can be learned by optimizing a relaxed piece-wise objective
function. Fan et al. [32] proposed a matrix factorization model for efficient
subspace clustering, which can assign the data samples to the corresponding
subspace directly. Nie et al. [33] integrated the anchor learning and the
structured bipartite graph learning into a subspace clustering framework via
CLR. Though some efforts have been made to directly learn the discrete
clustering structure [31, 33, 3], they typically seek to constrain the number
of connected components in the graph (especially via CLR) yet lack the ability
to consider the distribution (or normalization) of these connected components.

###  2.3 One-step Clustering

The subspace clustering is frequently associated with the spectral clustering,
where the spectral clustering is performed on the learned similarity matrix
(from the subspace representation) to obtain the final clustering.

Conventional spectral clustering typically comply with the two-step
formulation, where the spectral embedding is learned via eigen-decomposition
in the first step and the $k$-means discretization is performed on the
spectral embedding in the second step, which, however, cannot optimize these
two steps simultaneously and may be negatively influenced by the instability
of $k$-means [34]. Recently, some one-step spectral clustering methods have
been proposed to obtain the discrete clustering solution without post-
processing.

One strategy is to employ the spectral rotation, which optimizes the
continuous spectral embedding and the discrete cluster indicator matrix
simultaneously to avoid the potential information loss that arises from the
two-step methods [35]. For example, Yang et al. [36] imposed the nonnegative
constraint on the spectral embedding, and presented a novel spectral
clustering method with nonnegativity, discreteness, and discrimination. Pang
et al. [37] proposed a joint model to optimize the spectral embedding and the
binary cluster indicator matrix simultaneously. Lu et al. [35] integrated
multiple kernel $k$-means (MKKM) and the spectral rotation into a unified
framework. Another strategy is to directly compute the discrete cluster
indicator matrix without relaxation. Chen et al. [38] directly solved the
normalized cut and obtained the discrete cluster indicator matrix by
optimizing the classical normalized cut model without extra post-processing.
Some recent studies [39, 40] show that the classic $k$-means clustering and
the spectral clustering can be reformulated as a unified framework, where the
clustering labels can be directly learned during their optimization process.
Despite the significant progress, these one-step spectral clustering methods
are mostly designed for the general graph (typically with an $N\times N$
similarity matrix), which are not feasible for the bipartite graph. More
recently, some attempts have been carried out to enable the one-step spectral
clustering for the bipartite graph [3], which utilize the Laplacian low-rank
constraint to control the number of connected components, but may still suffer
from imbalanced or ill clusters due to their lack of the ability in conducting
direct and normalized bipartite graph cut.

##  3 Methodology

In this section, we describe the proposed OBCut approach in detail.
Specifically, the notations are summarized in Section 3.1. The adaptive
bipartite graph construction via subspace learning is formulated in Section
3.2. The normalized bipartite graph cut criterion is presented in Section 3.3.
The computation of the new cut criterion is analyzed in Section 3.4. Finally,
Section 3.5 provides the unified formulation of our OBCut approach.

###  3.1 Notations

Throughout this paper, the set is written as uppercase blackboard bold, such
as $\mathbb{R}$. The vector and the matrix are written as lowercase boldface
and uppercase boldface, respectively. Given a matrix
$\textbf{B}\in\mathbb{R}^{N\times M}$, its $(i,j)$-th entry is denoted as
$b_{ij}$ or $\textbf{B}(i,j)$, and its $i$-th row and $j$-th column are
denoted as $\textbf{b}_{i:}$ (or $\textbf{B}(i,:)$) and $\textbf{b}_{:j}$ (or
$\textbf{B}(:,j)$), respectively. Let the transpose of matrix B be denoted as
$\textbf{B}^{\top}$, and the $F$-norm of B be denoted as
$||\textbf{B}||_{F}=\sqrt{\sum_{i=1}^{N}\sum_{j=1}^{M}b_{ij}^{2}}=\sqrt{Tr(\textbf{B}^{\top}\textbf{B})}$,
where $Tr(\cdot)$ is the trace of the matrix. Let I denote the identity
matrix, 1 denote a column vector with all entries being one, and
$\textbf{B}\geq 0$ denote that all the entries in this matrix are larger than
or equal to zero. For clarity, the main mathematical notations and their
descriptions used in this paper are shown in Table I.

TABLE I: Summary of Notations Notations |  Descriptions
---|---
$\mathbb{S}_{i}$ |  The sample set in the $i$-th cluster
$\mathbb{A}_{j}$ |  The anchor set in the $j$-th cluster
$N$ |  The number of samples
$M$ |  The number of anchors
$k$ |  The number of clusters
$d$ |  Dimension
$\textbf{X}\in\mathbb{R}^{d\times N}$ |  Data matrix
$\textbf{A}\in\mathbb{R}^{d\times M}$ |  The anchor matrix
$\textbf{B}\in\mathbb{R}^{N\times M}$ |  The similarity matrix of a bipartite graph
$\textbf{Y}\in\\{0,1\\}^{N\times K}$ |  The discrete cluster indicator matrix
$\textbf{H}\in\mathbb{R}^{M\times K}$ |  The spectral embedding matrix for anchors

###  3.2 Adaptive Bipartite Graph Construction via Anchor-Based Subspace
Learning

Given a data set with $N$ data samples, let $\textbf{X}\in\mathbb{R}^{d\times
N}$ denote its data matrix, where the $i$-th column is the feature vector of
the $i$-th sample and $d$ is the dimension.

In the conventional bipartite graph formulation, to select a set of anchors,
the random sampling based selection and the $k$-means based selection are two
of the most frequently-used strategies [13, 41]. However, the random sampling
based anchor selection may not sufficiently reflect the overall distribution
of the data [42], while the $k$-means based selection is able to discover a
set of more representative anchors but cannot well handle the non-linearly
separable data. Recently, some studies have gone beyond the conventional
random sampling based or $k$-means based anchor selection to explore more
effective strategies, such as the hybrid representative selection (HRS) [14],
the directly alternate sampling (DAS) [17], and the variance-based de-
correlation anchor selection (VDA) [42]. The HRS strategy performs the random
sampling and the $k$-means clustering sequentially, which strikes a balance
between the effectiveness of the $k$-means based selection and the efficiency
of the random sampling based selection. Both the DAS and VDA strategies
compute the score of each sample point by a self-defined function so as to
measure the importance of the sample for anchor selection.

Despite the considerable progress, the previous works [13, 41, 42, 14, 17]
mostly tend to select the anchors in a fixed manner, yet cannot go beyond the
conventional (fixed) anchor selection to enforce the adaptive anchor learning
or even the joint modeling of anchor learning and bipartite graph learning.

In this paper, we seek to jointly and adaptively learn the anchor matrix
$\textbf{A}\in\mathbb{R}^{d\times M}$ and the bipartite graph
$\textbf{B}\in\mathbb{R}^{N\times M}$, where $M$ is the number of anchors. It
follows the basic assumption of subspace learning that each sample can be
written as an affine or linear combination of the learned anchors, that is,
$\textbf{X}=\textbf{A}\textbf{B}^{\top}+\textbf{E}$, where
$\textbf{E}\in\mathbb{R}^{d\times N}$ is the error term. To adaptively learn
the anchor matrix and the bipartite graph, we define the objective function as

$\displaystyle\min_{\textbf{A},\textbf{B}}~{}$
$\displaystyle||\textbf{X}-\textbf{A}\textbf{B}^{\top}||_{F}^{2}$
$\displaystyle s.t.~{}$
$\displaystyle\textbf{B}\textbf{1}=\textbf{1},\textbf{B}\geq 0,$ (1)

where the constraints $\textbf{B}\textbf{1}=\textbf{1}$ and $\textbf{B}\geq 0$
restrict each entry in B to $0\leq b_{ij}\leq 1$. In the following, this
objective function will serve as the graph learning term in our unified
objective function in Section 3.5 .

###  3.3 Normalized Formulation of Bipartite Graph Cut

Besides the bipartite graph learning, we proceed to formulate the bipartite
graph partitioning, for which purpose we for the first time, to the best of
our knowledge, theoretically characterize a one-step bipartite graph cut
criterion with normalization and optimize it in linear time.

Previous bipartite graph based methods [12, 13, 14] generally involve a two-
step process for graph partitioning, which first conduct eigen-decomposition
on the bipartite graph (to obtain the spectral embedding by stacking the first
$k$ eigen-vectors), and then build the final clustering labels by performing
$k$-means on the spectral embedding. Instead of following the conventional
two-step formulation, we propose a new one-step bipartite graph cut criterion
in this section. Specifically, we first propose a variant of RatioCut [43] for
the bipartite graph, and then, inspired by the normalized cut (Ncut) [22],
extend this variant to a normalized formulation of the bipartite graph cut.

Given a bipartite graph $\textbf{G}(\mathbb{S},\mathbb{A},\textbf{B})$ with
$\textbf{B}=(b_{ij})\in\mathbb{R}^{N\times M}$, where $\mathbb{S}$ is the
sample set with $N$ elements, $\mathbb{A}$ is the anchor set with $M$ ($M\ll
N$) elements, and $b_{ij}>0$ denotes the weight of the edge between the $i$-th
sample and the $j$-th anchor. Let $b_{ij}=0$ if there is no edge between the
$i$-th sample and the $j$-th anchor. Note that each edge in
$\textbf{G}(\mathbb{S},\mathbb{A},\textbf{B})$ has one endpoint in
$\mathbb{S}$ and one endpoint in $\mathbb{A}$. That is, there are no edges
between two samples or between two anchors. For convenience, we can use the
similarity matrix B to represent the bipartite graph
$\textbf{G}(\mathbb{S},\mathbb{A},\textbf{B})$.

In graph theory, for two disjoint sets $\mathbb{S}_{i}$ and $\mathbb{A}_{j}$,
a cut between $\mathbb{S}_{i}$ and $\mathbb{A}_{j}$ is defined as

$\displaystyle
cut(\mathbb{S}_{i},\mathbb{A}_{j})=\sum\limits_{n\in\mathbb{S}_{i},m\in\mathbb{A}_{j}}\textbf{B}(n,m).$
(2)

The sample set $\mathbb{S}$ and the anchor set $\mathbb{A}$ can be partitioned
into multiple disjoint sets, i.e.,
$\mathbb{S}=\mathbb{S}_{1}\cup\cdots\cup\mathbb{S}_{k}$ with
$\mathbb{S}_{i}\cap\mathbb{S}_{j}=\emptyset~{}(\forall i\neq j)$, and
$\mathbb{A}=\mathbb{A}_{1}\cup\cdots\cup\mathbb{A}_{k}$ with
$\mathbb{A}_{i}\cap\mathbb{A}_{j}=\emptyset~{}(\forall i\neq j)$, where $k$ is
the number of clusters. Note that the elements of the pair
$(\mathbb{S}_{i},\mathbb{A}_{i})$ belong to the same cluster. By removing
edges between different clusters, the degree of similarity between different
clusters can be formulated as the sum of the weights of the edges that have
been removed. The simplest and most direct aim of clustering (or graph
partitioning) is to minimize the similarity between all different clusters,
that is

$\displaystyle
cut((\mathbb{S}_{1},\mathbb{A}_{1}),\cdots,(\mathbb{S}_{k},\mathbb{A}_{k}))$
$\displaystyle=$
$\displaystyle\frac{1}{2}\sum\limits_{i=1}^{k}(cut(\mathbb{S}_{i},\mathop{\cup}_{j\neq
i}\mathbb{A}_{j})+cut(\mathop{\cup}_{j\neq i}\mathbb{S}_{j},\mathbb{A}_{i})).$
(3)

According to [22, 44], the minimum cut criterion tends to cut out imbalanced
clusters, especially for the isolated nodes in the bipartite graph. Inspired
by the RatioCut, we formulate the following variant of the cut in (3.3):

$\displaystyle\sum\limits_{i=1}^{k}(\frac{cut(\mathbb{S}_{i},\mathop{\cup}\limits_{j\neq
i}\mathbb{A}_{j})}{|\mathbb{S}_{i}|}+\frac{cut(\mathop{\cup}\limits_{j\neq
i}\mathbb{S}_{j},\mathbb{A}_{i})}{|\mathbb{A}_{i}|}).$ (4)

This definition in (4) can balance the number of samples between different
clusters, but it cannot balance the number of samples and that number of
anchors in the same cluster. In view of this, we seek a partition of
$\textbf{G}(\mathbb{S},\mathbb{A},\textbf{B})$, where the ratios of samples
and anchors belonging to the same cluster should be as similar as possible.
Thus we have the following variant of (4):

$\displaystyle\sum\limits_{i=1}^{k}$
$\displaystyle(\frac{cut(\mathbb{S}_{i},\mathop{\cup}\limits_{j\neq
i}\mathbb{A}_{j})}{|\mathbb{S}_{i}|}+\frac{cut(\mathop{\cup}\limits_{j\neq
i}\mathbb{S}_{j},\mathbb{A}_{i})}{|\mathbb{A}_{i}|}$
$\displaystyle+cut(\mathbb{S}_{i},\mathbb{A}_{i})(\frac{1}{\sqrt{|\mathbb{S}_{i}|}}-\frac{1}{\sqrt{|\mathbb{A}_{i}|}})^{2}).$
(5)

Let P be the augmented graph of B defined as [17]

$\displaystyle\textbf{P}=\begin{bmatrix}&\textbf{B}\\\ \textbf{B}^{\top}&\\\
\end{bmatrix}\in\mathbb{R}^{(N+M)\times(N+M)}.$ (6)

The degree matrix $\textbf{D}=diag(\textbf{P}\textbf{1})$ is a diagonal
matrix. It can also be written in a block-diagonal form, that is

$\displaystyle\textbf{D}=\begin{bmatrix}\textbf{D}_{(N)}&\\\
&\textbf{D}_{(M)}\\\ \end{bmatrix},$ (7)

where $\textbf{D}_{(N)}=diag(\textbf{B}\textbf{1})$ and
$\textbf{D}_{(M)}=diag(\textbf{B}^{\top}\textbf{1})$. Thus the graph Laplacian
of the bipartite graph $\textbf{G}(\mathbb{S},\mathbb{A},\textbf{B})$ can be
written as $\textbf{L}=\textbf{D}-\textbf{P}$.

Note that the definition of Eq. (3.3) does not consider the degree of each
point (i.e., each node). Inspired by the Ncut, it is intuitive that, not only
the number of nodes in each cluster, but also the sum of edge weights (i.e.,
the sum of degrees of all nodes) in each cluster should be balanced. Thus we
present the following bipartite graph cut criterion:

$\displaystyle Bip$ $\displaystyle
artiteGraphCut((\mathbb{S}_{1},\mathbb{A}_{1}),\cdots,(\mathbb{S}_{k},\mathbb{A}_{k}))$
$\displaystyle=\sum\limits_{i=1}^{k}$
$\displaystyle(\frac{cut(\mathbb{S}_{i},\mathop{\cup}\limits_{j\neq
i}\mathbb{A}_{j})}{|\mathbb{S}_{i}|}+\frac{cut(\mathop{\cup}\limits_{j\neq
i}\mathbb{S}_{j},\mathbb{A}_{i})}{|\mathbb{A}_{i}|}$
$\displaystyle+cut(\mathbb{S}_{i},\mathbb{A}_{i})(\frac{1}{\sqrt{|\mathbb{S}_{i}|}}-\frac{1}{\sqrt{|\mathbb{A}_{i}|}})^{2}$
$\displaystyle-\frac{\sum\limits_{n\in\mathbb{S}_{i}}\textbf{D}_{(N)}(n,n)}{|\mathbb{S}_{i}|}-\frac{\sum\limits_{m\in\mathbb{A}_{i}}\textbf{D}_{(M)}(m,m)}{|\mathbb{A}_{i}|}).$
(8)

An important property of the proposed cut criterion in (3.3) is that it can be
equivalently expressed as the matrix trace form, that is

$\displaystyle\min~{}BipartiteGraphCut((\mathbb{S}_{1},\mathbb{A}_{1}),\cdots,(\mathbb{S}_{k},\mathbb{A}_{k}))$
$\displaystyle\Leftrightarrow$
$\displaystyle\max\limits_{\bar{\textbf{Y}}_{(N)}\in
Nind(\mathbb{S},k),\bar{\textbf{Y}}_{(M)}\in
Nind(\mathbb{A},k)}Tr(\bar{\textbf{Y}}_{(N)}^{\top}\textbf{B}\bar{\textbf{Y}}_{(M)}),$
(9)

where the definitions of $\bar{\textbf{Y}}_{(N)}$ and
$\bar{\textbf{Y}}_{(M)}$, and the proof of the equivalence in (3.3) will be
shown in Section 3.4.

###  3.4 Computing of the Cut Criterion

In this section, we describe the definition of the normalized indicator and
theoretically prove that the above-mentioned bipartite graph cut criterion can
be equivalently expressed as a brief matrix trace form.

######  Definition 1.

Given a partition of $\mathbb{S}$ into $k$ sets
$\mathbb{S}_{1},\cdots,\mathbb{S}_{k}$ with $|\mathbb{S}|=N$, we define the
set of normalized indicators from the partition of $\mathbb{S}$ by
Nind$(\mathbb{S},k)$. One of the normalized indicators is defined as

$\bar{\textbf{Y}}_{(N)}(i,j)=\left\\{\begin{aligned}
&\frac{1}{\sqrt{|\mathbb{S}_{j}|}}&\text{if}~{}i\in\mathbb{S}_{j},\\\
&0&\text{otherwise}.\end{aligned}\right.$ (10)

where $i=1,\cdots,N$ and $j=1,\cdots,k$. Then we have
$Nind(\mathbb{S},k)=\\{\bar{\textbf{Y}}_{(N)}|\bar{\textbf{Y}}_{(N)}^{\top}\bar{\textbf{Y}}_{(N)}=\textbf{I},\bar{\textbf{Y}}_{(N)}$
as defined in (10)$\\}$.

Thereafter, we have the following theorem.

######  Theorem 1.

Given a bipartite graph $\textbf{G}(\mathbb{S},\mathbb{A},\textbf{B})$, with
$|\mathbb{S}|=N$ and $|\mathbb{A}|=M$, the following conclusion holds:

$\displaystyle\min~{}BipartiteGraphCut((\mathbb{S}_{1},\mathbb{A}_{1}),\cdots,(\mathbb{S}_{k},\mathbb{A}_{k}))$
$\displaystyle\Leftrightarrow$
$\displaystyle\max\limits_{\bar{\textbf{Y}}_{(N)}\in
Nind(\mathbb{S},k),\bar{\textbf{Y}}_{(M)}\in
Nind(\mathbb{A},k)}Tr(\bar{\textbf{Y}}_{(N)}^{\top}\textbf{B}\bar{\textbf{Y}}_{(M)}).$
(11)

###### Proof.

Let $\bar{\textbf{Y}}=[\bar{\textbf{Y}}_{(N)};\bar{\textbf{Y}}_{(M)}]$, where
$\bar{\textbf{Y}}_{(N)}\in Nind(\mathbb{S},k)$ and $\bar{\textbf{Y}}_{(M)}\in
Nind(\mathbb{A},k)$. According to the definitions of D in Eq. (7) and
$\bar{\textbf{Y}}$, we have

$\displaystyle\sum\limits_{i=1}^{k}(\frac{\sum\limits_{n\in\mathbb{S}_{i}}\textbf{D}_{(N)}(n,n)}{|\mathbb{S}_{i}|}+\frac{\sum\limits_{m\in\mathbb{A}_{i}}\textbf{D}_{(M)}(m,m)}{|\mathbb{A}_{i}|})$
$\displaystyle=$ $\displaystyle
Tr(\bar{\textbf{Y}}_{(N)}^{\top}\textbf{D}_{(N)}\bar{\textbf{Y}}_{(N)}+\bar{\textbf{Y}}_{(M)}^{\top}\textbf{D}_{(M)}\bar{\textbf{Y}}_{(M)})$
$\displaystyle=$ $\displaystyle
Tr(\bar{\textbf{Y}}^{\top}\textbf{D}\bar{\textbf{Y}}).$ (12)

Moreover, for the cluster $(\mathbb{S}_{i},\mathbb{A}_{i})$, according to the
definition of the cut in Eq. (2), we know that

$\displaystyle\frac{cut(\mathbb{S}_{i},\mathop{\cup}\limits_{j\neq
i}\mathbb{A}_{j})}{|\mathbb{S}_{i}|}+\frac{cut(\mathop{\cup}\limits_{j\neq
i}\mathbb{S}_{j},\mathbb{A}_{i})}{|\mathbb{A}_{i}|}$
$\displaystyle+cut(\mathbb{S}_{i},\mathbb{A}_{i})(\frac{1}{\sqrt{|\mathbb{S}_{i}|}}-\frac{1}{\sqrt{|\mathbb{A}_{i}|}})^{2}$
$\displaystyle=$
$\displaystyle\sum\limits_{n\in\mathbb{S}_{i},m\notin\mathbb{A}_{i}}\frac{b_{nm}}{|\mathbb{S}_{i}|}+\sum\limits_{n\notin\mathbb{S}_{i},m\in\mathbb{A}_{i}}\frac{b_{nm}}{|\mathbb{A}_{i}|}$
$\displaystyle+\sum\limits_{n\in\mathbb{S}_{i},m\in\mathbb{A}_{i}}b_{nm}(\frac{1}{\sqrt{|\mathbb{S}_{i}|}}-\frac{1}{\sqrt{|\mathbb{A}_{i}|}})^{2}$
$\displaystyle=$
$\displaystyle\sum\limits_{n\in\mathbb{S}_{i},m\notin\mathbb{A}_{i}}b_{nm}(\frac{1}{\sqrt{|\mathbb{S}_{i}|}}-0)^{2}+\sum\limits_{n\notin\mathbb{S}_{i},m\in\mathbb{A}_{i}}b_{nm}(0-\frac{1}{\sqrt{|\mathbb{A}_{i}|}})^{2}$
$\displaystyle+\sum\limits_{n\in\mathbb{S}_{i},m\in\mathbb{A}_{i}}b_{nm}(\frac{1}{\sqrt{|\mathbb{S}_{i}|}}-\frac{1}{\sqrt{|\mathbb{A}_{i}|}})^{2}.$
(13)

Further, according to the definitions of $\bar{\textbf{Y}}_{(N)}$ and
$\bar{\textbf{Y}}_{(M)}$, we have that

$\displaystyle\eqref{eq:theorem_term1}=$
$\displaystyle\sum\limits_{n=1}^{N}\sum\limits_{m=1}^{M}b_{nm}(\bar{\textbf{Y}}_{(N)}(n,i)-\bar{\textbf{Y}}_{(M)}(m,i))^{2}$
$\displaystyle=$
$\displaystyle\sum\limits_{n=1}^{N}\sum\limits_{m=1}^{M}b_{nm}(\bar{\textbf{Y}}(n,i)-\bar{\textbf{Y}}(N+m,i))^{2}$
$\displaystyle=$
$\displaystyle\frac{1}{2}(\sum\limits_{n=1}^{N}\sum\limits_{m=1}^{M}b_{nm}(\bar{\textbf{Y}}(n,i)-\bar{\textbf{Y}}(N+m,i))^{2}$
$\displaystyle+\sum\limits_{m=1}^{N}\sum\limits_{n=1}^{M}b_{mn}(\bar{\textbf{Y}}(N+n,i)-\bar{\textbf{Y}}(m,i))^{2}).$
(14)

According to the definition of the augmented graph P in Eq. (6) and the
important property [43] of graph Laplacian $\textbf{L}=\textbf{D}-\textbf{P}$,
we have that

$\displaystyle\eqref{eq:theorem_term1_var1}=$
$\displaystyle\frac{1}{2}\sum\limits_{n=1}^{N+M}\sum\limits_{m=1}^{N+M}p_{nm}(\bar{y}_{ni}-\bar{y}_{mi})^{2}=\bar{\textbf{y}}_{:i}^{\top}\textbf{L}\bar{\textbf{y}}_{:i}.$
(15)

From Eqs. (3.4) and (15), and the definition of the cut criterion in Eq.
(3.3), we have that

$\displaystyle
BipartiteGraphCut((\mathbb{S}_{1},\mathbb{A}_{1}),\cdots,(\mathbb{S}_{k},\mathbb{A}_{k}))$
$\displaystyle=$
$\displaystyle\sum\limits_{i=1}^{k}\bar{\textbf{y}}_{:i}^{\top}\textbf{L}\bar{\textbf{y}}_{:i}-Tr(\bar{\textbf{Y}}^{\top}\textbf{D}\bar{\textbf{Y}})=Tr(\bar{\textbf{Y}}^{\top}\textbf{L}\bar{\textbf{Y}})-Tr(\bar{\textbf{Y}}^{\top}\textbf{D}\bar{\textbf{Y}})$
$\displaystyle=$ $\displaystyle-
Tr(\bar{\textbf{Y}}^{\top}\textbf{P}\bar{\textbf{Y}})=-2Tr(\bar{\textbf{Y}}_{(N)}^{\top}\textbf{B}\bar{\textbf{Y}}_{(M)})$
(16)

Thereby, we prove the Theorem 1. ∎

Furthermore, given the indicator matrices $\textbf{Y}\in\\{0,1\\}^{N\times k}$
and $\textbf{H}\in\\{0,1\\}^{M\times k}$, the Eq. (1) can be equivalently
represented as follows:

$\displaystyle\min~{}BipartiteGraphCut((\mathbb{S}_{1},\mathbb{A}_{1}),\cdots,(\mathbb{S}_{k},\mathbb{A}_{k}))$
(17) $\displaystyle\Leftrightarrow$ $\displaystyle\left\\{\begin{aligned}
&\max_{\textbf{Y},\textbf{H}}~{}Tr((\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}\textbf{Y}^{\top}\textbf{B}\textbf{H}(\textbf{H}^{\top}\textbf{H})^{-\frac{1}{2}})\\\
&s.t.~{}\textbf{Y}\in\\{0,1\\}^{N\times
k},\textbf{Y}\textbf{1}=\textbf{1};\textbf{H}\in\\{0,1\\}^{M\times
k},\textbf{H}\textbf{1}=\textbf{1}.\end{aligned}\right.$

With $k\leq M\ll N$, when $M=k$, we have
$\textbf{H}^{\top}\textbf{H}=\textbf{I}$, and the following Corollary holds.

######  Corollary 1.

Given a bipartite graph $\textbf{G}(\mathbb{S},\mathbb{A},\textbf{B})$, where
$|\mathbb{S}|=N$ and $|\mathbb{A}|=M=k$, for the indicator
$\textbf{Y}\in\\{0,1\\}^{N\times k}$ and $\textbf{H}\in\mathbb{R}^{M\times
k}$, the following conclusion holds:

$\displaystyle\min~{}BipartiteGraphCut((\mathbb{S}_{1},\mathbb{A}_{1}),\cdots,(\mathbb{S}_{k},\mathbb{A}_{k}))$
(18) $\displaystyle\Leftrightarrow$ $\displaystyle\left\\{\begin{aligned}
&\max_{\textbf{Y},\textbf{H}}~{}Tr((\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}\textbf{Y}^{\top}\textbf{B}\textbf{H})\\\
&s.t.~{}\textbf{Y}\in\\{0,1\\}^{N\times
k},\textbf{Y}\textbf{1}=\textbf{1};\textbf{H}^{\top}\textbf{H}=\textbf{I},\textbf{H}\geq
0.\end{aligned}\right.$

###  3.5 Unified Formulation of One-step Bipartite Graph Cut

In this section, we provide the unified formulation of our proposed OBCut
approach, where the adaptive bipartite graph learning and the one-step
normalized bipartite graph partitioning are simultaneously enforced.

Specifically, the bipartite graph B can be learned via the objective (3.2),
and can be partitioned in a one-step manner via the proposed cut criterion in
the objective (18). By relaxing the objective (18), we can rewrite it into a
more concise optimization problem as

$\displaystyle\max_{\textbf{Y},\textbf{H}}~{}$ $\displaystyle
Tr((\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}\textbf{Y}^{\top}\textbf{B}\textbf{H})$
$\displaystyle s.t.~{}$ $\displaystyle\textbf{Y}\in\\{0,1\\}^{N\times
k},\textbf{Y}\textbf{1}=\textbf{1};\textbf{H}^{\top}\textbf{H}=\textbf{I}.$
(19)

Then we proceed to unify the adaptive anchor learning, the bipartite graph
learning, and the one-step normalized bipartite graph partitioning in a joint
learning framework. Formally, we have the overall objective function of OBCut
as follows:

$\displaystyle\min_{\textbf{A},\textbf{B},\textbf{Y},\textbf{H}}~{}||\textbf{X}-\textbf{A}\textbf{B}^{\top}||_{F}^{2}-\lambda
Tr((\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}\textbf{Y}^{\top}\textbf{B}\textbf{H})$
$\displaystyle s.t.~{}\textbf{B}\textbf{1}=\textbf{1},\textbf{B}\geq
0;\textbf{Y}\in\\{0,1\\}^{N\times
k},\textbf{Y}\textbf{1}=\textbf{1};\textbf{H}^{\top}\textbf{H}=\textbf{I}.$
(20)

where $\lambda>0$ is a trade-off parameter between the anchor-based subspace
learning and the bipartite graph cut.

######  Theorem 2.

Given a bipartite graph $\textbf{B}\in\mathbb{R}^{N\times M}$ with
$|b_{ij}|\leq\alpha$ ($\alpha>0$), let the sum of entries in $\textbf{y}_{:j}$
be denoted as $n_{j}$ ($n_{j}\geq 1$). The upper bound of the objective
function value in (3.5) is $NM\alpha$.

###### Proof.

Since $\textbf{H}^{\top}\textbf{H}=\textbf{I}$, we have $|h_{ij}|\leq 1$,
$\forall i,j$. And we know that
$(\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}=diag([\frac{1}{\sqrt{n_{1}}},\frac{1}{\sqrt{n_{2}}},\cdots,\frac{1}{\sqrt{n_{k}}}])$.
Thus, we have

$\displaystyle
Tr((\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}\textbf{Y}^{\top}\textbf{B}\textbf{H})=Tr(\begin{bmatrix}\frac{\textbf{y}_{:1}^{\top}\textbf{B}}{\sqrt{n_{1}}}\\\
\frac{\textbf{y}_{:2}^{\top}\textbf{B}}{\sqrt{n_{2}}}\\\ \vdots\\\
\frac{\textbf{y}_{:k}^{\top}\textbf{B}}{\sqrt{n_{k}}}\\\
\end{bmatrix}\begin{bmatrix}\textbf{h}_{:1},\textbf{h}_{:2},\cdots,\textbf{h}_{:k}\\\
\end{bmatrix})$ $\displaystyle=$
$\displaystyle\sum\limits_{j=1}^{k}\frac{\textbf{y}_{:j}^{\top}\textbf{B}\textbf{h}_{:j}}{\sqrt{n_{j}}}\leq\sum\limits_{j=1}^{k}\textbf{y}_{:j}^{\top}\textbf{B}\textbf{h}_{:j}\leq\sum\limits_{j=1}^{k}n_{j}M\alpha=NM\alpha.$
(21)

∎

According to Theorem 2, we know that the lower bound of the objective function
value in the minimization problem (3.5) is $-\lambda NM$. Remarkably, the
objective (3.5) can serve as an add-on module, and can well be integrated into
other bipartite graph learning models so as to provide the capability of one-
step normalized bipartite graph partitioning.

##  4 Optimization and Theoretical Analysis

In this section, we design an alternating optimization algorithm to minimize
the objective function (3.5) in Section 4.1, and analyze its computational
complexity in Sections 4.2.

###  4.1 Optimization of Problem

####  4.1.1 Update Y

With the other variables fixed, the subproblem that only relates to Y can be
written as

$\displaystyle\max_{\textbf{Y}}~{}$ $\displaystyle
Tr((\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}\textbf{Y}^{\top}\textbf{B}\textbf{H})$
$\displaystyle s.t.~{}$ $\displaystyle\textbf{Y}\in\\{0,1\\}^{N\times
K},\textbf{Y}\textbf{1}=\textbf{1}.$ (22)

Since $\textbf{Y}\in\\{0,1\\}^{N\times K}$ and
$\textbf{Y}\textbf{1}=\textbf{1}$, we know that
$(\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}$ is a diagonal matrix111When
$\textbf{y}_{:j}=\textbf{0}$, the $j$-th diagonal entry of the diagonal matrix
$\textbf{Y}^{\top}\textbf{Y}$ is equal to $0$. The equation
$\textbf{y}_{:j}=\textbf{0}$ indicates no sample belongs to the $j$-th
cluster, which, however, is not desired and would cause the division-by-zero
error in calculating $(\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}$. To avoid
this situation, we can use
$(\textbf{Y}^{\top}\textbf{Y}+\epsilon\textbf{I})^{-\frac{1}{2}}$ instead of
$(\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}$, where $\epsilon>0$ is a very
small constant. It is obvious that
$(\textbf{Y}^{\top}\textbf{Y}+\epsilon\textbf{I})^{-\frac{1}{2}}\rightarrow(\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}$
when $\epsilon\rightarrow 0$.. Let $\textbf{Q}=\textbf{B}\textbf{H}$, the
subproblem (4.1.1) can be transformed as

$\displaystyle\max_{\textbf{Y}}~{}$ $\displaystyle
Tr((\textbf{Y}(\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}})^{\top}\textbf{Q})=\sum\limits_{j=1}^{K}\frac{\sum_{i=1}^{N}y_{ij}q_{ij}}{\sqrt{\textbf{y}_{:j}^{\top}\textbf{y}_{:j}}}$
$\displaystyle s.t.~{}$ $\displaystyle\textbf{Y}\in\\{0,1\\}^{N\times
K},\textbf{Y}\textbf{1}=\textbf{1}.$ (23)

According to [40], since $\sqrt{\textbf{y}_{:j}^{\top}\textbf{y}_{:j}}$
involves every row of Y, we can optimize Y row by row.

For updating the $i$-th row vector $\textbf{y}_{i:}$ in Y, we can explore the
increase of the objective function values in objective (4.1.1), when
$\textbf{y}_{i:}$ changes from $\textbf{y}_{i:}=\textbf{0}$ to $y_{ij}=1$.
Whether the initial value of $y_{ij}$ is $0$ or $1$, the increment can be
unified into the following form as

$\displaystyle\Delta_{ij}=\frac{\sum_{s=1}^{N}y_{sj}q_{sj}+q_{ij}(1-y_{ij})}{\sqrt{\textbf{y}_{:j}^{\top}\textbf{y}_{:j}+(1-y_{ij})}}-\frac{\sum_{s=1}^{N}y_{sj}q_{sj}+q_{ij}y_{ij}}{\sqrt{\textbf{y}_{:j}^{\top}\textbf{y}_{:j}-y_{ij}}}.$
(24)

Then $\textbf{y}_{i:}$ can be updated as

$\displaystyle
y_{ij}=<j=\mathop{\arg\max}\limits_{l\in\\{1,2,\cdots,K\\}}\Delta_{il}>,$ (25)

where $<\cdot>$ returns $0$ when the argument is false or $1$ otherwise.

####  4.1.2 Update H

With the other variables fixed, the subproblem that only relates to H can be
written as

$\displaystyle\max_{\textbf{H}^{\top}\textbf{H}=\textbf{I}}~{}$ $\displaystyle
Tr(\textbf{H}^{\top}\textbf{B}^{\top}\textbf{Y}(\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}).$
(26)

According to [45], we can have the optimal solution to the objective (26) as

$\displaystyle\textbf{H}=\textbf{U}\textbf{V}^{\top},$ (27)

where $\textbf{U}\in\mathbb{R}^{M\times K}$ and
$\textbf{V}\in\mathbb{R}^{K\times K}$ are obtained from the compact SVD [46]
of
$\textbf{B}^{\top}\textbf{Y}(\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}=\textbf{U}\Sigma\textbf{V}^{\top}$.

####  4.1.3 Update B

With the other variables fixed, the subproblem that only relates to B can be
written as

$\displaystyle\min_{\textbf{B}}~{}$
$\displaystyle||\textbf{X}-\textbf{A}\textbf{B}^{\top}||_{F}^{2}-\lambda
Tr((\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}\textbf{Y}^{\top}\textbf{B}\textbf{H})$
$\displaystyle s.t.~{}$
$\displaystyle\textbf{B}\textbf{1}=\textbf{1},\textbf{B}\geq 0.$ (28)

Since the optimization of each row of B in subproblem (4.1.3) is independent,
we can optimize B in a row-by-row manner.

Let
$\hat{\textbf{Q}}=\textbf{H}(\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}\textbf{Y}^{\top}$,
the optimization of the $i$-th row of B (i.e. $\textbf{b}_{i:}$) can be
formulated as follows:

$\displaystyle\min_{\textbf{b}_{i:}}~{}$
$\displaystyle||\textbf{x}_{:i}-\textbf{A}\textbf{b}_{i:}^{\top}||_{2}^{2}-\lambda\textbf{b}_{i:}\hat{\textbf{q}}_{:i}$
$\displaystyle s.t.~{}$
$\displaystyle\textbf{b}_{i:}\textbf{1}=1,\textbf{b}_{i:}\geq 0.$ (29)

Thereafter, the optimization problem (4.1.3) can be rewritten as the following
Quadratic Programming problem

$\displaystyle\min_{\textbf{b}_{i:}}~{}$
$\displaystyle\textbf{b}_{i:}\hat{\textbf{H}}\textbf{b}_{i:}^{\top}-\textbf{b}_{i:}\textbf{f}$
$\displaystyle s.t.~{}$
$\displaystyle\textbf{b}_{i:}\textbf{1}=1,\textbf{b}_{i:}\geq 0,$ (30)

where $\hat{\textbf{H}}=\textbf{A}^{\top}\textbf{A}$, and
$\textbf{f}=2\textbf{A}^{\top}\textbf{x}_{:i}+\lambda\hat{\textbf{q}}_{:i}$.
According to [17], the problem (4.1.3) can be optimized by the augmented
Lagrangian multiplier (ALM) method.

####  4.1.4 Update A

With the other variables fixed, the subproblem that only relates to A can be
written as

$\displaystyle\min_{\textbf{A}}~{}$
$\displaystyle||\textbf{X}-\textbf{A}\textbf{B}^{\top}||_{F}^{2}.$ (31)

It is obvious that the subproblem (31) is a convex optimization problem [33].
The optimal solution can be obtained by setting the derivative w.r.t. A to
zero, so we have222When $\textbf{B}^{\top}\textbf{B}$ is not invertible, we
can use the Moore-Penrose inverse $(\textbf{B}^{\top}\textbf{B})^{+}$.

$\displaystyle\textbf{A}=\textbf{X}\textbf{B}(\textbf{B}^{\top}\textbf{B})^{-1}.$
(32)

For clarity, the overall process of our OBCut approach is described in
Algorithm 1.

Algorithm 1 One-step bipartite graph cut (OBCut)

0: The normalized data matrix X, the cluster numbers $k$, the number of
anchors $M\geq k$, and parameter $\lambda>0$.

0: Use $k$-means to initialize A and Y. Initialize B by solving problem (3.2)
and $K$-nearest-neighbor ($K$-NN) bipartite graph ($K=5$). Initialize H by Eq.
(27).

1: repeat

2: Update Y by Eq. (25).

3: Update H by Eq. (27).

4: Update B by solving problem (4.1.3).

5: Update A by Eq. (32).

6: until Convergence or maximum iteration reached

6: The clustering results Y.

###  4.2 Computational Complexity Analysis

In this section, we analyze the computational complexity of our OBCut
approach. First, the initialization of the anchor set by $k$-means takes
$O(NMdt_{1})$ time, where $t_{1}$ is the number of iterations. The
initialization of the bipartite graph takes $O(NMK)$ time [13], where $K$ is
the number of nearest neighbors. In each iteration, it takes $O(Nk)$ time to
update Y. When updating H, it takes $O(MNk)$ time to calculate
$\textbf{B}^{\top}\textbf{Y}(\textbf{Y}^{\top}\textbf{Y})^{-\frac{1}{2}}$, and
$O(Mk^{2})$ time to perform the SVD and update H. Thus, the total
computational complexity of updating H is $O(Mk^{2}+MNk)$. When solving the
problem (4.1.3), it takes $O(NMk)$ time to calculate $\hat{\textbf{Q}}$. It
costs $O(NM^{2}d)$ time to update B, so the total time complexity of updating
B is $O(NMk+NM^{2}d)$. For updating A, it costs $O(dNM+dM^{2}+NM^{2}+M^{3})$
time in each iteration.

Therefore, the overall computational complexity of OBCut is
$O(NMK+NMdt_{1}+t_{2}(NMk+NM^{2}d+Mk^{2}+M^{3}))$, where $t_{2}$ is the number
of iterations. With $K$, $k$, $t_{1}$, $t_{2}$ being small constants and $M\ll
N$, the computational complexity of OBCut is linear to the number of samples
$N$.

##  5 Experiments

In this section, we conduct experiments to evaluate the the proposed OBCut
approach against several state-of-the-art subspace/spectral clustering
approaches on multiple real-world datasets. All experiments are conducted on a
computer with an Intel i9-12900KF CPU and 16GB of RAM.

###  5.1 Datasets and Evaluation Metrics

In the experiments, we evaluate the proposed method and the baseline methods
on eight real-world datasets, namely, Leeds [47], MPEG-7 [48], Yale, News
Group-20 (NG-20) [49], Abalone [50], Letter Recognition (LR) [51], Youtube
Faces-50 (YTF-50) [52], and Youtube Faces-100 (YTF-100) [52], whose data sizes
range from 832 to 195,537. The details of these benchmark datasets are given
in Table II.

To quantitatively compare the clustering results by different methods, we
adopt three well-known evaluation metrics, i.e., the normalized mutual
information (NMI) [52], the accuracy (ACC) [53], and the purity (PUR) [54].
For these three metrics, larger values indicate better clustering results.

TABLE II: Description of the benchmark datasets Dataset |  #Sample |  Dimension |  #Class
---|---|---|---
Leeds |  832 |  30,000 |  10
MPEG-7 |  1,400 |  6,000 |  70
Yale |  1,755 |  1,200 |  3
NG-20 |  3,970 |  8,014 |  4
Abalone |  4,177 |  7 |  28
LR |  20,000 |  16 |  26
YTF-50 |  126,054 |  512 |  50
YTF-100 |  195,537 |  512 |  100

###  5.2 Baseline Methods and Experimental Settings

In our experiments, we compare OBCut against nine spectral clustering and
subspace clustering methods, which are listed below.

  * •

SSC [7]: Sparse subspace clustering.

  * •

ESCG [23]: Efficient spectral clustering on graphs.

  * •

SSC-OMP [11]: Sparse subspace clustering by orthogonal matching pursuit.

  * •

LSC [13]: Landmark-based spectral clustering.

  * •

FastESC [24]: Fast explicit spectral clustering.

  * •

EulerSC [25]: Euler spectral clustering.

  * •

U-SPEC [14]: Ultra-scalable spectral clustering.

  * •

RKSC [26]: Refined $K$-nearest neighbor graph for spectral clustering.

  * •

DCDP-ASC [27]: Approximate spectral clustering based on dense cores and
density peaks.

Given a dataset, we perform each test method 20 times and report its average
scores (w.r.t. NMI, ACC, and PUR). For our OBCut method, the number of anchors
$M=100$ is used for all the datasets, and its trade-off parameter is tuned in
the range of $[10^{-5},10^{-4},\cdots,10^{5}]$. Similarly, the hyper-
parameters in the baseline methods are also tuned in the range of
$[10^{-5},10^{-4},\cdots,10^{5}]$, unless some specific tuning range is given
in their corresponding papers.

TABLE III: Average NMI(%) over 20 runs by different clustering methods. The
best two scores in each row are highlighted in bold, while the best one in
[bold and brackets].

Datasets |  SSC |  ESCG |  SSC-OMP |  LSC |  FastESC |  EulerSC |  U-SPEC |  RKSC |  DCDP-ASC |  OBCut
---|---|---|---|---|---|---|---|---|---|---
Leeds |  N/A |  13.05±1.01 |  7.45±0.23 |  11.70±1.53 |  9.99±1.48 |  6.71±0.71 |  12.71±0.60 |  12.59±0.88 |  1.28±0.00 |  [27.71±0.00]
MPEG-7 |  70.39±0.81 |  61.11±1.52 |  [73.30±0.60] |  60.67±1.11 |  47.64±1.45 |  60.56±0.70 |  63.85±1.13 |  58.38±2.07 |  6.85±0.00 |  71.96±0.00
Yale |  [100.00±0.00] |  [100.00±0.00] |  [100.00±0.00] |  80.25±15.42 |  97.94±4.08 |  78.90±0.00 |  64.25±15.41 |  72.89±0.00 |  [100.00±0.00] |  [100.00±0.00]
NG-20 |  0.42±0.00 |  0.31±0.11 |  9.96±5.43 |  1.47±1.13 |  0.09±0.02 |  0.08±0.04 |  0.16±0.17 |  0.63±0.00 |  0.45±0.00 |  [18.83±0.00]
Abalone |  13.09±0.11 |  16.59±0.42 |  6.86±0.22 |  15.13±0.25 |  16.64±2.21 |  7.26±0.32 |  15.38±0.26 |  0.65±0.00 |  16.80±0.00 |  [18.07±0.00]
LR |  N/A |  31.24±1.30 |  2.51±0.13 |  33.06±1.31 |  34.72±5.93 |  24.71±0.86 |  34.86±0.71 |  7.92±0.05 |  22.39±0.00 |  [37.43±0.00]
YTF-50 |  N/A |  N/A |  4.28±0.13 |  67.13±1.76 |  71.32±6.38 |  17.25±1.85 |  74.92±0.98 |  69.28±0.00 |  51.44±0.00 |  [82.60±0.00]
YTF-100 |  N/A |  N/A |  3.89±0.22 |  58.86±0.90 |  68.17±0.74 |  66.59±0.44 |  66.13±0.75 |  53.06±0.00 |  7.77±0.00 |  [81.53±0.00]
Avg.score |  - |  - |  26.03 |  41.03 |  43.31 |  32.76 |  41.53 |  34.42 |  25.87 |  [54.77]
Avg.rank |  6.88 |  5.25 |  5.63 |  5.13 |  5.13 |  7.13 |  4.75 |  6.63 |  5.88 |  [1.13]

  * 1

Note that N/A indicates the out-of-memory error.

TABLE IV: Average ACC(%) over 20 runs by different clustering methods. The
best two scores in each row are highlighted in bold, while the best one in
[bold and brackets].

Datasets |  SSC |  ESCG |  SSC-OMP |  LSC |  FastESC |  EulerSC |  U-SPEC |  RKSC |  DCDP-ASC |  OBCut
---|---|---|---|---|---|---|---|---|---|---
Leeds |  N/A |  23.73±0.85 |  17.92±0.43 |  22.82±1.03 |  21.53±1.76 |  19.32±0.96 |  22.99±1.05 |  23.97±0.95 |  12.74±0.00 |  [27.16±0.00]
MPEG-7 |  50.77±1.16 |  42.62±1.41 |  [55.00±1.07] |  39.04±1.69 |  32.29±2.08 |  42.55±1.12 |  44.50±1.17 |  40.40±2.64 |  4.43±0.00 |  54.36±0.00
Yale |  [100.00±0.00] |  [100.00±0.00] |  [100.00±0.00] |  86.59±14.15 |  99.47±1.36 |  92.93±0.00 |  59.07±17.64 |  85.13±0.00 |  [100.00±0.00] |  [100.00±0.00]
NG-20 |  25.29±0.00 |  27.52±0.34 |  33.41±4.15 |  28.02±2.16 |  25.13±0.03 |  26.31±0.43 |  25.25±0.25 |  25.57±0.00 |  28.44±0.00 |  [40.23±0.00]
Abalone |  12.26±0.15 |  15.91±1.14 |  13.72±0.47 |  13.18±0.42 |  21.42±3.09 |  13.13±0.53 |  13.79±0.65 |  16.57±0.00 |  19.56±0.00 |  [23.22±0.00]
LR |  N/A |  24.24±1.13 |  5.80±0.09 |  25.86±1.83 |  26.66±4.13 |  22.65±1.03 |  [26.86±1.29] |  9.68±0.01 |  18.34±0.00 |  26.51±0.00
YTF-50 |  N/A |  N/A |  6.14±0.08 |  54.39±3.31 |  59.09±5.88 |  22.85±1.74 |  65.62±2.00 |  62.85±0.00 |  41.04±0.00 |  [68.07±0.00]
YTF-100 |  N/A |  N/A |  4.30±0.04 |  39.53±1.58 |  53.63±1.65 |  56.33±1.23 |  49.49±1.39 |  45.43±0.00 |  8.55±0.00 |  [67.74±0.00]
Avg.score |  - |  - |  29.54 |  38.68 |  42.40 |  37.01 |  38.45 |  38.70 |  29.14 |  [50.91]
Avg.rank |  7.50 |  5.25 |  5.50 |  6.00 |  5.25 |  6.25 |  5.00 |  5.63 |  5.75 |  [1.38]

  * 1

Note that N/A indicates the out-of-memory error.

TABLE V: Average PUR(%) over 20 runs by different clustering methods. The best
two scores in each row are highlighted in bold, while the best one in [bold
and brackets].

Datasets |  SSC |  ESCG |  SSC-OMP |  LSC |  FastESC |  EulerSC |  U-SPEC |  RKSC |  DCDP-ASC |  OBCut
---|---|---|---|---|---|---|---|---|---|---
Leeds |  N/A |  27.30±0.98 |  20.84±0.46 |  26.02±1.32 |  24.07±2.07 |  20.90±0.87 |  26.47±0.78 |  26.95±0.83 |  13.10±0.00 |  [29.09±0.00]
MPEG-7 |  57.01±0.90 |  46.47±1.42 |  58.68±0.97 |  41.93±1.50 |  34.73±1.88 |  43.79±1.16 |  47.72±1.28 |  46.38±2.37 |  7.93±0.00 |  [59.14±0.00]
Yale |  [100.00±0.00] |  [100.00±0.00] |  [100.00±0.00] |  88.07±10.62 |  99.47±1.36 |  92.93±0.00 |  71.67±12.21 |  85.13±0.00 |  [100.00±0.00] |  [100.00±0.00]
NG-20 |  25.47±0.00 |  27.57±0.40 |  36.57±5.57 |  28.24±2.19 |  25.16±0.02 |  26.46±0.40 |  25.29±0.27 |  25.74±0.00 |  28.54±0.00 |  [41.74±0.00]
Abalone |  24.31±0.25 |  27.75±0.32 |  19.97±0.26 |  27.71±0.36 |  25.78±1.56 |  19.99±0.35 |  [27.77±0.28] |  17.00±0.00 |  26.67±0.00 |  26.12±0.00
LR |  N/A |  27.24±1.06 |  6.52±0.10 |  27.75±1.81 |  29.03±4.40 |  24.09±0.80 |  28.74±1.19 |  11.01±0.05 |  18.91±0.00 |  [30.18±0.00]
YTF-50 |  N/A |  N/A |  7.32±0.06 |  59.97±2.69 |  64.34±5.90 |  24.34±1.71 |  68.73±1.67 |  67.74±0.00 |  42.58±0.00 |  [76.82±0.00]
YTF-100 |  N/A |  N/A |  5.27±0.05 |  45.34±1.46 |  58.97±1.45 |  62.34±1.21 |  54.21±1.28 |  51.41±0.00 |  9.19±0.00 |  [73.88±0.00]
Avg.score |  - |  - |  31.90 |  43.13 |  45.19 |  39.36 |  43.83 |  41.42 |  30.87 |  [54.62]
Avg.rank |  7.13 |  4.75 |  5.88 |  5.38 |  5.75 |  6.25 |  4.63 |  6.38 |  5.88 |  [1.50]

  * 1

Note that N/A indicates the out-of-memory error.

###  5.3 Comparison Results and Analysis

In this section, we report and analyze the comparison results of OBCut and the
nine baseline subspace/spectral clustering methods on the eight benchmark
datasets. The clustering scores w.r.t. NMI, ACC, and PUR are given in Tables
III, IV, and V, respectively.

As shown in Table III, OBCut achieves the best NMI scores on seven out of the
eight datasets. Although SSC-OMP outperforms OBCut on the MPEG-7 dataset
w.r.t. NMI, yet on all the other seven datasets OBCut yields better or
significantly better clustering performance than SSC-OMP. In comparison with
the other bipartite graph based methods (namely, LSC and U-SPEC), whose
anchors are fixed after initialization, our OBCut method can automatically
learn a set of anchors during the optimization process and exhibits better NMI
scores than LSC and U-SPEC on all the eight datasets. The influence of the
joint learning of the anchors and the bipartite graph in OBCut will further be
evaluated in Section 5.5.

As shown in Tables IV and V, in terms of ACC and PUR, OBCut is also able to
produce the best or almost the best clustering performance on most of the
benchmark datasets. Besides the comparison of the clustering scores on each
dataset, we further provide the average ranks and average scores (across all
datasets) by different clustering methods at the bottoms of Tables III, IV,
and V. In terms of the average score, our OBCut method obtains average scores
(across all datasets) of 54.77, 50.91, and 54.62, w.r.t. NMI(%), ACC(%), and
PUR(%), respectively, while the second best method only achieves average
scores of 43.31, 42.40, and 45.19, respectively. In terms of the average rank,
OBCut obtains average ranks of 1.13, 1.38, and 1.50, w.r.t. NMI(%), ACC(%),
and PUR(%), respectively, which substantially outperforms the second best
method whose average ranks are 4.75, 5.00, and 4.63, respectively. To
summarize, the comparison results in Tables III, IV, and V have confirmed the
advantageous clustering performance of the proposed OBCut method over the
state-of-the-art subspace/spectral clustering methods.

###  5.4 Parameter Analysis

In this section, we test the influence of the trade-off parameter $\lambda$
and the number of anchors $M$ in OBCut on four benchmark datasets.

TABLE VI: The clustering performance of OBCut with varying values of parameters $\lambda$ and $M$ on the benchmark datasets. Dataset |  MPEG-7 |  Yale |  Abalone |  LR
---|---|---|---|---
NMI(%) |  |  |  |
ACC(%) |  |  |  |
PUR(%) |  |  |  |

Specifically, we illustrate the clustering performance of OBCut (w.r.t. NMI,
ACC, and PUR) in Table VI with varying values of $\lambda$ and $M$. In terms
of the trade-off parameter $\lambda$, moderate or relatively small values of
$\lambda$ are usually beneficial to the clustering performance, which suggests
the balance between the adaptive bipartite graph learning term and the
bipartite graph partitioning term in OBCut. In terms of the number of anchors
$M$, our OBCut method yields quite consistent clustering performance with
varying number of anchors. In practice, the tuning of the number of anchors is
not a necessary issue. In this work, we use $M=100$ on all the benchmark
datasets.

###  5.5 Influence of Adaptive Learning of Anchors and Bipartite Graph

In the proposed OBCut method, the adaptive anchor learning and the bipartite
graph learning are simultaneously enforced. In this section, we test the
influence of the adaptive learning of the anchors and the bipartite graph.

Specifically, three versions (or variants) of our OBCut method are compared.
First, the proposed OBCut method with learnable anchors and learnable
bipartite graph is denoted as OBCut(LA+LG). Second, the variant using fixed
anchor set and learnable bipartite graph is denoted as OBCut(FA+LG). Third,
the variant using fixed anchor set and fixed bipartite graph is denoted as
OBCut(FA+FG). As shown in Table VII, when comparing the performances of
OBCut(LA+LG) and OBCut(FA+LG), it can be observed that the incorporation of
adaptive anchor learning generally leads to more robust clustering performance
than using fixed anchors. When comparing the performances of OBCut(LA+LG) and
OBCut(FA+FG), it can be observed that the joint learning of the anchor set and
the bipartite graph can significantly benefit the clustering performance.

TABLE VII: The clustering performance of OBCut with or without the adaptive learning of the anchors and the bipartite graph (FA: Fixed Anchors; FG: Fixed Bipartite Graph; LA: Learnable Anchors; LG: Learnable Bipartite Graph). Dataset |  MPEG-7 |  Yale |  Abalone |  LR
---|---|---|---|---
NMI(%) |  |  |  |
ACC(%) |  |  |  |
PUR(%) |  |  |  |
|

###  5.6 Influence of the Unified Formulation

In the objective function (3.5) of OBCut, the adaptive anchor and bipartite
graph learning is enforced via the first subspace learning term, while the
normalized bipartite graph partitioning term is enabled via the second term.
In this section, we test the influence of the joint modeling of bipartite
graph learning and bipartite graph partitioning in OBCut. Specifically, by
treating the bipartite graph learning and the bipartite graph partitioning as
two separate steps, we can have the variant called OBCut(two-step
formulation). As shown in Table VIII, especially on the Yale and Abalone
datasets, the proposed method with the unified formulation outperforms the
two-step variant w.r.t. NMI and ACC by a significant margin. From the
experimental results on the four test datasets, it can be observed that the
unified formulation of OBCut is able to yield overall more robust clustering
performance than the two-step variant.

TABLE VIII: The clustering performance of OBCut with unified (one-step) formulation against two-step formulation. Dataset |  MPEG-7 |  Yale |  Abalone |  LR
---|---|---|---|---
NMI(%) |  |  |  |
ACC(%) |  |  |  |
PUR(%) |  |  |  |
|

(a) MPEG-7 (b) Yale (c) Abalone (d) LR

Figure 1: Convergence of the objective function value of OBCut with increasing
iterations.

###  5.7 Convergence Analysis

In this section, we conduct the convergence analysis on the four benchmark
datasets. Figure 1 shows the objective function values of OBCut varying with
different iterations. As can be seen in this figure, the objective function
values monotonically decrease and rapidly converge as the number of iterations
grows, which shows the good convergence property of our proposed OBCut method.

###  5.8 Execution Time

In this section, we evaluate the time efficiency of different clustering
methods. As the YTF-100 dataset consists of 195,537 data samples, we test the
execution times of different methods with different subsets of YTF-100, whose
sizes go from 10,000 to the full size of 195,537. As shown in Fig. 2, SSC and
ESCG are not computationally feasible for the full dataset of YTF-100 due to
the out-of-memory error. For the other methods, OBCut is faster than DCDP-ASC,
RKSC and EulerSC, and slower than U-SPEC, FastESC, and LSC, probably due to
the fact that U-SPEC and LSC utilize the predefined bipartite graph but lack
the bipartite graph learning process.

To conclude the experimental analysis, the proposed OBCut method is able to
achieve significantly better clustering performance than the baseline methods
(as shown in Tables III, IV, and V) while maintaining competitive efficiency
for very large-scale datasets (as shown in Fig. 2).

(a) Original Scale

(b) Logarithmic Scale

Figure 2: Time costs of different clustering methods on the YTF-100 dataset
with the data size varying from $10,000$ to $195,537$.

##  6 Conclusion

In this paper, we propose a new scalable subspace clustering approach based on
one-step bipartite graph cut (OBCut). In particular, we first characterize a
one-step normalized bipartite graph cut criterion, and theoretically prove its
equivalence to a trace maximization problem. Based on the new bipartite graph
cut criterion, by simultaneously modeling adaptive anchor learning, bipartite
graph learning (via subspace learning), and normalized bipartite graph
partitioning in a joint learning framework, we can directly achieve a discrete
clustering solution in a one-step formulation. An alternating optimization
algorithm is designed to solve this joint learning problem, whose time
complexity is linear to the sample size. Extensive experiments on eight real-
world datasets have demonstrated the superiority of our OBCut approach over
the state-of-the-art subspace/spectral clustering approaches.

## Acknowledgments

This project was supported by the NSFC (61976097, 62276277 & U22A2095), and
the Natural Science Foundation of Guangdong Province (2021A1515012203).

## References

  * [1] R. Vidal, “Subspace clustering,” _IEEE Signal Processing Magazine_ , vol. 28, no. 2, pp. 52–68, 2011.
  * [2] C. Tang, X. Zhu, X. Liu, M. Li, P. Wang, C. Zhang, and L. Wang, “Learning a joint affinity graph for multiview subspace clustering,” _IEEE Transactions on Multimedia_ , vol. 21, no. 7, pp. 1724–1736, 2019.
  * [3] Z. Kang, Z. Lin, X. Zhu, and W. Xu, “Structured graph learning for scalable subspace clustering: From single view to multiview,” _IEEE Transactions on Cybernetics_ , vol. 52, no. 9, pp. 8976–8986, 2022.
  * [4] S. Wang, X. Liu, X. Zhu, P. Zhang, Y. Zhang, F. Gao, and E. Zhu, “Fast parameter-free multi-view subspace clustering with consensus anchor guidance,” _IEEE Transactions on Image Processing_ , vol. 31, pp. 556–568, 2021.
  * [5] C. Fettal, L. Labiod, and M. Nadif, “Scalable attributed-graph subspace clustering,” in _Proc. of AAAI Conference on Artificial Intelligence_ , vol. 37, 2023.
  * [6] Y. Xu, S. Chen, J. Li, C. Xu, and J. Yang, “Fast subspace clustering by learning projective block diagonal representation,” _Pattern Recognition_ , vol. 135, p. 109152, 2023.
  * [7] E. Elhamifar and R. Vidal, “Sparse subspace clustering: Algorithm, theory, and applications,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 35, no. 11, pp. 2765–2781, 2013.
  * [8] G. Liu, Z. Lin, S. Yan, J. Sun, Y. Yu, and Y. Ma, “Robust recovery of subspace structures by low-rank representation,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 35, no. 1, pp. 171–184, 2013.
  * [9] C.-Y. Lu, H. Min, Z.-Q. Zhao, L. Zhu, D.-S. Huang, and S. Yan, “Robust and efficient subspace segmentation via least squares regression,” in _Proc. of European Conference on Computer Vision (ECCV)_ , 2012, pp. 347–360.
  * [10] C.-G. Li, C. You, and R. Vidal, “Structured sparse subspace clustering: A joint affinity learning and subspace clustering framework,” _IEEE Transactions on Image Processing_ , vol. 26, no. 6, pp. 2988–3001, 2017.
  * [11] C. You, D. Robinson, and R. Vidal, “Scalable sparse subspace clustering by orthogonal matching pursuit,” in _Proc. of IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2016, pp. 3918–3927.
  * [12] W.-Y. Chen, Y. Song, H. Bai, C.-J. Lin, and E. Y. Chang, “Parallel spectral clustering in distributed systems,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 33, no. 3, pp. 568–586, 2010.
  * [13] D. Cai and X. Chen, “Large scale spectral clustering via landmark-based sparse representation,” _IEEE Transactions on Cybernetics_ , vol. 45, no. 8, pp. 1669–1680, 2014.
  * [14] D. Huang, C.-D. Wang, J.-S. Wu, J.-H. Lai, and C.-K. Kwoh, “Ultra-scalable spectral clustering and ensemble clustering,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 32, no. 6, pp. 1212–1226, 2020.
  * [15] J. Wang, Z. Ma, F. Nie, and X. Li, “Fast self-supervised clustering with anchor graph,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 33, no. 9, pp. 4199–4212, 2022.
  * [16] Z. Li, X.-M. Wu, and S.-F. Chang, “Segmentation using superpixels: A bipartite graph partitioning approach,” in _Proc. of IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_. IEEE, 2012, pp. 789–796.
  * [17] X. Li, H. Zhang, R. Wang, and F. Nie, “Multiview clustering: A scalable and parameter-free bipartite graph fusion method,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 44, no. 1, pp. 330–344, 2020\.
  * [18] F. Nie, X. Wang, M. Jordan, and H. Huang, “The constrained laplacian rank algorithm for graph-based clustering,” in _Proc. of AAAI Conference on Artificial Intelligence_ , vol. 30, no. 1, 2016.
  * [19] Z. Li, F. Nie, X. Chang, L. Nie, H. Zhang, and Y. Yang, “Rank-constrained spectral clustering with flexible embedding,” _IEEE Transactions on Neural Networks and Learning Systems_ , vol. 29, no. 12, pp. 6073–6082, 2018.
  * [20] G. Zhong and C.-M. Pun, “Nonnegative self-representation with a fixed rank constraint for subspace clustering,” _Information Sciences_ , vol. 518, pp. 127–141, 2020.
  * [21] F. Nie, X. Wang, C. Deng, and H. Huang, “Learning a structured optimal bipartite graph for co-clustering,” _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 30, 2017.
  * [22] J. Shi and J. Malik, “Normalized cuts and image segmentation,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 22, no. 8, pp. 888–905, 2000.
  * [23] J. Liu, C. Wang, M. Danilevsky, and J. Han, “Large-scale spectral clustering on graphs,” in _Proc. International Joint Conference on Artificial Intelligence (IJCAI)_ , 2013.
  * [24] L. He, N. Ray, Y. Guan, and H. Zhang, “Fast large-scale spectral clustering via explicit feature mapping,” _IEEE Transactions on Cybernetics_ , vol. 49, no. 3, pp. 1058–1071, 2018.
  * [25] J.-S. Wu, W.-S. Zheng, J.-H. Lai, and C. Y. Suen, “Euler clustering on large-scale dataset,” _IEEE Transactions on Big Data_ , vol. 4, no. 4, pp. 502–515, 2017.
  * [26] M. Alshammari, J. Stavrakakis, and M. Takatsuka, “Refining a k-nearest neighbor graph for a computationally efficient spectral clustering,” _Pattern Recognition_ , vol. 114, p. 107869, 2021.
  * [27] D. Cheng, J. Huang, S. Zhang, X. Zhang, and X. Luo, “A novel approximate spectral clustering algorithm with dense cores and density peaks,” _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , vol. 52, no. 4, pp. 2348–2360, 2021.
  * [28] F. Nie, W. Chang, Z. Hu, and X. Li, “Robust subspace clustering with low-rank structure constraint,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 34, no. 3, pp. 1404–1415, 2022.
  * [29] X. Peng, Z. Yu, Z. Yi, and H. Tang, “Constructing the L2-graph for robust subspace learning and subspace clustering,” _IEEE Transactions on Cybernetics_ , vol. 47, no. 4, pp. 1053–1066, 2017.
  * [30] C. Lu, J. Feng, Z. Lin, T. Mei, and S. Yan, “Subspace clustering by block diagonal representation,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 41, no. 2, pp. 487–501, 2019.
  * [31] W. Chang, F. Nie, R. Wang, and X. Li, “Robust subspace clustering by learning an optimal structured bipartite graph via low-rank representation,” in _Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2019, pp. 3692–3696.
  * [32] J. Fan, “Large-scale subspace clustering via k-factorization,” in _Proc. of ACM SIGKDD Conference on Knowledge Discovery & Data Mining_, 2021, p. 342–352.
  * [33] F. Nie, W. Chang, R. Wang, and X. Li, “Learning an optimal bipartite graph for subspace clustering via constrained laplacian rank,” _IEEE Transactions on Cybernetics_ , vol. 53, no. 2, pp. 1235–1247, 2023.
  * [34] Y. Yang, F. Shen, Z. Huang, H. T. Shen, and X. Li, “Discrete nonnegative spectral clustering,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 29, no. 9, pp. 1834–1845, 2017.
  * [35] J. Lu, Y. Lu, R. Wang, F. Nie, and X. Li, “Multiple kernel k-means clustering with simultaneous spectral rotation,” in _Proc. of IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , 2022, pp. 4143–4147.
  * [36] Y. Yang, F. Shen, Z. Huang, H. T. Shen, and X. Li, “Discrete nonnegative spectral clustering,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 29, no. 9, pp. 1834–1845, 2017.
  * [37] Y. Pang, J. Xie, F. Nie, and X. Li, “Spectral clustering by joint spectral embedding and spectral rotation,” _IEEE Transactions on Cybernetics_ , vol. 50, no. 1, pp. 247–258, 2018.
  * [38] X. Chen, W. Hong, F. Nie, D. He, M. Yang, and J. Z. Huang, “Spectral clustering of large-scale data by directly solving normalized cut,” in _Proc. of ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, 2018, pp. 1206–1215.
  * [39] S. Pei, F. Nie, R. Wang, and X. Li, “Efficient clustering based on a unified view of $k$-means and ratio-cut,” _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 33, pp. 14 855–14 866, 2020.
  * [40] C. Tang, Z. Li, J. Wang, X. Liu, W. Zhang, and E. Zhu, “Unified one-step multi-view spectral clustering,” _IEEE Transactions on Knowledge and Data Engineering_ , 2022.
  * [41] Z. Kang, W. Zhou, Z. Zhao, J. Shao, M. Han, and Z. Xu, “Large-scale multi-view subspace clustering in linear time,” in _Proc. of AAAI Conference on Artificial Intelligence_ , vol. 34, no. 04, 2020, pp. 4412–4419.
  * [42] W. Xia, Q. Gao, Q. Wang, X. Gao, C. Ding, and D. Tao, “Tensorized bipartite graph learning for multi-view clustering,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 45, no. 4, pp. 5187–5202, 2023\.
  * [43] U. Von Luxburg, “A tutorial on spectral clustering,” _Statistics and Computing_ , vol. 17, no. 4, pp. 395–416, 2007.
  * [44] H. Zha, X. He, C. Ding, H. Simon, and M. Gu, “Bipartite graph partitioning and data clustering,” in _Proc. of International Conference on Information and Knowledge Management (CIKM)_ , 2001, pp. 25–32.
  * [45] J. Huang, F. Nie, and H. Huang, “Spectral rotation versus k-means in spectral clustering,” in _Proc. of AAAI Conference on Artificial Intelligence_ , vol. 27, no. 1, 2013, pp. 431–437.
  * [46] F. Nie, R. Zhang, and X. Li, “A generalized power iteration method for solving quadratic problem on the stiefel manifold,” _Science China Information Sciences_ , vol. 60, no. 11, pp. 1–10, 2017.
  * [47] J. Wang, K. Markert, M. Everingham _et al._ , “Learning models for object recognition from natural language descriptions,” in _Proc. of British Machine Vision Conference (BMVC)_ , 2009, pp. 2.1–2.11.
  * [48] L. Latecki, R. Lakamper, and T. Eckhardt, “Shape descriptors for non-rigid shapes with a single closed contour,” in _Proc. IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , vol. 1, 2000, pp. 424–429 vol.1.
  * [49] B. Long, Z. M. Zhang, and P. S. Yu, “Co-clustering by block value decomposition,” in _Proc. of ACM SIGKDD International Conference on Knowledge Discovery in Data Mining_ , ser. KDD ’05, 2005, p. 635–640.
  * [50] S.-S. Yu, S.-W. Chu, C.-M. Wang, Y.-K. Chan, and T.-C. Chang, “Two improved k-means algorithms,” _Applied Soft Computing_ , vol. 68, pp. 747–755, 2018\.
  * [51] D. Huang, C.-D. Wang, H. Peng, J. Lai, and C.-K. Kwoh, “Enhanced ensemble clustering via fast propagation of cluster-wise similarities,” _IEEE Transactions on Systems, Man, and Cybernetics: Systems_ , vol. 51, no. 1, pp. 508–520, 2021.
  * [52] D. Huang, C.-D. Wang, and J.-H. Lai, “Fast multi-view clustering via ensembles: Towards scalability, superiority, and simplicity,” _IEEE Transactions on Knowledge and Data Engineering_ , 2023.
  * [53] S.-G. Fang, D. Huang, X.-S. Cai, C.-D. Wang, C. He, and Y. Tang, “Efficient multi-view clustering via unified and discrete bipartite graph learning,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2023.
  * [54] Y. Liang, D. Huang, C.-D. Wang, and P. S. Yu, “Multi-view graph learning by joint modeling of consistency and inconsistency,” _IEEE Transactions on Neural Networks and Learning Systems_ , 2022.

|  Si-Guo Fang received the B.S. degree in information and computing sciences
from the China Jiliang University, Hangzhou, China, in 2021. He is currently
pursuing the master degree in computer science with the College of Mathematics
and Informatics, South China Agricultural University, Guangzhou, China. His
research interests include data mining and machine learning.
---|---
|  Dong Huang received the B.S. degree in computer science in 2009 from South
China University of Technology, Guangzhou, China. He received the M.Sc. degree
in computer science in 2011 and the Ph.D. degree in computer science in 2015,
both from Sun Yat-sen University, Guangzhou, China. He joined South China
Agricultural University in 2015, where he is currently an Associate Professor
with the College of Mathematics and Informatics. From July 2017 to July 2018,
he was a visiting fellow with the School of Computer Science and Engineering,
Nanyang Technological University, Singapore. His research interests include
data mining and machine learning. He has published more than 70 papers in
international journals and conferences, such as IEEE TKDE, IEEE TNNLS, IEEE
TCYB, IEEE TSMC-S, ACM TKDD, SIGKDD, AAAI, and ICDM. He was the recipient of
the 2020 ACM Guangzhou Rising Star Award.
---|---
|  Chang-Dong Wang received the B.S. degree in applied mathematics in 2008,
the M.Sc. degree in computer science in 2010, and the Ph.D. degree in computer
science in 2013, all from Sun Yat-sen University, Guangzhou, China. He was a
visiting student at the University of Illinois at Chicago from January 2012 to
November 2012. He is currently an Associate Professor with the School of Data
and Computer Science, Sun Yat-sen University, Guangzhou, China. His current
research interests include machine learning and data mining. He has published
more than 100 scientific papers in international journals and conferences such
as IEEE TPAMI, IEEE TKDE, IEEE TNNLS, IEEE TSMC-C, ACM TKDD, Pattern
Recognition, SIGKDD, AAAI, ICDM and SDM. His ICDM 2010 paper won the Honorable
Mention for Best Research Paper Award. He was awarded 2015 Chinese Association
for Artificial Intelligence (CAAI) Outstanding Dissertation.
---|---
|  Jian-Huang Lai received the M.Sc. degree in applied mathematics in 1989 and
the Ph.D. degree in mathematics in 1999 from Sun Yat-sen University, China. He
joined Sun Yat-sen University in 1989 as an Assistant Professor, where he is
currently a Professor with the School of Data and Computer Science. His
current research interests include the areas of digital image processing,
pattern recognition, multimedia communication, wavelet and its applications.
He has published more than 200 scientific papers in the international journals
and conferences on image processing and pattern recognition, such as IEEE
TPAMI, IEEE TKDE, IEEE TNN, IEEE TIP, IEEE TSMC-B, Pattern Recognition, ICCV,
CVPR, IJCAI, ICDM and SDM. Prof. Lai serves as a Standing Member of the Image
and Graphics Association of China, and also serves as a Standing Director of
the Image and Graphics Association of Guangdong.
---|---


11institutetext: Sberbank Artificial Intelligence Laboratory, Moscow, Russia
11email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>

# RuBioRoBERTa: a pre-trained biomedical language model for Russian language
biomedical text mining

Alexander Yalunin  Alexander Nesterov  Dmitriy Umerenkov  Target Other
arthritis Target Increase in body temperature Target entailment

###### Abstract

This paper presents several BERT-based models111https://github.com/sberbank-
ai-lab/RuBioRoBERTa for Russian language biomedical text mining (RuBioBERT,
RuBioRoBERTa). The models are pre-trained on a corpus of freely available
texts in the Russian biomedical domain. With this pre-training, our models
demonstrate state-of-the-art results on RuMedBench – Russian medical language
understanding benchmark that covers a diverse set of tasks, including text
classification, question answering, natural language inference, and named
entity recognition.

###### Keywords:

Natural Language Processing Transfer Learning Russian Medical Data EHR BERT.

##  1 Motivation

The transition to electronic health records led to an overwhelming number of
medical data being stored digitally. With the increasing availability of
medical texts and the rapid progress of text processing models, biomedical
text mining is a rapidly expanding field. Different players from startups to
medical institutions build applied solutions to solve medical tasks using
biomedical texts. The vast majority of these solutions use the transformer
neural network models pre-trained on large text corpora. Such pre-training is
computationally expensive and requires the assembly of a corresponding
dataset. Thanks to the community effort, we now have access to pre-trained
models for all languages. For this work, we used transformer networks pre-
trained on Russian language texts from
SberDevices222https://github.com/sberbank-ai/model-zoo and DeepPavlov [4].

A series of models with novel BERT architecture, e.g., ClinicalBERT [1],
BlueBERT [7], successfully applied to a range of healthcare and biomedical
domain tasks. In BioBERT [5] authors showed that additional pre-training of
transformer models on biomedical domain texts leads to noticeable improvements
over a wide range of corresponding domain tasks. We do the same thing for the
Russian language: we pre-train three transformer models on a large corpus of
Russian medical texts and evaluate on the recently released medical benchmark
RuMedBench [2]. With this pre-training, our models demonstrate state-of-the-
art results. We hope that the presented models will be used as baselines for a
wide array of applied biomedical models.

##  2 Setup

###  2.1 Biomedical Corpus for pre-training

Our created biomedical texts corpus is based on the public Russian-language
scientific articles database CyberLeninka333https://cyberleninka.ru/. All
articles presented on this resource are freely distributed with the license
CC-BY. For our work, we use articles related to the categories: fundamental
medicine, clinical medicine, health sciences, biotechnology, and medical
technology. Each article we use contains a title, abstract, and publication
text. The final corpus includes 338,000 articles published from 1929 to 2021.
The total volume of the corpus consists of 1.2 billion words.

###  2.2 Downstream Tasks

This paper aims to measure language learning abilities in the medical domain.
As such, we study downstream performance on a diverse set of benchmarks,
including question answering, natural language inference, named-entity
recognition, and text classification. Precisely, we measure performance on the
RuMedBench [2] medical text classification meta-benchmark, which consists of
five downstream tasks.

In RuMedTop3 the task is to predict the three most probable ICD-10 codes
related to the deceases based only on raw patient symptoms. In RuMedSymptomRec
based on a given text premise, recommend a relevant symptom. In RuMedDaNet
given a medical context and a question, give a yes/no answer. The contexts
come from diverse fields: therapeutic medicine, pharmacology, biochemistry,
human physiology, and anatomy. In RuMedNLI given premise and hypothesis to
infer the relation as either entailment, contradiction, or neutral. The
premises are extracted from the Past Medical History section in MIMIC-III
records, and hypotheses are generated by the clinicians. Finally, in RuMedNER
the task is to classify words in drug therapy product reviews.

###  2.3 Models

We take three publicly available checkpoints of BERT [3] and RoBERTa [6] based
models, which were pre-trained on general domain corpora: RuBERT [4], ruBERT
and ruRoBERTa444https://github.com/sberbank-ai/model-zoo. The first is an
adapted multilingual version of BERT pre-trained by DeepPavlov on Russian
Wikipedia. The second and the third are the version of BERT and RoBERTa pre-
trained by SberDevices on Russian Wikipedia and Taiga corpus. We additionally
pre-train these models on our biomedical corpus, resulting in bio-versions:
RuBERT+Bio, RuBioBERT, and RuBioRoBERTa, respectively. Finally, we show the
effectiveness of our approach in biomedical text mining by fine-tuning and
evaluating them on RuMedBench.

###  2.4 Training Details

We use the HuggingFace [8] library to obtain models and training scripts. Each
model is trained with default hyper-parameters if not stated otherwise.

The BERT-based models have a vocabulary size of 120K subword units, 178
million parameters, and they were pre-trained on 30GB general text corpora.
The BERT-based models have a vocabulary size of 50K subword units, 355 million
parameters, and they were pre-trained on 250GB general text corpora.

Each model is pre-trained on the biomedical corpus for 1 epoch with batch size
64 and weight decay of 0.01. The learning rate is warmed up over the ﬁrst
20000 steps to a peak value of 5e-5, and then linearly decays. The whole pre-
training took 12 days on three NVIDIA V100 GPUs.

The hyperparameters are identical for all tasks on the fine-tuning stage: we
train for 10 epochs with a batch size of 32 and weight decay of 0.01. The
learning rate is warmed up over the ﬁrst 30% of steps to a peak value of 3e-5,
and then decays with cosine annealing.

##  3 Results

Table 1: Performance metrics (%) on the _RuMedBench_ test sets. Model | $\stackrel{{\scriptstyle Acc/Hit@3}}{{\mathrm{Top3}}}$ | $\stackrel{{\scriptstyle Acc/Hit@3}}{{\mathrm{SymptomRec}}}$ | $\stackrel{{\scriptstyle Acc{\color[rgb]{1,1,1}/}}}{{\mathrm{DaNet}}}$ | $\stackrel{{\scriptstyle Acc{\color[rgb]{1,1,1}/}}}{{\mathrm{NLI}}}$ | $\stackrel{{\scriptstyle Acc/F1}}{{\mathrm{NER}}}$ | Overall
---|---|---|---|---|---|---
Previous best | 47.45/70.44 | 34.94/52.05 | 71.48 | 77.29 |  96.47/73.15 | 67.20
RuBERT | 41.24/65.57 | 20.59/34.59 | 68.75 | 77.43 | 96.29/72.57 | 62.32
ruBERT | 44.04/69.71 | 23.69/38.09 | 64.06 | 78.06 | 96.59/74.07 | 63.04
ruRoBERTa | 45.74/72.14 | 40.92/54.37 | 74.61 | 82.42 | 97.09/77.79 | 70.21
RuBERT+Bio | 45.13/72.26 | 26.92/41.99 | 51.17 | 78.62 | 96.45/74.04 | 61.64
RuBioBERT | 43.55/68.86 | 28.94/44.55 | 53.91 | 80.31 | 96.63/75.97 | 62.69
RuBioRoBERTa | 46.72/72.87 | 44.01/58.95 | 76.17 | 82.77 | 97.19/77.81 | 71.54
Human | 25.06/48.54 | 7.23/12.53 | 93.36 | 83.26 | 96.09/76.18 | 61.89

As shown in Table 1, our best model RuBioRoBERTa outperforms the previous
state-of-the-art on all tasks and demonstrates the highest overall score. The
obvious explanation of why RuBioRoBERTa is the best model among those we
present is that it has the largest number of parameters, and it was pre-
trained longer on general corpora. Another observation is that ”bio” models
outperform their correspondent ”general” versions in most tasks. It validates
our approach in biomedical text mining and additional pre-training. Like in
previous work, our model outperforms assessor-clinicians in the first two
tasks. In addition, RuBioRoBERTa now beats human in RuMedNER, i.e., in drug
review classification. The RuMedDaNet is the most challenging one of the
proposed tasks, as it requires a deeper understanding of the relation between
the context and the hypothesis. We hope that the current lag between the human
level and the best model of more than 15% will be reduced after more advanced
and specialized Russian medical models appear.

##  4 Qualitative results

Table 2: Prediction samples from ruRoBERTa and RuBioRoBERTa on RuMedBench. Task |  Model |  Sample
---|---|---
NER |  ruRoBERTa |  So they kept us on syrups, like _bronchomax_ , and as a result, pneumonia and a hospital.
|  RuBioRoBERTa |  So they kept us on syrups, like _bronchomax_ , and as a result, pneumonia and a hospital.
Top3 |  Input, |  Pain in the wrist joints, when lifting weights, rotation.
|  ruRoBERTa |  Polyarthrosis, Seropositive rheumatoid arthritis, Other rheumatoid arthritis
|  RuBioRoBERTa |  Other arthritis, Other rheumatoid arthritis, Other arthrosis
Sym |  Input, |  Pronounced dry cough, increased since the last night, runny nose, headache, weakness, - not measured, chills.
|  ruRoBERTa |  Sore throat, Runny nose, Dry cough
|  RuBioRoBERTa |  Chills, Increase in body temperature, Yellow colored urine
NLI |  Input, |  Sentence 1: ACA in XXX with residual left-sided weakness, Sentence 2: Had a stroke.
|  ruRoBERTa |  neutral
|  RuBioRoBERTa |  entailment

We conduct a qualitative analysis of models results to explore the sources of
improvements. Table 2 gives examples of the predictions from ruRoBERTa and
RuBioRoBERTa. For a significant amount of cases, RuBioRoBERTa was able to
understand the standard medical abbreviations. In the NLI example, the model
needs to know that ACA stands for Acute Cerebrovascular Accident to answer
whether the person had a stroke correctly. Also, for several cases, the
biomedical pre-training allowed the model to more confidently recognize drug
and diseases names like _pneumonia_ in the NER example. In the Top3 task, the
symptoms listed in the input are not characteristic of any particular
rheumatic disease. It was correctly interpreted by RuBioRoBERTa, placing the
diagnosis corresponding to nonspecific arthritis _(Other arthritis)_ in the
first place. In the SymRec task, the domain-specific model also performed
better, recommending symptoms not found in the original text, which is not the
case for the non-domain-specific model.

##  5 Clinical Relevance

We believe it is crucial to develop benchmarks and models for languages other
than English. The models that we propose can directly support the Russian
research community that develops AI medicine methods. Concretely, the models
pre-trained in the medical domain that we publish can be used as a starting
checkpoint for the textual models used in medicine and healthcare. Also, our
models can serve as comparison baselines for works in multilingual/cross-
lingual fields that solve medical tasks in different languages.

##  6 Conclusion

This study introduces RuBioRoBERTa, a pre-trained biomedical language model
that demonstrates state-of-the-art results on the RuMedBench benchmark. We
conduct qualitative analysis to verify our approach in biomedical text mining.
We release the source code and the weights of RuBioRoBERTa and RuBioBERT. Our
further plan is to increase the volume and quality of the biomedical text
corpus, utilize the latest models and techniques in NLP, increase the
computational resources and support the development of the RuMedBench
benchmark.

## References

  * [1] Alsentzer, E., Murphy, J., Boag, W., Weng, W.H., Jin, D., Naumann, T., McDermott, M.: Publicly available clinical BERT embeddings. In: Proceedings of the 2nd Clinical Natural Language Processing Workshop. pp. 72–78. Association for Computational Linguistics, Minneapolis, Minnesota, USA (Jun 2019)
  * [2] Blinov, P., Reshetnikova, A., Nesterov, A., Zubkova, G., Kokh, V.: Rumedbench: A russian medical language understanding benchmark. arXiv preprint arXiv:2201.06499 (2022)
  * [3] Devlin, J., Chang, M.W., Lee, K., Toutanova, K.: Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint arXiv:1810.04805 (2018)
  * [4] Kuratov, Y., Arkhipov, M.: Adaptation of deep bidirectional multilingual transformers for russian language. arXiv preprint arXiv:1905.07213 (2019)
  * [5] Lee, J., Yoon, W., Kim, S., Kim, D., Kim, S., So, C.H., Kang, J.: Biobert: a pre-trained biomedical language representation model for biomedical text mining. Bioinformatics 36(4), 1234–1240 (2020)
  * [6] Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., Stoyanov, V.: Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv:1907.11692 (2019)
  * [7] Peng, Y., Yan, S., Lu, Z.: Transfer learning in biomedical natural language processing: an evaluation of bert and elmo on ten benchmarking datasets. arXiv preprint arXiv:1906.05474 (2019)
  * [8] Wolf, T., Chaumond, J., Debut, L., Sanh, V., Delangue, C., Moi, A., Cistac, P., Funtowicz, M., Davison, J., Shleifer, S., et al.: Transformers: State-of-the-art natural language processing. In: Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations. pp. 38–45 (2020)