Abstract
Graph clustering is a popular technique in machine learning that partitions data points based on pairwise similarities. However, the quality of the similarity graph is often compromised by outliers. We propose a Capped $l_1$-Norm Sparse Representation (CSR) method to address this. By employing a capped $l_1$-norm loss, CSR effectively removes the influence of extreme outliers. Additionally, a structural rank constraint is used to learn a similarity graph with a clear cluster structure, eliminating the need for traditional post-processing. Extensive experiments demonstrate CSR's superiority and robustness compared to state-of-the-art methods.
Introduction
The performance of graph clustering is largely determined by the quality of the similarity graph, which is typically constructed based on data point distances. A major challenge in this field is the presence of outliers that can corrupt the data structure. Standard loss functions, such as quadratic loss, are highly sensitive to these outliers. Even robust norms like $l_1$ only mitigate their influence rather than eliminating it. CSR aims to create a truly robust method that ignores extreme outliers while simultaneously learning a graph with a mathematically guaranteed cluster structure.
Methodology
The CSR method introduces three key innovations to improve graph clustering:
Capped $l_1$-Norm Loss
Unlike standard $l_1$ norms, the capped version uses a threshold $\epsilon$. If a data point's reconstruction error exceeds this threshold, it is flagged as an outlier, and its error is "capped" at a constant value. This prevents extreme outliers from dominating the objective function and pulling the model out of alignment.
Adaptive Sparse Representation
The model learns the similarity graph by representing each data point as a linear combination of others. This captures the local manifold structure of the data more effectively than simple distance metrics.
Structural Rank Constraint
CSR incorporates a constraint on the Laplacian matrix of the graph. By forcing the Laplacian to have a specific number of zero eigenvalues, the resulting graph is guaranteed to have exactly $c$ connected components (where $c$ is the number of clusters). This means the clustering is "built-in" to the graph learning process, removing the need for $k$-means.
Experimental Results
CSR was evaluated on eight diverse real-world benchmark datasets, including face datasets (Jaffe, Extended Yale B), digit datasets (USPS, MNIST), and biological data (Lung).
Performance and Robustness
CSR consistently achieved the highest Clustering Accuracy (ACC) and Normalized Mutual Information (NMI). For instance, on the Jaffe dataset, CSR achieved an ACC of 0.9671. In explicit outlier tests (Jaffe + Caltech101), CSR maintained an ACC of 0.9712, while other robust methods like RASL dropped to 0.7728.
Parameter Sensitivity
The method demonstrates stability across a range of the $\gamma$ parameter, which balances reconstruction error and graph sparsity. As shown in Figure 5, the accuracy remains high and stable across several orders of magnitude for $\gamma$.
Visual Clarity
Visualization of the learned similarity graphs shows that CSR produces much "cleaner" graphs with very few connections between different clusters compared to competitors. Figure 6 shows the similarity matrix for the CAN method, which exhibits more noise and inter-cluster connections than the results achieved by CSR.
Conclusion
The Capped $l_1$-Norm Sparse Representation method offers a robust and effective approach to graph clustering. By "ignoring" rather than just penalizing extreme outliers and enforcing a structural rank constraint, CSR learns high-quality similarity graphs that directly reveal cluster structures. Future research will explore automated threshold selection and further optimization for large-scale datasets.
Summary updated