On the evaluation of graph construction methods for semi-supervised transductive classification - Freire, Leonardo Macedo; Oliva, Jefferson Tales; Santos, Valéria de Carvalho; Freitas, Vander Luis de Souza; Castro Gertrudes, Jadson (Anais do Symposium on Knowledge Discovery, Mining and Learning (KDMiLe), 2025)
Semi-supervised learning addresses critical challenges in machine learning when labeled data is scarce but unlabeled data is abundant. However, ensuring effective label propagation in transductive semi-supervised classification algorithms is challenging due to the significant influence of the underlying graph's topological structure. This article systematically investigates this problem by evaluating various graph construction methods alongside traditional approaches, including the novel application of the HDBSCAN*-derived Mutual Reachability Minimum Spanning Tree (MST_R) and the Disparity Filter (DF). We employed the Local and Global Consistency (LGC) algorithm for label propagation and assessed performance using macro-averaged F-measure and statistical tests (Friedman and Nemenyi). Our experiments show that the DF demonstrates compelling performance, showing no statistical difference from top-ranked methods like SYM_FKNN. On the other hand, MST_R exhibited limitations that could be verified in future studies. This comprehensive analysis, further supported by Spearman's rank correlation with graph and data properties, provides important insights into optimal graph selection for robust semi-supervised classification workflows.