Journal
PATTERN RECOGNITION
Volume 45, Issue 4, Pages 1363-1372Publisher
ELSEVIER SCI LTD
DOI: 10.1016/j.patcog.2011.09.001
Keywords
Graph-based semi-supervised learning; Manifold assumption; Neighborhood graph construction
Ask authors/readers for more resources
Graph based methods are among the most active and applicable approaches studied in semi-supervised learning. The problem of neighborhood graph construction for these methods is addressed in this paper. Neighborhood graph construction plays a key role in the quality of the classification in graph based methods. Several unsupervised graph construction methods have been proposed that have addressed issues such as data noise, geometrical properties of the underlying manifold and graph hyper-parameters selection. In contrast, in order to adapt the graph construction to the given classification task, many of the recent graph construction methods take advantage of the data labels. However, these methods are not efficient since the hypothesis space of their possible neighborhood graphs is limited. In this paper, we first prove that the optimal neighborhood graph is a subgraph of a k '-NN graph for a large enough k ', which is much smaller than the total number of data points. Therefore, we propose to use all the subgraphs of k '-NNs graph as the hypothesis space. In addition, we show that most of the previous supervised graph construction methods are implicitly optimizing the smoothness functional with respect to the neighborhood graph parameters. Finally, we provide an algorithm to optimize the smoothness functional with respect to the neighborhood graph in the proposed hypothesis space. Experimental results on various data sets show that the proposed graph construction algorithm mostly outperforms the popular k-NN based construction and other state-of-the-art methods. (C) 2011 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available