Graph Construction and b-Matching for Semi-supervised Learning

by Tony Jebara, Jun Wang and Shi-fuh Chang

This is an ``advertisement'' paper for their 2007 paper on b-matching. In general b-matching is a graph construction algorithm as k-NN. This paper enumerate all kinds of combinations of label diffusion (propagation?):

• graph construction, kNN and b-matching
• weight, Gaussian kernel, LLR (like LLE).
• diffusion algorithms, GRF, LGC and GTAM.

I don't buy their conclusion. Yes graph construction might be important to later algorithms, but the b-matching result doesn't seem so different from k-NN. Maybe we have to try for ourselves.