## 2 Methodology
### Mixture Graph Construction  
[PERSON] _et al._[2] observed that a semi-supervised linear classifier based on a \(k\)NN graph in the subspace can achieve higher accuracy than the classifier based on a \(k\)NN graph in the original space. This observation indicates that a \(k\)NN graph in the high dimensional space is often suffered from noisy and redundant features. In contrast, a \(k\)NN graph in the low dimensional space is less suffered from the redundant and noisy features. In addition, [PERSON] _et al._[15] found that an \(l_{1}\) graph constructed in the subspace is also less suffered from noise features than the \(l_{1}\) graph in the original space. Inspired by these observations, we investigate a mixture graph, combined by \(k\)NN graphs constructed in several random subspaces of original space, for semi-supervised classification. The detailed procedure of mixture graph is listed as follows:  
(1). Randomly sampling \(d\) feature indices without replacement, and project \(\mathbf{X}\) into \(\mathbf{X}^{t}=[\mathbf{x}_{1}^{t};\mathbf{x}_{2}^{t};\cdots;\mathbf{x}_{n}^ {t}]\in\mathbb{R}^{n\times d}\), \(\mathbf{x}_{i}^{t}\) is consisted of the sampled \(d\) features of \(\mathbf{x}_{i}\).  
(2). Construct a \(k\)NN graph on \(\mathbf{X}^{t}\), and define the corresponding association matrix as:  
\[\mathbf{W}_{ij}^{t}=\left\{\begin{array}{ll}1,&\mbox{if}\quad\mathbf{x}_{j}^ {t}\in\mathcal{N}_{k}(\mathbf{x}_{i}^{t})\mbox{ or }\mathbf{x}_{i}^{t}\in\mathcal{N}_{k}( \mathbf{x}_{j}^{t})\\ 0,&\mbox{otherwise}\end{array}\right. \tag{6}\]  
where \(\mathcal{N}_{k}(\mathbf{x}_{i}^{t})\) includes \(k\) nearest neighborhood samples of \(\mathbf{x}_{i}^{t}\), and the neighborhood relationship is determined by the Euclidean distance between samples. In this way, we can construct a \(k\)NN graph \(G^{t}\) and define its association matrix \(\mathbf{W}^{t}\) in the \(t\)-th subspace.  
(3). Repeat the above two steps \(T\) times and thus \(T\) graphs can be constructed in \(T\) random subspaces, one graph for each subspace. Then, these \(k\)NN graphs can be integrated into a mixture graph and its association matrix is defined as follows:  
\[\mathbf{W}_{ij}^{mg}=\frac{1}{T}\sum_{t=1}^{T}\mathbf{W}_{ij}^{t} \tag{7}\]Since the mixture graph is combined with \(T\) graphs constructed in random subspaces, the impact of noisy and redundant features is reduced. The mixture graph can not only hold more complicated geometric distribution of samples than any of the \(T\) graphs as the diversity of random subspaces, but also be less sensitive to \(k\) than a single \(k\)NN graph. From the viewpoint of ensemble learning [30] that the accuracy of an ensemble classifier is no smaller than the average accuracy of base classifiers; thus, the mixture graph avoids the risk of choosing a bad \(k\)NN graph. Some recent methods (_i.e._, diffuse interfaces [31], \(p\)-Laplacian [32]) were proposed to identify relevant features and to discard noisy features for semi-supervised learning. These methods are reported to perform well on samples with a large number of noisy features. In this case, our mixture graph may not work well as supposed. However, \(p\)-Laplacian can be borrowed by the mixture graph to discard these noisy features.  
To investigate these potential advantages of mixture graph, we substitute \(\mathbf{W}\) in Equation (1) with mixture graph \(\mathbf{W}^{mg}\) and then perform semi-supervised classification on \(\mathbf{W}^{mg}\) to predict the labels of unlabeled samples. In this way, we propose a method called Semi-Supervised Classification based on Mixture Graph (SSCMG). We study the characteristics of mixture graph by comparing it with several representative GSSC methods (_i.e._, RMGT [7], LNP [11], CGSSL[10]) and analyze its sensitivity under different values of input parameter.