---
abstract: 'A panoply of multi-view clustering algorithms has been developed to deal with prevalent multi-view data.  Among them, spectral clustering-based methods have drawn much attention and demonstrated promising results recently.  Despite progress, there are still two fundamental questions that stay unanswered to date.  First, how to fuse different views into one graph.  More often than not, the similarities between samples may be manifested differently by different views.  Many existing algorithms either simply take the average of multiple views or just learn a common graph.  These simple approaches fail to consider the flexible local manifold structures of all views.  Hence, the rich heterogeneous information is not fully exploited.  Second, how to learn the explicit cluster structure.  Most existing methods don’t pay attention to the quality of the graphs and perform graph learning and spectral clustering separately.  Those unreliable graphs might lead to suboptimal clustering results.  To fill these gaps, in this paper, we propose a novel multi-view spectral clustering model which performs graph fusion and spectral clustering simultaneously.  The fusion graph approximates the original graph of each individual view but maintains an explicit cluster structure.  Experiments on four widely used data sets confirm the superiority of the proposed method.' 
address:
- |
    School of Computer Science and Engineering,\
    University of Electronic Science and Technology of China,\
    Chengdu, Sichuan, 611731, China
- 'Institute of High Performance Computing, A\*STAR, Singapore.' 
author:
- Zhao Kang
- Guoxin Shi
- Shudong Huang
- Wenyu Chen
- Xiaorong Pu
- Joey Tianyi Zhou
- Zenglin Xu
bibliography:
- 'ref.bib'
title: 'Multi-graph Fusion for Multi-view Spectral Clustering'
---

Multi-view learning; spectral clustering; graph fusion

Introduction
============

With the increasing popularity of sensors and multi-camera surveillance systems, one object is often represented from multiple views [@chao2019semi; @zhu2018multi; @tang2018consensus; @ding2019multiway].  For example, a person can be uniquely identified in terms of face, fingerprint, iris, and signature; an image can be described by different kinds of descriptors: SIFT, HOG, and LBP, where SIFT is robust to image illumination, noise, and rotation, HOG is sensitive to marginal information, while LBP is a powerful texture feature; the same document can be represented in different languages.  Different views can capture distinct perspectives of data.  Numerous real-world applications have benefited from multi-view data by leveraging the complementary information [@li2017multi; @chao2017survey; @zhang2018generalized; @liu2018late; @kang2019multiple].  Thus, multi-view learning has become an important research field [@chen2013twkm; @huang2019auto]. 

As an important ingredient of multi-view learning, multi-view clustering has been widely investigated to identify underlying structures in multi-view data in an unsupervised way [@huang2018self; @wang2019study].  Although each view contains different fractional information, they together admit the same clustering structure.  Simply concatenating all features into a single view and then employing a clustering algorithm on this single view data might not obtain better performance than traditional methods which use single view separately [@zhan2018adaptive; @huang2019auto]. 

In the past decade, plenty of advanced multi-view clustering algorithms have been proposed and they perform effectively by considering the diversity and complementarity of different views.  According to the mechanisms on which those methods are based, we can roughly divide them into five categories: co-training style methods [@kumar2011cotrain; @kumar2011co; @tao2018reliable]; multi-kernel learning [@liu2017multiple; @tzortzis2012kernel; @guo2014multiple]; multi-view graph clustering [@wang2016iterative; @cao2015diversity; @gao2015multi; @zhan2017graph; @wang2017exclusivity; @zhang2019multitask]; multi-view subspace clustering [@liu2013multi; @guo2013convex; @xu2017re; @liu2018consensus]; multi-task multi-view clustering [@zhang2015multi; @gu2009learning]. 

Among these methods, spectral clustering based multi-view algorithms often report satisfying results. [ @kumar2011cotrain] proposed a co-training approach to search for the clustering that agree across the views.  In this approach, the eigenvectors obtained from one view are used to update the graph of the other view. [ @kumar2011co] further developed a co-regularized method to look for clustering that are consistent across the views, where the eigenvectors of all views are regularized.  Despite their popularity, a common drawback shared by these two methods is that their performance heavily depends on the input graph.  It is well-known that small perturbations in the entries of the graph may lead to large perturbations in the eigenvectors, thus leads to inferior clustering accuracy [@hunter2010performance; @zhao2015automatic; @robust2019kang; @ding2018semi].  Therefore, constructing an accurate graph is highly desired. 

To this end, a number of graph learning based clustering methods have been proposed recently [@kang2017twin; @zhang2013graph; @kang2019low].  They seek to learn graph from data dynamically.  This approach enjoys several nice properties, such as robustness to noise and outliers, independence of similarity metrics.  For example, Nie et al.  constructed the graph based on adaptive neighbors [@nie2014clustering], i.e., the probability of one data point being the neighbor of another point is treated as a measure of the similarity between them.  Afterwards, many researchers extended this idea to deal with multi-view data. [ @nie2016parameter] reformulated the standard spectral clustering model and put forth a parameter-free multi-view clustering method.  This algorithm assumes that all graphs share a common eigenvector.  Additionally, this approach takes graph construction and spectral clustering as two separate procedures.  As a result, they are not jointly optimized.  To solve this problem, [@nie2017multi] further developed a unified framework which performs graph learning and spectral clustering simultaneously.  However, in this approach, only a common graph is learned based on adaptive neighbors.  Consequently, it fails to preserve the flexible local manifold structures for all views which leads to suboptimal clustering performance [@wang2016iterative].  In addition, one significant limitation of adaptive neighbors-based graph learning is that it can only capture the intrinsic local structure information of the data. 

On the other hand, subspace clustering method has the capability to explore global low-dimensional manifold structure encoded by the data correlations embedded in high-dimensional space [@peng2017deep; @chen2012fgkm; @kang2017kernel; @zhang2016joint; @li2015robust].  It’s based on the self-expressiveness property which assumes that each sample can be linearly represented by the other ones.  This representation coefficient matrix $Z$ behaves like the similarity graph matrix [@zhang2017latent; @xia2014robust; @kang2019Clustering; @zhang2019robust].  Two widely used assumptions about $Z$ are low-rank [@liu2013robust] and sparse [@elhamifar2013sparse].  After obtaining the graph, the final clustering result is generated by the spectral clustering algorithm [@ng2002spectral; @chen2018dnc].  Based on this strategy, varieties of multi-view clustering methods have been proposed. 

Gao et al. [ @gao2015multi] proposed multi-view subspace clustering algorithm.  It learns a graph for each view and enforces a common cluster indicator matrix for all graphs.  Thus, the clustering result is consistent for all views.  However, this assumption is too strong since the common cluster indicator matrix must negotiate with all graphs.  Consequently, the resulted solution might not be optimal. [ @cao2015diversity] focused on boosting the multi-view clustering by exploring the complementarity of multi-view representations.  In specific, they utilize the Hilbert Schmidt Independence Criterion (HSIC) to capture the diversity information.  As a result, multiple graphs are built and their average is used as input for spectral clustering.  This simple post-processing strategy treats all views equally, which might result in inferior performance.  Wang et al. [ @wang2016iterative] developed a low-rank based multi-view spectral clustering method.  Though they added a term to characterize the agreement among the graph, they still used the average of graphs for spectral clustering.  This two-step approach might cause unsatisfied results since the averaged graph might not be optimal for subsequent clustering task. 

![ Illustration of our GFSC approach.  GFSC integrates graph learning, graph fusion, and spectral clustering into a unified framework.  The clustering result is further utilized to guide the graph construction and fusion, which in turn contributes to a better clustering. []{ data-label="flowgraph"}](flowgraph){width=".98\textwidth"}

Despite these progresses, multi-view spectral clustering still arguably faces the following fundamental limitations.  First, how to effectively fuse the graphs from all views.  Integrating graphs is not trivial since exploration of complementary information of multiple views is the core of multi-view learning [@gao2015multi].  Simply taking the average of them fails to consider the discriminative property of views.  In many situations, the similarities between samples may be manifested differently by different views.  For instance, two video clips that present the same content but in different languages, their audio content will be different.  Second, how to consider the explicit cluster structure.  It is widely accepted that the clustering results highly depend on the quality of the affinity graph.  Many existing methods implement graph construction and spectral clustering separately.  Thus, the learned graph might not be ideal for subsequent clustering. 

To solve the above challenging problems, we propose a novel multi-view spectral clustering method which performs graph fusion and spectral clustering simultaneously.  Fig.  \[flowgraph\] shows the idea of our approach.  The fusion graph approximates the original graph of each individual view but maintains an explicit cluster structure.  Experiments on four widely used data sets confirm the superiority of the proposed method.  The contributions of this paper are summarized in the following two aspects:

-   A novel graph fusion mechanism is proposed to integrate the multi-view information.  It is based on two basic principles: 1) the graph of each view is a perturbation of the consensus graph, and 2) graph that is close to the consensus graph should be assigned a large weight.  The graphs are weighted dynamically during the fusion process so that the adversary effect of noise graphs is reduced effectively. 

-   The cluster structure of the consensus graph is further considered.  As a result, an optimal graph, which has exactly $k$ connected components if there are $k$ clusters, can be readily achieved for clustering.  The experimental results confirm its superiority compared to state-of-the-art methods. 

**Notation.**  In this paper, matrices are represented by capital letters and vectors are denoted by lower case letters.  For an arbitrary matrix $X\in \mathbb{R}^{m\times n}$, its Frobenius norm is $\|X\|_F=\sqrt{\sum_{i=1}^m\sum_{j=1}^n X_{ij}^2}$. The $\ell_2$-norm of vector $x$ is represented by $\|x\|=\sqrt{x^T \cdot x}$, where $T$ means transpose.  $Tr(X)$ denotes the trace of $X$. $X\geq 0$ means that all elements of $X$ are nonnegative.  $I$ is the identity matrix with a proper size. 

Multi-view Spectral Clustering Revisited
========================================

Let $X=\{X^1, X^2, \cdots, X^t\}$ denote the multi-view data with $t$ views.  $X^v\in\mathbb{R}^{m_v\times n}(v=1,\cdots,t)$ is the data matrix of view $v$, $m_v$ is the dimension of features in the $v$-th view, and $n$ is the number of samples.  Given the adjacent matrix $Z^v\geq 0$ of each view, the graph Laplacian matrix $L^v=D^v-Z^v$, where diagonal matrix $D^v$ is the degree matrix with $d_{ii}^v=\sum_{j=1}^n z_{ij}^v$. Assuming that the cluster indicator matrix $F\in\mathbb{R}^{n\times k}$ is the same across all the views, we can formulate the multi-view spectral clustering problem as [@gao2015multi] $$\min_{F,F^TF=I} \sum\limits_{v=1}^t Tr(F^TL^vF),$$ where each graph contributes equally to the final result $F$. In above equation, we ignore the details about the graph construction.  Instead of enforcing multiple graphs share the same $F$, several other works simply take the average of graphs and then implement the spectral clustering separately [@cao2015diversity; @wang2016iterative].  Consequently, the complementary information is not fully exploited since each view is not distinguished from the others.  Furthermore, the graphs from different views might differ a lot.  It is unrealistic for them to achieve an agreement $F$. Thus, these approaches will lead to inferior clustering result.  Some researchers try a linear combination of those graphs [@li2015large].  However, the complementary information from multi-view data is not necessarily linearly related.  In addition, this linear combination is also sensitive to the weights assigned to each graph.  To fill this gap, in this paper, we propose a strategy to integrate the graphs. 

Even if we can achieve a high-quality graph based on our graph fusion principle, we are still unsure whether the graph is suitable for the subsequent clustering task at hand.  Ideally, the optimal graph should have an exactly $k$ number of components so that vertices in each connected component of the graph are grouped into the same one cluster.  Hence, we go further and incorporate the cluster structure of the consensus graph. 

Proposed Multi-graph Fusion for Multi-view Spectral Clustering
==============================================================

Self-expressiveness based Graph Learning
----------------------------------------

Self-expressiveness property states that each data sample can be expressed as a linear combination of other samples.  This combination coefficient indicates the similarities between samples [@vidal2011subspace; @liu2013robust].  This similarity graph $Z$ can be obtained by solving $$\min_Z \|X-XZ\|_F^2+\alpha \|Z\|_F^2 \quad s.t.  \quad Z\geq 0,
\label{single}$$ where $\alpha$ is a trade-off parameter.  It can be easily extended to multi-view data, i.e., $$\min_{Z^v} \sum\limits_{v=1}^t \|X^v-X^vZ^v\|_F^2+\alpha \|Z^v\|_F^2 \quad s.t.  \quad Z^v\geq 0,
\label{multi}$$ where the same trade-off parameter is often adopted for simplicity.  Different graphs capture different aspects of the multi-view data.  Then the average of these graphs is often used to achieve the final clustering result [@cao2015diversity; @wang2016iterative].  That is to say, the consensus graph $S$, $$S=\frac{\sum\limits_{v=1}^t Z^v}{t},$$ is taken as the input for spectral clustering algorithm [@ng2002spectral].  It is obvious that this approach fails to distinguish the different contributions of different views.  More often than not, some views containing irrelevant or noisy representation might severely damage the graphs and lead to degraded performance.  To recap the powerfulness of the complementarity nature of multi-view data, we propose a way to aggregate these basic graphs to form a consensus graph $S$.

Graph Fusion
------------

Our proposed graph fusion method is based on two intuitive assumptions: 1) the graph $Z^v$ of each view is a perturbation of the consensus graph $S$, and 2) the graph that is close to the consensus graph should be assigned a large weight.  The consensus graph $S$ is supposed to capture the ground-truth sample similarity hidden in the multi-view data.  To avoid the influence of low quality (noisy) views, we try to assign different weights to different graphs.  As a result, we can reach a better clustering performance based on $S$ than that of $Z^v$.

Based on above principles, our graph fusion mechanism can be formulated as $$\sum\limits_{v=1}^t w_v\|Z^v-S\|_F^2,
\label{fuse}$$ where the weight $w_v$ characterizes the importance of view $v$. We can simply adopt the inverse distance weighting scheme [@nie2016parameter; @nie2017self], i.e., $$w_v=\frac{1}{2\|Z^v-S\|_F}. 
\label{weightw}$$ Since $S$ is unknown beforehand, we can calculate it approximately based on an iterative approach.  Then we combine Eq. ( \[fuse\]) and (\[multi\]).  It yields $$\begin{split}
\min_{Z^v,S}& \sum\limits_{v=1}^t \|X^v-X^vZ^v\|_F^2+\alpha \|Z^v\|_F^2+\beta w_v\|Z^v-S\|_F^2 \\
& s.t.  \quad Z^v\geq 0,
\label{firstobj}
\end{split}$$ Through solving this problem, we can obtain both the graph for each view and the consensus graph adaptively.  Additionally, the graphs are weighted dynamically during the fusion process so that the adversary effect of noise graphs is reduced effectively.  Although we can directly implement spectral clustering based $S$, we move forward and consider the cluster structure of it since the current graph $S$ might not be optimal for the subsequent clustering task. 

Structured Graph Learning 
--------------------------

Ideally, the solution $S$ of problem (\[firstobj\]) should have exact $k$ connected components, i.e., the data points are already clustered into $k$ clusters.  However, the current solution can hardly satisfy to such a condition.  This can be fulfilled based on the following theorem [@mohar1991laplacian]:

The number of connected components $k$ of the graph $S$ is equal to the multiplicity of zero eigenvalues of its Laplacian matrix $L$.

Since $L$ is a positive semi-definite matrix, its eigenvalues $\sigma_n\geq \cdots\geq\sigma_2\geq \sigma_1\geq0$. Theorem 1 means that if $\sum_{i=1}^k \sigma_i=0$, then our expectation can be approximately satisfied.  Hence, we can minimize $\sum_{i=1}^k \sigma_i$ instead to satisfy the requirement.  According to Ky Fan’s theorem [@fan1949theorem], we can obtain an objective function $$\sum\limits_{i=1}^k \sigma_i=\min_{F,F^TF=I} Tr(F^TLF). 
\label{fan}$$ The right part of this equation is nothing but the objective function of spectral clustering.  Hence, Eq. ( \[fan\]) establishes the connection between our requirement for the graph structure and spectral clustering. 

Minimizing Eq. ( \[fan\]), we can approximately guarantee the structure of graph $S$. Therefore, we can combine Eqs. ( \[fan\]) and (\[firstobj\]) to a single objective function, which fulfills the tasks of graph learning, graph fusion, and spectral clustering.  Consequently, our proposed multi-Graph Fusion for multi-view Spectral Clustering (GFSC) can be formulated as $$\begin{split}
\min_{Z^v,S,F}& \sum\limits_{v=1}^t \{\|X^v-X^vZ^v\|_F^2+\alpha \|Z^v\|_F^2+\beta w_v\|Z^v-S\|_F^2\}\\
&+\gamma Tr(F^TLF) \quad s.t.  \quad Z^v\geq 0,\quad F^TF=I,
\label{obj}
\end{split}$$ where $\alpha$, $\beta$, and $\gamma$ are regularization parameters.  The objective function (\[obj\]) enjoys the following properties:

-   [The last term in Eq. ( \[obj\]) functions as a regularizer on graph $S$. We tune the structure of $S$ adaptively so that we achieve the optimal condition.  At the same time, it seamlessly integrates the graph construction and spectral clustering processes. ]{} 

-   [For this multi-view spectral clustering method, the graph is automatically learned from the data rather than pre-defined as in most existing spectral clustering methods.  This results in a reliable and robust graph. ]{} 

-   [The graph fusion term seeks to find the underlying relationships between samples.  Rather than treating each view equally, weight $w_v$ can well distinguish the different contributions of different views.  Consequently, the complementary information of heterogeneous data is more effectively explored.]{} 

-   [In this joint framework, the high-quality clustering result is utilized to guide the graph construction, which is then used to obtain a new clustering.  This mutually improving approach can boost the final clustering result. ]{} 

Optimization of Problem (\[obj\])
=================================

The variables in Eq. ( \[obj\]) are coupled to each other.  We can solve them utilizing an alternating iterative strategy. 

**Solving $Z^v$ when $F$ and $S$ are fixed**.  The problem (\[obj\]) becomes $$\min_{Z^v} \sum\limits_{v=1}^t \{\|X^v-X^vZ^v\|_F^2+\alpha \|Z^v\|_F^2+\beta w_v\|Z^v-S\|_F^2\}. 
\label{subz}$$ We can observe that Eq. ( \[subz\]) is independent for each view.  Thus, we can update $Z^v$ separately for each view.  Taking the derivative of Eq. ( \[subz\]) w.r.t.  $Z^v$, we have $$-2(X^v)^T(X^v-X^vZ^v)+2\alpha Z^v+2\beta w_v(Z^v-S\|_F^2).$$ Setting above formula to zero, we obtain $$Z^v=\left((X^v)^TX^v+\alpha I+\beta w_v I\right)^{-1}\left(\beta w_v S+(X^v)^TX^v\right). 
\label{solvez}$$ **Solving $S$ when $F$ and $Z^v$ are fixed**.  Remembering that $L$ is a function of $S$, thus we obtain $$\min_S \sum\limits_{v=1}^t \beta w_v\|Z^v-S\|_F^2+\gamma Tr(F^TLF). 
\label{objs}$$ To solve this subproblem, we use equality $$\sum\limits_{i,j}\frac{1}{2}\|F_{i,:}-F_{j,:}\|^2 s_{ij}=Tr(F^TLF)$$ and define $p_i\in\mathbb{R}^{n\times 1}$ with the $j$-th entry $p_{ij}=\|F_{i,:}-F_{j,:}\|^2$. Then problem (\[objs\]) can be solved column-wisely $$\min_{S(:,i)} \sum\limits_{v=1}^t \beta w_v\|Z(:,i)^v-S(:,i)\|^2+\frac{\gamma}{2} p_i^TS(:,i).$$ Its derivative w.r.t.  $S(:,i)$ is $-2\beta \sum_v w_v(Z(:,i)^v-S(:,i))+\frac{\gamma}{2} p_i$, which should be zero.  It yields $$S(:,i)=\frac{\sum_v w_vZ^v(:,i)-\frac{\gamma p_i}{4\beta}}{\sum_v w_v}. 
\label{solves}$$ **Solving $F$ when $Z^v$ and $S$ are fixed**.  It yields $$\min_F Tr(F^TLF)\quad s.t.\quad F^TF=I.
\label{solvef}$$ The optimal solution of $F$ is obtained by the $k$ eigenvectors of $L$ corresponding to the $k$ smallest eigenvalues. 

The details of solving the problem in Eq. ( \[obj\]) is summarized in Algorithm 1.  We stop our algorithm if the maximum iteration number 200 is reached or the relative change of $S$ is less than $10^{-3}$. The complete implementation package is available [^1]. 

Computational Analysis
----------------------

The main computation demand of Algorithm 1 is due to the update of $Z^v$ and $F$. Specifically, updating $Z^v$ costs about $O(n^3)$ due to the matrix inversion and multiplication.  The complexity of updating $F$ is also $O(n^3)$ due to the employment of SVD operation.  To make our algorithm more efficient, several off-the-shell acceleration algorithms could be utilized, e.g., skinny SVD [@zhang2014fast], sampling-based methods [@zhang2016sampling; @xu2018improved; @jia2017nystrom].  In our experiments, we don’t apply these acceleration techniques. 

[**Input:**]{} Data matrices: $X^1,\cdots, X^t$, parameters $\alpha>0$, $\beta>0$, $\gamma>0$.\
[**Output:**]{} $Z^1,\cdots, Z^t$, $S$, $F$.\
[**Initialize:**]{} Random matrices $S$ and $F$, $w_v=1/t$.\
[**REPEAT**]{}

Update $Z^v$ according to Eq. ( \[solvez\]) for each view.  For each element $Z_{ij}^v=max(Z_{ij}^v, 0)$. Update $S$ according to Eq. ( \[solves\]).  Update $F$ by solving the problem (\[solvef\]).  Update $w_v$ according to (\[weightw\]). 

**UNTIL** [stopping criterion is met.]{} 

Experiments
===========

Data Set Descriptions
---------------------

We employ four widely used multi-view data sets for performance evaluation, namely BBC, Reuters[^2], Digits, Caltech20[^3].  Among them, BBC and Reuters are text data sets; Digits and Caltech20 are image data.  In these cases, $Z^v$ represents the similarity between different documents or images.  Table \[data\] shows the concrete information of the data sets.  According to [@cai2013multi], we normalize the data sets so that all the values of each view are in the range \[-1, 1\]. 

Evaluation Metrics
------------------

We evaluate the performance using three popular metrics: accuracy (Acc), normalized mutual information (NMI), purity [@peng2018integrate]. 

-   [**Accuracy (Acc).**  Accuracy is applied to find the one-to-one relationship between clusters and classes and evaluates how many data points are contained in each cluster that are from the corresponding class.  It is the summation of the whole matching degree between all pair class-clusters.  $$Acc=\frac{1}{n}\text{max}(\sum\limits_{X_i,Y_j}N(X_i,Y_j)),$$ where $X_i$ represents the $i$-th cluster, $Y_j$ denotes the $j$-th class, and $N(X_i,Y_j)$ denotes the number of points that are assigned to cluster $i$ but belongs to class $j$. Accuracy is defined as the maximum sum of $N(X_i,X_j)$ over all pairs of clusters and classes. ]{} 

-   [**Normalized Mutual Information (NMI).**  Let $X$ and $Y$ be two random variables, $H(X)$ and $H(Y)$ are their corresponding entropies.  Then the NMI is defined as $$NMI(X,Y)=\frac{I(X,Y)}{\sqrt{H(X)H(Y)}},$$ where ${I(X,Y)}$ denotes the mutual information between $X$ and $Y$. Higher value indicates better performance. ]{} 

-   [**Purity.**  Purity is defined as the percent of the total number of points that are classified correctly.  Then, $$Purity=\frac{1}{n}\sum\limits_{i=1}^{k}\text{max}|g_i\cap t_j|,$$ where $g_i$ denotes a cluster and $t_j$ represents the classification that has the maximum count for cluster $g_i$. .]{} 

Comparison Algorithms
---------------------

We compare with both single view and multi-view clustering algorithms. 

-   [Spectral clustering (**SC**) [@ng2002spectral]]{}: We include the classic SC method as baseline method.  We apply SC on each view of features.  SC(1) means the implementation of SC on the 1st view.  SC(Ave) means that the result is based on the average graph of views.  Note that all graphs are learned from data according to Eq. ( \[single\]). 

-   [K-means clustering (**KM**): We conduct KM on the concatenated features.  That is to say, we assume that all the views are of the same importance to the clustering task. ]{} 

-   [Co-training multi-view spectral clustering (**Co-train**) [@kumar2011cotrain]: It utilizes the eigenvector from one view to guide the graph construction in another view.  Consequently, the clusterings of multiple views tend towards consensus.]{} 

-   [Co-regularized multi-view spectral clustering (**Co-reg**) [@kumar2011co]: This method employs co-regularization technique to make the clusterings in different views agree with each other.]{} 

-   [Multi-view kernel K-means (**MVKKM**) [@tzortzis2012kernel]: This method transforms each view into a kernel matrix and learns a weighted combination of kernels.  At the same time, kernel k-means algorithm is applied to obtain the final result.]{} 

-   [Robust multi-view K-means clustering (**RMKMC**) [@cai2013multi]: It adopts $\ell_{21}$-norm in traditional k-means algorithm to deal with data outliers.  In addition, a weight factor is introduced for each view. ]{} 

-   [Multi-view clustering with self-paced learning (**MSPL**) [@xu2015multi]: This method applies the self-paced learning strategy to multi-view clustering.  Hence the multi-view model is learned from easy to complex examples/views which are determined by a probabilistic smoother weighting scheme.]{} 

-   [Auto-weighted multiple graph learning (**AMGL**) [@nie2016parameter]: It extends the spectral clustering method to multi-view situation.  Different from our approach, the graphs are learned by adaptive neighbors approach. ]{} 

-   [Multi-view subspace clustering (**MVSC**) [@gao2015multi]: Multiple graphs are learned and they share the same cluster indicator matrix.  Unlike our approach, there is no graph fusion process.]{} 

-   [Diversity-induced multi-view subspace clustering (**DiMSC**) [@cao2015diversity]: Multiple graphs are learned and their average is inputted to the spectral clustering algorithm.  Moreover, the Hilbert Schmidt Independence Criterion (HSIC) is incorporated as a diversity regularizer to explore the complementarity of multiple views.]{} 

-   [Iterative based multi-view spectral clustering (**IMVSC**) [@wang2016iterative]: This method learns multiple graphs and each one is assumed to be low-rank and sparse.  In addition, Laplacian regularization and views agreement are imposed on the graphs.  Finally, the average of learned graphs is used for spectral clustering. ]{} 

-   [Our proposed **GFSC**.  Both graph fusion and graph structure are considered in our approach.  After obtaining $F$, we implement K-means on it to obtain the final discrete cluster labels.  Furthermore, to see the effect of graph structure, we also compare with the approach based on problem (\[firstobj\]) referred as **GF**.  Unlike GFSC in problem (\[obj\]), we implement the spectral clustering method separately after obtaining $S$ in GF. ]{} 

Results
-------

For those methods with parameters, we tune them to achieve the best performance.  For example, the range for our method is displayed in Figure \[sensitivity\].  We repeat each algorithm 10 times and report their mean and standard deviation (std) values in Tables \[bbc\]-\[caltech\].  The best results are marked in boldface.  According to these results, we can draw the following conclusions. 

-   [Comparing the SC performance on different views, we can see that different views indeed produce different results.  This confirms the heterogeneity of multiple views.  Therefore, it is essential to differentiate views when we build a multi-view learning model, just as we do in this paper.]{} 

-   [Comparing SC(Ave) with each individual view results, we can see that naively taking the average of graphs might deteriorate the performance.  In order to obtain reliable results, it is eager to design a graph fusion mechanism. ]{} 

-   [With respect to SCs and SC(Ave), our proposed GFSC method often shows better performance.  This is largely due to the fact that a more accurate graph is learned in our approach.  Remember that we employ both graph fusion and weighting strategy in our model.]{} 

-   [GFSC always performs better than GF.  This fully demonstrates the importance of considering the graph structure.  Additionally, GF often outperforms SC(Ave).  This shows the advantage of graph fusion. ]{} 

-   [Our GFSC method consistently outperforms k-means based multi-view methods, i.e., KM, MVKKM, RMKMC, MSPL.  This validates the superiority of spectral clustering method.  It is well-known that spectral clustering often performs better than k-means technique.]{} 

-   [In addition, GFSC consistently performs better than AMGL.  AMGL is based on adaptive neighbors which captures the local structure of data.  By contrast, our graph learning is based on self-expressiveness which is supposed to grasp the global structure of data. ]{} 

-   [Our method significantly outperforms classic multi-view methods Co-train and Co-reg.  Co-train and Co-reg methods construct graphs manually and they mainly regularize the multiple partitions. ]{} 

-   [Compared to state-of-the-art multi-view subspace clustering algorithms, i.e., DiMSC, MVSC, and IMVSC, our method beats them in most cases in terms of Acc, NMI, and Purity.  Though they build the graphs in a similar way as ours, they don’t use any graph fusion strategy.  This fully demonstrates the efficacy of our graph fusion. ]{} 

In summary, these observations validate the efficacy of our graph fusion and graph structure learning strategies. 

\[bbc\]

Parameter Analysis
------------------

In our proposed model, there are three parameters $\alpha$, $\beta$, and $\gamma$ that need to be set properly.  We choose their values by grid searching.  Figures \[bbc\]-\[caltech\] show the range for each dataset and the sensitivity of the accuracy with regard to the parameters.  As can be seen, the optimal parameters are $\{10^{-7},10^{7},10^{-5}\}$, $\{10, 10^{3}, 0.01\}$,$\{10^{-4},1,10^{-4}\}$,$\{10^{-7},0.1,10^{-7}\}$ for BBC, Reuters, Digits, Caltech20, respectively.  Overall, our method performs stably to some extent w.r.t.  a wide range of parameter values. 

Conclusion
==========

In this paper, we proposed a novel multi-view spectral clustering method.  Unlike many existing methods, which often use averaged graph to perform spectral clustering, we propose a way to fuse graphs to achieve a consensus graph.  A parameter-free weighting scheme is introduced to distinguish the contributions of different graphs.  Moreover, the cluster structure of the consensus graph is also considered in the proposed method.  Consequently, the proposed approach integrates graph learning, fusion, and spectral clustering into a unified framework.  These three subtasks are mutually boosted based on an alternating iterative optimization strategy.  Experiments on benchmark data sets verify the effectiveness of the proposed methods.  The results show that both the consensus graph and the graph structure help improve the clustering quality. 

Acknowledgement
===============

This paper was in part supported by Grants from the Natural Science Foundation of China (Nos.  61806045, 61572111, and 61772115), two Fundamental Research Fund for the Central Universities of China (Nos.  ZYGX2017KYQD177 and A03017023701012), and a 985 Project of UESTC (No.  A1098531023601041). 

References
==========

[^1]: https://github.com/sckangz/GFSC

[^2]: http://archive.ics.uci.edu/ml/datasets.html

[^3]: http://www.vision.caltech.edu/Image Datasets/Caltech101/
