Multi-view Subspace Clustering on Topological Manifold
Authors: Shudong Huang
Hongjie Wu
Yazhou Ren
Ivor Tsang
Zenglin Xu
Wentao Feng
Jiancheng Lv
Venue: NeurIPS 2022 Accept (2022)
Keywords: Subspace Clustering
Multi-view Learning
Topological Manifold Learning

Abstract: Multi-view subspace clustering aims to exploit a common affinity representation by means of self-expression. Plenty of works have been presented to boost the clustering performance, yet seldom considering the topological structure in data, which is crucial for clustering data on manifold. Orthogonal to existing works, in this paper, we argue that it is beneficial to explore the implied data manifold by learning the topological relationship between data points. Our model seamlessly integrates multiple affinity graphs into a consensus one with the topological relevance considered. Meanwhile, we manipulate the consensus graph by a connectivity constraint such that the connected components precisely indicate different clusters. Hence our model is able to directly obtain the final clustering result without reliance on any label discretization strategy as previous methods do. Experimental results on several benchmark datasets illustrate the effectiveness of the proposed model, compared to the state-of-the-art competitors over the clustering performance.

Multi-view Subspace Clustering on Topological Manifold
Shudong Huang', Hongjie Wu':
Yazhou Ren?, Ivor W. Tsang', Zenglin Xu', Wentao Feng' Jiancheng Lv
'College of Computer Science, Sichuan University, China
SSchool of Computer Science and Engineering, UESTC, China
*Centre for Frontier Al Research, STAR,, Singapore "ccoool of Computer Science and Technology, Harbin Institute of Technology Shenzhen, China
(huangsd, ft.feng202,, 1vjiancheng) @scu. edu. en, wuhongjie@0 1e0ggmmm111@mmmmll1 yazhou. yazhou. www.ueennneeeeeeem .du.cn, en, ivor. tsang@gmail com, xuzenglin@hit, www.eniiiiiutiuu.eee.mmemm
180gmail. com,
Abstract
Multi-view subspace clustering aims to exploit common affinity representation by means of self-expression. Plenty of works have been presented to boost the clustering performance, yet seldom considering the topological structure in data, which is crucial for clustering data on manifold. Orthogonal to existing works, in this paper, we argue that it is beneficial to explore the implied data manifold by learning the topological relationship between data points. Our model seamlessly in- tegrates multiple affinity graphs into a consensus one with the topological relevance considered. Meanwhile, we manipulate the consensus graph by a connectivity constraint such that the connected components precisely indicate different clusters. Hence our model is able to directly obtain the final clustering result without reliance on any label discretization strategy as previous methods do. Experimental results several benchmark datasets illustrate the effectiveness of the proposed model, compared to the state-of-the-un competitors over the clustering performance.
Introduction
With the evolution of multimedia, large amounts of data represented by multiple types (i.e., views). A document, for example, can be presented by images, audio, text. Likewise, a text can be expressed in different languages [1]. In order integrate the complementary information among multiple views, numerous sophisticated multi-view clustering algorithms have been proposed [2, 3], which typically produce better results than single-view clustering [4, 5].
Over the past years, reffsseprennnntooon subspace clustering methods, which assume that each data point can be reconstructed by linear combination of other data points, have gained broad attention. The seff-represnntation property able to capture the heterogeneous relationships between data and therefore produces excellent clustering results [6]. Meanwhile, self-reprreennation property based multi-view subspace clustering algorithms have been developed up to now [7]. For instance, diversity- induced multi-view subspace clustering (DiMSC) [8] adopts the Hilbert-Schmidt independence criterion (HSIC) as a diversity term to measure the dependence of different views. By minimizing the diversity term, the subspace representations are compelled be distinct from each other. Instead of integrating multi-view graphs into consensus one, [9] involves the spectral clustering into their object function derive unified indicator matrix. Therefore, the consistent clustering results of
"qqual contribution. CCoresponning author.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

data points in different views are ensured. [10] separates the subspace representations of different views by a shared consistent representation and a set of specific representations, which is expected to better accommodate real-world data. To eliminate the redundant information of data observations or kernel matrices, [11] utilizes eigendecomposition to get the robust data representations, which helps to obtain the consensus representations of low redundancy and better clustering results. Lately, number of anchor-based multi-view subspace clustering methods [12-14] draw significant attention because they can achieve promising performance with large reduction in storage and computational time.
Despite the significant progress made by the aforementioned methods, there are still drawbacks that can be modified. On one hand, these methods do not consider the manifold topological struc- ture. Considering that real-world datasets are usually sampled from nonlinear low-dimensional manifold [15-17], it essential to explicitly explore the topological relationship for clustering data on manifold. On the other hand, existing multi-view clustering methods usually adopt predefined similarity graphs. That is, the graph learning and subsequent multi-view clustering in these methods separated. Thus the constructed graph may not be suitable, let alone optimal, for the subsequent clustering. It is preferred to automatically learn the similarity information between data points and involve graph learning
part of the optimization procedure.
Regrading the deficiencies mentioned above, in this paper we argue that is beneficial to explore the implied data manifold by learning the topological relationship between data points. To do so, we propose to seamlessly integrate multiple affinity graphs into a consensus one with the topological relevance considered. Besides, we manipulate the consensus graph by connectivity constraint such that the connected components precisely indicate different clusters. Hence our model is able to directly obtain the final clustering result without reliance on any label discretization step. By leveraging the subtasks of affinity graph constructing, topological relevance learning, and discrete label partitioning into unified framework, each subtask can be enhanced in mutual reinforcement manner. An alternating iterative algorithm is carefully designed to solve the optimization problem of the proposed model. Experimental results on several benchmark datasets demonstrate the effectiveness of our method.
Notations. We use boldface upperease letter, e.g., M. to denote the matrix. M, represents the ij-th element of M. I-Ile represents the Frohenius norm of matrix and is a column vector with all its elements equal to I. I denotes the identity matrix with proper size.
2 Preliminary
It is well-known that real-world datasets are often sampled from nonlinear low-dimensional manifold which is embedded in the high dimensional ambient space [15, 18-20j. Hence it is necessary to exploit the manifold structure implied within the original data.
Recently, [17] pointed out that is preferred to boost the learning performance by making use of the manifold topological structure than the Fuclidean structure. It is based on a simple yet intuitive assumption that the topological connectivities between individuals could be propagated from near to far. In other words, the spatial similarity between two individuals may be small, but their topological relevance to each other would be high if they are linked by consecutive neighbors. A visualized example is given in Figure 1. For better illustration, we visualize the topological relevance in both a 2D version (left subfigure) as well as a 3D version (right subfigure). Taking the left subfigure as an example, although the dark blue and light grey points with low similarity in terms of spatial location and velocity, they are closely connected to each other considering the high topological relevance between them.
Instead of relying on the Fuclidean structure, it is naturally expected to learn a more suitable manifold topological structure such that the intrinsic similarities can be explicitly uncovered. Considering that data points with a high similarity would share similar topological relevance, given a predefined similarity graph Z E g=Xa, where n is the number of data points, [17] investigated the topological structure of data by solving
min 2
Σ
Zit (S.
Swx)² 3 ||S 11/2
(1)
i.,k=1
2

---

High
bigh stoilartes
Low
Similarity on location and velocity
Similarity on topological structure
Figure 1: Illustration of topological relevance. Left: the dark blue point and the light gray point show low similarity on spatial velocity, but they keep high topological relevance to each other [17]. Right: closer distance in the Euclidean structure does not mean higher topological relevance.
where 3 a trade-off parameter. i, j. and are data point indexes. S represents the target topological relationship matrix, and Sij denotes the data point j's topological relevance i. Note that the first term in Eq. (1) is essentially smoothness constraint that fits the above assumption, i.e., it guarantees the data points j and share similar topological relationship with data point they are similar. And the second term is incorporated to prevent the trivial solution. According to Eq. (I), the topological consistency be propagated through neighbors with high similarities, and the distant data points will keep close relationship if they are linked by consecutive neighbors. Notwithstanding, Eq. (1) is fed with predefined graph, which would lead performance degradation as the predefined graph might not be optimal for subsequent learning procedures. Hence it is preferred to automatically learn similarity graphs from data.
Self-expression has been widely employed to recover the similarity graph in the form of subspace representation [6]. Given dataset X the self-expression based clustering problem can be defined as
[1, X2, ... x.,] E mxx with data points and m features,
min |X
XZ
2 + Z
(2)
s.t. Z 2 0, diag (Z) 0,
where a is a trade-off parameter and diag (Z) represents the vector consists of diagonal elements of Z. It is obvious that Eq. (2) learns the neighboring data points of data point and the corre- sponding weights by the sparse reconstruction from other data points. Moreover, the learned sparse representation enjoys several nice properties, e.g., the datum-adaptive ability and robustness to noise [21, 22].
Based on Eq. (2), can easily extend it to multi-view formulation when dealing with the multi-view data [X (1) (2) x(m),, which can be formed as
min (()
(e)
(())
+a
Z
F
(3)
8. (1) 2 0, diag (z()) = =0,
where m number of views, and (z) 5 v S m) denotes the affinity representation that automatically learned from the v-th view.
The Proposed Methodology
To explicitly incorporate the manifold topological structure into multi-view clustering, we propose to
learn topological relation graph based on Eq. (1). With the subspace representation automatically

---

obtained in Eq. (3), we arrive at
x (v) z (0)
+ 2(1)
+ 2 1=1
Wb
Σ
(1) jk
(Sij S + +.311 B|| 1|p
iJAK=1
s.1. z 2 0, diag (Z = 0, s 1, 20,
(4)
where the consensus graph S reveals the topological relationship across multiple views and is further constrained to be non-nnn -ngaative and the sum of each row is 1. w, is the weight for the e-th views, which can be considered as a constant within each iteration and will be introduced later.
Nevertheless, the learned S in Eq. (4) does not contain explicit cluster structures. It is expected that the consensus graph contains exactly e connected components where is the number of clusters. sounds unrealistic that such clear structured S could be achieved out of thin air. Fortunately, we can solve this problem with a useful connectivity constraint. Moreover, in Eq. (4), we see that if the j-th data point is connected with many similar neighbors, it will largely affect the objective value. Thus we tend to normalize the objective function so that each point can be treated equally. Considering the above concerns, propose normalized version of Eq. (4) with additional connectivity constraint, which can be finally formulated as
(1)
X (v) (())
7
min Z(2)
+ a
==1
2
(v)
Szy
Sik
+B I|
(5)
Wh
D (r)
VD (v)
111.==1
s.t. Z (1) 2 0, diag (z() = O, s
1, 2 0, rank (Ls) =
where (vv) is the degree matrix of (z)) Lg is the Laplacian matrix of S, and rank (Ls) = is rank constraint that manipulates the target graph S containing exactly connected components. In this way, the subsequent label discretization step can be avoided since each connected component precisely indicates individual cluster. As for the weight w, of each view, set in a self-tuned way inspired by [23, 24]:
2
W.y 1
n
(())
Sy
S.k (
(6)
jk
(v) kk
ij,k=1
It is worth mentioning the salient contributions of our model formulated in Eq. (5) follows:
Orthogonal to other multi-view subspace clustering approaches. our model explicitly ex- plores the implied data manifold by learning the topological relationship across multiple views. To the best of our knowledge, this is the first work that delicately incorporates the topological structure in multi-view subspace clustering.
Our model flawlessly integrates the subtasks including affinity graph constructing, manifold topological structure learning, and discrete label partitioning into unified framework. Hence our model is an end-to-end single-stage learning paradigm.
An alternating iterative algorithm is introduced to solve the optimization problem. Exper- iments on several benchmark datasets illustrate the effectiveness of the proposed model, compared to the state-of-the-art competitors over the clustering performance.
3.1 Algorithm Derivation
In order to solve the problem in Eq. (5), we derive optimization algorithm optimize the objective function. Since the corresponding optimization problem not jointly convex in variables, we choose to solve it by updating one variable while fixing other variables.

---

3.1.1
Update (0) for Each View
For (()), the corresponding problem is
2
min 2(0)
x - x (
2
+ Σ w
Σ
Sū
S
i,j.==1
VD
D
(v)
(7)
kk
8.1. z(0) 2 0, ding (z(.) = O.
Eq. (7) can be rewritten as
Tr ( aTr (z(0)(()²) Tr ST I I- D-D( (0))))) S
min (
(8)
s.t. ((0) 2 0, diag (Z(1) =
where ())) (x(*) x (z) (x(*) x z()) T. Taking the derivative of Eq. (8) w.r.t Z(v)
and setting the derivative to zero, we get following solution
Z max (2Kl + -aII
(2K()) + +w, "G",GG")).
where G D S. and K(w) (v) ((0) be treated a liner kernel. Note that the nonlinear
kernel can also be applied in our model.
3.1.2 Update S
Dropping the unrelated terms of Eq. (5) w.r.t. S, thus need to solve
min- S
Wy
jk
(v)
Siy
(D)
D (w)
+ +BI I|
(10)
==1
1.j.A
jj
Rkk
s.l. S
1, stj 0, rank (Ls) =
We that Eq. (10) is difficult to solve due to the rank constraint. Let or (Ls) be the i-th smallest eigenvalue of Lg. The constraint rank (Ls) = n - would be satisfied if >i=1 0; (Ls) = 0 since Lg is a positive semidefinite matrix. According to Ky Fan's Theorem [25]:
Σ o (Ls) = min Tr LF
F
(11)
s.t. FER FF
where F E Raxe denotes the cluster indicator matrix. We incorporate the constraint term Σt σi (Ls), i.e, minf Ir L5F), into the cost function, thus Eq. (10) can be rewritten as
min 2
W
(1)
S
Sik
+ + I1 + 2XIr (F" LsFF
(12)
T = 1, Sij 2 0, s.t.
where À is a self-tuned parameter.
Based on Eq. (12), first we search the optimal solution of F, which can be obtained by solving
Tr Ls)L,F),
min FC FTF-
(13)
which is essentially spectral problem and F can be achieved by calculating the e eigenvectors of Lş corresponding to the smallest eigenvalues.
5

---

Algorithm 1: Algorithm to solve Eq. (18)
Input: nonzero matrix A and nonzero vector b. Set < < initialize v > 0, q.
Output: S.
1: repeat
2: Update p according to (20).
3: Update according to (21).
4: Update 1) f pT)
5: Update f + 7) (s: - -p).
6:
until converge
Algorithm 2: The Algorithm for Eq. (5)
Input: Mieti-view data (x(1) (() ,..., ,..,,,,.)))) X(m)
with m views, cluster number e, parameters a and
B.
Initialize the weight of each view w. m
Initialize the affinity graph Z(() according to Eq. (2).
Initialize the consensus graph. S = =Er= w.Z())
Output: The indicator matrix R with exactly e connected components.
1: repeat
2: Update (()) according to Eq. (9).
3: Update S by Algorithm 1.
4: Update according to Eq. (13).
5: Update wa according to Eq. (6).
6: until converge
Then we search the optimal solution of S. It is clear that Eq. (12) w.r.t. S can be formulated in vector form as
2
m
S
S
n + A
min 8
Wy
jk
+
SSi
1,))
ff
f,
Sij
1====
VD
D
Kk
j=1
j=1
s.t.
8ig 0.
(14)
Note that Eq. (14) independent for different i, thus we have the following compact formulation
m
Z ((v) )) s; 3 [|s:
min 20,5 1=1
We I (
c; 112 + s u,
(15)
where c; denotes the i-th column vector of identity matrix I, and u, represents a vector with its j-th
element = > [fa - 1
Denote A = >' Wy I - D(v) $ (0)) D(v)
(v) - #) + 3I and b = 23e; Eq. (15) is equivalent
to optimizing
5/ As; sf b.
(16)
2055 1=1
We Eq. (16) is essentially quadratic optimization problem, hence it can be solved with the classical augmented Lagrangian multiplier (ALM) method [26]. Specifically, we can solve Eq. (16) by tackling counterpart
min By 2,200. 1= 1=1,p=s
s b. 8 Ap
(17)
Based on Eq. (17), the corresponding augmented Lagrangian function be defined as
min
$f Ap
s b
7 8; p
(18)
B, s,20,s{1=11p

---

where the second term in Eq. (18) is employed to guarantee that = S;. and q are the penalty coefficient and parameter, respectively.
is clear that we can solve and 8; in an iterative updating way:
1) Update p with fixed s,. The corresponding cost function w.r.t p is
4p =p
?
8; - p
-
1
(19)
17
Setting
0Ce Op 0, we obtain
1 (ATs: + p = S;
(20)
2) Update s; with fixed p. The corresponding cost function w.r.t. S; can be reformulated as
Ap
min $13 2 1=1
P
17 4
(21)
17
which leads to a closed-form solution and can be directly obtained by [21]. According to the ALM principles [26]. 77 can be exaggerated increasingly during each iteration, and is updated by obtain optimal solution for S based on this effective ALM strategy. The detailed algorithm to solve Eq. (18) outlined in Algorithm
< q (s: p). Finally,
Up now, with the variable (()) updated by Eq. (9), updated by Eq. (18), updated by Eq. (13), and w, updated by Eq. (6), the overall algorithm to solve the objective in Eq. (5) can be summarized in Algorithm 2. Owing space limitation, we give the convergence analysis and the time complexity of Algorithm& 2 in the Appendix B and Appendix C, respectively.
Experiments
We evaluate the proposed method by comparing it with following state-of-the-art competitors: Diversity-induced Multi-view Subspace Clustering (DiMSC) [8], Auto-weighted Multiple Graph Learning (AMGL) [27], Multi-view Clustering with Graph Learning (MVGL) [28], Weighted Multi- view Spectral Clustering(
[29], Consistent and Specific Multi-view Subspace Clustering (CSMSC) [10], Graph-based Multi-view Clustering (GMC) [24], Large-scale Multi View Subspace Clustering in linear time (LMVSC) [12], Scalable Multi- Subspace Clustering with unified an- chors (SMVSC) [13], and Multi- View Subspace Clustering via Co-training robust data representation (CoMSC) [11]. The classic graph-based algorithm, spectral clustering (SC) [18], is also included as baseline. We apply SC by making use of the most informative view, i.c., one that achieves the best performance (denoted by SChest).
Table 1: Characteristics of datasets. n, m, and denote the number of samples, views, and clusters, respectively. d, denotes the dimensionality of the features in the w-th view.
Datasct
di
d2
d6
3Sources
169
3
6
3560
3631
3068
MSRC
210
7
24
576
512
256
254
COIL-20
1440
20
1024
3304
6750
Caltech-7
1474
6
7
48
40
254
1984
512
928
100Leaves
1600
100
64
64
64
Caltech-20
2386
6
20
48
40
254
1984
512
928
MNIST
10000
3
10
30
9
30
The experiments are conducted on several benchmark datasets, namely, 3Sources, MSRC, 100Leaves, COIL-20, Caltech-7, Caltech-20, and MNIST. The detailed information of all datasets is given in Appendix The specific characteristics of these datasets are also summarized in Table The parameters for comparison algorithms are set according to the recommendations in their corresponding paper. The parameter settings of our model will introduced later. We repeat all algorithms 10 times to eliminate the effect of random factors, and report the average scores. Four widely-used metrics, i.e. clustering accuracy (ACC), Normalized Mutual Information (NMI), Purity, and F-score, are used to achieve a comprehensive evaluation.
7

---

Table 2: Clustering results of all methods different datasets (%). second best performance is underlined.
The best performance is bolded, and the
Datasel
SCheot
DiMSC
AMGL
MVGL
WMSC
CSMSC
GMC
LMVSC
SMVSC
CoMSC
Ours
ACC.
MSources
53.67
76.33
44.14
42.54
57.75
78. 34
69.23
50.18
43.14
64.26
81.07
MSRC
58.95
72.38
70.67
70.48
69.00
80.48
74.76
74.71
81.43
80.86
85.24
COIL-20
72.75
76.15
79.30
75.21
76.58
75.06
79.10
75.56
61.07
71.90
80.42
Caltech-7
48.58
41.51
64.66
56.38
38.95
62.08
69.20
60.91
57.22
64.65
77.61
100Leaves
69.62
47.87
79.00
78.23
76.78
82.38
67.32
38.03
78.75
83.56
Caltech-21
41.74
28.45
49.69
57.29
33.98
47.47
45.64
47.10
61.36
53.32
68,99
MNIST
52.74
51.79
85.10
30.55
51.91
50.64
84,37
71.45
77.16
69.65
87.44
3Sources
49.99
63.77
18.35
27.11
49.33
70.75
54.80
30.51
24.21
59.32
70.81
MSRC
46.81
60.08
66.80
58.18
59.53
71.43
74.21
65.55
70.18
74.08
77.35
COIL-20
81.91
83.02
91.43
83.80
84,16
84.17
91.79
83.24
73.06
81.42
91,90
Caltech-7
28.99
32.10
52.76
51.63
28.08
51.82
60.56
44.33
44.96
55.96
64.51
100Lcaves
86.17
70.98
90.48
90.44
84.64
64.92
90.42
92.48
Caltech-20
45.47
27.59
54.47
58.59
41.81
57.83 83
38.46
49.21
57.56
59.38
56.53
MNIST
47.13
34.08
76.08
24.04
47.31
46.13
76.39
63.46
62,40
64,80
77.49
Purity
3oources
49.94
71,48
84.62
MSRC
60.00
72.38
74.14
70.48
71.38
80.48
79.05
75.33
81.43
81.76
85,24
COIL-20
75.25
78.94
84.37
77.78
78.19
77.56
84.79
79.08
61.72
78.94
85.00
Caltech-7
79.58
70.98
85.80
72.73
88.60
100Leaves
72.94
50.47
83.42
57.44
80.55
79.
85.06
77.39
39.49
85.44
86.01
Caltech-21 20
70.54
54.83
68.33
74.85
67.29
77.91
55.49
52.48
71.32
61.12
75.02
MNIST
56.27
52.37
85.43
30.55
55.94
54.22
84.37
77.00
77.16
76.38
87.44
3Sources
48.49
70.68
38.18
44.75
50.79
60.47
41.87
38.46
60.49
75.25
MSRC
43.88
58.61
62.22
54.56
57.52
70.13
69.68
64.71
69.36
71.35
75.29
COIL-20
69.09
72.27
75.95
71.43
73.40
70.75
79.42
70.23
53.68
66.33
82.29
Caltech-7
40.01
42.26
6141
59.77
37.78
61.74
72.17
56.37
55.46
64,92
79.77
100Lcaves
61.94
33.12
59.14
8.58
72.63
69.64
50.42
58.20
23,20
73.19
69.29
Caltech-20
33.21
20.10
39.78
47.05
30,54
42.30
34.03
39.78
66.27
47.72
53.13
MNIST
32.80
74.99
74.43
62.39
77.67
(a) DIMSC
(b) MVGL
CSMSC
(d) CoMSC
(e) Ours
Figure 2: Target consensus graph of dataset 1c0lea (first categories) learned by different methods.
4.1 Results and Analysis
The clustering performance all methods on four metrics is shown in Table As we see, our proposed method achieves the best performance in the majority of cases, which validates the effective- ness of our method. Moreover, it obvious that the improvement remarkable. On dataset MSRC, for instance, method even achieves substantial improvements around 4.7%, 4.2%. 4.3%, and 10.5% over the most competitive methods in terms of ACC, NMI, Purity, and F-score, respectively. Note that DiMSC, CSMSC, LMVSC, SMYSC, and CoMSC are all multi-view subspace clustering methods that adopt the Euclidean structure. From the results, it is obvious our method that employs manifold topological structure is much better than that in terms of clustering performance, which verifies our assumption that manifold topological structure is more suitable to explicitly uncover the intrinsic similarities. Taking the dataset 100Leaves as example, we visualize the target graph learned by different methods. For better visualization, we plot the first seven categories of dataset 100Leaves Figure As can be seen, DiMSC cannot even find the block diagonal structure of the target graph. MVGL, CSMSC, and CoMSC are able to search the block diagonal structure but contain lots of noise obviously. with much clear clustering structure.
contrary, our model almost achieves pure structured graph

---

(a) Caltech-7
(b) 100Leaves
(c) Caltech-20
Figure 3: NMI w.r.t. and B.
4.2 Parameter Analysis
This section investigates the sensitivity of our method with respect to different parameter settings. Note that À involved in Eq. (12) self-tuned parameter, which can be in a heuristic way. That is, we can initialize to random positive value (e.g., À = 10), if the connected components of S is greater than c in current iteration, we set <- 3. and if is less than c, we set + 2A. This strategy guarantees S contains clear clustering structure with exact connected components. Hence we only need to set the parameters a and / properly. Here we empirically search them in the range 10.1,0.5,1,5, 10,,0 for simplicity. The clustering performance of three datasets is shown in Figure (owing to space limitation, the results of other datasets are attached in Appendix D), we can find that the clustering results of our method are relatively stable for different parameter settings, which demonstrates the robustness of our model. As introduced before, the target consensus graph S can be treated an indicator matrix, where the points from the same cluster are connected to the same component. Once we obtain S, the cluster label of each data point can be directly assigned without any postprocessing. Hence our method is very stable. In general, we could obtain a promising clustering performance by setting = B = 10 in practical applications.
0.9
1830
2284
1545
2282
NMI
1540
1820
O8
08]
08)
0.7
0.2
2280
0.6
1810
0.0
0.0
10
15
20
10
15
20
5
10
15
20
Iteration
Iteration
Iteratio
(a) 3Sources
(b) MSRC
(c) COIL-20
Figure 4: Convergence speed of our method, where OBJ denotes the objective value.
4.3 Convergence Study
Here we verify the convergence property of the proposed algorithm. The convergence curves along with the corresponding performance of our algorithm on 3Sources, MSRC, and COIL-20 datasets are recorded in Figure 4 (the convergence curves of other datasets are attached in Appendix D), where the red line denotes the NMI of our method and the grey line indicates the objective value. As can see, the proposed optimization algorithm is efficient and converges very fast, usually within 10 iterations, which empirically illustrates the efficiency of the proposed algorithm.
5 Conclusion
In this paper, we propose to explore the implied data manifold by learning the topological relationship between data points. To do so, we seamlessly integrate multiple affinity graphs into consensus one with the topological relevance considered. Besides, manipulate the consensus graph by

---

a connectivity constraint such that the connected components precisely indicate different clusters. Hence our model can directly obtain the discrete result without any postprocessing. An alternating iterative algorithm is carefully designed to solve the optimization problem of the proposed model. Experimental results have shown that (1) manifold topological structure is suitable to explicitly uncover the intrinsic similarities, thus beneficial for multi-view subspace clustering tasks; (2) our model is quite robust with respect to different parameter settings, which demonstrates its stability; (3) the proposed optimization algorithm is very efficient and converges fast. However, note that our model cannot deal with the nonlinear data, which can be considered in future works. As mentioned in Subsection 3.1.1, the kernel strategy would be option to explore nonlinear structure. Furthermore, we are also interested in extending the proposed framework to other machine learning frameworks, such semi- supe--seeeeieed learning and deep learning.
Acknowledgments
We thank the anonymous reviewers for their helpful comments and suggestions. This work is supported by the Key Program of National Science Foundation of China (Grant No. 61836006). partially supported by the National Science Foundation of China under Grant 62 and 62106161. the 111 Project under Grant B21044, and the Sichuan Science and Technology Program under Grants 2021ZDZX0011 and 2022YFG018 188.
References
[1] Chang-Dong Wang, Jian-Huang Lai, and S Yu Philip. Multi-view clustering based on belief propagation. IEEE Transactions on Knowledge and Data Engineering, 1804):1007-1021, 2015.
[2] Changqing Zhang, Huazhu Fu, Qinghua Hu, Xiaochun Cao, Yuan Xie, Dacheng Tao, and Dong Xu. Generalized latent multi-view subspace clustering. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(1):86-99 2018.
[3] Chang Tang, Xinzhong Zhu, Xinwang Liu, Miaomiao Li, Pichao Wang, Changqing Zhang, and Lizhe Wang. Learning a joint affinity graph for multiview subspace clustering. IEEE Transactions on Multimedia, 21(7):124-11736, 2019.
[4] Steffen Bickel and Tobias Scheffer. Multi-view clustering. In Proceedings of the Fourth IEEE International Conference on Data Mining, pages 19-26, 2004.
[5] Shudong Huang, Ivor Tsang, Zenglin Xu, and Jian Cheng Lv. Measuring diversity in graph learning: A unified framework for structured multi-view clustering. IEEE Transactions on Knowledge and Data Engineering, pages 1-15, 2021.
[6] Ehsan Elhamifar and René Vidal. Sparse subspace clustering, In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, volume 6, pages 2790-2797, 2009.
[7] Shudong Huang, Zhao Kang, Ivor W Tsang, and Zenglin Xu. Auto-weighted multi-view clustering via kernelized graph learning. Pattern Recognition, 88:174-184, 2019.
[8] Xiaochun Cao, Changqing Zhang, Huazhu Fu, Si Liu, and Hua Zhang. Diversity-indueed multi-view subspace clustering. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 586-594, 2015.
[9] Hongchang Gao, Feiping Nic, Xuclong Li. and Heng Huang. Multi-view subspace clustering. In Proceedings of the IEEE International Conference on Computer Vision, pages 4238-4244 2015.
[10] Shirui Luo, Changqing Zhang, Wei Zhang, and Xiaochun Cao. Consistent and specific multi- view subspace clustering. In Proceedings of the AAAI Conference on Artificial Intelligence. volume 32, 2018
[11] Jiyuan Liu, Xinwang Liu, Yuexiang Yang, Xifeng Guo, Marius Kloft, and Liangzhong He. Multiview subspace clustering via co-training robust data representation. IEEE Transactions on Neural Networks and Learning Systems, pages 1-13, 2021.
10

---

[12] Zhao Kang, Wangtao Zhou, Zhitong Zhao, Junming Shao, Meng Han, and Zenglin Xu. Large- scale multi-view subspace clustering in linear time. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4412 2020.
[13] Mengjing Sun, Pei Zhang, Siwei Wang. Sihang Zhou, Wenxuan Tu, Xinwang Liu, En Zhu, and Changjian Wang. Scalable multi-view subspace clustering with unified anchors. In Proceedings of the 29th ACM International Conference on Multimedia, pages 3528-3536 2021.
[14] Siwei Wang, Xinwang Liu, Xinzhong Zhu, Pei Zhang, Yi Zhang, Feng Gao, and En Zhu. Fast parameter-free frree multi-vien subspace clustering with consensus anchor guidance. IEEE Transactions on Image Processing, 31:556-568, 2022.
[15] Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. Science, 290(5500):2323-232222 2000.
[16] Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural Computation, 15(6):1373-1396 2003.
[17] Qi Wang, Mulin Chen, and Xuelong Li. Quantifying and detecting collective motion by manifold learning. In Proceedings of the AAAI Conference on Artificial Intelligence, pages 4292-4298, 2017.
[18] Andrew Y Ng. Michael I Jordan, and Yair Weiss. On spectral clustering: analysis and an algorithm. In Advances in Neural Information Processing Systems, pages 849-856, 2001.
[19] Zhenyue Zhang, Jing Wang, and Hongyuan Zha. Adaptive manifold learning. IEEE Transactions on Puttern Analysis and Machine Intelligence, 34(2):253-265 2011.
[20] Ha Quang Minh, Loris Bazzani, and Vittorio Murino. A unifying framework in vector-valued reproducing kernel hilbert spaces for manifold regularization and co-regularized multi-view learning. Journal of Machine Learning Research, 17:1-72, 2016.
[21] Jin Huang, Feiping Nie, and Heng Huang. A new simplex sparse learning model measure data similarity for clustering. In Proceedings of the 24th International Joint Conference on Artificial Intelligence, pages 3569 3375, 2015.
[22] Shudong Huang, Ivor W Tsang. Zenglin Xu, Jiancheng Lv, and Quanhui Liu. Cdd: Multi- view subspace clustering via cross-view diversity detection. In Proceedings of the 29th ACM International Conference on Multimedia, pages 2308-2316, 2021.
[23] Feiping Nie, Guohao Cai, and Xuelong Li. Multi-view clustering and semi-supervised classifica- tion with adaptive neighbours. In Proceedings of the AAAI Conference on Artificial Intelligence, 2017.
[24] Hao Wang, Yan Yang, and Bing Liu. Gme: Graph-based milti-view clustering. IEEE Transac- tions on Knowledge and Data Engineering, 32(6): 16-1129, 2020.
[25] Ky Fan. On a theorem of weyl concerning eigenvalues of linear transformations i. Proceedings of the National Academy of Sciences of the United States of America, 35(11):652665,, 1949.
[26] Dimitri P Bertsekas. Nonlinear programming. Journal of the Operational Research Society, 48(3):334-333 -34,,133,111 1997.
[27] Feiping Nie, Jing Li, and Xuelong Li. Parameter-free auto-weighted multiple graph learning: a framework for multiview elustering and semi-supervised classification. In Proceedings of the Twenty-Fifth International Joint Conference on Artificial Intelligence, pages 1881-1887,2016
[28] Kun Zhan, Changqing Zhang, Junpeng Guan, and Junsheng Wang. Graph learning for multiview clustering. IEEF Transactions on Cybernetics, pages 2887-28959, 2018.
[29] Linlin Zong, Xianchao Zhang, Xinyue Liu, and Hong Yu. Weighted multi-view spectral clustering based on spectral perturbation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
11

---

[30] Feiping Nie, Heng Huang, Xiao Cai, and Chris H Ding. Efficient and robust feature selection via joint 12,1-nrrms -norms minimization. In Advances in Neural Information Processing Systems, pages 1813-1821,
2010. 2010.
[31] Mokhtar S Bazaraa, Hanif D Sherali, and Chitharanjan M Shetty, Nonlinear programming: theory and algorithms. John Wiley Sons, 2013.
[32] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of Machine Learning Research, 9(11), 2008
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 5
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] We provide them as URL.
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] The important details are provided in Section 4.2 and in the code.
(c) Did you report error bars (e.g.. with respect the random seed after running experi- ments multiple times)? [N/A] For fair comparison, we repeat all algorithms 10 times. Considering the appearance of the Table 2, we did not report the standard deviation. (d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix D.I.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes] See Appendix A.
(c) Did you include any new assets either the supplemental material or as URL? [Yes]
We include the proposed algorithm in the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A] All assets used are open-source.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "u-2JvcMJrMd", "reviewer": "Reviewer_wnN6", "summary": "To explore the implied data manifold by learning the topological relationship between data points, this paper proposes to integrate multiple affinity graphs into a consensus one with the topological relevance considered. And to get the discrete result directly, a connectivity constraint is included in the proposed model. Detailed analyses about the optimization and convergence are provided. Solid experimental results are shown to demonstrate the efficiency and stability of the proposed algorithm.", "questions": "\n1. Is there any assumption of the algorithm?\n2. Why there is no synthetic dataset with topological clusters used to verify the performance of the proposed algorithm.\n3. How to determine the range of parameters \\alpha and \\beta?\n4. What are linear data and nonlinear data?", "limitations": "Yes, the authors have addressed the limitations.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.\tThis paper is well organized and the motivation is clear to understand.\n2.\tThe proposed algorithm, the optimization procedure, and the corresponding analysis are convinced.\n3.\tThe empirical evaluation shows significantly better results than existing related clustering algorithms.\nWeaknesses:\n1.\tIt could be better to analyze the properties and behaviors of the proposed algorithms.\n2.\tIntroduction section, the motivation for the proposed algorithm is ambiguous.\n3.\tThere are some writing problems in the current manuscript.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "su9q5sxLJRq", "reviewer": "Reviewer_1etV", "summary": "To explore the benefits of the topological structure in multi-view data, this paper is to integrate multiple affinity graphs into a consensus one with the topological manifold for multi-view subspace clustering. Experimental results on several benchmark datasets illustrate the effectiveness of the proposed model. ", "questions": "Please see the weaknesses.", "limitations": "The novelty of the proposed method seems limited", "rating": 5, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper is well-written and is easy to follow.\n2. This paper proposes a multi-view subspace clustering method based on topological manifold.\n3. The proposed method achieves good performance compared to the state-of-the-art competitors over the clustering performance.\n\nWeakness:\n1. The novelty of the proposed method seems limited since it is simple to combine the multi-view learning formulation in Eq. (4) with the topological structure in Eq. (3). Moreover, Eq. (4) is popular in multi-view subspace clustering and Eq. (3) has been proposed in [17]. Which part is introduced in this paper?\n2. In fact, Fig. 1 is same to the Fig. 2 of [17]. So, please cite this paper in the caption of Fig. 1.\n3. Experiment on the topological manifold is missing. I suggest one experiment to show the topological manifold. \n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "UulMzd57XbK", "reviewer": "Reviewer_2xAj", "summary": "This paper proposes a new multi-view subspace clustering method to exploit a common affinity representation using self-expression property. The proposed model explores the implied data manifold by learning the topological relationship between data points. Then, the model integrates multiple affinity graphs into a consensus one with the topological relevance considered. Experimental results on seven benchmark datasets illustrate the effectiveness of the proposed model.", "questions": "1) Since manifold learning requires a large amount of computational complexity, so how to handle large data sets with the proposed methods? Are there any speedup tricks?\n2) The paper is well written but there are some grammatical errors and expression problems in the paper. It is suggested to conduct further inspections.\n3) The detailed information about experimental settings is missing. Is there a significant difference in parameter settings for different datasets? And please provide different parameter settings for all datasets if possible.\n", "limitations": "Yes, the authors have addressed the limitations in Section 5.", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ The theoretical basis is intuitive and sound, and the optimization algorithm is well designed.\n+ The convergence of the corresponding algorithm is theoretically and empirically guaranteed.\n+ The paper is well written and organized, and the code is available.\n+ Extensive experiments are conducted, and the experimental results of the proposed method are promising.\n\nWeaknesses:\n- The computation complexity of the proposed model seems to be O(n^3). Hence this model is computationally slow on large data sets.\n- The experiments section should be improved. More diverse experimental results, such as ablation analysis, should be available.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept