GraphHop: An Enhanced Label Propagation Method for Node Classification

An undirected graph can be represented by a triple:

where $\mathcal{V}$ denotes a set of $n$ nodes, $\boldsymbol{A}\in\mathbb{R}^{n\times n}$ is the adjacency matrix between nodes, and $\boldsymbol{X}\in\mathbb{R}^{n\times d}$ is the attribute matrix whose $d$-dimensional row vector is an attribute vector associated with each node. In the setting of semi-supervised classification, each labeled node belongs to one class,

Nodes are divided into labeled and unlabeled sets with their indices denoted by

respectively.

Let $\mathcal{H}$ be the set of $n\times c$ matrices with nonnegative entries. Matrix

is the global label embedding matrix. It can be divided into

where $\boldsymbol{H}_{l}$ and $\boldsymbol{H}_{u}$ represent labeled and unlabeled examples, respectively. For labeled examples $i\in\mathcal{L}$, vector $\boldsymbol{h}_{i}$ is an one-hot vector, where $h_{ij}=1$ if $x_{i}$ is labeled as $y_{i}=j$ and $h_{ij}=0$ otherwise. For unlabeled examples $i\in\mathcal{U}$, vector $\boldsymbol{h}_{i}$ is a probability vector whose element $h_{ij}$ is the predicted probability of belonging to class $j$. To classify unlabeled node $i$ in the convergence stage, we assign it the label of the most likely class:

The goal of transductive graph learning is to infer labels of unlabeled nodes (i.e., matrix $\boldsymbol{H}_{u}$), given attribute matrix $\boldsymbol{X}$, adjacency matrix $\boldsymbol{A}$, and labeled examples $\boldsymbol{H}_{l}$. In the extremely small label rate case, the number of examples in the labeled set is much smaller than that in the unlabeled set; namely,

Both the attribute matrix and the label embedding matrix can be treated as signals on graphs. For example, the $d$-dimensional column vectors of attribute matrix $\boldsymbol{X}$ can be viewed as a $d$-channel graph signal. One assumption for semi-supervised learning is that data points that are close in a high density region should have similar attributes and produce similar outputs. This property can be stated qualitatively below.

The smoothness of attributes and labels can be verified by evaluating their means and variances as a function of the length of the shortest path between every two nodes, which is usually measured in terms of the hop count. Here, we propose an alternative approach to verify the smooth label assumption and conduct experiments on the Cora, CiteSeer and PubMed datasets (see Sec. V for more details) using the following procedure.

We add the number of Laplacian frequency components incrementally, reconstruct label embeddings for classification, and show two accuracy curves for each dataset in Fig. 2, where the one using low frequency components is in blue and the one using high frequency components is in red. The blue curve rises up quickly while the red curve increases slowly in all three cases, which support our assumption that label signals are smooth on graphs. Interestingly, the performance does drop when adding more high frequency components for PubMed.

Based on the smoothness assumption of label signals, we expect that a smoothening operation on node attributes and labels helps achieve better classification results. There are several common ways to achieve the smoothening effect, which can be categorized into the following three types.

1. 1.

   Average attributes or label embedding vectors of neighboring nodes. It is well known that the average operation behaves like a lowpass filter [12]. Another reason for taking the average is that nodes have different numbers of $m$-hop neighbors, denoted by $\Omega_{m}$, where $m=1,2,\cdots$. By averaging the attributes/labels of nodes with the same hop distance, we can consider the impact of $m$-hop neighbors for all nodes uniformly.

2. 2.

   Use regression for label prediction. We need to predict labels for a great majority of nodes based on attributes of all nodes and labels of a few nodes. One way for prediction is to train a regressor. In the current setting, the logistic regression (LR) classifier is a better choice due to the discrete nature of the output. Regression (regardless of a linear or a logistic regressor) is fundamentally a smoothening operation since it adopts a fixed but smaller model size to fit a large number of observations.

3. 3.

   Incorporate a smooth regularization term in an objective function. One can introduce a quadratic penalty term and, at the same time, remain consistent with the initial labeling. This is used in the label propagation (LP) method [1, 2] as elaborated below.

The LP method can be formally defined as a minimization of cost function

where $\boldsymbol{Y}_{l}$ is the one-hot label embedding matrix of labeled nodes, $||\cdot||_{F}$ is the Frobenius norm, $\alpha$ is a parameter controlling the degree of the regularization, and $\boldsymbol{L}$ is the unnormalized graph Laplacian. The optimization solution of embedding matrix $\boldsymbol{H}$ in Eq. (5) can be derived equivalently by applying a embedding propagation process, where the $t$th iteration update is

where $\boldsymbol{H}^{(0)}_{l}=\boldsymbol{H}_{l}$ and zeros for unlabeled examples. The update rule can be described by replacing the current label embeddings with their averaged neighbors’ through a look up table plus the initially labeled examples. As shown in Eqs. (5) and (6), we see that the LP method exploits smoothening operations of the first and the third types, respectively.

A closed-form solution to Eqs. (5) and (6) can be equivalently cast in form of

Despite the simple and efficient propagation process in Eq. (6), the LP method is limited in its learning abilities in label embedding vector update in the following three aspects.

• •

  Only label embeddings of immediate (one-hop) neighbors are being propagated at each iteration according to Eq. (6). It could be advantageous to consider label embeddings of nodes in a larger neighborhood.

• •

  The availability of node attributes is not leveraged.

• •

  The current label vectors of unlabeled nodes are fully replaced (Eq. (6)) by propagated embeddings from neighbors of the previous iteration. The simple label update rule limits the ability to learn the correlation of label embeddings between the node itself and its neighbors.

The goal of the initialization stage is to offer good initialize label embedding vectors for all nodes. Recall that the label embedding vector is a $C$-dimensional vector whose elements indicate the probability of a node belonging to class $c=1,\cdots,C$. If a node is a labeled one, its initial embedding is a one-hot (or multi-hot in multi-label classification) vector. If a node has no label, we can train an LR classifier that uses the attributes of the node itself as well its multi-hop neighbors to predict the initial embeddings. This is justified by the underlying assumption of semi-supervised graph learning; namely, nodes of spatial proximity should have similar attributes and produce similar outputs (i.e., labels).

The input to the LR classifier is the averaged attributes of $m$-hops, $m=0,1,\cdots,M$, where $m=0$ denotes the self node. For node $j$, we have the following averaged attribute vectors of dimension $d$:

where $\Omega_{m}(j)$ denotes the $m$-hop neighbors of node $j$. This yields an aggregated attribute matrix, $\boldsymbol{X}_{M}\in\mathbb{R}^{n\times d(M+1)}$, whose $d(M+1)$-dimensional row vector is the concatenation of these $(M+1)$ vectors associated with each node. Mathematically, we can express it as

where $\|$ denotes column-wise concatenation, $\boldsymbol{\tilde{A}}^{m}$ is the normalized $m$-hop adjacency matrix, and $m$ is the hop index. The output of the LR classifier is the initial label embeddings matrix, denoted by $\boldsymbol{H}^{(0)}\in\mathbb{R}^{n\times C}$, of all nodes. This aggregation procedure is illustrated in Fig. 4.

We first use the labeled examples to determine the model parameters of the LR classifier in the training phase. Afterwards, we use the trained LR classifier to infer the initial label embeddings of unlabeled nodes. Mathematically, this is expressed as

where $\mathrm{p}_{\text{model}}$ denotes the predictor based on the LR classifier, $\boldsymbol{Y}$ is the label embeddings of known examples and $\boldsymbol{\theta}$ is the set of learned model parameters.

After initialization, the GraphHop method processes label embedding vectors via a two-step procedure at each iteration as elaborated below.

We analyze the relationship between the lower bound of iteration number, label rate, and the hops number in the label propagation step. The higher-order (large hops) of nodes was efficiently approximated within $k$-hop neighbors in [17]. Here, we call the approximation of each unlabeled node is sufficient if at least one initially labeled examples are captured in its $k$-hop surroundings after iteration, and otherwise insufficient. If all unlabeled nodes are sufficient, we call the iteration sufficient.

We define the shortest distance between nodes $u$ and $v$ as $dist(u,v)$ in the graph. Given initially labeled examples, we partition node set $\mathcal{V}$ into several subsets

where $\mathcal{V}_{0}$ denotes the set of initially labeled nodes,

is the subset of unlabeled nodes that have the same minimum distance (i.e., of $i$ hops) to one of labeled nodes, and $I$ is the maximum distance between an unlabeled node and a labeled one. Since each node will aggregate $k$-hop neighbors embeddings at one iteration, we have the following Lemma.

Based on Lemma 1, we can derive the number of sufficient nodes after $t$ iterations.

It is easy to get the following corollary.

The result in Corollary 1 shows that the relationship between sufficient iterations and the maximum hop number in $K$ is in inverse ratio. Increasing $k$ will decrease the required number of iterations. The initial label rate $j$ and graph density $d$ also have an influence on the iteration number. Yet, the effects are minor due to the logarithm function. Particularly, in a large-scale graph where $j\ll n$, changing the label rate has negligible influence on the iteration number. The same behavior has been shown in the experiment section. In practice, we observe that GraphHop converges in few iterations (usually 10) since few iterations are required to achieve sufficiency.

The time and memory complexities of GraphHop are significantly lower that the traditional training in graph neural networks. The reason is that GraphHop can do minibatch training, which is not available GCN-based methods due to the neighbor expansion problem [11]. The LR classifiers are directly trained based on the output of Eq. (12), where minibatches can be easily applied to matrix $\boldsymbol{H}_{M}^{(t-1)}$ (see lines 6 and 16 in Algorithm 1) as input.

Suppose that the total training minibatch number is $N$, the number of iterations is $t$, the minibatch size is $b$, and the number of classes is $c$. Then, the time complexity of one minibatch propagation is

where the first term comes from label aggregation while the second from label update. The memory usage complexity is

which represents one minibatch embeddings and parameters for the classifiers. Note that the parameter size is fixed and independent of iterations $t$ and scales linearly in terms of the minibatch size $b$.

We evaluate the performance of GraphHop on six representative graph datasets as shown in Table I. Cora, CiteSeer, and PubMed [5] are three citation networks. Nodes are papers while edges are citation links in these graphs. The task is to predict the category of each paper. PPI and Reddit [18] are two datasets of large-scale networks. PPI is a multi-label dataset, where each node denotes one protein with multiple labels in the gene ontology sets (121 in total). Amazon2M [11] is by far the largest graph dataset that is publicly available with over 2 millions nodes and 61 millions of edges obtained from Amazon co-purchasing networks. The raw node features are bag-of-words extracted from product descriptions. We use the principal component analysis (PCA) [19] to reduce their dimension to $100$. Also, we use the top-level category as the class label for each node.

We evaluate GraphHop and several benchmarking methods on the semi-supervised node classification task in a transductive setting at a number of label rates. For citation datasets, we first conduct experiments by following the conventional train/validate/test split (i.e., 20 labels per class) of the training set. Next, we train models at extremely low label rates (i.e., 1, 2, 4, 8, and 16 labeled examples per class). For the PPI, Reddit, and Amazon2M three large-scale networks, the original data splits target at inductive learning scenario, which do not fit our purpose. To tailor them to the transductive semi-supervised setting, we adopt fewer labeled training examples. To be specific, for Reddit and Amazon2M, we pick the same number of examples in each class randomly with multiple label rates for training. For the multi-label PPI dataset, we simply select a small portion of examples randomly in the training. A fixed size of remaining examples is selected as validation while the rest is used as testing. The full data splits are summarized in Table II. For simplicity, we use the percentages of training examples to indicate different data split in reporting performance results.

We implement GraphHop in PyTorch [20]. For the LR classifiers in the initialization stage and the iteration stage, we use the same Adam optimizer with a learning rate of $0.01$ and $5\times 10^{-5}$ weight decay. The batch size is fixed to $512$ for citation networks but adaptive for large-scale graphs since experiments show there is a trade-off using different batch sizes for the latter case. The training epochs are set to $1000$ with an early stopping criterion which stops the classifiers from training and goes to the next iteration. We set the maximum iteration to $100$ for citation datasets and $200$ for large-scale networks. These numbers are large enough for GraphHop to converge as shown in the experiments. For hyperparameters $T$, $\alpha$, and $\beta$, we perform a grid search in the parameter space based on the validation results. The hyperparameter tuning ranges and their final values are listed in Table III and IV, respectively. Note that hyperparameters are tuned for different label rates. We show their values with respect to the largest label rates in Table IV. All experiments were conducted on a machine with a NVIDIA Tesla P100 GPU (16 GB memory), 10-core Intel Xeon CPU ($2.40$ GHz), and $100$ GB of RAM.

We conduct performance benchmarking between GraphHop and several state-of-the-art methods and compare their results for small- and large-scale datasets below.

Since GraphHop is an iterative algorithm, we study test accuracy curves as a function of the iteration number for all six datasets with different label rates in Fig. 5. We have two main observations. First, for Cora, CiteSeer, and PubMed datasets, test accuracy curves converge in about 10, 5, and 4 iterations, respectively. Second, for Reddit and Amazon2M, test accuracy curves achieve their peaks in a few iterations, drop and then converge. The latter is due to over-smoothing of label signals as explained in Sec. V-E. Repeatedly applying smoothing operators will result in the convergence of feature vectors to the same values [27]. It can be alleviated by residual connections [31]. In practice, we can find the optimal iteration number for each dataset by observing the convergence behavior based on the evaluation data.

Furthermore, we need to train an LR classifier for label embedding initialization and propagation through iterative optimization. To achieve this objective, we show the training loss curves of the LR classifiers as a function of the epoch number for all six datasets in Fig. 6. We see that all LR classifiers converge relatively fast. Although fewer labeled nodes tend to demand more iterations to achieve convergence, yet its impact on convergence behavior is minor, which is consistent with Corollary 1.

To demonstrate the efficiency and scalability of GraphHop, we compare training time and memory usage of several methods in Table VII. Here, we focus on benchmarking models that can handle large-scale graphs such as GraphSAGE [18], Cluster-GCN [11], L-GCN [30] and FastGCN [29]. For citation networks of smaller sizes, we adopt their original codes and implement them in a supervised way. For large-scale graphs (i.e., Reddit, PPI, and Amazon2M), we follow the process discussed earlier and set the label rate to the largest. We measure the averaged running time per epoch (or per iteration for GraphHop) and the total training time in seconds. An early stopping is adopted. That is, we record the time when the performance on the validation set drops continuously for five iterations. For memory usage, we only consider the GPU memory ²²2It is measured by torch.cuda.memory_allocated() for PyTorch and tf.contrib.memory_stats.MaxBytesInUse() for TensorFlow. .

Generally speaking, GraphHop can achieve fast training with low memory usage. Although L-GCN has the lowest memory usage, all parameters are fixed without validation applied (validation data are counted in memory consumption for ours and other baselines) so that the comparison may not be fair. To shed light on training complexity and memory usage, we plot the time complexity versus memory usage of different methods on Reddit in Fig. 7 based on the data in Table VII. The lower-left corner of this figure indicates the desired region that has low training complexity and low GPU memory consumption. Furthermore, we can balance the training time and memory usage by changing the batch size as shown in Fig. 8 for GraphHop. By increasing the batch size, the memory consumption goes up in exchange for lower training time.