A Study of Transductive Graph-Based Regression

Abstract

Regression methods play an important role in many real-world applications such as econometric, pattern recognition, and prediction of protein chains to cite a few tasks. Although some studies have been exploring graphbased prediction of continuous values also called regression problems, in the semi-supervised context, they have not yet explored the formalism and potential of complex network theory and usually, they address only the classiffcation problem (discrete labels). Beyond that, those graph-based approaches do not address factors such as the impact of using different graph construction methods on the regression result, exploration of topological features of the adopted graph representation, how the inference is carried out, and what type of graph-based label propagation strategy is adopted. Here, in the proposed approach, all the relevant dimensions of the technique, such as knowledge and data representations, inference strategy, and evaluation criteria are addressed. First, we combine two well-known network construction models, spectral and k-NN. Separately, the k-NN network generates a regular degree connected network and the spectral network generates a network with groups of vertices densely connected internally, however, it leads to several unconnected groups (or sub-networks), which harms methods such as Random Walks and label propagation. Therefore, we combine spectral and k-NN to ensure a hybrid connected network. Second, as the inference strategy, we use a transductive method for label propagation by using a robust network technique combining Random Walks for the regression task, which turns forward the propagation of values by the network in unlabeled objects using the leastsquares regression method. An empirical analysis of different data sets shows that our strategy surpasses traditional approaches considering the measures used in the evaluation.