Informativity-based graph: Exploring mutual kNN and labeled vertices for semi-supervised learning

Data repositories are getting larger and in most of the cases, only a small subset of their data items is labeled. In such scenario semi-supervised learning (SSL) techniques have become very relevant. Among these algorithms, those based on graphs have gained prominence in the area. An important step in graph-based SSL methods is the conversion of tabular data into a weighted graph. However, most of the SSL literature focuses on developing label inference algorithms without studying graph construction methods and its effect on the base algorithm performance. This paper provides a novel technique for building graph by using mutual kNN and labeled vertices. The use of prior information, i.e., to consider the small fraction of labeled vertices, has been underexplored in SSL literature and mutual kNN has been only explored in clustering. The empirical evaluation of the proposed graph showed promising results in terms of accuracy, when it is applied to the label propagation task. Additionally, the resultant networks have lower average degree than kNN networks.