The anchor similarity matrix, widely used for efficient clustering, exhibits an imbalance between its rows and columns - only the rows are typically constrained by probabilistic properties, unlike the regular similarity matrix where both dimensions are regulated. This paper addresses the critical question of how to impose meaningful constraints on the columns to better capture the data structure. We propose a novel method, termed Multi-view Clustering via Bilaterally constrained anchor Graph (MCBG), which learns a fused anchor similarity matrix with bilateral constraints. To ensure consistency across views, we quantitatively assess their contributions and integrate them into a unified model. By applying distinct constraints to rows and columns, MCBG promotes a balanced and expressive anchor similarity distribution, avoiding degenerate cases. Furthermore, a rank constraint on the Laplacian matrix of an anchor-pairwise graph is incorporated, ensuring a one-step post-processing-free multi-view clustering framework. An efficient alternating iterative optimization algorithm is developed, adapted to the natural properties of the target problem. Extensive experiments validate the superiority of the proposed method.

Graph clustering typically involves a two-step process: relaxation followed by post-processing. However, it often leads to significant information loss during relaxation and solution deviation in post-processing. Additionally, traditional graph clustering faces computational challenges due to regular graph construction and spectral decomposition, and binary indicators hinder interpretability in uncertain scenarios. We propose a novel method termed Fast Fuzzy Graph Cut (FFGC) to overcome key issues in graph clustering by: preventing information loss by tackling the original graph cut problem; eliminating solution deviation by directly solving for the target variable; alleviating computational burdens by employing anchor graphs in place of regular graphs; and enhancing flexibility by incorporating a regularization term to soften the cluster indicator. The use of a fuzzy cluster indicator within the graph cut framework expands FFGC's applicability to a wider range of real-world data, increasing both its adaptability and interpretability. In addition, we develop two efficient optimization algorithms to solve the resulting objective problem. Extensive experimental evaluations validate the superior efficiency and effectiveness of FFGC in clustering tasks. The code is available athttps://github.com/caccode/FFGC.

In most existing graph-based multi-view clustering methods, the eigen-decomposition of the graph Laplacian matrix followed by a post-processing step is a standard configuration to obtain the target discrete cluster indicator matrix. However, we can naturally realize that the results obtained by the two-stage process will deviate from that obtained by directly solving the primal clustering problem. In addition, it is essential to properly integrate the information from different views for the enhancement of the performance of multi-view clustering. To this end, we propose a concise model referred to as Multi-view Discrete Clustering (MDC), aiming at directly solving the primal problem of multi-view graph clustering. We automatically weigh the view-specific similarity matrix, and the discrete indicator matrix is directly obtained by performing clustering on the aggregated similarity matrix without any post-processing to best serve graph clustering. More importantly, our model does not introduce an additive, nor does it has any hyper-parameters to be tuned. An efficient optimization algorithm is designed to solve the resultant objective problem. Extensive experimental results on both synthetic and real benchmark datasets verify the superiority of the proposed model.

Multi-view semi-supervised learning (SSL) has attracted great attention due to its effectiveness in information utilization of multiple views and labeled and unlabeled data to solve practical problems. However, most existing methods exhibit high computational complexity. Effective integration of the information on different views to achieve enhanced performance remains a challenging task. In this study, we combine an anchor-based approach with multi-view semi-supervised learning to address these problems. A novel multi-view SSL method called fast multi-view SSL (FMSSL) based on learned graph is proposed. Starting from the affinity graphs constructed by using an anchor-based strategy, FMSSL learns an optimal multi-view consensus graph by using feature and label information. The learned graph can jointly consider the relation of multiple views to approximate the manifold structure. The learned graph is then introduced into the SSL model as the weight matrix of a bipartite graph to simultaneously perform separate classification on the original samples and anchors. Accordingly, multi-view SSL can be efficiently performed, and the computational complexity can be significantly reduced. We propose an effective algorithm to optimize the objective function. Extensive experimental results on different real-world datasets demonstrate the effectiveness and efficiency of the proposed algorithm.

Generally, the existing graph-based multi-view clustering models consists of two steps: (1) graph construction; (2) eigen-decomposition on the graph Laplacian matrix to compute a continuous cluster assignment matrix, followed by a post-processing algorithm to get the discrete one. However, both the graph construction and eigen-decomposition are time-consuming, and the two-stage process may deviate from directly solving the primal problem. To this end, we propose Fast Multi-view Discrete Clustering (FMDC) with anchor graphs, focusing on directly solving the spectral clustering problem with a small time cost. We efficiently generate representative anchors and construct anchor graphs on different views. The discrete cluster assignment matrix is directly obtained by performing clustering on the automatically aggregated graph. FMDC has a linear computational complexity with respect to the data scale, which is a significant improvement compared to the quadratic one. Extensive experiments on benchmark datasets demonstrate its efficiency and effectiveness.

Faced with the increasing data diversity and dimensionality, multi-view dimensionality reduction has been an important technique in computer vision, data mining and multi-media applications. Since collecting labeled data is difficult and costly, unsupervised learning is of great significance. Generally, it is crucial to explore the complementarity or independence of different feature spaces in multi-view learning. How to find a low-dimensional subspace to preserve the intrinsic structure of original unlabeled high-dimensional multi-view data is still challenging. In addition, noises and outliers always appear in real data. In this study, we propose a novel model called flexible multi-view unsupervised graph embedding (FMUGE). A flexible regression residual term is introduced so that the strict linear mapping is relaxed, new-coming data and noises are better handled, and the raw data negotiate with the learned low-dimensional representation in the procedure. To ensure the consistency among multiple views, FMUGE adaptively weights different features and fuses them to get an optimal multi-view consensus similarity graph, which assists high-quality graph embedding. We propose an efficient alternating iterative algorithm to optimize the proposed model. Finally, experimental results on synthetic and benchmark datasets show the significant improvement of FMUGE over the state-of-the-art methods.