Deep Manifold Learning with Graph Mining

In this paper, the boldface capital letters and boldface lower letters are employed to present matrics and vectors respectively. Suppose the $\bm{m_{i}}$ as the $i$-th row of the matrix $\bm{M}\in R^{d\times c}$. The element of $\bm{M}$ is $m_{ij}$. Besides, the $F$-norm of the matrix $\bm{M}$ is defined as $||\bm{M}||_{F}=\sqrt{\sum_{i=1}^{d}\sum_{j=1}^{c}m_{ij}^{2}}$. The trace and transpose of matrix $\bm{M}$ are denoted as $Tr(\bm{M})$ and $\bm{M}^{T}$, respectively. $\nabla_{\bm{x}}f(\bm{x})$ means the the gradient of $f(\bm{x})$ w.r.t. $\bm{x}$. And $\bm{1}_{c}$ is a unit column vector with dimension c. For the semi-supervised classification, $\bm{X}=[\bm{x_{1},x_{2},...,x_{n}}]\in R^{n\times d}$ is the feature matrix with $n$ samples and $d$ dimensions. And we have $l$ labeled data points and $u$ unlabeled data samples where $l+u=n$. Let $\bm{Y}=[\bm{Y}_{l};\bm{Y}_{u}]\in R^{n\times c}$ denotes the labeled and unlabeled with $c$ classes. And $\bm{Y}_{u}$ is initialized according to $\bm{Y}_{u}\bm{1}_{c}=\bm{1}_{u}$. Apart from that, we denote $\bm{H}^{(m)}\in R^{n\times d_{m}}$ as the $m$-th layer hidden feature.

The classic convolutional neural network is designed to process regular data like images. However, there exists numerous irregular data, such as citation networks and social networks. Owing to the distribution of these data is not shift-invariant, the traditional neural networks could not extract the latent topological information of these data. Aiming to tackle these issues, some researchers try to transfer traditional Laplacian kernel and convolution operators into graph data space by spectral decomposition based on the graph [21, 22, 23]. However, the spectral decomposition of the Laplacian matrix is very time-consuming. Defferrard et al [22] employ the Chebyshev polynomial to fit the results of spectral decomposition and design a Chebyshev convolution kernel as follows

where $\tilde{\bm{\Lambda}}=2\bm{\Lambda}/\lambda_{max}-\bm{I}_{N}$ is the normalized feature vector matrix, $\lambda_{max}$ is the spectral radius, $\bm{\theta}\in R^{K}$ is Chebyshev coefficient vector, and the Chebyshev polynomial is defined as $T_{k}(x)=2xT_{k-1}(x)-T_{k-2}(x)$.

Based on this, Kipf et al [24] use the first-order expansion of the Chebyshev polynomial to fit the graph convolution kernel with $K=1,\lambda_{max}=2$. To prevent overfitting and reduce complexity, the authors introduce some tricks, $\bm{\theta}_{0}=-\bm{\theta}_{1}$, $\bm{\tilde{A}}=\bm{A}+\bm{I}_{N}$ and the diagnonal element in degree matrix is $\widetilde{\bm{D}}_{ii}=\sum_{j}\widetilde{\bm{A}}_{ij}$. Finally, the classic GCN is defined as follows

Apart from that, manifold learning [25] is a classic nonlinear algorithm for dimensionality reduction, representation learning, and classification tasks. It believes that the data nodes are generated from a low-dimensional manifold embedded in a high-dimensional space and this procedure is often described by a function with few underlying parameters. Based on this idea, manifold learning aims to uncover the function in order to explore the latent topological structure of the data.

As is known to us, Softmax has been widely used as a decision layer in lots of classic neural networks. Moreover, on some computer vision tasks such as image classification, these networks also have made excellent progress and can be generally formulated as

where $f_{n}$ is a neural network such as CNN to extract the deep features, $a\in\{0,1,...,m\}$ is the $a$-th layer in the network, and $\bm{W}^{(a)}$ is the weight matrix in the $a$-th layer. The latent feature in the $a$-th layer is defined as $\bm{H}^{(a)}$ and the $\bm{H}^{(0)}$ is equivalent to $\bm{X}$. $\bm{\hat{Y}}\in R^{n\times c}$ is the prediction label. The latent feature $\bm{H}^{(m)}$ has the same shape with $\bm{\hat{Y}}$. $\sigma(\cdot)$ is the activation function. Aiming to predict the classes, Softmax maps and normalizes these deep features into real numbers in $[0,1]$ via the formula defined as

The cross-entropy is employed as the loss function and optimized via gradient descent. Aiming to classify the irregular data such as citation network, [24] defines the graph convolution to extract the graph deep features and also classify them via softmax.

From the Eq. (4), softmax mainly forecasts the probability according to the value of the embedding. However, it ignores the latent topological distribution of the graph embedding. For example, in social networks, people ought to have a high degree of similarity to those with whom they socialize frequently. Therefore, introducing the softmax into GCN for irregular data classification may not get the same achievements as utilizing CNN for the regular data without this topological structure. More importantly, the softmax is optimized via gradient descent with thousands of iteration to obtain approximate solutions, whose time complexity is non-linear with the number of the convolutional layers. Aiming to improve the performance of the GCN, we propose a graph neural network with a non-gradient decision layer.

In each iteration of the back propagation, the computaional complexity of graph convolution in Eq. (10) is $O(|\mathcal{E}|d_{a})$, where $\bm{A}$ is a sparse matrix and the amount of non-zero entries is $|\mathcal{E}|$. Assume that the proposed deep graph model converges after $t$ iterations. The time complexity of a non-gradient decision layer is $O(u\log u+u^{2}c+ud_{m}c)$, where $u$ is unlabel nodes. Therefore, the total complexity is $O(|\mathcal{E}|d_{a}+t(ulogu+u^{2}c+ud_{m}c))$. Considering that the solution of the non-gradient decision layer is independent with gradient and there is no need to optimize the classifier every iteration, the complexity can be approximate to $O(|\mathcal{E}|d_{a})$.

Since problem $\min\limits_{\bm{U}^{T}\bm{U}=I}||\bm{X}\bm{U}-\bm{Y}||_{F}^{2}$ is difficult to solve directly, we introduce the matrix $\bm{V}\in R^{d\times(d-c)}$ generated in the orthogonal complement spaces of $\bm{U}$ according to [26]. The problem is equivalent to the following balanced problem

To express more conveniently, we define the matrix $\bm{S}=[\bm{U},\bm{V}]$ and problem can be transformed into

where $\bm{R}=[\bm{Y},\bm{X}\bm{V}]$.

Owing to the orthogonal embedding, the problem can be simplified into

Notice that the first term in Eq. (13) is equal to a constant under the constraints. Therefore, the problem can be transformed into

The following lemma [27] points out that the transformed problem Eq. (14) has a closed-form solution.

According to Lemma 1, $\bm{S}$ can be calculated by

where $[\bm{E},\sim,\bm{F}^{T}]=svd(\bm{H}^{(m)}\bm{R})$. Therefore, the orthogonal matrix is obtained

where $\bm{S}[:,:c]$ means that the first $c$ columns of all the rows of $\bm{S}$ is taken.

It is difficult to optimize the second term in problem (8) directly. Therefore, we transform it like

Considering that $\bm{D}=diag(\sum_{j}a_{ij})$, the Eq. (18) is formulated as

where $d_{i}$ represents the diagonal element in $\bm{D}$. Furthermore, the inital problem is written as

where the $\bm{X}_{l}$ and $\bm{X}_{u}$ are the label and unlabel graph feature, respectively.

The first parts in Eq. (20) can be transformed by

And the $\mathcal{J}_{2}$ can also be simplified by

with $\bm{L}_{lu}=\bm{L}_{ul}^{T}$.

Combing the sub-problems Eq. (21) and Eq. (22), the primal problem can be define as

Owing to a constraint on $\bm{Y}_{u}$, the problem Eq. (23) is derivated w.r.t $\bm{Y}_{u}$ and set to 0. Then, we have

Having be decomposed with SVD, we can obtain the $[\bm{B},\bm{\Psi},\bm{C}^{T}]=svd(\bm{P})$. Note that

where $\bm{K}=\bm{C}^{T}\bm{Q}^{T}\bm{B}$. Clearly, $\bm{K}\bm{K}^{T}=\bm{I}$ such that $k_{ij}\leq 1$. Hence, we have

We can simply set $\bm{K}=\bm{C}^{T}\bm{Q}^{T}\bm{B}=\bm{I}_{r}$. In other words,

Consequently, the lemma is proved.

We employ citation networks and coauthor networks to evaluate the performance of models:

The detail of these datasets is summarized in TABLE I.

The ratio of labeled data for training is divided according to TABLE I. Like the [18], we employ the extra 500 labeled nodes as a valid set to optimize the hyperparameters including the hidden units in each layer, weight coefficient $\lambda$ in Eq. (10), dropout, and learning rate.

Before classification, the adjacent and feature matrix are accordingly (row-)normalized to the range of $[0,1]$. The two graph convolution layers are used as a deep graph feature extractor. For the hidden units in each layer, dropout rate, learning rate, and weight coefficient $\lambda$, we choose values of parameters from $\left\{10,32,64,128,256,512\right\}$, $\left\{0.1,0.3,0.5,0.7,0.9\right\}$, $\left\{10^{-3},10^{-2},10^{-1},...,10^{2},10^{3}\right\}$ and $\left\{2^{-3},2^{-2},2^{-1},...,2^{2},2^{3}\right\}$ respectively via 4-fold cross-validation and record the best records. The initialization described in [31] is employed to initialize the network weights. We train the model for a maximum of 500 training iterations with batch gradient descent. After tuning the hyperparameters, we adopt the adam optimizer with a learning rate of 0.01 and optimize the orthogonal manifold classifier every 50 iterations. Accuracy is employed to evaluate the performance of the model.

We compare the proposed model with eight state-of-the-art semi-supervised models including Graph neural networks with personalized pagerank ($APPNP$) [32], Unifying GCN and label propagation ($GCN$-$LPA$) [30], Multi-graph representation learning ($MulGraph$) [33], Deep graph infomax ($DGI$) [34],Parameter-Free Similarity of Label and Side Information ($PFS$-$LS$) [35], Graph Convolution Network ($GCN$) [24], Variational Graph Auto-Encoder ($GAE$) [36], Semi-supervised learning with Graph Embedding ($GraphEmbedding$)[18] and Deep learning via semi-supervised embedding ($DeepEmbedding$) [37]. Among them, $PFS$-$LS$ is a non-GNN model.

To be fair, we utilize the same experiment setting in section 5.2 train these comparison models and tune the correlated hyper-parameters. For classification models based graph, we utilize the self-loop adjacent $\widetilde{\bm{A}}$ to train as the same as in Eq. [10]. The models mentioned above are evaluated 10 times on the benchmark datasets. The accuracy and standard deviation are reported in TABLE II. Therefore, we could conclude that:

• 1)

  The proposed model has achieved state-of-the-art accuracy with respect to the comparison methods. For example, on Citeseer and Pubmed dataset, we achieve $74.8\%$ and $80.87\%$ accuracy respectively. The scores are higher than the other methods, which indicates that the proposed model could mine the conceal relationship among points and work well on classification tasks with few labeled data.

• 2)

  When dealing with the datasets with high dimensions, huge points, and low labeling ratios like Pubmed and Coauthor-CS, it has a $1\%$ relative improvement over previous state-of-the-art. Besides, the proposed model has a good performance on Coauthor-Phy which has nearly 2.5 million edges and complex topological relationships.

• 3)

  The proposed model is more successful and reasonable to integrate the graph topological structure with the label information than some state-of-the-art models like GCN-LPA, APPNP, and MulGraph. Among them, GCN-LPA utilizes label propagation to learn the edge weights of graphs. Compared with these models, ours integrates manifold learning with label local-structure as a non-gradient classifier. In this way, the deep graph networks could extract meaningful features to contribute to the decision layer.

The proposed model and comparison models are all implemented with PyTorch 1.2.0 on Windows 10 PC.

Fig. 3 shows the results on each benchmark datasets. It suggests that the proposed model converges rapidly on each dataset with $\lambda=1$ during the training step. The decision layer (defined in Eq. (7)) is optimized after every 100, 50, and 80 backpropagation on each dataset respectively, which contributes to the objective value dropped sharply and accelerates the training of the proposed model. Besides, we investigate the impacts of the dropout in graph network and parameter $\lambda$ (defined in Eq. (10)) on the model. The dropout ratio and $\lambda$ value are chosen like in Sec. 5.2. Convergence Epoch and Accuracy are utilized to evaluate the training speed and classification performance of the model. The result is shown in Fig. 4. From the results, we notice that the Convergence Epoch varies considerably with the $\lambda$ changing. On the contrary, Accuracy is not sensitive to weight value. In conclusion, the $\lambda$ mainly has an impact on the convergence rate of the model, and the proper dropout ratio could enhance the performance of the proposed model via discarding some neurons during the training.

Apart from that, we utilize the t-SNE [28] to reduce the deep graph embedding $\bm{H}^{(m)}$ (defined in Eq. (10)) to 2D. Before visualize, these embeddings are not normalized and the dimension is not reduced via PCA and normalized. The perplexity of t-SNE is set to 30. And the visualization of the reduction results in Fig. 2. We notice that the topological data is not preserved well at the beginning of the training. When the algorithm has converged, the distribution of the deep graph embedding is evenly and could be easy to classify.

We conduct an ablation study to evaluate how each part of the proposed non-gradient graph layer, Orthogonal Manifold (OM) and Local-structure Preservation (LP), contribute to overall model performances. Besides, GCN with a softmax classification strategy is employed as a baseline. The setting and results are summarized in Table III. We confirm that graph mining methods, orthogonal manifold learning and local-structure preservation, can both learn the relationship knowledge among the deep embedding. Besides, it is shown that the accuracy of GCN-OR and GCN-LP are both superior to traditional GCN-softmax. Moreover, the proposed deep model with a non-decision layer not only properly unifies the OM and LP parts but also successfully utilizes the topological structure and label information to enhance the performance.