Graph Kernels by Spectral Transforms
Zhu Xiaojin, Kandola Jaz, L. John, Zoubin Ghahramani · The MIT Press eBooks · 2006
This chapter develops an approach to searching over a nonparametric family of spectral transforms by using convex optimization to maximize kernel alignment to the labeled data. Order constraints are imposed to encode a preference for smoothness with respect to the graph structure. This results in a flexible family of kernels that is more data-driven than the standard parametric spectral transforms. This approach relies on a quadratically constrained quadratic program (QCQP) and is computationally practical for large data sets. Many graph-based semi-supervised learning methods can be viewed as imposing smoothness conditions on the target function with respect to a graph representing the data points to be labeled. The smoothness properties of the functions are encoded in terms of Mercer kernels over the graph. The central quantity in such regularization is the spectral decomposition of the graph Laplacian, a matrix derived from the graph’s edge weights.