[table]capposition=top capbtabboxtable[][]

# Discrete Optimal Graph Clustering

Yudong Han, Lei Zhu, Zhiyong Cheng, Jingjing Li, Xiaobai Liu This work was
supported National Natural Science Foundation of China under Grant 61802236
and 61806039, in part by the National Postdoctoral Program for Innovative
Talents under Grant BX201700045, in part by the China Postdoctoral Science
Foundation under Grant 2017M623006.Y. Han and L. Zhu are with the School of
Information Science and Engineering, Shandong Normal University, Jinan 250358,
China. (Corresponding author: Lei Zhu, E-mail: leizhu0608@gmail.com)Z. Cheng
is with the Qilu University of Technology (Shandong Academy of Sciences),
Shandong Computer Science Center (National Supercomputer Center in Jinan),
Shandong Artificial Intelligence Institute, China.J. Li is with the School of
Computer Science and Engineering, University of Electronic Science and
Technology of China, Chengdu 611731, China.X. Liu is with the Department of
Computer Science, San Diego State University, California, 92182, USA.

###### Abstract

Graph based clustering is one of the major clustering methods. Most of it work
in three separate steps: similarity graph construction, clustering label
relaxing and label discretization with k-means. Such common practice has three
disadvantages: 1) the predefined similarity graph is often fixed and may not
be optimal for the subsequent clustering. 2) the relaxing process of cluster
labels may cause significant information loss. 3) label discretization may
deviate from the real clustering result since k-means is sensitive to the
initialization of cluster centroids. To tackle these problems, in this paper,
we propose an effective discrete optimal graph clustering (DOGC) framework. A
structured similarity graph that is theoretically optimal for clustering
performance is adaptively learned with a guidance of reasonable rank
constraint. Besides, to avoid the information loss, we explicitly enforce a
discrete transformation on the intermediate continuous label, which derives a
tractable optimization problem with discrete solution. Further, to compensate
the unreliability of the learned labels and enhance the clustering accuracy,
we design an adaptive robust module that learns prediction function for the
unseen data based on the learned discrete cluster labels. Finally, an
iterative optimization strategy guaranteed with convergence is developed to
directly solve the clustering results. Extensive experiments conducted on both
real and synthetic datasets demonstrate the superiority of our proposed
methods compared with several state-of-the-art clustering approaches.

###### Index Terms:

Optimal graph, Discrete label learning, Out-of-sample, Information loss

##  I Introduction

Clustering is one of the fundamental techniques in machine learning. It has
been widely applied to various research fields, such as gene expression[1],
face analysis[2], image annotation[3], and recommendation[4, 5]. In the past
decades, many clustering approaches have been developed, such as k-means[6],
spectral clustering[7, 8],[9],[10],[11] spectral embedded clustering[12] and
normalized cut[13].

K-means identifies cluster centroids that minimize the within cluster data
distances. Due to the simpleness and efficiency, it has been extensively
applied as one of the most basic clustering methods. Nevertheless, k-means
suffers from the problem of the curse of dimensionality and its performance
highly depends on the initialized cluster centroids. As an alternative
promising clustering method, spectral clustering and its extensions learn a
low-dimensional embedding of the data samples by modelling their affinity
correlations with graph [14, 15, 16, 17, 18, 19, 20, 21]. These graph based
clustering methods,[22],[23],[24],[25], [26] generally work in three separate
steps: similarity graph construction, clustering label relaxing and label
discretization with k-means. Their performance is largely determined by the
quality of the pre-constructed similarity graph, where the similarity
relations of samples are simply calculated with a fixed distance measurement,
which cannot fully capture the inherent local structure of data samples. This
unstructured graph may lead to sub-optimal clustering results. Besides, they
rely on k-means to generate the final discrete cluster labels, which may
result in unstable clustering solution as k-means.

Recently, clustering with adaptive neighbors (CAN)[27] is proposed to
automatically learn a structured similarity graph by considering the
clustering performance. Projective clustering with adaptive neighbors
(PCAN)[27] improves its performance further by simultaneously performing
subspace discovery, similarity graph learning and clustering. With structured
graph learning, CAN and PCAN enhance the performance of graph based clustering
further. However, they simply drop the discrete constraint of cluster labels
to solve an approximate continuous solution. This strategy may lead to
significant information loss and thus reduce the quality of the constructed
graph structure. Moreover, to generate the final discrete cluster labels,
graph cut should be exploited in them on the learned similarity graph. To
obtain the cluster labels of out-of-sample data, the whole algorithm should be
run again. This requirement will bring consideration computation cost in real
practice.

In this paper, we propose an effective discrete optimal graph clustering
(DOGC) method. We develop a unified learning framework, where the optimal
graph structure is adaptively constructed, the discrete cluster labels are
directly learned, and the out-of-sample extension can be well supported. In
DOGC, a structured graph is adaptively learned from the original data with a
guidance of reasonable rank constraint for pursuing the optimal clustering
structure. Besides, to avoid the information loss in most graph based
clustering methods, a rotation matrix is learned in DOGC to rotate the
intermediate continuous labels and directly obtain the discrete ones. Based on
the discrete cluster labels, we further integrate a robust prediction module
into the DOGC to compensate the unreliability of cluster labels and learn a
prediction function for out-of-sample data clustering. To solve the formulated
discrete clustering problem, an alternate optimization strategy guaranteed
with convergence is developed to iteratively calculate the clustering results.
The key advantages of our methods are highlighted as follows:

TABLE I: Summary of the main notations. Symbols |  Explanations
---|---
$d$ |  The feature dimension of data
$c$ |  The number of clusters
$k$ |  The nearest neighbor number of data points
$n$ |  Data size
$\alpha,\beta,\gamma$ |  Penalty parameters
X |  Data matrix
$\ \textbf{I}_{z}$ |  An identity matrix of size $z\times z$
A |  The fixed similarity matrix calculated directly by Gaussian kernel function
S |  The learned similarity matrix corresponding to X
W |  The projection matrix for dimension reduction
P |  The mapping matrix from original data to discrete cluster labels
F |  The continuous cluster labels
Y |  The discrete cluster labels
Q |  The rotation matrix
$\ \ \textbf{D}_{\mathrm{S}}$ |  Degree matrix of similarity matrix S
$\ \ \textbf{L}_{\mathrm{S}}$ |  Laplacian matrix of similarity matrix S

  1. 1.

Rather than exploiting a fixed similarity matrix, a similarity graph is
adaptively learned from the raw data by considering the clustering
performance. With reasonable rank constraint, the dynamically constructed
graph is forced to be well structured and theoretically optimal for
clustering.

  2. 2.

Our model learns a proper rotation matrix to directly generate discrete
cluster labels without any relaxing information loss as many existing graph
based clustering methods.

  3. 3.

With the learned discrete cluster labels, our model can accommodate the out-
of-sample data well by designing a robust prediction module. The discrete
cluster labels of database samples can be directly obtained, and
simultaneously the clustering capability for new data can be well supported.

The rest of this paper is organized as follows. Section ii@ revisits several
representative graph based clustering methods. Section iii@ describes the
details of the proposed methods. Section iv@ introduces the experimental
setting. The experimental results are presented in Section<EMAIL_ADDRESS>Section vi@
concludes the paper.

##  II Graph Clustering Revisited

###  II-A Notations

For the data matrix
$\textbf{X}=\big{\\{}\textbf{x}_{1},\ldots,\textbf{x}_{n}\big{\\}}\in\mathbb{R}^{d\times
n}$, the $(i,j)_{th}$ entry of X and the $i_{th}$ sample of X are denoted by
$x_{ij}$ and $\textbf{x}_{i}$ respectively. The trace of X is denoted by
$Tr(\textbf{X})$. The Frobenius norm of matrix X is denoted by
$\parallel$X$\parallel_{\mathrm{F}}$. The similarity matrix corresponds to X
is denoted by S, whose $(i,j)_{th}$ entry is $s_{ij}$. An identity matrix of
size $z\times z$ is represented by $\textbf{I}_{z}$ and 1 denotes a column
vector with all elements as 1. The main notations used in this paper are
summarized in Table I.

###  II-B Spectral Clustering

Spectral clustering[7] requires Laplacian matrix
$\textbf{L}_{\mathrm{S}}\in\mathbb{R}^{n\times n}$ as an input. It is computed
as
$\textbf{L}_{\mathrm{S}}=\textbf{D}_{\mathrm{S}}-\frac{(\textbf{S}^{\top}+\textbf{S})}{2}$,
where $\textbf{D}_{\mathrm{S}}\in\mathbb{R}^{n\times n}$ is a diagonal matrix
with the $i_{th}$ diagonal element as
$\sum_{j}\frac{(s_{ij}^{\top}+s_{ij})}{2}$. Supposing there are $c$ clusters
in the dataset X, spectral clustering solves the following problem:

$\displaystyle\min_{\textbf{Y}}Tr(\textbf{Y}^{\top}\textbf{L}_{\mathrm{S}}\textbf{Y})\quad\mathrm{s.t.}\;\textbf{Y}\in\mathrm{Idx}$
(1)

where
$\textbf{Y}=[\textbf{y}_{1},\textbf{y}_{2},\ldots,\textbf{y}_{n}]^{\top}\in\mathbb{R}^{n\times
c}$ is the clustering indicator matrix and $\textbf{Y}\in\mathrm{Idx}$ means
that the clustering label vector of each sample
$\textbf{y}_{i}\in\big{\\{}0,1\big{\\}}^{c\times 1}$ contains only one element
1 and the others are 0. As the discrete constraint is imposed on Y, Eq.(1)
becomes a NP-hard problem. To tackle it, most existing methods first relax Y
to continuous clustering indicator matrix
$\textbf{F}=[\textbf{f}_{1},\textbf{f}_{2},\ldots,\textbf{f}_{n}]^{\top}\in\mathbb{R}^{n\times
c}$, and then calculate the relaxed solution as

$\displaystyle\min_{\textbf{F}}Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})\quad\mathrm{s.t.}\;\textbf{F}^{\top}\textbf{F}=\textbf{I}_{c}$
(2)

Where the orthogonal constraint $\textbf{F}^{\top}\textbf{F}=\textbf{I}_{c}$
is adopted to avoid trivial solutions. The optimal solution of F is comprised
of $c$ eigenvectors of $\textbf{L}_{\mathrm{S}}$ corresponding to the $c$
smallest eigenvalues. Once F is obtained, k-means is applied to generate the
final clustering result. For presentation convenience, we denote F and Y as
continuous labels and discrete labels respectively.

TABLE II: Main differences between the proposed methods and representative clustering methods. Methods |  Projective Subspace Learning |  Information Loss |  Optimal Graph |  Discrete Optimization |  Out-of-Sample Extension
---|---|---|---|---|---
KM |  $\times$ |  $\times$ |  $\times$ |  $\times$ |  $\times$
N-cut |  $\times$ |  $\surd$ |  $\times$ |  $\times$ |  $\times$
R-cut |  $\times$ |  $\surd$ |  $\times$ |  $\times$ |  $\times$
CLR |  $\times$ |  $\surd$ |  $\surd$ |  $\times$ |  $\times$
SEC |  $\times$ |  $\surd$ |  $\times$ |  $\times$ |  $\times$
CAN |  $\times$ |  $\surd$ |  $\surd$ |  $\times$ |  $\times$
PCAN |  $\surd$ |  $\surd$ |  $\surd$ |  $\times$ |  $\times$
DOGC |  $\surd$ |  $\times$ |  $\surd$ |  $\surd$ |  $\times$
DOGC-OS |  $\surd$ |  $\times$ |  $\surd$ |  $\surd$ |  $\surd$

###  II-C Clustering and Projective Clustering with Adaptive Neighbors

Clustering and projective clustering with adaptive neighbors learns a
structured graph for clustering. Given a data matrix X, all the data points
$\textbf{x}_{j}\mid_{j=1}^{n}$ are connected to $\textbf{x}_{i}$ as neighbors
with probability $\textbf{s}_{i}\mid_{i=1}^{n}$. A smaller distance is
assigned with a large probability and vice versa. To avoid the case that only
the nearest data point is the neighbor of $\textbf{x}_{i}$ with probability 1
and all the other data points are excluded from the neighbor set of
$\textbf{x}_{i}$, a nature solution is to determine the probabilities
$\textbf{s}_{i}\mid_{i=1}^{n}$ by solving

$\displaystyle\min_{\textbf{s}_{i}^{\top}\textbf{1}=1,0\leq s_{ij}\leq
1}\sum_{i,j=1}^{n}\parallel\textbf{x}_{i}-\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}+\xi
s_{ij}^{2}$ (3)

The second term is a regularization term, and $\xi$ is a regularization
parameter.

In the clustering task that partitions the data into $c$ clusters, an ideal
neighbor assignment is that the number of connected components is the same as
the number of clusters $c$. In most cases, all the data points are connected
as just one connected component. In order to achieve an ideal neighbor
assignment, the probability $\textbf{s}_{i}\mid_{i=1}^{n}$ is constrained such
that the neighbor assignment becomes an adaptive process and the number of
connected components is exact $c$. The formula to calculate S in them is:

$\displaystyle\min_{\textbf{S},\textbf{F}}\sum_{i,j=1}^{n}(\parallel\textbf{x}_{i}-\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}+\xi
s_{ij}^{2})+2\lambda Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})$
(4) $\displaystyle\;\mathrm{s.t.}\ \forall
i,\textbf{s}_{i}^{\top}\textbf{1}=1,0\leq s_{ij}\leq
1,\textbf{F}\in\mathbb{R}^{n\times
c},\textbf{F}^{\top}\textbf{F}=\textbf{I}_{c}$

where $\lambda$ is large enough,
$Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})$ is forced to be zero.
Thus, the constraint $rank(\textbf{L}_{S})=n-c$ can be satisfied [28].

###  II-D The Constrained Laplacian Rank for Graph based Clustering

The constrained Laplacian rank for graph based clustering (CLR)[29] follows
the same idea of clustering and projective clustering with adaptive neighbors.
Differently, it learns a new data matrix S based on the given data matrix A
such that S is more suitable for the clustering task. In CLR, the
corresponding Laplacian matrix $\textbf{L}_{\mathrm{S}}$ is also constrained
as $rank(\textbf{L}_{\mathrm{S}})=n-c$. Under this constraint, all data points
can be directly partitioned into exact $c$ clusters[28]. Specifically, CLR
solves the following optimization problem

$\displaystyle\min_{\textbf{S}}\parallel\textbf{S}-\textbf{A}\parallel_{\mathrm{F}}^{2}$
(5) $\displaystyle\mathrm{s.t.}\sum_{j}s_{ij}=1,s_{ij}\geq
0,rank(\textbf{L}_{\mathrm{S}})=n-c$

###  II-E Key Differences between Our Methods and Existing Works

Our work is an advocate of discrete optimization of cluster labels, where the
optimal graph structure is adaptively constructed, the discrete cluster labels
are directly learned, and the out-of-sample extension can be well supported.
Existing clustering methods, k-means (KM), normalized-cut (N-cut)[30], ratio-
cut (R-cut)[13], CLR, spectral embedding clustering (SEC), CAN and PCAN,
suffer from different problems. Our methods aim to tackle them in a unified
learning framework. The main differences between the proposed methods and
existing clustering methods are summarized in Table II.

##  III The Proposed Methodology

In this section, we present the details of the proposed methods and introduce
an alternative optimization for solving the problems.

###  III-A Overall Formulation

Most existing graph based clustering methods separate the graph construction
and clustering into two independent processes. The unguided graph construction
process may lead to sub-optimal clustering result. CAN and PCAN can alleviate
the problem. However, they still suffer from the problems of information loss
and out-of-sample extension.

In this paper, we propose a unified discrete optimal graph clustering (DOGC)
framework to address their problems. DOGC exploits the correlation between
similarity graph and discrete cluster labels when performing the clustering.
It learns a similarity graph with optimal structure for clustering and
directly obtains the discrete cluster labels. Under this circumstance, our
model can not only take the advantage of the optimal graph learning, but also
obtain discrete clustering results. To achieve above aims, we derive the
overall formulation of DOGC as

$\displaystyle\min_{\textbf{S},\textbf{F},\textbf{Y},\textbf{Q}}\sum_{i,j=1}^{n}\parallel\textbf{x}_{i}-\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}+\xi
s_{ij}^{2}+2\lambda Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})$
(6)
$\displaystyle\quad\quad\quad+\alpha\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}$
$\displaystyle\mathrm{s.t.}\ \textbf{S}\in\mathbb{R}^{n\times
n},\textbf{F}\in\mathbb{R}^{n\times
c},\textbf{F}^{\top}\textbf{F}=\textbf{I}_{c},\textbf{Q}^{\top}\textbf{Q}=\textbf{I}_{c},\textbf{Y}\in\mathrm{Idx}$

where $\alpha$ and $\xi$ are penalty parameters, Q is a rotation matrix that
rotates continuous labels to discrete labels. The $\lambda$ can be determined
during the iteration. In each iteration, we can initialize $\lambda=\xi$, then
adaptively increase $\lambda$ if the number of connected components of S is
smaller than $c$ and decrease $\lambda$ if it is greater than $c$.

In Eq.(LABEL:eq:6), we learn an optimal structured graph and discrete cluster
labels simultaneously from the raw data. The first term is to learn the
structured graph. To pursue optimal clustering performance, S should
theoretically have exact $c$ connected components if there are $c$ clusters.
Equivalently, to ensure the quality of the learned graph, the Laplacian matrix
$\textbf{L}_{\mathrm{S}}$ should have $c$ zero eigenvalues and the sum of the
smallest $c$ eigenvalues, $\sum_{i=1}^{c}\sigma_{i}(\textbf{L}_{\mathrm{S}})$,
should be zero. According to Ky Fan theorem[31],
$\sum_{i=1}^{c}\sigma_{i}(\textbf{L}_{\mathrm{S}})=\min_{\textbf{F}^{\top}\textbf{F}=\textbf{I}_{c}}Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})$.
Hence, the second term guarantees that the learned S is optimal for subsequent
clustering. The third term
$\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}$ is to find a
proper rotation matrix Q that makes FQ close to the discrete cluster labels Y.
Ideally, if data points $i$ and $j$ belong to different clusters, we should
have $s_{ij}=0$ and vice versa. That is, we have $s_{ij}\neq 0$ if and only if
data points $i$ and $j$ are in the same cluster, or equivalently
$\textbf{f}_{i}\approx\textbf{f}_{j}$ and $\textbf{y}_{i}=\textbf{y}_{j}$.

The raw features may be high-dimensional and they may contain adverse noises
that are detrimental for similarity graph learning. To enhance the robustness
of the model, we further extend Eq.(LABEL:eq:6) as

$\displaystyle\vspace{-4mm}\min_{\textbf{S},\textbf{F},\textbf{Y},\textbf{Q},\textbf{W}}\underbrace{\sum_{i,j=1}^{n}\frac{\parallel\textbf{W}^{\top}\textbf{x}_{i}-\textbf{W}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})}+\xi
s_{ij}^{2}}_{similarity\quad graph\quad learning}+$ (7)
$\displaystyle\underbrace{2\lambda
Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})}_{continuous\;label\;learning}+\underbrace{\alpha\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}}_{discrete\;label\;learning}$
$\displaystyle\mathrm{s.t.}\ \forall i,\textbf{s}_{i}^{\top}\textbf{1}=1,0\leq
s_{ij}\leq 1,\textbf{F}\in\mathbb{R}^{n\times c},\
\textbf{F}^{\top}\textbf{F}=\textbf{I}_{c},$
$\displaystyle\textbf{Q}^{\top}\textbf{Q}=\textbf{I}_{c},\
\textbf{W}^{\top}\textbf{W}=\textbf{I}_{c},\ \textbf{Y}\in\mathrm{Idx}$

where W is a projection matrix. It maps high-dimensional data into a proper
subspace to remove the noises and accelerate the similarity graph learning.

###  III-B Optimization Algorithm for Solving Problem (7)

In this subsection, we adopt alternative optimization to solve problem (7)
iteratively. In particular, we optimize the objective function with respective
to one variable while fixing the remaining variables. The key steps are as
follows

Update S: For updating S, the problem is reduced to

$\displaystyle\min_{\textbf{S}}\sum_{i,j=1}^{n}\frac{\parallel\textbf{W}^{\top}\textbf{x}_{i}-\textbf{W}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})}+\xi
s_{ij}^{2}$ (8) $\displaystyle\quad\quad\quad+2\lambda
Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})$
$\displaystyle\mathrm{s.t.}\ \forall i,\textbf{s}_{i}^{\top}\textbf{1}=1,0\leq
s_{ij}\leq 1$

Since
$\sum_{i,j=1}^{n}\parallel\textbf{f}_{i}-\textbf{f}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}=2Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})$,
the problem (LABEL:eq:8) can be rewritten as

$\displaystyle\min_{\textbf{S}}\sum_{i,j=1}^{n}\frac{\parallel\textbf{W}^{\top}\textbf{x}_{i}-\textbf{W}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})}+\xi
s_{ij}^{2}$ (9)
$\displaystyle\quad\quad\quad+\lambda\parallel\textbf{f}_{i}-\textbf{f}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}$
$\displaystyle\mathrm{s.t.}\ \forall i,\textbf{s}_{i}^{\top}\textbf{1}=1,0\leq
s_{ij}\leq 1$

In problem (LABEL:eq:9), $\textbf{s}_{i}$ can be solved separately as follows

$\displaystyle\min_{\textbf{s}_{i}}\sum_{j=1}^{n}d_{ij}^{wx}s_{ij}+\xi
s_{ij}^{2}+\lambda d_{ij}^{f}s_{ij}$ (10) $\displaystyle\mathrm{s.t.}\
\textbf{s}_{i}^{\top}\textbf{1}=1,0\leq s_{ij}\leq 1$

where
$d_{ij}^{wx}=\frac{\parallel\textbf{W}^{\top}\textbf{x}_{i}-\textbf{W}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})}$
and
$d_{ij}^{f}=\parallel\textbf{f}_{i}-\textbf{f}_{j}\parallel_{\mathrm{F}}^{2}$.

The optimal solution $\textbf{s}_{i}$ can be obtained by solving the convex
quadratic programming problem $\min_{\textbf{s}_{i}^{\top}\textbf{1}=1,0\leq
s_{ij}\leq
1}\parallel\textbf{s}_{i}+\frac{1}{2\xi}\textbf{d}_{i}\parallel_{\mathrm{F}}^{2}$,
and $d_{ij}=d_{ij}^{wx}+\lambda d_{ij}^{f}$.

Update F: For updating F, it is equivalent to solve

$\displaystyle\min_{\textbf{F}}Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})+\alpha\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}\quad\mathrm{s.t.}\
\textbf{F}^{\top}\textbf{F}=\textbf{I}_{c}$ (11)

The above problem can be efficiently solved by the algorithm proposed by [32].

Update W: For updating W, the problem becomes

$\displaystyle\min_{\textbf{W}^{\top}\textbf{W}=\textbf{I}_{c}}\sum_{i,j=1}^{n}\frac{\parallel\textbf{W}^{\top}\textbf{x}_{i}-\textbf{W}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})}$
(12)

which can be rewritten as

$\displaystyle\min_{\textbf{W}^{\top}\textbf{W}=\textbf{I}_{c}}\frac{Tr(\textbf{W}^{\top}\textbf{X}\textbf{L}_{\mathrm{S}}\textbf{X}^{\top}\textbf{W})}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})}$
(13)

We can solve W using the Lagrangian multiplier method. The Lagrangian function
of problem (13) is

$\displaystyle\pounds(\textbf{W},\epsilon)=\frac{\parallel\textbf{W}^{\top}\textbf{x}_{i}-\textbf{W}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})}-\epsilon(Tr(\textbf{W}^{\top}\textbf{W}-\textbf{I}_{c}))$
(14)

where $\epsilon$ is the Lagrangian multipliers. Taking derivative
$\pounds(\textbf{W},\epsilon)$ w.r.t W and setting it to zero, we have

$\displaystyle(\textbf{X}\textbf{L}_{\mathrm{S}}\textbf{X}^{\top}-\frac{\parallel\textbf{W}^{\top}\textbf{x}_{i}-\textbf{W}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})}\textbf{XHX}^{\top})\textbf{W}=\epsilon\textbf{W}$
(15)

We denote that
$\textbf{V}=\textbf{X}\textbf{L}_{S}\textbf{X}^{\top}-\frac{\parallel\textbf{W}^{\top}\textbf{x}_{i}-\textbf{W}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})}\textbf{XHX}^{\top}$.
The solution of W in problem (15) is formed by $m$ eigenvectors corresponding
to the $m$ smallest eigenvalues of the matrix V. In optimization, we first fix
W in V. Then we update W by $\textbf{V}\textbf{W}=\epsilon\textbf{W}$, and
assign the obtained $\tilde{\textbf{W}}$ after updating to W in V[33]. We
iteratively update it until $\mathrm{K.K.T.}$ condition[34] in Eq.(15) is
satisfied.

Update Q: For updating Q, we have

$\displaystyle\min_{\textbf{Q}}\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}\;\mathrm{s.t.}\
\textbf{Q}^{\top}\textbf{Q}=\textbf{I}_{c}.$ (16)

It is the orthogonal Procrustes problem [35], which admits a closed-form
solution.

Update Y: For updating Y, the problem becomes

$\displaystyle\min_{\textbf{Y}\in\mathrm{Idx}}\alpha\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}\
\mathrm{s.t.}\ \textbf{Y}\in\mathrm{Idx}$ (17)

Note that $Tr(\textbf{Y}^{\top}\textbf{Y})=n$, the problem (LABEL:eq:16) can
be rewritten as below

$\displaystyle\max_{\textbf{Y}\in\mathrm{Idx}}Tr(\textbf{Y}^{\top}\textbf{PQ})\
\mathrm{s.t.}\ \textbf{Y}\in\mathrm{Idx}$ (18)

The optimal solution of Y can be obtained as

$\displaystyle\textbf{Y}_{ij}=\left\\{\begin{array}[]{ll}1,&\textrm{$j=arg\max_{k}(\textbf{PQ})_{ik}$}\\\
0,&\textrm{otherwise}\\\ \end{array}\right.$ (19)

The main procedures for solving the problem (7) are summarized in Algorithm 1.

Input: Data matrix $\textbf{X}\in\mathbb{R}^{d\times n}$, cluster number $c$,
reduced dimension $m$, parameter $\alpha\geq 0$;

Output: F, S, Y, W, Q;

1.Randomly initialize F, S, Y, W, Q;

while  _there is no change on F, S, Y, W, Q_ do

2.Update
$\textbf{L}_{\mathrm{S}}=\textbf{D}_{\mathrm{S}}-\frac{(\textbf{S}^{\top}+\textbf{S})}{2}$;

3.Update S according to the problem (LABEL:eq:10);

4.Update F by solving the problem (11);

5.Update W according to problem (15);

6.Update Q by solving the problem (16);

7.Update Y according to the Eq.(19);

end while

Return F, S, Y, W, Q;

Algorithm 1 Optimizing problem (7)

###  III-C Determine the value of $\xi$[27]

In practice, regularization parameter is difficult to tune since its value
could be from zero to infinite. In this subsection, we present an effective
method to determine the regularization parameter $\xi$ in problem
(LABEL:eq:8). For each $i$, the objective function in problem (LABEL:eq:9) is
equal to the one in problem (LABEL:eq:10). The Lagrangian function of problem
(LABEL:eq:10) is

$\displaystyle\pounds(\textbf{s}_{i},\eta,\bm{\phi})=\frac{1}{2}\parallel\textbf{s}_{i}+\frac{\textbf{d}_{i}^{wx}}{2\xi_{i}}\parallel_{\mathrm{F}}^{2}-\eta(\textbf{s}_{i}^{\top}\textbf{1}-1)-\bm{\phi}_{i}^{\top}\textbf{s}_{i}$
(20)

where $\eta$ and $\bm{\phi}_{i}\geq\textbf{0}$ are the Lagrangian multipliers.

According to the $\mathrm{K.K.T.}$ condition, it can be verified that the
optimal solution $\textbf{s}_{i}$ should be

$\displaystyle s_{ij}=(-\frac{d_{ij}^{wx}}{2\xi_{i}}+\eta)_{+}$ (21)

In practice, we could achieve better performance if we focus on the locality
of data. Therefore, it is preferred to learn a sparse $\textbf{s}_{i}$, i.e.,
only the $k$ nearest neighbors of $\textbf{x}_{i}$ have chance to connect to
$\textbf{x}_{i}$. Another benefit of learning a sparse similarity matrix S is
that the computation burden can be alleviated significantly for subsequent
processing.

Without loss of generality, suppose $d_{i1}^{wx},d_{i2}^{wx},...,d_{in}^{wx}$
are ordered from small to large. If the optimal $\textbf{s}_{i}$ has only $k$
nonzero elements, then according to Eq.(21), we know $s_{i,k}\geq 0$ and
$s_{i,k+1}=0$. Therefore, we have

$\displaystyle-\frac{d_{ik}^{wx}}{2\xi_{i}}+\eta>0,-\frac{d_{i,k+1}^{wx}}{2\xi_{i}}+\eta\leq
0$ (22)

According to Eq.(21) and the constraint $\textbf{s}_{i}^{\top}\textbf{1}=1$,
we have

$\displaystyle\sum_{j=1}^{k}(-\frac{d_{ij}^{wx}}{2\xi_{i}}+\eta)=1\Rightarrow\eta=\frac{1}{k}+\frac{1}{2k\xi_{i}}\sum_{j=1}^{k}d_{ij}^{wx}$
(23)

Hence, we have the following inequality for $\xi$ according to Eq.(22) and
Eq.(23).

$\displaystyle\frac{k}{2}d_{i,k}^{wx}-\frac{1}{2}\sum_{j=1}^{k}d_{ij}^{wx}<\xi_{i}\leq\frac{k}{2}d_{i,k+1}^{wx}-\frac{1}{2}\sum_{j=1}^{k}d_{ij}^{wx}$
(24)

Therefore, in order to obtain an optimal solution $\textbf{s}_{i}$ to the
problem (LABEL:eq:10) that has exact $k$ nonzero values, we could set
$\xi_{i}$ to be

$\displaystyle\xi_{i}=\frac{k}{2}d_{i,k+1}^{wx}-\frac{1}{2}\sum_{j=1}^{k}d_{ij}^{wx}$
(25)

The overall $\xi$ could be set to the mean of
$\xi_{1},\xi_{2},\ldots,\xi_{n}$. That is, we could set the $\xi$ to be

$\displaystyle\xi=\frac{1}{n}\sum_{i=1}^{n}(\frac{k}{2}d_{i,k+1}^{wx}-\frac{1}{2}\sum_{j=1}^{k}d_{ij}^{wx})$
(26)

The number of neighbors $k$ is much easier to tune than the regularization
parameter $\xi$ since $k$ is an integer and it has explicit meaning.

###  III-D Out-of-Sample Extension

Recall that most existing graph based clustering methods can hardly generalize
to the out-of-sample data, which is widely existed in real practice. In this
paper, with the learned discrete labels and mapping matrix, we can easily
extend DOGC for solving the out-of-sample problem. Specifically, we design an
adaptive robust module with $\ell_{2,p}$ loss[36] and integrate them into the
above discrete optimal graph clustering model, to learn prediction function
for unseen data. In our extended model (DOGC-OS), discrete labels are
simultaneously contributed by the original data through the mapping matrix P
and the continuous labels F though the rotation matrix Q. Specifically, DOGC-
OS is formulated as follows

$\displaystyle\min_{\textbf{S},\textbf{F},\textbf{Y},\textbf{Q},\textbf{W},\textbf{P}}\underbrace{\sum_{i,j=1}^{n}\frac{\parallel\textbf{W}^{\top}\textbf{x}_{i}-\textbf{W}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})}+\xi
s_{ij}^{2}}_{similarity\quad graph\quad learning}+$ (27)
$\displaystyle\underbrace{2\lambda
Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})}_{continuous\;label\;learning}+\underbrace{\alpha\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}+\beta\pounds_{2,p}(\textbf{P};\textbf{X},\textbf{Y})}_{discrete\;label\;learning}$

where $\pounds_{2,p}(\textbf{P};\textbf{X},\textbf{Y})$ is the prediction
function learning module. It is calculated as

$\displaystyle\pounds_{2,p}(\textbf{P};\textbf{X},\textbf{Y})=\parallel\textbf{Y}-\textbf{X}^{\top}\textbf{P}\parallel_{2,p}+\gamma\parallel\textbf{P}\parallel_{\mathrm{F}}^{2}$
(28)

$\textbf{P}\in\mathbb{R}^{d\times c}$ is the projection matrix and the loss
function is $\ell_{2,p}(0\leq p\leq 2)$ loss, which is capable of alleviating
sample noise

$\displaystyle\parallel\textbf{M}\parallel_{2,p}=\sum_{i=1}^{n}\parallel\textbf{M}_{i}\parallel_{2}^{p}$
(29)

$\textbf{M}_{i}$ is the $i_{th}$ row of matrix M. The above $\ell_{2,p}$ loss
not only suppresses the adverse noise but also enhances the flexibility for
adapting different noise levels.

###  III-E Optimization Algorithm for Solving Problem (LABEL:eq:26)

Due to the existence of $\ell_{2,p}$ loss, directly optimizing the model turns
out to be difficult. Hence, we transform it to an equivalent problem as
follows

$\displaystyle\min_{\textbf{S},\textbf{F},\textbf{Y},\textbf{Q},\textbf{W},\textbf{P}}\sum_{i,j=1}^{n}(\frac{\parallel\textbf{W}^{\top}\textbf{x}_{i}-\textbf{W}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})}+\xi
s_{ij}^{2})$ (30) $\displaystyle\quad\quad\quad+2\lambda
Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})+\alpha\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}$
$\displaystyle\quad\quad\quad+\beta(Tr(\textbf{R}^{\top}\textbf{DR})+\gamma\parallel\textbf{P}\parallel_{\mathrm{F}}^{2})$
$\displaystyle\mathrm{s.t.}\;\forall i,\textbf{s}_{i}^{\top}\textbf{1}=1,0\leq
s_{ij}\leq 1,\ \textbf{F}^{\top}\textbf{F}=\textbf{I}_{c},$
$\displaystyle\textbf{W}^{\top}\textbf{W}=\textbf{I}_{c},\textbf{Q}^{\top}\textbf{Q}=\textbf{I}_{c},\textbf{Y}\in\mathrm{Idx}$

where D is a diagonal matrix with its $i_{th}$ diagonal element computed as
$\textbf{D}_{ii}=\frac{1}{\frac{2}{p}\parallel\textbf{r}_{i}\parallel_{2}^{2-p}}$
and $\textbf{R}=\textbf{Y}-\textbf{X}^{\top}\textbf{P}$ which is denoted as
the loss residual, $\textbf{r}_{i}$ is the $i_{th}$ row of R.

The steps of updating S, F, Q, W are similar to that of DOGC except the
updating of P and Y.

Update P: For updating P, we arrive at

$\displaystyle\min_{\textbf{P}}Tr((\textbf{Y}-\textbf{X}^{\top}\textbf{P})\textbf{D}(\textbf{Y}-\textbf{X}^{\top}\textbf{P}))+\gamma\parallel\textbf{P}\parallel_{\mathrm{F}}^{2}$
(31)

With the other variables fixed, we arrive at the optimization rule for
updating P as

$\displaystyle\textbf{P}=(\textbf{XDX}^{\top}+\gamma\textbf{I}_{d})^{-1}\textbf{XDY}$
(32)

Update Y: For updating Y, we arrive at

$\displaystyle\min_{\textbf{Y}\in\mathrm{Idx}}\alpha\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}+\beta
Tr((\textbf{Y}-\textbf{X}^{\top}\textbf{P})^{\top}\textbf{D}(\textbf{Y}-\textbf{X}^{\top}\textbf{P}))$
(33)

Given the facts that $Tr(\textbf{Y}^{\top}\textbf{Y})=n$ and
$Tr(\textbf{Y}^{\top}\textbf{DY})=Tr(\textbf{D})$, we can rewrite the above
sub-problem as below

$\displaystyle\max_{\textbf{Y}\in\mathrm{Idx}}Tr(\textbf{Y}^{\top}\textbf{B})$
(34)

where $\textbf{B}=\alpha\textbf{FQ}+\beta\textbf{DX}^{\top}\textbf{P}$. The
above problem can be easily solved as

$\displaystyle\textbf{Y}_{ij}=\left\\{\begin{array}[]{ll}1,&\textrm{$j=arg\max_{k}\textbf{B}_{ik}$}\\\
0,&\textrm{otherwise}\\\ \end{array}\right.$ (35)

###  III-F Discussion

In this subseciton, we discuss the relations of our method DOGC with main
graph based clustering methods.

  * •

Connection to Spectral Clustering[37]. In our model, $\alpha$ controls the
transformation from continuous cluster labels to discrete labels, and
$\lambda$ is adaptively updated with the number of connected components in the
dynamic graph S. When W is a unit matrix, the process of projective subspace
learning with W becomes an identity transformation. When S is fixed, it is not
a dynamic structure any more and $\lambda$ will remain unchanged. When
$\alpha\rightarrow 0$, the effect of the third item in Eq.(7) is invalid.
Under these circumstances, Eq.(7) is equivalent to
$\min_{\textbf{F}}Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})$.
Thus our model degenerates to the spectral clustering.

  * •

Connection to Optimal Graph Clustering[27]. In DOGC, when W is a unit matrix
and $\alpha\rightarrow 0$, the effects of W and $\alpha$ are the same as
above. Differently, when S is dynamically constructed, Eq.(7) is equivalent to
$\min_{\textbf{S},\textbf{F}}\sum_{i,j=1}^{n}(\parallel\textbf{x}_{i}-\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}+\xi
s_{ij}^{2})+2\lambda Tr(\textbf{F}^{\top}\textbf{L}_{\mathrm{S}}\textbf{F})$,
where S contains a specific $c$ connected components and $\lambda$ is adjusted
by the value of $c$. Under these circumstances, our model degenerates to the
optimal graph clustering.

###  III-G Complexity Analysis

As for DOGC, with our optimization strategy, the updating of S requires
$O(N^{2})$. Solving Q involves SVD and its complexity is $O(Nc^{2}+c^{3})$. To
update F, we need $O(Nc^{2}+c^{3})$. To update W, two layers of iterations
should be performed to achieve convergence. The number of internal iterations
is generally a constant, so the time complexity of updating W is $O(N^{2})$.
Optimizing Y consumes $O(Nc^{2})$. In DOGC-OS, we need to consider another
updating process of D and P which both consume $O(N)$. Hence, the whole time
complexity of the proposed methods are all $O(N^{2})$. The computation
complexity is comparable to many existing graph-based clustering methods.

###  III-H Convergence Analysis

In this subsection, we prove that the proposed iterative optimization in
Algorithm 1 will converge. Before that, we introduce three lemmas.

######  Lemma 1.

For any positive real number $a$ and $b$, we can have the following inequality
[38]:

$\displaystyle a^{\frac{p}{2}}-\frac{p}{2}\frac{a}{b^{\frac{2-p}{2}}}\leq
b^{\frac{p}{2}}-\frac{p}{2}\frac{b}{b^{\frac{2-p}{2}}}$ (36)

######  Lemma 2.

Let $\textbf{r}_{i}$ be the $i_{th}$ row of the residual R in previous
iteration, and $\tilde{\textbf{r}_{i}}$ be the $i_{th}$ row of the residual
$\tilde{\textbf{R}}$ in current iteration, it has been shown in [39] that the
following inequality holds:

$\displaystyle\parallel\tilde{\textbf{r}_{i}}\parallel^{p}-\frac{p\parallel\tilde{\textbf{r}_{i}}\parallel^{2}}{2\parallel\textbf{r}_{i}\parallel^{2-p}}\leq\parallel\textbf{r}_{i}\parallel^{p}-\frac{p\parallel\textbf{r}_{i}\parallel^{2}}{2\parallel\textbf{r}_{i}\parallel^{2-p}}$
(37)

######  Lemma 3.

Given
$\textbf{R}=\big{\\{}\textbf{r}_{1},\ldots,\textbf{r}_{n}\big{\\}}^{\top}$,
then we have the following conclusion:

$\displaystyle\sum_{i=1}^{n}\parallel\tilde{\textbf{r}_{i}}\parallel^{p}-\sum_{i=1}^{n}\frac{p\parallel\tilde{\textbf{r}_{i}}\parallel^{2}}{2\parallel\textbf{r}_{i}\parallel^{2-p}}\leq\sum_{i=1}^{n}\parallel\textbf{r}_{i}\parallel^{p}-\sum\frac{p\parallel\textbf{r}_{i}\parallel^{2}}{2\parallel\textbf{r}_{i}\parallel^{2-p}}$
(38)

###### Proof.

By summing up the inequalities of all $\textbf{r}_{i},i=1,2,\ldots,n$,
according to Lemma 2, we can easily reach the conclusion of Lemma 3. ∎

######  Theorem 1.

In DOGC-OS, updating
$\tilde{\textbf{Y}},\tilde{\textbf{F}},\tilde{\textbf{Q}},\tilde{\textbf{W}},\tilde{\textbf{P}},\tilde{\textbf{S}}$
will decrease the objective value of problem (LABEL:eq:26) until converge.

###### Proof.

Let
$\tilde{\textbf{Y}},\tilde{\textbf{F}},\tilde{\textbf{Q}},\tilde{\textbf{W}},\tilde{\textbf{P}},\tilde{\textbf{S}}$
are the optimized solution of the alternative problem (LABEL:eq:26), and we
denote

$\displaystyle\left\\{\begin{array}[]{ll}\psi=\sum_{i,j=1}^{n}\frac{\parallel\textbf{W}^{\top}\textbf{x}_{i}-\textbf{W}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}s_{ij}}{Tr(\textbf{W}^{\top}\textbf{XHX}^{\top}\textbf{W})},\\\
\tilde{\psi}=\sum_{i,j=1}^{n}\frac{\parallel\tilde{\textbf{W}}^{\top}\textbf{x}_{i}-\tilde{\textbf{W}}^{\top}\textbf{x}_{j}\parallel_{\mathrm{F}}^{2}\tilde{s_{ij}}}{Tr(\tilde{\textbf{W}}^{\top}\textbf{XHX}^{\top}\tilde{\textbf{W}})},\\\
\end{array}\right.$ (39)

It is easy to know that:

$\displaystyle\frac{p}{2}\frac{\tilde{\psi}^{\frac{2}{p}}}{(\psi^{\frac{2}{p}})^{\frac{2-p}{2}}}+\xi\parallel\tilde{\textbf{S}}\parallel_{\mathrm{F}}^{2}\leq\frac{p}{2}\frac{\psi^{\frac{2}{p}}}{(\psi^{\frac{2}{p}})^{\frac{2-p}{2}}}+\xi\parallel\textbf{S}\parallel_{\mathrm{F}}^{2}$
(40)

According to Lemma 1, we have

$\displaystyle(\tilde{\psi}^{\frac{2}{p}})^{\frac{p}{2}}-\frac{p}{2}\frac{\tilde{\psi}^{\frac{2}{p}}}{(\psi^{\frac{2}{p}})^{\frac{2-p}{2}}}\leq(\psi^{\frac{2}{p}})^{\frac{p}{2}}-\frac{p}{2}\frac{\psi^{\frac{2}{p}}}{(\psi^{\frac{2}{p}})^{\frac{2-p}{2}}}$
(41)

By summing over Eq.(40) and Eq.(41) in the two sides, we arrive at

$\displaystyle\tilde{\psi}+\xi\parallel\tilde{\textbf{S}}\parallel_{\mathrm{F}}^{2}\leq\psi+\xi\parallel\textbf{S}\parallel_{\mathrm{F}}^{2}$
(42)

We also denote

$\displaystyle\left\\{\begin{array}[]{ll}\jmath=Tr(\textbf{F}^{\top}\textbf{L}_{S}\textbf{F})+\alpha\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}+\beta\gamma\parallel\textbf{P}\parallel_{\mathrm{F}}^{2}\\\
\tilde{\jmath}=Tr(\tilde{\textbf{F}}^{\top}\tilde{\textbf{L}_{S}}\tilde{\textbf{F}})+\alpha\parallel\tilde{\textbf{Y}}-\tilde{\textbf{F}}\tilde{\textbf{Q}}\parallel_{\mathrm{F}}^{2}+\beta\gamma\parallel\tilde{\textbf{P}}\parallel_{\mathrm{F}}^{2}\\\
\end{array}\right.$ (43)

Then, we have

$\displaystyle\tilde{\jmath}+\beta
Tr(\tilde{\textbf{R}}^{\top}\textbf{D}\tilde{\textbf{R}})\leq\jmath+\beta
Tr(\textbf{R}^{\top}\textbf{DR})$ (44)
$\displaystyle\Rightarrow\tilde{\jmath}+\beta\sum_{i=1}^{n}\frac{p\parallel\tilde{\textbf{r}_{i}}\parallel^{2}}{2\parallel\textbf{r}_{i}\parallel^{2-p}}\leq\jmath+\beta\sum_{i=1}^{n}\frac{p\parallel\textbf{r}_{i}\parallel^{2}}{2\parallel\textbf{r}_{i}\parallel^{2-p}}$
(45)

$\displaystyle\Rightarrow\tilde{\jmath}+\beta\sum_{i=1}^{n}\parallel\tilde{\textbf{r}_{i}}\parallel^{p}-\beta(\sum_{i=1}^{n}\parallel\tilde{\textbf{r}_{i}}\parallel^{p}-\sum_{i=1}^{n}\frac{p\parallel\tilde{\textbf{r}_{i}}\parallel^{2}}{2\parallel\textbf{r}_{i}\parallel^{2-p}})\leq$
(46)
$\displaystyle\jmath+\beta\sum_{i=1}^{n}\parallel\textbf{r}_{i}\parallel^{p}-\beta(\sum_{i=1}^{n}\parallel\textbf{r}_{i}\parallel^{p}-\sum_{i=1}^{n}\frac{p\parallel\textbf{r}_{i}\parallel^{2}}{2\parallel\textbf{r}_{i}\parallel^{2-p}})$

With Lemma 3, we have

$\displaystyle\tilde{\jmath}+\beta\sum_{i=1}^{n}\parallel\tilde{\textbf{r}_{i}}\parallel^{p}\leq\jmath+\beta\sum_{i=1}^{n}\parallel\textbf{r}_{i}\parallel^{p}$
(47)

By summing over Eq.(42) and Eq.(47) in the two sides, we arrive at

$\displaystyle\tilde{\psi}+\xi\parallel\tilde{\textbf{S}}\parallel_{\mathrm{F}}^{2}+\tilde{\jmath}+\beta\sum_{i=1}^{n}\parallel\tilde{\textbf{r}_{i}}\parallel^{p}\leq$
(48)
$\displaystyle\psi+\xi\parallel\textbf{S}\parallel_{\mathrm{F}}^{2}+\jmath+\beta\sum_{i=1}^{n}\parallel\textbf{r}_{i}\parallel^{p}$

This equation indicates that the monotonic decreasing trend of the objective
function in Eq.(LABEL:eq:26) in each iteration. ∎

TABLE III: Discriptions of 12 datasets Datasets |  Sample |  Feature |  Class
---|---|---|---
Solar |  322 |  12 |  6
Vehicle |  846 |  18 |  4
Vote |  434 |  16 |  2
Ecoli |  336 |  7 |  8
Wine |  178 |  13 |  3
Glass |  214 |  9 |  6
Lenses |  24 |  4 |  3
Heart |  270 |  13 |  2
Zoo |  101 |  16 |  7
Cars |  392 |  8 |  3
Auto |  205 |  25 |  6
Balance |  625 |  4 |  3

##  IV Experimental configuration

In this section, we introduce the experimental settings, including experiments
datasets, baselines, evaluation metric and implementation details.

###  IV-A Experimental datasets

The experiments are conducted on 12 publicly available datasets, including
eight object datasets (i.e., Wine, Ecoli, Vehicle, Auto, Glass, Lenses, Zoo,
Cars), one disease dataset (i.e. Heart), one dataset to model psychological
experiments (i.e. Balance), one dataset for voting election (i.e. Vote) and
one dataset for describing the change about the number of solar flares. All
these datasets can be obtained from UCI repository
(http://archive.ics.uci.edu/ml/datasets). The descriptions of these 12
datasets are summarized in Table III.

###  IV-B Evaluation Baselines

In experiments, we compare the proposed DOGC and DOGC-OS with the following
clustering methods:

  * •

KM[6]: KM learns clustering model by jointly minimizing the distances of
similar samples and maximizing that of dissimilar samples.

  * •

R-cut[30], N-cut[13]: In this two methods, clusters are represented with
subgraphs. R-cut and N-cut simultaneously maximize the weights between the
same subgraphs and minimize the weights between different subgraphs.

  * •

NMF[40]: It first decomposes the nonnegative feature matrix into the product
of two nonnegative matrices. Then, k-means is performed on the one of
nonnegative matrix with lower matrix dimension to calculate the cluster
labels.

  * •

CLR[29]: CLR has two variants: CLR0 and CLR1. The former supports L1-norm
regularization term and the latter supports the L2-norm. Instead of using a
fixed input similarity matrix, they both first learn the similarity matrix S
with exact $c$ connected components based on fixed similarity matrix A. Then,
graph cut is performed on S to calculate the final cluster labels.

  * •

CAN[27]: CAN learns the data similarity matrix by assigning the adaptive
neighbors for each data point based on local distances. It imposes the rank
constraint on the Laplacian matrix of similarity graph, such that the number
of connected components in the resulted similarity matrix is exactly equal to
the cluster number.

  * •

PCAN[27]: Derived from CAN, PCAN improves its performance further by
simultaneously performing subspace discovery, similarity graph learning and
clustering.

###  IV-C Evaluation Metrics

We employ Normalized Mutual Information (NMI), Accuracy (ACC) and Purity as
main evaluation metrics.

  * •

NMI: We first define normalized mutual information of two distributions
$\tilde{A}$ and $\tilde{B}$ as below:

$\displaystyle
NMI(\tilde{A},\tilde{B})=\frac{H(\tilde{A},\tilde{B})}{\sqrt{\Psi(\tilde{A})\Psi(\tilde{B})}},$
(49)

where $H(\tilde{A},\tilde{B})$ computes the mutual information of $\tilde{A}$
and $\tilde{B}$. $\Psi(\cdot)$ is the entropy of a distribution. Denote
$n_{i}$ as the number of datums in the $i_{th}$ cluster $\textbf{C}_{i}$
generated by a clustering algorithm, $\hat{n_{j}}$ as the number of data
points in the $j_{th}$ ground truth class $\textbf{G}_{j}$, $n_{ij}$ as the
number of data occurring in both $\textbf{C}_{i}$ and $\textbf{G}_{j}$. Then,
NMI is calculated as follows:

$\displaystyle NMI=\frac{\sum_{i=1}^{c}\sum_{j=1}^{c}n_{i,j}\log(\frac{n\times
n_{i,j}}{n_{i}\hat{n_{j}}})}{\sqrt{(\sum_{i=1}^{c}n_{i}\log\frac{n_{i}}{n})(\sum_{j=1}^{c}\hat{n_{j}}\log\frac{\hat{n_{j}}}{n})}}.$
(50)

Larger NMI values indicate better clustering performance.

  * •

ACC: Denote $\textbf{y}_{i}$ as the resultant cluster label of
$\textbf{x}_{i}$ using certain clustering method and $\textbf{g}_{i}$ as the
ground truth of $\textbf{x}_{i}$, then we have

$\displaystyle
ACC=\frac{\sum_{i}\delta(\textbf{y}_{i},map(\textbf{g}_{i}))}{n},$ (51)

where $\delta(x,y)=1$ if $x=y$, $\delta(x,y)=0$ otherwise, and
$map(\textbf{g}_{i})$ is the best mapping function that permutes cluster
labels to match the ground truth labels. Larger ACC values indicate better
clustering performance.

  * •

Purity: Apart from ACC and NMI, purity is another popularly used evaluation
metric. For ground-truth set
$\bm{\mu}=\big{\\{}\mu_{1},\mu_{2},\ldots,\mu_{n}\big{\\}}$ and clustering
result set $\bm{\nu}=\big{\\{}\nu_{1},\nu_{2},\ldots,\nu_{n}\big{\\}}$, the
purity is computed by first assigning each cluster to the class which is the
most frequent in the cluster, and then counting the number of correctly
assigned objects, finally dividing by $n$:

$\displaystyle
Purity(\bm{\mu},\bm{\nu})=\frac{1}{n}\Sigma_{k}\max_{j}|\nu_{k}\cap\mu_{j}|$
(52)

Similar to ACC and NMI evaluation metric, the higher the purity, the better
clustering performance.

###  IV-D Implementation Details

In the experiment, we set the number of clusters to be the ground truth in
each dataset. The parameters of all compared algorithms are in arrange of
$\big{\\{}10^{-6},10^{-4},10^{-2},1,10^{2},10^{4}\big{\\}}$. For those methods
calling for a fixed similarity matrix as an input, like Ratio Cut, Normalized
Cut, CLR0, CLR1 and NMF, the graph is constructed with the Gaussian kernel
function. As for CAN, PCAN, DOGC and DOGC-OS, we randomly initialize their
involved variables. We repeat the clustering process 100 times independently
to perform all the methods and record the best result. The best performance of
DOGC-OS and DOGC is achieved when $k$ is set to around $\frac{1}{10}$ of the
total amount of each dataset. In DOGC, there is only one parameter $\alpha$.
When $\alpha$ ranges in $\big{\\{}10^{-6},10^{-4},10^{-2}\big{\\}}$, we record
the best result of DOGC on each dataset. In DOGC-OS, there are three
parameters: $\alpha$, $\beta$ and $\gamma$. With $\alpha$ ranging in
$\big{\\{}10^{-4},10^{-2}\big{\\}}$, we will obtain a generally optimal result
on each dataset. We further optimize the results by fixing $\alpha$ and
adjusting $\beta$. $\alpha$ is mainly used for discrete label learning, and
$\beta$ is a parameter that controls the projection from the raw data to the
final cluster labels. The balance of $\alpha$ and $\beta$ is crucial. $\gamma$
is adjusted while the overfitting problem arises. When predicting the new
data, we set $\gamma$ to 0.1 or 1. When we pour all the data into model to
perform training, we set $\gamma$ to 0.0001.

TABLE IV: ACC on Real Datasets Methods | KM | R-Cut | N-Cut | CLR0 | CLR1 | NMF | CAN | PCAN | DOGC | DOGC-OS
---|---|---|---|---|---|---|---|---|---|---
Solar | 0.5182 | 0.3498 | 0.3932 | 0.2879 | 0.2879 | 0.5201 | 0.5448 | 0.4396 | 0.4789 | 0.6149
Vehicle | 0.4527 | 0.4598 | 0.4598 | 0.4101 | 0.4101 | 0.4433 | 0.4468 | 0.4527 | 0.4276 | 0.5532
Vote | 0.8345 | 0.5701 | 0.5701 | 0.6206 | 0.6206 | 0.8092 | 0.8667 | 0.9218 | 0.9401 | 0.9562
Ecoli | 0.7679 | 0.5417 | 0.5476 | 0.5565 | 0.5922 | 0.6101 | 0.8053 | 0.8274 | 0.8125 | 0.8631
Wine | 0.7022 | 0.6180 | 0.6180 | 0.5168 | 0.5168 | 0.6685 | 0.9494 | 0.9940 | 0.9944 | 0.9831
Glass | 0.5561 | 0.3828 | 0.3826 | 0.4392 | 0.5093 | 0.3785 | 0.5000 | 0.4953 | 0.6075 | 0.5981
Lenses | 0.6250 | 0.5000 | 0.5000 | 0.5000 | 0.4583 | 0.6667 | 0.7624 | 0.8750 | 0.8750 | 0.8750
Heart | 0.5926 | 0.6259 | 0.6296 | 0.6222 | 0.6111 | 0.6296 | 0.5963 | 0.7148 | 0.8556 | 0.8370
Zoo | 0.8416 | 0.5149 | 0.5149 | 0.4455 | 0.4455 | 0.8020 | 0.7921 | 0.8218 | 0.8916 | 0.8812
Cars | 0.4490 | 0.6301 | 0.6378 | 0.6173 | 0.6173 | 0.6122 | 0.6250 | 0.5791 | 0.6039 | 0.6735
Auto | 0.3659 | 0.3220 | 0.3171 | 0.3610 | 0.3610 | 0.3415 | 0.3463 | 0.3268 | 0.4146 | 0.4488
Balance | 0.6400 | 0.5296 | 0.5264 | 0.6368 | 0.6624 | 0.6656 | 0.5616 | 0.5936 | 0.6823 | 0.7312
TABLE V: NMI on Real Datasets Methods | KM | R-Cut | N-Cut | CLR0 | CLR1 | NMF | CAN | PCAN | DOGC | DOGC-OS
---|---|---|---|---|---|---|---|---|---|---
Solar | 0.4131 | 0.1884 | 0.2119 | 0.2618 | 0.2618 | 0.3375 | 0.3869 | 0.2549 | 0.2876 | 0.4219
Vehicle | 0.1800 | 0.1881 | 0.1928 | 0.1574 | 0.1574 | 0.1369 | 0.2070 | 0.0530 | 0.1980 | 0.2370
Vote | 0.3658 | 0.0745 | 0.0745 | 0.1275 | 0.1275 | 0.3067 | 0.4320 | 0.5888 | 0.6616 | 0.6852
Ecoli | 0.5606 | 0.5207 | 0.5210 | 0.5173 | 0.4836 | 0.5045 | 0.7220 | 0.7244 | 0.6425 | 0.6901
Wine | 0.8385 | 0.8562 | 0.8792 | 0.3144 | 0.3144 | 0.8324 | 0.8897 | 0.9425 | 0.9729 | 0.9261
Glass | 0.3575 | 0.3215 | 0.2858 | 0.3266 | 0.3266 | 0.2870 | 0.2691 | 0.3382 | 0.3601 | 0.3575
Lenses | 0.4696 | 0.2197 | 0.1619 | 0.1619 | 0.1396 | 0.3097 | 0.3977 | 0.6227 | 0.6652 | 0.6652
Heart | 0.0190 | 0.0437 | 0.0482 | 0.0350 | 0.0357 | 0.0494 | 0.1227 | 0.1330 | 0.4042 | 0.3556
Zoo | 0.7803 | 0.5926 | 0.6119 | 0.3770 | 0.3770 | 0.7483 | 0.7446 | 0.7366 | 0.8168 | 0.8259
Cars | 0.1910 | 0.1948 | 0.2020 | 0.2025 | 0.2025 | 0.1713 | 0.2747 | 0.2686 | 0.2724 | 0.2926
Auto | 0.1090 | 0.1346 | 0.1331 | 0.1690 | 0.1691 | 0.0285 | 0.0426 | 0.0703 | 0.2257 | 0.2074
Balance | 0.2966 | 0.1469 | 0.1432 | 0.0922 | 0.1147 | 0.2259 | 0.1510 | 0.1221 | 0.2831 | 0.3093

##  V Experimental results

In this section, we evaluate the performance of the proposed methods on both
synthetic and real datasets. First, we compare our method with the baselines
on 12 real datasets. Then, we demonstrate the effects of the proposed methods
on discrete label learning, optimal graph learning, projective subspace
learning, and out-of-sample extension. Next, parameter experiment is carried
out to evaluate the robustness of the proposed methods. Finally, the
convergence of the proposed methods is verified by the experimental results.

(a) KM (b) DOGC-I (c) DOGC-OS (d) Noise sensitivity (ACC)

Figure 1: Clustering results on the 36 multi-clusters synthetic data.

(a) KM (b) DOGC-II (c) DOGC-OS

Figure 2: Clustering results on the two-moon synthetic data.

###  V-A Performance Comparison

Table IV and Table V present the main ACC and NMI comparison. The presented
results clearly demonstrate that DOGC and DOGC-OS consistently outperform the
compared approaches on all real datasets. On Wine, the accuracy of DOGC can
nearly reach 1. On most datasets, our methods outperform the second best
baseline by more than 0.02. In particular, DOGC-OS achieves an amazing
improvement of 0.1408 on Heart compared to the second best baseline PCAN.
Compare with the best clustering method PCAN on Ecoli, the proposed DOGC-OS
obtains an absolute improvement of 0.0357. In compared approaches, graph based
clustering methods without optimal graph learning generally achieve worse
performance. This may attribute to their fixed similarity graph which is not
optimal for the subsequent clustering. In addition, it is interesting to find
that optimal graph clustering methods may not obtain better performance than
the graph based approaches in certain case. This may be because that the
insufficient input samples in these datasets cannot provide enough information
for learning a well structured graph for clustering. Under this circumstance,
the performance of CAN and PCAN may be impaired. Finally, we analyze why DOGC-
OS outperforms DOGC on some datsets, in the DOGC-OS model, the final
clustering indicator matrix Y stems from two transformations
$\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}$ and
$\parallel\textbf{Y}-\textbf{X}^{\top}\textbf{P}\parallel_{\mathrm{F}}^{2}$.
Only $\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}$ is in DOGC.
It can be seen that DOGC-OS whose Y is under two transformations guidance
should be better than DOGC that is guided from
$\parallel\textbf{Y}-\textbf{FQ}\parallel_{\mathrm{F}}^{2}$ only.

###  V-B Effects of Discrete Label Learning

Our methods can directly solve discrete cluster labels without any relaxing.
To evaluate the effects of discrete label learning, we compare the performance
of DOGC-OS with a variant of our method DOGC-I that relaxes the discrete
labels to continuous labels on 36 muti-clusters synthetic dataset. This
synthetic dataset is a randomly generated multi-cluster data, there are 36
clusters distributed in a spherical way. Figure 1 and Table VI show the
experimental results. From them, we can clearly observe that DOGC-OS fully
separates the data (as shown in Figure 1) and achieves superior clustering
performance than DOGC-I on 5 UCI real datasets (as shown in Table VI).
Further, we set noise level of 36 muti-clusters synthetic dataset in the range
from 0.02 to 0.1 with the interval of 0.01 and observe the performance. We run
k-means, DOGC-I and DOGC-OS 100 times and report the best result. Figure 1
reports the results. From it, we can find that DOGC-OS consistently achieves
higher clustering accuracy than that of DOGC-I and k-means under different
noise levels.

Methods | ACC | NMI
---|---|---
DOGC-I | DOGC-II | DOGC-OS | DOGC-I | DOGC-II | DOGC-OS
Wine | 0.9752 | 0.9752 | 0.9831 | 0.8750 | 0.8989 | 0.9261
Solar | 0.5627 | 0.6111 | 0.6149 | 0.3998 | 0.4169 | 0.4219
Vehicle | 0.4785 | 0.5532 | 0.5532 | 0.1980 | 0.2261 | 0.2370
Vote | 0.9382 | 0.9494 | 0.9562 | 0.7364 | 0.6784 | 0.6852
Ecoli | 0.7981 | 0.8251 | 0.8631 | 0.5742 | 0.5898 | 0.6901

TABLE VI: Performance of DOGC-I, DOGC-II and DOGC-OS on five UCI datasets. The
best result is marked with bold.

###  V-C Effects of Optimal Graph Learning

In this subsection, we conduct experiment to investigate the effects of
optimal graph learning in our methods. To this end, we compare the performance
of DOGC-OS with a variant of our methods DOGC-II that removes optimal graph
learning function on the two-moon synthetic dataset. In experiments, DOGC-II
exploits a fixed similarity graph for input. The two-moon data is randomly
generated and there are two data clusters distributed in two-moon shape. Our
goal is to divide the data points into exact two clusters. Figure 2 and Table
VI show the experimental results. From them, we can clearly observe that our
methods can clearly partition the two-moon data (as shown in Figure 2) and
achieve superior clustering performance than DOGC-II on 5 UCI real datasets
(as shown in Table VI). These results demonstrate that the optimal graph
learning in our methods can indeed discover the intrinsic data structure and
thus improve the clustering methods.

###  V-D Effects of Projective Subspace Learning

Both DOGC and DOGC-OS can discover a discriminative subspace for data
clustering. To validate the effects of projective subspace learning, we
compare our methods with PCA[41] and LPP[42] on two-Gaussian data[43]. In this
dataset, two clusters of data are randomly generated to obey the Gaussian
distribution. In experiments, we observe their separation capability by
varying the distance of two clusters. Figure 3 shows the main results. From
it, we can observe that all these four methods can easily find a proper
projection direction when two clusters are far from each other. However, as
the distance between these two clusters reduces down, PCA becomes ineffective.
As the two clusters become closer, LPP fails to achieve the projection goal.
However, both DOGC and DOGC-OS always perform well. Theoretically, PCA only
focuses on the global structure. Thus it will fail immediately when two
clusters become closer. LPP pays more attention on preserving the local
structure. It could still achieve satisfactory performance when two clusters
are relatively close. Nevertheless, when the distance of two clusters becomes
fairly small, LPP is also incapable any more. Different from them, DOGC and
DOGC-OS can always keep a satisfactory separation capability consistently as
they could identify a discriminative projective subspace with the force of
reasonable rank constraint.

(a) Clusters are far away (b) Clusters are relatively close (c) Clusters are
fairly close

Figure 3: Clustering results on the two-Gaussian synthetic data

###  V-E Effects of Out-of-Sample Extension

Out-of-sample extension is designed in our approach to predict the unseen data
and improve the clustering accuracy. In this subsection, we conduct experiment
to evaluate the effects of out-of-sample extension. Specifically, 5 UCI
datasets are used to demonstrate the capability of the proposed method on
clustering the unseen data. 6 representative clustering methods: k-means
(KM)[6], spectral clustering (SC)[7], spectral embedding clustering (SEC)[12],
discriminative k-means (DKM)[44], local learning (LL)[45], clustering with
local and global regularization (CLGR)[46] are used for performance
comparison. On each dataset, we randomly choose $50\%$ of data samples for
training and the rest for testing. In DOGC-OS, the training data is used to
train projection matrix P with which the discrete cluster labels of testing
data are obtained by projection process. For other methods, we import two
parts of data together into their models and report their clustering. As shown
in Table VII and Table VIII, DOGC-OS achieves higher ACC than other methods on
both training data and testing data. Furthermore, to evaluate the effects of
out-of-sample extension on improving the clustering performance, we compare
DOGC-OS with DOGC that removes the part of out-of-sample extension. The
results are shown in Table IV and Table V. From them, we can clearly observe
that DOGC-OS can achieve superior performance in most datasets.

TABLE VII: ACC on training part of five datasets Methods | KM | DKM | SC | LL | CLGR | SEC | DOGC-OS
---|---|---|---|---|---|---|---
Solar | 0.4568 | 0.5679 | 0.4444 | 0.4074 | 0.5370 | 0.5802 | 0.6147
Vehicle | 0.4539 | 0.4539 | 0.4941 | 0.5532 | 0.5177 | 0.4681 | 0.5626
Vote | 0.7844 | 0.8624 | 0.8394 | 0.8716 | 0.8440 | 0.7936 | 0.9309
Ecoli | 0.6488 | 0.6667 | 0.3631 | 0.4286 | 0.5179 | 0.6429 | 0.8333
Wine | 0.7079 | 0.7079 | 0.7079 | 0.5843 | 0.7079 | 0.7416 | 0.9326
TABLE VIII: ACC on Testing part of five datasets Methods | KM | DKM | SC | LL | CLGR | SEC | DOGC-OS
---|---|---|---|---|---|---|---
Solar | 0.5155 | 0.5466 | 0.3043 | 0.5217 | 0.6025 | 0.5776 | 0.6089
Vehicle | 0.4468 | 0.4586 | 0.3877 | 0.5272 | 0.4894 | 0.4539 | 0.5302
Vote | 0.8065 | 0.8433 | 0.7926 | 0.8986 | 0.8525 | 0.8111 | 0.9401
Ecoli | 0.7321 | 0.7262 | 0.6548 | 0.7202 | 0.6726 | 0.7381 | 0.7738
Wine | 0.7079 | 0.7079 | 0.6292 | 0.5393 | 0.7753 | 0.6966 | 0.9326

Figure 4: ACC and NMI variations with the parameter $\alpha$ in DOGC.

(a) ACC (Vote)-Sensitivity of $p$

(b) NMI (Vote)-Sensitivity of $p$

(c) ACC (Ecoli)-Sensitivity of $p$

(d) NMI (Ecoli)-Sensitivity of $p$

Figure 5: Parameter variations with parameter $p$ in DOGC-OS

(a) $\alpha$=0.0001 (b) $\gamma$=0.0001 (c) $\beta$=0.01

Figure 6: Performance variations with the parameters $\alpha$, $\beta$ and
$\gamma$ on Vote.

(a) $\alpha$=0.000001 (b) $\gamma$=0.000001 (c) $\beta$=0.001

Figure 7: Performance variations with the parameters $\alpha$, $\beta$ and
$\gamma$ on Ecoli.

###  V-F Parameter Sensitivity Experiment

There are three parameters: $\alpha$, $\beta$ and $\gamma$ in DOGC-OS, and one
parameter $\alpha$ in DOGC. In this subsection, we perform experiments on Vote
and Ecoli to evaluate the parameter sensitivity of the proposed methods, and
investigate how they perform on different parameter settings. In experiment,
we tune the parameters $\alpha$, $\beta$ and $\gamma$ in the range of
$\big{\\{}10^{-6},10^{-4},10^{-2},1,10^{2},10^{4}\big{\\}}$, and $p$ from 0.25
to 1.75. In DOGC, we observe the variations of ACC and NMI with $\alpha$ from
$10^{-6}$ to $10^{4}$ (as shown in Figure 4). In DOGC-OS, we first select
three groups of parameters with fixed $\alpha$, $\beta$ and $\gamma$ (as shown
in Figure 5). From it, we find that $p$=1.25 is optimal for clustering. Then,
we fix $p$=1.25, and evaluate the performance variations with remaining
$\alpha$, $\beta$, $\gamma$. Specifically, we fix two parameters and observe
the variations of ACC with the other one. Figure 6 and 7 illustrate the main
experimental results. The analysis of the parameters effects are as follows:

(a) DOGC (Ecoli) (b) DOGC (Vote) (c) DOGC-OS (Ecoli) (d) DOGC-OS (Vote)

Figure 8: The variations of objective function value with the number of
iterations on two datasets.

  * •

Joint effects of $\alpha$ and $\beta$. $\alpha$ contributes to discrete label
learning. In DOGC and DOGC-OS, $\alpha$ plays a crucial role in clustering
performance. In experiments, we find that our methods can achieve satisfactory
performance with $\alpha$ in the range of
$\big{\\{}10^{-6},10^{-4},10^{-2}\big{\\}}$. In DOGC-OS, when $\alpha$ is
small, we observe a decreasing trend of performance as $\beta$ increases. Once
$\alpha$ is larger than $\beta$, our method works better instead.

  * •

Effects of $\gamma$. $\gamma$ controls the prediction residual error
$\parallel\textbf{Y}-\textbf{X}^{\top}\textbf{P}\parallel_{2,p}$. In DOGC-OS,
as $\gamma$ increases from $10^{-2}$ to $10^{-1}$, it performs gradually
better. When $\gamma$ keeps going up, we observe a decreasing trend instead.
If $\gamma$ is small, the regularization term will become less significant and
over-fitting problem may be brought. On the contrary, when we use large
$\gamma$, the prediction residual error will not be well controlled. Under
this circumstance, our approach DOGC-OS will produce sub-optimal prediction
function and discrete cluster labels.

  * •

Effects of $p$. In DOGC-OS, when $\alpha$ is optimal, $p$ will have less
influence on the clustering performance. The main reason is that the influence
of $\alpha$ covers $p$. In contrast, if $\alpha$ is not optimal, the influence
of $p$ on ACC gradually becomes important. Under such circumstance, when $p$
is in the range of 1 to 1.5, it can help to improve ACC.

###  V-G Convergence Experiment

We have theoretically proved that the proposed iterative optimization can
obtain a converged solution. In this subsection, we empirically evaluate the
convergence of the proposed algorithms. We conduct experiments on Vote and
Ecoli. Similar results can be obtained on other datasets. Figure 8 records the
variations of objective function value of Eq.(7) and Eq.(LABEL:eq:26)
respectively with the number of iterations. It clearly shows that our
approaches are able to converge rapidly within only a few iterations (less
than 10).

##  VI Conclusions

In this paper, we propose a unified discrete optimal graph clustering
framework. In our methods, a structured graph is adaptively learned with the
guidance of a reasonable rank constraint to support the clustering. Discrete
cluster labels are directly learned by learning a proper rotation matrix to
avoid the relaxing information loss. Besides, projective subspace learning is
performed in our framework to eliminate noise and extract discriminative
information from raw features to facilitate clustering. Moreover, our model
can support the clustering task on the out-of-sample data by designing a
robust prediction module. Experiments on both synthetic and real datasets
demonstrate the superior performance of the proposed methods.

## Acknowledgment

The authors would like to thank the anonymous reviewers for their constructive
and helpful suggestions.

## References

  * [1] D. Jiang, C. Tang, and A. Zhang, “Cluster analysis for gene expression data: A survey,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 16, no. 11, pp. 1370–1386, 2004.
  * [2] 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.
  * [3] X. Wang, L. Zhang, X. Li, and W. Ma, “Annotating images by mining image search results,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , vol. 30, no. 11, pp. 1919–1932, 2008.
  * [4] Z. Cheng and J. Shen, “On effective location-aware music recommendation,” _ACM Transactions on Information Systems_ , vol. 34, no. 2, pp. 13:1–13:32, 2016.
  * [5] ——, “Just-for-me: An adaptive personalization system for location-aware social music recommendation,” in _Proceedings of International Conference on Multimedia Retrieval_ , 2014, pp. 185:185–185:192.
  * [6] J.B.MacQueen, “Some methods for classification and analysis of multivariate observations,” _Proceedings of Berkeley Symposium on Mathematical Statistics and Probability_ , pp. 281–297, 1967.
  * [7] A. Y. Ng, M. I. Jordan, and Y. Weiss, “On spectral clustering: Analysis and an algorithm,” in _Advances in Neural Information Processing Systems 14_ , 2001, pp. 849–856.
  * [8] 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, 2015.
  * [9] 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.
  * [10] M. Hu, Y. Yang, F. Shen, L. Zhang, H. T. Shen, and L. Xuelong, “Robust web image annotation via exploring multi-facet and structural knowledge,” _IEEE Transactions on Image Processing_ , vol. 26, no. 10, pp. 4871–4884, 2017.
  * [11] Y. Yang, Z. Ma, Y. Yang, F. Nie, and H. T. Shen, “Multitask spectral clustering by exploring intertask correlation,” _IEEE Transactions on cybernetics_ , vol. 45, no. 5, pp. 1083–1094, 2015.
  * [12] F. Nie, Z. Zeng, I. W. Tsang, D. Xu, and C. Zhang, “Spectral embedded clustering: A framework for in-sample and out-of-sample spectral clustering,” _IEEE Transactions on Neural Networks_ , vol. 22, no. 11, pp. 1796–1808, 2011.
  * [13] J. Shi and J. Malik, “Normalized cuts and image segmentation,” in _Proceedings of Conference on Computer Vision and Pattern Recognition_ , 1997, pp. 731–737.
  * [14] H. Cui, L. Zhu, C. Cui, X. Nie, and H. Zhang, “Efficient weakly-supervised discrete hashing for large-scale social image retrieval,” _Pattern Recognition Letters_ , 2018, doi:https://doi.org/10.1016/j.patrec.2018.08.033.
  * [15] X. Liu, Y. Xu, L. Zhu, and Y. Mu, “A stochastic attribute grammar for robust cross-view human tracking,” _IEEE Transactions on Circuits and Systems for Video Technology_ , vol. 28, no. 10, pp. 2884–2895, 2018.
  * [16] X. Liu, Q. Xu, T. Chau, Y. Mu, L. Zhu, and S. Yan, “Revisiting jump-diffusion process for visual tracking: A reinforcement learning approach,” _IEEE Transactions on Circuits and Systems for Video Technology_ , 2018, doi:10.1109/TCSVT.2018.2862891.
  * [17] X. Lu, L. Zhu, Z. Cheng, X. Song, and H. Zhang, “Efficient discrete latent semantic hashing for scalable cross-modal retrieval,” _Signal Processing_ , vol. 154, pp. 217 – 231, 2019.
  * [18] L. Wang, L. Zhu, E. Yu, J. Sun, and H. Zhang, “Task-dependent and query-dependent subspace learning for cross-modal retrieval,” _IEEE Access_ , vol. 6, pp. 27 091–27 102, 2018.
  * [19] J. Li, K. Lu, Z. Huang, L. Zhu, and H. T. Shen, “Transfer independently together: A generalized framework for domain adaptation,” _IEEE Transactions on Cybernetics_ , 2018, doi:10.1109/TCYB.2018.2820174.
  * [20] ——, “Heterogeneous domain adaptation through progressive alignment,” _IEEE Transactions on Neural Networks and Learning Systems_ , pp. 1–11, 2018, doi:10.1109/TNNLS.2018.2868854.
  * [21] J. Li, Y. Wu, J. Zhao, and K. Lu, “Low-rank discriminant embedding for multiview learning,” _IEEE Transactions on Cybernetics_ , vol. 47, no. 11, pp. 3516–3529, 2017.
  * [22] X. Li, G. Cui, and Y. Dong, “Graph regularized non-negative low-rank matrix factorization for image clustering,” _IEEE Transactions on Cybernetics_ , vol. 47, no. 11, pp. 3840–3853, 2017.
  * [23] F. Shen, Y. Xu, L. Liu, Y. Yang, Z. Huang, and H. T. Shen, “Unsupervised deep hashing with similarity-adaptive and discrete optimization,” _IEEE Transactions on Pattern Analysis and Machine Intelligence_ , 2018, doi:10.1109/TPAMI.2018.2789887.
  * [24] F. Shen, Y. Yang, L. Liu, W. Liu, D. Tao, and H. T. Shen, “Asymmetric binary coding for image search,” _IEEE Transactions on Multimedia_ , vol. 19, no. 9, pp. 2022–2032, 2017.
  * [25] F. Shen, X. Zhou, Y. Yang, J. Song, H. T. Shen, and D. Tao, “A fast optimization method for general binary code learning,” _IEEE Transactions on Image Processing_ , vol. 25, no. 12, pp. 5610–5621, 2016.
  * [26] X. Xu, F. Shen, Y. Yang, H. T. Shen, and X. Li, “Learning discriminative binary codes for large-scale cross-modal retrieval,” _IEEE Transactions on Image Processing_ , vol. 26, no. 5, pp. 2494–2507, 2017.
  * [27] F. Nie, X. Wang, and H. Huang, “Clustering and projected clustering with adaptive neighbors,” in _Proceedings of International Conference on Knowledge Discovery and Data Mining_ , 2014, pp. 977–986.
  * [28] Y. Alavi, “The laplacian spectrum of graphs,” _Graph theory, combinatorics, and applications_ , vol. 2, no. 12, pp. 871–898, 1991.
  * [29] F. Nie, X. Wang, M. I. Jordan, and H. Huang, “The constrained laplacian rank algorithm for graph-based clustering,” in _Proceedings of AAAI Conference on Artificial Intelligence_ , 2016, pp. 1969–1976.
  * [30] L. W. Hagen and A. B. Kahng, “New spectral methods for ratio cut partitioning and clustering,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 11, no. 9, pp. 1074–1085, 1992.
  * [31] K. Fan, “On a theorem of weyl concerning eigenvalues of linear transformations i,” _Proceedings of the National Academy of Sciences of the United States of America_ , vol. 36, no. 1, pp. 652–655, 1949.
  * [32] Z. Wen and W. Yin, “A feasible method for optimization with orthogonality constraints,” _Mathematical Programming_ , vol. 142, no. 1-2, pp. 397–434, 2013.
  * [33] X. Wang, Y. Liu, F. Nie, and H. Huang, “Discriminative unsupervised dimensionality reduction,” in _Proceedings of International Joint Conference on Artificial Intelligence_ , 2015, pp. 3925–3931.
  * [34] L. V. S. Boyd, “Convex optimization,” _European Journal of Operational Research_ , vol. 170, no. 1, pp. 326–327, 2006.
  * [35] F. Nie, R. Zhang, and X. Li, “A generalized power iteration method for solving quadratic problem on the stiefel manifold,” _Information Sciences_ , vol. 60, no. 11, pp. 112 101:1–112 101:10, 2017.
  * [36] Y. Yang, Z. Zha, Y. Gao, X. Zhu, and T. Chua, “Exploiting web images for semantic video indexing via robust sample-specific loss,” _IEEE Transactions on Multimedia_ , vol. 16, no. 6, pp. 1677–1689, 2014.
  * [37] J. Huang, F. Nie, and H. Huang, “Spectral rotation versus k-means in spectral clustering,” in _Proceedings of AAAI Conference on Artificial Intelligence_ , 2013, pp. 431–437.
  * [38] F. Nie, G. Cai, J. Li, and X. Li, “Auto-weighted multi-view learning for image clustering and semi-supervised classification,” _IEEE Transactions on Image Processing_ , vol. 27, no. 3, pp. 1501–1511, 2018.
  * [39] Z. Kang, C. Peng, Q. Cheng, and Z. Xu, “Unified spectral clustering with optimal graph,” in _Proceedings of AAAI Conference on Artificial Intelligence_ , 2018, pp. 3366–3373.
  * [40] T. Li and C. H. Q. Ding, “The relationships among various nonnegative matrix factorization methods for clustering,” in _Proceedings of International Conference on Data Mining_ , 2006, pp. 362–371.
  * [41] Y. Souissi, M. Nassar, S. Guilley, J. Danger, and F. Flament, “First principal components analysis: A new side channel distinguisher,” in _Proceedings of International Conference on Information Security and Cryptology_ , 2010, pp. 407–419.
  * [42] X. He and P. Niyogi, “Locality preserving projections,” in _Advances in Neural Information Processing Systems 16_ , 2003, pp. 153–160.
  * [43] L. Zelnik-Manor and P. Perona, “Self-tuning spectral clustering,” in _Advances in Neural Information Processing Systems 17_ , 2004, pp. 1601–1608.
  * [44] J. Ye, Z. Zhao, and M. Wu, “Discriminative k-means for clustering,” in _Advances in Neural Information Processing Systems 20_ , 2007, pp. 1649–1656.
  * [45] M. Wu and B. Schölkopf, “A local learning approach for clustering,” in _Advances in Neural Information Processing Systems 19_ , 2006, pp. 1529–1536.
  * [46] F. Wang, C. Zhang, and T. Li, “Clustering with local and global regularization,” _IEEE Transactions on Knowledge and Data Engineering_ , vol. 21, no. 12, pp. 1665–1678, 2009.

|  Yudong Han is pursuing Bachelor’s degree at the School of Information
Science and Engineering, Shandong Normal University, China. He is under the
supervision of Prof. Lei Zhu (2016-). His research interest is in the area of
big data mining.
---|---
|  Lei Zhu received the B.S. degree (2009) at Wuhan University of Technology,
the Ph.D. degree (2015) at Huazhong University of Science and Technology. He
is currently a full Professor with the School of Information Science and
Engineering, Shandong Normal University, China. He was a Research Fellow at
the University of Queensland (2016-2017), and at the Singapore Management
University (2015-2016). His research interests are in the area of large-scale
multimedia content analysis and retrieval.
---|---
|  Zhiyong Cheng received the Ph.D degree in computer science from Singapore
Management University, Singapore. He is currently a full professor with
Shandong Artificial Intelligence Institute, China. He was a Research Fellow at
the National University of Singapore (2016-2018), and a visiting student with
the School of Computer Science, Carnegie Mellon University (2014-2015). His
research interests mainly focus on large-scale multimedia content analysis and
retrieval. His work has been published in a set of top forums, including ACM
SIGIR, MM, WWW, TOIS, IJCAI, TKDE, and TCYB.
---|---
|  Jingjing Li received his MSc and PhD degree in Computer Science from
University of Electronic Science and Technology of China in 2013 and 2017,
respectively. Now he is a national Postdoctoral Program for Innovative Talents
research fellow with the School of Computer Science and Engineering,
University of Electronic Science and Technology of China. He has great
interest in machine learning, especially transfer learning, subspace learning
and recommender systems.
---|---
|  Xiaobai Liu received his PhD from the Huazhong University of Science and
Technology, China. He is currently an Assistant Professor of Computer Science
in the San Diego State University (SDSU), San Diego. His research interests
focus on scene parsing with a variety of topics, e.g. joint inference for
recognition and reconstruction, commonsense reasonzing, etc. He has published
30+ peer-reviewed articles in top-tier conferences (e.g. ICCV, CVPR etc.) and
leading journals (e.g. TPAMI, TIP etc.) He received a number of awards for his
academic contribution, including the 2013 outstanding thesis award by CCF
(China Computer Federation). He is a member of IEEE.
---|---