Paper: Using the Mutual k-Nearest Neighbor Graphs for Semi-supervised Classification on Natural Language Data

ACL ID W11-0318
Title Using the Mutual k-Nearest Neighbor Graphs for Semi-supervised Classification on Natural Language Data
Venue International Conference on Computational Natural Language Learning
Session Main Conference
Year 2011
Authors

The first step in graph-based semi-supervised classification is to construct a graph from in- put data. While the k-nearest neighbor graphs have been the de facto standard method of graph construction, this paper advocates using the less well-known mutual k-nearest neigh- bor graphs for high-dimensional natural lan- guage data. To compare the performance of these two graph construction methods, we run semi-supervised classification methods on both graphs in word sense disambiguation and document classification tasks. The experi- mental results show that the mutual k-nearest neighbor graphs, if combined with maximum spanning trees, consistently outperform the k- nearest neighbor graphs. We attribute better performance of the mutual k-nearest neigh- bor graph to its being more resistive to m...