Structured Graph Learning for Clustering and Semi-supervised Classification

Zhao Kang; Chong Peng; Qiang Cheng; Xinwang Liu; Xi Peng; Zenglin Xu; Ling Tian

Source-linked AI summary

Structured Graph Learning for Clustering and Semi-supervised Classification

Zhao Kang, Chong Peng, Qiang Cheng, Xinwang Liu, Xi Peng, Zenglin Xu, Ling Tian

arXiv:2008.13429v1Aug 31, 2020cs.LGcs.AIcs.CVstat.ML

TL;DR

Graph construction and refinement pose a major challenge. The paper proposes an iterative graph-learning framework whose components are mutually reinforced, with theoretical connections to kernel k-means, k-means, and spectral clustering; experiments show high potential in real-world applications.

Problem
Refining the graph used in graph-based learning poses a major challenge.
Method
The framework iteratively learns graph components that are mutually reinforced and is theoretically connected to kernel k-means, k-means, and spectral clustering.
Results
Experiments show the method has high potential for real-world applications.
Takeaways & Limitations
The framework jointly improves its graph-learning components through iterative mutual reinforcement.
Takeaways & Limitations
The proposed approach has high time complexity, motivating future work on computational improvements.

Abstract

from arXiv · show

Graphs have become increasingly popular in modeling structures and interactions in a wide variety of problems during the last decade. Graph-based clustering and semi-supervised classification techniques have shown impressive performance. This paper proposes a graph learning framework to preserve both the local and global structure of data. Specifically, our method uses the self-expressiveness of samples to capture the global structure and adaptive neighbor approach to respect the local structure. Furthermore, most existing graph-based methods conduct clustering and semi-supervised classification on the graph learned from the original data matrix, which doesn't have explicit cluster structure, thus they might not achieve the optimal performance. By considering rank constraint, the achieved graph will have exactly $c$ connected components if there are $c$ clusters or classes. As a byproduct of this, graph learning and label inference are jointly and iteratively implemented in a principled way. Theoretically, we show that our model is equivalent to a combination of kernel k-means and k-means methods under certain condition. Extensive experiments on clustering and semi-supervised classification demonstrate that the proposed method outperforms other state-of-the-art methods.

1. Introduction

The paper develops a graph-learning framework that combines local and global structure while imposing explicit cluster structure and jointly learning graphs and labels. It targets limitations in graph construction for clustering and semi-supervised classification, with experiments reporting advantages over state-of-the-art methods.

Motivation and framework: Graph construction is critical because the learned graph underlies subsequent clustering or label inference, yet its unknown data structure can cause suboptimal performance.Existing graph-based methods first construct an affinity graph and then apply spectral clustering or label propagation.
Motivation and framework: The framework combines local adaptive neighbors with global self-expressiveness to learn a similarity graph from complementary structure information.Local and global information are described as complementary, and the framework unifies them for graph learning.
Structured graph learning: The method imposes a rank constraint so the learned graph has exactly c connected components when the data contain c clusters or classes.The paper presents this explicit cluster structure as a requirement that many existing methods do not incorporate.
Joint learning: Graph learning and label inference are integrated into a unified objective, allowing their results to mutually reinforce one another instead of using separate stages.The framework is presented as jointly and iteratively learning the graph and labels.
Theory and evaluation: Theoretical analysis connects the model to kernel k-means, k-means, and spectral clustering, while experiments report effectiveness and advantages over state-of-the-art clustering and semi-supervised classification methods.The paper also extends the framework to simultaneously learn a graph, labels, and an optimal combination of multiple kernels.

2. Structured Graph Learning with Single Kernel

The single-kernel framework combines local adaptive-neighbor structure with global self-expressive structure, then imposes graph connectivity constraints to encode cluster structure.

2.1. Local Structure Learning: The local graph assigns larger similarity to nearby samples and characterizes pairwise sample relationships.Its adaptive-neighbor formulation allows neighborhoods to change during optimization.
2. Structured Graph Learning with Single Kernel: The framework combines adaptive-neighbor learning for local structure with self-expressiveness for global relationships.The resulting graph is intended to preserve complementary local and global information.
2.2. Global Structure Learning: Self-expressiveness captures global relationships but assumes data lie in a union of subspaces, limiting performance on unions of manifolds in raw space.Mapping nonlinear data into an implicit higher-dimensional space is used to recover nonlinear relationships.
2.3. Structured Graph Learning: The desired graph has exactly c connected components for c clusters or classes, with each component corresponding to one class.This is enforced through rank(L) = n −c, using the Laplacian’s zero-eigenvalue multiplicity.
2.4. Optimization: The coupled optimization alternates graph and cluster/label updates, with P obtained from the c smallest eigenvectors of the Laplacian.The formulation replaces the difficult rank constraint with an equivalent optimization involving P and Z.

REPEAT

The algorithm alternates updates of the cluster representation and graph, adaptively changes neighbors, and converges through monotonic objective decrease while selecting sparsity through α.

REPEAT: Nearest neighbors change at each iteration, so the method learns neighborhoods adaptively rather than fixing them beforehand.The update can be solved in parallel with quadratic programming packages.
REPEAT: The optimization alternates between updating P and Z, using cluster structure to guide graph learning and graph structure to guide clustering.The objective decreases monotonically and the bounded objective therefore converges.
REPEAT: The parameter α controls the balance between the trivial solution and uniform distribution, while sparse local learning connects each point to its k nearest neighbors.The proposed parameter rule searches neighborhood size k instead of tuning α blindly.
REPEAT: The selected α range ensures each row has exactly k nonzero components, and the average row sparsity is close to k when α is set to its mean value.This provides a practical way to determine the neighborhood size.

3. Theoretical Connection

Theoretical analysis connects the learned graph to spectral clustering and shows that, as α grows, the model becomes a combination of kernel k-means and k-means.

3.1. Connection to Kernel K-means and K-means Clustering: When α →∞, the proposed model is equivalent to a combination of kernel k-means and k-means problems.For finite α, it is described as a generalization of both methods that can partition data of arbitrary shape.
3.2. Connection to Spectral Clustering: The rank constraint makes the similarity graph block diagonal, with each block representing one connected component.Within a component, the solution assigns all graph elements the same value 1/n_i.
3.1. Connection to Kernel K-means and K-means Clustering: The first term of the formulation is exactly kernel k-means, while the second term is exactly the k-means problem.The kernel-space representation supplies the kernel k-means component, and the remaining term corresponds to within-class scatter minimization.
3.2. Connection to Spectral Clustering: Unlike conventional spectral clustering, the method learns Z together with P and incorporates cluster or class structure instead of using a fixed graph.The paper states that this coupled learning collaboratively improves both variables.

4. Structured Graph Learning with Multiple Kernel

The multiple-kernel extension learns a suitable or consensus kernel jointly with the graph and cluster representation, avoiding exhaustive kernel selection.

4. Structured Graph Learning with Multiple Kernel: The multiple-kernel extension constructs a consensus kernel from a pool of predefined kernels.This addresses the dependence of kernel methods on kernel selection and the impracticality of exhaustive search.
4. Structured Graph Learning with Multiple Kernel: Replacing the single kernel with a weighted combined kernel yields the proposed structured graph learning model with multiple kernels.The combined feature map scales each kernel feature map by the square root of its weight.
4. Structured Graph Learning with Multiple Kernel: The method iteratively updates Z, P, and kernel weights w so each component is refined using the others’ results.With fixed w, the algorithm updates Z and P using the combined kernel; with fixed Z and P, it solves for w.
4. Structured Graph Learning with Multiple Kernel: Algorithm 2 provides the procedure for solving the multiple-kernel optimization from the input kernel matrices.Initialization sets the kernel weights uniformly at 1/r.

REPEAT

The framework jointly and iteratively learns graph structure and labels for semi-supervised classification. Its procedure updates graph, embedding, and labels until convergence while using labeled and estimated labels.

REPEAT: The multiple-kernel procedure alternates kernel, embedding, graph, and weight updates until a stopping criterion is met.It computes Kw, obtains P from the c smallest eigenvectors of the graph Laplacian, updates Z columnwise, then updates h and w.
REPEAT: SGMK unifies graph learning and label inference because solving the two stages separately leaves label information unused during graph construction.Given and estimated labels are used to build the graph and predict unknown labels.
REPEAT: The framework is reformulated for semi-supervised learning with a one-hot label matrix for the labeled samples.Each labeled sample has a class-indicator vector, and the label matrix contains l labeled points.
REPEAT: For semi-supervised classification, labeled samples are arranged before unlabeled samples and the class labels of unlabeled points are assigned using the learned representation.The method updates P differently for classification and then applies a decision rule to unlabeled points.

5. Clustering Experiments

The clustering experiments evaluate the proposed methods on eight public datasets using multiple kernels and standard clustering metrics. SGSK generally outperforms competing spectral, kernel k-means, and structure-specific methods, while combining local and global structure improves performance.

5. Clustering Experiments: The experiments use eight public datasets, 12 kernels, and accuracy, NMI, and Purity to assess clustering performance.The datasets include face, binary alpha digit, and TREC-derived document datasets.
5. Clustering Experiments: SGSK improves best accuracy over SC and RMMK by 42.95% and 36.01% on average, respectively.The comparison is reported for the best accuracy across the clustering experiments.
5. Clustering Experiments: SGSK performs best in most cases on YALE, JAFFE, ORL, and AR, outperforming spectral clustering and robust kernel k-means methods.Local- and global-structure methods also outperform SC and RKKM on these datasets.
5. Clustering Experiments: SGMK achieves much better results than MKKM, AASC, and RMKKM in the multiple-kernel setting.Multiple-kernel methods are reported as close to or better than their corresponding single-kernel methods.
5. Clustering Experiments: Removing local structure generally weakens SGMK, supporting the benefit of jointly incorporating local and global structure.The global-only component performs better than SGMK in several cases, showing that the relative contribution can vary by dataset.
5. Clustering Experiments: SGMK performs well across wide ranges of γ and k on YALE and JAFFE.The sensitivity experiments vary γ and neighborhood size k.

6. Semi-supervised Classification Experiments

The semi-supervised experiments evaluate SGMK on face, digit/letter, and visual-object recognition tasks with varying labeled-data proportions. SGMK generally outperforms other state-of-the-art methods, and accuracy increases as more samples are labeled.

6. Semi-supervised Classification Experiments: SGMK integrates local and global structure with a rank constraint to improve graph quality for semi-supervised classification.Its formulation jointly learns similarity information and class indicators.
6. Semi-supervised Classification Experiments: Methods that jointly conduct label prediction and graph learning often achieve better performance than methods using labels only during propagation.The comparison includes GFHF, LGC, SCAN, S2LRR, S3R, and SGMK.
6. Semi-supervised Classification Experiments: Classification accuracy increases monotonically as the percentage of labeled samples rises.The experiments use 10%, 30%, and 50% labeled samples from each class.
6. Semi-supervised Classification Experiments: SGMK outperforms other state-of-the-art methods in general on the semi-supervised learning task.The result is reported for experiments using randomly selected labeled samples and repeated trials.
6. Semi-supervised Classification Experiments: SGMK's advantage over self-expressive and adaptive-neighbor baselines supports incorporating both global and local structure information.S2LRR and S3R capture global information, whereas SCAN is designed to reveal local structure.

7. Conclusion

The paper concludes with a graph-learning framework that jointly learns graph structure and labels while preserving local and global information. It also extends the approach to multiple kernels, but acknowledges high computational complexity as a limitation.

7. Conclusion: The framework iteratively learns the graph matrix and labels while incorporating both local and global structure information.A rank constraint on the graph Laplacian is used for clustering and classification.
7. Conclusion: The resulting unified model improves graph and label learning collaboratively and yields a more informative and discriminative graph.The conclusion connects the rank-constrained graph to clustering and classification tasks.
7. Conclusion: The multiple-kernel extension avoids extensive search for the most suitable kernel.The conclusion presents multiple-kernel learning as an extension of the framework.
7. Conclusion: Experiments indicate high potential for real-world applications.The conclusion summarizes the empirical evidence without specifying a single application domain.
7. Conclusion: High time complexity limits the proposed approach, motivating future efficiency improvements using anchor points.The proposed direction learns a graph between all data points and selected landmarks.