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

Proceedings of the Fifteenth Conference on Computational Natural Language Learning, pages 154–162, Portland, Oregon, USA, 23–24 June 2011. c⃝2011 Association for Computational Linguistics Using the Mutual k-Nearest Neighbor Graphs for Semi-supervised Classification of Natural Language Data Kohei Ozaki and Masashi Shimbo and Mamoru Komachi and Yuji Matsumoto Nara Institute of Science and Technology 8916-5 Takayama, Ikoma, Nara 630-0192, Japan {kohei-o,shimbo,komachi,matsu}@is.naist.jp Abstract 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 mak- ing hub vertices. The mutual k-nearest neigh- bor graphs also perform equally well or even better in comparison to the state-of-the-art b-matching graph construction, despite their lower computational complexity. 1 Introduction Semi-supervised classification try to take advan- tage of a large amount of unlabeled data in addi- tion to a small amount of labeled data, in order to achieve good classification accuracy while reducing the cost of manually annotating data. In particular, graph-based techniques for semi-supervised classi- fication (Zhou et al., 2004; Zhu et al., 2003; Cal- lut et al., 2008; Wang et al., 2008) are recognized as a promising approach. Some of these techniques have been successfully applied for NLP tasks: word sense disambiguation (Alexandrescu and Kirchhoff, 2007; Niu et al., 2005), sentiment analysis (Gold- berg and Zhu, 2006), and statistical machine trans- lation (Alexandrescu and Kirchhoff, 2009), to name but a few. However, the focus of these studies is how to as- sign accurate labels to vertices in a given graph. By contrast, there has not been much work on how such a graph should be built, and graph construction re- mains “more of an art than a science” (Zhu, 2005). Yet, it is an essential step for graph-based semi- supervised classification and (unsupervised) cluster- ing, and the input graph affects the quality of final classification/clustering results. Both for semi-supervised classification and for clustering, the k-nearest neighbor (k-NN) graph construction has been used almost exclusively in the literature. However, k-NN graphs often produce hubs, or vertices with extremely high degree (i.e., the number of edges incident to a vertex). This ten- dency is obvious especially if the original data is high-dimensional—a characteristic typical of natu- ral language data. In a later section, we demonstrate that such hub vertices indeed deteriorate the accu- racy of semi-supervised classification. While not in the context of graph construction, Radovanovi´c et al. (2010) made an insightful obser- vation into the nature of hubs in high-dimensional …

Content truncated to 500 words