# Semi-Supervised Ridge Regression with Adaptive Graph-Based Label Propagation
## 1 Introduction
[30] presented a local ridge regression (LRR) algorithm to effectively solve the illumination variation and partial occlusion problems of facial images. To deal with the singular problem in the extreme learning machine learning algorithms, [31] proposed an extreme learning machine ridge regression (ELMRR) learning algorithm with ridge parameter optimization. For reducing the computation time and retaining statistical optimality, [PERSON] et al. [32] suggested a decomposition-based scalable approach to perform kernel ridge regression (KRR) [33], which randomly divided a dataset of size \(N\) into \(m\) subsets with equal size. The KRR calculated an independent estimator for each subset, and then averaged the local solutions into a global predictor. In order to improve the training efficiency with large-scale data, [34] proposed an accelerator for kernel ridge regression algorithms based on data partition (PP-KRR). To address the limitation of LSR method which ignored the correlation among samples, [PERSON] et al. [18] presented the inter-class sparsity based discriminative least square regression (ICS_DLSR) algorithm for multi-class classification. In order to improve the performance of dictionary learning, a locality-constrained and label embedding dictionary learning (LCLE-DL) [35] algorithm was proposed by considering both the locality of samples and label information. The aforementioned approaches are supervised algorithms, which can make full use of labeled sample information, but they cannot utilize unlabeled samples information adequately. However, the labeled samples are finite since they are needed to be obtained artificially [36]. Moreover, the cost of manually labeled samples is too high due to the usage of manpower, material resources and energy. Hence, it is difficult to satisfy the requirement of for real-life sample [37]. Conversely, the unlabeled samples can easily be collected from the Internet, web chatting, digital camera of surveillance and so on [38]. As a result, it is necessary to utilize the information of unlabeled samples to improve the performance of ridge regression algorithm [39; 40]. [PERSON] et al. [39] extended the local linear regression to the local linear semi-supervised regression (LLSSR) by adding manifold regularization. To reduce the distributed error and enlarge the number of data subsets using unlabeled data, [PERSON] et al. [40] provided an error analysis for distributed semi-supervised learning with kernel ridge regression (DSKRR) based on a divide-and-conquer strategy. Although these semi-supervised ridge regression algorithms utilized the labeled and unlabeled data simultaneously, the distribution relationships between the labeled and unlabeled data were not considered at all. Considering the computational efficiency and effectiveness, label propagation (LP) has attracted much attention in the study of the graph-based semi-supervised learning [41; 42]. The core idea of LP is to propagate the information of labeled data to unlabeled data by constructing a weighted undirected graph. In the past few years, many LP algorithms such as gaussian fields and harmonic functions (GFHF) [43] and local and global consistency (LGC) [44] have been proposed. These methods can employ both labeled and unlabeled samples during training processing, but their performances heavily depended on the underlying geometrical structure of the original data distribution. In addition, they fail to build an explicit classifier for the testing samples or new coming samples. Therefore, these methods cannot directly obtain the label information of the testing samples. In order to deal with the first problem, many sophisticated graph construction algorithms have been studied in recent years [45; 46; 47]. To some extent, they alleviated the limitations of traditional \(k\) nearest neighbor or \(\varepsilon\) ball graphs, but their graph construction process was independent of the subsequent LP task. In other words, the graph structure was fixed in the process of LP.