Graph-Based Semi-Supervised Learning - Introduction to Semi-Supervised Learning - page 54

54 CHAPTER 5. GRAPH-BASED SEMI-SUPERVISEDLEARNING
while neighborhoods across curves would be rotated 90 degrees. The resulting graph should avoid
inter-class edges. Results using a similar approach for several datasets like the one seen here can be
found in [ 75 ].
(a) 4-NN graph
(b) Harmonic function predictions
Figure 5.5: Graph-based semi-supervised learning using a bad graph can lead to poor performance.
This chapter introduced the notion of using a graph over labeled and unlabeled data to
perform semi-supervised learning. We discussed several algorithms that share the intuition that the
predictions should be smooth with respect to this graph. We introduced some notions from spectral
graph theory to justify this approach, and illustrated what can go wrong if the graph is not constructed
carefully. In the next chapter, we discuss semi-supervised support vector machines, which make a
very different assumption about the space containing the data.
BIBLIOGRAPHICAL NOTES
The idea of the target function being smooth on the graph, or equivalently regularization by the
graph, is very natural. Therefore, there are many related methods that exploit this idea, includ-
ing Mincut [ 21 ] and randomized Mincut [ 20 ], Boltzmann machines [ 70 , 209 ], graph random