ANPGT: Towards Adaptive Node Property Extraction and Integration

Graph transformers (GTs) with elaborate positional/structural encodings (PEs/SEs) have excelled in graph representation learning, especially in graph‐level tasks. However, their potential in large‐scale node classification remains untapped for several reasons: (i) Current PEs/SEs are insufficient in modelling large‐scale real‐world graphs, where a multi‐angle portrayal of node properties is required. (ii) The common integration of PEs/SEs with self‐attention overlooks nodes' distinct preferences, leading to sub‐optimal performance. (iii) The global receptive field of self‐attention leads to quadratic complexity with respect to graph size and introduces potential noise, which significantly hinders the learning of node‐level tasks. In this paper, we propose the adaptive node property graph transformer (ANPGT) to address the above issues. ANPGT, with its node property extractor (NPE) and adaptive property integrator (API), flexibly extracts multi‐angle node Properties and integrates them according to node‐specific preferences. Theoretically, we analyse the necessity of adaptive node property learning. Empirically, ANPGT achieves or matches the best performance on nine real‐world datasets (up to three million nodes) and various synthetic benchmarks regarding heterophily and noises. ANPGT exhibits almost linear complexity relative to graph size.