Graph Inference Learning for semi-supervised Classification

Formally, we denote an undirected/directed graph as $\mathcal{G}=\{\mathcal{V},\mathcal{E},\mathcal{X},\mathcal{Y}\}$, where $\mathcal{V}=\{v_{i}\}_{i=1}^{n}$ is the finite set of $n$ (or $|\mathcal{V}|$) vertices, $\mathcal{E}\in\mathbb{R}^{n\times n}$ defines the adjacency relationships (i.e., edges) between vertices representing the topology of $\mathcal{G}$, $\mathcal{X}\in\mathbb{R}^{n\times d}$ records the explicit/implicit attributes/signals of vertices, and $\mathcal{Y}\in\mathbb{R}^{n}$ is the vertex labels of $C$ classes. The edge $\mathcal{E}_{ij}=\mathcal{E}(v_{i},v_{j})=0$ if and only if vertices $v_{i},v_{j}$ are not connected, otherwise $\mathcal{E}_{ij}\neq 0$. The attribute matrix $\mathcal{X}$ is attached to the vertex set $\mathcal{V}$, whose $i$-th row $\mathcal{X}_{v_{i}}$ (or $\mathcal{X}_{i\cdot}$) represents the attribute of the $i$-th vertex $v_{i}$. It means that $v_{i}\in\mathcal{V}$ carries a vector of $d$-dimensional signals. Associated with each node $v_{i}\in\mathcal{V}$, there is a discrete label $y_{i}\in\{1,2,\cdots,C\}$.

We consider the task of semi-supervised node classification over graph data, where only a small number of vertices are labeled for the model learning, i.e., $|\mathcal{V}_{Label}|\ll|\mathcal{V}|$. Generally, we have three node sets: a training set $\mathcal{V}_{tr}$, a validation set $\mathcal{V}_{val}$, and a testing set $\mathcal{V}_{te}$. In the standard protocol of prior literatures (Yang et al., 2016), the three node sets share the same label space. We follow but do not restrict this protocol for our proposed method. Given the training and validation node sets, the aim is to predict the node labels of testing nodes by using node attributes as well as edge connections. A sophisticated machine learning technique used in most existing methods (Kipf & Welling, 2017; Zhou et al., 2004) is to choose the optimal classifier (trained on a training set) after checking the performance on the validation set. However, these methods essentially ignore how to extract transferable knowledge from these known labeled nodes to unlabeled nodes, as the graph structure itself implies node connectivity/reachability. Moreover, due to the scarcity of labeled samples, the performance of such a classifier is usually not satisfying. To address these issues, we introduce a meta-learning mechanism (Finn et al., 2017; Ravi & Larochelle, 2017; Sung et al., 2017) to learn to infer node labels on graphs. Specifically, the graph structure, between-node path reachability, and node attributes are jointly modeled into the learning process. Our aim is to learn to infer from labeled nodes to unlabeled nodes, so that the learner can perform better on a validation set and thus classify a testing set more accurately.

For convenient inference, we specifically build a structure relation between two nodes on the topology graph. The labeled vertices (in a training set) are viewed as the reference nodes, and their information can be propagated into those unlabeled vertices for improving the label prediction accuracy. Formally, given a reference node $v_{i}\in\mathcal{V}_{Label}$, we define the score of a query node $v_{j}$ similar to $v_{i}$ as

$\displaystyle s_{i\rightarrow j}=f_{r}(f_{e}(\mathcal{G}_{v_{i}}),f_{e}(\mathcal{G}_{v_{j}}),f_{\mathcal{P}}(v_{i},v_{j},\mathcal{E})),$

(1)

where $\mathcal{G}_{v_{i}}$ and $\mathcal{G}_{v_{j}}$ may be understood as the centralized subgraphs around $v_{i}$ and $v_{j}$, respectively. $f_{e},f_{r},f_{\mathcal{P}}$ are three abstract functions that we explain as follows:

• •

  Node representation $f_{e}(\mathcal{G}_{v_{i}})\longrightarrow\mathbb{R}^{d_{v}}$, encodes the local representation of the centralized subgraph $\mathcal{G}_{v_{i}}$ around node $v_{i}$, and may thus be understood as a local filter function on graphs. This function should not only take the signals of nodes therein as input, but also consider the local topological structure of the subgraph for more accurate similarity computation. To this end, we perform the spectral graph convolution on subgraphs to learn discriminative node features, analogous to the pixel-level feature extraction from convolution maps of gridded images. The details of feature extraction $f_{e}$ are described in Section 4.

• •

  Path reachability $f_{\mathcal{P}}(v_{i},v_{j},\mathcal{E})\longrightarrow\mathbb{R}^{d_{p}}$, represents the characteristics of path reachability from $v_{i}$ to $v_{j}$. As there usually exist multiple traversal paths between two nodes, we choose the function as reachable probabilities of different lengths of walks from $v_{i}$ to $v_{j}$. More details will be introduced in Section 4.

• •

  Structure relation $f_{r}(\mathbb{R}^{d_{v}},\mathbb{R}^{d_{v}},\mathbb{R}^{d_{p}})\longrightarrow\mathbb{R}$, is a relational function computing the score of $v_{j}$ similar to $v_{i}$. This function is not exchangeable for different orders of two nodes, due to the asymmetric reachable relationship $f_{\mathcal{P}}$. If necessary, we may easily revise it as a symmetry function, e.g., summarizing two traversal directions. The score function depends on triple inputs: the local representations extracted from the subgraphs w.r.t. $f_{e}(\mathcal{G}_{v_{i}})$ and $f_{e}(\mathcal{G}_{v_{j}})$, respectively, and the path reachability from $v_{i}$ to $v_{j}$.

In semi-supervised node classification, we take the training node set $\mathcal{V}_{tr}$ as the reference samples, and the validation set $\mathcal{V}_{val}$ as the query samples during the training stage. Given a query node $v_{j}\in\mathcal{V}_{val}$, we can derive the class similarity score of $v_{j}$ w.r.t. the $c$-th ($c=1,\cdots,C$) category by weighting the reference samples $\mathcal{C}_{c}=\{v_{k}|y_{v_{k}}=c\}$. Formally, we can further revise Eqn. (1) and define the class-to-node relationship function as

	$\displaystyle s_{\mathcal{C}_{c}\rightarrow j}$	$\displaystyle=\phi_{r}(F_{\mathcal{C}_{c}\rightarrow v_{j}}\sum_{v_{i}\in\mathcal{C}_{c}}w_{i\rightarrow j}\cdot f_{e}(\mathcal{G}_{v_{i}}),f_{e}(\mathcal{G}_{v_{j}})),$		(2)
	s.t.	$\displaystyle\quad w_{i\rightarrow j}=\phi_{w}(f_{\mathcal{P}}(v_{i},v_{j},\mathcal{E})),$		(3)

where the function $\phi_{w}$ maps a reachable vector $f_{\mathcal{P}}(v_{i},v_{j},\mathcal{E})$ into a weight value, and the function $\phi_{r}$ computes the similar score between $v_{j}$ and the $c$-th class nodes. The normalization factor $F_{\mathcal{C}_{c}\rightarrow v_{j}}$ of the $c$-th category w.r.t. $v_{j}$ is defined as

$\displaystyle F_{\mathcal{C}_{c}\rightarrow v_{j}}=\frac{1}{\sum_{v_{i}\in\mathcal{C}_{c}}w_{i\rightarrow j}}.$

(4)

For the relation function $\phi_{r}$ and the weight function $\phi_{w}$, we may choose some subnetworks to instantiate them in practice. The detailed implementation of our model can be found in Section 4.

According to the class-to-node relationship function in Eqn. (2), given a query node $v_{j}$, we can obtain a score vector $\mathbf{s}_{\mathcal{C}\rightarrow j}=[s_{\mathcal{C}_{1}\rightarrow j},\cdots,s_{\mathcal{C}_{C}\rightarrow j}]^{\intercal}\in\mathbb{R}^{C}$ after computing the relations to all classes . The indexed category with the maximum score is assumed to be the estimated label. Thus, we can define the loss function based on cross entropy as follows:

$\displaystyle\quad\mathcal{L}=-\sum_{v_{j}}\sum_{c=1}^{C}y_{j,c}\log\hat{y}_{\mathcal{C}_{c}\rightarrow j},$

(5)

where $y_{j,c}$ is a binary indicator (i.e., 0 or 1) of class label $c$ for node $v_{j}$, and the softmax operation is imposed on $s_{\mathcal{C}_{c}\rightarrow j}$, i.e., $\hat{y}_{\mathcal{C}_{c}\rightarrow j}=\exp(s_{\mathcal{C}_{c}\rightarrow j})/\sum_{k=1}^{C}\exp(s_{\mathcal{C}_{k}\rightarrow j})$. Other error functions may be chosen as the loss function, e.g., mean square error. In the regime of general classification, the cross entropy loss is a standard one that performs well.

Given a training set $\mathcal{V}_{tr}$, we expect that the best performance can be obtained on the validation set $\mathcal{V}_{val}$ after optimizing the model on $\mathcal{V}_{tr}$. Given a trained/pretrained model $\Theta=\{f_{e},\phi_{w},\phi_{r}\}$, we perform iteratively gradient updates on the training set $\mathcal{V}_{tr}$ to obtain the new model, formally,

$\displaystyle\Theta^{\prime}=\Theta-\alpha\nabla_{\Theta}\mathcal{L}_{tr}(\Theta),$

(6)

where $\alpha$ is the updating rate. Note that, in the computation of class scores, since the reference node and query node can be both from the training set $\mathcal{V}_{tr}$, we set the computation weight $w_{i\rightarrow j}=0$ if $i=j$ in Eqn. (3). After several iterates of gradient descent on $\mathcal{V}_{tr}$, we expect a better performance on the validation set $\mathcal{V}_{val}$, i.e., $\underset{\Theta}{\min}~{}\mathcal{L}_{val}(\Theta^{\prime})$. Thus, we can perform the gradient update as follows

$\displaystyle\Theta=\Theta-\beta\nabla_{\Theta}\mathcal{L}_{val}(\Theta^{\prime}),$

(7)

where $\beta$ is the learning rate of meta optimization (Finn et al., 2017).

During the training process, we may perform batch sampling from training nodes and validation nodes, instead of taking all one time. In the testing stage, we may take all training nodes and perform the model update according to Eqn. (6) like the training process. The updated model is used as the final model and is then fed into Eqn. (2) to infer the class labels for those query nodes.

We evaluate our proposed GIL method on three citation network datasets: Cora, Citeseer, Pubmed (Sen et al., 2008), and one knowledge graph NELL dataset (Carlson et al., 2010). The statistical properties of graph data are summarized in Table 1. Following the previous protocol in (Kipf & Welling, 2017; Zhuang & Ma, 2018), we split the graph data into a training set, a validation set, and a testing set. Taking into account the graph convolution and pooling modules, we may alternately stack them into a multi-layer Graph convolutional network. The GIL model consists of two graph convolution layers, each of which is followed by a mean-pooling layer, a class-to-node relationship regression module, and a final softmax layer. We have given the detailed configuration of the relationship regression module in the class-to-node relationship of Section 4. The parameter $d_{p}$ in Eqn. (9) is set to the mean length of between-node reachability paths in the input graph. The channels of the 1-st and 2-nd convolutional layers are set to 128 and 256, respectively. The scale of the respective filed is 2 in both convolutional layers. The dropout rate is set to 0.5 in the convolution and fully connected layers to avoid over-fitting, and the ReLU unit is leveraged as a nonlinear activation function. We pre-train our proposed GIL model for 200 iterations with the training set, where its initial learning rate, decay factor, and momentum are set to 0.05, 0.95, and 0.9, respectively. Here we train the GIL model using the stochastic gradient descent method with the batch size of 100. We further improve the inference learning capability of the GIL model for 1200 iterations with the validation set, where the meta-learning rates $\alpha$ and $\beta$ are both set to 0.001.

We compare the GIL approach with several state-of-the-art methods (Monti et al., 2017; Kipf & Welling, 2017; Zhou et al., 2004; Zhuang & Ma, 2018) over four graph datasets, including Cora, Citeseer, Pubmed, and NELL. The classification accuracies for all methods are reported in Table 2. Our proposed GIL can significantly outperform these graph Laplacian regularized methods on four graph datasets, including Deep walk (Zhou et al., 2004), modularity clustering (Brandes et al., 2008), Gaussian fields (Zhu et al., 2003), and graph embedding (Yang et al., 2016) methods. For example, we can achieve much higher performance than the deepwalk method (Zhou et al., 2004), e.g., 43.2% vs 74.1% on the Citeseer dataset, 65.3% vs 83.1% on the Pubmed dataset, and 58.1% vs 78.9% on the NELL dataset. We find that the graph embedding method (Yang et al., 2016), which has considered both label information and graph structure during sampling, can obtain lower accuracies than our proposed GIL by 9.4% on the Citeseer dataset and 10.5% on the Cora dataset, respectively. This indicates that our proposed GIL can better optimize structure relations and thus improve the network generalization. We further compare our proposed GIL with several existing deep graph embedding methods, including graph attention network (Velickovic et al., 2018), dual graph convolutional networks (Zhuang & Ma, 2018), topology adaptive graph convolutional networks (Du et al., 2017), Multi-scale graph convolution (Abu-El-Haija et al., 2018), etc. For example, our proposed GIL achieves a very large gain, e.g., 86.2% vs 83.3% (Du et al., 2017) on the Cora dataset, and 78.9% vs 66.0% (Kipf & Welling, 2017) on the NELL dataset. We evaluate our proposed GIL method on a large graph dataset with a lower label rate, which can significantly outperform existing baselines on the Pubmed dataset: 3.1% over DGCN (Zhuang & Ma, 2018), 4.1% over classic GCN (Kipf & Welling, 2017) and TAGCN (Du et al., 2017), 3.2% over AGNN (Thekumparampil et al., 2018), and 3.6% over N-GCN (Abu-El-Haija et al., 2018). It demonstrates that our proposed GIL performs very well on various graph datasets by building the graph inference learning process, where the limited label information and graph structures can be well employed in the predicted framework.

Meta-optimization: As can be seen in Table 3, we report the classification accuracies of semi-supervised classification with several variants of our proposed GIL and the classical GCN method (Kipf & Welling, 2017) when evaluating them on the Cora dataset. For analyzing the performance improvement of our proposed GIL with the graph inference learning process, we report the classification accuracies of GCN (Kipf & Welling, 2017) and our proposed GIL on the Cora dataset under two different situations, including “only learning with the training set $\mathcal{V}_{tr}$" and “with jointly learning on a training set $\mathcal{V}_{tr}$ and a validation set $\mathcal{V}_{val}$". “GCN /w jointly learning on $\mathcal{V}_{tr}$ & $\mathcal{V}_{val}$" achieves a better result than “GCN /w learning on $\mathcal{V}_{tr}$" by 3.6%, which demonstrates that the network performance can be improved by employing validation samples. When using structure relations, “GIL /w learning on $\mathcal{V}_{tr}$" obtains an improvement of 1.9% (over “GCN /w learning on $\mathcal{V}_{tr}$”), which can be attributed to the building connection between nodes. The meta-optimization strategy (“GIL /w meta-training from $\mathcal{V}_{tr}$ $\rightarrow$ $\mathcal{V}_{val}$" vs “GIL /w learning on $\mathcal{V}_{tr}$”) has a gain of 2.9%, which indicates that a good inference capability can be learnt through meta-optimization. It is worth noting that, GIL adopts a meta-optimization strategy to learn the inference model, which is a process of migrating from a training set to a validation set. In other words, the validation set is only used to teach the model itself how to transfer to unseen data. In contrast, the conventional methods often employ a validation set to tune parameters of a certain model of interest.

Network settings: We explore the effectiveness of our proposed GIL with the same mean pooling mechanism, but with different numbers of convolutional layers, i.e., “GIL + mean pooling" with one, two, and three convolutional layers, respectively. As can be seen in Table 3, the proposed GIL with two convolutional layers can obtain a better performance on the Cora data than the other two network settings (i.e., GIL with one or three convolutional layers). For example, the performance of ‘GIL /w 1 conv. layer + mean pooling" is slightly decreased by 1.7% over “GIL /w 2 conv. layers + mean pooling" on the Cora dataset. Furthermore, we report the classification results of our proposed GIL by using mean and max-pooling mechanisms, respectively. GIL with mean pooling (i.e., “GIL /w 2 conv layers + mean pooling") can get a better result than the GIL method with max-pooling (i.e., “GIL /w 2 conv layers + max-pooling"), e.g., 86.2% vs 85.2% on the Cora graph dataset. The reason may be that the graph network with two convolutional layers and the mean pooling mechanism can obtain the optimal graph embeddings, but when increasing the network layers, more parameters of a certain graph model need to be optimized, which may lead to the over-fitting issue.

Influence of different between-node steps: We compare the classification performance within different between-node steps for our proposed GIL and GCN (Kipf & Welling, 2017), as illustrated in Fig. 2. The length of between-node steps can be computed with the shortest path between reference nodes and query nodes. When the step between nodes is smaller, both GIL and GCN methods can predict the category information for a small part of unlabeled nodes in the testing set. The reason may be that the node category information may be disturbed by its nearest neighboring nodes with different labels and fewer nodes are within 1 or 2 steps in the testing set. The GIL and GCN methods can infer the category information for a part of unlabeled nodes by adopting node attributes, when two nodes are not connected in the graph (i.e., step=$\infty$). By increasing the length of reachability path, the inference process of the GIL method would become difficult and more graph structure information may be employed in the predicted process. GIL can outperform the classic GCN by analyzing the accuracies within different between-node steps, which indicates that our proposed GIL has a better reference capability than GCN by using the meta-optimization mechanism from training nodes to validation nodes.

Influence of different label rates: We also explore the performance comparisons of the GIL method with different label rates, and the detailed results on the Pubmed dataset can be shown in Fig. 2. When label rates increase by multiplication, the performances of GIL and GCN are improved, but the relative gain becomes narrow. The reason is that, the reachable path lengths between unlabeled nodes and labeled nodes will be reduced with the increase of labeled nodes, which will weaken the effect of inference learning. In the extreme case, labels of unlabeled nodes could be determined by those neighbors with the $1\sim 2$ step reachability. In summary, our proposed GIL method prefers small ratio labeled nodes on the semi-supervised node classification task.

Inference learning process: Classification errors of different epochs on the validation set of the Cora dataset can be illustrated in Fig. 5.3. Classification errors are rapidly decreasing as the number of iterations increases from the beginning to 400 iterations, while they are with a slow descent from 400 iterations to 1200 iterations. It demonstrates that the learned knowledge from the training samples can be transferred for inferring node category information from these reference labeled nodes. The performance of semi-supervised classification can be further increased by improving the generalized capability of the Graph CNN model.

Module analysis: We evaluate the effectiveness of different modules within our proposed GIL framework, including node representation $f_{e}$, path reachability $f_{\mathcal{P}}$, and structure relation $f_{r}$. Note that the last one $f_{r}$ defines on the former two ones, so we consider the cases in Table 5.3 by adding modules. When not using all modules, only original attributes of nodes are used to predict labels. The case of only using $f_{e}$ belongs to the GCN method, which can achieve 81.5% on the Cora dataset. The large gain of using the relation module $f_{r}$ (i.e., from 81.5% to 85.0%) may be contributed to the ability of inference learning on attributes as well as local topology structures which are implicitly encoded in $f_{e}$. The path information $f_{\mathcal{P}}$ can further boost the performance by 1.2%, e.g., 86.2% vs 85.0%. It demonstrates that three different modules of our method can improve the graph inference learning capability.

Computational complexity: For the computational complexity of our proposed GIL, the cost is mainly spent on the computations of node representation, between-node reachability, and class-to-node relationship, which are about $O((n_{tr}+n_{te})*e*d_{in}*d_{out})$, $O((n_{tr}+n_{te})*e*P)$, and $O(n_{tr}*n_{te}d_{out}^{2})$, respectively. $n_{tr}$ and $n_{te}$ refer to the numbers of training and testing nodes, $d_{in}$ and $d_{out}$ denote the input and output dimensions of node representation, $e$ is about the average degree of graph node, and $P$ is the step length of node reachability. Compared with those classic Graph CNNs (Kipf & Welling, 2017), our proposed GIL has a slightly higher cost due to an extra inference learning process, but can complete the testing stage with several seconds on these benchmark datasets.