Dynamic Anchor-based Ensemble Clustering via Hypergraph Reconstruction

1 Introduction

Ensemble clustering integrates multiple base clustering results to capture a more robust consensus result [Chen et al., 2023; Shi et al., 2021; Li et al., 2021; Bai et al., 2020]. Without accessing the data features, the range and level of effective information that ensemble clustering can utilize are quite limited, which also gives it the characteristic of protecting data privacy [Zhou et al., 2024]. Most existing ensemble clustering methods focus on converting base clustering results into a Co-association (CA) matrix. The CA matrix describes the frequency with which samples belong to the same cluster and characterizes the cluster structure at the sample level. These methods incorporate various learning paradigms or graph-based techniques to improve the quality of the CA matrix, ultimately obtaining discrete consensus clustering result through hierarchical or spectral clustering methods [Jia et al., 2021; Xu et al., 2024]. However, the n×n-sized CA matrix inevitably leads to a time complexity of O (n2 ) or even O (n3 ), making it difficult to scale to large-scale datasets.

∗Corresponding Author

Anchor-based ensemble clustering methods are proposed to address this scalability issue. These methods achieve the ensemble by selecting representative samples (anchors), learning the relationships between the anchors and the samples (the anchor similarity matrix), and clustering in three steps [Zhang et al., 2024a; Liu et al., 2024]. The strategy for selecting anchors is crucial for the quality of the anchor similarity matrix and directly impacts clustering accuracy. Existing methods treat the cluster centers obtained by K-means and its variants as anchors, and once the anchors are selected, they remain fixed [Huang et al., 2020; Zhang et al., 2024a; Li et al., 2023]. This reduces the flexibility and quality of the constructed anchor similarity matrix, and in practical applications, the number of anchors is often large. Moreover, these methods use data features when selecting anchors, which limits the privacy-preserving capabilities of ensemble clustering. To address these issues, there is an urgent need to propose a method that dynamically learns anchors without relying on data features, in order to preserve the privacy-preserving nature of ensemble clustering and improve the quality of the anchor similarity matrix. Specifically, this method should meet the following challenges. (C1): How to improve the reliability of base clustering results to enhance the accuracy of subsequent anchor point learning. (C2): How to dynamically learn anchor points and construct high-quality anchor similarity matrices using only base clustering results to preserve the privacy-preserving characteristics of ensemble clustering. (C3): How to fully leverage the effective local information in base clustering results to improve clustering accuracy.

To address these challenges, we propose a novel method named dynamic anchor-based ensemble clustering via hypergraph reconstruction (YACHT). Specifically, as shown in Figure 1, YACHT transforms the base clustering results into a hypergraph and designs a hypergraph enhancement strategy based on random walks on hyperedges to improve the reliability of the initial hypergraph. Then, YACHT reconstructs the hypergraph through matrix factorization. During the reconstruction process, both the anchor matrix and the anchor similarity matrix are incorporated into the optimization objective for dynamic learning. Moreover, a mapping matrix is introduced to filter out redundant information in the hypergraph. This helps capture a higher-quality anchor similarity matrix. Next, YACHT incorporates the hypergraph into the optimization objective and imposes a hypergraph regularizer. The regularizer constrains the hypergraph update and derives a label partition. YACHT aligns the label partition with the local consensus information extracted from the base clustering results. This alignment strategy helps constrain the hypergraph to retain local consensus information during the update process without introducing significant deviations. Finally, the final consensus results are obtained by applying the Kmeans method to the anchor similarity matrix.

The main contributions of this paper are:

• We propose a novel method named dynamic anchorbased ensemble clustering via hypergraph reconstruction (YACHT). Compared to methods based on the CA matrix, YACHT reduces the time complexity to O(n) and is more suitable for large-scale datasets.
• We introduce a hypergraph enhancement strategy to improve the reliability of the initial hypergraph. The hypergraph regularizer and local consensus information alignment term are imposed to prevent significant deviations during the hypergraph update process.
• We design an alternating optimization strategy for the objective function. The effectiveness of YACHT is demonstrated through comparisons with 17 representative clustering methods.

2 RelatedWork

2.1 Ensemble Clustering

Strehl and Ghosh [Strehl and Ghosh, 2003] conducted early research on ensemble clustering, defining ensemble clustering as the process of learning a consensus result from a set of base clustering results. Ensemble clustering alleviates the robustness and stability issues of single-clustering methods. It can be broadly divided into two categories: methods based on the quality of base clustering results and methods based on consensus function strategies. The former either selects high-quality base clustering results from the base clustering set or relies on robust clustering algorithms to generate more accurate base clustering results [Huang et al., 2023; Abbasi et al., 2019; Zhao et al., 2017]. Methods based on consensus function strategies have garnered wide attention due to their excellent performance. These include CA matrixbased methods [Tao et al., 2019; Liu et al., 2015; Xie et al., 2024] and bipartite graph-based methods. CA matrix-based methods focus on improving the quality of the CA matrix [Hao et al., 2024; Jia et al., 2024] or learning its underlying subspace to explore cluster structures [Tao et al., 2019; Tao et al., 2021]. Bipartite graph-based methods leverage the association between samples and clusters to obtain consensus partitions [Fern and Brodley, 2004]. Some of these methods adopt self-paced learning frameworks to progressively learn consensus results [Zhou et al., 2021a].

2.2 Anchor based Clustering

A large number of anchor-based clustering methods have been proposed [Liu et al., 2024; Wan et al., 2023]. The motivation for introducing anchors in clustering is to enhance the scalability of the algorithm. Anchors are representative samples selected from the data, which are then used to learn the affinity relationships among the samples. Research on anchors in ensemble clustering is still in its early stages. Representative methods include: Yang et al. performed spectral clustering based on anchors and then assigned samples to the nearest anchor clusters, significantly improving timeliness [Yang et al., 2023]. Li et al. proposed an ensemble method that reuses anchor similarity matrix and employs light-k-means [Li et al., 2023]. Zhang et al. introduced a fast k-nearest neighbor approximation method to construct similarity matrices for approximating affinity matrix [Zhang et al., 2024a]. However, a key limitation of these methods is that they used raw data features to select anchors, compromising the privacy-protecting characteristics of ensemble clustering. Huang and Liang's methods [Huang et al., 2020; Liang et al., 2020] did not incorporate data features. However, their methods either used fixed anchors or ignore local consensus information, leading to poorer performance. Unlike the methods mentioned above, our method does not introduce data features, allowing for dynamic anchor learning and fully leveraging local consensus information.

3 The ProposedMethod

This section details the YACHT method, covering the objective function, optimization, and time complexity analysis.

3.1 Constructing and Enhancing the Hypergraph

Given n samples X = {x1, x2, ..., xn} and m base clustering results Ξ = {C1, C2, ..., Cm}, where xi denotes the i-th sample. Cj = {π1 j , π2 j , ..., πsj j } represents the j-th base clustering result that partitions X into sj base clusters. πh j represents the h-th base cluster in Cj. A hypergraph G = (V, E, ˜W) can be constructed from the base clustering results, where V represents the set of nodes, each corresponding to a sample. Each hyperedge in the hyperedge set E can represent a base cluster. Therefore, the number of hyperedges is equal to the number of base clusters s = ∑mj=1 sj. As shown in Figure 1, we can construct the initial hypergraph indicator matrix ˜H. The hyperedge weight ˜W is a diagonal matrix, where the diagonal elements ˜Wii represents the weights of the i-th hyperedge. Since each hyperedge represents a base cluster, we use local entropy weights [Huang et al., 2018] to represent the weights of the hyperedges. The hyperedge weights are defined as:

where p( ˜Hi:, ˜Hj:) = | ˜Hi: ⋂ ˜Hj:| | ˜Hi: | represents the ratio of the number of intersecting samples between two hyperedges to the number of samples in i-th hyperedge. θ represents the weight decay parameter, where a smaller value indicates faster weight decay.

Due to the weaknesses of the base clustering algorithms, the reliability and stability of the initial hypergraph generated from the base clustering results are compromised [Zhou et al., 2022]. We improve the reliability of the hypergraph by introducing random walks to explore the proximity between hyperedges [Zhang et al., 2024b]. We use the Jaccard distance to define the direct similarity between hyperedges:

where Oij represents the similarity between the i-th and j-th hyperedges. NormalizingOas ˙O= D-1 o Oallows it to be interpreted as a probability transition matrix, where Do denotes the Laplacian matrix of O. Then, the high-order relationship matrix ˜O ∈ Rs×s of the hyperedges is defined as:

where ˙O(d) = ˙O(d-1)⊤ ˙O. Based on this similarity, we can improve the existing hypergraph structure. We generate the enhanced hypergraph H ∈ Rs×n as follows:

where 1 (·) is a mapping function that maps all values greater than 0 to 1, and α is the similarity threshold. As shown in Eq. (2), the hyperedges of the enhanced hypergraph H may change, resulting in new hyperedge weights W.

3.2 Reconstructing the Hypergraph with Hypergraph Regularization

After obtaining the enhanced hypergraph H, a self-expressive model is employed to capture sample affinities:

where S ∈ Rn×n denotes the similarity matrix and D is the dictionary. This form can reconstruct H, but has the following issues: (i) the similarity matrix S is n × n, and the reconstruction of H is slow, leading to lower computational efficiency; (ii) it cannot filter out the redundant information in the hypergraph. Therefore, we introduce anchor learning and a mapping matrix. The anchor points reduce the similarity matrix dimension from n × n to k × n relations, where k is the number of anchor points. This results in a smaller anchor similarity matrix Z compared to S, thereby accelerating the reconstruction process. The introduction of the mapping matrix helps filter out redundant hyperedges in the hypergraph, which aids in capturing a higher-quality anchor similarity matrix. Therefore, we obtain the following form:

where P ∈ Rs′×s is the projection matrix, Z ∈ Rk×n is the similarity matrix representing the relationship between the anchors and the samples, and A ∈ Rs′×k denotes the anchor matrix. s′ is the number of representative base clusters. The orthogonal constraints on variables P and A help learn a better similarity matrix Z [Feng et al., 2024].

Furthermore, we attempt to incorporate H into the optimization objective, as the quality of H directly impacts the reliability of Z. However, unconstrained updates inevitably lead to large errors and unreliable Z. Therefore, to learn a better hypergraph, we apply the widely used hypergraph regularizer [Gao et al., 2022; Zhang et al., 2018]. We rewrite equation (3) as:

where L = I - D-1/2 v H⊤WD-1 e HD-1/2 v is the Laplacian matrix of the hypergraph. Dv = diag(H⊤W1) denotes the node degree matrix, De = diag(1⊤H⊤) is the edge degree matrix. This regularizer not only constrains the hypergraph update but also derives a label indicator matrix F ∈ Rn×c , where c is the number of clusters. The label indicator matrix helps us align the local consensus information derived from the base clustering results. This ensures that the hypergraph preserves this information during the optimization process while avoiding significant deviations.

3.3 Aligning Local Consensus Information

In general, local consensus information refers to results that are reflected in all base clustering results, for example, when two samples are clustered together in every base clustering perspective. Since the CA matrix captures relationships at the sample level, local consensus information can be easily applied in methods based on the CA matrix [Jia et al., 2021; Jia et al., 2024; Li et al., 2024]. To align local consensus information with the label indicator matrix F derived from the hypergraph, we also need to define a consensus base cluster S to match the size of F.

Definition 1. Let S be a set of objects. The set S is a consensus base cluster if and only if (i) ∀xi, xj ∈ S s.t. ˜H:i = ˜H:j, and (ii) the number of samples contained in the set, num(S), is at least 2 (num(S)).

Definition 1 provides the definition of consensus base cluster based on the initial hypergraph. Although both consensus base clusters and microclusters [Huang et al., 2016] require consistent sample-base cluster relationships (i.e. ˜H:i = ˜H:j), we additionally require that consensus base clusters contain more than 2 samples. This is because microclusters can include single samples, but retaining a consensus base cluster with only a single sample for alignment is meaningless. Considering the size of F, we strive to retain as much information as possible from the large number of local consensus base clusters. We first sort the number of samples in all consensus base clusters and then retain the top c consensus base clusters. Based on these c base clusters, we generate the local consensus information indicator matrix. Figure 2 shows the construction process of the local consensus information indicator matrix Y. Note that all of this is based solely on the base clustering results, without relying on any ground truth. Finally, we minimize the error between F and Y to achieve alignment. The final objective function is as follows:

3.4 Optimization

To solve Eq. (5), we employ the alternating optimization strategy [Zhong and Pun, 2022], i.e., optimizing the target variable alternately while fixing other variables.

Update P To update the variable P, other variables need to be fixed. The subproblem w.r.t. P is as follows:

We expand the Frobenius norm by the trace operation and remove terms unrelated to P, further transforming Eq. (6) into the following form:

where Q = AZH⊤. Supposing the Singular value decomposition (SVD) of Q is UQΣQV⊤Q, we can obtain the optimal solution for P as UQV⊤Q.

Update A With P, Z, H and F being fixed, the subproblem for A is as follows:

Similar to the subproblem for P, we transform the subproblem for A into the following form by expanding the Frobenius norm:

where B = PHZ⊤. Similarly, we perform the SVD decomposition B = UBΣBV⊤ B, and then obtain the optimal solution for the variable A as UBV⊤ B.

Update Z With P, A, H and F being fixed, the subproblem for Z is as follows:

Eq. (9) can be solved using the augmented Lagrange multiplier (ALM) method [Bazaraa et al., 2013]. Its augmented Lagrangian function is as follows:

where J ∈ Rn×1 represents the Lagrange multiplier, µ is the penalty parameter. Next, we take the derivative of Eq. (10) and set it to zero. The variable Z can be updated by:

Update H With P, A, Z and F being fixed, the subproblem for H is as follows:

Since Dv and De are related to H, we need to first take the derivatives of Dv and De before taking the derivative of Eq. (11). Denote that D- 12 v = diag ([dv1 , ..., dvn ]) and D-1 e = diag ([de1 , ..., den ]). We can get:

Algorithm 1 Obatain label indicator matrix F

Input: Matrix G, Y.

Output: F.

• 1: Initialize an orthogonal matrix F satisfying FF⊤ = I.
• 2: while not converged do
• 3: Update Q′ by Q′ =GF+2Y.
• 4: Calculate the SVD of Q′ =UQ′ΣQ′V⊤Q′ .
• 5: Update F by F =UQ′V⊤Q′ .
• 6: end while

where δ is the Kronecker delta, i.e., δiq = 1 if i = q and δiq = 0 otherwise. Let the subproblem for Eq. (11) be denoted as Q (H). The derivative w.r.t. H can be written as:

where J is a matrix where all elements are 1. Setting the derivative ∇Q to 0 and then solving is quite difficult, so we use the projected gradient method to optimize the variable H [Gao et al., 2022]. H is updated as follows:

where α is the learning rate, and P is the projection onto the feasible set {H|1 ≥ H ≥ 0}. P is defined as follows:

Update F With P, A, Z and H being fixed, the subproblem for F is as follows:

where G = D-1/2 v H⊤WD-1 e HD-1/2 v . Inspired by [Zhuge et al., 2019], we solve for variable F using Algorithm 1 and obtain its closed-form solution.

Update J and µ The Lagrange multipliers and penalty parameters in the ALM method are updated as follows:

where ρ > 0 is a user-defined constant, and µmax represents the maximum value of µ. The overall process of the algorithm is summarized in Algorithm 2.

3.5 Complexity Analysis

In YACHT, the time complexity is mainly driven by the hypergraph enhancement strategy and the updates of several variables. The hypergraph enhancement strategy involves random walks on the hyperedges and matrix multiplication, with a time complexity of O(s3 ). For variable P, its update

Algorithm 2 YACHT

Input: m base clustering results, c, k and α.

Output: Consensus result s.

• 1: Initialize P, A, Z, and J. Construct the initial hypergraph ˜H and obtain the enhanced hypergraph H.
• 2: while not converged do
• 3: Update P by solving Eq. (7).
• 4: Update A by solving Eq. (8).
• 5: Update Z by solving Eq. (9).
• 6: Update H by solving Eq. (11).
• 7: Update F by Algorithm 1.
• 8: Update J and µ by Eq. (15).
• 9: end while
• 10: Obtain the left singular vector U by performing SVD on Z. Perform k-means method on U to obtain s.

process involves SVD decomposition and matrix multiplication, resulting in a time complexity of O(s′ s2 + s′n(k + s)). For variable A, its time complexity is O(s′k2 + s′n(k + s)). For variable Z, it involves matrix inversion, resulting in a time complexity of O(k3 ). For variable H, we use the projected gradient method for optimization. In each iteration, the time complexity of the computation can be reduced to O(n) by appropriately applying the associative law of matrix multiplication. Similarly, for variable F, by adjusting the order of matrix multiplication, its computational complexity can be controlled within O(c2n). According to [Zhou et al., 2022], the number of base clusters is much smaller than the number of samples, so we have n >> s, n >> k, and n >> s′ . Overall, the total time complexity of YACHT is linearly related to the number of samples, O(n).

4 Experiment

4.1 Experimental Setup

We conduct extensive experiments on 10 real datasets. Characteristics of these datasets are provided in Table 1. Some methods [Zhou et al., 2019; Tao et al., 2019] provide relevant base clustering results, which we use directly for convenience. For the other datasets 1 , we randomly run the K-means method 100 times to generate the base clustering result set.

1 http://archive.ics.uci.edu/datasets

Following many ensemble methods, we set the ensemble size to 20 and conduct 10 repeated experiments with different base clustering combinations, reporting the mean and standard deviation. All compared methods use the same combination of base clustering. In YACHT, we set the hyperedge weight parameter θ = 0.4 and the maximum order of hyperedge random walks d = 20. We set the hyperparameters as follows: the number of anchors k = k′+c, where k′ ∈ {-1, 0, 1, 2, 3};

and the similarity threshold α ∈ [0.9 : 0.01 : 1]. All methods are evaluated using two popular clustering metrics: Accuracy (ACC), and Adjusted Rand Index (ARI). We use 17 representative methods, including state-of-the-art (SOTA) ensemble methods, fast ensemble methods and anchor-based clustering methods. · SOTA ensemble methods: ECCMS [Jia et al., 2024], CEAM [Zhou et al., 2024], SPCE [Zhou et al., 2021b], CESHL [Zhou et al., 2022], TRCE [Zhou et al., 2021c], DREC [Zhou et al., 2019], ECPCS-HC/MC [Huang et al., 2021]. · Fast ensemble methods: LWEA/LWGP [Huang et al., 2018], U-SENC [Huang et al., 2020], SEC [Liu et al., 2015], PTA-AL/CL [Huang et al., 2016], PTGP [Huang et al., 2016]. · Anchor-based clustering methods: AWMVC [Wan et al., 2023], SMVAGC-SF [Wang et al., 2024].

4.2 Experimental Results

Table 2 presents the experimental results on two metrics. 'N/A' indicates excessive runtime or insufficient memory. From the experimental results, we have the following observations: (i) YACHT outperforms the average results of base clustering on all metrics across all datasets, demonstrating the effectiveness of integrating multiple base clustering results. (ii) YACHT demonstrates strong performance advantages across various datasets of different sizes, highlighting the method's excellent scalability. Particularly in terms of the ARI metric, YACHT outperforms all comparison methods across all datasets. (iii) Overall, fast ensemble methods generally do not outperform SOTA ensemble methods on most datasets. However, SOTA methods are often limited by the size of the dataset and may fail to produce results. (iv) YACHT outperforms the hypergraph method CESHL across all metrics, validating the effectiveness of using anchors to reconstruct the hypergraph.

4.3 Parameter Study and Time Comparison

Figure 3 shows the impact of different parameter combinations on the accuracy of the YACHT method. We observe that, on large-scale datasets, the YACHT method is not highly sensitive to parameter combinations, indicating that YACHT exhibits good robustness. For large-scale datasets (FashionMNIST, EMNIST), we select no more than twenty anchor points to reconstruct the hypergraph, achieving the highest clustering accuracy, which validates the effectiveness of the reconstruction. Additionally, the parameter α has some impact on the accuracy of the YACHT method, indicating that although H is incorporated into the optimization objective, the initial values still affect the clustering accuracy. This also suggests that the hypergraph enhancement strategy can adjust the hypergraph structure through a threshold, providing a better initial value for the optimization method. Figure 4 shows a comparison of the running time across different methods. Although the YACHT method is not the fastest ensemble clustering method, it is the first to introduce a dynamic anchor learning strategy compared to existing fixed-anchor ensemble methods. Dynamic anchor learning significantly improves Dataset accuracy, but updating the anchors inevitably requires more time. In practical applications, accepting a bit of additional runtime is reasonable in order to achieve higher accuracy.

Table 3: Ablation study results.

4.4 Ablation Study

Table 3 shows the results of the ablation versions of the YACHT method. 'w/o H-Re' indicates the version without hypergraph reconstruction, where k-means is applied directly on the hypergraph. 'w/o H-r' indicates the version using hypergraph reconstruction only, without hypergraph update and regularization. 'w/o H-e' refers to the version without the hypergraph enhancement strategy. We observe that the clustering accuracy significantly decreases without hypergraph reconstruction, which suggests that reconstruction helps remove erroneous information, improving clustering accuracy. Overall, the absence of the hypergraph enhancement strategy and the lack of hypergraph regularizer both lead to a decrease in clustering accuracy. This demonstrates the effectiveness of hypergraph reconstruction and the hypergraph regularizer in the YACHT method.

5 Conclusion

This paper proposes a dynamic anchor-based learning and hypergraph reconstruction ensemble clustering method, YACHT. YACHT transforms the base clustering results into a hypergraph and designs a hypergraph enhancement strategy to improve its reliability. Unlike other methods, YACHT learns a high-quality anchor similarity matrix through hypergraph reconstruction. Additionally, it constructs a more reliable hypergraph and constrains its update using a local consensus alignment term and hypergraph regularization. Experiments on real datasets validate the effectiveness of YACHT. Although YACHT is not the fastest ensemble method, its accuracy significantly outperforms existing SOTA methods.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China (62472294) and Grant 2024ZD0607700.