Robust Multi-class Graph Transduction with higher order regularization

Graph transduction refers to a family of algorithms that learn from both labeled and unlabeled examples using a weighted graph and scarce label information via regularization or label propagation. A recent empirical study showed that the Robust Multi-class Graph Transduction (RMGT) algorithm achieves state-of-the-art performance on a variety of graph transduction tasks. Although RMGT achieves state-of-the-art performance and is parameter-free, this method was specifically designed for using the combinatorial Laplacian within its regularization framework. Unfortunately, the combinatorial Laplacian may not be the most appropriate graph Laplacian for all real applications and recent empirical studies showed that normalized and iterated Laplacians may be better suited than combinatorial Laplacians in general tasks. In this paper, we generalize the RMGT algorithm for any positive semidefinite matrix. Therefore, we provide a novel graph transduction method that can naturally deal with higher order regularization. In order to show the effectiveness of our method, we empirically evaluate it against five state-of-the-art graph-based semi-supervised learning algorithms with respect to graph construction and parameter selection on a number of benchmark data sets. Through a detailed experimental analysis using recently proposed empirical evaluation models, we see that our method achieved competitive performance on most data sets. In addition, our method achieved good stability with respect to the graph´s parameter for most data sets and graph construction methods, which is a valuable property for real applications. However, the Laplacian´s degree value may have a moderate influence in the performance of our method.