Generalization Performance of Ensemble Clustering: From Theory to Algorithm

We sincerely thanks for all your constructive comments!

Weakness 1. Statistical significance tests

We 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

Weakness 2. Describe some key conclusions in the main text

Due 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.

Weakness 3: Weakness 2. Time complexity of the proposed algorithm

The 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

Weakness 4: Clarify formula derivation (Eq. (8) to Eq. (9))

For $\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 \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.

Question 1: Generalization form of loss function

There 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: $D_\phi(x, y) = \phi(x) - \phi(y) - \langle \nabla \phi(y), (x-y) \rangle.$

Thus, we can transform Eq. (7) in the text into a more generalized form: $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),$

where $K^w = (\nabla \phi)^{-1}\left( \frac{1}{m} \sum_{t=1}^m \nabla \phi(mw_tK^t) \right)$.

Consequently, we can derive a generalized Bias-Diversity decomposition: $\underset{w}{\min} \, -\langle \nabla \phi(K^w), K^* \rangle + \langle \nabla \phi(K^w), K^w \rangle - \phi(K^w)$ Based 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.

We sincerely thanks for all your constructive comments!

We denote "Experimental Designs Or Analyses" as E, "Questions For Authors" as Q, and "Weakness" as W to save space.

E2 & W7: Global optimal solution

Our 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 $J(aw_1+(1-a)w_2)=\max _{Z\in\Gamma}tr((2\tilde{K}+K^{aw_1+(1-a)w_2})ZZ^T)$

$=\max _{Z\in \Gamma}tr((2\tilde K+\sum _{t=1}^m{(aw _{1t}+(1-a)w _{2t})^2K^{(t)}})ZZ^T)$ $\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$ $=\max _{Z\in\Gamma}tr((2a\tilde{K}+aK^{w_1}+2(1-a)\tilde{K}+(1-a)K^{w_2})ZZ^T)$ $\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)$

$=aJ(w_1)+(1-a)J(w_2)$,

which 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.

We 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.

W4,5 & Q1: Hyperparameter setting

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.

E3: Ablation study & Noise situation

In 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.

As 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

W6 & Q2: Computational efficiency

The time complexity of each module in our method is as follows:

• Construct each similarity: $O(n^2)$
• Calculate \tilde{K}: $O(n^{2.376})$
• Solve Z: $O(n^2)$
• Compute reduced gradient: $O(n^2)$
• Update $w$: $O(m)$

Note 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.

W1,8: Verification of theoretical results and necessary conditions for consistency

Our 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.

We 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.

W2,3: Symbolic definitions and Notations

As 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.

We sincerely thanks for all your constructive comments!

Weakness 1: Improve writing quality and clarify some concepts

Thanks for your suggestions! We will make the following changes in the final version of the paper:

• Provide a more detailed explanation of ensemble clustering and motivation in Introduction
• 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)
• Add Section 2.3 "Problem Definition" to clarify the problem definition
• In Section 3 "Generalization Performance" we will provide more details for several equations
• In Section 4 "Key Factors in Ensemble Clustering" we will include a more detailed derivation of Eq. (8) to Eq. (9)
• Move some important experimental conclusions into Section 6 Experiments instead of Appendix
• Review the entire paper to avoid undefined symbols and typos

Comment 1: A typo in $\bar{A}=1/m\sum_i^m A^{(t)}$

The correct form is $\bar{A}=1/m\sum _t^m A^{(t)}$, and we will correct it in the final version.

Comment 2: Definition of matrix $D$ and notation $D^{(t)−1/2}$ are confusing

$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.

Question 1: Is the gap condition between the k-th and k+1-th eigenvalues of $K^\*$ mild or generally true

It is a mild condition and can be explained in two aspects.

1. $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].
2. 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

Therefore, 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.

[1] Error bounds for kernel-based approximations of the Koopman operator.

[2] Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation.

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?

• 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.

• 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".