Mutual k-Nearest Neighbor Graphs for Semi-Supervised Learning

Kohei Ozaki (0951027)

In graph-based semi-supervised learning, graph construction methods are known to influence performance and have gained increasing attention over the past few years. In this thesis, we investigate the effect of the hub nodes of a graph on classification tasks and propose a new efficient graph construction approach.

In natural language processing tasks, such as word sense disambiguation and document classification, we demonstrate that our proposed method outperforms the state-of-the-art graph construction methods in terms of prediction accuracy in most cases. In addition, we show the graph produced by our proposed method satisfies the cluster assumption better than other methods.