Abstract
Graph-based semi-supervised learning has attracted much attention in recent years. Many successful methods rely on graph structure to propagate labels from labeled data to unlabeled data. Although graph structure affects the performance of the system, only few works address its construction problem. In this work, the graph structure is constructed by adjusting the hyperparameter controlling the connection weights between nodes. The idea is to learn the hyperparameters for graphs that yields low leave-one-out prediction error on labeled data while retaining high stability of the prediction on unlabeled data. The problem is solved efficiently using the gradient-based optimization technique. Experimental results indicate that the proposed technique yields improvement of generalization error as well as stability of the labeling function.