Graph Transformers in Network Analysis

Abstract

Graph neural networks have established themselves as the dominant paradigm for learning on structured relational data, but their message-passing architectures suffer from well-documented limitations: over-smoothing at depth, limited expressive power bounded by the Weisfeiler-Leman graph isomorphism test, and poor capture of long-range dependencies across graph diameter. Graph Transformers address these limitations by applying attention mechanisms directly to graph structure, enabling global information propagation without the depth constraint of iterative message passing. This study benchmarks eight Graph Transformer architectures -- Graphormer, GraphGPS, NodeFormer, Exphormer, SAT (Structure-Aware Transformer), GraphViT, NAGphormer, and DIFFormer -- across five network analysis tasks: node classification, link prediction, graph classification, community detection, and network resilience assessment. Evaluation spans nine benchmark datasets including ogbn-arxiv, ogbl-collab, PCQM4Mv2, TUDatasets, and a purpose-built European Critical Infrastructure Network (ECIN) dataset. Graphormer achieves the highest performance on molecular graph tasks (MAE 0.0864 on PCQM4Mv2). GraphGPS achieves best mean rank across all tasks (1.8). NodeFormer scales to graphs with 10^6 nodes through linear attention, enabling network resilience assessment at infrastructure scale. Community detection using Graph Transformers achieves NMI of 0.784 on synthetic stochastic block model graphs, 14.2% above GCN baselines. A scalability-accuracy trade-off framework for Graph Transformer selection is proposed.