Recently, Multi-View Graph Clustering (MVGC) methods have achieved significant progress, leading to their wide adoption in various applications. However, most MVGC methods merely pursue consistent information by simply fusing multi-view graphs, ignoring the cross-view interactions among them, which limits the ceiling of their performance. To make up for this deficiency, we design a credible cross-view graph enhancement module to explore the credible topological structure, while accomplishing cross-view interactions, to boost clustering performance in multi-view graph scenarios. Besides, we reconsider the graph clustering task from the perspective of graph signal processing. From this novel perspective, we adapt the high-order Graph Trend Filter to reveal the inhomogeneities in graph smoothness levels and further consider the brand-new local preference in MVGC, which provides theoretical guidance for graph clustering. Building on these insights, we propose the Enhanced Graph Trend Filter Clustering (EGTFC) method and present an effective algorithm accompanied by corresponding theoretical analyses to tackle the optimization problem inherent in EGTFC. Finally, substantial experimental results on twelve benchmark datasets demonstrate the effectiveness of our proposals and the superiority over thirteen state-of-the-art MVGC methods.

Most existing multi-view graph clustering models focus on integrating the topological structure of different views directly, which cannot efficiently stimulate the collaboration between multiple views. To alleviate this problem, this paper proposes a Triangle Topology Enhancement (T2E) module, which expands two topological structures based on the raw topology of each view, including the self-triangle enhanced topology that highlights the local view information and the cross-view triangle enhanced topology containing the global-local view information. Afterward, this paper designs a novel multi-view graph clustering model, named MGC-T2E, to integrate both the raw and derived topological structures and directly induce consistent clustering indicators based on a self-supervised clustering module. In the simulation, the experimental results demonstrate that MGC-T2E achieves state-of-the-art performances compared with a mass of current competitors.

Graph-based multiview clustering methods have gained significant attention in recent years. In particular, incorporating graph filtering into these methods allows for the exploration and utilization of both feature and topological information, resulting in a commendable improvement in clustering accuracy. However, these methods still exhibit several limitations: 1) the graph filters are predetermined, which disconnects the link with subsequent clustering tasks and 2) the separability of the filtered features is poor, which may not be suitable for the clustering. To mitigate these aforementioned issues, we propose Multiview Clustering via Block Diagonal Graph Filtering (MvC-BDGF), which can learn cluster-friendly graph filters. Specifically, the block diagonal graph filter with localized characteristics, which could make the filtered features very discriminating, is innovatively designed. The MvC-BDGF model seamlessly integrates the learning of graph filters with the acquisition of consensus graphs, forming a unified framework. This integration allows the model to obtain optimal filters and simultaneously acquire corresponding clustering labels. To solve the optimization problem in the MvC-BDGF model, an iterative solver based on the coordinate descent method is devised. Finally, a large number of experiments on benchmark datasets fully demonstrate the effectiveness and superiority of the proposed model. The code is available at https://github.com/haonanxin/MvC-BDGF_code.

Normalized-Cut (N-Cut) is a famous model of spectral clustering. The traditional N-Cut solvers are two-stage: 1) calculating the continuous spectral embedding of normalized Laplacian matrix; 2) discretization via$K$-means or spectral rotation. However, this paradigm brings two vital problems: 1) two-stage methods solve a relaxed version of the original problem, so they cannot obtain good solutions for the original N-Cut problem; 2) solving the relaxed problem requires eigenvalue decomposition, which has${\mathcal {O}}(n^{3})$time complexity ($n$is the number of nodes). To address the problems, we propose a novel N-Cut solver designed based on the famous coordinate descent method. Since the vanilla coordinate descent method also has${\mathcal {O}}(n^{3})$time complexity, we design various accelerating strategies to reduce the time complexity to${\mathcal {O}}(|E|)$($|E|$is the number of edges). To avoid reliance on random initialization which brings uncertainties to clustering, we propose an efficient initialization method that gives deterministic outputs. Extensive experiments on several benchmark datasets demonstrate that the proposed solver can obtain larger objective values of N-Cut, meanwhile achieving better clustering performance compared to traditional solvers.

Exploiting consistent structure from multiple graphs is vital for multi-view graph clustering. To achieve this goal, we propose an Efficient Balanced Multi-view Graph Clustering via Good Neighbor Fusion (EBMGC-GNF) model which comprehensively extracts credible consistent neighbor information from multiple views by designing a Cross-view Good Neighbors Voting module. Moreover, a novel balanced regularization term based on p-power function is introduced to adjust the balance property of clusters, which helps the model adapt to data with different distributions. To solve the optimization problem of EBMGC-GNF, we transform EBMGC-GNF into an efficient form with graph coarsening method and optimize it based on accelareted coordinate descent algorithm. In experiments, extensive results demonstrate that, in the majority of scenarios, our proposals outperform state-of-the-art methods in terms of both effectiveness and efficiency.

The key challenge of multi-view graph-based clustering is to mine consistent clustering structures from multiple graphs. Existing works seek clustering decisions from either multiple spectral embeddings or multiple affinity matrices, ignoring the interactions among them. To address this problem, we propose a Bidirectional Attentive Multi-view Clustering (BAMC) model to explore a consensus space w.r.t.spectral embedding and affinity matrix simultaneously, where they can promote each other to mine richer structural information from multiple graphs. BAMC is composed of a Spectral Embedding Learning (SEL) module, an Affinity Matrix Learning (AML) module, and a Bidirectional Attentive Clustering (BAC) module. SEL seeks consensus spectral embeddings by aligning the distributions of elements sampled from subspaces spanned by multiple spectral embeddings. AML learns a consensus affinity matrix from input affinity matrices. BAC guarantees consistency between the learned consensus spectral embeddings and the affinity matrix. To balance their effects, it also assigns adaptive weights to SEL and AML's objective functions. To solve the optimization problem involved in BAMC, we propose an efficient algorithm based on the Majority-Minimization framework with an ingenious surrogate problem. Extensive experiments on several synthetic and real-world datasets demonstrate the superb performance of BAMC.

Multiview clustering (MVC) aims to exploit heterogeneous information from different sources and was extensively investigated in the past decade. However, far less attention has been paid to handling large-scale multiview data. In this brief, we fill this gap and propose a fast multiview clustering by an optimal graph mining model to handle large-scale data. We mine a consistent clustering structure from landmark-based graphs of different views, from which the optimal graph based on the one-hot encoding of cluster labels is recovered. Our model is parameter-free, so intractable hyperparameter tuning is avoided. An efficient algorithm of linear complexity to the number of samples is developed to solve the optimization problems. Extensive experiments on real-world datasets of various scales demonstrate the superiority of our proposal.

Given an affinity graph of data samples, graph-based clustering aims to partition these samples into disjoint groups based on the affinities, and most previous works are based on spectral clustering. However, two problems among spectral-based methods heavily affect the clustering performance. Firstly, the randomness of post-processing procedures, such as$K$-means, affects the stability of clustering. Secondly, the separated stages of spectral-based methods, including graph construction, spectral embedding learning, and clustering decision, lead to mismatched problems. In this paper, we explore a structured graph learning (SGL) framework that aims to fuse these stages to improve clustering stability. Specifically, SGL adaptively learns a structured affinity graph that contains exact$k$connected components. Each connected component corresponds to a cluster so clustering assignments can be directly obtained according to the connectivity of the learned graph. In this way, SGL avoids the randomness brought by reliance on traditional post-processing procedures. Meanwhile, the graph construction and structured graph learning procedures happen simultaneously, which alleviates the mismatched problem effectively. Moreover, we propose an efficient algorithm to solve the involved optimization problems and discuss the connections between this work and previous works. Numerical experiments on several synthetic and real datasets demonstrate the effectiveness of our methods.

Multiple Kernel K-means (MKKM) uses various kernels from different sources to improve clustering performance. However, most of the existing models are non-convex, which is prone to be stuck into bad local optimum, especially with noise and outliers. To address the issue, we propose a novel Self-Paced and Discrete Multiple Kernel K-Means (SPD-MKKM). It learns the MKKM model in a meaningful order by progressing both samples and kernels from easy to complex, which is beneficial to avoid bad local optimum. In addition, whereas existing methods optimize in two stages: learning the relaxation matrix and then finding the discrete one by extra discretization, our work can directly gain the discrete cluster indicator matrix without extra process. What's more, a well-designed alternative optimization is employed to reduce the overall computational complexity via using the coordinate descent technique. Finally, thorough experiments performed on real-world datasets illustrated the excellence and efficacy of our method.

Multiple Kernel k-means and its variants integrate a group of kernels to improve clustering performance, but it still has some drawbacks: 1) linearly combining base kernels to get the optimal one limits the kernel representability and cuts off the negotiation of kernel learning and clustering; 2) ignoring the correlation among kernels leads to kernel redundancy; 3) solving NP-hard cluster assignment problem by a two-stage strategy leads to information loss. In this paper, we propose the Discrete Multi-kernel k-means with Diverse and Optimal Kernel Learning (DMK-DOK) model, which adaptively seeks for a better kernel by residing in the base kernel neighborhood and negotiates the kernel learning and clustering. Moreover, it implicitly penalizes the highly correlated kernels to enhance the kernel fusion with less redundancy and more diversity. What’s more, it jointly learns discrete and relaxed labels in the same optimization objective, which can avoid information loss. Lastly, extensive experiments conducted on real-world datasets illustrated the superiority of our model.

Multiple kernel k-means clustering (MKKM) and its variants have been thoroughly studied over the past decades. However, most existing models utilize a spectrum-based two-step approach to solve the clustering objective, which may deviate from the final cluster labels and lead to suboptimal performance. To address this issue, we elaborate a novel MKKMSR framework that simultaneously optimizes the discrete and continuous cluster labels by incorporating spectral rotation into MKKM. In addition, the proposed model can be easily integrated with other MKKM models to boost their performance. What’s more, an efficient alternative algorithm is proposed to solve the joint optimization problem. Extensive experiments on real-world datasets demonstrate the superiorities of the proposed framework.

This paper proposes an Efficient Multi-view Graph Clustering with Comprehensive Fusion (EMGC²F) model and a corresponding efficient optimization algorithm to address multi-view graph clustering tasks effectively and efficiently. Compared to existing works, our proposals have the following highlights: 1) EMGC²F directly finds a consistent cluster indicator matrix with a Super Nodes Similarity Minimization module from multiple views, which avoids time-consuming spectral decomposition in previous works. 2) EMGC²F comprehensively mines information from multiple views. More formally, it captures the consistency of multiple views via a Cross-view Nearest Neighbors Voting (CN²V) mechanism, meanwhile capturing the importance of multiple views via an adaptive weighted-learning mechanism. 3) EMGC²F is a parameter-free model and the time complexity of the proposed algorithm is far less than existing works, demonstrating the practicability. Empirical results on several benchmark datasets demonstrate that our proposals outperform SOTA competitors both in effectiveness and efficiency.

The multiple kernel k -means (MKKM) and its variants utilize complementary information from different sources, achieving better performance than kernel k -means (KKM). However, the optimization procedures of most previous works comprise two stages, learning the continuous relaxation matrix and obtaining the discrete one by extra discretization procedures. Such a two-stage strategy gives rise to a mismatched problem and severe information loss. Even worse, most existing MKKM methods overlook the correlation among prespecified kernels, which leads to the fusion of mutually redundant kernels and bad effects on the diversity of information sources, finally resulting in unsatisfying results. To address these issues, we elaborate a novel Discrete and Parameter-free Multiple Kernel k -means (DPMKKM) model solved by an alternative optimization method, which can directly obtain the cluster assignment results without subsequent discretization procedure. Moreover, DPMKKM can measure the correlation among kernels by implicitly introducing a regularization term, which is able to enhance kernel fusion by reducing redundancy and improving diversity. Noteworthily, the time complexity of optimization algorithm is successfully reduced, through masterly utilizing of coordinate descent technique, which contributes to higher algorithm efficiency and broader applications. What's more, our proposed model is parameter-free avoiding intractable hyperparameter tuning, which makes it feasible in practical applications. Lastly, extensive experiments conducted on a number of real-world datasets illustrated the effectiveness and superiority of the proposed DPMKKM model.

The multiple kernel k-means (MKKM) and its variants utilize complementary information from different kernels, achieving better performance than kernel k-means (KKM). However, the optimization procedures of previous works all comprise two stages, learning the continuous relaxed label matrix and obtaining the discrete one by extra discretization procedures. Such a two-stage strategy gives rise to a mismatched problem and severe information loss. To address this problem, we elaborate a novel Discrete Multiple Kernel k-means (DMKKM) model solved by an optimization algorithm that directly obtains the cluster indicator matrix without subsequent discretization procedures. Moreover, DMKKM can strictly measure the correlations among kernels, which is capable of enhancing kernel fusion by reducing redundancy and improving diversity. What’s more, DMKKM is parameter-free avoiding intractable hyperparameter tuning, which makes it feasible in practical applications. Extensive experiments illustrated the effectiveness and superiority of the proposed model.