Semi-supervised classification in the Censored Block Model

Semi-supervised learning is characterized by a partially labelled dataset, in the sense that we know the true labels, i.e. classes, of a usually small fraction of the datapoints. Optimally embedding this "semi-supervised information" in the learning process is a hard task, that can be carried out through the development of specific algorithms and an efficient graph construction. Here we focus more on the latter point: restricted to the semi-supervised version of a paradigmatic model for the branch of the statistical physics that deals with AI concepts, namely the Censored Block Model (or Planted Spin Glass), we propose various graph constructions and give them theoretical justifications. After having developed those configurations, we apply on them two of the simplest algorithms of graph-based inference, namely the Naive Mean Field and the one based on the Adjacency matrix. We study specifically the latter and discover an inefficiency in the learning process strongly similar to the one found and fixed by Mai and Couillet in their work on Laplacian Regularization. In the same way, we provide the algorithm of a further parameter that controls how much the learning process relies on the "semi-supervised information" and eventually try to optimize it. The study sets the basis for an extension to the semi-supervised case of the algorithms recently developed by the statistical physics community, based on the spectral properties of the Non-Backtracking and the Bethe-Hessian matrices.