HopGAT: Hop-aware Supervision Graph Attention Networks for Sparsely Labeled Graphs

Existing attention-based graph methods usually specify the maximum hop value between a center node and its neighbors, e.g. 1, in GATs. Then, the numerical hop value in a graph is coarsely equivalent to a Boolean variable representing whether a node is a neighbor of another node. However, as we have noted in Observation 1, the class labels of neighboring nodes with a smaller hop value are more likely to be consistent with those of their center nodes in a homogeneous graph network, and the hop value offers more information than a Boolean variable.

In this study, a hop value is used to express the closeness or similarity of a node to its center node. Therefore, we encode a hop value into a $d$-dimensional vector as $he$:

where $max_{hv}$ is the pre-defined maximal hop value, $max(\cdot)$ is a maximum value function, $d$ is the dimension of the hop embedding, $i$ is the index of the dimensions, $hv$ is the corresponding hop value, $sin$ and $cos$ are sine and cosine functions, respectively, and $he_{hv}$ represents the hop encoding for the hop value $hv$.

Through this definition, not only the absolute hop value but also the relative hop value can be learned since, as a fixed offset $p$, $he_{hv+p}$ can be transformed as a linear function of $he_{hv}$. Since the number of heads in each layer can be different, the dimensions of nodes in each hidden layer are also different. Therefore, the dimension of the hop embedding in each layer may be different.

We propose two attention mechanisms based on the above hop encoding: product-based attention and addition-based attention.

For a node pair $(i,j)$, $i$ and $j$ are the center and neighboring nodes, respectively. $hv_{i,j}$ is the hop value from $i$ to $j$. The hop encoding for the $t$th layer is written as $he^{t}$, where each line represents a hop encoding for a hop value.

• 1.

  Product-based Attention This attention mechanism is mainly based on the dot product between the embeddings of two nodes.

  $$e_{ij}=a_{c}(h_{i})\odot(a_{n}(h_{j})+lookup(a_{he}(he^{t}),hv_{i,j}))$$

  (7)

  $e_{ij}$ indicates the importance of node $j$ to node $i$, $a_{c}$, $a_{n}$ and $a_{he}$ are three independent single-layer feedforward neural networks, $\odot$ denotes the dot product operation, and $lookup$ is a function that looks up the hop encoding for the hop value $hv_{i,j}$ in $he^{t}$.

• 2.

  Addition-based Attention This mechanism is based on the addition operation on two node embeddings. The attention coefficients are formulated as follows:

  $$\begin{split}e_{ij}=LeakyReLU(lookup(a_{he}(he^{t}),hv_{i,j})\\ \odot(a_{c}(h_{i})||a_{n}(h_{j})))\end{split}$$

  (8)

  where the symbol $||$ is a concatenation operation. The LeakyReLU activation function is used to execute the non-linearization operation.

To make coefficients easily comparable, we normalize them across all neighbors $j$ using the softmax function:

where $\mathcal{N}_{i}$ is the neighboring node set of node $i$. Once $\alpha_{ij}$ is obtained, we use Equations 3 - 4 to perform the final node classification.

The hop value of self-connection is defined as 0, and it is also encoded into a non-zero hop encoding vector. Through this design, all attention coefficients are uniformly calculated according to the node features and hops.

The hop value represented in the graph data is a label-free and effective indicator for quantifying the correlation between two nodes. Specifically, the correlation between two directly connected nodes in the graphs should be assigned a larger value, while the coefficient between two indirectly connected or disconnected nodes is expected to have a smaller value. In addition, a prior investigation showed that “classification accuracy depends exponentially on attention correctness” [23] and that the general attention models cannot effectively automatically learn sufficient semantic information from neighbors with different hop values. All of this motivates us to develop a hop-aware approach to supervise the training process for attention coefficients between two nodes.

Generally, the correlation between two nodes becomes weaker when their hop value is over a certain value. Therefore, we set a boundary for the hop value. The coefficients between the center node and its neighboring nodes are uniformly grouped into a default value when the hop value reaches the maximum value, $max_{hv}$, which means a weak connection between two nodes. We formulate the definition of ground-truth attention $e^{GT}$ as follows:

This can be interpreted as follows: the larger the hop value is, the smaller the ground-truth attention.

When the hop value is greater than two, a negative ground-truth attention value will be assigned. This negative value does not indicate a negative association between these two nodes. This coefficient has not been normalized by the softmax function as in Equation 9. After normalization, the attention coefficients will be between 0 and 1, indicating the strong and weak correlation between two nodes.

To be more accurate, we use $e^{kl}_{ij}$ to denote the attention coefficient between nodes $i$ and $j$ of the $k$th head in the $l$th layer, which are produced during the training procedure as in Equations 7 and 8. We use the mean square error to control the distance between the ground-truth attention $e^{GT}$ and the computed coefficients $e^{kl}_{ij}$.

$\mathcal{L}_{att}$ will be used as a part of the loss function to supervise the training process for the attention coefficients between two nodes.

In total, there are $L*K*N*N$ attention coefficients in the calculation of $\mathcal{L}_{att}$. To decrease the computation cost, especially in a graph with a large number of nodes, we thus proposed a random sampling strategy, $sample(r)$, with which a subset of node pairs is sampled with sample ratio $r$.

The number of node pairs with $hv_{i,j}>=max_{hv}$ is greater than that with less than $max_{hv}$. For example, in the Citeseer dataset, there are approximately 12,000 node pairs with less than 2 hops, whereas there is approximately 11,000,000 pairs with more hops. For balancing the distribution between node pairs with hop values of greater or less than $max_{hv}$, $sample(r)$ only samples from the node pairs with hop values greater than $max_{hv}$. Furthermore, we sample each batch differently to guarantee the diversity of the training data. $\mathcal{L}_{att}$ is calculated as follows:

The results for the inductive tasks are listed in Table 4. The improvement column records the improved values of HopGAT against GATs, which shows better performance compared to other baseline methods.

Compared with GATs, the results demonstrate that HopGATs obtain a significant gain across all datasets with different proportions of labeled nodes. Specifically, the smallest improvement is 1.0% for the 80% label rate, and the highest improvement is 5.3% for the 20% label rate. It is observed that given fewer labeled nodes, a higher performance gain is achieved, from 1.2% to 5.3% - except for a small fluctuation at the 80% label rate. The results show that the proposed model is effective in addressing the inductive task on the sparsely labeled graph network.

Another important observation from the table is that we cannot achieve a proportional performance gain by labeling additional nodes. Labeling more nodes, e.g., from 20% to 40%, the performance gains is nearly 6%. With a 40% labeled graph, the performance loss is only 3.9%, from 98.5% to 94.6%, compared to the fully labeled graph. More labeled nodes results in smaller performance gains. Therefore, if necessary, we should balance the cost of labeling more nodes and performance gain.

The results of all transductive tasks are shown in Table 5. Compared with GATs, the maximum improvement for Cora, Citeseer and PubMed are 0.6%, 1.1% and 2.4% respectively. The minimum improvements are 0.0%, 0.4% and 1.1% respectively. This proves the effectiveness of our model on transductive tasks.

We also investigate the improved average performance on individual datasets. The improved average accuracy is 0.42%, 0.74% and 1.54% on the Cora, Citeseer and PubMed datasets, respectively. These datasets include 2708, 3327, and 19717 nodes, respectively. This shows that the larger the graphs are, the more benefit that the proposed model can obtain.

We can observe that the greater the number of labeled nodes, the higher the performance gain obtained on Citeseer and PubMed. This is different from the inductive task, in which fewer labeled nodes results in higher performance gains. This could be caused by the large difference between the mechanisms of inductive and transductive tasks. In the inductive tasks, validation and test nodes are completely unseen in the entire training process, whereas they directly participate in the training process in the transductive tasks. This means that with the HopGAT model, the training nodes could learn more correlations from the validation/test nodes in the transductive tasks, even when the test nodes are not labeled. In addition, the smaller the dataset is, the stronger the randomness during the sampling, which can cause a fluctuation of the performance gains in certain cases.

We investigate the effectiveness of the supervised attention coefficients. We thus generate a visualization of the attention coefficients produced by the proposed HopGAT model. We trained on the training set of PubMed. We record the distribution of the produced attention coefficients during the different training epochs. Figure 5 (a) comes from a head of the 1st layer, and Figure 5 (b) is from the 2nd layer. Similar to Figure 3, the horizontal axis shows the value of the attention coefficients, and the vertical axis records the occurrence number of the coefficients. Compared to Figure 3, there are three clusters that correspond to the attention coefficients for 0, 1 and greater than 1 hop value from left to right.

Comparing Figure 5 (a) to Figure 5 (b), we noticed that the attention coefficients inside the 2nd layer have more clear boundaries among different hop values than those in the 1st layer. This is consistent with the expectation that the signal received from the deeper layer is much stronger than the first layers due to back propagation.

In this section, we evaluate the proposed learning strategy. We train the HopGAT model on PPI with a 100% label rate and the hyperparameters mentioned above. Then, we record the entire training process as a learning curve of the loss for the node classification, attention coefficients, and micro-averaged $F_{1}$ score. We also visualize the changes of $\gamma$ with increasing training epochs.

The value of $\gamma$ is used to balance the node classification and attention supervision loss functions. As shown in Figure 6 (a), at the early stage of training, i.e., the first 100 steps, more powerful supervision on the attention was imposed due to a larger $\gamma$. Once $\mathcal{L}_{att}$ is relatively stable and when reasonable attention coefficients are established, the major energy of the learning strategy turns into $\mathcal{L}_{cls}$ alternatively, as shown in Figure 6 (b) and 6 (c). This is defined as mid-term - from 100 to 1,700 steps.

At the tail of the training process, from epoch 1,700 to 2600, we observed that the learning curve was reasonably smooth and that $\gamma$ was stable and small. $1-\gamma$ is a relatively large value, above 0.8 (one subtracts the value in Figure 6 (a)), and the node classification loss thus draws greater attention from the optimizer. The optimizer adjusts the gradient almost based on the $\mathcal{L}_{cls}$ and therefore may neglect the subsequent impact on $\mathcal{L}_{att}$, which could result in a sharp increase in $\mathcal{L}_{att}$. As shown in Figure 6 (c), we captured these fluctuations four times. We therefore introduce the saturation parameter $\gamma_{str}$ to resist the sudden increase in $\gamma$. In this way, the fluctuations are handled appropriately, and better performance is achieved. Importantly, this type of fluctuation only occurs at the end of the training process, and it is not a necessary appearance for each training procedure.

In Figure 5, another interesting point is that during the first 40 epochs, $\gamma$ is relatively large, and the HopGAT thus pays more attention to the adjustment of $\mathcal{L}_{att}$ and impacts the distribution of the attention coefficients. We can observe the emergence of the three separate clusters in this phase. After the 40 epochs, $\gamma$ starts to be restricted, and the boundaries of the clusters become more clear. This provides evidence that once reasonable supervision of the attention coefficients in the early phase is applied, the subsequent learning of the node classification can be jointly performed.