Source-linked AI summary
Low-rank Kernel Learning for Graph-based Clustering
Zhao Kang, Liangjian Wen, Wenyu Chen, Zenglin Xu
TL;DR
Kernel-based graph clustering depends strongly on the chosen kernel, while multiple-kernel approaches remain vulnerable to corrupted candidates and limited representation. The paper jointly learns a low-rank consensus kernel and similarity graph, allowing the kernel to lie near candidate kernels and the two learning processes to enhance each other. Experiments and document-clustering results report improved performance over existing clustering techniques.
Problem
Kernel-based clustering is highly dependent on the chosen kernel, while candidate kernels may be corrupted by noise and outliers and linear combinations can limit consensus-kernel representation.
Method
The method jointly learns a low-rank consensus kernel and similarity graph, allowing the kernel to reside in the neighborhood of candidate kernels rather than enforcing a linear combination.
Results
The method improves clustering performance compared with existing clustering techniques, including in document clustering experiments.
Takeaways & Limitations
Graph construction and kernel learning are unified so that each learned similarity representation can improve the other.
Takeaways & Limitations
The approach is motivated by candidate kernels that can be corrupted by noise and outliers and by the limited representation of linear-combination consensus kernels.
Abstract
from arXiv · showhide
Constructing the adjacency graph is fundamental to graph-based clustering. Graph learning in kernel space has shown impressive performance on a number of benchmark data sets. However, its performance is largely determined by the chosen kernel matrix. To address this issue, the previous multiple kernel learning algorithm has been applied to learn an optimal kernel from a group of predefined kernels. This approach might be sensitive to noise and limits the representation ability of the consensus kernel. In contrast to existing methods, we propose to learn a low-rank kernel matrix which exploits the similarity nature of the kernel matrix and seeks an optimal kernel from the neighborhood of candidate kernels. By formulating graph construction and kernel learning in a unified framework, the graph and consensus kernel can be iteratively enhanced by each other. Extensive experimental results validate the efficacy of the proposed method.
1. Introduction
The paper addresses kernel dependence in graph-based clustering by jointly learning a similarity graph and a consensus kernel. It uses low-rank structure and searches beyond strict linear combinations of candidate kernels, with experiments reporting superior clustering performance.
- Motivation: Kernel K-means requires a kernel matrix whose choice assumes an often-unknown data distribution, making performance highly dependent on kernel selection.Multiple kernel learning partly addresses selection by combining candidate kernels, but noise and outliers can corrupt them.
- Motivation: Similarity-graph quality is crucial for spectral clustering, while Gaussian-kernel parameter selection remains open and the kernel is sensitive to noise and outliers.Automatic graph-learning methods can handle structures with different scales and densities and often provide high-quality graphs.
- Proposed approach: The proposed method learns the graph in kernel space and develops a consensus kernel to reduce dependence on a prespecified kernel.The unified model integrates graph learning and kernel learning so each learned object can improve the other through their shared pairwise-similarity nature.
- Proposed approach: A low-rank regularizer exploits the underlying structure of the kernel matrix and allows the suitable kernel to lie in the neighborhood of base kernels.This avoids enforcing the optimal kernel to be only a linear combination of predefined kernels and is intended to improve robustness when candidate kernels are corrupted.
- Contributions: The unified model learns an optimal consensus kernel and similarity graph while using one task’s result to improve the other.The contribution is framed as a mutual negotiation between graph construction and kernel learning.
- Evaluation: Extensive experiments compare the method with existing state-of-the-art clustering methods and report superior performance.The conclusion states that document-clustering experiments improve performance compared with existing clustering techniques.
2. Related Work
Prior graph and kernel-learning methods construct similarities or consensus kernels from predefined kernels, but linear-combination constraints can limit representation and robustness. The proposed direction jointly learns a graph and a low-rank kernel while allowing the ideal kernel to lie near, rather than exactly within, candidate kernels.
- Multiple kernel learning: RMKKM learns a robust consensus kernel as a linear combination of multiple candidate kernels to integrate complementary information.Its robust formulation addresses noise and outliers in kernel learning.
- Graph-based learning: Self-expression methods learn affinity weights that encode relationships among samples and then use the affinity graph for spectral clustering.Kernel-space extensions jointly construct similarity matrices and learn cluster labels.
- Limitations: Linear combinations of predefined kernels ignore kernel structure and can limit the representation ability of the optimal kernel.The restriction is problematic when real data are corrupted or the ideal kernel lies near, rather than exactly at, the combined kernel.
- Limitations: Designing a large kernel pool is time-consuming, so predefined candidates cannot generally guarantee a globally optimal kernel.The practical objective is therefore to make better use of candidate kernels.
- Proposed direction: The proposed framework jointly learns a similarity graph and kernel matrix using low-rank structure, enlarging the search region around candidate kernels.The combined kernel is factorized into a low-rank optimal component and a residual, and graph and kernel learning are unified.
3. Proposed Methodology
The method learns a graph and consensus kernel together by combining kernel-space self-expression, low-rank regularization, and a neighborhood-based multiple-kernel formulation. Alternating optimization updates the graph, kernel, auxiliary variables, and kernel weights before spectral clustering is applied to the learned graph.
- Formulation: Kernel-space self-expression models linear relationships among samples in feature space, corresponding to nonlinear relationships in the original representation.The model uses the kernel matrix to construct a graph representation.
- Formulation: Kernel weights combine candidate kernels while allowing the optimal kernel to lie in their neighborhood rather than requiring an exact linear combination.A corrupted or inappropriate kernel receives a small weight, while the residual separates noise from the low-rank component.
- Formulation: The learned kernel K is regularized with a nuclear norm so it captures sample correlations and is robust to noise and errors.The low-rank structure reflects the cluster structure encoded by pairwise similarities.
- Optimization: The unified model repeatedly improves graph coefficients, the kernel, and kernel weights by alternating their updates.This formulation reinforces the connection between optimal-kernel learning and graph learning.
- Clustering: After graph learning, spectral clustering is applied to Z to obtain the final cluster labels.The learned graph can also support semi-supervised classification, although this work focuses on clustering.
REPEAT
The algorithm alternates graph, kernel, auxiliary-variable, weight, and multiplier updates until a stopping criterion is met. Its dominant computations are cubic in the number of samples, with partial SVD offering a lower-cost low-rank alternative.
- Algorithm: The update cycle calculates Z, updates K, computes J, calculates W, solves for g, and updates Lagrange multipliers.The procedure repeats these steps until the stopping criterion is met.
- Complexity: O(n^3) is the computational cost for Z and K, while W also costs O(n^3) because each iteration requires an SVD.Partial SVD can reduce the W cost to O(kn^2), where k is the lowest rank found.
- Complexity: O(n^2) is the complexity of sparse J updates, and the kernel-construction cost is O(n^2).The g subproblem is polynomial-time quadratic programming, with size determined by the small number r of kernels.
4. Experiments
The experiments evaluate graph-based clustering across image, text, and multi-view benchmark data using accuracy and multiple clustering metrics. Results indicate that low-rank kernel learning performs strongly across benchmarks and remains effective over a wide parameter range.
- Data sets: The study evaluates eight real-world benchmark data sets, including image data sets and text corpora.The first five data sets are images, while the remaining four are text corpora.
- Evaluation metrics: The evaluation uses accuracy, normalized mutual information, F-score, Precision, Recall, ARI, Entropy, and Purity to characterize clustering performance.Accuracy measures cluster-to-class correspondence, while NMI measures clustering quality.
- Benchmark results: LKG achieves the best performance among all state-of-the-art algorithms on the benchmark comparison.The experiments compare single-kernel, multiple-kernel, and graph-based clustering methods.
- Statistical significance: LKGs and LKGr outperform KKM, SC, RKKM, SSR, MKKM, AASC, and RMKKM with statistical significance.Wilcoxon tests produce p-values below 0.05 against these methods, except SCSK and SCMK.
- Parameter sensitivity: LKGr gives reasonable accuracy across a wide range of β and γ values on YALE, JAFFE, and ORL.The sensitivity study fixes α and varies β and γ across several orders of magnitude.
- Multi-view evaluation: On multi-view data, the proposed approach performs better than other baselines on most measures.The multi-view evaluation uses Cora and NUS-WIDE, with repeated runs for LKGs and LKGr.
5. Conclusion
The paper proposes a multiple-kernel graph-clustering method that learns a low-rank consensus kernel near the combined kernel. Experiments on image and document clustering show improved performance over existing clustering techniques.
- Method: The proposed method unifies graph construction and kernel learning through a multiple-kernel graph-clustering framework.The unified formulation allows graph learning and kernel learning to be treated together.
- Method: The consensus kernel is explicitly constrained to be low-rank and lie near the combined kernel.This design differs from existing multiple-kernel learning methods.
- Method: The learned graph is described as more informative and discriminative for data affected by noise and outliers.The conclusion links this property to the low-rank kernel-learning approach.
- Results: Experiments on image and document clustering show improved performance compared with existing clustering techniques.The reported evaluation covers both image clustering and document clustering.