# Semi-Supervised Ridge Regression with Adaptive Graph-Based Label Propagation
## 3 The Proposed Method
### Objective Function of SSRR-AGLP  
In the proposed method, we first divide the dataset into training set and testing set, and then the training set is subdivided into labeled sample set and unlabeled sample set. Suppose the training sample set is \(X=[x_{1},x_{2},...,x_{l},x_{l+1},...,x_{n}]=[X_{l},X_{u}]\in R^{d\times n}\), where \(X_{l}=[x_{1},x_{2},...,x_{l}]\in R^{l\times d}\) represents the labeled samples of the training set and \(X_{u}=[x_{l+1},x_{l+2},...,x_{l+u}]\in R^{d\times(n-l)}\) represents unlabeled samples of the training set. In addition, \(n\) represents the number of training samples and \(d\) represents the feature dimension of the samples. \(Y=[y_{1},y_{2},...,y_{l},y_{l+1},...,y_{n}]\in\{0,1\}^{c\times n}\) is the labeled matrix of training samples, where \(y_{i}\in R^{c\times 1}(1\leq i\leq n)\) represents the label vector of the \(i\)-th sample, \(c\) is the total number of classes, and \(y_{ij}\) is the \(j\)-th element in \(y_{i}\). If \(x_{i}\) is a labeled sample and belongs to the \(j\)-th class, then \(y_{ij}=1\), otherwise \(y_{ij}=0\). If \(x_{i}\) is an unlabeled sample, all elements in \(y_{i}\) are 0, that is, \(\forall i>l,\ y_{i}=0\in R^{c\times 1}\). The first aim of the proposed SSRR-AGLP is to utilize the label information of labeled samples to predict the label of unlabeled samples. Therefore, the LP algorithm is adopted in this work. However,different from the traditional LP algorithm, a relationship graph between samples is first constructed by the reconstructive coefficient of samples. The objective function is formulated as follows:  
\[ \begin{array}{l}\underset{S}{\text{min}}\ \varphi(S)=||X-XS||_{2}^{2}\\ s.t.S\geq 0\end{array}  \tag{9}\]  
where \(S=[s_{1},s_{2},\cdots,s_{n}]\in R^{n\times n}\) is the weight matrix of graph, \(s_{i}=[s_{i1},s_{i2},...,s_{in}]^{T}\in R^{n\times 1}\) is the reconstruction coefficient vector of sample \(x_{i}\), and its element value denotes the weight of an edge between the sample \(x_{i}\) and other samples in the graph. In order to make the reconstruction coefficients physically more meaningful, the non-negative constraint for the reconstruction coefficients is introduced in our model. The non-negativity constraint can enhance the discriminability of the reconstruction coefficients, so that the sample will more likely be reconstructed by the samples from the same clustering. The connection relationship between sample pairs in the graph is represented by reconstructive coefficients. For instance, if a coefficient of the sample pair \(x_{j}\) and \(x_{i}\) is non-zero, then there exists an edge between them in the graph and the weight of edge \(S_{ij}\) is set as the coefficient corresponding to \(x_{j}\). Thus, the local information of data can be exploited by selecting the nearest neighbors of a sample. As mentioned above, the locality and sparsity constraint term for \(S\) can be defined as follows:  
\[\underset{S}{\text{min}}\ \phi(S)=||E\odot S||_{1} \tag{10}\]  
where \(||\cdot||_{1}\) is the \(l_{1}\)-norm of a matrix and \(\odot\) is the element-wise multiplication. \(E=[e_{ij}]\in R^{n\times n}\) is the local adaptation matrix, in which the element \(e_{ij}\) is defined as follows:  
\[e_{ij}=\exp(\frac{||x_{i}-x_{j}||_{2}^{2}}{\sigma^{2}}) \tag{11}\]  
From Equation (11), we can clearly find that a smaller \(e_{ij}\) indicates \(x_{i}\) is more similar to \(x_{j}\) and vice versa. Hence, minimizing Equation (10) with respect to \(S\) will assign small or nearby zero to reconstructive coefficients of samples which are far from \(x_{i}\). This means that if two samples are distant from each other, they are unlikely to be connected in the graph. Combining Equation (9) with (10), the adaptive graph model in the label propagation is generated as follows:  
\[ \begin{array}{l}\underset{S}{\text{min}}\ \varphi(S)=||X-XS||_{2}^{2}+ \alpha||E\odot S||_{1}\\ s.t.\ S\geq 0\end{array}  \tag{12}\]  
where \(\alpha>0\) is a balance parameter which controls the importance of the locality and sparsity constraint term.