Reducing Attention Complexity in Graph Transformers through Subgraph Partitioning

Abstract

This dissertation addresses the challenge of scaling Graph Transformers by proposing a subgraph-based strategy to reduce attention complexity. The proposed framework preserves representational power while making attention computation tractable for largescale graphs. The method begins by partitioning the input graph into K subgraphs using the METIS algorithm. Each subgraph is encoded using a combination of local structural features from a Graph Convolutional Network (GCN) and global positional cues from Laplacian Positional Embeddings (LPEs). These embeddings are fused via a trainable projection function to form subgraph tokens. A supergraph is constructed to model interactions among subgraphs, allowing attention to be applied over a K × K matrix instead of the full n × n space, thereby reducing complexity from O(n2) to O(K2). Finally, a component-aware prediction strategy maps subgraph-level predictions to individual nodes using learned weights and regularization. Empirical evaluations demonstrate that the framework delivers higher accuracy, improved convergence, and scalability across diverse benchmark datasets.