# Efficient Multi-View Graph Clustering with Local and Global Structure
Preservation

Yi Wen<EMAIL_ADDRESS>,  Suyuan Liu<EMAIL_ADDRESS>National
University of Defense TechnologyChangshaChina ,  Xinhang Wan
<EMAIL_ADDRESS>National University of Defense TechnologyChangshaChina
,  Siwei Wang<EMAIL_ADDRESS>Intelligent Game and Decision
LabBeijingChina ,  Ke Liang<EMAIL_ADDRESS>National University of
Defense TechnologyChangshaChina ,  Xinwang Liu<EMAIL_ADDRESS>National University of Defense TechnologyChangshaChina ,  Xihong Yang
<EMAIL_ADDRESS>and  Pei Zhang<EMAIL_ADDRESS>National University of
Defense TechnologyChangshaChina

(2023)

###### Abstract.

Anchor-based multi-view graph clustering (AMVGC) has received abundant
attention owing to its high efficiency and the capability to capture
complementary structural information across multiple views. Intuitively, a
high-quality anchor graph plays an essential role in the success of AMVGC.
However, the existing AMVGC methods only consider single-structure
information, i.e., local or global structure, which provides insufficient
information for the learning task. To be specific, the over-scattered global
structure leads to learned anchors failing to depict the cluster partition
well. In contrast, the local structure with an improper similarity measure
results in potentially inaccurate anchor assignment, ultimately leading to
sub-optimal clustering performance. To tackle the issue, we propose a novel
anchor-based multi-view graph clustering framework termed Efficient Multi-View
Graph Clustering with Local and Global Structure Preservation (EMVGC-LG).
Specifically, a unified framework with a theoretical guarantee is designed to
capture local and global information. Besides, EMVGC-LG jointly optimizes
anchor construction and graph learning to enhance the clustering quality. In
addition, EMVGC-LG inherits the linear complexity of existing AMVGC methods
respecting the sample number, which is time-economical and scales well with
the data size. Extensive experiments demonstrate the effectiveness and
efficiency of our proposed method.

multi-view graph clustering; large-scale clustering

††journalyear: 2023††copyright: acmlicensed††conference: Proceedings of the
31st ACM International Conference on Multimedia; October 29–November 3, 2023;
Ottawa, ON, Canada.††booktitle: Proceedings of the 31st ACM International
Conference on Multimedia (MM ’23), October 29–November 3, 2023, Ottawa, ON,
Canada††price: 15.00††isbn: 979-8-4007-0108-5/23/10††doi:
10.1145/3581783.3611986††submissionid: 1308††ccs: Computing methodologies
Cluster analysis††ccs: Theory of computation Unsupervised learning and
clustering

##  1\. INTRODUCTION

With the advent of the information society, data are usually extracted from
multiple sensors in real-world applications (Xu et al., 2022; Li et al., 2018;
Wang, 2021; Liang et al., 2022, 2023; Li et al., 2022b; Zhang et al., 2022).
Take the video for example, a clip could be decomposed into the picture, sound
records, and text descriptions, which are obtained from a camera, microphone,
and producer, respectively (Wan et al., 2022; Liu et al., 2023b; Wan et al.,
2023a). Regarding each modality as a view, how to effectively integrate
information from different views has turned out to be an essential task in
multi-view scenarios (Wan et al., 2023b, c; Xu et al., 2023). Multi-view graph
clustering (MVGC), as the classical unsupervised multi-view methods (Huang et
al., 2019a; Wang et al., 2015b; Zhang et al., 2018a; Liu et al., 2023c, a, e,
2022c), which can uncover the intrinsic structure of data pairs, is widely
adopted in data mining and knowledge discovery (Chen et al., 2022; Nie et al.,
2011, 2020). In general, MVGC methods achieve desirable achievement with two
essential processes (Zhang et al., 2020), i.e., view-specific graph
construction, and the consensus graph fusion. For instance, Li et al. (Li et
al., 2019) construct the fused latent representations with structural
information fusion from different views in a weighted manner.

Despite abundant MVGC algorithms proposed in recent years, most of them suffer
the cubic computational overhead $\mathcal{O}(n^{3})$ and quadratic space
overhead $\mathcal{O}(n^{2})$ due to the full graph construction and
decomposition (Wen et al., 2020; Kang et al., 2021; Wen et al., 2021a), which
hinder their application on large-scale scenarios. As a result, anchor-based
multi-view graph clustering (AMVGC), which selects typical anchors to denote
the whole data, is proposed to enhance the algorithm’s efficiency. For
instance, Li et al. (Li et al., 2015) propose an innovative anchor-based
multi-view clustering method by fusing the local structure and diverse
features. Shi et al. (Shi et al., 2021) generate the indicator matrix by an
integrated framework that unifies the anchor graph learning and structure
rotation.

Two basic structures, i.e., global and local structures, both play crucial
roles in numerous AMVGC studies. As shown in Figure 1 (right), the global
structure, which captures the relationship between samples and all anchors,
usually has a dense correspondence matrix. Meanwhile, the matrix with local
structure is always blocky (with an appropriate permutation) owing to only the
relationship between samples and one anchor with high similarity being
considered. However, the over-scattered global structure leads to learned
anchors failing to depict the cluster partition well, while the local
structure with an improper similarity measure results in potentially
inaccurate anchor assignment. A natural question is whether combining the two
structures leads to a better method (Liu et al., 2022b). The effectiveness of
similar thought is demonstrated by other studies in vision (Wu et al., 2021)
and language (Wu et al., 2020; Peng et al., 2022) tasks. Nonetheless, it is
non-trivial to incorporate global and local structures in the MVC field due to
the objective equation inconsistency. One pioneer work, (He and Niyogi, 2003)
merged global and local structures to learn the similarity of the original
data on the kernel space in a single view case. However, their high time
expenditure and single-view scenario limit the scalability of the method. To
the best of our knowledge, no generalized framework with global and local
structure preservation has been proposed in the field of AMVGC. Besides,
existing anchor selection usually uses a heuristic sampling strategy and is
separated from the graph learning phase, resulting in the clustering
performance dependent on the quality of anchor initialization. For instance,
Kang et al. (Kang et al., 2020b) generate fixed anchors in each view by
k-means and average the generated anchor graphs into the fusion graph. Because
of the randomness and inflexibility of the k-means and sampling strategy,
their clustering performance usually exhibits poor stability.

Figure 1. Two types of the anchor graph: local (left) and global (right). The
two types of information often have strong patterns: blocky and dense.
$\mathcal{G}_{LA}$ and $\mathcal{M}_{LA}$ denote the visualization and matrix
of local anchor graph. $\mathcal{G}_{GA}$ and $\mathcal{M}_{GA}$ denote the
visualization and matrix of global anchor graph.

To tackle these problems, we design a novel anchor-based multi-view graph
clustering framework termed Efficient Multi-View Graph Clustering with Local
and Global Structure Preservation (EMVGC-LG). Specifically, a unified
framework with a theoretical guarantee is designed to capture local and global
information. Besides, EMVGC-LG jointly optimizes anchor construction and graph
learning to enhance the clustering quality. Moreover, we theoretically prove
that the proposed paradigm with a global structure can well approximate the
local information. In addition, EMVGC-LG inherits the linear complexity of
existing AMVGC methods respecting the sample number, which is time-economical
and scales well with the data size. Meanwhile, a two-step iterative and
convergent optimization algorithm is designed in this paper. We summarize the
contributions of this paper as follows:

  * •

We design an anchor graph learning framework termed Efficient Multi-View Graph
Clustering with Local and Global Structure Preservation (EMVGC-LG). With the
proven properties, the proposed anchor graph paradigm can not only capture the
global structure between data but also well approximate the local structure.

  * •

In contrast to existing sampling or fixed anchors, the anchor learning and
graph fusion processes are jointly optimized in our framework to enhance the
clustering quality.

  * •

Extensive experiments on ten benchmark datasets demonstrate the effectiveness
and efficiency of our proposed method.

##  2\. Related Work

In this section, we present recent research regarding our work, comprising
multi-view graph clustering (MVGC) and anchor-based multi-view graph
clustering (AMVGC).

###  2.1. Multi-View Graph Clustering

With the given dataset
$\\{\mathbf{X}^{(p)}\\}_{p=1}^{v}\in\mathbb{R}^{d_{p}\times n}$ consisting of
$n$ samples from $v$ views, the representative multi-view graph clustering
(MVGC) model can express as follows:

$\displaystyle\min_{\mathbf{S}^{(p)},\mathbf{S}}\sum_{p=1}^{v}\
\left\|\mathbf{X}^{(p)}-\mathbf{X}^{(p)}\mathbf{S}^{(p)}\right\|_{F}^{2}+\mu\mathcal{L}\left(\mathbf{S}^{(p)},\mathbf{S}\right),$
$\displaystyle\text{ s.t.
}\left\\{\begin{array}[]{l}\operatorname{diag}\left(\mathbf{S}^{(p)}\right)=\mathbf{0},\mathbf{S}^{(p)\top}\mathbf{1}_{n}=\mathbf{1}_{n},\mathbf{S}^{(p)}\geq\mathbf{0},\\\
\operatorname{diag}(\mathbf{S})=\mathbf{0},\mathbf{S}^{\top}\mathbf{1}_{n}=\mathbf{1}_{n},\mathbf{S}\geq\mathbf{0},\end{array}\right.$

where the first term denotes the data self-representation matrix learning
module, and the second term represents the structure integration process
performed in $\\{\mathbf{S}^{(p)}\\}_{p=1}^{v}$ to generate a common
$\mathbf{S},\mu$ represents a trade-off parameter, $\mathcal{L}$ is the
regularization term. After obtaining the fused global graph $\mathbf{S}$, we
need to obtain the spectral embedding $\mathbf{F}\in\mathbb{R}^{n\times k}$:

(1)
$\min_{\mathbf{F}}\operatorname{Tr}\left(\mathbf{F}^{\top}\mathbf{L}\mathbf{F}\right),s.t.\mathbf{F}^{\top}\mathbf{F}=\mathbf{I}_{k},$

where $\mathbf{L}$ denotes the graph Laplace operator, which is calculated by
$\mathbf{D}-\mathbf{W}$. $\mathbf{D}$ is a diagonal matrix, and its element is
defined as $d_{ii}=\sum_{j=1}^{n}s_{ij}$. $\mathbf{W}$ is the symmetric
similarity matrix, which is calculated by
$\frac{\mathbf{S}+\mathbf{S}^{\top}}{2}$. $\mathbf{F}$ is the spectral
representation (Ng et al., 2002; Hamilton, 2020), and the final clustering
label is acquired after the $k$-mean algorithm.

Numerous methods have been proposed on the basis of this framework by imposing
different constraints (Nie et al., 2016b; Yin et al., 2018; Li et al., 2021;
Jin et al., 2023; Li et al., 2023) or exploring various types of
regularization terms (Yin et al., 2018; Yang et al., 2019; Zhang et al.,
2017). Nie et al. (Nie et al., 2016a) generate the optimal Laplacian matrices
by the linear combinations of Laplacian basis matrices constructed from multi-
view samples. Gao et al. (Gao et al., 2015) learn independent representations
from each view to capture the diverse information and use a consensus
clustering structure to ensure intra-view consistency. Zhang et al. (Zhang et
al., 2015) take the view-specific subspace representation as a tensor and
explore the intersection information from the diverse views by using low-rank
constraints.

Nevertheless, such a paradigm cannot prevent the whole graph construction and
consequent spectral decomposition process (Kang et al., 2019b; Wen et al.,
2019). The time overhead of the methods is at least
$\mathcal{O}\left(n^{3}\right)$ and the space complexity is at least
$\mathcal{O}\left(n^{2}\right)$, largely hindering the large-scale
applications.

###  2.2. Anchor-based Multi-View Graph Clustering

In recent years, anchor-based multi-view graph clustering (AMVGC) has received
abundant attention owing to its high efficiency. By constructing the
relationship between the representative anchors selected and samples, i.e.,
anchor graph $\mathbf{Z}^{(p)}$, to recover the full graph, the space
complexity of AMVGC can efficiently reduce from $\mathcal{O}(n^{3})$ to
$\mathcal{O}(nm)$ (Guo and Ye, 2019; Ou et al., 2020).

To our knowledge, a data point within a subspace could be calculated as a
linear combination of other data from the same subspace, which is known as the
self-expression proposition (Ren and Sun, 2020; Kang et al., 2019a).
Therefore, AMVGC methods can count on the self-expression property for the
purpose of constructing a reliable anchor graph, which we also refer to as the
global structure since it utilizes the whole data information. The classical
anchor-based multi-view graph clustering with global structure can be shown as
follows:

(2) $\displaystyle\min_{\mathbf{Z}}\
\sum_{p=1}^{v}\left\|\mathbf{X}^{(p)}-\mathbf{A}^{(p)}\mathbf{Z}\right\|_{F}^{2}+\mu\left\|\mathbf{Z}\right\|_{F}^{2},$
$\displaystyle\text{ s.t.
}\mathbf{Z}^{\top}\mathbf{1}_{m}=\mathbf{1}_{n},\mathbf{Z}\geq\mathbf{0},$

where $\mathbf{A}^{(p)}$ denotes the anchor matrix from the $p$-th view, and
$\mathbf{Z}$ denotes the common anchor graph. The final clustering indicates
matrix can be calculated from the SVD decomposition of $\mathbf{Z}$ (Kang et
al., 2020b; Xie et al., 2020, 2019). Consequently, the computational and space
expenditure is reduced from $\mathcal{O}(n^{3})$ to $\mathcal{O}(vnm)$, where
$n,m$, and $v$ denotes the number of samples, anchors, and views,
correspondingly.

Based on a specific similarity measure, local structure only considers the
relationship between samples and one anchor with high similarity. The
significance of preserving local manifold structure has been well recognized
in non-linear model and cluster analysis (Ren and Sun, 2020; Wen et al.,
2021b) since neighboring samples usually maintain consistent label
information. A classical anchor-based multi-view graph clustering with local
structure can be calculated by

(3)
$\begin{split}&\min_{\mathbf{z}}\sum_{p=1}^{v}\sum_{i=1}^{n}\sum_{j=1}^{m}\left\|\mathbf{x}_{i}^{(p)}-\mathbf{a}_{j}^{(p)}\right\|_{2}^{2}\mathbf{z}_{ji}+\mu_{1}\sum_{i=1}^{n}\sum_{j=1}^{m}\mathbf{z}_{ji}^{2}\
,\\\ &\text{ s.t. }\mathbf{z}_{i}\geq
0,\mathbf{z}_{i}^{\top}\mathbf{1}=\mathbf{1}\text{ ,}\end{split}$

where $\mathbf{x}_{i}^{(p)}$ is the $i$-th data from the $p$-th view,
$\mathbf{a}_{j}^{(p)}$ is the $j$-th anchor from the $p$-th view,
$\mathbf{z}_{i}$ denotes the $i$th column of $\mathbf{Z}$, and $\mu$ is the
balance parameter that constrains $\mathbf{z}_{i}\geq 0$ and
$\mathbf{z}_{i}^{\top}\mathbf{1}=\mathbf{1}$ guarantee the probabilistic
properties of $\mathbf{z}_{i}$.

##  3\. Method

###  3.1. Problem Formulation

Intuitively, a high-quality graph plays an important role in the success of
graph-based clustering (Chen et al., 2020; Huang et al., 2019b; Li et al.,
2022a; Yang et al., 2023, 2022b; Liu et al., 2023d, 2022a; Yang et al.,
2022a). Most multi-view graph clustering(MVGC) methods usually adopt a self-
representation strategy to characterize the samples. Although the global
structure is well-explored, the local structure is ignored, which provides
insufficient information for the learning task and ultimately leads to sub-
optimal clustering performance (Huang et al., 2022; Wang et al., 2015a; Gao et
al., 2020). Several attempts have been made to address the issues (Ren et al.,
2012). For instance, He et al. (He and Niyogi, 2003) merged global and local
structures to generate the similarity of the original data in the kernel
space. Wen et al. (Wen et al., 2021b) uses low-rank constraints to produce
adaptive graphs for the purpose of one-step clustering. However, their high
time and space expenditure hinder the application of the method.

In this paper, we employ an anchor strategy, which selects representative
samples to capture the manifold structure. Besides, we adopt the view-
independent anchor and generate a common anchor graph to efficiently excavate
the complementary and consistent information of multiple views. With the view-
specific anchor $\mathbf{A}^{(p)}\in\mathbb{R}^{d_{p}\times m}$ and the
consistent anchor graph $\mathbf{Z}\in\mathbb{R}^{m\times n}$, the classical
anchor-based multi-view graph clustering with global structure Eq.(2) can be
formulated into the following equivalence problem:

(4)
$\displaystyle\min_{\mathbf{Z}}\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{A}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)-2\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{X}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)+\mu\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{Z}\right),$
$\displaystyle s.t.\quad\mathbf{Z}\geq
0,\mathbf{Z}^{\top}\mathbf{1}=\mathbf{1},$

where the $\mu$ is balanced hyperparameter of regularization term.

For local structure preserving, we summarize the paradigm of the traditional
AMVGC with local structure and introduce the terms
$\operatorname{tr}(\mathbf{A}^{(p)}\operatorname{diag}(\mathbf{Z}\mathbf{1})\mathbf{A}^{(p)\top})$,
which can be mathematically derived from numerous methods, including BIMVC(Li
and He, 2020), MVASM(Han et al., 2020), and MGLSMC(Jiang et al., 2021). With
the local term, our objective equation becomes:

(5)
$\begin{split}&\min_{\mathbf{Z}}\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{A}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)-2\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{X}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)\\\
&\quad\quad+\lambda\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{A}^{(p)}\operatorname{diag}(\mathbf{Z}\mathbf{1})\mathbf{A}^{(p)\top}\right)+\mu\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{Z}\right)\text{,
}\\\ &s.t.\quad\mathbf{Z}\geq
0,\mathbf{Z}^{\top}\mathbf{1}=\mathbf{1},\end{split}$

where $\mathbf{X}^{(p)}\in\mathbb{R}^{d_{p}\times n}$ represents the orignial
data with $d_{p}$ dimensions in the $p$-th view.

Although the local and global structures are preserved, the quality of our
model is highly dependent on the anchor initiation. Most existing anchor-based
multi-view graph clustering algorithms use heuristic sampling strategies such
as K-means to acquire desirable anchors. However, the anchor construction, as
well as the structure learning are separated from each other, which could
restrict the clustering capability. Unlike traditional techniques, we learn
anchors automatically instead of sampling in this paper. Finally, we can
define the optimization for EMVGC-LG as follows:

(6)
$\begin{split}&\min_{\mathbf{A}^{(p)},\mathbf{Z}}\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{A}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)-2\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{X}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)\\\
&\quad\quad+\lambda\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{A}^{(p)}\operatorname{diag}(\mathbf{Z}\mathbf{1})\mathbf{A}^{(p)\top}\right)+\mu\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{Z}\right)\text{.
}\\\ &s.t.\quad\mathbf{Z}\geq
0,\mathbf{Z}^{\top}\mathbf{1}=\mathbf{1}\end{split}$

###### Proposition 0.

By setting $\lambda\in\left(0,1\right],\mu=\lambda\mu_{1}$, minimizing Eq. (3)
can be approximated by minimizing Eq. (LABEL:my_formula).

###### Proof.

By adding the item
$\sum_{p=1}^{v}\operatorname{tr}(\mathbf{X}^{(p)\top}\mathbf{X}^{(p)})$ not
related to the optimized variables, Eq. (LABEL:my_formula) can be transformed
into the following equivalence problem:

$\displaystyle Eq.(\ref{my formula})\Leftrightarrow$
$\displaystyle\lambda\sum_{p=1}^{v}\left(\operatorname{tr}\left(\mathbf{X}^{(p)\top}\mathbf{X}^{(p)}\right)-2\operatorname{tr}\left(\mathbf{X}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)+\operatorname{tr}(\mathbf{M}^{(p)}\mathbf{Z})\right)$
$\displaystyle+\left(1-\lambda\right)\sum_{p=1}^{v}\left(\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{A}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)-2\operatorname{tr}\left(\mathbf{X}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)\right.$
$\displaystyle\left.+\operatorname{tr}\left(\mathbf{X}^{(p)\top}\mathbf{X}^{(p)}\right)\right)+\lambda\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{A}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)+\mu\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{Z}\right)$
$\displaystyle=\lambda\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{A}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)+\left(1-\lambda\right)\sum_{p=1}^{v}\left\|\mathbf{X}^{(p)}-\mathbf{A}^{(p)}\mathbf{Z}\right\|_{F}^{2}$
$\displaystyle+\lambda\sum_{p=1}^{v}\left(\operatorname{tr}\left(\mathbf{X}^{(p)\top}\mathbf{X}^{(p)}\right)-2\operatorname{tr}\left(\mathbf{X}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)+\operatorname{tr}(\mathbf{M}^{(p)}\mathbf{Z})\right)$
$\displaystyle+\lambda\mu_{1}\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{Z}\right)$
$\displaystyle\geq\quad\lambda\sum_{i=1}^{n}\sum_{j=1}^{m}\left(\sum_{p=1}^{v}\left\|\mathbf{x}_{i}^{(p)}-\mathbf{a}_{j}^{(p)}\right\|_{2}^{2}\mathbf{z}_{ji}+\mu_{1}\mathbf{z}_{ji}^{2}\right)\Leftrightarrow
Eq.(\ref{local})$

where
$\operatorname{tr}(\mathbf{M}^{(p)}\mathbf{Z})=\operatorname{tr}\left(\mathbf{A}^{(p)}\operatorname{diag}(\mathbf{Z}\mathbf{1})\mathbf{A}^{(p)\top}\right)$,
$\mathbf{M}^{(p)}_{i,:}=\left[\mathbf{q}_{1}^{(p)},\cdots,\right.$
$\left.\mathbf{q}_{m}^{(p)}\right]$,
$\mathbf{q}_{j}^{(p)}=\mathbf{A}^{(p)\top}_{:,j}\mathbf{A}^{(p)}_{:,j}.$ ∎

###### Remark 1.

Proposition 1 illustrates that the proposed Eq.(LABEL:my_formula) is an upper
bound of Eq.(3). Therefore, our model can approximate the local structure by
minimizing Eq.(LABEL:my_formula). The tradeoff between the global and local
structure preservation is adjusted by the parameter $\lambda$.

###  3.2. Optimization

When all the variables are considered together, the optimization of
Eq.(LABEL:my_formula) becomes a nonconvex problem, and we address it with an
alternating optimization algorithm.

####  3.2.1. Optimization of Anchor Matrices
$\\{\mathbf{A}^{(p)}\\}_{p=1}^{v}$

When $\\{\mathbf{Z}^{(p)}\\}_{p=1}^{v}$ is fixed, the optimization for
$\\{\mathbf{A}^{(p)}\\}_{p=1}^{v}$ can be written as follows:

(7) $\displaystyle\min_{\mathbf{A}^{(p)}}$
$\displaystyle\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{A}^{(p)}\mathbf{Z}\mathbf{Z}^{\top}\mathbf{A}^{(p)\top}\right)-2\operatorname{tr}\left(\mathbf{Z}\mathbf{X}^{(p)\top}\mathbf{A}^{(p)}\right)$
$\displaystyle\quad+\lambda\operatorname{tr}\left(\mathbf{A}^{(p)}\operatorname{diag}(\mathbf{Z}\mathbf{1})\mathbf{A}^{(p)\top}\right).$

Considering the optimization of each $\mathbf{A}_{v}$ is independent of the
corresponding view. Therefore, we can optimize Eq. (7) by solving the problems
as follows,

(8)
$\min_{\mathbf{A}^{(p)}}2\mathbf{A}^{(p)}\mathbf{Z}\mathbf{Z}^{\top}+2\lambda\mathbf{A}^{(p)}\operatorname{diag}(\mathbf{Z}\mathbf{1})-2\mathbf{X}^{(p)}\mathbf{Z}^{\top}.$

Intuitively, $\mathbf{A}^{(p)}$ can be calculated by:

(9)
$\mathbf{A}^{(p)}=\mathbf{X}^{(p)}\mathbf{Z}^{\top}\left(\mathbf{Z}\mathbf{Z}^{\top}+\lambda\operatorname{diag}(\mathbf{Z}\mathbf{1})\right)^{-1}.$

####  3.2.2. Optimization of Consistent Anchor Graph $\mathbf{Z}$

When $\\{\mathbf{A}^{(p)}\\}_{p=1}^{v}$ is fixed, the optimization for
$\mathbf{Z}$ can be written as follows:

(10) $\displaystyle\min_{\mathbf{Z}}$
$\displaystyle\quad\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{A}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)+\lambda\sum_{p=1}^{v}\operatorname{tr}(\mathbf{M}^{(p)}\mathbf{Z})$
$\displaystyle-2\sum_{p=1}^{v}\operatorname{tr}\left(\mathbf{X}^{(p)\top}\mathbf{A}^{(p)}\mathbf{Z}\right)+\mu\operatorname{tr}\left(\mathbf{Z}^{\top}\mathbf{Z}\right),$
$\displaystyle s.t.\mathbf{Z}\geq 0,\mathbf{Z}^{\top}\mathbf{1}=\mathbf{1},$

where
$\mathbf{M}^{(p)}_{i,:}=\left[\mathbf{q}_{1}^{(p)},\cdots,\mathbf{q}_{m}^{(p)}\right]$
, $\mathbf{q}_{j}^{(p)}=\mathbf{A}^{(p)\top}_{:,j}\mathbf{A}^{(p)}_{:,j}.$

As mentioned earlier, the above optimization process of $\mathbf{Z}$ can be
easily expressed as the below Quadratic Programming (QP) problem,

(11)
$\displaystyle\min\frac{1}{2}\mathbf{Z}_{:,i}^{\top}\mathbf{Q}\mathbf{Z}_{:,i}+f_{i}^{\top}\mathbf{Z}_{:,i},$
$\displaystyle\text{ s.t.
}\mathbf{Z}_{:,i}^{\top}\mathbf{1}=1,\mathbf{Z}_{:,i}\geq 0,$

where
$\mathbf{Q}=\sum_{p=1}^{v}\mathbf{A}^{(p)\top}\mathbf{A}^{(p)}+\mu\mathbf{I}$,$f_{i}=-\sum_{p=1}^{v}\left({\mathbf{X}_{:,i}^{(p)}}^{\top}\mathbf{A}^{(p)}+\frac{\lambda}{2}\mathbf{M}_{i,:}^{(p)}\right)$.

Because each column of $\mathbf{Z}$ is a $m$-dimensional vector, the time
complexity of this sub-problem is $\mathcal{O}(nm^{3})$. The entire
optimization process for solving Eq.(LABEL:my_formula) is summarized in
Algorithm 1.

Algorithm 1 Efficient Multi-View Graph Clustering with Local and Global
Structure Preservation (EMVGC-LG)

0: multi-views dataset $\\{\mathbf{X}^{(p)}\\}_{p=1}^{v}$, the number of
cluster $k$.

1: Initialize $\\{\mathbf{A}^{(p)}\\}_{p=1}^{v}$.

2: repeat

3: Obtain $\\{\mathbf{A}^{(p)}\\}_{p=1}^{v}$ with Eq. (7).

4: Obtain $\mathbf{Z}$ with Eq. (10).

5: until converged

6: Obtain $\mathbf{H}$ by performing SVD on $\mathbf{Z}$

6: Perform k-means on $\mathbf{H}$ to obtain discrete labels.

###  3.3. Discussions

####  3.3.1. Convergence

As the iterations proceed, two variables of the above optimization procedure
will be separately addressed. Since each subproblem has reached the global
optimum, the value of the EMVGC-LG function will monotonically decrease and
finally reach convergence. Moreover, since the lower bound of the objective
function can be easily proved to be
$-\sum_{p=1}^{v}\operatorname{tr}(\mathbf{X}^{(p)\top}\mathbf{X}^{(p)})$ (by
Proposition 1), our proposed EMVGC-LG is proven to converge to the local
optimum.

####  3.3.2. Space Complexity

In this paper, the primary memory overhead of our approach is the matrix
$\mathbf{Z}\in\mathbb{R}^{m\times n}$ and
$\mathbf{A}^{(p)}\in\mathbb{R}^{d_{p}\times m}$. As a result, the space
complexity of EMVGC-LG is $m\left(n+d\right)$, where $d=\sum_{p=1}^{v}d_{p}$.
$m\ll n$ and $d\ll n$ are within our settings. Therefore, the space complexity
of EMVGC-LG is $\mathcal{O}(n)$.

####  3.3.3. Time Complexity

The time complexity of EMVGC-LG is composed of two optimization steps, as
previously mentioned. The time complexity of updating
$\\{\mathbf{A}^{(p)}\\}_{p=1}^{v}$ is $\mathcal{O}\left((nmd+m^{3})v\right)$.
When analytically obtaining $\mathbf{Z}$, it costs $\mathcal{O}(nm^{3})$ for
all columns. Therefore, the total time cost of the optimization process is
$\mathcal{O}\left(n(mdv+m^{3})+m^{3}v\right)$. Consequently, the computational
complexity of EMVGC-LG is $\mathcal{O}(n)$, which is linearly related to the
number of data.

##  4\. Experiment

In this section, we perform numerous experiments to assess our proposed EMVGC-
LG. Concretely, we discuss the clustering quality on synthetic and real
datasets, the evolution of the objective values, the running time, the
sensitivity of the parameters, and the ablation study. Our code is accessible
on the https://github.com/wy1019/EMVGC-LG.

###  4.1. Synthetic Datasets

In order to visualize the different influences of local and global structure,
we performed experiments on a synthetic two-view two-dimensional dataset
containing 500 samples extracted from five clusters produced by a Gaussian
function. From Figure 2, we can observe that incorporating local and global
information can effectively enhance the clustering performance. Compared with
a singular structure, our strategy improves the performance by 11.85% and
26.08%, respectively, and yields a clearer partition of clusters.

Table 1. Benchmark datasets

Datasets | Samples | Views | Clusters
---|---|---|---
Reuters12 | 1200 | 5 | 6
Flower17 | 1360 | 7 | 17
Mfeat | 2000 | 2 | 10
VGGFace50 | 16936 | 4 | 50
Caltech256 | 30607 | 4 | 257
YouTubeFace10 | 38654 | 4 | 10
Cifar10 | 60000 | 4 | 9
Cifar100 | 60000 | 4 | 99
YouTubeFace20 | 63896 | 4 | 20
YouTubeFace50 | 126054 | 4 | 50

###  4.2. Real-world Datasets

Ten extensively available datasets were used to assess the validity of the
proposed algorithms. The information of the datasets are as follows, including
Reuters12111https://archive.ics.uci.edu/ml/datasets/reuters-21578+text+categorization+collection,
Flower17222https://www.robots.ox.ac.uk/vgg/data/flowers/17/,
Mfeat333http://www.svcl.ucsd.edu/projects/crossmodal/,
VGGFace50444https://www.robots.ox.ac.uk/vgg/data/vgg_face/,
Caltech256555https://authors.library.caltech.edu/7694/, YouTubeFace107,
Cifar106, Cifar100666https://www.cs.toronto.edu/kriz/cifar.html,
YouTubeFace207, and YouTubeFace50777https://www.cs.tau.ac.il/wolf/ytfaces/.
The detailed information is listed in Table 1. Specifically, Reuters12 is a
subset of Reuters, which contains 1200 documents described in five languages,
including English, France, German, Italian, and Spanish. Flower17 is a flower
dataset with 80 images for each class. Mfeat contains 2000 images of
handwritten numbers from 0 to 9. Each sample is expressed by six different
feature sets, i.e., 216-dimensional FAC, 76-dimensional FOU, 64-dimensional
KAR, 6 MORs, 240-dimensional Pix, and 47-dimensional ZER. VGGFace50 is derived
from VGGFace. Caltech256 contains 30607 images spanning 257 object categories.
Features were extracted from 60,000 tiny color images of 10 categories and 100
categories in four views of Cifar10 and Cifar100 by ResNet18, ResNet50, and
DenseNet121. YoutubeFace10, YoutubeFace20, and YouTubeFace50 are face video
datasets withdrawn from YouTube.

Table 2. Empirical evaluation and comparison of EMVGC-LG with ten baseline
methods on ten benchmark datasets

Dataset | RMKM | AMGL | FMR | PMSC | BMVC | LMVSC | SMVSC | SFMC | FMCNOF | FPMVS-CAG | Proposed
---|---|---|---|---|---|---|---|---|---|---|---
ACC (%)
Reuters12 | 44.00±0.00 | 18.12±0.42 | 52.35±1.90 | 27.88±0.75 | 50.33±0.00 | 47.92±2.98 | 55.69±3.06 | 17.08±0.00 | 28.58±0.00 | 45.82±3.29 | 60.74±2.01
Flower17 | 23.24±0.00 | 9.70±1.53 | 33.43±1.75 | 20.82±0.74 | 26.99±0.00 | 37.12±1.86 | 27.13±0.84 | 7.57±0.00 | 17.43±0.00 | 25.99±1.83 | 53.28±2.51
Mfeat | 80.80±0.00 | 71.42±5.42 | 64.53±2.28 | 66.41±4.40 | 65.80±0.00 | 82.86±6.95 | 65.57±3.99 | 56.90±0.00 | 56.95±0.00 | 65.11±4.18 | 88.53±4.87
VGGFace50 | 8.23±0.00 | 2.95±0.35 | O/M | O/M | 10.30±0.00 | 10.56±0.26 | 13.36±0.60 | 3.64±0.00 | 5.51±0.00 | 12.06±0.36 | 15.29±0.74
Caltech256 | 9.87±0.00 | O/M | O/M | O/M | 8.63±0.00 | 9.57±0.17 | 10.54±0.15 | O/M | 2.70±0.00 | 8.78±0.07 | 11.70±0.36
YouTubeFace10 | 74.88±0.00 | O/M | O/M | O/M | 58.58±0.00 | 74.48±5.30 | 72.93±3.96 | 55.80±0.00 | 43.42±0.00 | 67.09±5.70 | 79.55±4.57
CIFAR10 | O/M | O/M | O/M | O/M | 27.81±0.00 | 29.02±0.81 | 29.11±1.35 | 10.02±0.00 | 20.53±0.00 | 26.89±0.71 | 31.14±1.07
CIFAR100 | O/M | O/M | O/M | O/M | 8.32±0.00 | 9.53±0.15 | 8.34±0.17 | 1.18±0.00 | 3.66±0.00 | 7.29±0.11 | 10.96±0.35
YouTubeFace20 | O/M | O/M | O/M | O/M | 57.39±0.00 | 67.26±3.53 | 67.13±4.20 | O/M | 38.61±0.00 | 63.08±3.79 | 72.79±2.73
YouTubeFace50 | O/M | O/M | O/M | O/M | 66.00±0.00 | 68.32±2.45 | O/M | O/M | 21.66±0.00 | 64.24±2.97 | 70.52±2.62
NMI (%)
Reuters12 | 26.83±0.00 | 3.46±0.76 | 31.43±0.84 | 14.76±0.58 | 27.25±0.00 | 27.86±1.49 | 32.46±1.72 | 12.61±0.00 | 7.15±0.00 | 24.59±3.20 | 35.80±1.03
Flower17 | 22.07±0.00 | 10.25±4.01 | 30.65±0.91 | 19.13±0.48 | 25.62±0.00 | 35.37±1.10 | 25.78±0.76 | 7.87±0.00 | 14.68±0.00 | 25.81±1.59 | 51.77±1.72
Mfeat | 82.28±0.00 | 77.12±2.19 | 66.21±0.73 | 63.29±1.63 | 59.39±0.00 | 82.46±2.79 | 57.99±2.11 | 68.15±0.00 | 55.47±0.00 | 57.77±2.73 | 82.90±2.78
VGGFace50 | 9.66±0.00 | 2.04±0.50 | O/M | O/M | 13.48±0.00 | 12.64±0.28 | 16.21±0.49 | 1.63±0.00 | 4.74±0.00 | 14.74±0.55 | 18.71±0.76
Caltech256 | 31.01±0.00 | O/M | O/M | O/M | 31.83±0.00 | 31.96±0.11 | 28.27±0.24 | O/M | 1.60±0.00 | 22.97±0.21 | 34.78±0.17
YouTubeFace10 | 78.83±0.00 | O/M | O/M | O/M | 54.66±0.00 | 77.74±2.03 | 78.57±2.80 | 77.46±0.00 | 39.15±0.00 | 76.11±3.06 | 82.21±2.97
CIFAR10 | O/M | O/M | O/M | O/M | 17.90±0.00 | 17.84±0.53 | 16.00±0.99 | 0.16±0.00 | 10.33±0.00 | 15.45±0.99 | 18.22±0.66
CIFAR100 | O/M | O/M | O/M | O/M | 15.05±0.00 | 15.40±0.18 | 14.40±0.20 | 0.53±0.00 | 7.04±0.00 | 13.62±0.16 | 18.42±0.33
YouTubeFace20 | O/M | O/M | O/M | O/M | 70.65±0.00 | 76.78±1.34 | 78.36±2.39 | O/M | 45.45±0.00 | 74.30±1.95 | 80.57±1.60
YouTubeFace50 | O/M | O/M | O/M | O/M | 81.90±0.00 | 82.43±0.78 | O/M | O/M | 43.03±0.00 | 82.08±1.07 | 84.17±0.83
Fscore (%)
Reuters12 | 32.18±0.00 | 28.36±0.01 | 38.62±0.43 | 27.25±0.41 | 35.49±0.00 | 34.80±1.16 | 39.12±1.10 | 27.71±0.00 | 24.11±0.00 | 34.14±1.23 | 43.01±1.29
Flower17 | 14.35±0.00 | 11.49±0.34 | 20.09±0.81 | 12.33±0.36 | 16.61±0.00 | 23.99±0.95 | 17.53±0.21 | 10.94±0.00 | 13.93±0.00 | 17.29±0.39 | 38.41±1.74
Mfeat | 76.64±0.00 | 65.74±7.46 | 58.89±1.02 | 55.68±2.20 | 50.87±0.00 | 78.11±5.34 | 53.09±2.65 | 45.62±0.00 | 45.52±0.00 | 52.50±3.10 | 80.93±4.85
VGGFace50 | 3.69±0.00 | 3.91±0.02 | O/M | O/M | 5.10±0.00 | 5.09±0.15 | 6.35±0.18 | 4.16±0.00 | 4.36±0.00 | 6.10±0.07 | 7.93±0.41
Caltech256 | 7.28±0.00 | O/M | O/M | O/M | 6.25±0.00 | 6.00±0.28 | 5.37±0.20 | O/M | 1.17±0.00 | 3.22±0.02 | 8.70±0.69
YouTubeFace10 | 66.93±0.00 | O/M | O/M | O/M | 52.53±0.00 | 68.93±3.19 | 68.34±5.78 | 61.25±0.00 | 32.88±0.00 | 66.10±5.06 | 75.38±4.44
CIFAR10 | O/M | O/M | O/M | O/M | 21.64±0.00 | 20.34±0.43 | 19.70±0.55 | 18.18±0.00 | 18.48±0.00 | 20.58±0.34 | 20.85±0.54
CIFAR100 | O/M | O/M | O/M | O/M | 4.37±0.00 | 3.69±0.05 | 4.47±0.06 | 1.98±0.00 | 2.56±0.00 | 3.78±0.01 | 4.36±0.15
YouTubeFace20 | O/M | O/M | O/M | O/M | 49.04±0.00 | 62.43±2.91 | 61.68±5.99 | O/M | 25.84±0.00 | 57.81±4.00 | 68.22±3.48
YouTubeFace50 | O/M | O/M | O/M | O/M | 57.09±0.00 | 62.49±2.45 | O/M | O/M | 15.67±0.00 | 56.89±3.18 | 63.34±1.78

(a) Local (ACC = 73.08%)

(b) Global (ACC = 88.15%)

(c) Ours (ACC = 100%)

Figure 2. Visualization of learned graph on synthetic datasets. Figure 3. Time
comparison of different MVC Methods on ten datasets (a)  Figure 4. The
ablation study of our local and global structure combination strategy on five
benchmark datasets. (a)  Figure 5. The ablation study of our anchor learning
strategy on five benchmark datasets. ”Fixed” indicates without our anchor
learning strategy.

###  4.3. Compared Methods

Along with our proposed EMVGC-LG, we run ten state-of-the-art multi-view graph
clustering methods for comparison, including Multi-view k-means Clustering on
Big Data (RMKM) (Cai et al., 2013), Parameter-free Auto-weighted Multiple
Graph Learning (AMGL) (Nie et al., 2016a), Flexible Multi-View Representation
Learning for Subspace Clustering (FMR) (Li et al., 2019), Partition Level
Multi-view Subspace Clustering (PMSC) (Kang et al., 2020a), Binary Multi-View
Clustering (BMVC) (Zhang et al., 2018b), Large-scale Multi-view Subspace
Clustering in Linear Time (LMVSC)(Kang et al., 2020b), Scalable Multiview
Subspace Clustering with Unified Anchors (SMVSC) (Sun et al., 2021), Multi-
view clustering: a Scalable and Parameter-free Bipartite Graph Fusion Method
(SFMC) (Li et al., 2020), Fast Multiview Clustering via Nonnegative and
Orthogonal Factorization (FMCNOF)(Yang et al., 2020), and Fast Parameter-free
Multiview Subspace Clustering with Consensus Anchor Guidance (FPMVS-CAG)(Wang
et al., 2022).

For all the aforementioned algorithms, we set their parameters as their
recommended range. In the proposed method, we adjusted $\lambda$ to
$[10^{-3},10^{-2},10^{-1},1]$, $\mu$ to $[0,10^{-4},1,10^{4}]$, and the anchor
numbers to [k, 2k, 5k], with a grid search scheme. In addition, we repeated
each experiment 10 times to calculate the mean performance and standard
deviation. To assess the clustering performance, we use three widely used
metrics, consisting of Accuracy (ACC), Normalised Mutual Information (NMI),
and Fscore. All experiments were conducted on a desktop computer with Intel
core i9-10900X CPU and 64G RAM, MATLAB 2020b (64-bit).

###  4.4. Experimental Results

Table 2 indicates the clustering performance on ten datasets. The best results
are marked in red, and the second-best results are marked in blue. ”O/M”
represents the unavailable results due to time-out or out-of-memory errors.
According to the results, we have the following observation:

  1. (1)

Compared with existing MVC methods, our proposed algorithm achieves the best
or second-best performance on ten datasets. In comparison with the second-best
ones, our EMVGC-LG acquires 5.05%, 16.16%, 5.67%, 1.93%, 1.16%, 4.67%, 2.03%,
1.43%, 5.53% and 2.2% in terms of ACC, which demonstrates local and global
structure fusion strategy. In other metrics, EMVGC-LG also achieved desirable
performance.

  2. (2)

Comparison with classical MVGC methods, i.e., RMKM, AMGL, FMR, and PMSC,
encounter scalability problems on large-scale datasets due to the huge matrix
computation and memory generated by the full graph construction. Our EMVGC-LG
outperforms them by 8.39%, 19.85%, 7.73%, 7.06%, 1.87%, and 4.67% of ACC on
six datasets, showing the superiority of our anchor-based algorithm.

  3. (3)

Comparison with existing AMVGC methods, i.e., BMVC, LMVSC, SMVSC, SFMC,
FMCNOF, and FPMVS-CAG, our EMVGC-LG still acquires comparable or better
performance. In particular, the LMVSC method shows better results than other
methods, which demonstrates its superiority in large-scale scenarios. In terms
of ACC, our EMVGC-LG achieves better performance than LMVSC by large margins
of 12.82%, 16.16%, 5.67%, 4.73%, 2.13%, 5.07%, 2.12%, 1.43%, 5.53%, and 2.20%,
illustrating our effectiveness.

(a)  Figure 6. Sensitivity analysis of anchor number m of our method on two
benchmark datasets.

###  4.5. Running Time Comparison

To validate the computational efficiency of the proposed EMVGC-LG, we plot the
average running time of each algorithm on ten benchmark datasets in Figure 3.
The results of some compared algorithms on large-scale datasets are not
reported due to memory overflow errors caused by their excessive time and
space complexity. As shown in the Figure 3, we can observe that

  1. (1)

Compared to full graph-based clustering methods, the proposed EMVGC-LG
significantly reduces run time through the construction of anchor graphs.

  2. (2)

Compared to the anchor-based MVC approach, i.e., SMVSC and FPMVS-CAG, the
proposed EMVGC-LG requires more time consumption, mainly due to our local and
global structure preservation strategy. Generally, the extra time spent is
worthwhile since our proposed EMVGC-LG demonstrates its superiority in most
datasets.

###  4.6. Ablation Study

####  4.6.1. Local and Global Structure Combination Strategy

The local and global structure combination strategy is the main contribution
of this paper. To further demonstrate the effectiveness of this strategy, we
present the experimental results of the ablation study in Figure 4, where
”Local” and ”Global” indicates only using the local or global structure,
respectively. In our experimental setting, we optimize the Eq.(3) and Eq.(2)
in the optimization process to obtain the final clustering result. In terms of
ACC, the proposed structure combination strategy improves the algorithm
performance on the Flower17, Mfeat, VGGFace50, Cifar100, and YouTubeFace20
datasets by 21.03%,8.71%, 6.74%, 1.46%, and 2.30% compared to the simple local
structure respectively, which demonstrates the effectiveness of our strategy.

(a)  Figure 7. Sensitivity analysis of $\lambda$ and $\mu$ of our method on
two benchmark datasets.

####  4.6.2. Anchor Learning Strategy

We conducted ablation experiments with the proposed anchor learning strategy,
as shown in Figure 5. ”Fixed” indicates initializing anchors by k-means
without updating during the optimization process. Compared to the above
methods, our approach significantly improves the clustering performance and
avoids the high time expenditure of k-means, demonstrating the effectiveness
of the anchor learning strategy.

###  4.7. Convergence and Sensitivity

We conducted several experiments to demonstrate the convergence of the
proposed algorithm. As shown in Figure 8, the objective value of our algorithm
is monotonically decreasing in each iteration. These results clearly verify
the convergence of our proposed algorithm.

(a)  Figure 8. Objective values of the proposed method on two benchmark
datasets.

To investigate the sensitivity of our algorithm to the number of anchors m, we
investigated how our performance shifts for different numbers of anchors. As
shown in Figure 6, the number of anchors has some effect on the performance of
our algorithm and basically achieves optimal performance at m = k. Moreover,
two hyperparameters, $\lambda$, and $\mu$, are used in our method, $\lambda$
is the local and global structure balanced parameter, and $\mu$ is the
coefficient of the sparsity regularization term. As is shown in Figure 7, we
conducted comparative experiments on two benchmark datasets to illustrate the
impact of these two parameters on performance. In terms of VGGFace50, our
method performs better when $\lambda$ is less than 0.001, and $\mu$ is larger
than 1. When the value of $\lambda$ is larger than 0.01, EMVGC-LG works well
on the Mfeat dataset, and $\mu$ has little effect on it. Thus, with fixed
$\lambda$, the variation of $\mu$ has a smaller effect on the final
performance on most datasets, while ACC with the same $\mu$ will be affected
by $\lambda$.

##  5\. Conclusion

In this paper, we propose a novel anchor-based multi-view graph clustering
framework termed Efficient Multi-View Graph Clustering with Local and Global
Structure Preservation (EMVGC-LG). Specifically, EMVGC-LG considers preserving
the local and global structures in a unified framework, which provides
comprehensive information for clustering. We theoretically prove that the
proposed paradigm with the global structure can well approximate the local
information. Besides, anchor construction and graph learning are jointly
optimized in our unified framework to enhance the clustering quality. In
addition, EMVGC-LG inherits the linear complexity of existing AMVGC methods
respecting the sample number, which is time-economical and scales well with
the data size. Extensive experiments demonstrate the effectiveness and
efficiency of our proposed method. In the future, we will explore the
relationship between local and global structure in more detail, e.g., under
what circumstances is local structure preferable to global structure?

##  6\. ACKNOWLEDGMENTS

This work was supported by the National Key R&D Program of China (no.
2020AAA0107100) and the National Natural Science Foundation of China (project
no. 62325604, 62276271).

## References

  * (1)
  * Cai et al. (2013) Xiao Cai, Feiping Nie, and Heng Huang. 2013.  Multi-view k-means clustering on big data. In _Twenty-Third International Joint conference on artificial intelligence_.
  * Chen et al. (2020) Man-Sheng Chen, Ling Huang, Chang-Dong Wang, and Dong Huang. 2020.  Multi-view clustering in latent embedding space. In _Proc. of AAAI_.
  * Chen et al. (2022) Qing Chen, Xiumin Li, Anguo Zhang, and Yongduan Song. 2022\.  Neuroadaptive Tracking Control of Affine Nonlinear Systems Using Echo State Networks Embedded With Multiclustered Structure and Intrinsic Plasticity.  _IEEE Transactions on Cybernetics_ (2022).
  * Gao et al. (2015) Hongchang Gao, Feiping Nie, Xuelong Li, and Heng Huang. 2015\.  Multi-view subspace clustering. In _Proceedings of the IEEE international conference on computer vision_. 4238–4246.
  * Gao et al. (2020) Quanxue Gao, Wei Xia, Zhizhen Wan, Deyan Xie, and Pu Zhang. 2020.  Tensor-SVD based graph learning for multi-view subspace clustering. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 3930–3937.
  * Guo and Ye (2019) Jun Guo and Jiahui Ye. 2019\.  Anchors bring ease: An embarrassingly simple approach to partial multi-view clustering. In _Proc. of AAAI_.
  * Hamilton (2020) William L Hamilton. 2020\.  Graph representation learning.  _Synthesis Lectures on Artifical Intelligence and Machine Learning_ 14, 3 (2020), 1–159.
  * Han et al. (2020) Junwei Han, Jinglin Xu, Feiping Nie, and Xuelong Li. 2020\.  Multi-view K-Means Clustering with Adaptive Sparse Memberships and Weight Allocation.  _IEEE Transactions on Knowledge and Data Engineering_ (2020).
  * He and Niyogi (2003) Xiaofei He and Partha Niyogi. 2003.  Locality preserving projections.  _Advances in neural information processing systems_ 16 (2003).
  * Huang et al. (2022) Dong Huang, Chang-Dong Wang, and Jian-Huang Lai. 2022\.  Fast multi-view clustering via ensembles: Towards scalability, superiority, and simplicity.  _arXiv preprint arXiv:2203.11572_ (2022).
  * Huang et al. (2019b) Dong Huang, Chang-Dong Wang, Jiansheng Wu, Jian-Huang Lai, and Chee Keong Kwoh. 2019b.  Ultra-scalable spectral clustering and ensemble clustering.  _IEEE Transactions on Knowledge and Data Engineering_ (2019).
  * Huang et al. (2019a) Shudong Huang, Zhao Kang, Ivor W Tsang, and Zenglin Xu. 2019a.  Auto-weighted multi-view clustering via kernelized graph learning.  _Pattern Recognition_ (2019).
  * Jiang et al. (2021) Tianyu Jiang, Quanxue Gao, and Xinbo Gao. 2021.  Multiple graph learning for scalable multi-view clustering.  _arXiv preprint arXiv:2106.15382_ (2021).
  * Jin et al. (2023) Jiaqi Jin, Siwei Wang, Zhibin Dong, Xinwang Liu, and En Zhu. 2023.  Deep Incomplete Multi-view Clustering with Cross-view Partial Sample and Prototype Alignment.  _arXiv preprint arXiv:2303.15689_ (2023).
  * Kang et al. (2019a) Zhao Kang, Zipeng Guo, Shudong Huang, Siying Wang, Wenyu Chen, Yuanzhang Su, and Zenglin Xu. 2019a.  Multiple Partitions Aligned Clustering. In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19_. International Joint Conferences on Artificial Intelligence Organization, 2701–2707.
  * Kang et al. (2021) Zhao Kang, Zhiping Lin, Xiaofeng Zhu, and Wenbo Xu. 2021\.  Structured Graph Learning for Scalable Subspace Clustering: From Single View to Multiview.  _IEEE Transactions on Cybernetics_ (2021).
  * Kang et al. (2019b) Zhao Kang, Haiqi Pan, Steven CH Hoi, and Zenglin Xu. 2019b.  Robust graph learning from noisy data.  _IEEE transactions on cybernetics_ 50, 5 (2019), 1833–1843.
  * Kang et al. (2020a) Zhao Kang, Xinjia Zhao, Chong Peng, Hongyuan Zhu, Joey Tianyi Zhou, Xi Peng, Wenyu Chen, and Zenglin Xu. 2020a.  Partition level multiview subspace clustering.  _Neural Networks_ (2020).
  * Kang et al. (2020b) Zhao Kang, Wangtao Zhou, Zhitong Zhao, Junming Shao, Meng Han, and Zenglin Xu. 2020b.  Large-scale multi-view subspace clustering in linear time. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 34. 4412–4419.
  * Li and He (2020) Lusi Li and Haibo He. 2020\.  Bipartite Graph based Multi-view Clustering.  _IEEE Transactions on Knowledge and Data Engineering_ (2020).
  * Li et al. (2022b) Liang Li, Siwei Wang, Xinwang Liu, En Zhu, Li Shen, Kenli Li, and Keqin Li. 2022b.  Local Sample-Weighted Multiple Kernel Clustering With Consensus Discriminative Graph.  _IEEE Transactions on Neural Networks and Learning Systems_ (2022), 1–14.  https://doi.org/10.1109/TNNLS.2022.3184970
  * Li et al. (2023) Liang Li, Junpu Zhang, Siwei Wang, Xinwang Liu, Kenli Li, and Keqin Li. 2023\.  Multi-View Bipartite Graph Clustering With Coupled Noisy Feature Filter.  _IEEE Transactions on Knowledge and Data Engineering_ (2023), 1–13.  https://doi.org/10.1109/TKDE.2023.3268215
  * Li et al. (2019) Ruihuang Li, Changqing Zhang, Qinghua Hu, Pengfei Zhu, and Zheng Wang. 2019.  Flexible Multi-View Representation Learning for Subspace Clustering.. In _Proc. of IJCAI_.
  * Li et al. (2020) Xuelong Li, Han Zhang, Rong Wang, and Feiping Nie. 2020\.  Multi-view clustering: A scalable and parameter-free bipartite graph fusion method.  _IEEE Transactions on Pattern Analysis and Machine Intelligence_ (2020).
  * Li et al. (2015) Yeqing Li, Feiping Nie, Heng Huang, and Junzhou Huang. 2015\.  Large-scale multi-view spectral clustering via bipartite graph. In _Twenty-Ninth AAAI Conference on Artificial Intelligence_.
  * Li et al. (2018) Yingming Li, Ming Yang, and Zhongfei Zhang. 2018.  A survey of multi-view representation learning.  _IEEE transactions on knowledge and data engineering_ 31, 10 (2018), 1863–1883.
  * Li et al. (2021) Zhenglai Li, Chang Tang, Xinwang Liu, Xiao Zheng, Wei Zhang, and En Zhu. 2021\.  Consensus graph learning for multi-view clustering.  _IEEE Transactions on Multimedia_ 24 (2021), 2461–2472.
  * Li et al. (2022a) Zhenglai Li, Chang Tang, Xiao Zheng, Xinwang Liu, Wei Zhang, and En Zhu. 2022a.  High-order correlation preserved incomplete multi-view subspace clustering.  _IEEE Transactions on Image Processing_ 31 (2022), 2067–2080.
  * Liang et al. (2022) Ke Liang, Lingyuan Meng, Meng Liu, Yue Liu, Wenxuan Tu, Siwei Wang, Sihang Zhou, X Liu, and F Sun. 2022.  A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multimodal.  (2022).
  * Liang et al. (2023) Ke Liang, Sihang Zhou, Yue Liu, Lingyuan Meng, Meng Liu, and Xinwang Liu. 2023\.  Structure Guided Multi-modal Pre-trained Transformer for Knowledge Graph Reasoning.  _arXiv preprint arXiv:2307.03591_ (2023).
  * Liu et al. (2023b) Meng Liu, Ke Liang, Bin Xiao, Sihang Zhou, Wenxuan Tu, Yue Liu, Xihong Yang, and Xinwang Liu. 2023b.  Self-supervised temporal graph learning with temporal and structural intensity alignment.  _arXiv preprint arXiv:2302.07491_ (2023).
  * Liu et al. (2023c) Meng Liu, Yue Liu, Ke Liang, Siwei Wang, Sihang Zhou, and Xinwang Liu. 2023c.  Deep Temporal Graph Clustering.  _arXiv preprint arXiv:2305.10738_ (2023).
  * Liu et al. (2022b) Meng Liu, Jiaming Wu, and Yong Liu. 2022b.  Embedding global and local influences for dynamic graphs. In _Proceedings of the 31st ACM International Conference on Information and Knowledge Management_. 4249–4253.
  * Liu et al. (2023a) Yue Liu, Ke Liang, Jun Xia, Sihang Zhou, Xihong Yang, , Xinwang Liu, and Z. Stan Li. 2023a.  Dink-Net: Neural Clustering on Large Graphs. In _Proc. of ICML_.
  * Liu et al. (2022a) Yue Liu, Wenxuan Tu, Sihang Zhou, Xinwang Liu, Linxuan Song, Xihong Yang, and En Zhu. 2022a.  Deep Graph Clustering via Dual Correlation Reduction. In _Proceedings of the AAAI Conference on Artificial Intelligence_ , Vol. 36. 7603–7611.
  * Liu et al. (2022c) Yue Liu, Jun Xia, Sihang Zhou, Siwei Wang, Xifeng Guo, Xihong Yang, Ke Liang, Wenxuan Tu, Z. Stan Li, and Xinwang Liu. 2022c.  A Survey of Deep Graph Clustering: Taxonomy, Challenge, and Application.  _arXiv preprint arXiv:2211.12875_ (2022).
  * Liu et al. (2023d) Yue Liu, Xihong Yang, Sihang Zhou, and Xinwang Liu. 2023d.  Simple contrastive graph clustering.  _IEEE Transactions on Neural Networks and Learning Systems_ (2023).
  * Liu et al. (2023e) Yue Liu, Xihong Yang, Sihang Zhou, Xinwang Liu, Zhen Wang, Ke Liang, Wenxuan Tu, Liang Li, Jingcan Duan, and Cancan Chen. 2023e.  Hard Sample Aware Network for Contrastive Deep Graph Clustering. In _Proc. of AAAI_.
  * Ng et al. (2002) Andrew Y Ng, Michael I Jordan, and Yair Weiss. 2002\.  On spectral clustering: Analysis and an algorithm. In _Advances in neural information processing systems_. 849–856.
  * Nie et al. (2016a) Feiping Nie, Jing Li, Xuelong Li, et al. 2016a.  Parameter-free auto-weighted multiple graph learning: a framework for multiview clustering and semi-supervised classification.. In _IJCAI_. 1881–1887.
  * Nie et al. (2016b) Feiping Nie, Xiaoqian Wang, Michael Jordan, and Heng Huang. 2016b.  The constrained laplacian rank algorithm for graph-based clustering. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 30.
  * Nie et al. (2020) Feiping Nie, Zheng Wang, Lai Tian, Rong Wang, and Xuelong Li. 2020.  Subspace sparse discriminative feature selection.  _IEEE Transactions on Cybernetics_ (2020).
  * Nie et al. (2011) Feiping Nie, Zinan Zeng, Ivor W Tsang, Dong Xu, and Changshui Zhang. 2011.  Spectral embedded clustering: A framework for in-sample and out-of-sample spectral clustering.  _IEEE Transactions on Neural Networks_ 22, 11 (2011), 1796–1808.
  * Ou et al. (2020) Qiyuan Ou, Siwei Wang, Sihang Zhou, Miaomiao Li, Xifeng Guo, and En Zhu. 2020\.  Anchor-based multiview subspace clustering with diversity regularization.  _IEEE MultiMedia_ 27, 4 (2020), 91–101.
  * Peng et al. (2022) Yifan Peng, Siddharth Dalmia, Ian Lane, and Shinji Watanabe. 2022.  Branchformer: Parallel mlp-attention architectures to capture local and global context for speech recognition and understanding. In _International Conference on Machine Learning_. PMLR, 17627–17643.
  * Ren et al. (2012) Yazhou Ren, Guoji Zhang, Guoxian Yu, and Xuan Li. 2012\.  Local and global structure preserving based feature selection.  _Neurocomputing_ 89 (2012), 147–157.
  * Ren and Sun (2020) Zhenwen Ren and Quansen Sun. 2020.  Simultaneous global and local graph structure preserving for multiple kernel clustering.  _IEEE transactions on neural networks and learning systems_ (2020).
  * Shi et al. (2021) Shaojun Shi, Feiping Nie, Rong Wang, and Xuelong Li. 2021\.  Fast multi-view clustering via prototype graph.  _IEEE Transactions on Knowledge and Data Engineering_ (2021).
  * Sun et al. (2021) Mengjing Sun, Pei Zhang, Siwei Wang, Sihang Zhou, Wenxuan Tu, Xinwang Liu, En Zhu, and Changjian Wang. 2021\.  Scalable Multi-view Subspace Clustering with Unified Anchors. In _Proceedings of the 29th ACM International Conference on Multimedia_. 3528–3536.
  * Wan et al. (2022) Xinhang Wan, Jiyuan Liu, Weixuan Liang, Xinwang Liu, Yi Wen, and En Zhu. 2022\.  Continual Multi-view Clustering. In _Proceedings of the 30th ACM International Conference on Multimedia_. 3676–3684.
  * Wan et al. (2023b) Xinhang Wan, Jiyuan Liu, Xinwang Liu, Siwei Wang, Yi Wen, Tianjiao Wan, Li Shen, and En Zhu. 2023b.  One-step Multi-view Clustering with Diverse Representation.  arXiv:2306.05437 [cs.LG]
  * Wan et al. (2023a) Xinhang Wan, Xinwang Liu, Jiyuan Liu, Siwei Wang, Yi Wen, Weixuan Liang, En Zhu, Zhe Liu, and Lu Zhou. 2023a.  Auto-weighted Multi-view Clustering for Large-scale Data.  arXiv:2303.01983 [cs.LG]
  * Wan et al. (2023c) Xinhang Wan, Bin Xiao, Xinwang Liu, Jiyuan Liu, Weixuan Liang, and En Zhu. 2023c.  Fast Continual Multi-View Clustering with Incomplete Views.  arXiv:2306.02389 [cs.LG]
  * Wang et al. (2015a) Chang-Dong Wang, Jian-Huang Lai, and S Yu Philip. 2015a.  Multi-view clustering based on belief propagation.  _IEEE Transactions on Knowledge and Data Engineering_ (2015).
  * Wang et al. (2022) Siwei Wang, Xinwang Liu, Li Liu, Wenxuan Tu, Xinzhong Zhu, Jiyuan Liu, Sihang Zhou, and En Zhu. 2022\.  Highly-efficient incomplete large-scale multi-view clustering with consensus bipartite graph. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 9776–9785.
  * Wang (2021) Yang Wang. 2021\.  Survey on deep multi-modal data analytics: Collaboration, rivalry, and fusion.  _ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM)_ 17, 1s (2021), 1–25.
  * Wang et al. (2015b) Yang Wang, Xuemin Lin, Lin Wu, Wenjie Zhang, Qing Zhang, and Xiaodi Huang. 2015b.  Robust subspace clustering for multi-view data by exploiting correlation consensus.  _IEEE Transactions on Image Processing_ (2015).
  * Wen et al. (2021b) Guoqiu Wen, Yonghua Zhu, Linjun Chen, Mengmeng Zhan, and Yangcai Xie. 2021b.  Global and Local Structure Preservation for Nonlinear High-dimensional Spectral Clustering.  _Comput. J._ 64, 7 (2021), 993–1004.
  * Wen et al. (2021a) Jie Wen, Zhihao Wu, Zheng Zhang, Lunke Fei, Bob Zhang, and Yong Xu. 2021a.  Structural deep incomplete multi-view clustering network. In _Proceedings of the 30th ACM International Conference on Information & Knowledge Management_. 3538–3542.
  * Wen et al. (2019) Jie Wen, Zheng Zhang, Yong Xu, Bob Zhang, Lunke Fei, and Hong Liu. 2019\.  Unified embedding alignment with missing views inferring for incomplete multi-view clustering. In _Proc. of AAAI_.
  * Wen et al. (2020) Jie Wen, Zheng Zhang, Zhao Zhang, Lunke Fei, and Meng Wang. 2020.  Generalized incomplete multiview clustering with flexible locality structure diffusion.  _IEEE transactions on cybernetics_ (2020).
  * Wu et al. (2021) Haiping Wu, Bin Xiao, Noel Codella, Mengchen Liu, Xiyang Dai, Lu Yuan, and Lei Zhang. 2021.  Cvt: Introducing convolutions to vision transformers. In _Proceedings of the IEEE/CVF International Conference on Computer Vision_. 22–31.
  * Wu et al. (2020) Zhanghao Wu, Zhijian Liu, Ji Lin, Yujun Lin, and Song Han. 2020.  Lite transformer with long-short range attention.  _arXiv preprint arXiv:2004.11886_ (2020).
  * Xie et al. (2019) Deyan Xie, Xiangdong Zhang, Quanxue Gao, Jiale Han, Song Xiao, and Xinbo Gao. 2019\.  Multiview clustering by joint latent representation and similarity learning.  _IEEE transactions on cybernetics_ 50, 11 (2019), 4848–4854.
  * Xie et al. (2020) Yuan Xie, Bingqian Lin, Yanyun Qu, Cuihua Li, Wensheng Zhang, Lizhuang Ma, Yonggang Wen, and Dacheng Tao. 2020\.  Joint deep multi-view learning for image clustering.  _IEEE Transactions on Knowledge and Data Engineering_ (2020).
  * Xu et al. (2023) Jie Xu, Chao Li, Liang Peng, Yazhou Ren, Xiaoshuang Shi, Heng Tao Shen, and Xiaofeng Zhu. 2023.  Adaptive Feature Projection With Distribution Alignment for Deep Incomplete Multi-View Clustering.  _IEEE Transactions on Image Processing_ 32 (2023), 1354–1366.
  * Xu et al. (2022) Jie Xu, Huayi Tang, Yazhou Ren, Liang Peng, Xiaofeng Zhu, and Lifang He. 2022\.  Multi-level feature learning for contrastive multi-view clustering. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 16051–16060.
  * Yang et al. (2020) Ben Yang, Xuetao Zhang, Feiping Nie, Fei Wang, Weizhong Yu, and Rong Wang. 2020\.  Fast multi-view clustering via nonnegative and orthogonal factorization.  _IEEE Transactions on Image Processing_ 30 (2020), 2575–2586.
  * Yang et al. (2019) Jufeng Yang, Jie Liang, Kai Wang, Paul L Rosin, and Ming-Hsuan Yang. 2019.  Subspace clustering via good neighbors.  _IEEE transactions on pattern analysis and machine intelligence_ 42, 6 (2019), 1537–1544.
  * Yang et al. (2022a) Xihong Yang, Yue Liu, Sihang Zhou, Xinwang Liu, and En Zhu. 2022a.  Mixed Graph Contrastive Network for Semi-Supervised Node Classification.  _arXiv preprint arXiv:2206.02796_ (2022).
  * Yang et al. (2022b) Xihong Yang, Yue Liu, Sihang Zhou, Siwei Wang, Xinwang Liu, and En Zhu. 2022b.  Contrastive Deep Graph Clustering with Learnable Augmentation.  _arXiv preprint arXiv:2212.03559_ (2022).
  * Yang et al. (2023) Xihong Yang, Yue Liu, Sihang Zhou, Siwei Wang, Wenxuan Tu, Qun Zheng, Xinwang Liu, Liming Fang, and En Zhu. 2023.  Cluster-guided Contrastive Graph Clustering Network. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 37. 10834–10842.
  * Yin et al. (2018) Ming Yin, Shengli Xie, Zongze Wu, Yun Zhang, and Junbin Gao. 2018.  Subspace clustering via learning an adaptive low-rank graph.  _IEEE Transactions on Image Processing_ (2018).
  * Zhang et al. (2018a) Changqing Zhang, Huazhu Fu, Qinghua Hu, Xiaochun Cao, Yuan Xie, Dacheng Tao, and Dong Xu. 2018a.  Generalized latent multi-view subspace clustering.  _IEEE transactions on pattern analysis and machine intelligence_ (2018).
  * Zhang et al. (2015) Changqing Zhang, Huazhu Fu, Si Liu, Guangcan Liu, and Xiaochun Cao. 2015.  Low-rank tensor constrained multiview subspace clustering. In _Proceedings of the IEEE international conference on computer vision_. 1582–1590.
  * Zhang et al. (2017) Changqing Zhang, Qinghua Hu, Huazhu Fu, Pengfei Zhu, and Xiaochun Cao. 2017.  Latent multi-view subspace clustering. In _Proc. of CVPR_.
  * Zhang et al. (2022) Junpu Zhang, Liang Li, Siwei Wang, Jiyuan Liu, Yue Liu, Xinwang Liu, and En Zhu. 2022.  Multiple Kernel Clustering with Dual Noise Minimization. In _Proceedings of the 30th ACM International Conference on Multimedia_ (Lisboa, Portugal) _(MM ’22)_. Association for Computing Machinery, New York, NY, USA, 3440–3450.  https://doi.org/10.1145/3503161.3548334
  * Zhang et al. (2020) Pei Zhang, Siwei Wang, Jingtao Hu, Zhen Cheng, Xifeng Guo, En Zhu, and Zhiping Cai. 2020.  Adaptive Weighted Graph Fusion Incomplete Multi-View Subspace Clustering.  _Sensors_ (2020).
  * Zhang et al. (2018b) Zheng Zhang, Li Liu, Fumin Shen, Heng Tao Shen, and Ling Shao. 2018b.  Binary multi-view clustering.  _IEEE transactions on pattern analysis and machine intelligence_ 41, 7 (2018), 1774–1782.