Graph-Based Learning via Auto-Grouped Sparse Regularization and Kernelized Extension
Yuqiang Fang, Ruili Wang, Bin Dai, Xindong Wu · IEEE Transactions on Knowledge and Data Engineering · 2014
The key task in developing graph-based learning algorithms is constructing an informative graph to express the contextual information of a data manifold. Since traditional graph construction methods are sensitive to noise and less datum-adaptive to changes in density, a new method called$\ell^1$-graph was proposed recently. A graph construction needs to have two important properties: sparsity and locality. The$\ell^1$-graph has a strong sparsity property, but a weak locality property. Thus, we propose a new method of constructing an informative graph using auto-grouped sparse regularization based on the$\ell^1$-graph, which is called as Group Sparse graph (GS-graph). We also show how to efficiently construct a GS-graph in reproducing kernel Hilbert space with the kernel trick. The new methods, the GS-graph and its kernelized version (KGS-graph), have the same noise-insensitive property as that of$\ell^1$-graph and also can successively preserve the properties of sparsity and locality simultaneously. Furthermore, we integrate the proposed graph with several graph-based learning algorithms to demonstrate the effectiveness of our method. The empirical studies on benchmarks show that the proposed methods outperform the$\ell^1$-graph and other traditional graph construction methods in various learning tasks.