Self-Attention Empowered Graph Convolutional Network for Structure Learning and Node Embedding

Throughout this paper, lowercase characters represent scalars, and bold lowercase characters and bold uppercase characters represent vectors and matrices, respectively. Unless otherwise specified, the notations employed in this study are listed in Table 1.

Let $\mathcal{G}=(\mathcal{V},\mathcal{E})$ be an undirected graph, where $\mathcal{V}$ and $\mathcal{E}$ represent the sets of nodes and edges, respectively. $|\mathcal{V}|=n$ is the number of nodes and $v_{i}\in\mathcal{V}$ denotes $i$-th node. $e_{ij}\in\mathcal{E}$ represents the edge between $v_{i}$ and $v_{j}$. $\mathcal{N}_{i}=\left\{v_{j}\in\mathcal{V}|e_{ij}\in\mathcal{E}\right\}$ represents the set of one-hop neighbors for node $i$. ${\bf A}\in\mathbb{R}^{n\times n}$ is the adjacency matrix. $A_{ij}=0$ if $e_{ij}\notin\mathcal{E}$ and $A_{ij}=1$ if $e_{ij}\in\mathcal{E}$. Let ${\bf X}=\left\{{\bf x}_{i}\right\}_{i=1}^{N}\in\mathbb{R}^{n\times d}$ be the feature matrix for nodes, where ${\bf x}_{i}\in\mathbb{R}^{1\times d}$ denotes the feature vector of node $v_{i}$. Each node is associated with a label. Given a multilayered network and the semantic labels ${\bf y}_{lab}$ for a subset of nodes $\mathcal{V}_{lab}\in\mathcal{V}$, where $y\in{\bf y}_{lab}$ means one of the $c$ predefined classes. GNNs can learn the feature representations of nodes and graphs by using the graph structure and node features. Then the task of node classification is to predict the label for each node without label $v_{i}\in\mathcal{V}|v_{i}\notin\mathcal{V}_{lab}$ according to the feature representations of the corresponding node [29].

Following the work in [3], GCN updates node features by adopting an isotropic averaging operation over the feature representations of one-hop neighbors. Let ${\bf h}_{j}^{\ell}$ be the feature representation of node $v_{j}$ in the $l$-th GCN layer, then a single message passing step in the GCN model takes the following form:

where ${\bf W}^{\ell}$ is a learnable weight matrix for the $l$-th GCN layer, $\mathcal{N}_{i}$ represents the set of one-hop neighbors of node $v_{i}$. Note that ${\rm deg}_{i}$ and ${\rm deg}_{j}$ denote the in-degrees of nodes $v_{i}$ and $v_{j}$, respectively. $\operatorname{ReLU}(\cdot)=\max(0,\cdot)$ is the nonlinear activation function. Along this line, the forward model of a 2-layer GCN [3] can be represented as:

where ${\bf A}\in\mathbb{R}^{n\times n}$ represents the adjacency matrix, and ${\bf X}\in\mathbb{R}^{n\times d}$ is the feature matrix of nodes and is also the input of the first GCN layer. $n$ is the number of nodes, and $d$ is the feature dimension of nodes. $\hat{{\bf A}}=\widetilde{{\bf D}}^{-1/2}\tilde{{\bf A}}\widetilde{{\bf D}}^{-1/2}$ represents the normalized $\tilde{{\bf A}}$, where $\tilde{{\bf A}}={\bf A}+{\bf I}$ represents ${\bf A}$ with self-loop, and ${\bf I}\in\mathbb{R}^{n\times n}$ is an identity matrix. $\tilde{{\bf D}}$ is the degree matrix of $\tilde{{\bf A}}$. Each element $\hat{A}_{i,j}$ is defined as:

The SA mechanism can learn the weight distributions of different features [30]. In other words, the SA mechanism can help the network to recognize features that are important for prediction. A transformer block consists of two sub-layers: an MHSA mechanism is the first sub-layer, and a simple fully connected feed-forward network is the second sub-layer [27]. The MHSA mechanism is calculated as follows:

where ${\bf X}$ is the input. ${\bf Q}_{i}$, ${\bf K}_{i}$, and ${\bf V}_{i}$ respectively correspond to the Query, Key, and Value of the $i$-th head ($i=1,\dots,m$). Moreover, a residual connection [31] and layer normalization [32] follow each sub-layer. Thus, the input of the second sub-layer is as follows:

The second sub-layer is a fully connected feed-forward network. Thus, the output of the transformer block is calculated as follows:

Most existing GNNs are designed for graphs with high homophily, where the connected nodes usually possess similar feature representations and have the same label, for example, citation and community networks [33]. However, there are many graphs with low or medium homophily in the real world, where the connected nodes often have distinct features and possess different labels, such as webpage linking networks [34]. In summary, in practical applications, GNNs designed under the assumption of high homophily are inappropriate for graphs with low or medium homophily.

To alleviate this problem, we build a re-connected adjacency matrix via structure learning to provide each node with reliable neighbor information. Specifically, we use the MHSA mechanism to compute the attention scores between nodes to explore their internal correlation. Considering our primary focus on undirected graphs, generating undirected reconstructed graphs aligns more closely with our practical requirements. Therefore, the MHSA mechanism is modified as follows:

where ${\bf X}\in\mathbb{R}^{n\times d}$ represents the node feature matrix. ${\bf W}_{i}^{Q}\in\mathbb{R}^{d\times p}$ denotes the learnable weighted matrix for the $i$-th head ($i=1,\dots,m$). Eq. 12 calculates the cosine scores between each pair of row vectors in matrix ${\bf Q}_{i}$, resulting in the cosine score matrix, $\text{head}_{i}\in\mathbb{R}^{n\times n}$. In this manner, we can obtain a symmetric attention score matrix ${\bf S}\in\mathbb{R}^{n\times n}$, where the element $S_{ij}$ ranges between $[-1,1]$. The MHSA mechanism can construct multiple fully connected graphs, enabling each node to connect to all the other nodes. This capability allows each node to aggregate features from any other node, but it may result in excessive computational burden and introduce noise. However, the re-connected adjacency matrix is expected to be sparse, connected, and non-negative [26]. To address this issue, we combine the KNN and minimum-threshold methods to select the most reliable neighbors for each node. Specifically, we first define a positive integer $r$ and a non-negative threshold $\epsilon$. Next, we retain attention scores that are either greater than $\epsilon$ or belong to the set of $r$ largest elements in the corresponding row while setting the remaining attention scores to zero. The new adjacency matrix ${\bf A}_{*}\in\mathbb{R}^{n\times n}$ is represented as:

where $\mathcal{R}$ denotes the the set of $r$ largest elements in the $i$-$th$ row of ${\bf S}$. To guarantee the symmetry of ${\bf A}_{*}$, we impose the following constraint on ${\bf A}_{*}$:

In this study, the re-connected graph and node embeddings are optimized simultaneously and benefit each other. In this manner, we can obtain a sparse, nonnegative, connected, and reliable re-connected adjacency matrix ${\bf A}_{*}$. Figure 2 shows the construction process of the re-connected adjacency matrix. In summary, the MHSA mechanism allows nodes to interact with any other node, and appropriate screening mechanisms help the nodes identify the most relevant new neighbors.

Transformer blocks with self-attention mechanisms can help the model recognize important features from the entire graph and pay more attention to these features [27]. Thus, the transformer block is an appropriate method to help the model capture long-range dependencies. However, using a transformer block directly to help GCN perform feature fusion can result in over-fitting. Therefore, we modify the transformer block to make it more applicable to GCN. A modified transformer block is shown in Figure 1. The MHSA mechanism of the modified transformer block is represented as:

where ${\bf W}^{0}\in\mathbb{R}^{d\times q}$, ${\bf W}_{i}^{Q}$, ${\bf W}_{i}^{K}$, and ${\bf W}_{i}^{V}\in\mathbb{R}^{q\times q/m}$ are learnable weighted matrix. ${\bf Q}_{i}$, ${\bf K}_{i}$ and ${\bf V}_{i}$ are the $Q$ (Query), $K$ (Key) and $V$ (Value) matrices derived from the linear transformation of ${\bf H}_{\text{original}}$, respectively. Compared with ${\bf X}_{\text{MHSA}}$ in Eq. 4, ${\bf H}_{\text{MHSA}}$ in Eq. 16 omit a fully connected layer for reducing model complexity and minimizing information loss. Then, We apply a dropout to ${\bf H}_{\text{MHSA}}\in\mathbb{R}^{n\times q}$ and ${\bf H}_{\text{original}}\in\mathbb{R}^{n\times q}$.

In the original transformer block [27], the MHSA mechanism is followed by a residual connection. The residual connection can overcome the problem of gradient disappearance, enabling the development of deeper models. Thus, we also apply the residual connection to ${\bf H}_{\text{MHSA}}$. The output of the modified transformer block, fusional feature vectors, is calculated as follows:

where the purpose of using dropout is to alleviate the over-fitting problem. For convenience, we represent the output of the modified transformer block as follows:

The fusional feature vectors and original feature vectors are concatenated as the ego-embeddings for nodes:

where $\|$ represents the concatenation function. Afterward, we employ the ${\bf A}_{*}$ generated from Subsection 3.1 to perform feature aggregation as follows:

where ${\hat{\bf A}_{*}}={\bf D}_{*}^{-1/2}{\bf A_{*}}{\bf D}_{*}^{-1/2}$ is the normalized ${\bf A_{*}}$, and ${\bf D}_{*}=\operatorname{diag}\left({\bf A}_{*}{\bf 1}_{n}\right)$ is the degree matrix of ${\bf A}_{*}$. We call the results of feature aggregation, ${\bf H}_{A_{*}}$, the reconnected-neighbor-embeddings. Similarly, we utilize the original adjacency matrix ${\bf A}$ to perform feature aggregation as follows:

where $k=1,2,\ldots,K$, $K$ represents the times of the feature aggregation. ${\bf H}^{(0)}_{A}={\bf H}$. $\hat{{\bf A}}={\bf D}^{-1/2}\left({\bf A}+{\bf I}\right){\bf D}^{-1/2}$ represents the normalized ${\bf A}$ with self-loop. Herein, ${\bf D}=\operatorname{diag}\left(\left({\bf A+I}\right){\bf 1}_{n}\right)$ is the degree matrix of ${\bf A}$ with self-loop, and ${\bf I}\in\mathbb{R}^{n\times n}$ is a identity matrix. ${\bf H}^{(K-1)}_{A}$ and ${\bf H}^{(K)}_{A}$ are defined as the neighbor-embeddings of nodes. Subsequently, the ego-embeddings, neighbor-embeddings, and re-connected neighbor-embeddings are concatenated as the general embeddings of nodes. The formula is written as:

Then we apply a dropout to ${\bf H}^{cb}$. For graphs under homophily, ${\bf H}^{(K-1)}_{A}$ and ${\bf H}^{(K)}_{A}$ are sufficient for downstream task. This can be proved by GCN [3] and GAT [2]. In addition, ${\bf H}_{A_{*}}$ can be treated as the supplement to ${\bf H}^{(K-1)}_{A}$ and ${\bf H}^{(K)}_{A}$. For the graphs with low/medium homophily, ${\bf H}$ and ${\bf H}_{A_{*}}$ can also perform well. Moreover, the approach of neighbor-embedding updating allows GCN-SA to capture higher-order neighbor information flexibly.

Afterward, a learnable weight vector ${\bf w}$ is generated, and the dimension of ${\bf w}$ is the same as the output dimensions of ${\bf H}^{cb}$. Then we take the Hadamard product between ${\bf H}^{cb}$ and ${\bf w}$ to highlight the important dimension of ${\bf H}^{cb}$:

Subsequently, nodes are classified in the following way:

where ${\bf W}^{1}$ is a trainable weighted matrix, and the output dimension of ${\bf W}^{1}$ is the same as the number of classes. The modified transformer block performing node embedding fusion can help GCN-SA fuse valuable information from different nodes to improve classification results. Then, we calculate the cross-entropy error over all labeled nodes:

where $\mathcal{Y}_{lab}$ is the set of node indices that have labels.

We employ an MHSA mechanism to capture the internal correlation between nodes and construct a fully connected re-connected adjacency matrix. Afterward, We obtain a connected and sparse re-connected adjacency matrix by masking the unnecessary edges. Subsequently, we obtain a reliable, connected, and sparse re-connected adjacency matrix through joint learning of the re-connected graph and node embeddings. Moreover, we propose a modified transformer block and use it to perform feature vector fusion. Next, we combine the fusional feature vector with the node feature vectors to train the model and reuse the modified transformer block to perform embedding fusion to help GCN-SA select valuable features from different nodes. Our GCN-SA model is trained using diverse information from different views to learn representative node embeddings and accurately perform downstream tasks. These steps can help GCN-SA capture long-range dependencies, allowing it to adapt to graphs with varying levels of homophily. The pseudo-code for the proposed GCN-SA is provided in Algorithm 1.

Eight open graph datasets are adopted to validate the proposed GCN-SA in the simulation, including three citation networks, two Wikipedia networks, and three WebKB networks.

The three standard citation network benchmark datasets include the Cora, Citeseer, and Pubmed datasets [35]. In the three citation networks, nodes correspond to papers, and node features are defined as the bag-of-words representation of the paper. Edges correspond to citations between papers. Each node has a unique label, defined as the corresponding paper’s academic topic.

Wikipedia networks are page-page networks on specific topics in Wikipedia, e.g., Chameleon and Squirrel datasets. In Wikipedia networks, nodes correspond to Wikipedia pages, and node features are represented as informative nouns on Wikipedia pages. Edges correspond to the reciprocal links between Wikipedia pages. Nodes are classified into five categories according to the amount of their average traffic.

The sub-networks of the WebKB networks include the Cornell, Texas, and Wisconsin datasets. These three datasets were collected from the computer science departments [25]. In WebKB networks, nodes correspond to web pages, and the bag-of-words representation of web pages serves as the node features. Edges represent hyperlinks between web pages. These web pages are divided into five classes.

Unless particularly specified, nodes per class are randomly split into $60\%$, $20\%$, and $20\%$ for training, validation, and testing by default across all datasets. Testing is performed when validation losses reach a minimum. A summary of the information for all datasets is presented in Table 2.

The homophily of graph-structured data is a crucial characteristic and plays a significant role in analyzing and utilizing them. As in [21], we also utilize the homophily ratio to measure the homophily level of a graph, $h=\frac{\left|\left\{(u,v):(u,v)\in\mathcal{E}\wedge y_{u}=y_{v}\right\}\right|}{|\mathcal{E}|}$, where $\mathcal{E}$ represents the set of edges, $y_{u}$ and $y_{v}$ represent the labels of node $u$ and $v$, respectively. $h$ is the proportion of edges in a graph that connect nodes with the same label (i.e., intra-class edges). This definition is proposed in [21]. Graphs have strong homophily if $h$ is high ($h\rightarrow 1$) and weak homophily if $h$ is low ($h\rightarrow 0$). Table 2 lists the homophily ratio $h$ for each graph. From the $h$ values of the adopted graphs, we can observe that all citation networks display a high level of homophily, while the WebKB networks and Wikipedia networks exhibit low homophily.

We compare the proposed GCN-SA with several baselines:

$\bullet$ MLP [22] is a simple deep neural network. MLP makes predictions based on the features of nodes without considering any local or non-local information.

$\bullet$ GAT [2] enables specifying different weights to different neighbors by employing the attention mechanism.

$\bullet$ GCN [3] is one of the most common GNNs. The GCN is introduced in Subsection 2.2. GCN makes predictions by aggregating local information.

$\bullet$ MixHop [36] repeatedly aggregates the feature representations of neighbors with various distances to learn robust node embeddings.

$\bullet$ Geom-GCN [25] captures geometric information of graphs to enhance GCN’s ability on representation learning. Three embedding methods, struc2vec, Isomap, and Poincare embedding, are employed in Geom-GCN, corresponding to three variants: Geom-GCN-S, Geom-GCN-I, and Geom-GCN-P. Nevertheless, we only report the best results of three Geom-GCN variants.

$\bullet$ IDGL [26] jointly and iteratively learning the node embeddings and the graph structure. In addition, IDGL dynamically stops when the learned graph is close enough to the optimized graph for the downstream prediction task.

$\bullet$ H₂GCN [21] identifies a set of significant designs, including ego and neighbor embedding separation, higher-order neighborhoods. By colligating these designs, H₂GCN adapts to both heterophily and homophily. We consider two variants: H₂GCN-1 and H₂GCN-2 according to the distance of neighbor nodes for each aggregation.

$\bullet$ CPGNN [37] incorporates an interpretable compatibility matrix for modeling the homophily level in the graph, which enables it to go beyond the assumption of strong homophily. CPGNN contains four variants: CPGNN-MLP-1, CPGNN-MLP-2, CPGNN-Cheby-1 and CPGNN-Cheby-2. According to the analysis in [37], CPGNN-Cheby-1 performs the best overall. Therefore, we consider the CPGNN-Cheby-1.

For comparison, we use eight state-of-the-art node classification algorithms, including MLP, GAT, GCN, MixHop, GEOM-GCN, IDGL, H₂GCN and CPGNN. In the above eight network models, all hyper-parameters are set according to [21], IDGL to [26], and CPGNN to [37]. Our GCN-SA includes many hyper-parameters, some of which are fixed, while others need to be searched on the validation set. The random seed is set as $42$ for all experiments. The number of attention heads $m$ is $4$ in the re-connected graph learning, and $m$ is $1$ in feature vector and embedding fusion. The numbers of hidden features $p$ are set as $16$. The descriptions of the hyperparameters need to be searched, and the corresponding ranges of values tried are provided in Table 8. Table 9 summarizes the values of all hyper-parameters and the corresponding classification accuracies on different datasets.

Among all the hyper-parameters, $K$, $r$, and $\epsilon$ play a particularly crucial role in our GCN-SA. $K$ determines the number of times feature aggregation is performed on the original graph structure, while $r$ and $\epsilon$ dictate the sparsity and connectivity of the reconnected graph. Therefore, we investigate the impact of these three hyper-parameters on the classification accuracies of our GCN-SA on seven datasets. Figure 3 shows the classification accuracies versus the $K$, $r$, and $\epsilon$ on different datasets. Since the behavior of GCN-SA in the Texas and Wisconsin datasets is similar, we omit the Wisconsin dataset for brevity. Referring to Figure 3 (b), it can be observed that as $K$ increases, GCN-SA behaves differently across various graphs. This phenomenon is mainly because different datasets have different levels of homophily. As for Figure 3 (c) and (d), the classification accuracies of our GCN-SA remain relatively stable with increasing values of $r$ and $\epsilon$. This consistency indicates that our graph-structure-learning method is effective and robust. The optimal values of $K$, $r$, and $\epsilon$ for different datasets are recorded in the Table 9.

ReLU is utilized as the nonlinear activation function. The training nodes are utilized for training our GCN-SA by minimizing cross-entropy loss. Adam optimizer [38] is employed in our GCN-SA. The proposed GCN-SA is implemented with the deep learning library PyTorch. The Python and PyTorch versions are 3.8.10 and 1.9.0, respectively. All experiments are conducted on a Linux server with a GPU (NVIDIA GeForce RTX 2080 Ti). The experimental results are the mean and standard deviation of ten runs for all the experiments.

In this section, we investigate the impact of our GCN-SA on the reliability of re-connected graph structures. We employ the homophily ratios, denoted as $h$, to evaluate the reliability of the reconnected graph structures. Higher values of $h$ correspond to greater reliability, while lower values indicate less reliability. Figure 4 displays the $h$ values for the original, initialized, and two reconnected graphs across eight datasets. The initialized graph is constructed by GCN-SA without optimization. In contrast, the two reconnected graphs are learned and optimized by NLGNN and GCN-SA methods, respectively. As seen from Figure 4, the $h$ values of the re-connected graphs are significantly higher than those of the original and initialized graphs for all datasets, particularly in the case of Wikipedia and WebKB networks. This is mainly because the re-connected graphs can be optimized toward the downstream prediction task in both NLGNN and GCN-SA methods. Additionally, we observe that the $h$ values of the re-connected graphs learned by our GCN-SA are always higher than those of the NLGNN. This difference is due to the limited power of the inner product-based similarity metric function employed by NLGNN in representing the intrinsic correlation between nodes. In comparison, our GCN-SA is more effective at capturing the internal correlation of nodes.

We employ the Gephi tool to visualize the original graph and the re-connected graph optimized by our GCN-SA, using the Wisconsin network as an example. Figure 5 presents the visualization of these two graphs, allowing for an intuitive examination of the structural changes brought about by our GCN-SA. We then select a specific node and highlight its neighborhood in both the original graph (Figure 5(b)) and the re-connected graph (Figure 5(d)). As depicted in Figure 5, the original graph appears chaotic, with numerous inter-class connections. However, after applying our GCN-SA, the structure of the reconnected graph becomes considerably more organized, with the fraction $h$ of intra-class edges reaching 90%. This improvement in accuracy performance demonstrates that our graph-structure-learning module can substantially enhance the graph structure.

Afterward, we investigate the impact of the ${\bf A}_{*}$ on the accuracy of our GCN-SA using an ablation study. Table 3 presents the accuracies of our GCN-SA across all adopted graphs. It can be observed that $\bf{A}$ significantly enhances the classification accuracies of our GCN-SA in citation networks and Wikipedia networks. This improvement is due to the $\bf{A}$, which can provide valuable neighbors for aggregation. Additionally, $\bf{A}_{*}$ also promotes the performance of our GCN-SA, particularly in WebKB networks. This is owing to $\bf{A}_{*}$ being more reliable than $\bf{A}$ in WebKB networks. Our GCN-SA, when combined with both $\bf{A}$ and $\bf{A}{*}$, performs well in all networks. Based on this observation, ${\bf A}_{*}$ can be treated as a qualified adjacency matrix for providing each node with reliable neighbors, thereby enhancing the ability of GCN-SA to capture long-range dependencies.

In this section, we examine the impact of the modified transformer block on the accuracies of GCN-SA. The modified transformer block operates at two different points within GCN-SA: feature vector fusion (Fusion_1) and node embedding fusion (Fusion_2). We employ an ablation study to assess the effects of Fusion_1 and Fusion_2 on the node classification accuracy of GCN-SA. Table 4 displays the classification accuracies of GCN-SA across all datasets. As observed, Fusion_1 enhances the performance of GCN-SA. For example, when Fusion_1 is applied to GCN-SA in the Chameleon dataset, the performance improves by 1.2%. Similarly, Fusion_2 also contributes to the improvement of GCN-SA’s accuracies. In the Texas dataset, GCN-SA achieves a 2.5% performance enhancement when Fusion_2 is incorporated. Ultimately, GCN-SA with both Fusion_1 and Fusion_2 achieves the best performance across all networks. Notably, in the Squirrel dataset, GCN-SA sees a 3.6% accuracy improvement when both Fusion_1 and Fusion_2 are applied. The experimental results demonstrate that both Fusion_1 and Fusion_2 can bolster GCN-SA’s ability to learn node embeddings effectively.

For further insight, we compare the impacts of the original transformer block and modified transformer block on the accuracies of GCN-SA. For this purpose, we introduce two variants of GCN-SA. The first variant, GCN-SA-W/O, that without feature vector and embedding fusion. The second variant, GCN-SA-TF, employs the original transformer block to perform feature vector and node embedding fusion. Table 5 displays the classification accuracies of GCN-SA-W/O, GCN-SA-TF, and GCN-SA across all datasets. As observed, GCN-SA-TF performs the worst, even underperforming GCN-SA-W/O. This might be due to the original transformer block making GCN suffer from over-fitting. In contrast, GCN-SA achieves the best classification performance, demonstrating that the modified transformer block is more effective in enhancing GCN compared to the original transformer block.

In this paper, $n$ denotes the number of nodes, while $d$ and $q$ represent the number of original and hidden features of nodes, respectively. $c$ is the class number of node labels. Given these definitions, the computational complexity of a 2-layer GCN, as shown in 2, is $\mathcal{O}(nq(d+c))$. Compared with the 2-layer GCN, our GCN-SA contains three additional SA mechanisms and one Hadamard product. The computational complexities of the first and the second SA mechanisms are the same and equal to $\mathcal{O}(n^{2}q)$. The computational complexity of the third SA mechanism is equal to $\mathcal{O}(n^{2}c)$. The Hadamard product’s computational complexity is $\mathcal{O}(8nq)$. In summary, the computational complexity of our GCN-SA is $\mathcal{O}(nq(d+c+8)+2n^{2}q+n^{2}c)$.

In addition, we compare the real running time (500 epochs) of GCN, GAT, Geom-GCN, IDGL, CPGNN, and GCN-SA with the hyper-parameters described in Section 4.3. The Cornell, Texas, and Wisconsin networks possess a similar number of nodes, edges, and node feature dimensions. Thus, we choose only one dataset, Texas, from the three for the sake of clarity and conciseness. Figure 6 exhibits the running time of classification approaches on Texas, Citeseer, Cora, Pubmed, Chameleon, and Squirrel networks. As observed, GCN is the fastest. Due to the time-consuming iterative graph structure learning module, IDGL is the slowest. GAT and GCN-SA are at comparable levels.

This experiment estimates the classification performance of the proposed GCN-SA and other outstanding approaches in the literature. In Table 6, the nodes of each class are randomly split into 48%, 32%, and 20% for training, validation, and testing. In Table 7, the proportions are 60%, 20%, and 20%. As seen from the Tables 6, some GNNs perform even worse than MLP on WebKB networks (low homophily), notably GAT, GCN, MixHop, and Geom-GCN, which have an accuracy of 58.9%, 57.0%, 73.5%, and 60.8% in Cornell, respectively. The proposed GCN-SA performs best and achieves 88.4% in Cornell. Meanwhile, on graphs with high homophily, our GCN-SA still has advantages. Compared with the H₂GCN, IDGL, and CPGNN, GCN-SA has 1.6%, 0.7%, and 2.4% higher accuracies on the Cora dataset. As can be seen, the proposed GCN-SA possesses the best classification performance. In addition, similar observations can be made in Table 7.

Here are our work’s main Strengths:

• $\bullet$ Our GCN-SA is a stable and effective node embedding method that can be used for heterophilic and homophilic graphs.

• $\bullet$ The developed modified transformer block incorporates GCN, allowing GCN to fuse valuable features from the entire graph.

• $\bullet$ The proposed graph-structure-learning strategy is flexible, and others can incorporate it into any GNN model to learn new and reliable graph structures.

• $\bullet$ Our GCN-SA demonstrates superior accuracy in graphs under various levels of homophily. Others can employ GCN-SA to learn node embeddings for graphs with various homophily levels.

Here are our work’s main limitations:

• $\bullet$ The advantages of our GCN-SA in homophilic graphs are not particularly significant.

• $\bullet$ The number of new neighbors may be unbalanced when the minimum threshold method is used to screen new neighbors.

• $\bullet$ Introducing multiple transformer blocks increases the computational complexity of the model.

We propose the following directions for future work:

• $\bullet$ Enhancing the competitiveness of GCN-SA, particularly for graphs with high-level homophily.

• $\bullet$ Improving the graph-structure-learning method to supply reliable and balanced new neighbors for each node.

• $\bullet$ Reducing the computational complexity of GCN-SA and addressing its scalability.

• $\bullet$ Extending GCN-SA to more challenging scenarios, such as large-scale, dynamic, or knowledge graphs.