  We propose a method to efficiently construct data-dependent kernels which can
make use of large quantities of (unlabeled) data. Our construction makes an
approximation in the standard construction of semi-supervised kernels in
Sindhwani et al. 2005. In typical cases these kernels can be computed in
nearly-linear time (in the amount of data), improving on the cubic time of the
standard construction, enabling large scale semi-supervised learning in a
variety of contexts. The methods are validated on semi-supervised and
unsupervised problems on data sets containing upto 64,000 sample points.
