Content and structure based attention for graph node classification

2.1 Graph neural network

Convolutional neural networks (CNNs) were used to extract features from images [15, 51]. Motivated by the effectiveness of CNN, the graph convolution operation is designed to extract information from graphs, which generally falls into two categories: spectral and spatial methods [6, 43]. Bruna et al. [14] utilized Fourier base vector to perform convolution in the spectral domain. ChebNet [27] introduced a well-approximated K-order Chebyshev polynomials for convolution operations, in which the computationally expensive Laplacian eigen decomposition is removed. Spatial methods are defined by a message-passing mechanism operating on the target node and its topological neighbors. The most representative early work is the algorithm GCN [45]. It conducts the layer-wise convolution operation iteratively in order to expand a node’s neighborhood, so as to aggregate the neighbor nodes’ feature to update its representation. Different from GCN, GraphSAGE [49] generates a node’s representation by aggregating features from a fixed number of neighbors, which can deal with inductive learning for unseen nodes or entirely new graphs. Further, GNNs have been widely studied from various perspectives, including over-smoothing problem [7], the adversarial attack and defense [50], and the model explainability [13]. Simplifying graph convolutional network (SGC) [10] considers that GCN may inherit unnecessary complexity and computation. Therefore, it removes nonlinearities between GCN layers, resulting in a linear model for repeated feature transformation and propagation. Labeling real data has a huge cost, but when labels are limited, GNN performance suffers a severe drop. Contrastive graph poisson networks (CGPN) [40] improves model performance by efficiently propagating limited labels throughout the graph. K-hop graph neural networks (k-hopGNNs) [12] update the representation of nodes by aggregating information from its k-hop neighborhood and immediate neighbors, which solves the problem that GNNS cannot recognize basic graph properties. The framework recognizes connectivity and triangular degrees of freedom. Two-level graph neural network (TL-GNN) [52] proposes a novel subgraph counting method based on dynamic programming algorithm that combines subgraph level and node-level information to enrich the features captured by the graph neural network, such as high-level information and node-level information. Furthermore, it overcomes the characterization limitation of existing neural networks, which is caused by local permutation problem. Multiresolution reservoir graph neural network (MRGNN) [23] reduces the high computational cost in the process of model training by generating explicit k-hop unsupervised graph representation processing, and excessive smoothing will occur in reservoir calculation when iterating graph structure. In general, this algorithm has absolute efficiency advantage over traditional algorithms, and maintains the performance. Weighted feature fusion of convolutional neural network and graph attention network (WFCG) [53] integrates convolutional neural network and graph neural network with the goal of complementary advantages, so as to fully explore high-dimensional features and achieve excellent results in hyperspectral images. Meta-learning spatial-temporal graph attention network (MetaSTGAT) [32] captures the dynamic changes of nodes in the graph based on the graph neural network, and then performs dynamic weighting.Furthermore, the model also takes advantage of the potential correlation between spatial and temporal information through graph neural network to improve the effectiveness of the model.

2.2 Attention mechanism

It is intuitive that the impact of each neighbor node is different when aggregating its features to the central node. To deal with this problem, the algorithm GAT utilizes a self-attention mechanism to learn the different contributions from each neighbor node and aggregates information from these neighbors based on the learned weights. Graph attention mechanisms have been used in many directions, such as targeted drug research [41, 59] and molecular property prediction [4]. Li et al. [29] demonstrated that GAT is dataset-dependence and the distributions across heads and layers are uniform. They adapted GAT by proposing margin-based constraints to reduce information propagation among nodes belonging to different classes. However, in most current attention-based approaches, the learned aggregation weights are based on node features, and they neglect other useful information inheriting in graph structure. Multi-view graph attention networks (MGAT) [56] explore an attention-based model that learns node representation from each view, and design a novel regularization term constraint for this algorithm, in order to cooperatively integrate multiple types of relationships in different views. To improve the generalization performance of the model. It can capture various relationships in the multi-view network, and then update the low-dimensional representation of nodes, and finally characterize the complex types of proximity relationships in the graph. Graph conjoint attention networks (CATs) [1] have proposed combining content and structure intervention to calculate attention score, and good results are achieved. However, fatally, it requires a large number of heavy and complex learning tasks to obtain additional representations of nodes, and the experiment lacks a convincing explanation. Structural attention network (SAN) [1] uses transition matrix to extract structural information among nodes. In order to distinguish the structure of multi-order in the graph, the output features of nodes in the graph are expressed as series of multi-order features. Although structural information is beneficial to the weighting process of the model, the node content information of the model is ignored in the weighting process, so there are limitations. Sparse graph attention networks (SGATs) [57] found that Gats were prone to overfitting and could not avoid noise interference when dealing with a large number of graph structure data. Therefore, SGATs sets activation state for connections by generating edge sparse maps, thus eliminating noise connections and maintaining model classification accuracy. Path reliability-based graph attention networks (PRGATs) [54] use multi-hop adjacent context information in the calculation of attention scores, which further expands the receptive domain of the network and captures the dependence relationships in a farther range. Solved the problem that GAT could not capture multi-hop neighbor information. Secondly, the model also uses an attention layer based on path reliability to further improve the performance of the graph against attacks. However, these models hardly fully exploit the potential of attention mechanism. Therefore, we propose to use both content and structure information to learn better attention patterns for node classification. We use a lightweight attention mechanism that greatly reduces the learning stress of the model, is more interpretive, and yields better results.

We follow the method introduced in GAT for content coefficient generation. For a L-layer model, the content coefficient f _ij is calculated as Equation (1). f _ij describes the relevance between two adjacent nodes i and j, which is normalized among its neighbourhood.

f ij = exp ( σ ( α T · [ W l h i | | W l h j ] ) ) ∑ k ∈ N i exp ( σ ( α T · [ W l h i | | W l h k ] ) ) ,(1) where ∥ is the concatenation operation, and σ (·) is a non-linear activation function, such as a LeakyReLU. and α ∈ ℝ 2 F are parameters which need to be tuned in the training. The bigger the value of f _ij , the more important the relevance between node i and j, relative to other neighbors.

Considering the adjacent matrix A that describes the structural information, we generates the structure coefficients from it. Please note that A needs to add a self-connection, because the node’s own information is the key to node feature update. For node i, a _i  ∈ A denotes the adjacency information between it and the other nodes. Therefore, a intuitive way to evaluate the structure coefficient between node i and node j is shown as Equation (2).

s ij = ∑ k = 1 V ( a ik ∑ m = 1 V a im a jk ∑ n = 1 V a jn ) .(2)

Note that the adjacency matrix A needs to be normalized, which guarantees the value of s _ij is between 0 and 1. The bigger the value of s _ij , the more similar their structure is. For example, if node i and node j share lots of neighbors or they allocate in the same community, s _ij will be large.

In order to incorporate content coefficients and structure coefficients, we introduce two learnable parameters g _f and g _s to adjust the relative importance between s _ij and f _ij . r _f and r _s are normalized results of g _f and g _s respectively, as shown in Equations (3) and (4).

r f = exp ( g f ) exp ( g f ) + exp ( g s ) .(3)

r s = exp ( g s ) exp ( g f ) + exp ( g s ) .(4)

Then, the attention weights are computed as

e ij = exp ( r f · f ij + r s · s ij ) ∑ k ∈ N i exp ( r f · f ik + r s · s ik ) .(5)

In Equation (5), r _f and r _s are used to control their proportions between f _ij and s _ij . e _ij measures the influence of node j on node i. Note that e _ij is different from e _ji , because node i and node j have different neighbors.

After getting attention weights from the center’s neighbors, it features can be updated according to the messaging passing mechanism.

h i l + 1 = σ ( ∑ j ∈ N i e ij W l h j l ) .(6)

To make the self-attention calculation more stable, we applied multi-head attention for feature transformation and concatenated the resulting features as the returned output:

h i l + 1 = K ‖ k = 1 σ ( ∑ j ∈ N i e ij k W l h j l ) .(7)

We set K = 8. Also, we used the Dropout mechanism and set it to 60 percent. This means that during model training, the activation value of the node stops working with a certain probability. Because this mechanism alleviates the over-dependence of some local features, it improves the model generalization. Secondly, this measure will reduce the complexity of the model in the forward propagation process and improve the training efficiency of the model. In addition, it can effectively alleviate the occurrence of overfitting and achieve the regularization effect to a certain extent.

After updating each node through information aggregation, we can obtain the corresponding class label of each node. In general, the dimension of the node representation obtained through the neural network is the same as the number of categories of the dataset. After processing by softmax, each element in the node representation represents the probability that it belongs to the corresponding class, and the class with the highest probability is the predicted result.

In the semi-supervised node classification task, we use standard cross entropy as the objective function, and use backpropagation to optimize the parameters in the model. Our goal is to minimize the inconsistency between the ground truth label and the prediction label. The specific formula is as follows:

L = - ∑ i ∈ T ∑ k ∈ C y ik log y ˜ ik + λ ∥ W ∥ 2 ,(8) among them, y and y ˜ represent true label and predicted result, respectively. C represents the collection of categories, T is the set of training nodes. We obtain the optimal model through multiple epochs of learning. λ is a regularization parameter, which controls the complexity of model parameters, so as to prevent overfitting and improve the generalization ability of the model.

For the node classification, the cross entropy loss is adopted, in which the inconsistence between the ground true labels and the predicted labels is minimized. In the training state, we construct the two-layer network structure for the proposed approach. The first layer utilizes multi-head attention. The output of the second layer is used to predict, so multi-head attention is no longer sensible. The whole process is described in Algorithm 1. Note that it would be run for multiply epochs to achieve convergence.

4.1 Datasets

We conducted experiments on three widely-used datasets, including Cora, Cite and Pubmed [21, 34]. They are standard citation network, in which nodes represent documents and edges represent citations. The original node features correspond to elements of a bag-of-words representation of a document. And, each node has a class label. All datasets are splitted to three parts: training, validation and testing. Considering the huge amount of nodes and edges in Pubmed, a connected subgraph is selected for our experiments. Table 1 showns the statistics of these datasets.

We compared out method with nine typical algorithms, including multilayer perceptron (MLP), Deepwalk, text-associated deep walk (TADW), deep graph infomax (DGI), GCN, edge enhanced graph neural network (EGNN), CAT, heat kernel graph convolutional network (HKGCN) and GAT. For convenience, we name the proposed model as content- and structure-based graph attention network (CSGAT).

MLP is a three-layer artificial neural network, including input layer, hidden layer and output layer. Different layers of MLP neural network are fully connected. It is the first neural network proposed to solve classification problems. We set the number of hidden units to 64.

Deepwalk 1 is a representative and successful work of early network representation learning. Deepwalk learns a social representation of a network from truncated random walks. It is also a method that only considers graph structure information when learning graph representation.

TADW 2 [5] takes advantage of the extra attribute information of nodes by designing related algorithms to simultaneously consider and embed the text information of nodes in the graph network into the final low-dimensional distributed representation.

DGI 3 [36] is a node level graph representation learning architecture that enables unsupervised learning. In order to obtain node representations, it trains an encoder model to maximize the mutual information for capturing the global information content of the entire graph.

GCN 4 [45] is a semi-supervised graph convolutional network, which introduces a convolution kernel that can be optimized to optimize the convolution parameters in the training process and achieve accurate feature extraction. It encode a localized approximation model for spectral graph convolutions by terms of layer-wise feature propagation, linear transformation, and pointwise nonlinear activation.

EGNN 5 [22] is a novel graph convolution framework, which solves the problem that GCN does not make full use of multiple edge features. It uses edge features across network layers to make more efficient use of one-dimensional edge features, and modifies the existing model to make use of multi-dimensional edge features using double random normalization.

CAT-I-MF 6 [44] is a conjoint attentions network. It incorporates the feature-based attention with structural interventions which may describe the global relation among nodes. It uses matrix decomposition to solve the objective function approaching adjacency matrix to obtain the structure representations. The resulting representations are used to capture the weighted mean attention with feature-based correlation.

HKGCN 7 [17] generalizes the SGC as a linear model by thermonuclear. SGC simplifies the model by removing the nonlinearity and weight matrix of all continuous layers in GCN. In this way, HKGCN can be used as a low-pass filter, which is conducive to the fast smooth convergence of feature propagation, and then the aggregation of local information. The performance of the model is improved while maintaining the efficiency advantage of the model.

GAT 8 [35] is a semi-supervised neural network which considers the attention mechanism. To compute the hidden representations of a center node, it employ a self-attention mechanism for assigning weights to the neighbors. However, the weight distribution is based on the content of low-order nodes, and the structure information is completely ignored, so the model has limitations.

4.3 Parameter settings

Our uses a two-layer model. The first layer is multi-head convolution, which consists of eight graph convolutions. Before entering the second layer, we concatenate the output of the first layer. The second layer consists of a single graph convolution, followed by a softmax activation, and its output is used for the classification task, and the element corresponding to the maximum value of the final output is the prediction result. To prevent overfitting, regularization is used. During training, we use λ = 0.0005 for Cora and Cite datasets, λ = 0.001 for Pubmed. Also, Dropout [31] p = 0.6 is applied to the input of each layer. All the above measures can effectively prevent overfitting and improve the generalization performance of the model.

The training objective is to minimize the cross-entropy on the training nodes, and the learning rate is 0.005 for all datasets except Pubmed which is 0.01. During the training process, we used an early stop strategy for the cross-entropy loss of the validation nodes, with a patience of 100 epochs. That is, if the validation loss does not decrease within 100 epochs, we stop training.

4.4 Evaluation

The experimental results of all methods are evaluated by Micro-F1, Macro-F1 and Weighted-F1. In those evaluations, precision P and recall R will be used in the calculation process.

P = TP TP + FP .(9)

R = TP TP + FN .(10)

Among them, TP is the number of instances which are positive and predicted correctly. FP is the number of instances which are negative but predicted to be positive. And, FN is the number of instances which are positive but predicted to be negative.

Equations (9) and (10) are calculated over all tested instances, which means that they do not need to distinguish between categories. Micro-F1 directly uses the precision p and recall R to calculate the F1-score:

Micro - F 1 = 2 PR P + R .(11)

If Equations (9) and (10) are calculated for each category, Macro-F1 can be calculated based on them. Specifically, denote P _e and R _e as precision and recall for class label e, respectively. Then, Macro-F1 can be calculated:

Micro - F 1 = ∑ e ∈ C 2 P e R e P e + R e | C | .(12)

Weighted-F1 considers the importance of different categories. The ratio a _e of the number of instances in each category e to the total number of instance is used as the weight to calculate it:

Weighted - F 1 = ∑ e ∈ C a e 2 P e R e P e + R e .(13)

For each set of testing data, all aproaches are run ten times to obtain the statistically steady performance. Table 2 records the summary of results in terms of Micro-F1, Macro-F1 and Weighted-F1 over three datasets. For each measure, we highlight the best results over each dataset in bold. MLP is a network embedding method based on word vector information extraction. Deepwalk is a random walk-based network embedding method. We can see that graph weighted convolution based methods like GCN, GAT, etc. outperform MLP and Deepwalk. DGI is an unsupervised model, so its model parameters do not perform as well as semi-supervised models in the absence of effective optimization. Interestingly, EGNN exploits edge features but does not yield overall performance advantages over GCN. CAT uses structural interventions to learn new node representations in model training. However, the lack of accurate information extraction mechanism makes the performance greatly limited. HKGCN, as a simplified version of the GCN model, not only improves the model efficiency, but also achieves stronger performance in some experimental structures. It is worth noting that GCN based on topological weighting and GAT that introduces node content attention mechanism usually have good performance. However, our method effectively improves GAT, making its graph structure information and node content a dual evaluation metric for the attention mechanism. This enables our model to discover meaningful neighbor nodes better than traditional method assignments. In addition, the structure-based attention used by the model is lightweight and efficient. It does not need to be trained in the process of model training, but only needs to simply traverse the graph structure before training, so that the structural information can be effectively extracted accurately. This mechanism can effectively extract higher-order structure information. In the following chapters, we will use heatmap to visualize it to prove its effectiveness. CSGAT algorithm demonstrates the best performance being achieved across all three datasets. It is worth mentioning that because we adopt more advanced attention mechanism compared with GAT, we can optimize the model parameters more efficiently, which speeds up the convergence rate of the model, which means that the training time is effectively shortened. In conclusion, the experimental results verify that the mixture of content-based and structure-based attention is effective.

We perform complexity analysis on the proposed algorithm CSGAT and compare it with GAT. As shown in Table 3, we record the running time of the algorithm on the Cora dataset to represent the complexity of the algorithm. It can be seen that our algorithm takes slightly more time than GAT in a single epoch because our algorithm makes full use of the graph information. However, thanks to the complementary advantages of content and structure information, our algorithm can converge faster in graph learning, which makes CSGAT reach the optimal solution with less number of epochs. In other words, CSGAT can achieve better performance in less total time. Therefore, CSGAT achieves better results in both running time and performance.

In this section, we analyze the parameter sensitivity through the Cite data set and report the performance of ours with different number of multi-head attention. The results are shown in Fig. 3. Note that when the number of multi-head attention is set to 1, the multi-head attention will be removed. It can be seen that with the increase of the number of multi-head attention, the overall performance of ours shows a trend of improvement. Therefore, to obtain the best performance on a certain dataset, we recommend searching for this parameter value first.

OPEN IN VIEWER

Fig. 3

Parameter analysis of different number of multi-head attention K.

To further explore the key component of our proposed hybrid attention mechanism, we design two variants of CSGAT method for ablation analysis, named CSGAT-content and CSGAT-structure. Note that CSGAT-content is the same as GAT in fact. CSGAT-content only utilizes the content-based attentions, while CSGAT-structure only utilizes the structure-based attentions. For convenience, all variants are single-layered, including no dropout and multi-head. In this way, other factors that affect the experimental results are removed. Table 4 reports the results of the comparing algorithms. It clearly indicates that the hybrid attention mechanism achieves the best performance. And, the content-based attention achieves the worst performance, which indicates the structure-based attention is superior to the content-based attention to some extend.

4.8.1 Heatmap analysis

We test the ability of CSGAT-structure to discover dominant neighbors under different graph structures, and visualize it as a heatmap in Fig. 4. In Fig. 4(a) we design a large community, and through CSGAT-structure, we can find important neighbor nodes within 2-hop neighbors. In Fig. 4(b)-(d), we design several special subgraphs, all of which contain communities. CSGAT-structure can well judge whether the central node is in the community or not, and further confirm whether the neighbor nodes belong to the same community or not. We eliminate the community in Fig. 4(e), (f), as we can see from the heatmap, the weights of the neighbor nodes have changed. Nodes that originally belonged to different communities from the central node gained relatively greater weights due to the elimination of the community structure. This is very beneficial.

OPEN IN VIEWER

Fig. 4

The heatmap of the attention mechanism based on topology structure under different graph structures. Left: A simple artificially constructed graph, the yellow node is the center node, and the blue node is the neighbor node, and the two are connected by edges; Middle: Visualization of weights; Right: Contours of weights.

4.8.2 Parameter sensitivity

As shown in Equation (5), r _f and r _s adjust the content-based scores and structure scores, leading to a standard weighted average. The two variable are tuned in the training. It is interesting to explore the importance of them in the proposed model. We visualized these those two weight coefficients in CSGAT model over the datasets Cora, Cite and Pubmed, as shown in Fig. 6. According to Fig. 6, the content-based scores are more important over dataset Cora, while the structure-based scores are more important over datasets Cite and Pubmed. Because Cora has the densest network structure in all datasets, it also has the most node classes, which means that there are connections between a large number of nodes of different classes. Therefore, there is a lot of noise in the structural information in Cora, which degrades the performance of the structure-based attention mechanism. Then, thanks to the adaptive mechanism of the network, the weight distribution takes the content as the main index. This does not mean that structure-based attention mechanisms have completely failed. As mentioned earlier, our attention mechanisms are mixed. Under different datasets, the attention mechanism will adopt different strategies, that is, different proportions, to achieve the optimal solution of the model. To sum up, both weighted scores play a role in constituting the attention of the model, however, their importance is different in different application domains.

OPEN IN VIEWER

Fig. 5

Neighbors and their weights of node p408 in dataset Cite. (a), (b), (c) represent the neighbors, weights in CSGAT-Content and weights in CSGAT, respectively.

OPEN IN VIEWER

Fig. 6

An illustration of weight coefficients between content-based scores and structure-based scores.