Zhang Zhiwei, Chen Xiaohong, Zhu Yulian
Accepted: 2026-07-01
Anchor-based bipartite graphs can approximate sample relationships with low computational cost, and have been widely used for graph construction in large-scale multi-view clustering. However, most existing methods generate anchors by random sampling, K-Means centers, or static dictionaries. The anchor positions are usually fixed before graph learning. For data with non-spherical clusters, ring-shaped clusters, elongated clusters, and large density differences among clusters, static anchors are difficult to approach local density peaks and curved cluster boundaries. This may lead to anchor mismatch. The sample-anchor bipartite graph constructed in this way may contain redundant or unreliable connections, which affects cross-view structure fusion and reduces the stability of clustering results. To address these problems, a Multi-view Bipartite Graph Clustering method guided by Mean-Shift (MBGC-MS) is proposed. The aim of the method is to maintain the high efficiency of anchor graphs, improve the adaptive representation ability of anchors for complex data distributions, and integrate graph learning and clustering assignment into a unified optimization process.
First, an anchor set is initialized in each view. Mean Shift is then used to iteratively update the anchors along the kernel density gradient, so that the anchors are changed from Euclidean center representatives to local density modes. After that, the local bandwidth is estimated according to the distance from each sample to its neighboring anchors. Only the neighboring anchor relationships of each sample are retained to construct a sparse and density-aware sample-anchor bipartite graph. Second, the bipartite graph of each view is decomposed into a shared consistency graph and view-specific complementary graphs. The consistency graph is used to describe the clustering structure jointly supported by different views, and a nuclear norm constraint is imposed to enhance its low-rank property and structural compactness. The complementary graph is used to preserve the discriminative local information that deviates from the consensus in each single view, and a sparsity constraint is imposed to suppress noise and redundant connections. Third, view weights are adaptively learned according to the reconstruction error, so as to avoid the information interference caused by equal-weight fusion of all views. On this basis, the consistency graph and complementary graphs are fused to construct a unified sample-anchor bipartite graph and an augmented Laplacian matrix. A spectral trace constraint is further imposed to make the unified graph tend to form a given number of connected components.
The proposed model adopts a block coordinate descent strategy to alternately update the clustering indicator matrix, consistency graph, complementary graphs, and view weights. Each subproblem can be solved by eigen-decomposition, soft-thresholding operator, singular value thresholding, or quadratic programming. In this way, one-step optimization of graph structure learning and clustering assignment is achieved. Experiments are conducted on four multi-view datasets, including Handwritten, BBC-sport, MSRC_v1, and Caltech101-7. ACC, NMI, and F-score are used as evaluation metrics. The results show that the proposed method obtains the best performance on 8 out of 12 metrics. On Handwritten, the highest NMI is obtained, reaching 0.949. On BBC-sport, the ACC and F-score reach 0.971 and 0.933, respectively. On MSRC_v1, the ACC and F-score reach 0.966 and 0.931, respectively. On Caltech101-7, the ACC, NMI, and F-score reach 0.711, 0.521, and 0.484, respectively, and all three metrics are the best.
Ablation experiments further show that Mean Shift anchor updating, consistency-complementarity decomposition, and Laplacian spectral trace constraint all contribute to performance improvement. On Caltech101-7, the ACC, NMI, and F-score of the complete model are higher than those of the model using only the Mean Shift module, whose corresponding values are 0.534, 0.362, and 0.348. The comparison of different anchor strategies shows that the three metrics of Mean Shift anchors are 0.711, 0.521, and 0.484, which are clearly higher than those of K-Means anchors, namely 0.576, 0.395, and 0.456, and also higher than those of random sampling anchors, namely 0.308, 0.260, and 0.320. The convergence experiments show that the objective function usually decreases rapidly in the first 5–10 iterations and becomes stable within 20 iterations. Complexity analysis and running time experiments show that, when the number of anchors and iterations are fixed, the running time of the algorithm grows approximately linearly with the sample size. In summary, the proposed method can calibrate anchor positions by using density information and enhance the representation ability of bipartite graphs for complex cluster structures. It also considers multi-view consistency, complementarity, and one-step clustering optimization. Therefore, it shows good clustering performance, stability, and scalability on non-spherical and uneven-density data.