Gradformer: Graph Transformer with Exponential Decay
Chuang Liu Zelin Yao Yibing Zhan Xueqi Ma Shirui Pan Wenbin Hu



A Reconfigurable Subarray Architecture and Hybrid Beamforming for 
Millimeter-Wave Dual-Function-Radar-Communication Systems

    
 Xin Jin, Tiejun Lv, Senior Member, IEEE, Wei Ni, Fellow, IEEE, Zhipeng Lin, Member, IEEE, Qiuming Zhu, Senior Member, IEEE, Ekram Hossain, Fellow, IEEE, and H. Vincent Poor, Life Fellow, IEEE

Manuscript received March 6, 2024; accepted April 22, 2024. This paper was supported in part by the National Natural Science Foundation of China under No. 62271068, the Beijing Natural Science Foundation under Grant No. L222046, the U.S National Science Foundation under Grants CNS-2128448 and ECCS-2335876. (corresponding author: Tiejun Lv.)

X. Jin and T. Lv are with the School of Communication and Information Engineering, Beijing University of Posts and Telecommunications, Beijing 100876, China (e-mail: {jxzoe, lvtiejun}@bupt.edu.cn).

W. Ni is with the Data61, Commonwealth Scientific and Industrial Research Organization, Sydney, Marsfield, NSW 2122, Australia.
(e-mail: wei.ni@ieee.org).

Z. Lin and Q. Zhu are with the College of Electronic and Information Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China (e-mail: {linlzp, zhuqiuming}@nuaa.edu.cn).

E. Hossain is with the Department of Electrical and Computer Engineering, University of Manitoba, Canada (e-mail: ekram.hossain@umanitoba.ca).

H. V. Poor is with the Department of Electrical and Computer Engineering, Princeton University, Princeton, NJ 08544 USA (e-mail: poor@princeton.edu).   


    —
=====================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================================




Graph Transformers (GTs) have demonstrated their advantages across a wide range of tasks. However, the self-attention mechanism in GTs overlooks the graph's inductive biases, particularly biases related to structure, which are crucial for the graph tasks. Although some methods utilize positional encoding and attention bias to model inductive biases, their effectiveness is still suboptimal analytically. Therefore, this paper presents Gradformer, a method innovatively integrating GT with the intrinsic inductive bias by applying an exponential decay mask to the attention matrix. Specifically, the values in the decay mask matrix diminish exponentially, correlating with the decreasing node proximities within the graph structure. This design enables Gradformer to retain its ability to capture information from distant nodes while focusing on the graph's local details. Furthermore, Gradformer introduces a learnable constraint into the decay mask, allowing different attention heads to learn distinct decay masks. Such an design diversifies the attention heads, enabling a more effective assimilation of diverse structural information within the graph. Extensive experiments on various benchmarks demonstrate that Gradformer consistently outperforms the Graph Neural Network and GT baseline models in various graph classification and regression tasks. Additionally, Gradformer has proven to be an effective method for training deep GT models, maintaining or even enhancing accuracy compared to shallow models as the network deepens, in contrast to the significant accuracy drop observed in other GT models.Codes are available at <https://github.com/LiuChuang0059/Gradformer>.












 









§ INTRODUCTION















Graph Transformers (GTs) <cit.> have shown remarkable success in achieving state-of-the-art performance across various applications. Unlike the local message-passing in graph neural networks (GNNs), GTs can capture long-range information from distant nodes. Specifically, the self-attention mechanism in GTs allows each node to directly attend to other nodes in a graph, enabling information aggregation from arbitrary nodes. 

The self-attention in GTs offers considerable flexibility and the capacity to aggregate information both globally and adaptively. However, this mechanism significantly neglects intrinsic inductive biases in graphs, which poses challenges in capturing the essential graph structural information. Without considering structural relationships, the indiscriminate attention to all nodes in a graph will render the self-attention mechanism's inadequate focus on key information and the aggregation of redundant information. This comes with the generation of meaningless attention scores and, ultimately, suboptimal learning outcomes. Furthermore, the above issue is particularly evident in scenarios with limited data.







Numerous studies have focused on integrating graph inductive biases into self-attention learning mechanisms. These studies are broadly divided into two main approaches: 1) Injected position encoding: Studies such as GT <cit.> and SAN <cit.> suggest using laplacian eigenfunctions as positional encodings (PEs) to contain the structural characteristics of graphs. 2) Attention bias:  Graphormer <cit.> proposes a direct addition of structural encodings into the attention mechanism as a bias, enhancing the GT's capacity to model graph-structured data. 
Notably, applying PEs, which are typically concatenated with input features, would affect attention scores and could be considered as a way to introduce attention bias, as illustrated in Figure <ref>. However, concatenated PEs and attention bias fail to directly and effectively guide attention scores to fully capture structural information in graphs. From the Figure <ref>, it is evident that the attention patterns in GTs augmented with PE or attention bias exhibit minimal deviation from those observed in the vanilla GTs. This observation suggests that the inductive biases introduced by these methods have a limited effect on the model's attention mechanism. Furthermore, the attention in these models appears to be inattentive (characterized by dense patterns), potentially leading to a failure in focusing on key information and aggregating redundant information. These findings highlight a critical need for more sophisticated approaches capable of effectively incorporating structural insights into the self-attention framework of GTs. Therefore, the goal is to develop a method that not only enhances the model's attention mechanism by focusing on structurally significant features but also reduces redundancy in the information aggregation process. 


Different from the aforementioned methods, we propose Gradformer, a novel method that innovatively integrates GTs with inductive bias. Specifically, Gradformer integrates an exponential decay mask into the GT self-attention architecture. This mask, multiplied with the attention score, explicitly controls each node's attention weights relative to other nodes, ensuring that the attention weights decay with an increasing node distance. In addition, the exponential decay ensures a gradual reduction in attention weights at the boundary of the full attention zone, avoiding an abrupt truncation. As a result, the introduced decay mask, rooted in the graph's structural bias, effectively guides the learning process within the self-attention framework. Furthermore, Gradformer incorporates a learnable constraint within the decay mask, applied to the attention heads, dynamically adjusting the node distance for full attention in a graph. This constraint amplifies the model's ability to discern local structural nuances and diversifies the attention heads, facilitating more effective assimilation of diverse structural information.

The design elements of Gradformer offer multiple benefits: 1) The decay mask effectively integrates a form of prior knowledge, deeply connected to the graph's structural attributes, into the GT models. 2) The structure-oriented prior knowledge precisely governs each node's interaction radius and hence defines the extent of its attention relative to other nodes, thus preventing the aggregation of redundant information. This is achieved by the design of exponential decay, which enables mask values for distant nodes approaching near-zero levels, thus effectively reducing their influence in the aggregation process. 3) The exponential decay mask endows the enhanced attention mechanism in Gradformer with the ability to function as a unified form of GNNs and GTs, synergizing their strengths: the local processing power of GNNs and global aggregation capabilities of GTs (further expounded in Section <ref>).  In summary, Gradformer empowers the self-attention mechanism to effectively concentrate on structural information within the graph and limit unnecessary aggregation from distant nodes.

To evaluate the effectiveness of our Gradformer, we conduct extensive experiments on various commonly-used datasets, including the large-scale Open Graph Benchmark (OGB) <cit.>. The experimental results consistently demonstrate that Gradformer outperforms state-of-the-art GT models on most datasets with remarkable stability and accuracy improvements, even as network depth increases. This finding stands in stark contrast to the performance of other GT models, where accuracy tends to decline with increased depth <cit.>.  Additionally, incorporating the decay mask design into Gradformer provides notable advantages for the graph classification task  in low-resource settings, underscoring the versatility and practicality of our model. Our main contributions are summarized as follows:


  
  * We propose a general GT with an exponential decay mask attention mechanism, termed Gradformer, which enhances the self-attention mechanism by fully leveraging the graph's structural information. Therefore, Gradformer maintains the ability to capture long-range information while prioritizing the local information of the graph, guided by an intense inductive bias.
  

  
  * We conduct extensive experiments to compare Gradformer with 14 GNN and GT baseline models for the graph classification task on various real-world graph datasets, including OGB. The experimental results consistently validate the effectiveness of the proposed Gradformer.






















§ RELATED WORK





  
Graph Transformers. 
In recent years, many transformer variants have been applied to graph modeling. Unlike GNNs, transformers display competitive or even superior performance across various tasks. Dwivedi et al. graph-transformer were the first to extend the transformer architecture to graphs and propose PEs <cit.>. Subsequently, numerous variants of GT have been proposed, making significant progress in graph-level tasks <cit.>. However, these methods are primarily designed for graph-level tasks due to the time and memory constraints of the self-attention layer, which requires 𝒪(n^2) complexity. Therefore, multiple studies <cit.> have been conducted to enhance GTs' scalability and efficiency, facilitating their application in node-level tasks. Additionally, GTs have been applied in various fields, including natural language processing <cit.>, computer vision <cit.>, recommendation systems <cit.>, multimodal contexts <cit.>, and reinforcement learning <cit.>. For a more detailed introduction, please refer to the recent GT reviews <cit.>. 





  
Prior Knowledge in Graph Transformer.

Numerous efforts have been undertaken to integrate prior knowledge into GTs to augment their performance. This integration can be classified into three categories. 1) Proposed position encodings: SAN <cit.> suggests utilizing learned Laplace eigenfunctions as a substitute for the original PE.  GraphGPS <cit.> summarizes possible positional and structural encodings for GTs. 2) Improved self-attention: Graphormer <cit.> suggests adding structural encodings to the attention metric as a bias to enhance GTs' structured-data modeling. Moreover, RT <cit.> and EGT <cit.> consider incorporating the edge vectors in their self-attention calculations. 3) Modified architecture: GraphTrans <cit.> introduces a transformer sub-network above a GNN layer. In GraphGPS, the transformer and GNN layers are placed in parallel. In this manuscript, our proposed method lies on the line of improving the self-attention learning.









§ METHODOLOGY





 §.§ Preliminaries




  
Notations.  A graph 𝒢 can be represented by an adjacency matrix 𝐀∈{0, 1}^ n × n and a node feature matrix 𝐗∈ℝ^ n × d, where n is the number of nodes, d is the node feature dimension, and  𝐀[i, j]=1 if an edge between nodes v_i and v_j exists, otherwise, 𝐀[i, j]=0. 




  
Graph Transformer. GTs <cit.> consist of two essential parts: a multi-head self-attention (MHA) module and a feed-forward network (FFN). Given the node embedding matrix  𝐇^(l)∈ℝ^ n × d^(l) in a graph, a single attention head is computed as follows: 

    𝐇^(l+1)=softmax(𝐐^(l) (𝐊^(l))^⊤/√(d^(l))) 𝐕^(l),

where 𝐇^(l+1)∈ℝ^n × d^(l+1) is the output matrix,  d^(l+1) is the output hidden dimension, and 𝐐^(l)∈ℝ^n × d^(l), 𝐊^(l)∈ℝ^n × d^(l), and 𝐕^(l)∈ℝ^n × d^(l) are the query, key, and value vectors, respectively, which are the projection results of 𝐇^(l)∈ℝ^ n × d^(l):

    𝐐^(l)=𝐇^(l)𝐖^Q; 𝐊^(l)=𝐇^(l)𝐖^K; 𝐕^(l)=𝐇^(l)𝐖^V ,

where 𝐖^Q ∈ℝ^d^(l)× d^(l+1), 𝐖^K ∈ℝ^d^(l)× d^(l+1), and 𝐖^V ∈ℝ^d^(l)× d^(l+1) are projection matrices. Note that the above single-head self-attention module can be generalized into a MHA via the concatenation operation. 














 §.§ Proposed Method: Gradformer




This subsection introduces the Gradformer method. First, we describe the fundamental Gradformer architecture with a primary focus on its central module, the exponential decay mask attention mechanism. The mechanism comprises two components: exponential decay and learnable constraints. Subsequently, we explore the Gradformer method in detail, with a focus on its general form and computational complexity.





  §.§.§ Architecture


As depicted in Figure <ref>, Gradformer extends the original GT architecture by incorporating a decay mask. The decay mask, derived from the graph's structural information, introduces a strong inductive bias into the self-attention learning.




  
Masking Attention with Exponential Decay. 
According to Eq. (<ref>), we observe that the attention matrix is comparable to a row-normalized adjacency matrix of a directly weighted complete graph. This dictates the aggregation of node features in a graph, similar to GCN. Unlike the input graph, this dynamically forms graph representations through the attention mechanism. However, the basic transformer does not directly consider the input structure (i.e., existing edges) when forming these weighted graphs (i.e., the attention matrices). Consequently, the attention mechanism may overlook the importance of certain neighbouring nodes due to feature similarity, and hence these dynamic graphs collapse immediately after aggregation. To address this issue, we introduce a decay mask 𝐌, related to the graph's structural information, to participate in the aggregation process as follows: 

    𝐌 =λ^ψ(v_i, v_j)∈ℝ^n × n,

where λ is a scalar and ψ(v_i, v_j) refers to a function that measures the spatial distance between v_i and v_j  in a graph. The function ψ(·) can be defined by the connectivity between the nodes in the graph. In this paper, we choose ψ(v_i, v_j) to present the distance of the shortest path (SPH) between v_i and v_j if the two nodes are connected. If not, we set the output of ψ(·) to a special value (i.e., -1). Based on the study <cit.>, our approach configures the attention mask 𝐌 to decrease monotonically and exponentially, as depicted in the left part of Figure <ref>. Compared to methods with linear decay, exponential decay eliminates the need for an additional endpoint and effectively filters attention at extended distances, with values for distant nodes diminishing to nearly zero. After obtaining the attention mask, it is multiplied with the attention score 𝐒∈ℝ^n × n, as illustrated in Figure <ref>, and formally defined as:

    𝐒̃^(l)=softmax(𝐒^(l)⊙𝐌^(l)), 
    Attn(𝐐^(l), 𝐊^(l), 𝐕^(l))  =𝐒̃^(l)𝐕^(l),

where 𝐒̃^(l) denotes the refined attention at layer l, and Attn denotes the self-attention operation with decay mask.












  
Mask Decay with Learnable Constraints.  To enhance the attention mechanism's ability to model local structural information, given the strong locality inherent in graphs, a refined version of Eq. (<ref>) is provided. This version incorporates a distance constraint into the decay operation, effectively tailoring the attention mechanism to be more sensitive to the local information. The refined decay mask is as follows:

    𝐌 =λ^Relu(ψ(v_i, v_j) - sp),

where sp is a scalar that defines the starting point of the decay. Specifically, if the spatial distance in ψ(v_i, v_j) is less than sp, the attention score between v_i and v_j remains unaffected by the decay. Hence, this design accurately controls each node's interaction radius, delineating the extent of its attention relative to other nodes and preventing the aggregation of redundant information.

Furthermore, to enable various attention heads to capture diverse structural information, we make the constraints sp learnable. Consequently, when the decay mechanism is extended to multi-head attention, a decay mask bearing different constraints is applied to each head, as shown below:

    𝐒̃^(l)=[𝐒^(l,1)⊙𝐌^(l,1) ; 𝐒̂^(l,2)⊙𝐌^(l,2); ⋯𝐒̂^(l,h)⊙𝐌^(l,h)],

where h represents the total number of attention heads. As illustrated in the right part of Figure <ref>, the constraints of different attention heads are learned to capture various structural information. Specifically, we observe that the learned constraint for Head 3 is relatively large. This characteristic enables Head 3 to focus on global information of the graph. Conversely, Head 1 exhibits a different learning pattern, which allows model to capture proximate information. 




























 §.§ Discussion
 




  
Gradformer is a General Form of GNNs and GTs. In essence, Gradformer represents a more generalized form of the GNN <cit.> and GT <cit.> models. This generalization becomes evident when considering the behavior of the decay mask 𝐌 under varying settings of the parameter λ. Specifically, when λ = 1, the decay mask in Eq. (<ref>) essentially transforms into an all-ones matrix. In this configuration, Gradformer effectively mirrors the GT model, as the decay mask exerts no modifying influence on the attention scores. Additionally, when λ = 0 , the decay mask 𝐌_0 retains the mask value of the 1-hop neighbors as one and sets all others to zero. This configuration parallels the adjacency matrix 𝐀, thereby aligning Gradformer closely with the GNN models. The formal derivation of the above process is as follows:

    𝐇^(l+1)=1/√(d^(l))(𝐒^(l)⊙𝐌_0^(l)) 𝐇^(l)𝐖 ;   𝐌_0^(l) = 𝐀 .

Taking the GCN layer as an example, the message passing mechanism is expressed as follows:

    𝐇^(l+1)  =σ(𝐀𝐇^(l)𝐖),

where σ denotes the Sigmoid activation function. From these equations, we can deduce that Gradformer essentially constitutes a generalized GNN form, possessing at least the same expressive capability as traditional GNNs.

In summary, Gradformer surpasses traditional GNNs by broadening its receptive field to encompass more relevant nodes. Furthermore, compared to GTs, Gradformer demonstrates superior capacity in fusing node representations with graph structure, capturing more topological information.









  
Computational Complexity. This subsection analyzes Gradformer's complexity. Compared to vanilla GTs, Gradformer incurs only the additional computational cost of point-wise multiplication between the decay and attention matrices. This process has significantly less computational complexity than self-attention. Additionally, Gradformer's additional memory requirement is the mask matrix, which shares the same size as the self-attention one. To illustrate Gradformer's complexity, detailed experimental results for time and memory are provided in the following section (See Figure <ref>).























§ EXPERIMENTS








 §.§ Experimental Settings




  
Datasets. We utilize nine commonly-used real-world datasets from various sources to ensure diversity, including five graph datasets from the TU database <cit.> (i.e., NCI1, PROTEINS, MUTAG, IMDB-B, and COLLAB), three datasets from Benchmarking GNN <cit.> (i.e., PATTERN, CLUSTER, and ZINC), and one dataset from OGB <cit.> (i.e., OGBG-MOLHIV), involving diverse domains (e.g., synthetic, social, biology, and chemistry), sizes (e.g., ZINC and OGBG-MOLHIV are large datasets), and tasks (e.g., node classification, graph classification and regression). For all datasets, we strictly follow the evaluation metrics and dataset split recommended by the given benchmarks <cit.>. 





  
Baseline. To demonstrate the effectiveness of our proposed method, we compare Gradformer with the following 14 baselines: (1) 4 standard GCN-based models: GCN gcn, GAT gat, GIN gin, and  GatedGCN gatedgcn; (2)  10 GT-based graph models: GraphTransformer graph-transformer, SAN san, Graphormer graphormer-v1, GraphTrans graphtrans, SAT sat,  EGT egt, GraphGPS graphgps, LGI-GT lgi-gt, KDLGT kdlgt, and DeepGraph deepgraph. For each baseline, we utilize the recommended settings as per the official implementation guidelines. 






  
Implementation Details. We assess our proposed model's effectiveness by measuring its performance in graph classification and regression tasks. To ensure reliability, we conduct 10 trials for each model using different random seeds. Accordingly, we report the average test accuracy/AUROC/MAE based on the epoch when the best validation accuracy/AUROC/MAE is achieved.  Furthermore, all the experiments are conducted on a server equipped with 8 NVIDIA A100s. 













  


 §.§ Overall Performance

We evaluate the proposed model's effectiveness by comparing it with GT models that are both shallow and deep. For each model and dataset, we conduct 10 trials with random seeds, and then measure the mean accuracy and standard deviation, which are reported in Tables <ref> and <ref>.




  
Performance of Gradformer. From the results in Table <ref>, we observe that: 
1) Gradformer demonstrates exceptional performance, achieving state-of-the-art results on five datasets while remaining competitive on three others. This highlights the efficacy of the proposed method.
2) Notably, on small-scale datasets such as NCI1 and PROTEINS, Gradformer outperforms all 14 methods, exhibiting improvements of 2.13% and 2.28%, respectively. This demonstrates Gradformer's effective integration of inductive biases into the GT model, a crucial advantage especially in scenarios with limited data availability. To further validate this observation, additional experiments under low-resource conditions for the large-scale datasets have been conducted (see next section).
3) Furthermore, Gradformer delivers competitive results on large-scale datasets (e.g., ZINC), demonstrating its potential applicability across various dataset scales.















  pinkbox/.style=
    colback=lightpink,
    colframe=lightpink,
    width = 1.0cm,
    height = 0.35cm,
    halign=center, 
    valign=center, 
  


  bluebox/.style=
    colback=iceblue,
    colframe=iceblue,
    width = 1.0cm,
    height = 0.35cm,
    halign=center, 
    valign=center, 
  






  
Performance of Gradformer with Deep Layers. Table <ref> displays the results of Gradformer with deep layers. Based on these results, the following observations can be made. 1) Increasing the number of layers notably decreases the accuracy of deep GTs, such as GraphGPS (e.g., a drop of 14.4% on NCI1 and 9.54% on CLUSTER). 2) In contrast, Gradformer demonstrates a significant improvement in this context.  It sustains performance on the NCI1 dataset and surpasses shallow models on CLUSTER and PATTERN datasets. This improvement can be attributed to Gradformer's inherent flexibility in accommodating increased model depth. Specifically, while self-attention in shallow networks is inclined to focus locally, it adopts a more global perspective in deeper networks. Therefore, incorporating residual connections enhances information flow between layers, stabilizing the learning process. The decay mask utilized by Gradformer plays a pivotal role in ensuring that the updated node information maintains higher fidelity to the original data, producing effects similar to those observed in shallower models. 




 §.§ Further Discussions





  
Results on Low-resource Settings.
We conduct experiments using datasets with a reduced number of labels on NCI1 and ZINC datasets. The results in Table <ref> indicate that Gradformer consistently outperforms GraphGPS across all settings, particularly when the number of labels is very low, with improvements of 2.4% and 2.3% for 5% and 10% labeled data, respectively. This finding indicates that our method effectively incorporates the inductive biases into the GTs, enabling them to efficiently assimilate graph information with a limited number of labeled datasets. Furthermore, this discovery highlights the potential applicability of our model under resource-constrained conditions, such as the biomedical field where labeled data are scarce and costly.

 







  
Performance without MPNN or Position Encoding. In our subsequent analysis, we examine the impact of two key GT components: the Message Passing Neural Network (MPNN) module and PE. This investigation involves four graph datasets. It is important to note that except for the specific components under study, all other aspects of the models are maintained in line with the complete models. The findings, summarized in Table <ref>, indicate that: 1) The removal of the MPNN module leads to a slight decline in Gradformer's performance, especially in contrast to GraphGPS. For instance, the performance of GraphGPS without MPNN diminishes by 15.67 on the PATTERN dataset, whereas Gradformer only experiences a reduction of 0.07. 2) The absence of PE seems to have a minimal, and in some cases even beneficial, impact on Gradformer. The model demonstrates improved performance on certain datasets (i.e., PATTERN) when PE is omitted. This finding suggests that Gradformer's architecture, particularly its decay mask design, can  compensate for the absence of positional information. In summary, these results imply that our method effectively enables self-attention mechanisms to capture more structural information.





  
The Impact of Graph Structure Index. As detailed in Section <ref>, our model's decay mask is formulated based on specific graph structural indices. In addition to the previously mentioned SPH, our study also examines another structural index: the discrete Ricci curvature (Curve) <cit.>. This index is the graph distance based on Riemannian manifold. Furthermore, we evaluate the effectiveness of a feature-based index, specifically the feature cosine similarity (FS). The results, illustrated in Figure <ref>, show that SPH consistently outperforms the other two indexes. Notably, the accuracy achieved with FS is significantly lower than that obtained with the structural indices (i.e., SPH and Curve). These findings further emphasize the importance of incorporating structural information in enhancing model performance.





  
The Impact of Decay Ratio and Decay Function. In an analysis conducted on three datasets, NCI1, PROTEINS, and COLLAB, the impact of varying the parameter λ is examined. The results are depicted in Figure <ref>. These findings reveal that as λ increases, the model's accuracy initially rises, reaching optimal performance typically around the values of 0.5 or 0.6. Subsequently, the model's accuracy declines. Furthermore, as elaborated in Section <ref>, specific λ  values confer distinct characteristics to Gradformer. For instance, at λ = 1, Gradformer aligns with the conventional GT model, whereas at λ = 0,  it nearly regresses to a GNN model. Notably, across varying decay ratios, Gradformer consistently exhibits superior performance over the standard GNN model. In addition, observations indicate that the exponential decay function consistently outperforms the linear one.











  
Efficiency Analysis. 
To validate Gradformer's efficiency, its training cost is compared with prominent methods such as SAN <cit.>, Graphormer <cit.>, and GraphGPS <cit.>, with a focus on metrics such as running time and GPU memory usage. The comparative results are presented in Figure <ref>. These findings reveal that Gradformer achieves an optimal balance between efficiency and effectiveness. Notably, Gradformer outperforms SAN and GraphGPS in computational efficiency and accuracy. Although Gradformer exhibits a marginally longer runtime compared to Graphormer, the former significantly surpasses the latter in accuracy, highlighting its superiority in balancing resource usage with high-performance outcomes.












§ CONCLUSION

In this study, we introduce Gradformer, a novel integration of GT with intrinsic inductive biases, achieved by applying an exponential decay mask with learnable parameters to the attention matrix. Through extensive experimentation across 9 graph datasets, Gradformer has shown its superiority by outperforming 14 contemporary GTs and GNNs. Notably, Gradformer's strength lies in its ability to maintain or even surpass shallow models in accuracy while deepening the network architecture. This is a feat not commonly observed in other GTs where accuracy tends to decline significantly in the same context. Despite its competitive performance, Gradformer still has areas for further improvement, including 1) exploring the feasibility of achieving state-of-the-art structure without the use of MPNN, and 2) investigating the potential for the decay mask operation to significantly improve GT efficiency.





§ ACKNOWLEDGMENTS

The work of Wenbin Hu was supported by the National Key Research and Development Program of China (2023YFC2705700). This work was supported in part by the Natural Science Foundation of China (No. 82174230), Artificial Intelligence Innovation Project of Wuhan Science and Technology Bureau (No. 2022010702040070), Natural Science Foundation of Shenzhen City (No. JCYJ20230807090211021).



named_short







§ EXPERIMENTAL SETTINGS



We evaluate the effectiveness of the proposed model in terms of mean accuracy, mean absolute error and AUROC, conducting 10 trials with random seeds for each model. For each baseline, we refer to the recommended settings in the official implementations and implement Gradformer with Python (3.11.0), Pytorch (2.1.0), and Pytorch Geometric (2.4.0). All experiments are conducted on a Linux server with 8 NVIDIA A100s with 40GB memory.


  
Dataset Splits. For TUDataset, we randomly split the dataset into training, validation, and test sets by a ratio of 8:1:1. The other evaluated benchmarks already define a standard train/validation/test dataset split. 



  
Training Details. The Adam <cit.> optimizer is used for the optimization of TUDataset without a learning rate scheduler. On the Benchmarking GNN and OGB datasets, we adopt AdamW optimizer with default settings, β_1 = 0.9, β_2 = 0.999, ϵ=10^-8, along with linear warmup increase of learning rate at the beginning of training and cosine decay during training. Finally, we report the test metric (i.e., MAE, Accuracy, and AUROC) achieved by the epoch that gives the highest metric on the validation dataset.



  
Hyperparameters. In our experimental setup for Gradformer, certain hyperparameters have been standardized to streamline the tuning process. Specifically, we have set the attention dropout rate at 0.5, and the weight decay is fixed at 1e^-5. For other hyperparameters across various datasets, we have aligned our settings with those used in GraphGPS <cit.> to maintain consistency and comparability. In the deep layer performance experiment, as detailed in Table 2 of the main text, the only variable we alter is the number of layers in Gradformer. This approach allows us to isolate the impact of layer depth on model performance. Additionally, we introduce a range of values for the hyperparameter λ, which is a key component in our model. The values for λ that we explore are within the set {0.3, 0.4, 0.5, 0.6, 0.7}.  For a comprehensive understanding of our experimental setup, detailed hyperparameters are systematically listed in Table <ref>. In this table, the term `Layers' refers to the number of layers in Gradformer. `PE' denotes Positional Encoding, `RWSE' stands for Random-walk Structure Encoding, and `Lap' signifies Laplacian Eigenvectors Encodings. The notation `-20' alongside these encodings indicates that the size of the positional embedding is set to 20. 







§ DATASETS AND BASELINES





 §.§ Introduction of Datasets



We use a total of nine datasets, including five from TUDataset <cit.>, three from Benchmarking GNN <cit.>, and one from Open Graph Benchmark (OGB) <cit.>, which vary in content domains, sizes, and tasks. All the adopted graph datasets can be downloaded from PyTorch Geometric (PyG). The dataset statistics are summarized in Table <ref>. A brief introduction to these datasets is provided below.




NCI1 consists of 4,110 molecule graphs from TUDataset, which represent two balanced subsets of datasets for chemical compounds screened for activity against non-small cell lung cancer and ovarian cancer cell lines, respectively.  
 

PROTEINS consists of 1,113 protein graphs from TUDataset, where each graph corresponds to a protein molecule, nodes represent amino acids, and edges capture the interactions between amino acids. 
 

MUTAG consists of 188 chemical compounds from TUDataset, divided into two classes according to their mutagenic effect on a bacterium. 
 

IMDB-BINARY consists 1,000 movie graphs from TUDataset, classifying movies into two categories based on certain criteria. Each graph represents a movie, with nodes as actors and edges indicating their collaborations. 
 

COLLAB consists 5,000 graphs representing collaboration networks from TUDataset. Nodes represent authors, and edges denote collaborations between them. The task involves classifying graphs into three classes based on specific criteria. 
 

ZINC consists of 12,000 chemical compounds represented as graphs. The task associated with this dataset is regression, constraining solubility of the molecule. 
 

CLUSTER consists of 12,000 graphs. This dataset is widely employed to model communities in social networks by capturing intra- and extra-community relationships. It is generated with the Stochastic Block Model (SBM). 
 

PATTERN consists of 14,000 graphs and aims to identify nodes within a graph associated with one of 100 distinct sub-graph patterns. These patterns are randomly generated using SBM parameters different from the remainder of the graph. Different from other tasks, PATTERN and CLUSTER are node classification tasks. 
 

Ogbg-molhiv consists of 41,127 graphs, which are molecular property prediction datasets adopted by OGB from MoleculeNet. The prediction task involves 2-class classification of a molecule’s fitness to inhibit HIV replication.







 §.§ Introduction of Baselines

To demonstrate the effectiveness of our proposed method, we compare Gradformer against 14 baselines. These baselines consist of four general Graph Convolutional Network (GCN)-based models and 10 Transformer-based models designed for graph-related tasks. We use the original paper implementations for all baseline models. If the original paper does not provide specific dataset settings, we maintain consistent parameter configurations with Gradformer. The links to the code implementations are included in Table <ref>; if unavailable, we utilize the implementations from PyTorch Geometric. 








  §.§.§ 5.2.1   GCN-based Methods
 


GCN <cit.>. Each node aggregates information from its neighboring nodes, facilitating the network in capturing the relational dependencies within the graph. This mechanism allows for learning complex patterns and representations for each node in the graph. 
 

GAT <cit.>. It operates on graph-structured data and utilizes self-attention layers of masks. Such a utilization is computationally efficient in these networks, enabling the assignment of varying importance to different nodes when processing regions of different sizes.
 

GIN <cit.>. GIN is a streamlined yet potent network architecture that shows comparable graph structure discrimination to the Weisfeiler-Lehman test and exhibits robust representation capabilities. 
 

GatedGCN <cit.>. It incorporates gating mechanisms to enhance the learning process within the graph structure by selectively filtering and weighting the information propagated through the edges of the graph. 


  §.§.§ 5.2.2   Graph Transformer-based Methods
 
 

GT <cit.>. GT is the pioneering work that generalizes transformer networks to arbitrary graphs and introduces the corresponding architecture. 
 
 
SAN <cit.>. SAN combines node features with learned position encodings (from Laplacian eigenvalues and eigenvectors), then uses them as attention keys and queries respectively, and employs edge features as attention Force values. 
 

Graphormer <cit.>. The Graphormer model introduces three structural encodings to enable the Transformer model to capture the structural information of the graph. These encodings allow the self-attention layer of the Graphormer model to successfully capture more important nodes or node pairs,leading to more accurate attention weight allocation. 
 

GraphTrans <cit.>. GraphTrans designed a novel GNNs readout module that uses a special token to aggregate all pairs interactions into a classification vector. It has been proven that modeling pairs node-node interaction is particularly important for large graph classification tasks. 
 

SAT <cit.>. SAT proposes Structure-Aware Transformer, a simple and flexible graph Transformer based on a novel self-attention mechanism. This mechanism integrates structural information into the original self-attention by extracting a subgraph representation rooted at each node before computing attention. 
 

EGT <cit.>. EGT exclusively use global self-attention as an aggregation mechanism rather than static localized convolutional aggregation.
 

GraphGPS <cit.>. GraphGPS allows for combining message passing networks with linear (long-range) transformer models to create a hybrid network. 
 

LGI-GT <cit.>. LGI-GT introduces a novel method for global information representation by propagating [CLS] token embeddings. It also incorporates an effective message passing module called edge-enhanced local attention, making LGI-GT a fully attentive Graph Transformer. 
 

KDL-GT <cit.>. KDLGT utilizes kernel decomposition methods to rearrange the order of matrix multiplications, thereby reducing the complexity to linear levels.

 

DeepGraph <cit.>. DeepGraph is a novel graph transformer model that explicitly incorporates substructure tokens in the encoded representation. It applies local attention to related nodes, yielding substructure-based attention encoding.













§ EVALUATION ON OTHER TASK





Given Gradformer's exemplary performance in graph classification task, we are motivated to extend our evaluation to node classification task. This shift in focus aims to specifically assess Gradformer's capability to leverage local information within a graph, a crucial aspect of node classification.  Traditional GTs typically treat all nodes in a graph uniformly, primarily relying on positional encoding to capture and preserve the graph's structural information. This approach, while effective in certain contexts, may not adequately emphasize the nuances of local graph structures. In contrast, the decay mask mechanism integrated into Gradformer offers significant advancements.




 §.§ Introduction of Datasets


We use three graph datasets, including two homophilic datasets (i.e., Cora and Citeseer) and one heterophilic dataset (i.e., Actor). All mentioned datasets are available from PyTorch Geometric (PyG) <cit.>. The detailed statistics for the node classification datasets are shown in Table <ref>. 


Definition of Homophily and Heterophily.
The edge homophily ratio (γ) introduced in H2GCN <cit.> quantifies the level of graph homophily. The edge homophily ratio is defined as follows:

    γ=|{(u, v):(u, v) ∈ε∧ y_u=y_v}|/|ε|,

where u and v represent the nodes in the graph, y_u and y_v refer to the node labels, and ε represents the set of the edges in the graph. The edge homophily ratio, γ → 0, indicates strong heterophily in the graph; γ → 1 suggests strong homophily. 
 

Homogeneous Graph. In the Cora dataset, nodes represent academic documents with citation relationships serving as connections between nodes. In the Citeseer dataset, nodes represent computer science papers, and edges indicate citation relationships. Each paper node is labeled with a predefined category, reflecting various topics in computer science.
 

Heterogeneous Graph. In the Actor dataset, nodes are linked to information regarding their participation in diverse movies or TV shows, and the edges represent connections between actors.



 §.§ Implementation Details.
 We evaluate the effectiveness of the proposed strategy in terms of node classification accuracy and conduct 10 trials with random seeds for each model. All methods share the same training, validation, and test splits, and the average and standard derivation are reported as the performance. The hyperparameter learning rate is set to 0.0001, with both the training batch size and evaluation batch size set to 128. Training epoch is set to 200. λ is searched within {0.4, 0.5, 0.6, 0.7, 0.8}, and the layer of Gradformer is searched within {1, 2, 3, 4}.  Subsequently, we select GraphGPS <cit.> as the baseline to evaluate the effectiveness of Gradformer. Finally, we report the test accuracy achieved at the epoch with the highest accuracy on the validation dataset.



 §.§ Experimental Results.
 Table <ref> provides a comprehensive summary of the node classification results. Based on these results, we can draw the following conclusions:
1) Superiority of Gradformer Over Baselines:  Gradformer demonstrates a consistent improvement in performance over the baseline models across three different datasets: Cora, Citeseer, and Actor. Specifically, the accuracy enhancements observed on these datasets are 0.12%, 0.52%, and 1.06%, respectively. This consistent outperformance across diverse datasets highlights the effectiveness of the Gradformer model in node classification tasks. 2) Enhanced Performance on Heterogeneous Graphs: A notable observation from the results is that Gradformer exhibits particularly impressive performance on the Actor dataset, which is a heterogeneous graph. The significantly better results on this dataset, compared to Cora and Citeseer, suggest that Gradformer is particularly well-suited for handling heterogeneous graphs. 










§ THE PSEUDOCODE OF DECAY MASK
 




The most crucial aspect of implementing Gradformer is the addition of the decay mask to the attention scores. This process involves simply multiplying the computed attention scores with the preprocessed decay mask. The pseudocode for adding the decay mask is presented in Figure <ref>, highlighting the method's straightforwardness and simplicity and thus underscoring its implementation efficiency.



