Generalized Category Discovery (GCD) aims to classify unlabeled data by leveraging knowledge from labeled categories. While existing methods have achieved remarkable progress, they often treat images as flat feature sets, neglecting the intrinsic hierarchy: where key objects dominate meaning and backgrounds serve as context. For instance, in images of a dog either standing on grass or lying on a bed, the dog remains the central semantic element, whereas the background varies. Motivated by this, we propose LEArning Intrinsic Hierarchy (LEAH), a lightweight plug-and-play module designed to model hierarchical structure within images. LEAH consists of two components: a pruner that filters task-irrelevant tokens to extract key objects, and a constructor that embeds key objects and full images into hyperbolic space using adaptive entailment cones to capture compositional semantics. LEAH can be easily integrated into existing GCD frameworks with minimal modification. When applied to SimGCD, it achieves up to 13.2% accuracy improvement on fine-grained benchmarks, demonstrating its effectiveness in discovering subtle inter-class differences through hierarchical modeling.

Neuroscientific evidence reveals that human visual recognition is not an instantaneous event but a hierarchical process, where the brain constructs a holistic perception by progressively integrating simple features like edges or texture into complex scenes. Ensemble learning successfully utilizes this principle, yet existing methods typically integrate models at the decision level, neglecting the rich, complementary information within the feature space itself and thus fundamentally limiting their potential. To address this, we introduce Synergistic Semantic Boosting (S2-Boosting), a framework that employs a self-supervised hierarchical semantic learning module to decompose an image into complementary, semantically meaningful parts autonomously. These parts guide a boosting procedure where a sequence of specialized learners, each focusing on a specific semantic partition, collaboratively corrects the ensemble's errors. We further present encouraging results on real-world image datasets, highlighting the intrinsic interpretability, paving the way for more robust and transparent models.

Federated clustering addresses the critical challenge of extracting patterns from decentralized, unlabeled data. However, it is hampered by the flaw that current approaches are forced to accept a compromise between performance and privacy: transmitting embedding representations risks sensitive data leakage, while sharing only abstract cluster prototypes leads to diminished model accuracy. To resolve this dilemma, we propose Structural Privacy-Preserving Federated Graph Clustering (SPP-FGC), a novel algorithm that innovatively leverages local structural graphs as the primary medium for privacy-preserving knowledge sharing, thus moving beyond the limitations of conventional techniques. Our framework operates on a clear client-server logic; on the client-side, each participant constructs a private structural graph that captures intrinsic data relationships, which the server then securely aggregates and aligns to form a comprehensive global graph from which a unified clustering structure is derived. The framework offers two distinct modes to suit different needs. SPP-FGC is designed as an efficient one-shot method that completes its task in a single communication round, ideal for rapid analysis. For more complex, unstructured data like images, SPP-FGC+ employs an iterative process where clients and the server collaboratively refine feature representations to achieve superior downstream performance. Extensive experiments demonstrate that our framework achieves state-of-the-art performance, improving clustering accuracy by up to 10% (NMI) over federated baselines while maintaining provable privacy guarantees.

Self-supervised 3D point cloud understanding is crucial for scene understanding, where Masked Autoencoders (MAE) have achieved excellent performance in point cloud representation learning. However, existing MAE-style methods fail to consider spatial-semantic variations in masking strategies, and joint learning with multi-view images often overlooks view redundancy. To address these challenges, we propose an MAE framework enhanced with reliable multi-view 2D-3D Key-part alignment and Reinforced masking, named as KR-MAE. Our approach comprises three key innovations: Reinforced Masking (RM) strategically samples visible tokens based on semantic saliency to enhance reconstruction fidelity; Reliable Multi-View Selector (RVS) dynamically refines the most informative image subset by filtering occluded or low-texture views, mitigating detrimental redundancy; Reliable-view 2D-3D Key-part Aligned Transformer (KAT) establishes semantic-aligned correspondence between salient 3D point cloud parts and reliable multi-view 2D image patches, leveraging rich texture cues from 2D images to compensate for sparse geometry in point cloud. Extensive experiments on 3D classification and segmentation benchmarks demonstrate that KR-MAE achieves state-of-the-art performance, surpassing prior multi-modal methods.

Ensemble learning methods, such as Bagging and Boosting, are well-regarded for their ability to enhance model performance by combining diverse base learners. These approaches leverage the strengths of individual models to achieve more accurate and robust predictions. However, real-world datasets often contain noise, which can significantly impair model effectiveness. This paper focuses on two prevalent and challenging types: feature noise, which can lead to fitting instability and poor generalization, and label noise, which can lead to erroneous supervision and model overfitting. Recognizing the inherent properties of ensemble learning, particularly its focus on optimizing the decision margin to improve classification accuracy, we see an opportunity to bolster ensemble model robustness. To address both feature and label noise, we propose a novel approach called Dual Geometry Margin Boosting (DGMB). This method employs two key strategies: the Decision Plane Margin (DPM), which enhances class separation, and the Hyper-Sphere Margin (HSM), which effectively filters out potentially noisy samples during the learning process. Our experiments demonstrate the impressive ability of DGMB to resist both feature and label noise. Through rigorous testing on various noise-contaminated datasets, we show that DGMB maintains strong performance and outperforms other robust Ensemble methods.

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.

Feature selection is one of the hot issues in machine learning. It reduces storage pressure by effectively screening features and has become a very practical data preprocessing method. At present, most feature selection algorithms apply $\ell _{2,1}$ -norm on the transformation matrix to calculate the scores for all features and then select appropriate features according to these scores. But their sparsity is limited, and meaningless regularization parameters increase the cost, making it prone to falling into local optimum. To solve the above difficulties, this article proposes a novel max-min robust unsupervised feature selection via sparse subspace (MMRUFS), which considers both the reconstruction term and variance term of data, so that the model can not only fully retain the original information of data, but also make the data more dispersed. Second, $\ell _{2,0}$ -norm constraint is used on the transformation matrix to directly select the optimal feature subset, avoiding the fine-tuning of regularization parameters. To enhance the robustness, MMRUFS carefully designs mark weight vector to make the model treat normal samples and outliers differently and achieves the effect of anomaly detection. Finally, MMRUFS is solved by designing the surrogate matrix, and its convergence is strictly guaranteed, experimental results reveal that MMRUFS outperforms other feature selection algorithms on multiple real-world datasets.

Graph-based multi-view clustering has become a powerful tool for multi-view data analysis by jointly capturing structural relationships across heterogeneous views. Despite significant advances in this field, several limitations persist. Most graph-based multi-view algorithms employ a relaxation-and-discretization two-stage paradigm to obtain clustering assignments, which may significantly undermine information preservation and clustering performance. Moreover, these methods often suffer from quadratic or even cubic time complexity, rendering them impractical for large-scale applications. Additionally, existing graph-based multi-view models struggle to adequately capture the inherent uncertainty characterized by ambiguous or overlapping clustering boundaries. To address these challenges, this paper proposes a multi-view fuzzy clustering method with anchor graph. Specifically, the proposed method learns a symmetric and doubly stochastic consensus similarity graph from multiple views and performs clustering directly on the learned consensus graph, thereby directly outputting clustering results. By imposing nonnegativity and row normalization constraints on the cluster indicator matrix, the proposed method can further reveal the underlying uncertain clustering structure. Furthermore, an iterative optimization algorithm with linear complexity is developed to solve the proposed model. Extensive experiments conducted on both synthetic and real-world benchmark datasets illustrate the effectiveness and efficiency of the proposed method against state-of-the-art models.

Tensor-based multi-view clustering algorithms have attracted considerable attention due to their superior clustering performance. However, these algorithms typically treat each view independently, failing to utilize the complementary information across all views, thus lacking globality. Additionally, employing low-rank tensor constraints to extract consistent information among views may result in the loss of important information due to weak consistency constraints. These limitations significantly hinder the clustering performance. To address these issues, we propose Simple Multi-view Tensor Clustering (SimMTC), which achieves globality and strong consistency. SimMTC first applies Fast Fourier Transform (FFT) to the anchor graphs to obtain high-frequency and low-frequency information, which encode similarities between samples and anchors from all views, thereby capturing global information. Orthogonal tensor factorization is then conducted in the frequency domain. Moreover, a novel strong consistency constraint based on FFT is introduced, which enhances the extraction of consistent information in the frequency domain. What's more, an efficient alternating optimization algorithm is designed to solve the optimization problem in SimMTC. Finally, extensive experiments on real-world datasets demonstrate that SimMTC achieves state-of-the-art clustering performance. The code has been made publicly available on GitHub at: https://github.com/haonanxin/SimMTC_code.

We propose the DPSM method, a density-based node clustering approach that automatically determines the number of clusters and can be applied in both data space and graph space. Unlike traditional density-based clustering methods, which necessitate calculating the distance between any two nodes, our proposed technique determines density through a propagation process, thereby making it suitable for a graph space. In DPSM, nodes are partitioned into small clusters based on propagated density. The partitioning technique has been proved to be sound and complete. We then extend the concept of spectral clustering from individual nodes to these small clusters, while introducing the CluCut measure to guide cluster merging. This measure is modified in various ways to account for cluster properties, thus provides guidance on when to terminate the merging process. Various experiments have validated the effectiveness of DPSM and the accuracy of these conclusions.

K-means algorithm divides samples into c classes based on their structural characteristics. However, due to the non convex nature of the clustering problem, algorithms are prone to converge to poor local minima. To address the aforementioned issues, we propose the Local Structure Preserving Clustering with Learnable Anchors (LSPC-LA) method. We assume that with a well-designed anchor selection strategy, samples near the same anchor tend to belong to the same cluster, which reveal high confidence Must-Link local structural information for clustering. Based on this observation, we first construct an anchor-based bipartite graph, transforming the sample clustering problem into anchor clustering problem by local structural information, thus reducing the solution space and minimizing the risk of poor local minima. Then we create an anchor guiding matrix to allow anchors to learn the sample structure, improving clustering performance. Subsequently, an alternating iterative algorithm is proposed to optimize the LSPC-LA model. Finally, extensive experiments demonstrate the accuracy of the local structural information and the effectiveness of LSPC-LA.

Deep models, characterized by complex structures and end-to-end optimization, proved effective in providing decision support based on real-world data. However, the lack of transparency in their decision-making process and the difficulty in interpreting the role of individual neurons limited their practical applicability in many critical and sensitive domains. Inspired by the parallels between neural networks and ensemble models, where performance was achieved through the collaboration of multiple weak learners, this article presents a novel perspective that reframes neural networks as hierarchical ensembles. We propose the hierarchical backpropagated ensemble (HBE) model, wherein each neuron functions both as a base learner and as part of an ensemble of preceding neurons. This framework applies ensemble learning techniques to neural networks, allowing each neuron to focus on specific subtasks while progressively constructing a network that meets global objectives. Experimental results on real-world data show that this hierarchical structure enhances the effectiveness of traditional ensemble models, and the ensemble-based explanations offer improved initialization and dynamically adjustable network structures, leading to more efficient training.

The representation learning of time series has a wide range of downstream tasks and applications in many practical scenarios. However, due to the complexity, spatiotemporality, and continuity of sequential stream data, compared with the representation learning of structural data such as images/videos, the time series self-supervised representation learning is even more challenging. Besides, the direct application of existing contrastive learning and masked autoencoder based approaches to time series representation learning encounters inherent theoretical limitations, such as ineffective augmentation and masking strategies. To this end, we propose a Language Pre-training guided Masking Representation Learning (LPMRL) for times series classification. Specifically, we first propose a novel language pre-training guided masking encoder for adaptively sampling semantic spatiotemporal patches via natural language descriptions and improving the discriminability of latent representations. Furthermore, we present the dual-information contrastive learning mechanism to explore both local and global information by meticulously designing high-quality hard negative samples of time series data samples. As a result, we also design various experiments, such as visualization of masking position and distribution and reconstruction error to verify the reasonability of proposed language guided masking technique. Last, we evaluate the performance of proposed representation learning via classification task conducted on 106 time series datasets, which demonstrates the effectiveness of proposed method.

The growing volume of remote sensing (RS) data highlights the need for enhanced data integration and processing. While combining hyperspectral and LiDAR data improves analysis by addressing spectral variability, challenges persist due to the high dimensionality, noise, and outliers in hyperspectral images (HSI). Additionally, supervised classification is labor-intensive, further motivating the need for advanced unsupervised clustering methods. Current clustering approaches, however, struggle with underutilization of spatial information, redundant spectral bands, and information divergence across multimodal data. To overcome these issues, we propose a Dimensionality-Reduced Spatial Bipartite Graph Clustering for Hyperspectral and LiDAR Data. This method integrates spatial information through bipartite graphs, reduces dimensionality by eliminating redundant bands, and employs a tensor-based framework to explore consistent structures in the low-rank space. This reduces information divergence and enhances clustering stability and performance. Extensive experiments demonstrate the effectiveness and robustness of the proposed method on real datasets.

Ensemble clustering using co-association matrices integrates multiple base clusterings but often overlooks interactions between crucial samples and base clusterings. This neglect can introduce noise and lead to information loss and instability. To address these issues, we propose the Consensus Graph-Based Spectral Ensemble Clustering via Low-Rank Tensor Learning (SECGTL) model. SECGTL organizes base clusterings into a third-order tensor and applies the Fast Fourier Transform (FFT) to capture inter-relations in the frequency domain. By rotating the tensor and minimizing the Tensor Schatten p-norm, SECGTL extracts shared information in a low-rank space, reducing noise and enhancing the learned common graph. With Laplacian rank constraints, SECGTL directly learns a graph with c-connected components, representing the clustering structure without post-processing. Extensive experiments on real-world datasets demonstrate SECGTL’s superior performance and robustness to noise.

Label noise in hyperspectral image classification (HIC) can severely degrade model performance by leading to incorrect predictions and overfitting, especially as erroneous labels propagate and compound throughout the training process. To address this, we propose a robust learning framework called Self-Supervised Localized Topology Consistency (SSLTC), which enforces local topology consistency to enhance model resilience against noisy labels. SSLTC captures local topology via a graph-based representation, where nodes represent samples and edges encode pairwise similarities. Predictions are propagated from topologically similar nodes to central nodes, constrained by Kullback-Leibler (KL) divergence to encourage consistent predictions and reduce sensitivity to noisy labels. Additionally, a self-supervised contrastive learning strategy is used to refine spectral-spatial representations in an unsupervised manner, further improving robustness. Extensive experiments on hyperspectral benchmark datasets with varying noise levels demonstrate the superiority of SSLTC in mitigating the adverse effects of label noise compared to state-of-the-art approaches in HIC tasks.

The use of anchors often leads to better efficiency and scalability, making them highly favored. However, there is a challenge in anchor-based multi-view subspace learning. A unified anchor graph overly emphasize the commonality between views, failing to adequately capture the view-specific individuality. This has led some models to independently explore the individuality of each view before aligning and integrating them, often achieving better performance but making the process more cumbersome. Therefore, this paper proposes a new model, simultaneously capturing the individuality and commonality between anchor graphs for multi-view clustering. The model has three notable advantages: First, it allows view-specific anchor graphs to align in real-time with a common anchor graph as a reference, eliminating the need for post-alignment. Second, it enforces a cluster-wise structure among anchors and balances sample distribution among them, providing strong discriminative power. Lastly, it maintains linear complexity with respect to the numbers of samples and anchors, avoiding the significant time costs associated with their increase. Comprehensive experiments demonstrate the effectiveness and efficiency of our method compared to various state-of-the-art algorithms.

Feature selection plays an important role in a wide range of applications. Most sparsity-based feature selection methods solve a relaxed$\ell _{2,p}$-norm ($0 \lt p \leq 1$) regularized problem, which often results in a sub-optimal feature subset and requires extensive effort to tune regularization parameters. Optimizing the non-convex$\ell _{2,0}$-norm constrained problem remains an open challenge. Existing optimization algorithms for solving the$\ell _{2,0}$-norm constrained problem often rely on specific data distribution assumptions and cannot guarantee global convergence. In this article, we propose an unsupervised discriminative feature selection method using$\ell _{2,0}$-norm constrained sparse projection (SPDFS) to address these challenges. Specifically, building on the principle of supervised linear discriminant analysis, fuzzy membership learning and$\ell _{2,0}$-norm constrained projection learning are jointly performed to learn a feature-wise sparse projection for unsupervised discriminative feature selection. More importantly, we follow two optimization strategies to address the NP-hard nature of the problem: a non-iterative algorithm with a globally optimal solution is derived for a special case, and an iterative algorithm with both ascent property and approximation guarantee is employed for the general case. Additionally, we explore the relationship between our model and its potential variants. Experimental results on both synthetic and real-world datasets demonstrate the superiority of the proposed method over several state-of-the-art methods in data clustering and text classification tasks. The code is available at:https://github.com/xiadongcs/SPDFS.

In the graph-based semi-supervised learning, the Green-function method is a classical method that works by computing the Green's function in the graph space. However, when applied to large graphs, especially those sparse ones, this method performs unstably and unsatisfactorily. We make a detailed analysis on it and propose a novel method from the perspective of optimization. On fully connected graphs, the method is equivalent to the Green-function method and can be seen as another interpretation with physical meanings, while on non-fully connected graphs, it helps to explain why the Green-function method causes a mess on large sparse graphs. To solve this dilemma, we propose a workable approach to improve our proposed method. Unlike the original method, our improved method can also apply two accelerating techniques, Gaussian Elimination, and Anchored Graphs to become more efficient on large graphs. Finally, the extensive experiments prove our conclusions and the efficiency, accuracy, and stability of our improved Green's function method.

Ensemble clustering based on co-association matrices integrates multiple connective matrices from base clusterings to achieve superior results. However, these methods primarily focus on inter-sample relationships, neglecting variations across different base clusterings, potentially introducing noise. Additionally, they overlook interactions between samples and base clusterings, which are crucial for extracting common information and avoiding post-processing steps that may cause information loss and instability in clustering results. To address these issues, we propose the Tensorized Graph Learning for Spectral Ensemble Clustering (TGLSEC) model. TGLSEC stacks all connective matrices into a third-order tensor, employs Fast Fourier Transform (FFT) for encoding, and elucidates inter-relations in the frequency domain. By minimizing the tensor Schatten p-norm, TGLSEC extracts common information in the low-rank space, eliminating noise and improving the quality of the common shared graph. Incorporating Laplacian rank constraints, TGLSEC learns a common shared graph with c-connected components, directly representing the clustering structure and avoiding post-processing steps, leading to more stable clustering results. To enhance computational efficiency for large-scale datasets, TGLSEC has been expanded into a bipartite-graph-based model, TGLSEC-BG, reducing complexity and computational time. Extensive experiments on real-world datasets demonstrate that TGLSEC and TGLSEC-BG exhibit superior clustering performance and robustness to noise.

Ensemble clustering, which combines the information from multiple base clusterings to obtain a better partition result, has received extensive attention due to its effectiveness and robustness. Although many algorithms have been developed in recent years that have achieved impressive results in practical applications, two challenging issues in ensemble clustering remain. First, most algorithms assume that all base clusterings have the same impact on the clustering results, assigning them the same weight. This makes the clustering performance susceptible to the influence of redundant, low-quality base clusterings. Second, co-association matrix-based algorithms often rely on additional methods, such as hierarchical agglomerative clustering, to obtain the final clustering result after constructing the weighted co-association matrix. This not only complicates optimization process but also leads to the loss of some sample-similarity information during clustering. To address this problem, we propose a novel Toward Balance Adaptive Weighted Ensemble Clustering (TBAWEC) algorithm. This method transforms the ensemble clustering problem into an optimization problem, producing the final result without requiring additional clustering algorithms. Moreover, we introduce balanced technology into ensemble clustering for the first time, significantly improving the balance of clustering results. Extensive experiments on real datasets demonstrate that the proposed algorithm outperforms the most advanced ensemble and balanced clustering algorithms simultaneously.

Clustering based on structured graph learning involves acquiring a proximity matrix with an explicit clustering structure from the original one. However, the original proximity matrix often lacks some must-links compared to the groundtruth, constraining the upper bound of clustering performance. High-order proximity information can mitigate this limitation, yet traditional high-order proximity matrix-based methods are time-intensive. To tackle this, we propose the Tensorized High-order Bipartite Graphs-based structured proximity matrix learning method (THBG). Firstly, we introduce a high-order bipartite graph proximity matrix with a swift computation method, incorporating high-order information and significantly reducing computational overhead. Secondly, we apply tensor nuclear norm minimization to the tensor composed of high-order bipartite graphs, learning a low-rank tensor representation that effectively harnesses the consistency of high-order information. Concurrently, a structured bipartite graph proximity matrix with an explicit clustering structure is adaptively learned based on the low-rank tensor representation and Laplace rank constraint. Experimental results demonstrate the superiority and great potential of this method. Code available:https://anonymous.4open.science/r/THBG-D10D.

The clustering algorithm has always been a hot spot in machine learning, which has made great progress and been widely used in different scenarios. Due to the characteristics and requirements of some application scenarios, the branch of the balanced clustering algorithm has been developed. The ideal of these algorithms is to obtain clusters containing approximately the same number of samples. However, when there are data points distributed at the boundary of different clusters, resulting in different probabilities of their belonging, hard-partitioned balanced clustering may not be able to handle these boundary data well, thus limiting their performance. Motivated by this, we propose a Fuzzy Min-Cut with Soft Balancing Effects (FCBE) method in this article. Specifically, the FCBE model utilizes fuzzy constraints to simultaneously enhance the ability of the balanced algorithm to capture boundary data members and the advantage of directly obtaining the partitioning results of graph-cut problem without postprocessing. In addition, a sparse regularization is introduced to avoid trivial solutions and maintain the separability of the relationship matrix. Furthermore, the proposed FCBE method can be viewed as a flexibly adjustable generalization pattern that not only has clear interpretability but also can become special cases with clear physical meanings under different parameter values. The feasibility of FCBE has been verified on real datasets.

Clusteringis an important unsupervised learning technique widely applied in data analysis and pattern recognition. Graph-based clustering methods have gained attention for their ability to effectively model complex data structures. However, traditional methods mainly rely on first-order proximity information, which struggles to capture high-order structural relationships between data points. Such limitation can significantly degrade clustering performance. To address this issue, we propose a novel fuzzy clustering approach leveraging orthogonal tensor decomposition on high-order anchor graphs (OTDHAG). Unlike conventional high-order graph-based methods that rely on self-multiplication of proximity matrices, which are computationally expensive, our method introduces the high-order anchor graph with low computational complexity, and exploits high-order proximity information via orthogonal tensor factorization on high-order anchor graphs. Meanwhile, tensor nuclear norm regularization is adopted to enhance clustering consistency, thereby improving clustering quality. Experiments on 10 benchmark datasets (e.g., MNIST, Wine, PIE) demonstrate that OTDHAG outperforms 14 state-of-the-art methods, achieving 92.3% accuracy on Wine (vs. 86.5% for DenoHOG) and 88.7% NMI on MNIST (vs. 82.1% for AOPL-Root). In conclusion, OTDHAG not only significantly improves clustering accuracy and computational efficiency but also provides a scalable solution for clustering tasks. Code available:https://anonymous.4open.science/r/HOAGTD-CED0.

The surge in remote sensing (RS) data underscores the need for improved data diversity and processing. While integrating hyperspectral (HS) and light detection and ranging (LiDAR) data enhances analysis and addresses spectral variability, the high dimensionality, noise, and outliers inherent in hyperspectral images present significant challenges. In addition, the precise labeling required for HS makes supervised classification labor-intensive, professional-focused, and time-consuming, further motivating the development of advanced HS clustering algorithms to address these issues. Unsupervised clustering addresses the above issues but still struggles due to the underutilization of auxiliary spatial and structural information, high data dimensionality with redundant hyperspectral bands, and information divergence from heterogeneity among multimodal data. These challenges impede the effective extraction of consistent structures, undermining clustering stability and overall model performance. To address these challenges, we propose a superpixel-based bipartite graph clustering (SBGC) enriched with spatial information for hyperspectral and LiDAR data models. Our proposed method fully utilizes spatial information to construct meaningful bipartite graphs for the efficient processing of multimodal RS data. By adopting a projected clustering paradigm, our approach simultaneously clusters and reduces dimensionality, effectively eliminating redundant bands. In addition, it innovatively stacks multimodal data into tensors, thoroughly exploring the consistent structures in the low-rank space among different modalities. This reduces the heterogeneity-induced information divergence and significantly enhances clustering performance. Extensive experiments on real datasets confirm the method’s effectiveness and advanced capabilities.

Label noise in hyperspectral image classification (HIC) has posed a significant challenge, mainly due to the complexity of high-dimensional spectral-spatial data. Existing approaches that rely on sample predictions for verification and correction often amplify confirmation bias, leading to decision boundaries that overfit to noisy labels. To address these issues, we propose a Manifold-Aligned Consistency Contrastive Learning (MACCL) framework that establishes a mutually-guided consistency alignment mechanism between the spectral-spatial representation space and label space through manifold learning theory to combat label noise. Specifically, to mitigate the confirmation bias of noisy labels, we introduce a manifold-aligned consistency learning module. It leverages the manifold assumption in the representation space, modeling local neighborhood graphs and enforcing consistent prediction distributions via KL divergence. This aligns label-space classifications with the representation space’s local geometry, suppressing isolated noise through manifold continuity. Additionally, to combat representation degradation that causes decision boundaries to overfit noisy labels, we integrate a noise-tolerant contrastive representation learning module. By applying confidence-guided criteria, the module focuses on high-confidence sample pairs and regularizes gradients. This emphasizes clean pairs during training, boosting the model’s discriminative ability and preserving true semantic relationships. Through this mutual guidance, the contrastive learning refines the local geometric structure through discriminative representation learning, driving the representation space closer to the intrinsic data manifold, while the manifold alignment propagates geometric constraints to rectify label space corruptions. Finally, experiments on several benchmark datasets with varying levels of noise have validated the superiority of the proposed MACCL framework.

Existing deep clustering methods leverage contrastive or non-contrastive learning to facilitate downstream tasks. Most contrastive-based methods typically learn representations by comparing positive pairs (two views of the same sample) against negative pairs (views of different samples). However, we spot that this hard treatment of samples ignores inter-sample relationships, leading to class collisions and degrade clustering performances. In this paper, we propose a soft neighbor supported contrastive clustering method to address this issue. Specifically, we first introduce a concept called perception radius to quantify similarity confidence between a sample and its neighbors. Based on this insight, we design a two-level soft neighbor loss that captures both local and global neighborhood relationships. Additionally, a cluster-level loss enforces compact and well-separated cluster distributions. Finally, we conduct a pseudo-label refinement strategy to mitigate false negative samples. Extensive experiments on benchmark datasets demonstrate the superiority of our method. The code is available at https://github.com/DuannYu/soft-neighbors-supported-clustering.

As we all known, sparse subspace learning can provide good input for spectral clustering, thereby producing high-quality cluster partitioning. However, it employs complete samples as the dictionary for representation learning, resulting in non-negligible computational costs. Therefore, replacing the complete samples with representative ones (anchors) as the dictionary has become a more popular choice, giving rise to a series of related works. Unfortunately, although these works are linear with respect to the number of samples, they are often quadratic or even cubic with respect to the number of anchors. In this paper, we derive a simpler problem to replace the original scalable subspace clustering, whose properties are utilized. This new problem is linear with respect to both the number of samples and anchors, further enhancing scalability and providing more efficient operations. Furthermore, thanks to the new problem formulation, we can adopt a separate fusion strategy for multi-view extensions. This strategy can better measure the inter-view difference and avoid alternate optimization, so as to achieve more robust and efficient multi-view clustering. Finally, comprehensive experiments demonstrate that our methods not only significantly reduce time overhead but also exhibit superior performance.

Principal Component Analysis (PCA) is one of the most important unsupervised dimensionality reduction algorithms, which uses squared -norm to make it very sensitive to outliers. Those improved versions based on -norm alleviate this problem, but they have other shortcomings, such as optimization difficulties or lack of rotational invariance, etc. Besides, existing methods only vaguely divide normal samples and outliers to improve robustness, but they ignore the fact that normal samples can be more specifically divided into positive samples and hard samples, which should have different contributions to the model because positive samples are more conducive to learning the projection matrix. In this paper, we propose a novel Data Subdivision Based Dual-Weighted Robust Principal Component Analysis, namely DRPCA, which firstly designs a mark vector to distinguish normal samples and outliers, and directly removes outliers according to mark weights. Moreover, we further divide normal samples into positive samples and hard samples by self-constrained weights, and place them in relative positions, so that the weight of positive samples is larger than hard samples, which makes the projection matrix more accurate. Additionally, the optimal mean is employed to obtain a more accurate data center. To solve this problem, we carefully design an effective iterative algorithm and analyze its convergence. Experiments on real-world and RGB large-scale datasets demonstrate the superiority of our method in dimensionality reduction and anomaly detection.

Principal Component Analysis (PCA) is one of the most famous unsupervised dimensionality reduction algorithms and has been widely used in many fields. However, it is very sensitive to outliers, which reduces the robustness of the algorithm. In recent years, many studies have tried to employ \(\ell_{1}\) -norm to improve the robustness of PCA, but they all lack rotation invariance or the solution is expensive. In this article, we propose a novel robust PCA, namely, Fuzzy Weighted Principal Component Analysis (FWPCA), which still uses squared \(\ell_{2}\) -norm to minimize reconstruction error and maintains rotation invariance of PCA. The biggest bright spot is that the contribution of data is restricted by fuzzy weights, so that the contribution of normal samples is much greater than noise or abnormal data, and realizes anomaly detection. Besides, a more reasonable data center can be obtained by solving the optimal mean to make projection matrix more accurate. Subsequently, an effective iterative optimization algorithm is developed to solve this problem, and its convergence is strictly proved. Extensive experimental results on face datasets and RGB anomaly detection datasets show the superiority of our proposed method.

Fuzzy c-means based on entropy regularization (FCER) is a commonly used machine learning algorithm that uses maximum entropy as the regularization term to realize fuzzy clustering. However, this model has many constraints and is challenging to optimize directly. During the solution process, the membership matrix and cluster centers are alternately optimized, easily converging to poor local solutions, limiting the clustering performance. In this paper, we start with the optimization model and propose an unconstrained fuzzy clustering model (UFCER) equivalent to FCER, which reduces the size of optimization variables from$(n+d)\times c$to$d\times c$. More importantly, there is no need to calculate the membership matrix during the optimization process iteratively. The time complexity is only linear, and the convergence speed is fast. We conduct extensive experiments on real datasets. The comparison of objective function value and clustering performance fully demonstrates that under the same initialization, our proposed algorithm can converge to smaller local minimums and get better clustering performance.

Unsupervised domain adaptation aims to classify unlabeled data points in the target domain using labeled data points from the source domain, while the distributions of data points in two domains are different. To address this issue, we propose a novel method called the anchor guided unsupervised domain adaptation method (AGDA). We minimize distribution divergence in a latent feature subspace using the Maximum Mean Discrepancy (MMD) criterion. Unlike existing unsupervised domain adaptation methods, we introduce anchor points in the original space and impose domains data to the same anchor points rather than center points to further reduce the domain difference. We optimize the anchor-based graph in the subspace to obtain discriminative transformation matrices. This enables our model to perform better on non-Gaussian distribution than methods focusing on global structure. Furthermore, the sparse anchor-based graph reduces time complexity compared to the fully connected graph, enabling exploration of local structure. Experimental results demonstrate that our algorithm outperforms several state-of-the-art methods on various benchmark datasets.

Structured proximity matrix learning, one of the mainstream directions in clustering research, refers to learning a proximity matrix with an explicit clustering structure from the original first-order proximity matrix. Due to the complexity of the data structure, the original first-order proximity matrix always lacks some must-links compared to the groundtruth proximity matrix. It is worth noting that high-order proximity matrices can provide missed must-link information. However, the computation of high-order proximity matrices and clustering based on them are expensive. To solve the above problem, inspired by the anchor bipartite graph, we present a novel high-order bipartite graph proximity matrix and a fast method to compute it. This proposed high-order bipartite graph proximity matrix contains high-order proximity information and can significantly reduce the computational complexity of the whole clustering process. Furthermore, we introduce an efficient and simple high-order bipartite graph fusion framework that can adaptively assign weights to each order of the high-order bipartite graph matrices. Finally, under the Laplace rank constraint, a consensus structured bipartite graph proximity matrix is obtained. At the same time, an efficient solution algorithm is proposed for this model. The model's efficacy is underscored through rigorous experiments, highlighting its superior clustering performance and time efficiency. Code available:https://anonymous.4open.science/r/HBGC-F6C4.

Ensemble clustering can utilize the complementary information among multiple base clusterings, and obtain a clustering model with better performance and more robustness. Despite its great success, there are still two problems in the current ensemble clustering methods. First, most ensemble clustering methods often treat all base clusterings equally. Second, the final ensemble clustering result often relies on$k$-means or other discretization procedures to uncover the clustering indicators, thus obtaining unsatisfactory results. To address these issues, we proposed a novel ensemble clustering method based on structured graph learning, which can directly extract clustering indicators from the obtained similarity matrix. Moreover, our methods take sufficient consideration of correlation among the base clusterings and can effectively reduce the redundancy among them. Extensive experiments on artificial and real-world datasets demonstrate the efficiency and effectiveness of our methods.

Feature selection plays an important role in data analysis, yet traditional graph-based methods often produce suboptimal results. These methods typically follow a two-stage process: constructing a graph with data-to-data affinities or a bipartite graph with data-to-anchor affinities and independently selecting features based on their scores. In this article, a large-scale feature selection approach based on structured bipartite graph and row-sparse projection (RS2BLFS) is proposed to overcome this limitation. RS2BLFS integrates the construction of a structured bipartite graph consisting of c connected components into row-sparse projection learning with k nonzero rows. This integration allows for the joint selection of an optimal feature subset in an unsupervised manner. Notably, the c connected components of the structured bipartite graph correspond to c clusters, each with multiple subcluster centers. This feature makes RS2BLFS particularly effective for feature selection and clustering on nonspherical large-scale data. An algorithm with theoretical analysis is developed to solve the optimization problem involved in RS2BLFS. Experimental results on synthetic and real-world datasets confirm its effectiveness in feature selection tasks.

The goal of balanced clustering is partitioning data into distinct groups of equal size. Previous studies have attempted to address this problem by designing balanced regularizers or utilizing conventional clustering methods. However, these methods often rely solely on classic methods, which limits their performance and primarily focuses on low-dimensional data. Although neural networks exhibit effective performance on high-dimensional datasets, they struggle to effectively leverage prior knowledge for clustering with a balanced tendency. To overcome the above limitations, we propose deep semisupervised balanced clustering, which simultaneously learns clustering and generates balance-favorable representations. Our model is based on the autoencoder paradigm incorporating a semisupervised module. Specifically, we introduce a balance-oriented clustering loss and incorporate pairwise constraints into the penalty term as a pluggable module using the Lagrangian multiplier method. Theoretically, we ensure that the proposed model maintains a balanced orientation and provides a comprehensive optimization process. Empirically, we conducted extensive experiments on four datasets to demonstrate significant improvements in clustering performance and balanced measurements. Our code is available at https://github.com/DuannYu/BalancedSemi-TNNLS.

This study addresses the problem of generalized category discovery (GCD), an advanced and challenging semi-supervised learning scenario that deals with unlabeled data from both known and novel categories. Although recent research has effectively engaged with this issue, these studies typically map features into Euclidean space, which fails to maintain the latent semantic hierarchy of the training samples effectively. This limitation restricts the exploration of more detailed and rich information and degrades the performance in discovering new categories. The emerging field of hyperbolic representation learning suggests that hyperbolic geometry could be advantageous for extracting semantic information to tackle this problem. Motivated by this, we proposed hyperbolic hierarchical representation learning for GCD (HypGCD). Specifically, HypGCD enhances representations in hyperbolic space, building upon the Euclidean space representation from two perspectives: instance-class level and instance-instance level. At the instance-class level, HypGCD endeavors to construct well-defined clusters, with each sample forming a robust hierarchical cluster structure. Concurrently, at the instance-instance level, HypGCD anticipates that a subset of samples will display a tree-like structure in local space, which aligns more closely with real-world scenarios. Finally, HypGCD optimizes the Euclidean and hyperbolic space collectively to obtain refined features. Additionally, we show that HypGCD is exceptionally effective, achieving state-of-the-art (SOTA) results on several datasets. The code is available at https://github.com/DuannYu/HypGCD.

Linear discriminant analysis (LDA) is a classic tool for supervised dimensionality reduction. Because the projected samples can be classified effectively, LDA has been successfully applied in many applications. Among the variants of LDA, trace ratio LDA (TR-LDA) is a classic form due to its explicit meaning. Unfortunately, when the sample size is much smaller than the data dimension, the algorithm for solving TR-LDA does not converge. The so-called small sample size (SSS) problem severely limits the application of TR-LDA. To solve this problem, we propose a revised formation of TR-LDA, which can be applied to datasets with different sizes in a unified form. Then, we present an optimization algorithm to solve the proposed method, explain why it can avoid the SSS problem, and analyze the convergence and computational complexity of the optimization algorithm. Next, based on the introduced theorems, we quantitatively elaborate on when the SSS problem will occur in TR-LDA. Finally, the experimental results on real-world datasets demonstrate the effectiveness of the proposed method.

Recently, more and more real-world datasets have been composed of heterogeneous but related features from diverse views. Multiview clustering provides a promising attempt at a solution for partitioning such data according to heterogeneous information. However, most existing methods suffer from hyper-parameter tuning trouble and high computational cost. Besides, there is still an opportunity for improvement in clustering performance. To this end, a novel multiview framework, called parameter-free multiview -means clustering with coordinate descent method (PFMVKM), is presented to address the above problems. Specifically, PFMVKM is completely parameter-free and learns the weights via a self-weighted scheme, which can avoid the intractable process of hyper-parameters tuning. Moreover, our model is capable of directly calculating the cluster indicator matrix, with no need to learn the cluster centroid matrix and the indicator matrix simultaneously as previous multiview methods have to do. What's more, we propose an efficient optimization algorithm utilizing the idea of coordinate descent, which can not only reduce the computational complexity but also improve the clustering performance. Extensive experiments on various types of real datasets illustrate that the proposed method outperforms existing state-of-the-art competitors and conforms well with the actual situation.

Graph-based clustering is a hot topic in machine learning, whose effectiveness highly relies on the quality of the learned graph. Recent researches preferred to learn the nearest doubly stochastic approximation of a graph to suppress intercluster connections and enhance intracluster connections and thus improve clustering performance. While current paradigm is limited by three key problems: 1) it is restricted by a predefined graph; 2) the separated stages of spectral decomposition-based way (graph learning, spectral embedding learning, and cluster assignment by k-means) cause mismatched problems and randomness; and 3) the optimization of doubly stochastic conditions is generally achieved by von Neumann successive projection (VNSP) lemma, which separates the conditions to form two subproblems for alternative optimization, converging only to a feasible solution. To solve these problems, in this article, a novel structured doubly stochastic graph-based clustering model termed SDSGC is proposed, which learns a structured doubly stochastic graph from data to directly provide cluster indicators. For optimization, a simple but effective augmented Lagrangian multiplier (ALM)-based method is proposed, which optimizes all the doubly stochastic conditions simultaneously to obtain the optimal solution. Experiments on one toy dataset and eight ad hoc noised face datasets have demonstrated that the proposed SDSGC is more robust to noise. Furthermore, a quantitative comparison of ten benchmarks has verified our SDSGC achieves better clustering performance when compared with SOTA methods. The code is available at https://github.com/NianWang-HJJGCDX/SDSGC.git.

As data collection becomes increasingly facile and descriptions of data grow more diverse, exploring heterogeneous multiview data is becoming essential. Extracting valuable insights from vast multiview datasets is profoundly meaningful which can leverage the diversity of multiple features to improve classification accuracy. As is well-known, semi-supervised learning (SSL) utilizes limited set of labeled samples to train models when addressing label scarcity. However, although the existing multiview semi-supervised algorithms can accomplish classification task, they often struggle with high complexity problem and lack interpretability, more transparent, and low-complexity approaches are worth studying. Besides, the interplay between graph structure and multiview consistency makes a deeper understanding of underlying data patterns but challenges persist in optimizing graph and ensuring scalability. In this article, we propose a fast multiview semi-supervised algorithm based on anchor graph (BGFMS), which improves the classification performance. It could significantly reduce the computational complexity by converting the label prediction of the original data into the forecast for few anchor points and avoids the additional processing procedure. Extensive experimental results on synthetic dataset and different real datasets validate the effectiveness and efficiency of our algorithm.

A challenging open problem in deep learning is the representation of tabular data. Unlike the popular domains such as image and text understanding, where the deep convolutional network is fashionable in many applications, there is still no widely used neural architecture that can effectively explore informative structure from tabular data. In addition, existing antoencoder-based nonlinear representation learning approaches that employ reconstruction loss, are incompetent to preserve discriminative information. As a step toward bridging these gaps, we propose a novel adaptive graph convolutional network (AdaGCN) for unsupervised generalizable tabular representation learning in this article. To be specific, we hypothesize that the keys to boosting the efficiency and practicality of learned representations lie in three aspects, i.e., adaptivity, unsupervised, and generalization. As a result, the adaptive graph learning module is first designed to remove the predefined rules in conventional GCN models, which can explore more local patterns on arbitrary tabular data. Moreover, our AdaGCN directly minimizes the difference between distributions of original tabular data and learned embeddings for training without any label information. Last but not least, the parametric property of AdaGCN makes the unseen data to be handled offline, which extremely expends the scope of applications. We present extensive experiments showing that AdaGCN significantly and consistently outperforms several representation learning and clustering methods on several real-world tabular datasets.

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.

Support Vector Machine (SVM) stands out as a prominent machine learning technique widely applied in practical pattern recognition tasks. It achieves binary classification by maximizing the "margin", which represents the minimum distance between instances and the decision boundary. Although many efforts have been dedicated to expanding SVM for multi-class case through strategies such as one versus one and one versus the rest, satisfactory solutions remain to be developed. In this paper, we propose a novel method for multi-class SVM that incorporates pairwise class loss considerations and maximizes the minimum margin. Adhering to this concept, we embrace a new formulation that imparts heightened flexibility to multi-class SVM. Furthermore, the correlations between the proposed method and multiple forms of multi-class SVM are analyzed. The proposed regularizer, akin to the concept of "margin", can serve as a seamless enhancement over the softmax in deep learning, providing guidance for network parameter learning. Empirical evaluations demonstrate the effectiveness and superiority of our proposed method over existing multi-classification methods. Complete version is available at https://arxiv.org/pdf/2312.06578.pdf. Code is available at https://github.com/zz-haooo/M3SVM.

In the realm of high-dimensional data analysis, the existence of outliers presents a substantial hurdle to the efficacy of feature selection methods that rely on the assumption of Gaussian distribution. To tackle this issue, we propose an outlier-robust feature selection method, ORFS, which combines robust ℓ2,1-norm minimization with group row-sparsity induced constrains to achieve both robustness and discriminative prediction capabilities. Moreover, the group row-sparsity constraints subspace learning based on ℓ2,0-norm can directly select features without parameter tuning. Finally, we introduce an iterative optimization strategy to solve NP-hard problem, and extensive experiments demonstrate the efficacy of ORFS in effectively eliminating the impact of outliers and significantly improving classification performance.

Graph Neural Networks (GNNs) have emerged as the predominant approach for analyzing graph data on the web and beyond. Contrastive learning (CL), a self-supervised paradigm, not only mitigates reliance on annotations but also has potential in performance. The hard negative sampling strategy that benefits CL in other domains proves ineffective in the context of Graph Contrastive Learning (GCL) due to the message passing mechanism. Embracing the subspace hypothesis in clustering, we propose a method towards expansive and adaptive hard negative mining, referred to as G raph contR astive leA rning via subsP ace prE serving (GRAPE ). Beyond homophily, we argue that false negatives are prevalent over an expansive range and exploring them confers benefits upon GCL. Diverging from existing neighbor-based methods, our method seeks to mine long-range hard negatives throughout subspace, where message passing is conceived as interactions between subspaces. %Empirical investigations back up this strategy. Additionally, our method adaptively scales the hard negatives set through subspace preservation during training. In practice, we develop two schemes to enhance GCL that are pluggable into existing GCL frameworks. The underlying mechanisms are analyzed and the connections to related methods are investigated. Comprehensive experiments demonstrate that our method outperforms across diverse graph datasets and remains competitive across varied application scenarios\footnoteOur code is available at https://github.com/zz-haooo/WWW24-GRAPE. .

Multi-view learning has raised more and more attention in recent years. However, traditional approaches only focus on the difference while ignoring the consistency among views. It may make some views, with the situation of data abnormality or noise, ineffective in the progress of view learning. Besides, the current datasets have become high-dimensional and large-scale gradually. Therefore, this paper proposes a novel multi-view compressed subspace learning method via low-rank tensor constraint, which incorporates the clustering progress and multi-view learning into a unified framework. First, for each view, we take the partial samples to build a small-size dictionary, which can reduce the effect of both redundancy information and computation cost greatly. Then, to find the consistency and difference among views, we impose a low-rank tensor constraint on these representations and further design an auto-weighted mechanism to learn the optimal representation. Last, due to the non-square of the learned representation, the bipartite graph has been introduced, and under the structured constraint, the clustering results can be obtained directly from this graph without any post-processing. Extensive experiments on synthetic and real-world benchmark datasets demonstrate the efficacy and efficiency of our method, especially for the views with noise or outliers.

Spectral clustering has been attracting increasing attention due to its well-defined framework and excellent performance. However, most traditional spectral clustering methods consist of two separate steps: 1) Solving a relaxed optimization problem to learn the continuous clustering labels, and 2) Rounding the continuous clustering labels into discrete ones. The clustering results of the relax-and-discretize strategy inevitably result in information loss and unsatisfactory clustering performance. Moreover, the similarity matrix constructed from original data may not be optimal for clustering since data usually have noise and redundancy. To address these problems, we propose a novel and effective algorithm to directly optimize the original spectral clustering model, called Direct Spectral Clustering (DSC). We theoretically prove that the original spectral clustering model can be solved by simultaneously learning a weighted discrete indicator matrix and a structured similarity matrix whose connected components are equal to the number of clusters. Both of them can be used to directly obtain the final clustering results without any post-processing. Further, an effective iterative optimization algorithm is exploited to solve the proposed method. Extensive experiments performed on synthetic and real-world datasets demonstrate the superiority and effectiveness of the proposed method compared to the state-of-the-art algorithms.

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.

We propose a novel discriminative feature learning method via Max-Min Ratio Analysis (MMRA) for exclusively dealing with the long-standing "worst-case class separation" problem. Existing technologies simply consider maximizing the minimal pairwise distance on all class pairs in the low-dimensional subspace, which is unable to separate overlapped classes entirely especially when the distribution of samples within same class is diverging. We propose a new criterion, i.e., Max-Min Ratio Analysis (MMRA) that focuses on maximizing the minimal ratio value of between-class and within-class scatter to extremely enlarge the separability on the overlapped pairwise classes. Furthermore, we develop two novel discriminative feature learning models for dimensionality reduction and metric learning based on our MMRA criterion. However, solving such a non-smooth non-convex max-min ratio problem is challenging. As an important theoretical contribution in this paper, we systematically derive an alternative iterative algorithm based on a general max-min ratio optimization framework to solve a general max-min ratio problem with rigorous proofs of convergence. More importantly, we also present another solver based on bisection search strategy to solve the SDP problem efficiently. To evaluate the effectiveness of proposed methods, we conduct extensive pattern classification and image retrieval experiments on several artificial datasets and real-world ScRNA-seq datasets, and experimental results demonstrate the effectiveness of proposed methods.

Dimensionality reduction (DR) targets to learn low-dimensional representations for improving discriminability of data, which is essential for many downstream machine learning tasks, such as image classification, information clustering, etc. Non-Gaussian issue as a long-standing challenge brings many obstacles to the applications of DR methods that established on Gaussian assumption. The mainstream way to address above issue is to explore the local structure of data via graph learning technique, the methods based on which however suffer from a common weakness, that is, exploring locality through pairwise points causes the optimal graph and subspace are difficult to be found, degrades the performance of downstream tasks, and also increases the computation complexity. In this article, we first propose a novel self-evolution bipartite graph (SEBG) that uses anchor points as the landmark of subclasses, and learns anchor-based rather than pairwise relationships for improving the efficiency of locality exploration. In addition, we develop an efficient local coherent structure learning (ELCS) algorithm based on SEBG, which possesses the ability of updating the edges of graph in learned subspace automatically. Finally, we also provide a multivariable iterative optimization algorithm to solve proposed problem with strict theoretical proofs. Extensive experiments have verified the superiorities of the proposed method compared to related SOTA methods in terms of performance and efficiency on several real-world benchmarks and large-scale image datasets with deep features.

Bipartite spectral graph partitioning (BSGP) method as a co-clustering method, has been widely used in document clustering, which simultaneously clusters documents and words by making full use of the duality between documents and words. It consists of two steps: 1) graph construction and 2) singular value decomposition on the bipartite graph to compute a continuous cluster assignment matrix, followed by post-processing to get the discrete solution. However, the generated graph is unstructured and fixed. It heavily relies on the quality of the graph construction. Moreover, the two-stage process may deviate from directly solving the primal problem. In order to tackle these defects, a novel bipartite graph partitioning method is proposed to learn a bipartite graph with exactly c connected components (c is the number of clusters), which can obtain clustering results directly. Furthermore, it is experimentally and theoretically proved that the solution of the proposed model is the discrete solution of the primal BSGP problem for a special situation. Experimental results on synthetic and real-world datasets exhibit the superiority of the proposed method.

Fuzzy theory, which extends precise binary logic to continuous fuzzy logic, provides an effective tool for uncertainty problems in machine learning and thus, evolved fuzzy methods such as fuzzy c-means and fuzzy graph clustering. Among them, graph-based clustering methods have become a hot spot in the field of unsupervised clustering due to their good ability to process nonlinear data. Unfortunately, they usually suffer from high time complexity and cumbersome regularization parameter tuning, so their practical applications are greatly limited. To this end, we propose an efficient graph-cut algorithm called fS2F. Based on the similarity graph between the dataset and landmark subset, fS2F transforms the membership learning of the entire dataset into a clustering problem of representative points, which greatly improves its clustering efficiency. In addition, fS2F softly constrains the cluster size in a way that does not require additional regularization parameters so that it can be widely and conveniently applied. The article also presents the optimization method for this model and demonstrates its effectiveness through experiments.

Deep fuzzy clustering employs neural networks to discover the low-dimensional embedding space of data, providing an effective solution to the clustering problem posed by high-dimensional data. Although some algorithms have achieved good results in application, the field still faces the following problems: the lack of clustering loss function limits the development of deep clustering, and most of them use the self-training strategy-based Kullback-Leibler (KL) divergence; some algorithms directly use conventional constrained clustering objective function as the loss function in deep models, and update network parameters alternately, the optimization process is cumbersome. Focusing on the issues mentioned above, this article first proposed an unconstrained fuzzy$c$-means algorithm that can be solved using gradient descent and then used it as the clustering loss function to obtain a novel deep fuzzy clustering model named unsupervised deep embedding for fuzzy clustering. The proposed model simultaneously learns the low-dimensional representation of data and performs fuzzy clustering. It updates parameters through gradient descent and backpropagation, achieving end-to-end optimization. The proposed algorithm's effectiveness and competitiveness are fully demonstrated through extensive experiments conducted on image and text datasets.

Ensemble clustering has emerged as a powerful framework for analyzing heterogeneous and complex data. Despite the abundance of existing schemes, co-association matrix-based methods remain the mainstream approach. However, focusing solely on pairwise correlations falls short of fully capturing the intricate cluster relationships. Moreover, despite its potential, ensemble clustering has yet to effectively leverage the powerful representation capabilities of neural networks. To address these limitations, we propose a deep ensemble clustering method called Ensemble Clustering with Attentional Representation (ECAR). Our method considers the results of base partition as groups with related information to explore higher-order fusion information. ECAR captures the importance of each sample's association with its related group by employing an attentional network, and encodes this information into a low-dimensional representation. The attentional network is trained by jointly optimizing the clustering loss from soft assignments learned from the embeddings and the reconstruction loss from the weighted graph generated from ensemble clustering. During training, the weights of base partitions are adaptively refined to promote diversity and consistency while reducing the impact of low-quality and redundant base partitions. Extensive experimental results on real-world datasets demonstrate the substantial improvement of our method over existing baseline ensemble clustering methods and deep clustering methods.

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.

Feature selection is one of the important topics of machine learning, and it has a wide range of applications in data preprocessing. At present, feature selection based on$\ell _{2,1}$-norm regularization is a relatively mature method, but it is not enough to maximize the sparsity and parameter-tuning leads to increased costs. Later scholars found that the$\ell _{2,0}$-norm constraint is more conductive to feature selection, but it is difficult to solve and lacks convergence guarantees. To address these problems, we creatively propose a novel Outliers Robust Unsupervised Feature Selection for structured sparse subspace (ORUFS), which utilizes$\ell _{2,0}$-norm constraint to learn a structured sparse subspace and avoid tuning the regularization parameter. Moreover, by adding binary weights, outliers are directly eliminated and the robustness of model is improved. More importantly, a Re-Weighted (RW) algorithm is exploited to solve our$\ell _{p}$-norm problem. For the NP-hard problem of$\ell _{2,0}$-norm constraint, we develop an effective iterative optimization algorithm with strict convergence guarantees and closed-form solution. Subsequently, we provide theoretical analysis about convergence and computational complexity. Experimental results on real-world datasets illustrate that our method is superior to the state-of-the-art methods in clustering and anomaly detection tasks.

Feature selection has achieved unprecedented success in obtaining sparse discriminative features. However, the existing methods almost use the$\ell _{2,p}$-norm constraint on transformation matrix to obtain sparse features, which introduces extra parameters and cannot obtain the features directly. In addition, existing algorithms only focused on the global structure and ignored the local structure, leading to poor performance when solving data with non-Gaussian distributions which a single center point cannot describe precisely. Based on above considerations, we propose a supervised feature selection via multi-center and local structure learning. We further introduce trace ratio criterion into our model in favor of improving the discriminant of features selected. In order to address the overlap problem, we use multiple center points to match the distribution of data and construct a$k$-Nearest Neighbor graph to explore the local structure of the data. In addition, we also propose an efficient method to optimize the transformation matrix with the$\ell _{2,0}$-norm constraint and can directly obtain the sparse features. We evaluate our method on Toy datasets and several real-world datasets, show improvement over state-of-the-art feature selection methods, and demonstrate the effectiveness of our model in dealing with non-Gaussian distributed data problems.

In recent years, graph-based multiview clustering methods have become a research hotspot in the clustering field. However, most existing methods lack consideration of cluster balance in their results. In fact, cluster balance is crucial in many real-world scenarios. Additionally, graph-based multiview clustering methods often suffer from high time consumption and cannot handle large-scale datasets. To address these issues, this paper proposes a novel graph-based multiview clustering method. The method is built upon the bipartite graph. Specifically, it employs a label propagation mechanism to update the smaller anchor label matrix rather than the sample label matrix, significantly reducing the computational cost. The introduced balance constraint in the proposed model contributes to achieving balanced clustering results. The entire clustering model combines information from multiple views through graph fusion. The joint graph and view weight parameters in the model are obtained through task-driven self-supervised learning. Moreover, the model can directly obtain clustering results without the need for the two-stage processing typically used in general spectral clustering. Finally, extensive experiments on toy datasets and real-world datasets are conducted to validate the superiority of the proposed method in terms of clustering performance, clustering balance, and time expenditure.

Principal component analysis (PCA) is one of the most successful unsupervised subspace learning methods and has been used in many practical applications. To deal with the outliers in real-world data, robust principal analysis models based on various measure are proposed. However, conventional PCA models can only transform features to unknown subspace for dimensionality reduction and cannot perform features’ selection task. In this article, we propose a novel robust PCA (RPCA) model to mitigate the impact of outliers and conduct feature selection, simultaneously. First, we adopt$\sigma $-norm as reconstruction error (RE), which plays an important role in robust reconstruction. Second, to conduct feature selection task, we apply$\ell _{2,0}$-norm constraint to subspace projection. Furthermore, an efficient iterative optimization algorithm is proposed to solve the objective function with nonconvex and nonsmooth constraint. Extensive experiments conducted on several real-world datasets demonstrate the effectiveness and superiority of the proposed feature selection model.

In the unsupervised feature selection method based on spectral analysis, constructing a similarity matrix is a very important part. In existing methods, the linear low-dimensional projection used in the process of constructing the similarity matrix is too hard, it is very challenging to construct a reliable similarity matrix. To this end, we propose a method to construct a flexible optimal graph. Based on this, we propose an unsupervised feature selection method named unsupervised feature selection with flexible optimal graph and$\ell _{2,1}$-norm regularization (FOG-R). Unlike other methods that use linear projection to approximate the low-dimensional manifold of the original data when constructing a similarity matrix, FOG-R can learn a flexible optimal graph, and by combining flexible optimal graph learning and feature selection into a unified framework to get an adaptive similarity matrix. In addition, an iterative algorithm with a strict convergence proof is proposed to solve FOG-R.$\ell _{2,1}$-norm regularization will introduce an additional regularization parameter, which will cause parameter-tuning trouble. Therefore, we propose another unsupervised feature selection method, that is, unsupervised feature selection with a flexible optimal graph and$\ell _{2,0}$-norm constraint (FOG-C), which can avoid tuning additional parameters and obtain a more sparse projection matrix. Most critically, we propose an effective iterative algorithm that can solve FOG-C globally with strict convergence proof. Comparative experiments conducted on 12 public datasets show that FOG-R and FOG-C perform better than the other nine state-of-the-art unsupervised feature selection algorithms.

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.

Spectral clustering (SC) has been widely used in many applications and shows excellent performance. Its high computational cost limits its applications; many strategies including the anchor technique can partly alleviate the high computational cost problem. However, early methods ignore the fact that SC usually involves two stages: relaxation and postprocessing, i.e., it relaxes the discrete constraints to continuous constraints, and then conducts the postprocessing to get the discrete solution, which is time-consuming and deviates from directly solving the primal problem. In this article, we first adopt the bipartite graph strategy to reduce the time complexity of SC, and then an improved coordinate descent (CD) method is proposed to solve the primal problem directly without singular value decomposition (SVD) and postprocessing, i.e., directly solving the primal problem not approximately solving. Experiments on various real-world benchmark datasets show that the proposed method can get better solutions faster with better clustering performance than traditional optimization methods. Furthermore, it can jump out of local minima of traditional methods and continue to obtain better local solutions. Moreover, compared with other clustering methods, it also shows its superiority.

-norm is used as distance metric. Recently, many scholars have devoted themselves to solving this difficulty. They learn the projection matrix from minimum reconstruction error or maximum projection variance as the starting point, which leads them to ignore a serious problem, that is, the original PCA learns the projection matrix by minimizing the reconstruction error and maximizing the projection variance simultaneously, but they only consider one of them, which imposes various limitations on the performance of model. To solve this problem, we propose a novel robust principal component analysis via joint reconstruction and projection, namely, RPCA-RP, which combines reconstruction error and projection variance to fully mine the potential information of data. Furthermore, we carefully design a discrete weight for model to implicitly distinguish between normal data and outliers, so as to easily remove outliers and improve the robustness of method. In addition, we also unexpectedly discovered that our method has anomaly detection capabilities. Subsequently, an effective iterative algorithm is explored to solve this problem and perform related theoretical analysis. Extensive experimental results on several real-world datasets and RGB large-scale dataset demonstrate the superiority of our method.

The success of existing unsupervised feature selection (UFS) methods heavily relies on the assumption that the intrinsic relationships among original high-dimensional (HD) data samples exist in the discriminative low-dimension (LD) subspace. However, previous UFS methods commonly construct pairwise graphs and employ$\ell_{2,1}$-norm regularization to severally preserve the local structure and calculate the score of features, which is computationally complex and easy to get stuck into local optimum, so that those approaches cannot be applied in dealing with large-scale datasets in practice. To overcome this challenge, we propose a novel UFS method, in which a novel anchor graph embedding paradigm is designed to extract the local neighborhood relationships among data samples by reducing the computational complexity of graph construction to be linear in the number of data. Moreover, to improve the optimality of selected features as well as the performance of downstream tasks, we propose a discrete feature scoring mechanism, which imposes orthogonal$\ell_{2,0}$-norm constraints on learned projections, in order to enhance the distinction of feature scores as well as reduce the probability of falling into local optimum. In addition, solving the proposed nonconvex and nonsmooth NP-hard problem is challenging, and we present an efficient optimization algorithm to address it and acquire a closed-form solution of the transformation matrix. Extensive experiments demonstrate the effectiveness and efficiency of the proposed UFS by comparison with several state-of-the-art approaches to clustering and image segmentation tasks.

Recently, graph-based multi-view clustering (GMC) has attracted extensive attention from researchers, in which multi-view clustering based on structured graph learning (SGL) can be considered as one of the most interesting branches, achieving promising performance. However, most of the existing SGL methods suffer from sparse graphs lacking useful information, which normally appears in practice. To alleviate this problem, we propose a novel multi-view and multi-order SGL ( [Formula: see text]SGL) model which introduces multiple different orders (multi-order) graphs into the SGL procedure reasonably. To be more specific, [Formula: see text]SGL designs a two-layer weighted-learning mechanism, in which the first layer truncatedly selects part of views in different orders to retain the most useful information, and the second layer assigns smooth weights into retained multi-order graphs to fuse them attentively. Moreover, an iterative optimization algorithm is derived to solve the optimization problem involved in [Formula: see text]SGL, and the corresponding theoretical analyses are provided. In experiments, extensive empirical results demonstrate that the proposed [Formula: see text]SGL model achieves the state-of-the-art performance in several benchmarks.

In this article, we propose a new unsupervised feature selection method named pseudo-label guided structural discriminative subspace learning (PSDSL). Unlike the previous methods that perform the two stages independently, it introduces the construction of probability graph into the feature selection learning process as a unified general framework, and therefore the probability graph can be learned adaptively. Moreover, we design a pseudo-label guided learning mechanism, and combine the graph-based method and the idea of maximizing the between-class scatter matrix with the trace ratio to construct an objective function that can improve the discrimination of the selected features. Besides, the main existing strategies of selecting features are to employ -norm for feature selection, but this faces the challenges of sparsity limitations and parameter tuning. For addressing this issue, we employ the -norm constraint on the learned subspace to ensure the row sparsity of the model and make the selected feature more stable. Effective optimization strategy is given to solve such NP-hard problem with the determination of parameters and complexity analysis in theory. Ultimately, extensive experiments conducted on nine real-world datasets and three biological ScRNA-seq genes datasets verify the effectiveness of the proposed method on the data clustering downstream task.

The existing multiview clustering models learn a consistent low-dimensional embedding either from multiple feature matrices or multiple similarity matrices, which ignores the interaction between the two procedures and limits the improvement of clustering performance on multiview data. To address this issue, a bidirectional probabilistic subspaces approximation (BPSA) model is developed in this article to learn a consistently orthogonal embedding from multiple feature matrices and multiple similarity matrices simultaneously via the disturbed probabilistic subspace modeling and approximation. A skillful bidirectional fusion strategy is designed to guarantee the parameter-free property of the BPSA model. Two adaptively weighted learning mechanisms are introduced to ensure the inconsistencies among multiple views and the inconsistencies between bidirectional learning processes. To solve the optimization problem involved in the BPSA model, an iterative solver is derived, and a rigorous convergence guarantee is provided. Extensive experimental results on both toy and real-world datasets demonstrate that our BPSA model achieves state-of-the-art performance even if it is parameter-free.

Clustering aims to make data points in the same group have higher similarity or make data points in different groups have lower similarity. Therefore, we propose three novel fast clustering models motivated by maximizing within-class similarity, which can obtain more instinct clustering structure of data. Different from traditional clustering methods, we divide all n samples into m classes by the pseudo label propagation algorithm first, and then m classes are merged to c classes ( ) by the proposed three co-clustering models, where c is the real number of categories. On the one hand, dividing all samples into more subclasses first can preserve more local information. On the other hand, proposed three co-clustering models are motivated by the thought of maximizing the sum of within-class similarity, which can utilize the dual information between rows and columns. Besides, the proposed pseudo label propagation algorithm can be a new method to construct anchor graphs with linear time complexity. A series of experiments are conducted on both synthetic and real-world datasets and the experimental results show the superior performance of three models. It is worth noting that for the proposed models, FMAWS2 is the generalization of FMAWS1 and FMAWS3 is the generalization of other two.

Neighborhood reconstruction methods have been widely applied to feature engineering. Existing reconstruction-based discriminant analysis methods normally project high-dimensional data into a low-dimensional space while preserving the reconstruction relationships among samples. However, there are three limitations: 1) the reconstruction coefficients are learned based on the collaborative representation of all sample pairs, which requires the training time to be the cube of the number of samples; 2) these coefficients are learned in the original space, ignoring the interference of the noise and redundant features; and 3) there is a reconstruction relationship between heterogeneous samples; this will enlarge the similarity of heterogeneous samples in the subspace. In this article, we propose a fast and adaptive discriminant neighborhood projection model to tackle the above drawbacks. First, the local manifold structure is captured by bipartite graphs in which each sample is reconstructed by anchor points derived from the same class as that sample; this can avoid the reconstruction between heterogeneous samples. Second, the number of anchor points is far less than the number of samples; this strategy can reduce the time complexity substantially. Third, anchor points and reconstruction coefficients of bipartite graphs are updated adaptively in the process of dimensionality reduction, which can enhance the quality of bipartite graphs and extract discriminative features simultaneously. An iterative algorithm is designed to solve this model. Extensive results on toy data and benchmark datasets show the effectiveness and superiority of our model.

Graph clustering based on graph contrastive learning (GCL) is one of the dominant paradigms in the current graph clustering research field. However, those GCL-based methods often yield false negative samples, which can distort the learned representations and limit clustering performance. In order to alleviate this issue, we propose the idea of maintaining mutual information (MI) between the representations and the inputs to mitigate the loss of semantic information of false negative samples. We demonstrate the validity of this proposal through relevant experiments. Since maximizing MI can be approximately replaced by minimizing reconstruction error, we further propose a graph clustering method based on GCL penalized by reconstruction error, in which our carefully designed reconstruction decoder, as well as reconstruction error term, improve the clustering performance. In addition, we use a pseudo-label-guided strategy to improve the GCL process and further alleviate the problem of false negative samples. Our experiment results demonstrate the superiority and great potential of our proposed graph clustering method compared with state-of-the-art algorithms.

Sparse learning based feature selection has been widely investigated in recent years. In this study, we focus on the l2,0-norm based feature selection, which is effective for exact top-k feature selection but challenging to optimize. To solve the general l2,0-norm constrained problems, we novelly develop a parameter-free optimization framework based on the coordinate descend (CD) method, termed CD-LSR. Specifically, we devise a skillful conversion from the original problem to solving one continuous matrix and one discrete selection matrix. Then the nontrivial l2,0-norm constraint can be solved efficiently by solving the selection matrix with CD method. We impose the l2,0-norm on a vanilla least square regression (LSR) model for feature selection and optimize it with CD-LSR. Extensive experiments exhibit the efficiency of CD-LSR, as well as the discrimination ability of l2,0-norm to identify informative features. More importantly, the versatility of CD-LSR facilitates the applications of the l2,0-norm in more sophisticated models. Based on the competitive performance of l2,0-norm on the baseline LSR model, the satisfactory performance of its applications is reasonably expected. The source MATLAB code are available at: https://github.com/solerxl/Code_For_AAAI_2023.

Most of the existing multi-view clustering algorithms are performed in the original feature space, and their performance in heavily reliant on the quality of the raw data. Besides, some two-stage strategies cannot achieve ideal results due to the absence of capturing the correlation between views. In view of this, we propose Multi-View K-means with Laplacian Embedding (MVKLE), which is capable of clustering multi-view data in the learned embedding space. Specifically, we employ local structure-preserving dimensionality reduction to obtain the underlying representation of each view, and obtain the clustering results directly through an effective optimization formulation. Experiments on several common multi-view datasets demonstrate the superiority of the proposed method.

Feature selection is widely used in multimedia applications to determine informative features from high-dimensional data. Due to the explosive growth of the data size and the expensive cost of obtaining labeled data, it is increasingly demanded to utilize both labeled and unlabeled data for feature selection. In this paper, we introduce the l2,0-norm in semi-supervised feature selection, which is able to select exact k informative features. Due to the non-convexity of l2,0-norm, we further devise an efficient coordinate-descent-based algorithm to solve the l2,0-norm constraint, which facilitates the application of l2,0-norm to more complex applications, including but not limited to the proposed model in this study. We experimentally verify the effectiveness of the proposed l2,0-norm-based semi-supervised method and the efficiency of the proposed optimization algorithm.

With the proliferation of multimedia applications, data is frequently derived from multiple sources, leading to the accelerated advancement of multi-view clustering (MVC) methods. In this paper, we propose a novel MVC method, termed GLSEF, to handle the inconsistency existing in multiple spectral embeddings. To this end, GLSEF contains a two-level learning mechanism. Specifically, on the global level, GLSEF considers the diversity of features and selectively assigns smooth weights to partial more discriminative features that are conducive to clustering. On the local level, GLSEF resorts to the Grassmann manifold to maintain spatial and topological information and local structure in each view, thereby enhancing its suitability and accuracy for clustering. Moreover, unlike most previous methods that learn a low-dimension embedding and perform the k-means algorithm to obtain the final cluster labels, GLSEF directly acquires the discrete indicator matrix to prevent potential information loss during post-processing. To address the optimization involved in GLSEF, we present an efficient alternating optimization algorithm accompanied by convergence and time complexity analyses. Extensive empirical results on nine real-world datasets demonstrate the effectiveness and efficiency of GLSEF compared to existing state-of-the-art MVC methods.

Feature selection (FS) plays an important role in machine learning, which extracts important features and accelerates the learning process. In this paper, we propose a deep FS method that simultaneously conducts feature selection and differentiable $ k $-NN graph learning based on the Dirichlet Energy. The Dirichlet Energy identifies important features by measuring their smoothness on the graph structure, and facilitates the learning of a new graph that reflects the inherent structure in new feature subspace. We employ Optimal Transport theory to address the non-differentiability issue of learning $ k $-NN graphs in neural networks, which theoretically makes our method applicable to other graph neural networks for dynamic graph learning. Furthermore, the proposed framework is interpretable, since all modules are designed algorithmically. We validate the effectiveness of our model with extensive experiments on both synthetic and real-world datasets.

Multi-view clustering aims to discover common patterns from multi-source data, whose generality is remarkable. Compared with traditional methods, deep learning methods are data-driven and have a larger search space for solutions, which may find a better solution to the problem. In addition, more considerations can be introduced by loss functions, so deep models are highly reusable. However, compared with deep learning methods, traditional methods have better interpretability, whose optimization is relatively stable. In this paper, we propose a multi-view spectral clustering model, combining the advantages of traditional methods and deep learning methods. Specifically, we start with the objective function of traditional spectral clustering, perform multi-view extension, and then obtain the traditional optimization process. By partially parameterizing this process, we further design corresponding differentiable modules, and finally construct a complete network structure. The model is interpretable and extensible to a certain extent. Experiments show that the model performs better than other multi-view clustering algorithms, and its semi-supervised classification extension also has excellent performance compared to other algorithms. Further experiments also show the stability and fewer iterations of the model training.

The principal subspace estimation is directly connected to dimension reduction and is important when there is more than one principal component of interest. In this article, we introduce two new algorithms to solve the feature-sparsity constrained PCA problem (FSPCA) for the principal subspace estimation task, which performs feature selection and PCA simultaneously. Existing optimization methods for FSPCA require data distribution assumptions and are lack of global convergence guarantee. Though the general FSPCA problem is NP-hard, we show that, for a low-rank covariance, FSPCA can be solved globally (Algorithm 1). Then, we propose another strategy (Algorithm 2) to solve FSPCA for the general covariance by iteratively building a carefully designed proxy. We prove (data-dependent) approximation bound and regular stationary convergence guarantees for the new algorithms. For the spectrum of covariance with exponential/Zipf's distribution, we provide exponential/posynomial approximation bounds. Constructive examples and numerical results are provided to demonstrate the tightness of our results. Experimental results show the promising performance and efficiency of the new algorithms compared with the state-of-the-arts on both synthetic and real-world datasets.

Although lots of clustering models have been proposed recently, k-means and the family of spectral clustering methods are both still drawing a lot of attention due to their simplicity and efficacy. We first reviewed the unified framework of k-means and graph cut models, and then proposed a clustering method called k-sums where a k-nearest neighbor ( k-NN) graph is adopted. The main idea of k-sums is to minimize directly the sum of the distances between points in the same cluster. To deal with the situation where the graph is unavailable, we proposed k-sums-x that takes features as input. The computational and memory overhead of k-sums are both O(nk), indicating that it can scale linearly w.r.t. the number of objects to group. Moreover, the costs of computational and memory are Irrelevant to the product of the number of points and clusters. The computational and memory complexity of k-sums-x are both linear w.r.t. the number of points. To validate the advantage of k-sums and k-sums-x on facial datasets, extensive experiments have been conducted on 10 synthetic datasets and 17 benchmark datasets. While having a low time complexity, the performance of k-sums is comparable with several state-of-the-art clustering methods.

Spectral Clustering (SC) has been the main subject of intensive research due to its remarkable clustering performance. Despite its successes, most existing SC methods suffer from several critical issues. First, they typically involve two independent stages, i.e., learning the continuous relaxation matrix followed by the discretization of the cluster indicator matrix. This two-stage approach can result in suboptimal solutions that negatively impact the clustering performance. Second, these methods are hard to maintain the balance property of clusters inherent in many real-world data, which restricts their practical applicability. Finally, these methods are computationally expensive and hence unable to handle large-scale datasets. In light of these limitations, we present a novel Discrete and Balanced Spectral Clustering with Scalability (DBSC) model that integrates the learning the continuous relaxation matrix and the discrete cluster indicator matrix into a single step. Moreover, the proposed model also maintains the size of each cluster approximately equal, thereby achieving soft-balanced clustering. What's more, the DBSC model incorporates an anchor-based strategy to improve its scalability to large-scale datasets. The experimental results demonstrate that our proposed model outperforms existing methods in terms of both clustering performance and balance performance. Specifically, the clustering accuracy of DBSC on CMUPIE data achieved a 17.93% improvement compared with that of the SOTA methods (LABIN, EBSC, etc.).

Clustering is used widely in various kinds of signal processing tasks, in which$k$-means is warmly welcomed by the researchers due to its efficiency and simplicity. Nevertheless, it fails to process non-spherical clusters which are common data distribution. As a variant of$k$-means, kernel$k$-means uses a kernel trick to map the raw data into a feature space to better describe the data with improved clustering performance. But the algorithms still have a lot of shortcomings in the application of signal processing: 1) Not all features contain a wealth of useful information, so all dimensions of features cannot be treated equally; 2) The use of high dimensional features for clustering exceedingly increases computational complexity with negligible improvement of clustering performance. To solve the problems, we propose a self-weighted Euler$k$-means (SWEKM) model, which can adaptively identify the importance of different features, perfectly integrating clustering and feature selection into a joint framework. Moreover, Euler kernel is adopted in SWEKM, which is capable of suppressing the interference of noise points and outliers with comparable computational complexity. Extensive experiments on datasets from the UCI database show that the SWEKM outperforms the state-of-the-art kernel$k$-means for clustering-based signal processing tasks.

In this article, we focus on utilizing the idea of co-clustering algorithms to address the subspace clustering problem. In recent years, co-clustering methods have been developed greatly with many important applications, such as document clustering and gene expression analysis. Different from the traditional graph-based methods, co-clustering can utilize the bipartite graph to extract the duality relationship between samples and features. It means that the bipartite graph can obtain more information than other traditional graph methods. Therefore, we proposed a novel method to handle the subspace clustering problem by combining dictionary learning with a bipartite graph under the constraint of the (normalized) Laplacian rank. Besides, to avoid the effect of redundant information hiding in the data, the original data matrix is not used as the static dictionary in our model. By updating the dictionary matrix under the sparse constraint, we can obtain a better coefficient matrix to construct the bipartite graph. Based on Theorem 2 and Lemma 1, we further speed up our algorithm. Experimental results on both synthetic and benchmark datasets demonstrate the superior effectiveness and stability of our model.

Linear discriminant analysis (LDA) aims to find a low-dimensional space in which data points in the same class are to be close to each other while keeping data points from different classes apart. To improve the robustness of LDA to non-Gaussian distribution data, most existing discriminant analysis methods extend LDA by approximating the underlying manifold of data. However, these methods suffer from the following problems: 1) local affinity or reconstruction coefficients are learned on the basis of the relationships of all data pairs, which would lead to a sharp increase in the amount of computation and 2) they learn the manifold information in the original space, ignoring the interference of the noise and redundant features. Motivated by these challenges, this article represents a novel discriminant analysis model, called fast and adaptive locality discriminant analysis (FALDA), to improve the efficiency and robustness. First, with the anchor-based strategy, a bipartite graph of each class is constructed to characterize the local structure of data. Since the number of anchor points is far less than that of data points, learning of fuzzy membership relationships between data points and anchor points within each class can save training time. Second, a maximum entropy regularization is introduced to control the uniformity of the weights of graphs and avoid the trivial solution. Third, the above relationships are updated adaptively in the process of dimensionality reduction, which can suppress the interference of the noise and redundant features. Fourth, the whitening constraint is imposed on the projection matrix to remove the relevance between features and restrict the total scatter of data in the subspace. Last but not the least, data with complex distribution can be explicitly divided into sub-blocks according to the learned anchor points (or subclass center points). We test our proposed method on synthetic data, benchmark datasets, and imbalanced datasets. Promising experimental results demonstrate the success of this novel model.

Spectral clustering have attracted more and more attention due to their well-defined mathematical frameworks and superior performance. However, there still exist two limitations to be solved: 1) most spectral clustering methods consist of two independent stages, which may cause unpredictable deviation of obtained clustering results from the genuine ones and lead to severe information loss and performance degradation; 2) spectral clustering methods employ the hard clustering mode, which lacks interpretability for data points in the boundary area belonging to multiple clusters. To simultaneously address these challenging issues for spectral clustering, we propose a graph-based soft-balanced fuzzy clustering (GBFC) model. Specifically, we explicitly preserve the nonnegative property of the clustering indicator matrix to enhance the interpretability of clustering results. Moreover, row normalization is imposed on the cluster indicator matrix to show the membership of each data point to different clusters. Additionally, a novel balanced constraint is designed to regularize the clustering results and constrain the size of clusters. We can directly obtain the clustering assignments without any post-processing, and the limitations of the previous two-stage clustering framework can be effectively addressed. Extensive experiments performed on both synthetic datasets and real world datasets demonstrate the superiority and effectiveness of the proposed algorithm compared with several state-of-the-art methods.

Since obtaining data labels is a time-consuming and laborious task, unsupervised feature selection has become a popular feature selection technique. However, the current unsupervised feature selection methods are facing three challenges: (1) they rely on a fixed similarity matrix derived from the original data, which will affect their performance; (2) due to the limitation of sparsity, they can only obtain sub-optimal solutions; (3) they have high computational complexity and cannot handle large-scale data. To solve this dilemma, we propose a fast unsupervised feature selection algorithm with bipartite graph and 2;0-norm constraint (BGCFS). We use the original data and the selected anchors to construct an adaptive bipartite graph in the subspace, and apply the l2,0-norm constraint to the projection matrix for feature selection. In this way, we can update the adaptive bipartite graph and the projection matrix simultaneously, and we can get the feature subset directly, without sorting the features. In addition, we propose an iterative algorithm that can solve the proposed problem globally to obtain a closed-form solution, and we provide a strict proof of convergence for it. Experiments on eight real data sets with different scales show that our method can select more valuable feature subsets more quickly

Fuzzy clustering algorithms have been widely used to reveal the possible hidden structure of data. However, with the increasing of data amount, large scale data has brought genuine challenges for fuzzy clustering. Most fuzzy clustering algorithms suffer from the long time-consumption problem since a large amount of distance calculations are involved to update the solution per iteration. To address this problem, we introduce the popular anchor graph technique into fuzzy clustering and propose a scalable fuzzy clustering algorithm referred to as Scalable Fuzzy Clustering with Anchor Graph (SFCAG). The main characteristic of SFCAG is that it addresses the scalability issue plaguing fuzzy clustering from two perspectives: anchor graph construction and membership matrix learning. Specifically, we select a small number of anchors and construct a sparse anchor graph, which is beneficial to reduce the computational complexity. We then formulate a trace ratio model, which is parameter-free, to learn the membership matrix of anchors to speed up the clustering procedure. In addition, the proposed method enjoys linear time complexity with the data size. Extensive experiments performed on both synthetic and real world datasets demonstrate the superiority (both effectiveness and scalability) of the proposed method over some representative large scale clustering methods.

K-means is one of the most simple and popular clustering algorithms, which implemented as a standard clustering method in most of machine learning researches. The goal of K-means clustering is finding a set of cluster centers and minimizing the sum of squared distances between each sample and its nearest clustering center. In this paper, we proposed a novel K-means clustering algorithm, which reformulate the classical K-Means objective function as a trace maximization problem and then replace it with a new formulation. The proposed algorithm does not need to calculate the cluster centers in each iteration and requires fewer additional intermediate variables during the optimization process. In addition, we proposed an efficient iterative re-weighted algorithm to solve the involved optimization problem and provided the corresponding convergence analysis. The proposed algorithm keeps a consistent computational complexity as Lloyd's algorithm,$\mathcal {O}(ndk)$, but shows a faster convergence rate in experiments. Extensive experimental results on real world benchmark datasets show the effectiveness and efficiency of the proposed algorithm.

Multi-view clustering attracts considerable attention due to its effectiveness in unsupervised learning. However, previous multi-view spectral clustering methods include two separated steps: 1) Obtaining a spectral embedding; 2) Performing classical clustering methods. Although these methods have achieved promising performance, there is still some limitations. First, in computing spectral embedding, multi-view spectral clustering approaches exist high computational complexity since they usually need eigenvalue decomposition on laplacian matrix L. Its computational complexity is O(n3) where n is the number of samples; Second, in constructing similarity matrices, previous methods need to compute similarity between any two samples; Third, the two-stage approach only can obtain sub-optimal solution; Fourth, treating equally all views is unreasonable. To address these issues, we propose a Fast Multi-view Clustering via Prototype Graph (FMVPG) method. Specifically, the prototype graph is firstly constructed, and then simultaneously perform spectral embedding to obtain the real matrix and spectral rotation to get the indicator matrix. In addition, the Alternating Direction Method of Multipliers (ADMM) is used to solve the joint optimization problem. Further, we conduct extensive experiments to evaluate the proposed FMVPG approach. These experimental results show the comparable or even better clustering performance than the state-of-the-art approaches.

Spectral clustering is a vital clustering method and has been widely applied for data analysis and pattern reorganization. A routine of solving spectral clustering problem consists of two successive stages: (1) solving a relaxed continuous optimization problem to obtain a real-valued indicator solution (2) transform the real-valued indicator into a 0-1 discrete one as the final clustering result. However, we may lose the optimal solution with such a two-stage process. Besides, the spectral clustering has a high time complexity which limits the analysis of large-scale data. To alleviate these problems, this paper proposes an efficient spectral clustering framework that computes spectral embedding and improved spectral rotation simultaneously (SE-ISR). In addition, we also provide a parameter-free method (SE-ISR-PF) to automatically choose the trade-off parameter. Furthermore, with an anchor-based similarity matrix construction, it is scalable to large-scale data. An effective algorithm with a strict convergence proof is provided to solve the corresponding optimization problem. Experimental results on several benchmark datasets demonstrate that the proposed algorithm outperforms the state-of-art methods.

In recent decades, unsupervised feature selection methods have become increasingly popular. Nevertheless, most of the existing unsupervised feature selection methods suffer from two major problems that lead to suboptimal solutions. Many methods impose a hard linear projection constraint on original data, which is overly strict in nature and not suitable for dealing with data sampled from nonlinear manifolds. Second, most existing methods usel2,p-norm (02S and SF2SOG, which can simultaneously learn optimal flexible projections and obtain an orthogonal sparse projection to directly select discriminative features by applyingl2,0-norm constraint. Moreover, we propose to explore the local structure of flexible embedding through preserving the manifold structure of original data and adaptively constructing an optimal graph in subspace. Thirdly, the novel iterative optimization algorithms are presented to solve objective functions guaranteeing convergence theoretically. Various evaluation experiments on synthetic and real-world datasets demonstrate the effectiveness and superiority of our proposed methods.

Graph-based semi-supervised learning, which further utilizes graph structure behind samples for boosting semi-supervised learning, gains convincing results in several machine learning tasks. Nevertheless, existing graph-based methods have shortcomings from two aspects. On the one hand, many of them concentrate on improving label propagation over the constructed graph through time-saving methods, e.g. path searching, without giving insights on constructing a proper graph accommodated to samples. On the other hand, some models are only devoted to constructing the appropriate graph resulting in a two-stage procedure, which may incur a suboptimal scenario. In this paper, we develop a joint learning method that considers both bipartite graph construction and label propagation simultaneously. With this configuration, the constructed graph is constantly adjusted by the smoothness term in the objective as the algorithm proceeds. The time complexity of our method gets significant improvement compared with traditional graph-based methods, and the experimental results on one synthetic dataset and several real-world benchmarks demonstrate the effectiveness and scalability of our proposed method.

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.

Considering many graph clustering methods are with quadratic or cubic time complexity and need post-processing to obtain the discrete solution. Combining with the anchor graph, we study a novel graph clustering model called Rank-$r$Discrete Matrix Factorization (DMF-RR), which is linear time complexity, and motivated by nonnegative matrix factorization (NMF). Instead of constraining the factor matrices of NMF to be nonnegative as many existed methods, we constrain them to indicator matrices. Thus, DMF-RR can obtain the discrete solution by directly solving the original problem without post-processing. Furthermore, considering the greater similarity between samples of the same category, an anchor graph is constructed as an input to capture essential clustering structure by utilizing the duality information between samples and anchors. Subsequently, an efficient and simple algorithm is proposed due to the nature of indicator matrices. Extensive experiments performed on synthetic and real-world datasets demonstrate the superiority of DMF-RR.

Fuzzy K-Means (FKM) clustering regards each cluster as a fuzzy set and assigns each sample to multiple clusters with a certain degree of membership. However, conventional FKM methods perform clustering on original data directly where the intrinsic structure of data may be corrupted by the noise. According, the performance of these methods would be challenged. In this paper, we present a novel fuzzy K-Means clustering model to conduct clustering tasks on the flexible manifold. Technically, we perform fuzzy clustering based on the shrunk patterns which have desired manifold structure. The shrunk patterns can be viewed as an approximation to the original data; and a penalty term is employed to measure the mismatch between them. Moreover, we integrate the learning of shrunk patterns and the learning of membership degree between shrunk patterns and clusters into a unified framework. Furthermore, we extend the proposed model for projected FKM clustering to find a suitable subspace to fit the non-linear manifold structure of data, reduce the interference of the noise and redundant features and gather homogeneous samples together simultaneously. Two alternating iterative algorithms are derived to solve these two models, respectively. Extensive experimental results demonstrate the feasibility and effectiveness of our proposed clustering algorithms.

Due to the difficulty of annotating large amounts of training data, directly learning the association of sound and its makers in natural videos is a challenging task for machines. In this paper, we present a novel audiovisual model that introduces a soft-clustering module as the audio and visual content detector, and regards the pervasive property of audiovisual concurrency as the latent supervision for inferring the correlation among detected contents. Furthermore, we discover for the first time that the complexity of data has an impact on the training efficiency and subsequent performance of audiovisual model, i.e., more complex data brings more obstacles to the model training, and degrades the performance of downstream audiovisual tasks. To address the issue of audiovisual learning, we propose a novel heterogeneous audiovisual scene analysis module that trains the model from simple to complex scene. We show that such ordered learning procedure rewards the model the merits of easy training and fast convergence. Meanwhile, our audiovisual model can also provide effective unimodal representation and cross-modal alignment performance. We further deploy the well-trained model into practical audiovisual sound localization and separation tasks. We show that our localization model significantly outperforms existing methods, based on which we show comparable performance in sound separation task by comparison to several related SOTA audiovisual learning methods without referring external visualsupervision.

Graph-based multi-view clustering method has attracted considerable attention in multi-media data analyse community due to its good clustering performance and efficiency in characterizing the relationship between data. But the existing graph-based clustering methods still have many shortcomings. Firstly, they have high computational complexity due to the eigenvalue decomposition. Secondly, the complementary information and spatial structure embedded in different views can affect the clustering performance. However, some existing graph-based clustering methods do not consider these two points. In this article, we use the anchor graphs of different views as input, which effectively reduces the computational complexity. And then we explicitly consider the complementary information and spatial structure between anchor graphs of different views by minimizing the tensor Schatten$p$-norm, aiming to achieve a better tensor with low-rank approximation. Finally, we learn the view-consensus anchor graph with connectivity constraints, which can directly indicate clusters by self-weighted strategy. An efficient alternating algorithm is then derived to optimize the proposed multi-view special clustering model. Furthermore, the constructed sequence was proved to converge to the stationary KKT point. Experiments show that our proposed method not only reduces the time cost, but also outperforms the most advanced methods.

Multitask learning (MTL) is a joint learning paradigm, which fuses multiple related tasks together to achieve the better performance than single-task learning methods. It has been observed by many researchers that different tasks with certain similarities share a low-dimensional common yet latent subspace. In order to get the low-rank structure shared across tasks, trace norm has been used as a convex relaxation of the rank minimization problem. However, trace norm is not a tight approximation for the rank function. To address this important issue, we propose two novel regularization-based models to approximate the rank minimization problem by minimizing the k minimal singular values. For our new models, if the minimal singular values are suppressed to zeros, the rank would also be reduced. Compared with the standard trace norm, our new regularization-based models are the tighter approximations, which can help our models capture the low-dimensional subspace among multiple tasks better. Besides, it is an NP-hard problem to directly solve the exact rank minimization problem for our models. In this article, we proposed two simple but effective strategies to optimize our models, which tactically solves the exact rank minimization problem by setting a large penalizing parameter. Experimental results performed on synthetic and real-world benchmark datasets demonstrate that the proposed models have the ability of learning the low-rank structure shared across tasks and the better performance than other classical MTL methods.

This work focuses on the projected clustering problem. Specifically, an efficient and parameter-free clustering model, named discriminative projected clustering (DPC), is proposed for simultaneously low-dimensional and discriminative projection learning and clustering, from the perspective of least squares regression. The proposed DPC, a constrained regression model, aims at finding both a transformation matrix and a binary indicator matrix to minimize the sum-of-squares error. Theoretically, a significant conclusion is drawn and used to reveal the connection between DPC and linear discriminant analysis (LDA). Experimentally, experiments are conducted on both toy and real-world data to validate the effectiveness and efficiency of DPC; experiments are also conducted on hyperspectral images to further verify its practicability in real-world applications. Experimental results demonstrate that DPC achieves comparable or superior results to some state-of-the-art clustering methods.

Principal component analysis (PCA) is a typical unsupervised dimensionality reduction algorithm, and one of its important weaknesses is that the squared$\ell _{2}$-norm cannot overcome the influence of outliers. Existing robust PCA methods based on paradigm have the following two drawbacks. First, the objective function of PCA based on the$\ell _{1}$-norm has no rotational invariance and limited robustness to outliers, and its solution mostly uses a greedy search strategy, which is expensive. Second, the robust PCA based on the$\ell _{2,1}$-norm and the$\ell _{2,p}$-norm is essential to learn probability weights for data, which only weakens the influence of outliers on the learning projection matrix and cannot be completely eliminated. Moreover, the ability to detect anomalies is also very poor. To solve these problems, we propose a novel discrete robust principal component analysis (DRPCA). Through self-learning binary weights, the influence of outliers on the projection matrix and data center estimation can be completely eliminated, and anomaly detection can be directly performed. In addition, an alternating iterative optimization algorithm is designed to solve the proposed problem and realize the automatic update of binary weights. Finally, our proposed model is successfully applied to anomaly detection applications, and experimental results demonstrate that the superiority of our proposed method compared with the state-of-the-art methods.

Linear discriminant analysis (LDA) is one of the most effective and popular methods to reduce the dimensionality of data with Gaussian assumption. However, LDA cannot handle non-Gaussian data because the center point is incompetent to represent the distribution of data. Some existing methods based on graph embedding focus on exploring local structures via pairwise relationships of data for addressing the non-Gaussian issue. Due to massive pairwise relationships, the computational complexity is high as well as the locally optimal solution is hard to find. To address these issues, we propose a novel and efficient local embedding learning via landmark-based dynamic connections (LDC) in which we leverage several landmarks to represent different subclusters in the same class and establish the connections between each point and landmark. Furthermore, in order to explore the relationship of landmarks pairwise more precisely, the relationship between each point and their corresponding neighbor landmarks are found in the optimal subspace, rather than the original space, which can avoid the negative influence of the noises. We also propose an efficient iterative algorithm to deal with the proposed ratio minimization problem. Extensive experiments conducted on several real-world datasets have demonstrated the advantages of the proposed method.

The goal of multi-view clustering is to partition samples into different subsets according to their diverse features. Previous multi-view clustering methods mainly exist two forms: multi-view spectral clustering and multi-view matrix factorization. Although they have shown excellent performance in many occasions, there are still many disadvantages. For example, multi-view spectral clustering usually needs to perform postprocessing. Multi-view matrix factorization directly decomposes the original data features. When the size of features is large, it encounters the expensive time consumption to decompose these data features thoroughly. Therefore, we proposed a novel multi-view clustering approach. The main advantages include the following three aspects: 1) it searches for a common joint graph across multiple views, which fully explores the hidden structure information by utilizing the compatibility among views; 2) the introduced nonnegative constraint manipulates that the final clustering results can be directly obtained; and 3) straightforwardly decomposing the similarity matrix can transform the eigenvalue factorization in spectral clustering with computational complexity$O(n^{3})$into the singular value decomposition (SVD) with$O({n}{c}^{2})$time cost, where${n}$and$c$, respectively, denote the numbers of samples and classes. Thus, the computational efficiency can be improved. Moreover, in order to learn a better clustering model, we set that the constructed similarity graph approximates each view affinity graph as close as possible by adding the constraint as the initial affinity matrices own. Furthermore, substantial experiments are conducted, which verifies the superiority of the proposed two clustering methods comparing with single-view clustering approaches and state-of-the-art multi-view clustering methods.

Feature selection is an important and effective data preprocessing method, which can remove the noise and redundant features while retaining the relevant and discriminative features in high-dimensional data. In real-world applications, the relationships between data samples and their labels are usually nonlinear. However, most of the existing feature selection models focus on learning a linear transformation matrix, which cannot capture such a nonlinear structure in practice and will degrade the performance of downstream tasks. To address the issue, we propose a novel nonlinear feature selection method to select those most relevant and discriminative features in high-dimensional dataset. Specifically, our method learns the nonlinear structure of high-dimensional data by a neural network with cross entropy loss function, and then using the structured sparsity norm such as$\ell _{2,p}$-norm to regularize the weights matrix connecting the input layer and the first hidden layer of the neural network model to learn weight of each feature. Therefore, a structural sparse weights matrix is obtained by conducting nonlinear learning based on a neural network with structured sparsity regularization. Then, we use the gradient descent method to achieve the optimal solution of the proposed model. Evaluating the experimental results on several synthetic datasets and real-world datasets shows the effectiveness and superiority of the proposed nonlinear feature selection model.

Graph-based subspace learning has been widely used in various applications as the rapid growth of data dimension, while the graph is constructed by affinity matrix of input data. However, it is difficult for these subspace learning methods to preserve the intrinsic local structure of data with the high-dimensional noise. To address this problem, we proposed a novel unsupervised dimensionality reduction approach named unsupervised subspace learning with flexible neighboring (USFN). We learn a similarity graph by adaptive probabilistic neighborhood learning process to preserve the manifold structure of high-dimensional data. In addition, we utilize the flexible neighboring to learn projection and latent representation of manifold structure of high-dimensional data to remove the impact of noise. The adaptive similarity graph and latent representation are jointly learned by integrating adaptive probabilistic neighborhood learning and manifold residue term into a unified objection function. The experimental results on synthetic and real-world datasets demonstrate the performance of the proposed unsupervised subspace learning USFN method.

Neighborhood reconstruction is a good recipe to learn the local manifold structure. Representation-based discriminant analysis methods normally learn the reconstruction relationship between each sample and all the other samples. However, reconstruction graphs constructed in these methods have three limitations: 1) they cannot guarantee the local sparsity of reconstruction coefficients; 2) heterogeneous samples may own nonzero coefficients; and 3) they learn the manifold information prior to the process of dimensionality reduction. Due to the existence of noise and redundant features in the original space, the prelearned manifold structure may be inaccurate. Accordingly, the performance of dimensionality reduction would be affected. In this article, we propose a joint model to simultaneously learn the affinity relationship, reconstruction relationship, and projection matrix. In this model, we actively assign neighbors for each sample and learn the inter-reconstruction coefficients between each sample and their neighbors with the same label information in the process of dimensionality reduction. Specifically, a sparse constraint is employed to ensure the sparsity of neighbors and reconstruction coefficients. The whitening constraint is imposed on the projection matrix to remove the relevance between features. An iterative algorithm is proposed to solve this method. Extensive experiments on toy data and public datasets show the superiority of the proposed method.

With its simplicity and effectiveness, k-means is immensely popular, but it cannot perform well on complex nonlinear datasets. Multiple kernel k-means (MKKM) demonstrates the ability to describe highly complex nonlinear separable data structures. However, its speed requirement cannot scale as well as the data size grows beyond tens of thousands. Nowadays, digital data explosion mandates more scalable clustering methods to assist the machine learning tasks in easy-to-access form. To address the issue, we propose to employ the Nystrom scheme for MKKM clustering, termed scalable multiple kernel k-means clustering. It significantly reduces the computational complexity by replacing the original kernel matrix with a low-rank approximation. Analytically and empirically, we demonstrate that our method performs as well as existing state-of-the-art methods, but at a significantly lower compute cost, allowing us to scale the method more effectively for clustering tasks.

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.

Multiple kernel clustering seeks to combine several kernels for boosting the clustering performance. However, most existing MKKM methods fail to evaluate kernel correlation adequately, which may inevitably select highly correlated kernels resulting in kernel redundancy. Besides, most existing methods solve the NP-hard cluster labels assignment task in two stages: first learning the relaxed labels with continuous values and then obtaining the discrete labels via other discretization methods like k-means. This two-stage strategy may result in the loss of information owing to the deviation between the genuine solution and the approximated one. In this work, we present a unified framework for Discrete Multi-kernel k-means with Kernel Diversity Regularization (DMK-KDR). It is capable of penalizing highly correlated kernels through a well-designed matrix-induced regularization, thus allowing for improved diversity and reduced redundancy in kernel fusion. Additionally, it learns both discrete and continuous clustering indicator matrices simultaneously, thereby ensuring the integrity of the discrete solution without over-reliance on k-means or the loss of information. The efficacy of our model has been evaluated in a number of experiments using real-world datasets.

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.

Multiview clustering partitions data into different groups according to their heterogeneous features. Most existing methods degenerate the applicability of models due to their intractable hyper-parameters triggered by various regularization terms. Moreover, traditional spectral based methods always encounter the expensive time overheads and fail in exploring the explicit clusters from graphs. In this paper, we present a scalable and parameter-free graph fusion framework for multiview clustering, seeking for a joint graph compatible across multiple views in a self-supervised weighting manner. Our formulation coalesces multiple view-wise graphs straightforward and learns the weights as well as the joint graph interactively, which could actively release the model from any weight-related hyper-parameters. Meanwhile, we manipulate the joint graph by a connectivity constraint such that the connected components indicate clusters directly. The designed algorithm is initialization-independent and time-economical which obtains the stable performance and scales well with the data size. Substantial experiments on toy data as well as real datasets are conducted that verify the superiority of the proposed method compared to the state-of-the-arts over the clustering performance and time expenditure.

Recently, several robust principle component analysis (RPCA) models have been proposed to improve the robustness of principle component analysis (PCA). But an important problem that the robustness to outliers affects the discrimination of correct samples has not been solved yet. To solve this problem, we propose a truncated robust principle component analysis (T-RPCA) model which treats correct samples and outliers separately. In fact, the proposed model performs an implicitly truncated weighted learning scheme which is more reasonable for robustness learning respective to previous works. Moreover, we propose a re-weighted (RW) optimization framework to solve a general problem and generalize two sub-frameworks upon it. To be specific, the first sub-framework orients a general truncated loss optimization problem which contains the objective problem of T-RPCA, and the second one focuses on a general singular-value based optimization problem. Besides, we provide rigorously theoretical guarantees for the proposed model, RW framework and sub-frameworks. Empirical studies demonstrate that the proposed T-RPCA model outperforms previous RPCA models on reconstruction and classification tasks.

k-means method using Lloyd heuristic is a traditional clustering method which has played a key role in multiple downstream tasks of machine learning because of its simplicity. However, Lloyd heuristic always finds a bad local minimum, i.e., the bad local minimum makes objective function value not small enough, which limits the performance of k-means. In this paper, we use coordinate descent (CD) method to solve the problem. First, we show that the k-means minimization problem can be reformulated as a trace maximization problem, then a simple and efficient coordinate descent scheme is proposed to solve the maximization problem. Two interesting findings through theory are that Lloyd cannot decrease the objective function value of k-means produced by our CD further, and our proposed method CD to solve k-means problem can avoid produce empty clusters. In addition, according to the computational complexity analysis, it is verified CD has the same time complexity with original k-means method. Extensive experiments including statistical hypothesis testing, on several real-world datasets with varying number of clusters, varying number of samples and varying number of dimensions show that CD performs better compared to Lloyd, i.e., lower objective value, better local minimum and fewer iterations. And CD is more robust to initialization than Lloyd whether the initialization strategy is random or initialization of k-means++.

Linear discriminant analysis (LDA) has been proven to be effective in dimensionality reduction. However, the performance of LDA depends on the consistency assumption of the global structure and the local structure. Some work extended LDA along this line of research and proposed local formulations of LDA. Unfortunately, the learning scheme of these algorithms is suboptimal in that the intrinsic relationship between data points is pre-learned in the original space, which is usually affected by the noise and redundant features. Besides, the time cost is relatively high. To alleviate these drawbacks, we propose a Fast Locality Discriminant Analysis framework (FLDA), which has three advantages: (1) It can divide a non-Gaussian distribution class into many sub-blocks that obey Gaussian distributions by using the anchor-based strategy. (2) It captures the manifold structure of data by learning the fuzzy membership relationship between data points and the corresponding anchor points, which can reduce computation time. (3) The weights between data points and anchor points are adaptively updated in the subspace where the irrelevant information and the noise in high-dimensional space have been effectively suppressed. Extensive experiments on toy data sets, UCI benchmark data sets and imbalanced data sets demonstrate the efficiency and effectiveness of the proposed method.

L,ineaTDiscriminant Analysis (LDA) has been widely used in supervised dimensionality reduction fields. How- ever, LDA is usually weak in tackling data with Non-Gaussian distribution due to its incapability of extracting the intrinsic structure of data. In order to learn the intrinsic information more effectively, some dimensionality reduction methods incorporate the adaptive full-connected graph into the algorithm frame, but the defect is that the calculation of each pairwise distance is very time-consuming. In this paper, we propose a novel fast adaptive local subspace learning with regressive regularization model to solve the supervised dimensional reduction problem. Firstly, the adaptive anchor point graph is used to capture local structure information, which can greatly reduce computation complexity. Secondly, by using regressive regularization, the samples from different classes can be better separated in the projected space and the workload of selecting the optimal reduced dimension is easier. Moreover, entropy regularization is used to derive more appropriate weights. Finally, extensive experiments are conducted on real world data sets to verify the superiority of our model.

Matrix completion, in essence, involves recovering a low-rank matrix from a subset of its entries. Most existing methods for matrix completion neglect two significant issues. First, in several practical applications, such as collaborative filtering, some samples may be corrupted completely. However, most of the robust algorithms consider only the condition that a few components of each column have been arbitrarily contaminated. Second, many real data are not static in nature. Nevertheless, the conventional batch-based matrix completion methods cannot efficiently deal with the out-of-sample, that is, the vector completion problem. In this article, we first provide a novel robust matrix completion model and then develop an efficient optimization method that only requires conducting one time singular value decomposition for a thin matrix per iteration. Furthermore, by exploiting the essence of online matrix completion algorithms, we develop a vector completion model which can help users predict the missing values of out of sample. Numerical comparisons with traditional batch-based and online matrix completion algorithms demonstrate the benefits of the proposed method on streaming data corrupted by column outliers. Moreover, we show that our model can be used to detect outliers from incomplete information. This advantage is validated via numerous experimental results on synthetic and real-world data.

In this article, we propose a novel feature selection approach via explicitly addressing the long-standing subspace sparsity issue. Leveraging$\ell _{2,1}$-norm regularization for feature selection is the major strategy in existing methods, which, however, confronts sparsity limitation and parameter-tuning trouble. To circumvent this problem, employing the$\ell _{2,0}$-norm constraint to improve the sparsity of the model has gained more attention recently whereas, optimizing the subspace sparsity constraint is still an unsolved problem, which only can acquire an approximate solution and without convergence proof. To address the above challenges, we innovatively propose a novel subspace sparsity discriminative feature selection (S2DFS) method which leverages a subspace sparsity constraint to avoid tuning parameters. In addition, the trace ratio formulated objective function extremely ensures the discriminability of selected features. Most important, an efficient iterative optimization algorithm is presented to explicitly solve the proposed problem with a closed-form solution and strict convergence proof. To the best of our knowledge, such an optimization algorithm of solving the subspace sparsity issue is first proposed in this article, and a general formulation of the optimization algorithm is provided for improving the extensibility and portability of our method. Extensive experiments conducted on several high-dimensional text and image datasets demonstrate that the proposed method outperforms related state-of-the-art methods in pattern classification and image retrieval tasks.

Fuzzy clustering is one of the most popular clustering approaches and has attracted considerable attention in many fields. However, high computational cost has become a bottleneck which limits its applications in large-scale problems. Moreover, most fuzzy clustering algorithms are sensitive to noise. To address these issues, a novel fuzzy clustering algorithm, called fast fuzzy clustering based on anchor graph (FFCAG), is proposed. The FFCAG algorithm integrates anchor-based similarity graph construction and membership matrix learning into a unified framework, such that the prior knowledge of anchors can be further utilized to improve clustering performance. Specifically, FFCAG first constructs an anchor-based similarity graph with a parameter-free neighbor assignment strategy. Then, it designs a quadratic programming model to learn the membership matrix of anchors, which is very different from traditional fuzzy clustering algorithms. More importantly, a novel balanced regularization term is introduced into the objective function to produce more accurate clustering results. Finally, we adopt an alternating optimization algorithm with guaranteed convergence to solve the proposed method. Experimental results performed on synthetic and real-world datasets demonstrate the proposed FFCAG can significantly reduce the computational time with comparable, even superior, clustering performance, compared with state-of-the-art algorithms.

Fuzzy$c$-means method (FCM) is a popular clustering method, which uses alternating iteration algorithm to update membership matrix$\mathbf {F}$and center matrix$\mathbf {M}$of$d \times c$size. However, original FCM suffers from finding a suboptimal local minimum, which limits the performance of FCM. In this article, we propose a new optimization method for fuzzy$c$-means problem. We first propose an equivalent minimization problem of FCM, then, a simple alternating iteration algorithm is proposed to solve the new minimization problem, which involves an effective and theoretically guaranteed Iteratively Reweighted (IRW) method, so we call the new optimization method IRW-FCM. Our IRW-FCM utilizes$c$not$dc$intermediate variables to update$\mathbf {F}$, which can decrease space complexity. Extensive experiments including objective-function value comparison and clustering-performance comparison show that IRW-FCM can obtain better local minima than FCM with fewer iterations. And according to the time-complexity analysis, it is verified IRW-FCM has the same linear time complexity with FCM. What's more, compared with other clustering methods, IRW-FCM also shows its superiority.

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.

Semi-supervised learning as one of most attractive problems in machine learning research field has aroused broad attentions in recent years. In this paper, we propose a novel locality preserved dimensionality reduction framework, named Semi-supervised Adaptive Local Embedding learning (SALE), which learns a local discriminative embedding by constructing a$k_1$Nearest Neighbors ($k_1$NN) graph on labeled data, so as to explore the intrinsic structure, i.e., sub-manifolds from non-Gaussian labeled data. Then, mapping all samples into learned embedding and constructing another$k_2$NN graph on all embedded data to explore the global structure of all samples. Therefore, the unlabeled data and their corresponding labeled neighbors can be clustered into same sub-manifold, so as to improve the discriminative power of embedded data. Furthermore, we propose two semi-supervised dimensionality reduction methods with orthogonal and whitening constraints based on proposed SALE framework. An efficient alternatively iterative optimization algorithm is developed to solve the NP-hard problem in our models. Extensive experiments conducted on several synthetic and real-world data sets demonstrate the superiorities of our methods on local structure exploration and classification task.

Fuzzy K-Means (FKM) clustering is of great importance for analyzing unlabeled data. FKM algorithms assign each data point to multiple clusters with some degree of certainty measured by the membership function. In these methods, the fuzzy membership degree matrix is obtained based on the calculation of the distance between data points in the original space. However, this operation may lead to suboptimal results because of the influence of noises and redundant features. Besides, some FKM clustering methods ignore the importance of the weighting exponent. In this paper, we propose a novel FKM method called Fuzzy K-Means Clustering With Discriminative Embedding. Within this method, we simultaneously conduct dimensionality reduction along with fuzzy membership degree learning. To retain most information in the embedding subspace and improve the robustness of this method, principal component analysis is incorporated into our framework. An iterative optimization algorithm is proposed to solve the model. To validate the efficacy of the proposed method, we perform comprehensive analyses, including convergence behavior, parameter determination and computational complexity. Moreover, we also match a appropriate weighting exponent for each data set. Experimental results on benchmark data sets show that the proposed method is more discriminative and effective for clustering tasks.

Feature selection is one of the most important techniques to deal with the high-dimensional data for a variety of machine learning and data mining tasks, such clustering, classification, and retrieval, etc. Fuzziness is a widespread nature of data in nature human society. However, most existing feature selection methods ignore the existence of fuzziness in the data, resulting in sub-optimal feature subsets. To address the problem, we propose a novel unsupervised feature selection method, called Unsupervised Discriminative Projection for Feature Selection (UDPFS) to select discriminative features by conducting fuzziness learning and sparse learning, simultaneously. Specifically, we use projection matrix transform data as its low-dimensional representation, which are partitioned into clusters by using membership matrix with sparse constraint. In addition,$\ell _{2, 1}$-norm regularization is applied to the projection matrix. Then, a discriminative projection matrix with row sparse is obtained by perform fuzziness learning and sparse learning, simultaneously. An effective alternative optimization algorithm is proposed to solve the objective function. Evaluate experimental results on several real-world datasets show the effectiveness and superiority of the proposed unsupervised feature selection method.

In this article, we propose a novel feature selection approach, named unsupervised feature selection with constrained$\ell _{2,0}$-norm (row-sparsity constrained) and optimized graph (RSOGFS), which unifies feature selection and similarity matrix construction into a general framework instead of independently performing the two-stage process; thus, the similarity matrix preserving the local manifold structure of data can be determined adaptively. Unlike those sparse learning-based feature selection methods that can only solve the relaxation or approximation problems by introducing sparsity regularization term into the objective function, the proposed method directly tackles the original$\ell _{2,0}$-norm constrained problem to achieve group feature selection. Two optimization strategies are provided to solve the original sparse constrained problem. The convergence and approximation guarantees for the new algorithms are rigorously proved, and the computational complexity and parameter determination are theoretically analyzed. Experimental results on real-world data sets show that the proposed method for solving a nonconvex problem is superior to the state of the arts for solving the relaxed or approximate convex problems.

Finding a consensus embedding from multiple views is the mainstream task in multiview graph-based clustering, in which the key problem is to handle the inconsistence among multiple views. In this article, we consider clustering effectiveness and practical applicability collectively, and propose a parameter-free model to alleviate the inconsistence of multiple views cleverly. To be specific, the proposed model considers the diversities of multiple views as two-layers. The first layer considers the inconsistence among different features of each view and the second layer considers linking the preembeddings of multiple views attentively. By this way, a consensus embedding can be learned via kernel method effectively and the whole learning procedure is parameter-free. To solve the optimization problem involved in the proposed model, we propose an alternative algorithm which is efficient and easy to implement in practice. In the experiments, we evaluate the proposed model on synthetic and real datasets and the experimental results demonstrate its effectiveness.

Multi-task learning has been observed by many researchers, which supposes that different tasks can share a low-rank common yet latent subspace. It means learning multiple tasks jointly is better than learning them independently. In this paper, we propose two novel multi-task learning formulations based on two regularization terms, which can learn the optimal shared latent subspace by minimizing the exactly k minimal singular values. The proposed regularization terms are the more tight approximations of rank minimization than trace norm. But it's an NP-hard problem to solve the exact rank minimization problem. Therefore, we design a novel re-weighted based iterative strategy to solve our models, which can tactically handle the exact rank minimization problem by setting a large penalizing parameter. Experimental results on benchmark datasets demonstrate that our methods can correctly recover the low-rank structure shared across tasks, and outperform related multi-task learning methods.

In this paper, we propose a novel approach called dependence-guided multi-view clustering (DGMC). Our model enhances the dependence between unified embedding learning and clustering, as well as promotes the dependence between unified embedding and embedding of each view. Specifically, DGMC learns a unified embedding and partitions data in a joint fashion, thus the clustering results can be directly obtained. A kernel dependence measure is employed to learn a unified embedding by forcing it to be close to different views, thus the complex dependence among different views can be captured. Moreover, an implicit-weight learning mechanism is provided to ensure the diversity of different views. An efficient algorithm with rigorous convergence analysis is derived to solve the proposed model. Experimental results demonstrate the advantages of the proposed method over the state of the arts on real-world datasets.

Most spectral clustering algorithms obtain firstly the embedding based on the similarity matrix of the input data and then discretize the embedding to get the final clustering result. So, their performance is greatly affected by the noise of the similarity matrix, and the two-step strategy may lead to a suboptimal result. In this article, a novel Rank-Constrained clustering algorithm with Adaptive Embedding called RCAE is proposed, where the spectral embedding and the clustering structure are learned simultaneously, so, the influence of noise on performance is greatly reduced. In addition, a rank constraint is adopted in our model, thus, the connectivity matrix with exactly c (the number of clusters to construct) connected components can be learned, therefore, the final clustering result can be obtained according to the connected components. Experiments on several benchmark datasets validate the superiority of the proposed methods, compared to the several state-of-the-art clustering algorithms [GitHub].

Dimension reduction is an effective technology to embed data with high dimension to lower dimension space, where Linear Discriminant Analysis (LDA), one of representative methods, only works with Gaussian distribution data. However, in order to solve non-Gaussian issue that only one cluster cannot well fit the distribution of same class, many graph-based discriminant analysis methods are proposed which capture local structure through measuring each pairwise distance. This is expense of time complexity because of the full-connections. In order to solve this issue, we propose a fast local representation learning with adaptive anchor graph to learn local structure information through similarity matrix in anchor-based graph. Notably, anchor points and similarity matrix are updated in subspace which is more precisely to capture local discriminant information. Experimental results on several synthetic and well-known datasets demonstrate the advantages of our method over the state-of-the-art methods.

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.

This paper explores a succinct kernel model for Group-Sparse Projections Learning (GSPL), to handle multiview feature selection task completely. Compared to previous works, our model has the following useful properties: 1) Strictness: GSPL innovatively learns group-sparse projections strictly on multiview data via ‘2;0-norm constraint, which is different with previous works that encourage group-sparse projections softly. 2) Adaptivity: In GSPL model, when the total number of selected features is given, the numbers of selected features of different views can be determined adaptively, which avoids artificial settings. Besides, GSPL can capture the differences among multiple views adaptively, which handles the inconsistent problem among different views. 3) Succinctness: Except for the intrinsic parameters of projection-based feature selection task, GSPL does not bring extra parameters, which guarantees the applicability in practice. To solve the optimization problem involved in GSPL, a novel iterative algorithm is proposed with rigorously theoretical guarantees. Experimental results demonstrate the superb performance of GSPL on synthetic and real datasets.

Linear Discriminant Analysis (LDA) is one of the most successful supervised dimensionality reduction methods and has been widely used in many real-world applications. However,l2ℓ2-norm is employed as the distance metric in the objective of LDA, which is sensitive to outliers. Many previous works improve the robustness of LDA by usingl1ℓ1-norm distance. However, the robustness against outliers is limited and the solver ofl1ℓ1-norm is mostly based on the greedy search strategy, which is time-consuming and easy to get stuck in a local optimum. In this paper, we propose a novel robust LDA measured byl2,1ℓ2,1-norm to learn robust discriminative projections. The proposed model is challenging to solve since it needs to minimize and maximize (minmax)l2,1ℓ2,1-norm terms simultaneously. As a result, we first systematically derive an efficient iterative optimization algorithm to solve a general ratio minimization problem, and then rigorously prove its convergence. More importantly, an alternately non-greedy iterative re-weighted optimization algorithm is developed based on the preceding approach for solving proposedl2,1ℓ2,1-norm minmax problem. Besides, an optimal weighted mean mechanism is driven according to the designed objective and solver, which can be applied to other approaches for robustness improvement. Experimental results on several real-world datasets show the effectiveness of proposed method.

Spectral clustering methods are gaining more and more interests and successfully applied in many fields because of their superior performance. However, there still exist two main problems to be solved: 1) spectral clustering methods consist of two successive optimization stages-spectral embedding and spectral rotation, which may not lead to globally optimal solutions, 2) and it is known that spectral methods are time-consuming with very high computational complexity. There are methods proposed to reduce the complexity for data vectors but not for graphs that only have information about similarity matrices. In this paper, we propose a new method to solve these two challenging problems for graph clustering. In the new method, a new framework is established to perform spectral embedding and spectral rotation simultaneously. The newly designed objective function consists of both terms of embedding and rotation, and we use an improved spectral rotation method to make it mathematically rigorous for the optimization. To further accelerate the algorithm, we derive a low-dimensional representation matrix from a graph by using label propagation, with which, in return, we can reconstruct a double-stochastic and positive semidefinite similarity matrix. Experimental results demonstrate that our method has excellent performance in time cost and accuracy.

Graph-based dimensionality reduction methods are widely used in classification and clustering tasks due to their superior performance. The key to the performance of these methods is how to construct the graph. Although some existing methods can obtain an adaptive graph and a projection matrix simultaneously by combining manifold learning and graph construction in a unified framework, the linear constraint used in manifold learning is too hard . To solve this problem, we propose a novel method named adaptive flexible optimal graph (AFOG) for unsupervised dimensionality reduction. AFOG can obtain an adaptive flexible optimal graph by relaxing the linear constraint in the process of low-dimensional manifold mapping. At the same time, by using the principle of maximum separability, it can also obtain an effective projection matrix, which can solve out-ofsample problems. Experiments on six public benchmark data sets indicate that AFOG outperforms several other state-of-the-art methods.

Multi-view clustering is a powerful tool for improving clustering results via integrating the heterogeneous features from different views. In this work, we develop a novel invisible weighted method to this issue. Specifically, our proposed method first considers the diversities among different features of each view with kernel function, and then fuses the multiple pre-embeddings of all the views attentively. As a result, a consensus embedding can be obtained with the adaptive invisible weighted model. Besides, we provide an efficient optimization approach to solve the involved optimization problem and provide the corresponding convergence analysis. Extensive experimental results on benchmark datasets validate the superiorities of the proposed method to the state-of-the-art methods.

The purpose of this study was to implement principal component analysis (PCA) on videocapsule endoscopy (VE) images to develop a new computerized tool for celiac disease recognition. Three PCA algorithms were implemented for feature extraction and sparse representation. A novel strip PCA (SPCA) with nongreedy L1-norm maximization is proposed for VE image analysis. The extracted principal components were interpreted by a non-parametric k-nearest neighbor (k-NN) method for automated celiac disease classification. A benchmark dataset of 460 images (240 from celiac disease patients with small intestinal villous atrophy versus 220 control patients lacking villous atrophy) was constructed from the clinical VE series. It was found that the newly developed SPCA with nongreedy L1-norm maximization was most efficient for computerized celiac disease recognition, having a robust performance with an average recognition accuracy of 93.9 percent. Furthermore, SPCA also has a reduced computation time as compared with other methods. Therefore, it is likely that SPCA will be a helpful adjunct for the diagnosis of celiac disease.

Semisupervised band selection (BS) technique plays an important role in processing hyperspectral images (HSIs) because of its superiority of using the limited labeled data and plentiful unlabeled data to select the discriminative and informative feature, which copes with the problem of high-dimensional and scare labeled samples of HSIs. Among semisupervised BS models, graph-based methods are superior to others in many situations and have received more and more attention. However, traditional graph-based models construct a similarity matrix and select valuable bands independently. The similarity matrix remains constant, which will damage the local manifold structure and lead to a suboptimal result. To solve this problem, we propose a semisupervised band selection with an optimal graph (BSOG) approach, which performs BS and local structure learning simultaneously. Instead of fixing the input similarity matrix, the similarity matrix is updated constantly to learn a better local structure. Besides, the learned similarity matrix is adaptive. Then, the optimal band subset can be selected by analyzing the obtained projection matrix$\boldsymbol W$. An efficient and simple optimization algorithm is proposed to solve this model. Experiments on four real HSIs data validate the effectiveness of the proposed model.

The rapid growth of the number of data brings great challenges to clustering, especially the introduction of multi-view data, which collected from multiple sources or represented by multiple features, makes these challenges more arduous. How to clustering large-scale data efficiently has become the hottest topic of current large-scale clustering tasks. Although several accelerated multi-view methods have been proposed to improve the efficiency of clustering large-scale data, they still cannot be applied to some scenarios that require high efficiency because of the high computational complexity. To cope with the issue of high computational complexity of existing multi-view methods when dealing with large-scale data, a fast multi-view clustering model via nonnegative and orthogonal factorization (FMCNOF) is proposed in this paper. Instead of constraining the factor matrices to be nonnegative as traditional nonnegative and orthogonal factorization (NOF), we constrain a factor matrix of this model to be cluster indicator matrix which can assign cluster labels to data directly without extra post-processing step to extract cluster structures from the factor matrix. Meanwhile, the F-norm instead of the L2-norm is utilized on the FMCNOF model, which makes the model very easy to optimize. Furthermore, an efficient optimization algorithm is proposed to solve the FMCNOF model. Different from the traditional NOF optimization algorithm requiring dense matrix multiplications, our algorithm can divide the optimization problem into three decoupled small size subproblems that can be solved by much less matrix multiplications. Combined with the FMCNOF model and the corresponding fast optimization method, the efficiency of the clustering process can be significantly improved, and the computational complexity is nearly O(n) . Extensive experiments on various benchmark data sets validate our approach can greatly improve the efficiency when achieve acceptable performance.

Recently, with the explosive increase in Internet data, the traditional Graph-based Semi-Supervised Learning (GSSL) model is not suitable to deal with large scale data as the high computation complexity. Besides, GSSL models perform classification on a fixed input data graph. The quality of initialized graph has a great effect on the classification result. To solve this problem, in this paper, we propose a novel approach, named optimal bipartite graph-based SSL (OBGSSL). Instead of fixing the input data graph, we learn a new bipartite graph to make the result more robust. Based on the learned bipartite graph, the labels of the original data and anchors can be calculated simultaneously, which solves co-classification problem in SSL. Then, we use the label of anchor to handle out-of-sample problem, which preserves well classification performance and saves much time. The computational complexity of OBGSSL is O(ndmt+nm2), which is a significant improvement compared with traditional GSSL methods that need O(n2d+n3), where n, d, m and t are the number of samples, features anchors and iterations, respectively. Experimental results demonstrate the effectiveness and efficiency of our OBGSSL model.

Linear discriminant analysis (LDA) is one of commonly used supervised subspace learning methods. However, LDA will be powerless faced with the no-label situation. In this paper, the unsupervised LDA (Un-LDA) is proposed and first formulated as a seamlessly unified objective optimization which guarantees convergence during the iteratively alternative solving process. The objective optimization is in both the ratio trace and the trace ratio forms, forming a complete framework of a new approach to jointly clustering and unsupervised subspace learning. The extension of LDA into Un-LDA enables to not only complete unsupervised subspace learning via the explicitly presented subspace projection matrix but also simultaneously finish clustering and even clustering out-of-sample data via the explicitly presented transformation matrix. To overcome the difficulty in solving the non-convex objective optimization, we mathematically prove that the Un-LDA optimization in both forms can be transformed into the simple K-means clustering optimization when the subspace is determined. The Un-LDA optimization is eventually completed by alternatively optimizing the clusters using K-means and the subspace using the supervised LDA methods and iterating this whole process until convergence or stopping criterion. The experiments demonstrate that our proposed Un-LDA algorithms are comparable or even much superior to the counterparts.

How to effectively cluster large-scale image data sets is a challenge and is receiving more and more attention. To address this problem, a novel clustering method called fast clustering with co-clustering via discrete non-negative matrix factorization, is proposed. Inspired by co-clustering, our algorithm reduces computational complexity by transforming clustering tasks into co-clustering tasks. Although our model has the same form of objective function as normalized cut, we relax it to a matrix decomposition problem, which is different from most graph-based approaches. In addition, an efficient optimization algorithm is proposed to solve the relaxed problem, where a discrete solution corresponding to the clustering result can be directly obtained. Extensive experiments have been conducted on several synthetic data sets and real word data sets. Compared with the state-of-the-art clustering methods, the proposed algorithm achieves very promising performance.

Many anchor-graph-based spectral clustering methods have been proposed to accelerate spectral clustering for large scale problems. In this paper, we revisit the popular large-scale spectral clustering method based on the anchor graph which is equivalent to the spectral decomposition on a similar matrix obtained using a second-order transition probability. However, due to the special structure of the bipartite graph, there is no stable distribution of the random walk process. The even-order transition probabilities may only a side view of the bipartite structure, resulting in breaking the independence of data points and leading to undesired artifacts for boundary samples. Therefore, we propose a Fast Spectral Clustering based on the Random Walk Laplacian (FRWL) method. The random walk Laplacian balances explicitly the popularity of anchors and the independence of data points, which keeps the structure of boundary samples. The experimental results demonstrate the efficiency and effectiveness of our method.

This paper tackles multi-view clustering via proposing a novel mixed embedding approximation (MEA) method. Formally, we aim to learn a uniform orthogonal embedding based on the orthogonal pre-embeddings of each view. At first, we hope that the uniform embedding can reconstruct the affinity graph of each view. To improve the representation of learnt embedding, we perform an embedding approximation on Grassmann manifold which is famous on subspace analysis. To perform the difference of views, a hidden weights learning module is provided. Moreover, we propose an iterative algorithm to solve the proposed MEA method and provide rigorously convergence analysis. Extensive experiments demonstrate the superiorities of the proposed method.

In this paper, we present a technique of definitely addressing the pairwise constraints in the semi-supervised clustering. Our method contributes to formulating the cannot-link relations and propagating them over the affinity graph flexibly. The pairwise constrained instances are provably guaranteed to be in the same or different connected components of the graph. Combined with the Laplacian rank constraint, the proposed model learns a Pairwise Constrained structured Optimal Graph (PCOG), from which the specified c clusters supporting the known pairwise constraints are directly obtained. An efficient algorithm invoked by the label propagation is designed to solve the formulation. Additionally, we also provide a compact criterion to acquire the key pairwise constraints for prompting the semi-supervised graph clustering. Substantial experimental results show that the proposed method achieves the significant improvements by using a few prior pairwise constraints.

In this paper, we first propose a novel Structured Sparse Subspace Learning S^3L module to address the long-standing subspace sparsity issue. Elicited by proposed module, we design a new discriminative feature selection method, named Subspace Sparsity Discriminant Feature Selection S^2DFS which enables the following new functionalities: 1) Proposed S^2DFS method directly joints trace ratio objective and structured sparse subspace constraint via L2,0-norm to learn a row-sparsity subspace, which improves the discriminability of model and overcomes the parameter-tuning trouble with comparison to the methods used L2,1-norm regularization; 2) An alternative iterative optimization algorithm based on the proposed S^3L module is presented to explicitly solve the proposed problem with a closed-form solution and strict convergence proof. To our best knowledge, such objective function and solver are first proposed in this paper, which provides a new though for the development of feature selection methods. Extensive experiments conducted on several high-dimensional datasets demonstrate the discriminability of selected features via S^2DFS with comparison to several related SOTA feature selection methods. Source matlab code: https://github.com/StevenWangNPU/L20-FS.

Spectral clustering and $k$-means, both as two major traditional clustering methods, are still attracting a lot of attention, although a variety of novel clustering algorithms have been proposed in recent years. Firstly, a unified framework of $k$-means and ratio-cut is revisited, and a novel and efficient clustering algorithm is then proposed based on this framework. The time and space complexity of our method are both linear with respect to the number of samples, and are independent of the number of clusters to construct, more importantly. These properties mean that it is easily scalable and applicable to large practical problems. Extensive experiments on 12 real-world benchmark and 8 facial datasets validate the advantages of the proposed algorithms compared to the state-of-the-art clustering algorithms. In particular, over 15x and 7x speed-up can be obtained with respect to $k$-means on the synthetic dataset of 1 million samples and the benchmark dataset (CelebA) of 200k samples, respectively [GitHub].

This paper presents new algorithms to solve the feature-sparsity constrained PCA problem (FSPCA), which performs feature selection and PCA simultaneously. Existing optimization methods for FSPCA require data distribution assumptions and are lack of global convergence guarantee. Though the general FSPCA problem is NP-hard, we show that, for a low-rank covariance, FSPCA can be solved globally (Algorithm 1). Then, we propose another strategy (Algorithm 2) to solve FSPCA for the general covariance by iteratively building a carefully designed proxy. We prove (data-dependent) approximation bound and convergence guarantees for the new algorithms. For the spectrum of covariance with exponential/Zipf's distribution, we provide exponential/posynomial approximation bound. Experimental results show the promising performance and efficiency of the new algorithms compared with the state-of-the-arts on both synthetic and real-world datasets.

Linear discriminant analysis technique is an effective strategy to solve the long-standing issue, i.e., the “curse of dimensionality” that brings many obstacles on high-dimensional data storage and analysis. However, the projections are prone to be affected, especially when the training set contains outlier samples whose distribution deviates from the globality. In many real-world applications, the outlier samples contaminated by noisy signal or spottiness have negative effects on the classification and clustering performance. To address this issue, we propose to develop a novel capped ℓp-norm LDA model for robust dimension reduction against to outliers specifically. Proposed method integrates the capped ℓp-norm based loss into the objective, which not only suppresses the light outliers but also works well even though the training set is contaminated seriously. Furthermore, we derive an alternative iterative re-weighted optimization algorithm to minimize the proposed objective based on capped ℓp-norm with rigorous convergence proofs. Extensive experiments conducted on synthetic and real-world datasets demonstrate the robustness against to outliers of proposed method.

This letter proposes a double-attentive principle component analysis (DA-PCA) model for image processing. Compared to the previous PCA-based works that cannot deal with normal images and outliers effectively, the proposed DA-PCA model performs a double-attentive mechanism to sever the connections with outliers and hold the effectiveness of normal images. To solve the proposed DA-PCA model, we propose an efficiently iterative algorithm and provide strict convergence analysis for it. Moreover, in the simulations, we conduct the reconstruction and classification experiments on several real datasets and the experimental results demonstrate the superb performance of our proposal.

Due to the multimodality of non-Gaussian data, traditional globality-preserved dimensionality reduction (DR) methods, such as linear discriminant analysis (LDA) and principal component analysis (PCA) are difficult to deal with. In this paper, we present a novel local DR framework via auto-optimized graph embedding to extract the intrinsic submanifold structure of multimodal data. Specifically, the proposed model seeks to learn an embedding space which can preserve the local neighborhood structure by constructing a k-nearest neighbors (kNNs) graph on data points. Different than previous works, our model employs the ℓ0-norm constraint and binary constraint on the similarity matrix to impose that there only be a k nonzero value in each row of the similarity matrix, which can ensure the k-connectivity in graph. More important, as the high-dimensional data probably contains some noises and redundant features, calculating the similarity matrix in the original space by using a kernel function is inaccurate. As a result, a mechanism of an auto-optimized graph is derived in the proposed model. Concretely, we learn the embedding space and similarity matrix simultaneously. In other words, the selection of neighbors is automatically executed in the optimal subspace rather than in the original space when the algorithm reaches convergence, which can alleviate the affect of noises and improve the robustness of the proposed model. In addition, four supervised and semi-supervised local DR methods are derived by the proposed framework which can extract the discriminative features while preserving the submanifold structure of data. Last but not least, since two variables need to be optimized simultaneously in the proposed methods, and the constraints on the similarity matrix are difficult to satisfy, which is an NP-hard problem. Consequently, an efficient iterative optimization algorithm is introduced to solve the proposed problems. Extensive experiments conducted on synthetic data and several real-world datasets have demonstrated the advantages of the proposed methods in robustness and recognition accuracy.

Hyperspectral anomaly detection (HAD) has drawn a significant attention of late due to its importance in many military and civilian applications. In this article, a fast hyperspectral anomaly detector that combines multiple features and isolation forest is proposed. This approach, which is based on the assumption that the anomalous pixels are more susceptible to isolation than the background pixels, consists of two main parts. First, the spectral, Gabor, extended morphological profile (EMP) and extended multiattribute profile (EMAP) features are extracted from the hyperspectral image (HSI). Next, the isolation forest of each feature is constructed using the subsampling strategy. This combination of multiple features can exploit both the spectral and spatial information of the HSI, thereby improving the anomaly detection performance significantly. Compared with eight state-of-the-art HAD methods, the experimental results on four real hyperspectral data sets demonstrate that the performance of our proposed approach is quite competitive in terms of detection accuracy and running time.

Dimensionality reduction plays a significant role in high-dimensional data processing, and Linear Discriminant Analysis (LDA) is a widely used supervised dimensionality reduction approach. However, a major drawback of LDA is that it is incapable of extracting the local structure information, which is crucial for handling multimodal data. In this article, we propose a novel supervised dimensionality reduction method named Adaptive Local Linear Discriminant Analysis (ALLDA), which adaptively learns a k -nearest neighbors graph from data themselves to extract the local connectivity of data. Furthermore, the original high-dimensional data usually contains noisy and redundant features, which has a negative impact on the evaluation of neighborships and degrades the subsequent classification performance. To address this issue, our method learns the similarity matrix and updates the subspace simultaneously so that the neighborships can be evaluated in the optimal subspaces where the noises have been removed. Through the optimal graph embedding, the underlying sub-manifolds of data in intra-class can be extracted precisely. Meanwhile, an efficient iterative optimization algorithm is proposed to solve the minimization problem. Promising experimental results on synthetic and real-world datasets are provided to evaluate the effectiveness of proposed method.

Semi-supervised learning models for multiview data are important in image classification tasks, since heterogeneous features are easy to obtain and semi-supervised schemes are economical and effective. To model the view importance, conventional graph-based multiview learning models learn a linear combination of views while assuming a priori weights distribution. In this paper, we present a novel structural regularized semi-supervised model for multiview data, termed Adaptive MUltiview SEmi-supervised model (AMUSE). Our new model learns weights from a priori graph structure, which is more reasonable than weight regularization. Theoretical analysis reveals the significant difference between AMUSE and the prior arts. An efficient optimization algorithm is provided to solve the new model. Experimental results on six real-world data sets demonstrate the effectiveness of the structural regularized weights learning scheme.

In many real-world applications, we are often confronted with high dimensional data which are represented by various heterogeneous views. How to cluster this kind of data is still a challenging problem due to the curse of dimensionality and effectively integration of different views. To address this problem, we propose two parameter-free weighted multi-view projected clustering methods which perform structured graph learning and dimensionality reduction simultaneously. We can use the obtained structured graph directly to extract the clustering indicators, without performing other discretization procedures as previous graph-based clustering methods have to do. Moreover, two parameter-free strategies are adopted to learn an optimal weight for each view automatically, without introducing a regularization parameter as previous methods do. Extensive experiments on several public datasets demonstrate that the proposed methods outperform other state-of-the-art approaches and can be used more practically.

As the captured information in our real word is very scare and labeling sample is time cost and expensive, semisupervised learning (SSL) has an important application in computer vision and machine learning. Among SSL approaches, a graph-based SSL (GSSL) model has recently attracted much attention for high accuracy. However, for most traditional GSSL methods, the large-scale data bring higher computational complexity, which acquires a better computing platform. In order to dispose of these issues, we propose a novel approach, bipartite GSSL normalized (BGSSL-normalized) method, in this paper. This method consists of three parts. First, the bipartite graph between the original data and the anchor points is constructed, which is parameter-insensitive, scale-invariant, naturally sparse, and simple operation. Then, the label of the original data and anchors can be inferred through the graph. Besides, we extend our algorithm to handle out-of-sample for large-scale data by the inferred label of anchors, which not only retains good classification result but also saves a large amount of time. The computational complexity of BGSSL-normalized can be reduced to O(ndm +nm2), which is a significant improvement compared with traditional GSSL methods that need O(n2d + n3), where n, d, and m are the number of samples, features, and anchors, respectively. The experimental results on several publicly available data sets demonstrate that our approaches can achieve better classification accuracy with less time costs.

Many modern clustering models can be divided into two separated steps, i.e., constructing a similarity graph (SG) upon samples and partitioning each sample into the corresponding cluster based on SG. Therefore, learning a reasonable SG has become a hot issue in the clustering field. Many previous works that focus on constructing better SG have been proposed. However, most of them follow an ideal assumption that the importance of different features is equal, which is not adapted in practical applications. To alleviate this problem, this article proposes a self-weighted clustering with adaptive neighbors (SWCAN) model that can assign weights for different features, learn an SG, and partition samples into clusters simultaneously. In experiments, we observe that the SWCAN can assign weights for different features reasonably and outperform than comparison clustering models on synthetic and practical data sets.

This paper addresses the subspace clustering problem based on low-rank representation. Combining with the idea of co-clustering, we proposed to learn an optimal structural bipartite graph. It's different with other classical subspace clustering methods which need spectral clustering as post-processing on the constructed graph to get the final result, our method can directly learn a structural graph with k connected components so that the different clusters are obtained easily. Furthermore, we introduce a regularization term of error matrix to our model which helps the proposed algorithm to be more effective to learn an optimal graph under the circumstances of various noise. Experimental results both on synthetic and benchmark datasets are presented to show the effectiveness and robustness of our model.

Recently, graph-based unsupervised feature selection algorithms (GUFS) have been shown to efficiently handle prevalent high-dimensional unlabeled data. One common drawback associated with existing graph-based approaches is that they tend to be time-consuming and in need of large storage, especially when faced with the increasing size of data. Research has started using anchors to accelerate graph-based learning model for feature selection, while the hard linear constraint between the data matrix and the lower-dimensional representation is usually overstrict in many applications. In this letter, we propose a flexible linearization model with anchor graph and [Formula: see text]-norm regularization, which can deal with large-scale data sets and improve the performance of the existing anchor-based method. In addition, the anchor-based graph Laplacian is constructed to characterize the manifold embedding structure by means of a parameter-free adaptive neighbor assignment strategy. An efficient iterative algorithm is developed to address the optimization problem, and we also prove the convergence of the algorithm. Experiments on several public data sets demonstrate the effectiveness and efficiency of the method we propose.

Hyperspectral image (HSI) clustering is very important in remote sensing applications. However, most graph-based clustering models are not suitable for dealing with large HSI due to their computational bottlenecks: the construction of the similarity matrix W, the eigenvalue decomposition of the graph Laplacian matrix L, and k-means or other discretization procedures. To solve this problem, we propose a novel approach, scalable graph-based clustering with nonnegative relaxation (SGCNR), to cluster the large HSI. The proposed SGCNR algorithm first constructs an anchor graph and then adds the nonnegative relaxation term. With this, the computational complexity can be reduced to O(ndlogm + nK2+ nKc + K3), compared with traditional graph-based clustering algorithms that need at least O(n2d + n2K) or O(n2d + n3), where n, d, m, K, and c are, respectively, the number of samples, features, anchors, classes, and nearest neighbors. In addition, the SGCNR algorithm can directly obtain the clustering indicators, without resort to k-means or other discretization procedures as traditional graphbased clustering algorithms have to do. Experimental results on several HSI data sets have demonstrated the efficiency and effectiveness of the proposed SGCNR algorithm.

The large-scale hyperspectral image (HSI) clustering problem has attracted significant attention in the field of remote sensing. Most traditional graph-based clustering methods still face challenges in the successful application of the large-scale HSI clustering problem mainly due to their high computational complexity. In this letter, we propose a novel approach, called fast spectral clustering with anchor graph (FSCAG), to efficiently deal with the large-scale HSI clustering problem. Specifically, we consider the spectral and spatial properties of HSI in the anchor graph construction. The proposed FSCAG algorithm first constructs anchor graph and then performs spectral analysis on the graph. With this, the computational complexity can be reduced to O(ndm), which is a significant improvement compared to conventional graph-based clustering methods that need at least O(n2d), where n, d, and m are the number of samples, features, and anchors, respectively. Several experiments are conducted to demonstrate the efficiency and effectiveness of the proposed FSCAG algorithm.

The locality preserving projections (LPP) algorithm is a recently developed linear dimensionality reduction algorithm that has been frequently used in face recognition and other applications. However, the projection matrix in LPP is not orthogonal, thus creating difficulties for both reconstruction and other applications. As the orthogonality property is desirable, orthogonal LPP (OLPP) has been proposed so that an orthogonal projection matrix can be obtained based on a step by step procedure; however, this makes the algorithm computationally more expensive. Therefore, in this paper, we propose a fast and orthogonal version of LPP, called FOLPP, which simultaneously minimizes the locality and maximizes the globality under the orthogonal constraint. As a result, the computation burden of the proposed algorithm can be effectively alleviated compared with the OLPP algorithm. Experimental results on two face recognition data sets and two hyperspectral data sets are presented to demonstrate the effectiveness of the proposed algorithm.

Block principal component analysis with ℓ1-norm (BPCA-L1) has demonstrated its effectiveness in a lot of visual classification and data mining tasks. However, the greedy strategy for solving the ℓ1-norm maximization problem is prone to being struck in local solutions. In this paper, we propose a BPCA with nongreedy ℓ1-norm maximization, which obtains better solutions than BPCA-L1 with all the projection directions optimized simultaneously. Other than BPCA-L1, the new algorithm has been evaluated against some popular principal component analysis (PCA) algorithms including PCA-L1 and 2-D PCA-L1 on a variety of benchmark data sets. The results demonstrate the effectiveness of the proposed method.

2-D principal component analysis based on l1 -norm (2DPCA-L1) is a recently developed approach for robust dimensionality reduction and feature extraction in image domain. Normally, a greedy strategy is applied due to the difficulty of directly solving the l1 -norm maximization problem, which is, however, easy to get stuck in local solution. In this paper, we propose a robust 2DPCA with non-greedy l1 -norm maximization in which all projection directions are optimized simultaneously. Experimental results on face and other datasets confirm the effectiveness of the proposed approach.

In this letter, a stable and orthonormal version of the OJA algorithm (SOOJA) is investigated for principal and minor subspace extraction and tracking. The new algorithm presented here guarantees the orthonormality of the weight matrix at each iteration through a novel orthonormalization method. Moreover, it obtains both a high numerical stability and a low computational complexity. The superiority of the proposed algorithm to some existing subspace tracking algorithms is demonstrated using a classical example. Simulation results confirm the veracity of the subspace tracking algorithm advocated.