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.