# Semi-Supervised Classification via Hypergraph Convolutional Extreme Learning Machine
## 2 Preliminary and Related Work
### Hypergraph Preliminary  
Hypergraph is the generalization of the simple graph, in which an edge can join any number of vertices. We refer to edges in a hypergraph as hyperedges. By contrast, we denote the regular graph in which each edge only connects two vertexes as a simple graph. A visual comparison between the simple graph and the hypergraph is illustrated in Figure 1. It can be seen that hypergraph can reveal a more complex data relationship, which is superior to the simple graph. For a learning task, hypergraph is usually used to represent the high-order intraclass variations among data points.  
Formally, let \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathcal{W})\) be a hypergraph composed of a vertex set \(v\in\mathcal{V}\) with the size of \(N\), a hyperedge set \(e\in\mathcal{E}\) with the size \(|\mathcal{E}|\), and a weight set of hyperedge \(\mathcal{W}\), where the weight of hyperedge \(e\) is indicated as \(w(e)\). A hypergraph is often described as an incidence matrix \(\mathbf{H}\in\mathbb{R}^{N\times|\mathcal{E}|}\) whose elements indicate whether a vertex joins a corresponding hyperedge (e.g., Figure 1b). Mathematically, the incidence matrix is defined by  
\[h(v,e)=\begin{cases}1&v\in e\\ 0&v\
otin e.\end{cases} \tag{1}\]  
The degree of a vertex \(v\) and the degree of a hyperedge \(e\) are given as follows, respectively  
\[d(v)=\sum_{e\in\mathcal{E}}w(e)h(v,e), \tag{2}\]  
\begin{table}
\begin{tabular}{l l} \hline \hline
**Notation** & **Definition** \\ \hline \(N\) & The number of data points. \\ \(m\) & The number of features. \\ \(C\) & The number of classes. \\ \(\mathbf{X}\) & The feature matrix of dataset, \(\mathbb{R}^{N\times m}\). \\ \(\mathbf{Y}\) & The label matrix with one-hot encoding, \(\mathbb{R}^{N\times C}\). \\ \(N_{\mathcal{T}}\) & The number of labeled samples. \\ \(\mathcal{T}\) & The labeled set. \\ \(\mathcal{U}\) & The unlabeled set. \\ \(\boldsymbol{\Theta}\) & The hidden layer parameter matrix, \(\mathbb{R}^{m\times L}\). \\ \(\boldsymbol{\beta}\) & The output layer parameter matrix, \(\mathbb{R}^{L\times C}\). \\ \(\mathbf{Z}\) & The matrix of latent representation, \(\mathbb{R}^{N\times L}\). \\ \(\mathbf{Z}^{\ddagger}\) & The Moore-Penrose generalized inverse of matrix \(\mathbf{Z}\). \\ \(L\) & The number of hidden neurons. \\ \(\mathcal{V}\) & The set of vertices in the hypergraph. \\ \(\mathcal{E}\) & The set of hyperedges in the hypergraph. \\ \(\mathbf{W}\) & The diagonal matrix of the hyperedge weights, \(\mathbb{R}^{|\mathcal{E}|\times|\mathcal{E}|}\). \\ \(\mathcal{G}\) & A hypergraph \(\mathcal{G}=(\mathcal{V},\mathcal{E},\mathbf{W})\). \\ \(\mathbf{H}\) & The incidence matrix of the hypergraph, \(\mathbb{R}^{N\times|\mathcal{E}|}\). \\ \(d(v)\) & The degree of the vertex \(v\). \\ \(\delta(e)\) & The degree of the hyperedge \(e\). \\ \(\mathbf{D}_{v}\) & The diagonal matrix of the vertex degrees, \(\mathbb{R}^{N\times N}\). \\ \(\mathbf{D}_{e}\) & The diagonal matrix of the hyperedge degrees, \(\mathbb{R}^{|\mathcal{E}|\times|\mathcal{E}|}\). \\ \(\mathbf{L}\) & The hypergraph Laplacian matrix, \(\mathbb{R}^{N\times N}\). \\ \hline \hline \end{tabular}
\end{table}
Table 1: Important notations used in this paper and their definitions.  
\[\delta(e)=\sum_{v\in\mathcal{V}}h(v,e)\,, \tag{3}\]  
By analogy with the simple graph, spectral analysis can be used as an efficient tool for the analysis of hypergraph. The normalized hypergraph Laplacian matrix [33; 34] is calculated by  
\[\mathbf{L}=\mathbf{I}-\mathbf{D}_{v}^{-1/2}\mathbf{HWD}_{e}^{-1}\mathbf{H}^{T} \mathbf{D}_{v}^{-1/2}. \tag{4}\]  
For a semi-supervised learning task, hypergraph is usually used by incorporating with an empirical error [35], as follows  
\[\operatorname*{arg\,min}_{\mathbf{F}}\mathcal{R}_{emp}(\mathbf{F})+\lambda \operatorname{tr}\left(\mathbf{F}^{T}\mathbf{L}\mathbf{F}\right), \tag{5}\]  
where \(\mathcal{R}_{emp}(\mathbf{F})\) denotes the empirical error term over a problem-dependent prediction \(\mathbf{F}\).