Capturing Individuality and Commonality Between Anchor Graphs for Multi-View Clustering

1 Introduction

Clustering has long been a crucial aspect of data analysis, which groups data according to specific patterns without label information. The emergence of multi-source data [Baltruˇsaitis et al., 2018] has raised higher demands for clustering tasks, giving rise to multi-view extension [Li et al., 2018; Fang et al., 2023]. In this setting, data often comes with multiple perspectives or representations. The consistent and complementary information among these views is explored to address the limitations of single-view information and enhance performance.

∗Corresponding author

Multi-view clustering can be roughly categorized into subspace-based [Gao et al., 2020; Huang et al., 2022], kernelbased [Li et al., 2022a; Liu, 2022], matrix factorization-based [Wan et al., 2023], and deep learning-based [Xu et al., 2022; Yan et al., 2023] methods. Subspace clustering is widely recognized as an effective data analysis technique, as it can directly learn affinities between samples, revealing the internal structure of the data. Unfortunately, it often struggles with the high computational costs associated with large-scale datasets.

On the other hand, the use of anchors has brought about better efficiency and scalability, making them highly popular. Naturally, this technology has been integrated into subspace learning models. In anchor-based subspace learning, a point-to-anchor graph is learned instead of a point-to-point graph. Since the number of anchors is usually much smaller than that of samples, it is more friendly to both runtime and memory. Anchors can be pre-selected, resorting to heuristic strategies such as k-means and feature scoring. However, these pre-selection strategies face the risk of being insufficient to represent the entire dataset, which leads to dynamic anchor learning strategies.

However, a challenge arises in anchor-based multi-view subspace learning. A unified anchor graph tends to overemphasize the commonality between views, failing to adequately capture the individuality of each view. This has led some models to independently explore each view's individuality before aligning and integrating them, often achieving better performance but making the process more cumbersome. Moreover, although existing models maintain linear complexity with respect to the number of samples, they often exhibit quadratic or even cubic complexity with respect to the number of anchors. The growth of anchors inevitably results in substantial time costs.

To address these issues, this paper proposes a new model, Capturing Individuality and Commonality between Anchor Graphs (CICAG) for multi-view clustering. The four contributions are summarized as follows:

• It captures both the individuality and commonality between anchor graphs, addressing the limitations of previous approaches that focus solely on either aspect.
• It enables view-specific anchor graphs to align in realtime with a common anchor graph as a reference, eliminating the need for post-alignment.

• It enforces a cluster-wise structure among anchors and balances samples distribution among them, providing strong discriminative power.
• It achieves linear computational complexity concerning both the number of samples and anchors, making it efficient and scalable even with a large number of anchors.

2 RelatedWork

Anchor-based multi-view learning models can be categorized into two main types: static anchor pre-selection and dynamic anchor learning. The former determine anchors in advance using heuristic methods, with no changes during subsequent anchor graph construction. The latter requires joint optimization of anchors and anchor graphs with dynamic updates. Dynamic anchor learning includes unified anchor graph strategies, which share a common anchor graph across all views, and view-specific anchor graph strategies, which learn a separate anchor graph for each view.

LMVSC [Kang et al., 2020] employs k-means to pre-select anchors for each view and constructs non-unified anchor graphs, which are then concatenated across views. SFMC [Li et al., 2022b] and TBGL [Xia et al., 2022] pre-select aligned anchors by concatenating all features and using a feature scoring strategy, subsequently merging multiple anchor graphs. Unlike SFMC, TBGL utilizes tensors to further explore complementary information across views.

FPMVS-CAG [Wang et al., 2022b], OMSC [Chen et al., 2022], EMVGC-LG [Wen et al., 2023], and CAMVC [Zhang et al., 2024] are representative models, dynamically exploring a unified anchor graph. FPMVS-CAG projects all views into a latent shared space to learn a single anchor graph. OMSC builds on FPMVS-CAG by jointly learning the mapping from the anchor graph to the cluster indicator matrix. EMVGC-LG embeds both local and global structural information into the anchor graph. CAMVC uses pseudo-labels to enforce cluster structure distribution among anchors.

FMVACC [Wang et al., 2022a], FDAGF [Zhang et al., 2023], and AEVC [Liu et al., 2024] are based on anchorbased subspace learning models, capturing separate anchor graphs for different views. FMVACC and AEVC both employ post-alignment strategies, whereas FDAGF directly concatenates anchor graphs from each view. Unlike FMVACC, which averages after alignment, AEVC embeds the learned anchors and anchor graphs into a new model for secondary learning, serving as regularization.

3 Methodology

3.1 Formulation

Typically, the framework for single-view subspace learning takes the following form.

where X ∈ Rd×n represents the complete single-view dataset, A ∈ Rd×m is a representative subset of samples, Z ∈ Rm×n is the weight matrix used to linearly combine A to reconstruct X, n, m and d are the number of samples, anchors and features, respectively. More concisely, A and Z can be referred to as the anchors and anchor graph, respectively. The anchor graph describes an affinity between X and A. As a multi-view extension strategy, a unified anchor graph is often required, resulting in the following form.

where Z is the anchor graph shared across views, while X(i) and A(i) denote the samples and anchors of the i-th view, respectively. Regrettably, this form overly emphasizes the commonality between views and fails to adequately capture the individuality of each view, thus giving rise to another form.

where Z(i) is the anchor graph unique to the i-th view. This case independently explores the individuality of each view before aligning and integrating them, often achieving better performance, but also making the process more cumbersome. Therefore, we propose a compromise solution.

In this approach, we not only extract a common Z for all views but also exploit a specific Z(i) for each view. The anchor set A(i) are shared between Z(i) and Z, ensuring that Z(i) and Z are well-aligned. Indirectly, through the assistance of Z, this alignment relationship is shared among Z(i) .

Meanwhile, the anchors are desired to be evenly distributed across the clusters and further aligned. Thus, the following strategy is adopted.

where F ∈ Rm×c is a predefined anchor-to-cluster assignment matrix, with each cluster containing at least ⌊m/c⌋ and at most ⌈m/c⌉ anchors. For instance, if there are 4 anchors and 2 clusters, then F is set as

Next, we further consider the constraints regarding several variables. If A(i) can effectively represent X(i) , the following equality holds.

This equation implies a series of simpler non-trivial solutions, which necessitate the orthogonality of A(i) .

It is suggested to more freely retain the individuality of Z(i) , only with each row summing to 1.

Meanwhile, Z must ensure a more balanced distribution of samples among anchors, subject to the following constraint.

Considering Problems 4-5 and Constraints 8-10, the final objective function is formulated as follows:

Figure 1 illustrates our proposed CICAG framework. It dynamically captures an individual anchor graph Z(i) for each view's data X(i) while simultaneously exploring a common anchor graph Z for all views. Z(i) and Z share a dynamic anchor set A(i) , thus enabling indirect real-time alignment between individual anchor graphs. Meanwhile, a predefined anchor-to-cluster assignment matrix F enforces the clusterwise structure among anchors and enhances alignment. Additionally, the common anchor graph requires a more balanced distribution of samples across the anchors.

3.2 Optimization

To solve our model, the following alternating optimization strategy is employed.

Update A(i)

If the components unrelated to A(i) are removed andW (i) is precomputed as

the resulting A(i) -subproblem is given.

Furthermore, the closed-form solution for Equation (13) can be revealed by Theorem 1 [Liu et al., 2021].

Theorem 1. Suppose that W (i) = U (i) c Σ(i) c V (i)T c , where U (i) c ∈ Rdi×c , Σ(i) c ∈ Rc×c and V (i) c ∈ Rm×c . Problem 13 has a closed-form solution A(i) = U (i) c V (i)T c .

Update Z(i)

If the components unrelated to Z(i) are removed, and ˜E(v) and E(v) are precomputed as

the resulting Z(i) -subproblem is given.

Furthermore, the optimal solution for Equation (16) can be revealed by Theorem 2.

Theorem 2. By introducing the Lagrange multiplier µ(i) and predefining S(i) and Φ(S(i) ) as

the dual problem of Problem 16 is derived as

whose exact gradient with respect to µ(i) is given by

Once the optimal µ(i) is found, the desired Z(i) can be recovered by

Proof. Similar to the proof of Theorem 3 but simpler.

Update Z

If the components unrelated to Z are removed, and ˜M (i) and M are precomputed as

the resulting Z-subproblem is given.

Furthermore, the optimal solution for Equation (24) can be revealed by Theorem 3.

Theorem 3. By introducing the Lagrange multipliers µ and ν, and predefining S and Φ(S) as

the dual problem of Problem 24 is

whose exact gradients with respect to µ and ν are given by

Once the optimal µ and ν are found, the desired Z can be recovered by

Proof. The following min-max problem is given

(31)

which is easily transformed into the max-min form.

Further, there are the following max-max problems

Obviously, Equation (33) is equivalent to Equation (27). In addition, split Φ(S) by column as

it is easy to konw the derivatives as

Further, its gradients w.r.t. µ and ν can be computed.

Final Fusion

Once our model converges, the desired anchor graph is obtained by Equation (36). For convenience, our methodological procedure is summarized in Algorithm 1.

Algorithm 1 CICAG Solver

Input: Dataset {X(i) }vi=1 , anchor number m, cluster number c, and parameters α, β and γ.

Output: Learned anchor graph Z∗ .

• 1: Initialize Z(i) ,Z and F.
• 2: while non-convergence do
• 3: Update A(i) by Theorem 1.
• 4: Update Z(i) by Theorem 2.
• 5: Update Z by Theorem 3.
• 6: end while
• 7: Obtain Z∗ by Equation (36).

3.3 Complexity

TimeComplexity. In theA(i) -subproblem, computingW (i) and obtaining its singular value decomposition necessitates O(nmd+mdc), while updating A(i) only costs O(mdc). In the Z(i) -subproblem, computing ˜E(i) and E(i) together involves O(nmd + nmc), obtaining the gradient with respect to µ(i) entails O(nm), and updating µ(i) and Z(i) involves O(n) and O(nm) respectively. In the Z-subproblem, computing M demands O(nmd+nmcv), obtaining the gradients with respect to µ and ν both necessitate O(nm), and updating µ, ν, and Z entails O(n), O(m), and O(nm) respectively. Thus, in one iteration, our model requires a computational complexity of only O(nmd + nmcv + mdc), which implies that our algorithm is not only linear in the number of samples n, but also linear in the number of anchors m, data dimension d, and the number of clusters c. Table 1 lists some notable algorithms whose complexities often reach quadratic or even cubic with respect to m, which actually limits their scalability. Additionally, the complexity of some algorithms with respect to c is not linear, making them less suitable for data with a large number of clusters.

Space Complexity. The original data {X(i) } consumes O(nd) space. The auxiliary variables generated from updating A(i) necessitate O(md), and A(i) also takes up O(md). The auxiliary variables generated from updating Z(i) require O(nmv), and Z(i) also takes up O(nmv). The auxiliary variables generated from updating Z demand O(nm) space, and Z itself also uses O(nm). Therefore, our algorithm needs only O(nd + md + nmv) space complexity, which is typical for anchor-based methods.

3.4 Convergence

Although the overall objective function, involving multiple variables, is non-convex, fortunately, each subproblem concerning a single variable is convex. For the A(i) -subproblem, a closed-form solution exists. For the Z(i) -subproblem and the Z-subproblem, their equivalent dual problems can be constructed. Since the exact gradients of the dual problems can be obtained, any gradient-based method can be used to find their optimal solutions. Let the objective function value at the t-th iteration be J({A(i) t }, {Z(i) t },Zt), then the following inequality holds.

Obviously, since the function value monotonically decreases with each iteration and has a lower bound, this algorithm can ensure convergence to a local minimum.

4 Experiment

4.1 Experimental Protocols

Datasets. Our experiments employ 9 public datasets for comparison, including 3Sources, WebKB, NUS-WIDE, NottingHill, Cifar10, Cifar100, YouTubeFace10, YouTubeFace20 and YouTubeFace50. Specifically, the last five are large-scale datasets. Their statistics are described in Table 2.

Baselines. Our CICAG is compared with the following 9 algorithms: SFMC [Li et al., 2022b], TBGL [Xia et al., 2022], FPMVS [Wang et al., 2022b], OMSC [Chen et al., 2022], FMVACC [Wang et al., 2022a], FDAGF [Zhang et al., 2023], EMVGC [Wen et al., 2023], CAMVC [Zhang et al., 2024] and AEVC [Liu et al., 2024]. These classic or state-of-the-art algorithms are highly correlated with ours and have a nearlinear computational complexity.

Settings. For our model, α is set to 0.1, while the remaining hyperparameters are tuned by a grid search, whose ranges are m ∈ {1c, 3c, 5c}, β ∈ {0.001, 0.01, · · · , 100, 1000}, and γ ∈ {0.001, 0.01, · · · , 100, 1000}. The hyperparameters of all compared algorithms are set by gird search according to the recommendations of their original papers. Considering the initialization sensitivity and randomness during running, we performed all algorithms 10 times.

Metrics. In our experiments, the performance is evaluated by Accuracy (ACC), Normalized Mutual Information (NMI) and Adjusted Rand Index (ARI). Their means and standard deviations are reported in experiments. Besides, their average runtime is also recorded.

4.2 Experimental Results

Performance. Table 3 shows, CICAG achieves the highest ACC across all used datasets, with its NMI and ARI being either the highest or second highest. Other algorithms show mixed results across different datasets. Additionally, the notably low standard deviation suggests strong algorithmic stability. Overall, our algorithm CICAG is highly competitive.

Runtime. As observed from Table 1, CICAG exhibits linear complexity in terms of the number of samples, anchors, and features. When the number of anchors and features is large, CICAG is more efficient compared to other algorithms. However, since the publicly available datasets have generally undergone preprocessing such as feature extraction or dimensionality reduction, making m and d relatively small, CICAG's efficiency advantage is not as apparent. Nevertheless, Figure 2 shows that, CICAG's efficiency consistently ranks in the top three, with only a small difference from the shortest runtime. Considering the performance shown in Table 3, CICAG's efficiency is entirely acceptable. Although CAMVC requires alternating variable optimization, each variable has a closed-form solution, significantly reducing its runtime. However, once m becomes too large, CAMVC's computational complexity grows cubically, leading to a significant decrease in efficiency.

Convergence. As seen from Figure 3, the training loss of CICAG on all datasets drops rapidly at first and then stabilizes. This suggests that our algorithm not only converges but also requires only a few iterations.

4.3 Ablation Study

In Table 4, taking the D8 (YouTubeFace20) as an example: the ACC of Z, learned via Equation (2), is 69.3; the ACCs of Z(i) , learned via Equation (3), range from 65.5 to 68.9; direct fusion yields an ACC of 66.2; alignment followed by fusion achieves 72.5; and CICAG touches 73.4. These results demonstrate that simultaneously capturing both individuality and commonality is effective.

4.4 Parameter Sensitivity

m&α. As shown in Figure 4, the trend of ACC with varying α is similar across different m, with their maximum values being close. Generally, setting m = 3c is a good choice. As α increases, the ACC of CICAG on NUS-WIDE, Cifar10, Cifar100, YouTubeFace20, and YouTubeFace50 does not show significant changes, while it exhibits a downward trend on WebKB, Notting-Hill, and YouTubeFace10, and a decrease followed by an increase on 3Sources. Overall, α achieves its maximum value around 0.1. Although the ACC at α = 0.1 is not optimal for WebKB and YouTubeFace, it is still very close to the maximum value. Therefore, setting α = 0.1 is generally a good choice.

β&γ. As shown in Figure 5, β should generally not exceed γ, while γ itself is relatively insensitive. However, in pursuit of optimal values, neither should be set too high.

5 Conclusion

This paper addresses a challenge in anchor-based multi-view subspace learning. Although multiple views share the same anchor graph to capture the commonality across views, this approach clearly overlooks the individuality of specific views. As a result, some models independently explore the individuality of each view, leading to issues of alignment and fusion of anchor graphs across views. Therefore, this paper proposes a new model, capturing both the individuality and commonality of anchor graphs for multi-view clustering. The model not only allows view-specific anchor graphs to be aligned in realtime based on a common anchor graph, but also generates a balanced sample distribution and cluster-level anchors to enhance discriminative power. Moreover, it is computationally efficient in terms of sample, anchor, feature and cluster numbers. Finally, comprehensive experiments demonstrate that our model is highly competitive in terms of both effectiveness and efficiency compared to other state-of-the-art models.

Acknowledgments

This work was supported in part by the National Natural Science Foundation of China under Grants 62236001, 62276212, and 62176212.