Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Authors: Xu Zhang
Haoye Qiu
Weixuan Liang
Hui LIU
Junhui Hou
Yuheng Jia
Venue: ICML 2025 poster (2025)
Keywords: Ensemble clustering
generalization performance
bias and diversity
Primary area: general_machine_learning->clustering
TL;DR: This paper investigates the theoretical foundations of ensemble clustering, and instantiates the theory to a new clustering ensemble algorithm.

Abstract: Ensemble clustering has demonstrated great success in practice; however, its theoretical foundations remain underexplored. This paper examines the generalization performance of ensemble clustering, focusing on generalization error, excess risk and consistency. We derive a convergence rate of generalization error bound and excess risk bound both of $\mathcal{O}(\sqrt{\frac{\log n}{m}}+\frac{1}{\sqrt{n}})$, with $n$ and $m$ being the numbers of samples and base clusterings. Based on this, we prove that when $m$ and $n$ approach infinity and $m$ is significantly larger than log $n$, i.e., $m,n\to \infty, m\gg \log n$, ensemble clustering is consistent. Furthermore, recognizing that $n$ and $m$ are finite in practice, the generalization error cannot be reduced to zero. Thus, by assigning varying weights to finite clusterings, we minimize the error between the empirical average clusterings and their expectation. From this, we theoretically demonstrate that to achieve better clustering performance, we should minimize the deviation (bias) of base clustering from its expectation and maximize the differences (diversity) among various base clusterings. Additionally, we derive that maximizing diversity is nearly equivalent to a robust (min-max) optimization model. Finally, we instantiate our theory to develop a new ensemble clustering algorithm. Compared with SOTA methods, our approach achieves average improvements of 6.0\%, 7.3\%, and 6.0\% on 10 datasets w.r.t. NMI, ARI, and Purity. The code is available at https://github.com/xuz2019/GPEC.

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Xu Zhang' Haoye Qiu Weixuan Liang?
Hui Liu
Junhui Hou Yuheng Jia 135
Abstract
1. Introduction
Ensemble clustering has demonstrated great suc- cess in practice; however, its theoretical founda- tions remain underexplored. This paper examines the generalization performance of ensemble clus- tering, focusing on generalization error, excess risk and consistency. We derive convergence rate of generalization error bound and excess risk
Ensemble clustering has attracted great attention in recent years due to its high aceuracy and robustness compared to single clustering algorithm. It integrates multiple clustering results to obtain consensus one instead of the access to the original features of the data, making it broadly applicable across various scenarios (Strehl & Ghosh, 2002). Many scholars have made considerable efforts in this area. For example, Fred and Jain (Fred Jain, 2005) utilized a voting mechanism to generate an n x similarity matrix to describe the relationships between sample pairs (n the number of samples), and applied hierarchical clustering derive the final clustering results. Huang (Huang et al., 2018) realized that the importance of clusters in ensemble pool varies and assigned different weights to various clusters by estimating their uncertainty. Recently, Jia (Jia et al., 2024) utilized the high-confidence relationships to propagate similarity and designed a self-enhancement framework for the similarity matrix. More researches on ensemble clustering can be found in (Topchy et al., 2005; Jia et al., 2019; Yi et al., 2012; Jia et al., 2021; Zhang, 2022; Zhou et al., 2024; Xu et al., 2024; Li & Jia, 2025; Peng et al., 2023).
bound both of (V log + Vv ), with and m be-
m
ing the numbers of samples and base clusterings. Based on this, we prove that when m and n ap- proach infinity and m is significantly larger than log i.e., m, clustering is consistent. Furthermore, recognizing that n and m are finite in practice, the general- ization error cannot be reduced to zero. Thus, by assigning varying weights to finite clusterings, we minimize the eπror between the empirical average clusterings and their expectation. From this, we theoretically demonstrate that to achieve better clustering performance, we should minimize the deviation (bias) of base clustering from its expec- tation and maximize the differences (diversity) among various base clusterings. Additionally, we derive that maximizing diversity is nearly equiv- alent robust (min-max) optimization model. Finally, we instantiate our theory to develop new ensemble clustering algorithm. Compared with SOTA methods, our approach achieves average improvements of 6.0%, 7.3%, and 6.0% on 10 datasets w.r.t. NMI, ARI, and Purity. The code is available at https://gituub.oo/uu/000000 www/xu22019///PEEE
OC, m > log ensemble
Despite significant advances in practice, the theoretical anal- ysis of ensemble clustering remains far from satisfactory. Theoretical analysis of an algorithm helps understand its generalization performance such as generalization error, excess risk and consistency. Generalization error represents the expected loss of an algorithm across the entire data distribution. Excess risk refers to the difference between the expected loss of a model and the expected loss of the optimal model. For consistency, it means that whether a learning algorithm can uncover the true underlying struc- ture of the data as the amount of training data increases. Most previous studies (Pollard, 1981; Bachem et al., 2017; Li et al., 2023) focus on the generalization performance of a single clustering algorithm. To the best of our knowl- edge, only one paper (Liu et al., 2017) has established a generalization error bound in the field of ensemble clus- tering while the excess risk and consistency are neglected. It demonstrates, from the perspective of weighted kemel k-means, that the generalization error bound of ensemble clustering is (n) However, this work fails to con- sider that each base clustering should be treated as random variable, which makes this study fundamentally no different
'School of Computer Science and Engineering, Southeast Uni- versity, Nanjing 210096, China *College of Computer Science and Technology, National | University of Defense Technology, Chang- sha, China 'Shooo of Computing Information Sciences, Saint Francis University, Hong Kong, China *Department Computer Science, City University of Hong Kong, Hong Kong. China Key Laboratory of New Generation Artificial Intelligence Technol- ogy and Its Interdisciplinary Applications (Southeast University). Ministry of Education, China. Correspondence to: Yuheng Jia <yhjia@seu.cdu.cn>.. seu.edu.cn>.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
from the researches of the generalization error of single clustering algorithm. In ensemble clustering, should consider not only the distribution of the data but also the distribution of the base clusterings. This underscores the need to understand the relationship between the number of samples n and the number of base clusterings m. There- fore, in this paper, we investigate the generalization error bound and excess risk bound for ensemble clustering, and + (z)
that the proposed algorithm surpasses other state-of- the-art methods significantly in terms of performance.
2. Preliminaries
In this section, we first briefly introduce key notations and general assumptions. Some of these align with (Von Luxburg et al., 2008) and (Liang al., 2023), where readers can consult for further details. We then proceed to describe the co-association matrix in ensemble clustering.
get the conclusion that both of them are 0( Based on these results, we derive the sufficient conditions for the consistency of ensemble clustering: both m and n approach infinity and m is significantly larger than log n, i.e., m, n + 00, m >> log n.
log v mr
2.1. Notations and General Assumptions
In this paper, let n represent the number of samples and the number of base clusterings. (.) and tr(-) are used to transpose and calculate the trace of matrix. ||A||r is the Frobenius norm of a matrix. ||A||2 donates the spectral norm of a matrix A, |||| ll2 is fz-norm for vector a. A B means B A is positive semi-definite.
Although the above conclusion reveals the relationship be- tween and in ensemble clustering, it is impractical in the real world to actually acquire infinite sample points and base clusterings. Therefore, we further consider whether it is possible to reduce the loss between the empirical average of base clusterings and the expectation of base clustering. By deriving the loss function between them, we reveal that minimizing the deviation of each base clustering with its expectation (bias) and maximizing the differences among various base clusterings (diversity) can promote the cluster- ing performance. However, once the base clusterings are given, both the bias and diversity are fixed. We, therefore, transform ensemble clustering into a learnable problem by weighting the base clusterings to decrease the loss, from which we also find that maximizing diversity is nearly equiv- alent to robust optimization problem. By instantiating our theory, we design new ensemble clustering algorithm and optimize it by the reduced gradient descent method. In summary, the key contributions of this work are:
We assume the sample space X' is compact. Let p(x) and Pa (a:) denote the corresponding true probability distribution and empirical distribution of æ respectively. The dataset S, = (x1,... ... .T,) is collected independently and identi- cally distributed (i.id.) from X' according to the distribution P. We denote T(1) as a base clustering generated i.i.d. by a clustering algorithm. (x;))) is the clustering label of the t-th base clustering for data I3. We denote x(()) as an n x 1 vector and k((1) the number of clusters for 7()),
II = - (m))) is the ensemble base clustering pool with m base clusterings.
2.2. Co-Association Matrix
In clustering, as no supervision is available, the labels we obtain are not aligned with the true labels of the samples. Nonetheless, the similarity relationship between sample pair is unique, we can define the similarity for each base clustering (()) uniquely as
We pioneer the derivation of the generalization error bound and excess risk bound for ensemble clustering, incorporating considerations of both data and cluster- ing distributions. We also establish sufficient condi- tions for the consistency of ensemble clustering, a novel advancement in the field.
11, if a= b, (xz)), 8 (a,
{1. 0, else.
A
Our theoretical cxploration uncovers that in ensemble clustering, minimizing bias between each base cluster- ing and its expectation, alongside maximizing diversity among base clusterings, enhances clustering perfor- mance. Moreover, we establish a fundamental link between diversity and robustness in this context.
The CA matrix Á (Fred & Jain, 2005) is the average of these similarity matrices, A = m Σm A (1), Since cach similarity matrix (()) is positive semi-definite matrix and A is a convex combination of these matrices, the CA matrix is also positive semi definiefe CA-based ensemble clustering methods (Huang et al., 2016; 2021; Zhou et al., 2023; Ji et al., 2024) try to learn more accurate CA matrix, and then perform hierarchical clustering or spectral clustering on it to obtain more accurate consensus result.
Building upon our theoretical framework, we introduce novel ensemble clustering algorithm and address it through the reduced gradient descent method, offer- ing a practical solution based on rigorous theoretical underpinnings.
3. Generalization Performance
By extensive experimental validation, we confirm the validity of our theoretical assertions and demonstrate
Based on the definition in Section 2.2, we define the de- gree normalized similarity matrix (+) of A (t) is K(t)
2

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
( where D(0-1/2 is the degree ma- trix of A Obviously K(t is still symmetric and positive semi-definite and we assume K(9) is generated from a kernel function k(t), where K( kT (x22 xz)). The empirical error function F as:
Lx (2,, (22 Pn) as
1 Σ
Lx (x) n 1=1
K (x, 2g (2:).
According to (Bengio et al., 2004), the eigenvalues of | K and Lg are the same except zero eigenvalues, and the em- pirical eigenfunctions of K are
Z2 K) for ensemble clustering is defined
F (2
max tr [2 K2 s.t. 2 I, (1)
2g(x)
1 ndg i=1
Σ
where i represents the spectral embedding of (normalized) CA matrix K, which is utilized to approximate the clus- ter indicator matrix. K Ti Σe ((t) the average of normalized similarity matrices, and the coefficient in Eq. (I) guarantees the convergence of eigenvalues of the ker- nel matrix to those of the corresponding integral operator as n - 00 (Liang et al., 2024; Rosasco et al., 2010). Let L be the largest eigenvalues KK. The solution to Eq. (I) is the eigenvectors Ż -z...... zu] correspond- ing to & largest eigenvalues of K. Considering the true continuous distribution of the data, we define the following integral operator Lkg (x) : L2 P) + L2 (X)
where (3() = Vrizig- Thus, Eq. (1) is rewritten as
n
n
K(2;K)= = max (
Σ q=
Σ (1,,, (1)
n
Key problems: According to the above definitions, we investigate the generalization performance of ensemble clus- tering including generalization error bound, excess risk bound, and sufficient conditions for consistency, which are defined follows:
Generalization error: the difference between empir- ical error and population-level error, represented as F) FZ: K*);
LKg (x) = / K (x, 9) (v)
Excess risk: quantifying the difference in error between a learning algorithm and the optimal algorithm on data distribution, expressed as F(2; K*) - F(Z Consistency: the clusterings produced by the given algorithm converge to a clustering that represents the entire underlying space. That is, as the number of sam- ples n and base clusterings m increase, the empirical eigenvectors Z converge to the cigenfunctions Z of the true underlying structure.
where 2 denotes square-integrable function space. Accord- ing to the definition of eigenfunction, we have
- / K y), (p)), (x) = Xxp x
where (z( is the corresponding eigenfunction of Àg. and Xg is the eigenvalue of Lx- Thus, we define the error mea- sured over the entire distributions of data and base clus- terings, referred to as the population-Ievel error with the expectation of base clustering.
The following three theorems address the key problems.
Theorem 3.1. Under the general assumptions and assume that the gap between the k-th and (k +k+ of the expectation of normalized similarity matrix K* is 8% and du 2 1 > 0 where e is constant. For any 0 1. with probability at least 1 - 8, we have
+1++t)tt 1)-th eigenvalues
F(Z:K*)
k Σ 11 K K2 (4Ma:)))lll1(((())0000000
max (4.)) Er
* (2; K2)
(3)
where 2 = [(g)** 1 denotes the corresponding eigenfunc- tions of integral operator Lg- with eigenvalues { K" (zx 3) = E (') (z. y)] is the expectation of the normal- ized similarity function (()), Note that K = E [()] K*, meaning the expectation of the CA function (K) is the
< (2v2c+1)
(
2 3m
6n 5
8
6n
2v 2 log (9)
log
log
+
m
vn
Proof. See Appendix A.1.1.
same that of single normalized similarity function. In
Remark. Theorem 3.1, for the first time, presents the gen- eralization error bound of ensemble clustering under the consideration of both the data distribution and the base clus- tering distribution, which is O( logn + Through this theorem, we establish the relationship between the sample size n and the number of base clusterings m. Clearly, if
the following sections, we will sometimes refer to K* as the expectation of the CA function.
However, as Ż and lie in the different space, we define the empirical integral operator, which is the approximation of the theoretical integral operator based on finite samples,
m
3

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
sample size n is fixed, the generalization error continues to decrease as the number of base clusterings increases, al- though it will not converge to zero. However, with a fixed m, we cannot guarantee the decrease of generalization error, instead, it tends to infinity as n increases. Thus, in ensemble clustering, simply acquiring more samples is not an effec- tive strategy, we still need to obtain more buse clusterings as data size increases. Additionally, a rapid growth of m is required allow the generalization error to converge to O, which implies that yn should be significantly larger than log n (i.e., m > log nt). In practice, we recommend setting m = vn to strike a balance between theoretical conver- gence and computational efficiency of time and space.
since multiplying the eigenvectors by 11 does not affect the outcome, we need to prepend coefficient ay to 2y to ensure that the signs of 2g and So are consistent.
4. Key Factors in Ensemble Clustering
While the preceding section offers theoretical guarantees for the performance of ensemble clustering when both m and n approach infinity, and explores the relationship between and n, it is not feasible to obtain infinite data points and base clusterings in practice. Therefore, in this section, we consider how to approximate the expectation of clustering (K*) with the average of the finite base clusterings (the CA matrix K) by the following optimization problem
Theorem 3.2. Under the same assumptions as Theorrm 3.1 and with the additional condition that || S V (Co > O is constant), for any O < 8 < 1, with probability at least 5, we have
min L F (2: K - F (2:K*)
(5)
tr 2 (2 R2) - tr (²TK²)).
F (2:K*) F (Z; Sk
20200
8 log
3
n1
+
n
When L = O, we perfectly fit the underlying structure of the samples using finite number of base clusterings. However, once the base clusterings are established, K is fixed and so as to the associated C. To decrease the loss L, we apply different weights to various base clusterings. Accordingly, we substitute CA matrix K with weighted CA matrix K", which is defined as
6n
8
6n
2v
log (9)
+2v2c
log
+ +
log
+
(4)
3m 6
m7
vn
Proof. See Appendix A.1.2.
Remark. Theorem 3.2 provides the excess risk bound for ensemble clustering, which is also expressed O(v log m ) Obviously, we require the same condition as in The- orem 3.1 (i.e., m, n - 00, m >> log n.) ensure that the population-level error (F( K*)) of the learned algorithm (2) converges to that (Z( K*)) of the optimal algorithm (2) on the entire data and clustering distributions. It is worth noting that this theorem introduces an additional mild assumption || so S. /Cg, which is easily satisfied given that K (z, 2:) S 1, ET-1 (x:) S n and (x) S +
M
K W
w. K(
(6)
We replace C as LW and obtain the follow theorem.
Theorem 4.1. Based on Eqs. (5) and (6) and let d' = Xx+1 (K+)), (g(K*)
k/n + 2/2/ eigenvalue of K", Wi mww, m is the number of base clusterings, we derive the Bias-Diverss decomposition for ensemble clustering,
) is the k-th
min L = (2:KK) P ((;:K')
Theorem 3.3. Under the same assumptions as Theorem 3.1, if, n - so and nn logn - 0, there exists a sequence (aa), E 1-1,1] such that"
(7)
m
Sc
l (1) K'
K (1)).
m
11a,2 - -0 -> 0,
Bias
Diversity
in probability.
Proof. See Appendix A.2.1.
Proof: See Appendix A.1.3.
Remark. This theorem describes the loss L is governed by two terms: Bias and Diversity. Here. Bias describes the average gap between each single weighted base clustering (wx, Kit)) and the expectation of base clustering (K"), while Diversity describes the average difference between each single weighted base clustering (#) and the weighted CA matrix (KW). Therefore, by adjusting w = ) to achieve low Bias and high Diversity, we can reduce the loss Lw and obtain better clustering performance.
Remark. Theorem 3.3 provides the sufficient conditions for the consistency of ensemble clustering. It describes that the corresponding empirical eigenvectors converge to the cigenfunctions in the limit case. Based on this, we conclude that the clustering learned from empirical data can converge to the true underlying structure of the data, thereby ensuring the consistency of ensemble clustering. Note that
4

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
To better analyze Theorem 4.1, we first simply Eq. (7) into more concise from:
Remark (Bias). It worth noting that existing algorithms (Bang al., 2018; Liu, 2023) only consider the optimization of diversity (robustness), while neglecting the Bias term. A natural concern arises for those methods: does min-max optimization sacrifice the most accurate individuals in the ensemble? For example, most individuals in the ensemble have high accuracy but a few have low accuracy, considering diversity might lead us to assign higher weights to the poorer performers, potentially dragging down the final consensus result (we will verify this in our experiments). Regrettably, existing algorithms neglect this issue. Our theory indicates that better clustering performance will be more likely to achieve by simultaneously optimizing (minimizing) bias and (maximizing) diversity in ensemble clustering.
min W
- 2tr K K*) ) + tr (K"K")
s.t. W W 1, W 0.
(8)
where the constraint w w = 1 is imposed to avoid sparse solutions for the weights w. The proof of Eq. (7) +
Eq. (8) is provided in Appendix A.2.2. Eq. (8) re- mains non-convex optimization problem of w and we still need to process KW to obtain the final clustering re- sults, such as performing hierarchical clustering or spectral clustering on it. To this end, we introduce the spectral embedding Z of KW to Eq. (8). Specifically. the first term of Eq. (8) (miny -tr (K"K*)) is reformulated as by substituting K" for ZZ For the second term minw tr(KwKW), we replace one instance of K" with the spectral embedding Z, i.e., tr(K"K") + maxz tr(K (r(KwZZT ). and further transform it into min- max optimization problem. Besides, the original constraint w w = 1 is non-convex, we revise to w 1 = 1 (where 1 is a column vector of all ones) and also modify the def- inition of Kw Σm wfK(') allowing w to be better interpreted as weight distribution. Together with orthogo- nal constraint on the spectral embedding Z, the optimization problem is finally redefined as:
maxz 2tr(Ks K ZZ" KZZZ"
5. Instantiation of Theorem 4.1
In this section, we instantiate our theoretical analysis (Eq. (9)) to obtain a novel ensemble clustering algorithm. Eq (9) is not directly usable as we do not know the true ex- pected value of the CA matrix K Therefore, we try to approximate it using a simple yet effective way.
5.1. Approximate K
We extract the high-confidence elements in the CA matrix to approximate K* This motivation is that if two samples belong the same cluster, their pairwise value in CA matrix is more likely to be higher, which is reflected in the high- confidence elements of the CA matrix, as illustrated in Fig. 1. It is evident that as the values in the CA matrix increase, the precision of the corresponding elements also improves. Therefore, high high-confidence elements from the CA matrix can well approximate the ground -ruuh relationship between two samples. Specifically, the high-confidence elements are calculated by
Robust optimization
max ZER
2tr KKZZz'
min max tr KWZZ ZERuxa
Bias
Diversity
S.L. ZT = I,w 1 = 1, w 2 O.
(9)
Remark 1 (Diversity). From Eq. (9), we observe that the Diversity term aims to enhance the diversity among the base clusterings. Although some heuristic methods (Fern & Brodley, 2003; Kuncheva & Vetrov, 2006; Hadjitodorov et al., 2006; Jia et al., 2011; Metaxas et al., 2023) were proposed to increase diversity in ensemble clustering, our approach is entirely derived from Theorem 4.1, offering solid theoretical guarantees.
H K 0,
Kij 2 a,
(10)
else
where a is a hyper-parameter. Eq. (10) retains the high- confidence elements in the CA matrix and discards the low- confidence ones. However, H in Eq. (10) is generally very sparse (as illustrated in Fig. 1, the recall and proportion rates of the elements in H decrease as a increases) and not semi- positive definite. Therefore, we compute its second-order similarity relations to make it denser and semi semi-positive by
Remark 2 (Robust Optimization). We surprisingly dis- cover that maximizing the Diversity term is equivalent to a robust min-max optimization model (aiming to identify the spectral embedding that performs well even with a bad weight vector), which is similar to some existing robust ensemble algorithm (Liu, 2023; Zhang et al., 2022; Bang et al., 2018; Tao et al., 2019; Liang et al., 2022). Unlike their motivation to enhance the model's 's resistance to noise, we explain that these algorithms essentially improve diversity within the ensemble to reduce the loss (L") between the empirical and expected error. This provides a theoretical explanations for why these algorithms work effectively.
K = (D-1)) H HTD
(11)
where D is diagonal matrix and D ja V (H )
5.2. Proposed Ensemble Clustering Algorithm
After approximating K* by K in Eq. (11), Eq. (9) can be instantiated into the following practical ensemble clustering
5

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Prppetaoo Pacaze
0-'
130
130
0-0
150
100
130
24 05 <0
Flarros for waying Bresholds CA mibii
(a) The proportion, precision, (b) High confidence matrix H (c) Second-order similarity re- (d) The ground truth similarity ma- and recall of high-confidence el- with threshold 0.4.
lation matrix of H. trix of seed dataset.
ements in different threshold.
Figure As shown Fig. (a), with the increase the high-confidence threshold, the proportion of elements and the recall rate gradually decrease, but the precision approaches 1, suggesting that high- colf-iennieeceeeee elements are reliable. Fig. (b) displays the visualization of the high-confidence matrix at a threshold 0.4, which resembles the ground truth shown in Fig. (d), although is still not dense enough. Consequently, computed the second-order similarity relationship K of H, as depicted in Fig. (c), which more closely approximates the ground truth (We use Seeds dataset for this experiment)
method (we provide brief proof of Eq. (9) + Eq. (12) in Appendix A.2.3).
As established in (Bonnans & Shapiro, 1998). J(w) is differentiable,
min max tr w
[2k KW ZZ
0J (w) 2w,tr (K"ZZz") Our
(12)
s.t. Z 7 Z
Σ Wi = 1, Wi 2 0.
where Z {arg maxz ur((2k Kw) ZZ ) ZT IJ. Building upon this, compute the gradient of J J(w) as follows:
Since both K and Kwl are positive semi-definite, the prob- lem is a convex problem with respect to Theoretically, we can obtain the global minimum point for w. Once the spectral embedding Z is obtained, we apply k-means al- gorithm to it to derive the final discrete clustering results.
VJ (w)), 0J (w) Ow.
0J (w) Ow,
Vt + u,
and
n OJ (w)
aJ (w)
(w),,
Ow,
Ow:
5.3. Optimization of Eq. (12)
1=,,60
where wi is not selected as the zero component of w. To address the constraint w 2 0, the final descent direction is computed as
Eq. (12) is a typical min-max optimization problem with multi-variables. The usual approach is to fix one variable and optimize the other, but this approach often fails to yield globally optimal solution. In (Liu, 2023), the author trans- formed this problem into minimizing the optimal value func- tion and employed reduced gradient descent for solving it. Given the similarity of our mooblem-solving approach to this method, we provide only the key steps of the optimization process. Readers are encouraged to refer to (Liu, 2023) for more details.
if ww = 0 and [VJ (w)), > 0,
de VJ (w),,
if we > 0 and t + u,
VJ (w)l...
if = u,
(13)
where d, the p-th component of gradient vector d. We use gradient descent to set Wt+1 < w. + ,dd and continue until the algorithm converges, where is learning The pseudo code for this algorithm is provided in Appendix C.
For Eq. (12), rewrite it as (the constraints have been omitted for brevity)
min I (w).J (ww) = max tr ((2K KW
zz
6. Experiments
In this context, we adopt a cluster-weighting strategy to pre- assign weights to different clusters of the base clusterings, follow- ing approaches such LWCA (Huang al., 2018) and NWCA (Zhang et al., 2024). this paper, we employ the NWCA method.
6.1. Comparative Experiment
We evaluated our method on 10 datasets with method CEAM (Zhou al., 2024), C.s?L, CEs²Q (Li et al., 2019), LWEA
6

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Table Performance (%) evaluation of different datasets based the NMI metric. We have highlighted the values of the best-performing
method in bold, and the second best method is marked with an underline.
Method
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
Average
CEAM (TKDE'24 24)
5.6
36.2
16.7
27.4
60.1
4.3+s
18.0+a
19.0
14.3++
8.8#s
21.0+s
CEs (AI' 19)
3.4
9.3
19.024
27.9
45.1
12.3ss
12.0aa
15.2
15.7+3
10.2
17.0
CEs²Q (AI''19) 19)
2.5
11.5+s
17.645
28.1+3
43,9
12.1
12.242
17.9*4
15.4+3
7.5+4
16.9
LWEA (TCYB' 18)
0.4
53.3+3
15.9#3
28.1
63.34a
12.1
13.743
21.0=4
14.7+1
7.9+4
23.0+3
NWCA (2rXiv'24)
0.4
52.5
16.0as
28.4
63.7aa
12.5+4
13.643
21.721
14.8
9.724
23.3
ECCMS (TNNLS'24)
0.4
50.7
18.4
28.22a
64.721
12.3ss
12.9
22.8-4
15.5
9.124
23.5
MKKM (arXiv' 18)
8.1
20.8
12.8
20.616
55,4
12.0
19.744
14.3a4
12.0
9.1
20.5
SMKKM (TPAMI'23) 23)
8.7
38.5+m
19.3
27.0aa
59.4.9
10.5
20.0+2
18.2
15.5+2
10.5+4
22.8
SEC (TKDE' 17)
9.2
24.9
17.3
21.94s
36.0a17
12.8
15.5
13.627
9.9
7.1
16.8
Proposed (a = 0.1)
25.0+11
58.3+1
20.0
29.4
67.5
14.4
18.8
19.6
15.0
12.4-1
28.0+4
Proposed
25.0
58.3
21.1
29.4
67.5
15.0
22.9
27.5
15.8
12.4
29.5
15
NMI
NMI
NMI ARI
0.5
ARI
0.5
ARI
0.5
Purity
Purity
Purity eiigt
Weight
eight
Indices of different base clusterings
Indices different base clusterings
Indices different base clusterings
(a) МKKM
(b) SimpleMKKM
(c) The proposed method
Figure 2. Illustration of the performance (line plot, NMI, ARI, and Purity) of each individual base clustering when the ensemble size is 10, as well as the clustering weights learned by the three different methods (bar plot). Note that all three metrics are better when they possess higher values. For better visualization, add 0.5 to the values of cach metrie.
(Huang et al.. 2018), NWCA (Zhang al., 2024), ECCMS (Jia et al., 2024), MKKM (Bang al., 2018), SMKKM (Liu, 2023), SEC (Liu et al., 2017). Due to the space limita- tions, detailed descriptions of the datasets and comparison methods are provided in Appendix E. and E.2. For each dataset, we repeat the experiments 20 times and compute the average performance. The true number of clustering class is chosen as k for each dataset. Three performance metries are selected evaluate the methods: NMI, ARI, and Purity, and larger value indicates better performance. Table reports the comparisons based on the NMI metric, while the results for ARI and Purity are provided in Appendix E.3. As shown in Table 1, we observe that:
of our method is more significant. For example, the D1 (Phishing) dataset, the results obtained by other methods are close to 0 as measured by NMI, rendering them nearly impractical for guiding applications, while our method can provide some valuable information.
Even with the hyper-parameter a = 0.1 fixed, our method outperforms the methods compared in most datasets and lead on average across all methods. For example, with fixed hyper-parameter, lead the second- method by 4.5%, 6.2%, and 4.4% in NMI, ARI, and Purity on average.
respectively
To further substantiate the efficacy of the modified method, we carry out prper-pparametr sensitivity experiment, abla- tion study, and ensemble size experiment. Due to space limitations, these experiments are detailed in Appendices E.4, E.5 and E.6.
The proposed method outperforms the comparison methods across all datasets. In terms of average per- formance, exceed the second- best method by 6.0%, 7.3%. and 6.0% in NMI. ARI, and Purity, respectively. On some difficulty datasets, the performance advantage

---

constant greater Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Table The detailed performance metries of three different learning weight methods.
Method
Objective Function
Essence
NMI
ARI
Puritty
Bias*
-iieersity
Total"
MKKM
min min tr Kw
[ zz
min Diversity
62.8
62.1
85.0
-94.6
116.2
21.6
w
2
min max KWZZT)
SMKKM
max Diversity
65.3
66.2
85.9
-10.0
1.0
-90
max tr [K 2
min Bias
Proposed
71.9
72.4
90.2
-24.0
6.4
-17.6
min max tr Zw
max Diversity
"Bias" refers to -2tr(K"K'), "- -Diversity" is defined as tr(K"K" and "Total" is equal to "Bias Diversity".
24
1.9
2.05
1.94
-.m. [in) 1/v 1 0.54 0.38
[in) 2/v/ 0.04
1.95
f (6)
f [k) 1/ 0.54, Togm/// 1.15
1/ 0.0 /lgm/
True crroc
23
(in) 1/yf 0.54, (ogg bo)
(i) M//h 0.54 /ogn/ kegling) 0.58
1.05
105
1.3
1.75
186
1.65
1.8
184
1.5
4000
5200
4030
6200
(a) m log log (diverge)
log n. (converge to e, >> 0)
(c)
(converge
Figure 3. We conducted experiments real data for Theorem 3.2. In this experiment, uniformly sample data with an increment of 100 for the validation of n. The blue dots represent the errors computed from the real data, while the red and pink lines represent the fittings using the formulas from Theorem 3.2.
6.2. Clustering Weight Analysis
ing our earlier discussion (Remark 3 in Section 4) that assigning weights solely enhance diversity can lead to misallocation. Our method introduces high-confidence ele- ments to guide the diversity and reduce bias, ensuring that higher weights are assigned to more accurate base cluster- ings. As a result, the proposed method achieves the lowest "Total" loss and enhances the final clustering performance. As a summary, the above analysis is consistent with our theoretical findings.
In this section, we analyze the base clustering weights learned by our method and compare them with those of other base clusterings weighted averaging method: MKKM (Bang et al., 2018), SimpleMKKM (SMKKM) (Liu, 2023). The details of these methods are summarized in Table 2, where we compare them across multiple metrics. As shown Table 2, MKKM inherently reduces the diversity of base clusterings, thereby concentrating the weights on single base clustering, as illustrated in Fig. 2. When the selected single base clustering aligns closely with the ground truth, MKKM significantly reduces bias, thereby enhancing clus- tering performance. However, this approach often faces two defects: 1) does not always assign higher weight to the more accurate base clustering, as it lacks supervision; and 2) even the best base clustering is selected every time, this method loses the advantage of ensemble learning that uses multiple base clusterings achieve better one. The objective function of the SimpleMKKM method is designed to enhance the diversity among base clusterings (as Table 2 reports), thereby distributing the weights as possible across multiple distinct base clusterings, as illustrated in Fig. 2. However, their weight values seem to follow an opposite trend the performance of individual clustering, validat-
6.3. Validation of Excess Risk Bound
In this section, we validate Theorem 3.2 using the real dataset WFRN. Theorem 3.2 exhibits three distinct scenarios of excess risk: divergence, convergence than zero, and convergence to zero. We conduct experi- ments for these scenarios with m = log log n. m = log n, and m = Vn, respectively. Since we cannot obtain the expectation of the CA matrix, we substitute it with the simi- larity matrix produced by the ground-truth label. Therefore, the fitting function is defined as a + /og n/m-+gap. where the gap represents the difference between the simi- larity matrix of the labels and the expected value of the CA matrix. It can be observed in Fig. 3 that the function fits the loss data points accurately when we choose a = 1 and
8

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
42 0.54, as indicated by the red line. Theoretically, our gap should be fixed value, as illustrated by the pink line. Although it does not completely conform to our data, the trend is consistent with the loss. From this experiment, we observe that when m = log log n, the loss value remains almost stable at 1.9; when m = log n, the loss value shows a clear decreasing trend and eventually arrives at 1.85; and when m = vn, the loss curve exhibits a steady decline, ultimately reaching loss value of approximately 1.7. Com- bining this experiment with our theoretical analysis, we further demonstrate that when m < log n, the excess risk diverges; when m = (log n). it converges to constant greater than O; and when m > log n, it converges to O.
specifically highlighted here.
References
Bachem, O., Lucic, M., Hassani, S. H., and Krause, A. Uniform deviation bounds for k-means clustering. In Proceedings of the 34th International Conference on Ma- chine Learning, volume 70, pp. 283-291. PMLR, 06-11 Aug 2017.
Bang, S., Yu, Y., and Wu, W. Robust multiple kernel k- means clustering using min-max optimization. arXiv preprint urXiv:180.0024: 2018.
Bengio, Y., Delalleau, O., Roux, N. L.,, Paiement, J.-F., Vin- cent, P., and Ouimet, M. Learning eigenfunctions links spectral embedding and kemnel pea. Neural Computation, 16(10):217--2119 2004.
7. Conclusion and Discussion
In this paper, we have presented the generalization enror bound, excess risk bound, and sufficient conditions for the consistency of ensemble clustering. Through this, we have elucidated the interplay between sample size n and the num- ber of base clustering m, offering insights relevant to practi- cal applications. By approximating clustering expectations using weighted finite clustering, we identified the impact of Bias and Diversity on the errors between them. Notably, we have shown that maximizing Diversity aligns closely with robust optimization principles. Our contribution extends to the introduction of a novel ensemble clustering algorithm rooted in our theoretical framework, which significantlyy outperforms other SOTA methods.
Bonnans, J. F. and Shapiro, A. Optimization problems with perturbations: guided tour. SIAM Review, 40(2):228 264, 1998.
Clémençon, S., Lugosi, G., and Vayatis, N. Ranking and empirical minimization of u-statistics. The Annals of Statistics, 36(2):844 874, 2008.
Fern, X. Z. and Brodley, C. E. Random projection for high dimensional data clustering: A cluster ensemble approach. In Proceedings of the 20th international conference on machine learning (ICML-03), pp. 186-193, 2003.
is also important to acknowledge certain limitations in our work. While we have established sufficient conditions for consistency, necessary conditions remain unaddressed, and the tightness of convergence rates for generalization eπror and excess risk is yet to be fully evidenced. The algorithm derived from our theory only represents a specific instance, leaving room for the exploration and comparison of diverse algorithms developed within this framework.
Fred, A. L. and Jain, A. K. Combining multiple clusterings using evidence accumulation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(6):835- 850, 2005.
Hadjitodorov, S. T., Kuncheva, L. I., and Todorova, L. P. Moderate diversity for better cluster ensembles. Informa- tion Fusion, 7(3):264 275, 2006.
Huang, D., Lai, J.-H., and Wang, C.-D. Robust ensemble clustering using probability trajectories. IEEE Transac- tions on Knowledge and Data Engineering, 13:5 1326, 2016
Acknowledgments
This work was supported by the National Natural Sci- ence Foundation of China under Grant U24A20322, and Hong Kong UGC under grant JGC/FDS11//0221 (BGC/FDS1//E33// and in part by the NSFC Excellent Young Scientists Fund 624221 18. This research work was also supported by the Big Data Computing Center of South- east University.
Huang, D., Wang, C.DD,, and Lai, J.-H. Locally weighted ensemble clustering. IEEE Transactions on Cybernetics, (553):166--1733 2018.
Huang, D., Wang, C.-D., Peng. H., Lai, J., and Kwoh, C.-K. Enhanced ensemble clustering via fast propagation of cluster-wise similarities. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 51(1):508-520, 2021.
Impact Statement
This paper presents work whose goal advance the field of ensemble clustering. There are many potential societal consequences of our work, none which we feel must be
Ji, X., Sun, J., Peng, J., Pang, Y., and Zhou, P. Clustering ensemble based on fuzzy matrix self eeffeenhancement IEEE Transactions on Knowledge and Data Engineering, 2024.

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Jia, J., Xiao, X., Liu, B., and Jiao, L. Bagging-based spec- tral clustering ensemble selection. Pattern Recognition Letters, 12(10):1456-1467 2011.
Liu, H., Wu, J., Liu, T., Tao, D., and Fu, Y. Spectral en- semble clustering via weighted k-means: Theoretical and practical evidence. IEEE Transactions Knowledge and Data Engineering, 29(5): 1140,1113,,,011 2017.
Jia, Y., Kwong, S., Hou, J., and Wu, W. Semi-supervised non-negative matrix factorization with dissimilarity and similarity regularization. IEEE transactions on neural networks and learning systems, 31(7):2510-255 2521, 2019.
Liu, X. Simplemkkm: Simple multiple kernel k-means. IEEE Transactions on Pattern Analysis and Machine In- telligence, 45(4):5174-5186 2023.
Jia, Y., Liu, H., Hou, J., Kwong, S., and Zhang, Q. Multi- view spectral clustering tailored tensor low-rank repre- sentation. IEEE Transactions on Circuits and Systems for Video Technology, 31((2)448844497, 2021.
McDiarmid, C. On the method of bounded differences, PP. 148-188. London Mathematical Society Lecture Note Series. Cambridge University Press, 1989.
Metaxas, I. M., Tzimiropoulos, G., and Patras, I. Divclust: Controlling diversity in deep clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 3418-3428, 2023.
Jia, Y., Tao, S., Wang, R., and Wang, Y. Ensemble cluster- ing via co-association matrix self-enhancement. IEEE Transactions on Neural Networks and Learning Systems, 35(8):1 110--1117 119,, 2024.
Peng, Z., Liu, H.,, Jia, Y., and Hou, Egre-net: Embedding- induced graph refinement clustering network. IEEE Transactions on Image Processing, 32:6457-6468, 2023.
Kuncheva, L. I. and Vetrov, D. P. Evaluation of stability of k-means cluster ensembles with respect to random initialization. IEEE transactions on pattern analysis and machine intelligence, 28(11):1799))
2006.
Pollard, D. Strong Consistency of K-Means Clustering. The Annals of Statistics, 9(1):135 140, 1981.
Latala, R. and Oleszkiewicz, K. On the best constant in the khinchin-kahane inequality. Studia Mathematica, 109(1): 101-104, 1994.
Rosasco, L., Belkin, M., and Vito, E. D. On learning with in- tegral operators. Journal of Machine Learning Research, 11(30):00 2010.
Li, F. Qian, Y., Wang, J., Dang, C., and Jing, L. Clus- tering ensemble based on sample's stability. Artificial Intelligence, 273:37-55, 2019.
Strehl, A. and Ghosh, J. Cluster ensembles a knowledge reuse framework for combining multiple partitions. Jour- nal of machine learning research, 3(Dec): 2002.
Li, S., Ouyang, S., and Liu, Y. Understanding the gener- alization performance of spectral clustering algorithms. Proceedings of the AAA/ Conference on Artificial Intelli gence, (117))6614-8666 Jun. 2023.
Tao, 7., Liu, H., Li, J., Wang, 7., and Fu, Y. Adversarial graph embedding for ensemble clustering. In Proceed- ings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 3562-3568. In- ternational Joint Conferences on Artificial Intelligence Organization, 7 2019.
Li, Z. and Jia, Y. Commix: Contrastive mixup at repre- sentation level for long-tailed deep clustering. In The Thirteenth International Conference on Learning Repre- sentations, 2025.
Topchy, A., Jain, A., and Punch, W. Clustering ensembles: models of consensus and weak partitions. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 27 (12): 112:1186-1881, 2005.
Liang, W., Liu, X., Zhou, S., Liu, J., Wang, S., and Zhu, E. Robust graph-based multi-view clustering. Proceedings of the AAAI Conference on Artificial Intelligence, 36(7): 7462-7469, Jun. 2022.
Vershynin, R. Concentration Without Independence, pp. 98-126. Cambridge Series in Statistical and Probabilistic Mathematies. Cambridge University Press, 2018.
Liang, W. Liu, X., Liu, Y., Ma, C., Zhao, Y., Liu, Z., and Zhu, E. Consistency of multiple kernel clustering. In Proceedings of the 40th International Conference on Machine Learning, pp. (6650-20676,, 2023.
Von Luxburg, U., Belkin, M., and Bousquet, O. Consistency of spectral clustering. The Annals of Statistics, pp. 555- 586, 2008.
Liang, W. Tang, C., Liu, X., Liu, Y., Liu, J., Zhu, E., and He. K. On the consistency and large-scale extension of multiple kernel clustering. JEEE Transactions on Pattern Analysis and Machine Intelligence, 46(10):6935-6947, 2024.
Xu, J., Li, T., and Duan, L. Enhancing ensemble clustering with adaptive high-order topological weights. Proceed- ings of the AAAI Conference on Artificial Intelligence, 38 (14):16184 161992 Mar. 2024.
10

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Yi, J., Yang, T., Jin, R., Jain, A. K., and Mahdavi, M. Robust ensemble clustering by matrix completion. In 20/2 IEEE 12th International Conference on Data Mining, pp. 1176- 1181, 2012.
Yu, Y., Wang, T., and Samworth, R. J. A useful variant of the davis-kahan theorem for statisticians. Biometrika, 102(2):315-323, 04 2014.
7hang, M. Weighted clustering ensemble: A review. Pattern Recognition, 124: 108428, 2022.
Zhang, X., Jia, Y., Song, M., and Wang, R. Simi- larity and dissimilarity guided co-association matrix construction for ensemble clustering. arXiv preprint arXiv:2411.00904 2024.
Zhang, Y.. Liang, W., Liu, X., Dai, S., Wang, S., Xu. L., and Zhu, E. Sample weighted multiple kernel k-means via min-max optimization. In Proceedings of the 30th ACM International Conference on Multimedia, MM '22, pp. 1679-1687, New York, NY, USA, 2022. Association for Computing Machinery.
Zhou, P., Du, L., Liu, X., Ling, Z. Ji, X., Li, X., and Shen, Y.-D. Partial clustering ensemble. IEEE Transactions on Knowledge and Data Engineering, 2023.
Zhou, P., Hu, B., Yan, D., and Du, L. Clustering ensemble via diffusion on adaptive multiplex. IEEE Transactions on Knowledge and Data Engineering, 36(4):146311474 2024.

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Appendix
A. Overview of the Appendix
Our appendix consists of three main sections:
Proofs of the three theorems in Section 3, i.e., Theorem 3.1 (generalization error bound), Theorem 3.2 (excess risk bound), and Theorem 3.3 (sufficient conditions for consistency).
Proof of Theorem 4.1 in Section 4, Eq. (7) = Eq. (8) and Eq. (9) = Eq. (12)
Some information omitted from the main text due to the space limit, including pseudo code for Section 5.3, related work, details of datasets and comparison methods, clustering performance on ARI and Purity metrics, as well as experiments on hyper-parameters, ablation studies, and ensemble size analysis.
To clarify our proof process, we provide sketches the proofs for the theorems in Sections and in Appendices A. and A.2, respectively, and the detailed proofs are provided in Appendix B.
A.1. The sketching proof Theorem 3.1, 3.2, 3.3
A.1.1. THE SKETCHING PROOF OF THEOREM 3.1
To proof Theorem 3.1, we first make the following decomposition,
i (2; F (2;K*) = f (2; (2; -2 (=; + / (2; - F (Z;K"),
where F(2;K') K*) is the empirical error with expected CA matrix K (function K*),
F F(2;K*)
1
ΣΣΣ K (,n
(c.),- Er
A can be further decomposed as (note that (2: is equivalent to F (2:K). F 2: ( k.)
is equivalent to 8 (2:K:)
F (2;
K
F 2 (²)K)
1 (ir 2 (2) -rr K k²t²) 2))
71
1
tr
T (K - K-) 2))
ur (2 - tr 2 k 2)
xx-2)
Aa
Therefore, prove Theorem 3.1 by bounding A1, A2, separately, which leads to the following three lemmas. Lemma A.I. Under the general assumptions, have
A = (1r
2
2n log 8
8
2n
log 8
3m
with probability at least (The detailed proof of Lemina A. is in Appendix B.1) Lemma A.2. Under the general assumptions and assume that the gap between the k-th and (k: + 1)-th eigenvalues of the expectation of normalized similarity matrix K" is 8n and 8x 2 ! > O where e a constunt, we have
A tr 2 (2 - ( (z'Kz 2/22
2
2n log
8
2n 8
log
3m
8
with probability at least (The detailed proof of Lemma A.2 is Appendix B.2)
12

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Lemma A.3. Under the general assumptions, have
< 2/2loge at.
== (2: -F F(;
vn
with probability at least 1 - 6. (The detailed proof of Lemma A.3 is in Appendix B.3)
For Lemma A.I, our proof primarily relies matrix Bernstein inequality. In the case of Lemma A.2, we apply perturbation theory to derive the bound for A2. The proof of Lemma A.3 is mainly concerned with the integral operator theory of (Rosasco et al., 2010). By combining Lemmas A.I, A.2, and A.3, we have
(2:K²) F (2: (2v2c+1)
2 3m
6n log
8
6n log
2v 2 log (9)
+
+
8
m
Vn
with at least probability - 8, which completes the proof of Theorem 3.1.
A.1.2. THE SKETCHING PROOF OF THEOREM 3.2
Based on the proof of Theorem 3.1, we have
F K F (Z;
=F (2;K*)
F (2:
+ (; - (3;
Generalization erturr
+ / =F (2; - F (2:
2; -
+ + (2;))
1 (2: + + +f(2x*)
- F (2;KK*
=F (2:K*)
E (2:x*)
+ E (2:K*)
F (2:
(2; K)
-p (2;
-Ai
A
+F (2 - - (2:K*)
+F (2;K:)
(2)
Au
=F (2:KK) - - (2:K*) + E (2:K*) - -F + F
(2; F (2;K*).
B
Therefore, we only need to bound C, the bounds of A2 and can be obtained directly from Lemmas A.2, A.3. Lemma A.4. Under the general assumptions and with the additional condition that |ا S co (co > a constant), we have
2v2co
8log 1
C -((;
S k
Vn
n
with probability at least 5. (The detailed proof of Lemmna A.4 is in Appendix B.4)
For bounding C, we utilize the McDiarmid's inequality (McDiarmid, 1989) and Rademacher complexity. The former is a standard tool to bound the difference of the random variable and its expectation. The reason for utilizing the latter technology that, F Z K*) is pairwise function and some tools in the i.idd condition is not satisfied (Li et al., 2023). We derive the bound of C analogously to (Li et al., 2023). By combining Lemmas A.2, A.3 and A.4, we derive that
2v 200
log
2 3m
6n log
8
6n log
2 2 log 0
F(2:K*) -(2 k
+1
+
2c
+
+
VR
n
5
5
with probability at least 5. This concludes the proof of Theorem 3.2.
13

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
A.1.3. THE SKETCHING PROOF THEOREM 3.3
Theorem 3.3 describes that empirical eigenvectors (2n) of CA matrix (K) converge to the eigenfunctions (G,) of integral operator (Lx=) in probability in the limit case. We introduce the intermediate vector 2g (2g is the eigenvector of expected CA matrix K*) and proceed with the following decomposition:
2 - Soloo S ||a,2 2 + 16020 Salloo.
MM
N
For M, we know that there exist a sequence (0g)g E f-1,1} such that 1bb22 - Sgllso -> as n + co, which has been proved in the Theorem 15 by (Von Luxburg et al., 2008). We need only prove that M converges to 0 in probability.
Lemma A.5. Under the same assumptions Lemma A.2, there exists sequence (dg)4 E {-1, such that
2g by - 0,
in probability as m, n + oo and m > logn. (The detailed proof of Lemma A.5 is in Appendix B.5)
For Lemma A.5, our proof technique primarily relies perturbation theory and trigonometric functions transformations. By incorporating M, we complete the proof of Theorem 3.3.
A.2. The sketching proof of Theorem 4.1 and Eq. (7) Eq. (8)
A.2.1. THE SKETCHING PROOF OF THEOREM 4.1
Theorem 4.1 presents the bias-diversity decomposition for ensemble clustering. To prove this theorem, we introduce the following two lemmas.
Lemma A.6. According to the definitions in Section 4, where Kw = - Wy K(0, K the expectation of K(0, and we the weight of t-th base clusterings. We have the following decomposition
m
m
K K
||
K*1
(mew - K..
The detailed proof of Lemmna A.6 is in Appendix B.6. Lemma A.7. Under the same assumptions as Lemma A.2, we derive that
p (2: - (2:K*)
(2;
-
k
2/2
|K -K'IFF
A (K*) Act1 (K*)
The detailed proof of Lemma A.7 in Appendix B.7.
The proof of Lemma A.6 primarily relies on the properties of the matrix trace. The proof of Lemma A.7 employs tools similar to those used in Lemma A.2. By combining these two lemmas and setting c' = k/n (222((((k")) > 1), we can readily prove Theorem 4.1.
A.2.2. THE SKETCHING PROOF EQ. (7) EQ. (8)
can be observed that the coefficient é' in Eq. (7) is constant greater than zero (given the number of samples n, the number of base clusterings m, and the number of clusters k). Therefore, Eq. (7) is entirely equivalent to
m
m
min
K
K"
Σ
l.,K() (+) 1o0-Kwo kwI2
Through equivalent transformation, we arrive at the following lemma. Lemma A.8. With the same definition of Lemma A.6, we have
m
min W
Σ (
K-1
(())
kW12 e min 2tr (KWK*) + (KKKW).
The detailed proof of Lemma A.8 is in Appendix 8.8.
Through Lemma 8, we can easily derive Eq. (8) from Eq. (7).
14

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
A.2.3. THE SKETCHING PROOF OF EQ. (9) EQ. (12)
Eq. (9) defined as
max ZER
2tr
K K"ZZ"]
+ min max w ZEREEE
K"ZZZ"
K
S. Z Z 1=
In this optimization problem, the first does not contain the optimization variable w, so we can directly combine it with the second term to obtain (we omit the constraints for the sake of brevity)
(ir (KKKZZZ))
K (KZZz))
min max ZERaXİ
21r
Based on the properties of the matrix trace, we can derive that
min max tr ((2K*+KW) +K zz ZER
By replacing K with K in Eq. (11), we finally obtain Eq. (12).
B. Detailed Proof
In this section, we provide detailed proof' for each lemma presented Appendices A. and A.2.
B.1. Proof Lemma A.1
To prove Lemma 1. we need to introduce the following matrix Bernstein inequality (Vershynin, 2018).
Lemma B.1. (Matrix Bernstein Inequality) Let X(1)... X (m) be O-mean n symmetric independent matrices such that X (9 C (C a constant) almost surely for all Then, V O, we have
m²g²
P
Σ
x
112 28)
< 2n 2np
m
2 2 +
mcC
3
where 0² = -12mm E (12]
Proof. For A,, we have
(K K*) 2))
A1
tr
71
71
T
(K - K*) 2
2
$| || 2
||
K" K-11 = || K'112
Define (1) (()) K", obviously we have E [ = [K)
- K* = 0. For a², we have
m
(
2
(K(t)
K*) 27
[(00]]
- Te [
- E k()))
+ E K
E (11)
m2
$ m
sup
E (02
K
msuu
+ ||
15

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Based Jensen's 's inequality and K < I, K
3 I, we have
E
(R)2
- E
(())
S E
(1)
| 12 S K S
|
for any t. Therefore, bound o² by
m sup
E
K
(1)
K
B
K
(1)
+ m
|
- 2m | 2m.
With Lemma B.I, we have
2
2n
2n 6
A
log
+
log
3m
m
with probability at least - 8.
B.2. Proof of Lemma A.2
We variant of Davis-Kahar theory (Yu et al., 2014) bound A2-
Lemma B.2. (Davis-Kahan theory) Assume X and X' are two n X real symmetric matrices and their largest d eigenvalues
are \ 2 X2 2 ... 2 Xa and X1 2 X₂ 2 ... 2 Xa the matrices Z and Z' are composed of corresponding eigenvectors
Z1 za] and | .... z/2.. we have
2 (d X - 1211,, 1X'X2 11 X'1RF)
Isiin 011,
Nd Ad+1
where (01 cos ",. Os cos-1 1 od) T, 01, Oa are the singular values of Z ZZ, sin(O) the d x diagonal matrix with the elements sin(O) sin (i,).
Proof. For A2, we have
1 tr
A
Z K
-r
Z K 2
K" ||
222
-3
- | 2l
12T
-82
F
= ižT
-22"
22 sin (0(2, 2)
2
K "K-KI 1-112
A (K*)
Ax+1 (K*)
2n
2n log 8
5 2v
log
3m
with probability at least - 8, where c= -= (K*)
>++1 (K*).
B.3. Proof of Lemma A.3
We introduce two integral operator in (Rosasco et al., 2010) to prove Lemma A.3.
Assume H is the RKHS associate with kernel function K (2, v). the empirical covariance operator T, : H. - H. is defined as
n
T, Σ (;, Kn.) Kry,
where Kz, K (Kx,) :). The expected covariance operator Txx -
Tu / (Kay Kydp (x).
16

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Proof. By the definition of F (2:K)) and F (2;K*), we have
F. -2
((2
n
K (T)) - Σ Σ/1, K" (A gml
n
(xx) So (20
> to (x) So (x)
& Bq Sq - Σ lg / So (z)
x
gml
k
Σ
(g
Ea)
qm1
where (4 (()) are the largest k eigenvalues of integral operators i-x- (x()) Lx (z(), respectively,
According to (Rosasco al., 2010), the eigenvalues of i. and Tn (with kernel function K*) are the same up to so do Lg- and Th (with kernel function K*), Therefore, we have
k Σ 4=1
6 og
S (ir((Tn) tr (Tx)) 2v2 log (ž)
i (2: - F (2; K*
(bg Eg) s
og
vn
q=1
with probability at least - 8.
B.4. Proof of Lemma A.4
To prove Lemma A.4, we first introduce the McDiarmid's inequality.
Lemma B.3. McDiarmid's 's inequality. For m random variables X; E X, E [m]] assume & - R is the real function of X; and & Ti,".. ... Tm, x/g E X, we have
If (z1, I [m) - (21, 24,," ... "mm,) S ci
Is.
then V e >> 0,the following inequality holds.
-2
(X Xm) - BB (X1, Xmm) 2) 2m)) s <exp
2
As mentioned in Lemma A.4, F(2; K") is pairwise function and some tools in the i..d. condition is not satisfied, therefore, we make the following definition.
Definition B.4. (Rademacher complexity for F(2; K*)) Let H. is the function space of 2, the empirical Rademacher complexity of C definied as
E (14, (1;) (ML+EE)
Rs (L) = E,
sup SEC
K"
22
where [0 are the i.i.d. Rademacher variables taking values and -1 with equal probability independent of the sample S.. 1/ means the greatest integer less than or equal to The Rademacher complexity is the expectation of R2 (C), R(C) (C))
17

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Proof. Based on the definition of 2, C. can be reformulated as
C= F (2;K*) F (2:
!/ )
Σ
K" (I, By (z) (1)d n²
n
KM
(1 Ut) (x4) 2g (v:)
9=1
Σ [ (ar, (1) (x, 2g (1) By (v))
S k sup
EC
Assume the i.i.d. sampled data are S,, = [.1.-.. ,,,,, ,n and st. = fo1, ... , . , we have
sup (x, Es, [K* (x,,,("")))))))),)))))))
sup (EIK (z, (B[K""Z, (
E (1)
EGEC
< sup 7,EL
Ess, [K" (2. &o (x) &g (v) E ب
K (z,, v) Ro (z) bg (v)]
n Σ
sup n1 2,EL jml
(1K* (2 m.) 2g (z.) 2g (z,)
K (1 Eg (2 (z))))
S sup Σ
+ (lăg (xx) Egg t (2x) 2n (z,)))
112 EG
j=1
1
The first inequality arises because sup (ʃ (x) -g())) - sup (S (x) 1 (x)) s sup (h (x) g (x)); the second inequality
readily derived from If (x) - g (x) S |f (a:) + lg (z)l; concerning the third and fourth inequalities, we note that
K (z, v) and Σラ Eg (x₂) Ey (I₂) n. Therefore, by applying McDiarmid's inequality, have
E. [K (x,8) Eg (x) 2g (w)) Es. [K (x. v) Eg (x) Eg (w))
sup
EC
[E[K* (x,y) 2g (x) 2g (v) R.s. [K* (ar, (x, (il) +
8 log x
<
sup
EC
n
[[ (z, v) &g (x) [v)] - Es. [K* 2) (x) &g (w)1))
with probability at least 1 1-8. Then we need to bound E According to (Clémençon et al., 2008), we have
sup E
E [K (z. Ey (x) 2g (v) Es, [K" (x, v) Ey (I) &g (1)))
E
sup
ELEC
1 E
K* (2..11111)) 2o (2,) bg (11111))
<E
sup 7
E K (x, 2) 2 (x) 2g (w))
18

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Donate Sh {+1,"" 3 be the sampled i.i.d. data, Sa is independent of Sn. We have
K (1)1)1))+4) 2g (zx) 2q (41311))
E
sup E
E K (x. v) 2g (g) (v)]
171
KJ (Ii, 21 (+)) (2t) in (rIp):))))
= Ss
sup
Esy
K
(1)4(1)44))
2g (1.)) 2gg ((())))))
EG
i=1
131
(111))) Bo (of) En (o( K¹ (at. By (mx)) 2o ((12)++))
< S.
sup E.C.C
K
2
i=1
(z/ 2yg (x1) 2y (0( - K (15. 2o (xx) &o (013)H))
-Es..Shie
sup EGE
03
K
[ 1=1
14 Σ O,K
2
Esy :0
sup ECC
(24)
20 (x1) 2g (0(=)T+)
[2_
121 Σ
2
Eyy
sup 2
K
2 (()14))
Eg (x() &o (0(+)++))
2
17 where {at).=] are the Rademacher variables. The second inequality is derived from Jensen's inequality; the third equality uses the standard symmetrization technique and the last inequality utilizes the Shinchin-Kahane inequality (Latala Oleszkiewicz, 1994). Assume that || < Vco. we can obtain that
1 sup 2g E.C.
2 Esa
K"* (Z)4=(1)44)) 2g (at) 2g ( (z(3)+:))
2
1=1
2
71
<
C
2
2 /2c0
Vn
Thus, can obtain
2V200 vn2
8 log 1 n
= F(2;K*) P(2:K) k
with at least probability 8.
B.5. Proof of Lemma A.5
Proof. For a given sequence (ag)a- ag and bygg. we can always find another sequence (by)g such that cos (a, 2g 2 Therefore, without loss of generality, we assume that the angle between 2, and ž,, is within [0, z]-
V (
/
0
1ag22 2g S llag2u - by v2- cos 0
2 sin
2
With sin (0) sin (2) cos (3) and cos (2) V2' have
| by 2gllo0 S si))
where = =(g 2g)g). From the proof of Lemma A.2, we can readily deduce that as m, n - 00, m |ag22 2 -> 0.
>>> log n,
19

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
B.6. Proof of Lemma A.6 Proof. For | k K* 11, we have
KW K*
2 - KW
K Kw1
Σ may k(tt) )) -IKK* - -
1 -
-2r
(K* - k K
m
1
m
2tr (KK- -
K* (KW) T
mwr, x(i) )) ||KK' K"
772
1
2tr (K* -Kw) (mw,k(- -KKK"))KK))) - -IKK* Kw
2tr (K* -K") (ma,kKK-KK)) - |KK- - -K
-
| K (1) K + 1mmw; K -K
RK* K" + mmn, k K' + ||mw; K K 11:)
m
1
Imw.K(0) - K3 1
|mw, K(0) kw
This concludes the proof of Lemma A.6.
B.7. Proof of Lemma A.7 Proof: Based on Lemma B.2, we have
f Z
KW)
-F (2;K')
1
2 T K km²)
- 2 K Kz
n
1
(Ir 2 (K"- )
- K" 22 T -22"
K 1r11/1211 + - | ||r|| 22 - -22 T 1|F
Kw
K* le 12 "1122"
T -22" 1|:
KW
2/2
KW
K" ||
K 12
d (K*)
Ak+11 (K*)
k
2
IKW
n A (K*)
Ak+1 (K+)
The first inequality utilizes the properties of the matrix trace, and the second inequality holds because 2 is an n x column- orthhgoalll matrix, and |K S n n||K* S n (noting that K is a degree normalized matrix). This concludes the proof of Lemma A.7.
20

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
B.8. Proof of Lemma A.8
Proof. Note that ū mew and K
Ei= W/ (O) we have
min
J K
K"
K
KW Il
+min
[Imwr 11=
10
2tr
+ |K*
EE
(1mw (1
2tr (mw;k(*K*) + +1 11:)
==1
1=1
172
@min w
2tr (k) + ||
2tr (()w + |
1=1
t=1
emin
2mtr (K"K*) Σ -2tr (mw; K KW + |
<+min
-2mtr (K"K*) + 2mtr (K*K"> mtr (K"K")
@min
-K" + (KKK")
w
Note that in the proof, since ignoring K* does not affect the optimization of w, we have omitted term | concludes the proof of Lemma A.8.
This
21

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
C. Pseudo code for Section 5.3
Algorithm
Input: Base clusterings (K( pm J
Initialization: Weight {we) ) m the number of cluster hyper-parameter a, the number of iterations p.
Output: Clustering result.
1: while not converged do
2: Compute the matrix (P) (consists of the eigenvectors corresponding to the top largest eigenvalues of K
3: Calculate (w((()) and the descent direction d!d) in Eq. (13).
Own
4: Update wlp+1) as ((++1) <- w(P) + 8d(P)
5: if [w((++) w(p) S then
6: Break.
end if
8: p p
9: end while
10: Apply the k-means algorithm to ((2) to obtain the final clustering result.
D. Related Work
This section reviews related works generalization performance of ensemble clustering. In (Liu al., 2017), the author derived the generalization enror bound of ensemble clustering with finite base clusterings from the perspective of weighted kernel k-means. Denote B (",, k() as a combined binary matrix of m base clusterings where
B(x, -) = b(x) =< b(x)1, b(x) >,
b(x) =< b(x)1. .....,,(())) >,
b (x) [1, (1) (x) =
(0, else
Based on the above definition, the author derived ensemble clustering is equivalent to weighted kernel k-means algorithm,
F Z
-mxx tt
D 1DDD-1/SDD-//// + Gx)
Σ
Imi mn (x)),
2
EEN
where is the CA matrix, Im... mm (x) min&
b(x) (x)
m 113 m7
Enec, Waca)" and we (x) = D x)
Execy (x)
Dm Ei (x), n (1) (xx)). The generalization error bound of ensemble clustering with finite base clusterings is
Engmi me (x)
Im my (I;;)
n
V2rmk
nt Σ
(b)(a)))
-2
STmk
2ark
Σ
n
(Wh(n))) )²)
+
In (1/8) 2n
7
mingex Wb(x)
n min (wb)))
with probability - 5. To the best of our knowledge, this work is the only one that provides generalization error bound for ensemble clustering. Other theoretical analyses related to clustering include generalization performance of multi-view clustering. For example, (Liu, 2023) proposed SimpleMKKM algorithm multi-view clustering and derived its generalization error. (Liang al., 2023) demonstrated the consistency of kernel weights in multi-view clustering and derived its the excess risk bound. Nevertheless, the scenarios they consider are remain limited to finite ensembles.
E. Comparative Experiment
In this section, we provide additional details about the comparative experiments that are omitted in the main text due to space limitations.
22

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
E.1. Details of Datasets
In the comparative experiments Section 6.1, we used 10 benchmark datasets including images, DNA, sensor information, etc. We have summarized the feature information of the datasets in Table 3, and the detailed information is as follows:
1. Phishing Websites:: The dataset consists of a collection of legitimate and phishing website instances. Each website represented by the set of features which denote, whether the website legitimate or not.
2. Rice": A total of 3810 images of rice grains were captured from two species: Cammeo and Osmancik rices. For each grain in these images, seven morphological features were extracted.
3. TOX_7 The dataset contains 171 samples, each with 5748 features, derived from feature selection at Arizona State University's 's repository.
4. Obesity": The dataset contains 2111 instances from individuals the countries of Mexico, Peru, and Colombia. includes 16 features reflecting eating habits and physical conditions, designed to estimate obesity levels.
5. S The dataset includes measurements of the geometrical properties of kernels from three wheat varieties, with seven real-valued features extracted using a soft X-ray technique and the GRAINS package.
6. ALLAML The dataset consists of a DNA microarray data matrix, where rows represent genes and columns represent cancer patients diagnosed with one of two types of leukemia: AML or ALL. The elements of the matrix indicate gene expression levels in the corresponding patients.
7. warpARIOP": The dataset includes over 4000 color images of 126 individuals, comprising 70 men and 56 women. It captures various facial expressions, lighting conditions, and occlusions.
8. 8FRN8: : The dataset includes four sensor readings, termed "simplified distances" (iee. front, left, right and back). Each distance represents the minimum sensor reading within 60-degree are in the respective direction around the robot.
9. Abalone": The dataset is designed to predict the age of abalones by collecting eight physical measurements, including sex, length, diameter, height, whole weight, shucked weight, viscera weight and shell weight.
10. Website Phishing" 10, The dataset includes 1353 websites, with phishing URLs sourced from the Phishtank data archive and legitimate websites collected from Yahoo and starting point directories using a custom PHP web script. It comprises 548 legitimate websites, 702 phishing URLs and 103 suspicious URLs.
E.2. Details Method
The detailed descriptions of 9 comparison methods introduced in Section 6.1 are follows.
1. CEAM (Zhou et al., 2024), this method introduces a novel approach for clustering ensemble which refines weak base clustering results through diffusion on an adaptive multiplex structure.
2. CRS Q (Li et al., 2019), these two methods use a linear determinacy function and a quadratic determinacy function to assess sample stability in clustering ensemble respectively, distinguishing stable samples (cluster core) from less stable ones (cluster halo) for robust clustering.
.m.mat
23

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Table 3. Size of different datasets
No.
Dataset
#Instance
#Feature
#Class
DI
Phishing Websites
2456
30
2
D2
Rice
3810
2
D3
TOX_171
171
5748
4
D4
Obesity
2111
16
7
D5
Seeds
210
3
D6
ALLAML
72
7129
2
D7
WarpAR1OP
130
2400
10
D8
WFRN
5456
4
4
D9
Abalone
4177
8
3
DIO
Website Phishing
1353
9
3
Table Performance (%) evaluation of different datasets based on the ARI metrie. We have highlighted values of the best- pest-performin method in bold, and the second- best method is marked with an underline.
Method
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
Average
CEAM (TKDE'24 24)
6,6+12
42.8
12.9
20.4+:
59.0#1a
2.7
2.5+1
10.8
12.8#5
10.1
18.1
CEs (AI' 19)
2.41+
3.0=10
14.0
20.3
33.3
18.3*6
0.2+²
6.827
15.4
9.629
12.3
CEs²Q (AIJ' 19)
1.743
3,5=7
12.4
20.0
31.221
18.516
0.312
9.0s1
15.2
6,745
11,8
LWEA (TCYB' 18)
-0.5
62.9+4
13.1
21.2+1
57.5
18.5+6
0.0+2
10.0++
13.5
8.846
20.5
NWCA (arXiv'24)
-0.5
62.324
12.9
21.621
56.326
19.8
-0.1
10.4
13.3
11.7
20.8
ECCMS (TNNLS'2
-0.5
56.
13.5
21.341
60.8
19.0#6
-0.3
12.2+4
14.0
10.5
20.7=6
MKKM (arXiv' 18)
8.8
47.1
9.542
14.21s
53.8
13.6
2.112
7.243
10.9
10.1
17.7
SMKKM (TPAMI'23)
8,845
41.9
14.6
17.04a
55.5*m
13.249
3.5+1
7.2+4
15.7
12.2
19.0
SEC (TKDE' 17)
8.9
23.8
12.8
13.54s
26.9
13.5
1.1+2
5.627
7.2+s
5.245
11.9
Fix 0.1 Proposed
30.9
69.2+1
15.8
22.1
67.5+s
20.64s
2.6+1
12.0ss
14.8
14.5
27.0=a
30.9
69.2
16.7
22.1+2
67.5
21.5
4.2+1
18.6
16.0#a
14.5 1-6
28.1
Table Performance (%) evaluation of different datasets based on the F-score metric. have highlighted the values hest- performing method in bold, and the second- best method marked with underline.
Method
D1
D2
D3
D4
DS
D6
D7
D8
D9
D10
Average
CEAM (TKDE'24 24)
60.5
79.4
46.4
42.7
83.1
66.0a2
22.812
51.4
49.9
61.8
56.4
CEs (AI'' 19)
58.0#4
59.5
46.3
42.0#z
65,0#m
72.2+a
19.3+2
49.1
51.7+3
62.7+6
52.6+4
CEs²Q (AI' 19)
57.4
60.3+s
44.7aa
41.9+2
62.9
72.4
19.2
50.5
51.643
60.3
52.1
LWEA (TCYB' 18)
55.5
89.6+1
46.0a3
43.2+1
81.7+4
72.4+3
18.6+a
49.5
51.3+2
61.2+*
56.9+2
NWCA (arXiv'244 24)
55.5
89.411
45.9aa
43.621
80.745
73.222
18.812
49.2a1
51.2+2
63.524
57.1
ECCMS (INNLS'24)
55.5
85.6+12
46.14a
43.3+1
84.0+a
72.643
18.542
51.0+3
51.6+3
62.5+4
57.1+3
MKKM (arXiv' 18)
62.1
82.6
42.9a3
37.41s
79.817
70.8
25.243
50.2+2
49.7
62.5
56.3
SMKKM (TPAMI'23)
62.9
73.747
47.7
39.8
80.6
69.9+4
23.44
53.2+1
52.2+1
63.3
56.7
SEC (TKDE' 17)
62.2.10
71.9
46.0aa
37.214
59.9
71.0z4
20.5
48.2
45.74s
58.845
52.1
Fix a = 0.1
76.5
91.640
48.9
43.7+t
87.641
73.8
21.44a
55.4
51.5+
65.1
61.5+3
Proposed
76.5
91.611
50.0
43.7
87.641
73.8
27.4
63.3
52.3
65.1
63.1
3. LWEA (Huang et al., 2018), this method enhances ensemble clustering by employing local weighting strategy based cluster uncertainty and ensemble-driven validity measure.
4. NWCA (Zhang et al., 2024), this method discovers that smaller clusters have higher precision and proposes the normalized ensemble entropy to weight different clusters accordingly.
24

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
5. ECCMS (Jia et al., 2024), this method enhances co-association matrices in ensemble clustering by extracting high- confidence pairings from base clusterings and propagating them to refine the CA matrix.
6. MKKM (Bang et al., 2018), this method utilizes min-max model to manage adversarial perturbations, ensuring the identification of accurate clusterings by optimally balancing the influence of multiple data views.
7. SMKKM (Liu, 2023), this method transforms complex min-max problem into simpler minimization of an optimal value function, optimizing kernel coefficients and clustering matrices effectively to achieve robust clustering performance.
8. SEC (Liu et al., 2017), this method combines the strengths of the co-association matrix with the efficiency of weighted K-means clustering and derives its generalization error bound.
E.3. Details of Comparative Experiment
In the appendix, we continue to demonstrate the performance of the algorithm on ARI and Purity. As can be seen in Table and Table 5, on both ARI and Purity, our method consistently leads against the compared methods across all datasets. For example, the D1 (Phishing) dataset, 8.9%; in terms of Purity, ours is at 76.5%, whereas the second-best is 62.9%. Moreover, even with fixed our method outperforms others on these two metrics, and while it may not be the second-best method on some datasets, such as D8 (WFRN), it is only slightly weaker than the second-ber best method (with a 0.2% difference in ARI).
method achieves an ARI of 30.9%, while the second-best method only reaches
0.5
0.5
05
0.5
(a) Phishing
(b) Rice
(c) TOX_171
(d) Obesity
(c) Sceds
WWI
NWI
(f) ALLAML
WarpAR10P
(h) WFRN
Abalone
(j)
Website
Figure 4. Analysis of hyperparameter a in K. We vary the value of from 0.1 to 0.9, with an incremental step of 0.1.
E.4. Hyper-parameter Analysis
In this paper, we have only one hyper-parameter, a, which serves as the threshold for extracting high-confidence elements. Fig. 4 shows the performance of our model under different settings. It can be seen that our method is quite robust across most datasets, and the optimal hyper-parameter is generally between 0.1 and 0.3. From the comparative experiments, we can also see that even with fixed parameters, our algorithm performs well. Therefore, we think that our algorithm is robust to the hyper-parameter a.
E.5. Ablation Experiment
Table 6 presents the results of our ablation experiments. When the Bias term is removed, the model becomes completely dominated by Diversity, which may drive the optimization process away from the correct direction and cause significant performance degradation; when the Diversity term is removed, the model loses the ability to leverage differences among base clusterings, leading to noticeable performance drops. Overall, in the vast majority of datasets, removing either Bias or
25

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Table Ablation experiments (clustering performance: %). We separately remove the Bias (denoted as w/o Bias) and the Diversity term (denoted w/o Diversity) from the original model to observe changes in the model's performance across three metrics.
Method
D1
D3
D4
D5
D6
D7
D8
D9
D10
NMI
Proposed
22.0:11
59.0+1
21.1
29.4
67.5
15.0
22.9a2
27.5
15.8
12.4
w/o Bias
8.724
38.521
19.3
27.0=a
59.4
10.5
20.0aa
18.2
15.5
10.5
w/o Diversity
23.7am
40.8
19.5
29.0a2
67.5
14.7.4
25.1
17.2
7.3a2
12.1
ARI
Proposed w/o Bias
10.9
69.5
16.7
22.1
67.5as
21.5
4.2+1
18.6
16.0
14.5
8.8
41.9
14.6+3
17.0as
55.5+1
13.249
3.5
7.2+4
15,7
12.2
w/o Diversity
6.9
64.9
15.0
21.9=a
58.024
21.4
3.1+1
5.0+1
5.623
14.1
Purity
Proposed 76.5
91.721
50.0
43.7
87.62²
73.8
27.4
63.3
52.3
65.1
w/o Bias
62.9
73.7a7
47.7
39.8
80.6as
69.914
23.4
53.2at
52.2a1
63.3a4
w/o Diversity 11.4+t1
84.2#
47.3
43.1
87.2#3
73.8+2
27.7
52.8+1
45.0+a
64.8#s
Diversity results in inferior clustering performance, while the complete model achieves the best results, confirming that the joint optimization of both components essential.
E.6. Ensemble Size Analysis
Figure reports the results of all methods across different datasets by varying the ensemble size m in terms of NMI. It can be observed that our method outperforms the compared SOTA methods on almost all datasets, except the ALLAML and Abalone datasets when the ensemble size is 10. Additionally, is evident that the performance of our method generally improves m increases, which aligns with the conclusion derived from Theorem 3.1.
26

---

Generalization Performance of Ensemble Clustering: From Theory to Algorithm
Phishing
Rice
TOX 171
Obesity
Seeds
0.
0.86
0.
0.4
66
0.12
0.22
NM
04-
0.08
02-
0112
0.12
0.12
size
ALLAML
WarpAR1PP
WERN
Abalone
Wabsite
0.24
0:12
0.24
0.22
0:11
0:5
0.0
0:14
0.14
0.07
0.12
006
0:17
0.1
0.0
0.9
Ensemble size
Ensemble size m
Ensemble size m
Ensemble size
Ensemble size
- CEAM ---- C ---- C ---- LWEA MKKM - SimpleMiKKи - SEC dd ECCMS -q-- NWCA - Preposed
Figure each dataset, vary the number of base clusterings in the ensemble observe the corresponding changes performance, measured by NMI.
27


Reviews:
[{"review_id": "20KXSIDppw", "reviewer": "Reviewer_ms8h", "summary": "The ensemble clustering is the problem of combining multiple base clusterings into a more accurate final clustering result. Prior research shows advances of ensemble clustering in practice while the theoretical analysis has fallen behind. \n\nThis paper provides the first generalization bound of emsemble clustering and extend their generalization bound into a new algorithm. The authors also conducted experiments to validate their bounds as evidence.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We sincerely thanks for all your constructive comments!**\n>**Weakness 1: Improve writing quality and clarify some concepts**\n\nThanks for your suggestions! We will make the following changes in the final version of the paper:\n- Provide a more detailed explanation of ensemble clustering and motivation in Introduction\n- Rename Section 2.2 from \"Co-Association Matrix\" to \"Ensemble Clustering\" and add a simple flowchart to illustrate the process. (Fig can be seen in <https://anonymous.4open.science/r/ICML8598/FigA1.pdf>)\n- Add Section 2.3 \"Problem Definition\" to clarify the problem definition\n- In Section 3 \"Generalization Performance\" we will provide more details for several equations\n- In Section 4 \"Key Factors in Ensemble Clustering\" we will include a more detailed derivation of Eq. (8) to Eq. (9)\n- Move some important experimental conclusions into Section 6 Experiments instead of Appendix\n- Review the entire paper to avoid undefined symbols and typos\n\n>**Comment 1: A typo in $\\bar{A}=1/m\\sum_i^m A^{(t)}$**\n\nThe correct form is $\\bar{A}=1/m\\sum _t^m A^{(t)}$, and we will correct it in the final version.\n>**Comment 2: Definition of matrix $D$ and notation $D^{(t)−1/2}$ are confusing**\n\n$D^{(t)}$ is the degree matrix of similarity matrix $A^{(t)}$, which is diagonal and defined as $D_{jj}^{(t)}=\\sum_{i=1}^n A_{ij}^{(t)}$ and $D^{(t)-1/2}$ is defined as a diagonal matrix where the diagonal elements are $(D _{jj}^{(t)})^{-1/2}$ and the off-diagonal elements are 0. We will define it in the final version.\n>**Question 1: Is the gap condition between the k-th and k+1-th eigenvalues of $K^\\*$ mild or generally true**\n\nIt is a mild condition and can be explained in two aspects.\n1. $K^*$ is regarded as the true similarity (kernel) of the data, and in many papers regarding kernels, they also adopted this assumption, such as [1] and [2].\n2. On different datasets, we randomly sampled base clusterings and then calculated their means to approximate $K^*$ (since the expectation is unattainable). The results show that in our 1000 experiments, **not once** were the k-th and (k+1)-th eigenvalues equal. The experiment can be seen in <https://anonymous.4open.science/r/ICML8598/FigA2.pdf>\n\nTherefore, it is a **mild condition** and we will incorporate this condition into the General Assumptions section in the final submission of our paper to avoid misunderstandings.\n\n[1] Error bounds for kernel-based approximations of the Koopman operator.\n\n[2] Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation.\n\n>**Question 2: A single clustering algorithm (like kernel k-means) can ensure convergence to the true value, but why does ensemble clustering require $m\\gg \\log n$. Experiment shows the loss is divergence when $m=\\log \\log n < \\log n$. Is this a \"more is less\" contradiction?**\n\n- It's important to note that in the generalization analysis of single clustering algorithm (like kernel k-means), it is often assumed that the data features are accessible or the kernel function represents the true similarity relationships in the data. Their studies concern the necessity of generalizing from finite-dimensional matrices to infinite-dimensional integral operators. But in ensemble clustering, our similarity matrices are binary and generated by $n\\times 1$ vectors (**no features or kernel functions**). We can view features or kernel functions as high-dimensional representations of the data, while considering the base clusterings in ensemble clustering as **special discrete one-dimensional projections**. The problem we are addressing is whether we can achieve the same results using **only** these discrete one-dimensional embeddings, instead of relying on high-dimensional representations. Our research shows that consistent results can be obtained when $m\\gg \\log n$. We believe this is valuable not only in ensemble clustering but also in other areas of machine learning.\n\n- Note that the loss diverges when $m = \\log \\log n$ in Section 6.3, Figure 3. However, in this experiment, the sample size $n$ increases with $m$, **rather than being fixed**. In Appendix E.6, Figure 5, we present an experiment where the clusterings size $m$ is increased while the sample size $n$ is fixed. This experiment shows that our clustering accuracy improves as $m$ increases (Our convergence rate $O(\\sqrt{\\frac{\\log n}{m}} + 1/\\sqrt{n})$ also shows that as 𝑚 increases and $n$ is fixed, the error is reduced). A more intuitive explanation is that, in ensemble clustering, we would like to approximate the true kernel function using $m$ binary similarity matrices (with dimension $n$). Here, $n$ should be considered as the **feature dimension** of the matrices, and $m$ as the **number of samples** (number of similarity matrices). As the feature dimension $n$ increases, we need to add more samples (similarity matrix) to avoid underfitting. Thus, this is **not a \"more is less contradiction\"**.", "claims_and_evidence": "Yes. The generalization bounds have been proved rigorously and experimental results also provide evidence.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I have briely read the statement and proofs in appendix. The claims and the way to get there seems correct.", "experimental_designs_or_analyses": "The authors have run experiments against a few existing benchmarks. The evaluation method also makes sense to me. Detailed introductions of experiment design is included in appendix.", "relation_to_broader_scientific_literature": "Given the success of ensemble clustering in practice,  results in this paper can benifit any machine learning research that conducts ensemble clustering as a subroutine.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength:  This paper is a rigorous theoretical study of ensemble learning and the results proved are novel .\n\nWeakness:  This paper could certainly benefit from improvements in its writting quality. There is no formal problem definition and I have to read the Fred-Jain paper to understand many concepts. Authors should not assume every reader is an expert in the area of study.", "other_comments_or_suggestions": "1. On page 2, section 2.2, the definition of $\\bar{A}=\\frac{1}{m}\\sum_{i=1}^m A^{(t)}$ is a typo?\n2. On page 2, section 3, the definition of matrix D can not be found anywhere. Moreover the notation $D^{(t)-\\frac{1}{2}}$ is very confusing.", "questions_for_authors": "1. Can you please provide some insights on the gap condition between the k-th and k+1-th eigenvalues of K^*? Is it a mild condition or is it generally true in practice?\n\n2. The $\\sqrt \\frac{\\log n}{m}$ bound means it requires $m>>\\log n$, namely, using more than $\\log n$ base clusterings, to guarantee convergence to the ground truth, which can be achieved by a single clustering (say kernel k-means). Moreover, the experiment also show the loss is divergence when $m=\\log \\log n<\\log n$. Is this a \"more is less\" contradiction?", "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": "", "extra_scores": {}}, {"review_id": "Ctmu8ULNak", "reviewer": "Reviewer_kz2j", "summary": "This paper investigates the theoretical foundations of ensemble clustering, focusing on its generalization performance, including generalization error, excess risk, and consistency. The authors derive theoretical bounds for these indicators and propose a new ensemble clustering algorithm based on their findings, demonstrating significant improvements over existing methods. The key contributions and findings are as follows:\n\n1.\tThe paper establishes the convergence rate for generalization error and excess risk, showing that increasing the number of base clusterings helps reduce the generalization error but cannot eliminate it. Furthermore, it proves that when both the number of samples nnn and base clusterings mmm approach infinity, with m>>log n, ensemble clustering achieves uniform convergence, meaning the clustering result progressively approximates the true data structure.\n\n2.\tThe study reveals that clustering performance can be improved by minimizing the bias of base clusterings (i.e., the difference between each base clustering and its expectation) while maximizing diversity among them. The authors further establish that maximizing diversity closely relates to robust optimization models.\n\n3.\tLeveraging this theoretical framework, the authors introduce a novel ensemble clustering algorithm. It utilizes high-confidence elements to approximate the expected co-association matrix and formulates clustering as a min-max optimization problem. The algorithm optimizes the base clustering weights using a descending step-degree method to ensure low bias and high diversity. Experimental results on multiple datasets demonstrate superior performance compared to state-of-the-art methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We sincerely thanks for all your constructive comments!**\n\nWe denote \"Experimental Designs Or Analyses\" as E, \"Questions For Authors\" as Q, and \"Weakness\" as W to save space.\n>**E2 & W7: Global optimal solution**\n\nOur model is a **convex optimization problem of w** (optimization function is convex and equality constraint is affine). Specifically, for our optimization function $J(w)$, we have\n$$J(aw_1+(1-a)w_2)=\\max _{Z\\in\\Gamma}tr((2\\tilde{K}+K^{aw_1+(1-a)w_2})ZZ^T)$$\n\n$$=\\max _{Z\\in \\Gamma}tr((2\\tilde K+\\sum _{t=1}^m{(aw _{1t}+(1-a)w _{2t})^2K^{(t)}})ZZ^T)$$\n$$\\le\\max _{Z\\in\\Gamma}tr((2\\tilde{K}+\\sum _{t=1}^m{(aw _{1t}^{2}+(1-a)w _{2t}^{2} )K^{(t)}})ZZ^T)\\quad Given\\ a(a-1)\\le 0$$\n$$=\\max _{Z\\in\\Gamma}tr((2a\\tilde{K}+aK^{w_1}+2(1-a)\\tilde{K}+(1-a)K^{w_2})ZZ^T)$$\n$$\\le a\\max _{Z\\in\\Gamma}tr((2\\tilde{K}+K^{w_1})ZZ^T)+(1-a)\\max _{Z\\in\\Gamma}tr((2\\tilde{K}+K^{w_2})ZZ^T)$$\n\n$=aJ(w_1)+(1-a)J(w_2)$,\n\nwhich means it is convex. Obviously, the constraint $\\sum_{t=1}^m w^{(t)}=1$ is affine. Therefore, it can be theoretically demonstrated that our method will achieve the **global optimal value** with different initializations. As verified by repeated experiments on various datasets, with random initializations (see <https://anonymous.4open.science/r/ICML8598/FigA3.pdf>), our algorithm consistently attains the global minimum.\n\nWe initialize the learning rate as $\\min(0.1,\\min_t(w_t/\\nabla_t))$ to maintain $w\\ge0$. When reaching the minimum loss with above learning rate, we use the Golden search method for finer updates, stopping when $|w_{new}-w_{old}|<0.001$ (i.e., convergence criterion is 0.001). We set the maximum number of iterations to 100, but in practice, the algorithm terminates after just a few dozen iterations.\n>**W4,5 & Q1: Hyperparameter setting**\n\n**Our algorithm has only one hyperparameter**: threshold $\\alpha$ and outperforms SOTA methods with $\\alpha$ even fixed at 0.1. Besides, In Appendix E.4, Fig 4, we have exhibited the performance across different datasets when the **threshold ranges from 0.1 to 0.9** using grid search (a method consistent with all the baselines). The results show that when the threshold is in {0.1,0.3}, the model achieves better performance, indicating our algorithm is **not sensitive to the hyperparameter**.\n>**E3: Ablation study & Noise situation**\n\nIn Appendix E.6, Table 6, we have conducted ablation experiments. It shows that performance declines when either the Bias or Diversity module is removed, indicating both are **important for optimal results**.\n\nAs your suggestions, we add more baselines (AAAI24, TKDD23, Inf Fus22, AAAI21) to validate our method under different levels of noise (from level 10% to 90%). The results show that our method **remains the best** in noise condition, which further demonstrate its robustness. The experiments are in <https://anonymous.4open.science/r/ICML8598/TabB12.pdf>\n>**W6 & Q2: Computational efficiency**\n\nThe time complexity of each module in our method is as follows:\n- Construct each similarity: $O(n^2)$\n- Calculate \\tilde{K}: $O(n^{2.376})$\n- Solve Z: $O(n^2)$\n- Compute reduced gradient: $O(n^2)$\n- Update $w$: $O(m)$\n\nNote that in matrix multiplication and eigenvalue decomposition, we can employ accelerated methods such as Coppersmith-Winograd algorithm. Thus, the time complexity of our method is $O(n^{2.376})$ and most of the baselines have the same time complexity, as they also involve matrix multiplication. We also conducted time cost experiment (which can be seen in <https://anonymous.4open.science/r/ICML8598/FigA4.pdf>), and the results show our method **outperforms these matrix optimization-based methods** in terms of both performance and time cost.\n>**W1,8: Verification of theoretical results and necessary conditions for consistency**\n\nOur convergence rates of generalization error and excess risk are both $O(\\sqrt{\\log n/m}+1/\\sqrt{n})$. **In Sec 6.3, Fig 3, we have demonstrated the convergence rate of the excess risk bound on real dataset.** According to your comments, we conduct experiment on generalization error rate in <https://anonymous.4open.science/r/ICML8598/FigA5.pdf>, and the result shows that it is also consistent with our theory. \n\nWe derived the sufficient condition for consistency is $m\\gg\\log n$, and **it is noteworthy that we are the first to theoretically depict the relationship between clusterings number and sample size**. Additionally, the conclusion that $m\\gg \\log n$ is a mild condition, indicating that we only need a few base clusterings to satisfy the consistency condition. However, we think the necessary condition is very challenging and we have rarely seen any similar research on this topic. We would like to leave this as our future work.\n>**W2,3: Symbolic definitions and Notations**\n\nAs suggested, we will revise the paper to avoid undefined notations. For example, we will correct the typo where $t$ is mistakenly written as $i$ in definition of $\\bar{A}$, and add an additional explanation for it.", "claims_and_evidence": "The claims presented in the paper are well-supported by both theoretical derivations and experimental validation.\n\n1. The paper rigorously derives the generalization error bound, excess risk bound, and sufficient conditions for the consistency of ensemble clustering. These theoretical results establish a solid foundation for the feasibility and effectiveness of the proposed algorithm, providing strong theoretical support for ensemble clustering method selection.\n\n2. Through comparisons with state-of-the-art methods, the experimental results demonstrate the superiority of the proposed algorithm across multiple datasets. The algorithm obtains good performance in terms of NMI, ARI, and Purity.\n\n3. The paper effectively integrates the bias-diversity tradeoff principle into ensemble clustering optimization. By minimizing bias and maximizing diversity, the proposed approach enhances clustering performance. This concept is further validated through both algorithmic design and empirical results.", "methods_and_evaluation_criteria": "In this paper, several evaluation criteria such as NMI, ARI and Purity are adopted at the same time. This comprehensive evaluation method is more comprehensive and can evaluate the performance of the algorithm from different perspectives. NMI and ARI provide an assessment of association with real labels, while Purity focuses more on clustering accuracy. By using the multi-index evaluation method, the effectiveness of the integrated clustering method can be comprehensively measured and its applicability in practical problems can be ensured.", "theoretical_claims": "I have reviewed the validity of the proofs for the theoretical claims presented in the paper. The key theorems—3.1 (generalization error bound), 3.2 (excess risk bound), and 3.3 (consistency)—are derived in a detailed and structured manner. The proof methodology is logical and rigorous, leveraging probability theory and statistical consistency principles. Intuitively, the results align with theoretical expectations, and the reasoning appears sound.", "experimental_designs_or_analyses": "The experiments effectively demonstrate the advantages of the proposed method, but there are areas that could be further improved for a more comprehensive evaluation.\n\n1. The paper evaluates the algorithm on multiple datasets.\n\n2. The paper discusses key parameters such as convergence rate, number of iterations, and learning rate. However, a more detailed exploration of how these parameters influence performance across different datasets would strengthen the experimental findings.\n\n3. Certain aspects that could enhance the credibility of the results are not explicitly addressed. For instance, ablation studies on the impact of individual components in the algorithm (e.g., the weighting strategy, bias-diversity optimization) could provide deeper insights into the contributions of each part. Additionally, comparisons with a broader range of baseline methods, particularly under different noise conditions, would further support the claims of robustness.", "relation_to_broader_scientific_literature": "This paper fills this gap in the generalization performance of ensemble clustering by providing a comprehensive analysis of the generalization error, excessive risk, and consistency of ensemble clustering.", "essential_references_not_discussed": "The paper has cited and discussed relevant prior findings and results necessary for contextualizing its contributions.", "other_strengths_and_weaknesses": "**strengths**\nThis paper provides a theoretical analysis of the generalization performance of ensemble clustering, addressing a key gap in understanding the theoretical foundations of ensemble clustering.\n\n**weaknesses**\n\n1.\tWhile the paper establishes sufficient conditions for clustering consistency, it does not discuss necessary conditions.\n\n2.\tSome symbolic definitions for intermediate processes are omitted, which may affect clarity.\n\n3.\tIn Section 2.2, the notation i in the definition of \\bar{A} is not explicitly explained.\n\n4.\tThe selection of an appropriate threshold is a challenge.\n\n5.\tAlthough the paper mentions a method for setting the threshold, it does not thoroughly analyze the impact of different threshold choices on the results.\n\n6.\tThe computational complexity of the proposed algorithm is not analyzed in detail.\n\n7.\tThe optimization process, which uses a reduced gradient descent method to optimize the weighted matrix W and spectral embedding Z, lacks an in-depth discussion of its convergence, efficiency, and stability in practical applications. Since gradient descent methods can be sensitive to initialization, it remains unclear whether the proposed approach guarantees a global optimal solution.\n\n8.\tWhile the paper validates its theoretical findings through experiments, these primarily focus on performance comparisons between algorithms. The verification of the theoretical results, such as experimentally confirming whether the convergence rates of generalization error and excess risk align with theoretical expectations—is not thoroughly addressed.", "other_comments_or_suggestions": "I have no other comment.", "questions_for_authors": "This paper presents a new integrated clustering algorithm based on theoretical framework. How do different hyperparameter Settings affect the performance of the algorithm, and how to choose the optimal hyperparameter?\n\nHow do the results of the proposed algorithm compare with other state-of-the-art methods in terms of computational efficiency and scalability?", "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": "", "extra_scores": {}}, {"review_id": "l9FflFEndL", "reviewer": "Reviewer_smn4", "summary": "This paper explores the theoretical foundations of ensemble clustering, focusing on its generalization performance, including generalization error, excess risk, and consistency. The authors derive convergence rates for both generalization error and excess risk, which are bounded by $\\mathcal{O}(\\sqrt{(\\log n / m)} + 1/\\sqrt{n})$ ($n,m$ are the numbers of samples and base clusterings) and demonstrate that ensemble clustering achieves consistency when both m and n approach infinity, and $m \\gg \\log n$. Recognizing that $m, n$ are finite in practice, the authors theoretically demonstrate that better clustering performance can be achieved by minimizing the bias of base clustering from its expectation and maximizing the diversity among base clusterings. Based on this, they instantiate their theory to a novel algorithm that utilized high-confidence pairwise similarity to approximate the expected clustering and solve it using a reduced gradient descent method, achieving state-of-the-art performance.\nKey contributions include: \n(1) For the first time, the authors derive the theoretical guarantees for generalization error, excess risk, and consistency of ensemble clustering; \n(2) They develop a bias-diversity decomposition and innovatively establish the relationship between diversity and robustness in ensemble clustering;\n(3) They propose a practical algorithm validated through extensive experiments. This work bridges theory and practice, offering both rigorous analysis and a high-performing solution for ensemble clustering.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**We sincerely thanks for all your constructive comments!**\n>**Weakness 1. Statistical significance tests**\n\n\nWe conducted paired t-tests on our method using NMI, ARI, and Purity metrics, and the results show that our method significantly **outperforms the sota methods** compared across almost all datasets. We believe this further demonstrates the effectiveness of the proposed approach. The experiment is in <https://anonymous.4open.science/r/ICML8598/TabB345.pdf>\n>**Weakness 2. Describe some key conclusions in the main text**\n\nDue to page space limitations, we placed some conclusions in the appendix. Following your suggestion, we will move the key conclusions from Appendix E.4. Hyper-parameter Analysis, E.5. Ablation Experiment, and E.6. Ensemble Size Analysis into the main text and noted that readers can find the detailed analyses in the appendix.\n>**Weakness 3: Weakness 2. Time complexity of the proposed algorithm**\n\nThe time complexity of our method is composed of the following parts: Construct each similarity, Calculate $\\tilde{K}$, Solve $Z$, Compute reduced gradient, and Update $w$. Through theoretical analysis, the **time complexity** of our method is $O(n^{2.376})$. Detailed time complexities for each module can be found in the comments for Reviewer 2. Additionally, the time complexities of most baseline methods we compared are also $O(n^{2.376})$, yet our method **significantly outperforms** them. We also conducted time cost experiments on different datasets, and the results confirm that our method surpasses these Co-associate matrix optimization-based methods in terms of both performance and time efficiency. The experiment can be found in <https://anonymous.4open.science/r/ICML8598/FigA4.pdf>\n>**Weakness 4: Clarify formula derivation (Eq. (8) to Eq. (9))**\n\nFor $\\min_w -2tr(K^wK^*)$, our objective is to adjust the weights ${w}$ such that the weighted CA matrix $K^w$ closely approximates its expected value $K^*$. To this end, we **reformulate the problem as finding a low-dimensional embedding** $Z$ for $K^*$. This approach consolidates 1) $max_w tr(K^wK^* )$ and 2) $\\max_Z tr(K^* ZZ^T)$ into a single expression, $max_Z tr(K^*ZZ^T)$, which corresponds to the Bias term in the objective function of Eq. (9). For $\\min_w tr(K^wK^w)$, we apply a similar strategy. Specifically, for the term $\\min_w tr(K^wK^w)$, we replace one instance of $K^w$ with the low-dimensional embedding $Z$, i.e., $tr(K^wK^w)\\Rightarrow \n \\max_Z tr(K^wZZ)$, and transforming it into a min-max optimization problem. Additionally, we constrain $Z$ to be an orthogonal matrix in its columns. It is important to note that the original constraint $w^Tw=1$ is nonconvex and a standard relaxation technique is $w^Tw\\le 1$. However, we revise this to $w1 = 1$ and also modify the definition of $K^w$. This approach has the advantage of allowing $w$ to be better interpreted as a weight distribution.\n>**Question 1: Generalization form of loss function**\n\nThere is a **general framework** for our method. For a continuously differentiable and strongly convex function $\\phi$, let $\\Omega$ be a convex set where $x, y \\in \\Omega\\$, we can define the Bregman divergence as:\n$$D_\\phi(x, y) = \\phi(x) - \\phi(y) - \\langle \\nabla \\phi(y), (x-y) \\rangle. $$\n\nThus, we can transform Eq. (7) in the text into a more generalized form:\n$$D_{\\phi}(K^*, K^w) = \\frac{1}{m} \\sum_{t=1}^m D_{\\phi}(K^*, mw_tK^t) - \\frac{1}{m} \\sum_{t=1}^m D_{\\phi}(K^w, mw_tK^t),$$\n\nwhere $K^w = (\\nabla \\phi)^{-1}\\left( \\frac{1}{m} \\sum_{t=1}^m \\nabla \\phi(mw_tK^t) \\right) $.\n\nConsequently, we can derive a generalized Bias-Diversity decomposition:\n$$\\underset{w}{\\min} \\, -\\langle \\nabla \\phi(K^w), K^* \\rangle + \\langle \\nabla \\phi(K^w), K^w \\rangle - \\phi(K^w)$$\nBased on this, we can let $\\phi(x)$ be various metric functions, such as KL divergence, JS divergence, etc. We believe **this is a more significant conclusion** and will be further discussed in future work.", "claims_and_evidence": "The methods proposed in the paper are well-aligned with the ensemble clustering problem and their claims made in this paper are supported by both theoretical analysis and experiments. I think the theoretical results in this paper are clear, providing generalization error, excess risk bounds, and consistency. The exploration of Bias and Diversity in ensemble clustering is well-developed, with a solid theoretical foundation and sufficient experimental validation.", "methods_and_evaluation_criteria": "The methods proposed in the paper are well-aligned with the ensemble clustering problem. The authors define the objective function of ensemble clustering in the form of a spectrum, which is logical and reasonable. Using this objective function, the authors investigate its generalization performance, including generalization error, excess risk, and consistency. These theoretical insights are of significant importance for research in ensemble clustering. Unlike heuristic definitions of the objective function, the authors instantiate their theory to develop a new algorithm. I believe this is highly valuable and provides a fresh perspective for the theoretical study of ensemble clustering. The adopted benchmark datasets (10 real datasets) and evaluation criteria (NMI, ARI, Purity) are appropriate for measuring clustering performance and the experiments they designed are reasonable and useful.", "theoretical_claims": "The authors provide several important theoretical claims related to ensemble clustering, specifically regarding its generalization performance, excess risk, and consistency. Besides, they provide a bias-diversity decomposition for ensemble clustering under their designed objective function, along with a proof of the equivalence between diversity and robustness. I have reviewed all the proofs provided, and the theoretical claims in this paper appear to be solid.", "experimental_designs_or_analyses": "The authors provide several important theoretical claims related to ensemble clustering, specifically regarding its generalization performance, excess risk, and consistency. Besides, they provide a bias-diversity decomposition for ensemble clustering under their designed objective function, along with a proof of the equivalence between diversity and robustness. I have reviewed all the proofs provided, and the theoretical claims in this paper appear to be solid.", "relation_to_broader_scientific_literature": "This paper significantly advances the theoretical understanding of ensemble clustering, offering theoretical guidance for practical applications. It establishes a formal link between model diversity and robustness, providing a theoretical foundation for enhancing performance in various ensemble-based methods. Notably, the algorithm introduced is not heuristic but directly derived from their theoretical framework, likely increasing scholarly focus on theoretical research.", "essential_references_not_discussed": "I have reviewed the references cited in the paper and did not find any significant omissions.", "other_strengths_and_weaknesses": "Strengths\nOriginality: The paper offers a novel theoretical framework for ensemble clustering.\nQuality: The theoretical results are rigorous and well-supported by comprehensive experiments.\nClarity: The paper is clearly written, with detailed explanations of complex concepts and a well-structured presentation of the theoretical derivations and experimental results.\nSignificance: The findings contribute valuable insights into the practical application of ensemble clustering, offering guidance for optimizing clustering performance in real-world scenarios.\nWeaknesses\n1.The paper would benefit from providing statistical significance tests to confirm the robustness of the reported improvements (e.g., paired t-tests or Wilcoxon signed-rank tests).\n2.The details of some experiments are not fully detailed in the main text but are mentioned to be in the appendices. It would be beneficial to include a brief summary of key findings from these experiments in the main paper.\n3.Although the authors have conducted extensive theoretical analysis of their algorithm, I believe it is necessary to add a part discussing the time complexity of their algorithm, as this would help to understand its practical implementation in real-world scenarios.\n4.The authors' derivation from Equation (8) to Equation (9) seems somewhat abrupt. I would suggest they include more details to clarify the process.", "other_comments_or_suggestions": "I don’t have other comments or suggestions.", "questions_for_authors": "Besides the questions I mentioned in the Weakness section, I would like to ask the authors whether they have considered more general cases when instantiating their theory, beyond just this spectral form of loss function?", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: All reviewers recommend acceptance, and appreciate the theoretical contributions of the work. Although there were some technical queries raised in the initial reviewing stage, the authors did a good job in addressing these.
In addition to some strong theoretical results in a field which is not brimming with such contributions, the proposed methodology also shows strong practical performance in comparison with relevant benchmarks.
Decision: Accept (poster)