## 4 Optimization for ISMLP

Table 4: The time complexity of several typical semi-supervised learning methods, where \(|\mathcal{P}|=|\mathcal{P}|+|\mathcal{P}|+|\mathcal{P}|\), \(r\) is the number of iterations in each method, and \(c\) (in the APTID) denotes the number of the inner iterations. Clearly, the time complexity of the proposed ISMLP has a linear dependence on the \(n\). \begin{table}
\begin{tabular}{l c c c c c c c c c c c c c c} \hline  & **EUCID** & **LSAML** & **SERAPH** & **S-RLMM** & **LRML** & **SLRML** & **APT** & **CMM** & **APIL** & **LMNN** & **SSML-DR** & **ISMLP** \\ \hline
5\% labeled data & 0.296 \(\pm\) 0.005 & 0.228 \(\pm\) 0.010 & 0.231 \(\pm\) 0.043 & 0.221 \(\pm\) 0.027 & 0.221 \(\pm\) 0.011 & 0.286 \(\pm\) 0.008 & 0.228 \(\pm\) 0.010 & 0.245 \(\pm\) 0.021 & 0.239 \(\pm\) 0.022 & 0.251 \(\pm\) 0.022 & 0.200 \(\pm\) 0.013 & 0.211 \(\pm\) 0.018 \\
10\% labeled data & 0.280 \(\pm\) 0.007 & 0.191 \(\pm\) 0.013 & 0.138 \(\pm\) 0.011 & 0.221 \(\pm\) 0.016 & 0.201 \(\pm\) 0.010 & 0.221 \(\pm\) 0.015 & 0.198 \(\pm\) 0.011 & 0.227 \(\pm\) 0.017 & 0.198 \(\pm\) 0.009 & 0.231 \(\pm\) 0.021 & 0.175 \(\pm\) 0.012 & **0.179 \(\pm\) 0.015** \\
30\% labeled data & 0.186 \(\pm\) 0.006 & 0.131 \(\pm\) 0.012 & 0.340 \(\pm\) 0.037 & 0.127 \(\pm\) 0.014 & 0.153 \(\pm\) 0.012 & 0.130 \(\pm\) 0.009 & 0.146 \(\pm\) 0.008 & 0.150 \(\pm\) 0.006 & 0.128 \(\pm\) 0.007 & 0.143 \(\pm\) 0.010 & 0.120 \(\pm\) 0.016 & **0.116 \(\pm\) 0.011** \\ \hline \end{tabular}
\end{table} 
Table 2: Classification performance (mean error rate, and standard deviation) of all the compared methods based on 3-NN with varying labeling rates on MNIST dataset, the best performance of each task is marked with boldface. \begin{table}
\begin{tabular}{l c c c c c c c c c c c c} \hline  & **LSCML** & **SERAPH** & **S-RLMM** & **LRML** & **SLRML** & **APT** & **CMM** & **APIL** & **LMNN** & **SSML-DR** & **ISMLP** \\ \hline
5\% labeled data & 0.296 \(\pm\) 0.005 & 0.228 \(\pm\) 0.010 & 0.231 \(\pm\) 0.044 & 0.221 \(\pm\) 0.027 & 0.221 \(\pm\) 0.011 & 0.286 \(\pm\) 0.008 & 0.228 \(\pm\) 0.010 & 0.245 \(\pm\) 0.021 & 0.239 \(\pm\) 0.022 & 0.261 \(\pm\) 0.022 & 0.200 \(\pm\) 0.013 & 0.211 \(\pm\) 0.018 \\
10\% labeled data & 0.280 \(\pm\) 0.007 & 0.191 \(\pm\) 0.013 & 0.138 \(\pm\) 0.011 & 0.221 \(\pm\) 0.016 & 0.201 \(\pm\) 0.010 & 0.221 \(\pm\) 0.015 & 0.198 \(\pm\) 0.011 & 0.227 \(\pm\) 0.017 & 0.198 \(\pm\) 0.009 & 0.231 \(\pm\) 0.021 & 0.175 \(\pm\) 0.012 & **0.179 \(\pm\) 0.015** \\
30\% labeled data & 0.186 \(\pm\) 0.006 & 0.131 \(\pm\) 0.012 & 0.340 \(\pm\) 0.037 & 0.127 \(\pm\) 0.014 & 0.153 \(\pm\) 0.012 & 0.130 \(\pm\) 0.009 & 0.146 \(\pm\) 0.008 & 0.150 \(\pm\) 0.006 & 0.128 \(\pm\) 0.007 & 0.143 \(\pm\) 0.010 & 0.120 \(\pm\) 0.016 & **0.116 \(\pm\) 0.011** \\ \hline \end{tabular}
\end{table} 
Table 3: Classification performance (mean error rate, and standard deviation) of all the compared methods based on 3-NN with varying labeling rate on MNIST dataset, the best performance of each task is marked with boldface. ### Retrieval Performance on Corel 5K Dataset

We also run a retrieval experiment on Corel 5K dataset with a labeling rate of 30%. Figure 3 documents the performance of the proposed ISMLP and LSeMML. In the first sub-figure, it is evident that ISMLP can effectively capture the semantic meaning of the query image, leading to accurate retrieval of five relevant images. In contrast, LSeMML mistakes the \"red\" element as the key property of the query image and unsurprisingly gives the irrelevant images in the 4-th and 5-th nearest neighbors. The major difference between ISMLP and LSeMML lies in the utilization of the unlabeled regularization term, i.e., LSeMML utilizes the EUCLID metric to mine the manifold information of the unlabeled data. When the EUCLID metric is not appropriate to measure the correlations and weights of the features, the resulting graph will be an inferior one. Therefore, the sub-optimal results can be observed in the retrieval list.