Capped $l_1$ -Norm Sparse Representation Method for Graph Clustering

Mulin Chen, Qi Wang, Shangdong Chen, Xuelong LiIEEE Access 2019 · OpenReview

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$.

Clustering accuracy (ACC) as a function of log(gamma), showing the stability of the CSR method across different parameter values.

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.

Similarity matrix generated by the CAN method, illustrating the baseline level of noise in state-of-the-art graph clustering.

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

Abstract

As one of the most popular clustering techniques, graph clustering has attracted many researchers in the field of machine learning and data mining. Generally speaking, graph clustering partitions the data points into different categories according to their pairwise similarities. Therefore, the clustering performance is largely determined by the quality of the similarity graph. The similarity graph is usually constructed based on the data points' distances. However, the data structure may be corrupted by outliers. To deal with the outliers, we propose a capped l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -norm sparse representation method (CSR) in this paper. The main contribution of this paper is threefold: 1) a similarity graph with clear cluster structure is learned by employing sparse representation with proper constraints; (2) the capped l <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> -norm loss is utilized to remove the outliers, which ensures the graph quality; and 3) an iterative algorithm is developed to optimize the proposed non-convex problem. The extensive experiments on real-world datasets show the superiority of the proposed method over the state-of-the-art, and demonstrate its robustness to the outliers.
BibTeX
@inproceedings{chen2019capped,
  author = {Mulin Chen and Qi Wang and Shangdong Chen and Xuelong Li},
  title = {{Capped $l\_1$ -Norm Sparse Representation Method for Graph Clustering}},
  booktitle = {IEEE Access},
  year = {2019},
  url = {https://openreview.net/forum?id=1JYeD-3Qnf},
}
Figure