Abstract: As an effective graph-based semi-supervised classification method, Label Propagation（LP） is widely used in image classification, text classification and other tasks. In the graph-based semi-supervised classification, the graph construction affects the performance of the algorithm to some extent. Although a large number of graph construction methods have been proposed, they exist in the problem of the separation between the graph construction and the subsequent learning processes, as well as neglecting the local structure of data. In order to solve the above problems, it proposes a new algorithm named Locality Constrained Adaptive Graph based Label Propagation（LCAGLP） in this paper. Firstly, it integrates the graph construction and label propagation into a unified framework, and also considers the locality and sparsity of samples in the process of graph construction. The idea makes the optimization graph more sparse and discriminative, which is conducive to label propagation. Then, an iterative optimization algorithm is designed for solving the objective function. Finally, extensive experiments are carried out on four databases, and the experimental results demonstrate the effectiveness of the proposed method.

Key words: locality constraint, adaptive graph, label propagation, semi-supervised learning

摘要： 标签传递是一种有效的基于图的半监督分类方法，被广泛应用于图像分类、文本分类等任务中。在基于图的半监督分类方法中，图的构建在一定程度上影响算法的性能。尽管已有大量的图构建方法被提出，然而现有方法存在图的构建与后续学习过程分离以及忽略数据的局部结构问题。为了解决上述问题，提出了一种基于局部约束的自适应图标签传递方法。在该方法中，将图构建与标签传递结合形成统一框架，并且在图构建过程中同时考虑样本的局部性与稀疏性，使得优化图更具有稀疏性和判别性，从而有利于标签传递。还提出了一种迭代优化算法求解目标函数，并在四个数据库上进行大量的实验，证明了所提出方法的有效性。

关键词: 局部约束, 自适应图, 标签传递, 半监督学习