Neighbourhood Transformer: Switchable Attention for Monophily-Aware Graph Learning

Graph neural networks have revolutionized the analysis of relational data, but their reliance on homophily—the assumption that connected nodes are similar—limits their effectiveness on heterophilic graphs prevalent in real-world scenarios. Traditional message passing frameworks struggle to filter conflicting signals from dissimilar neighbors, leading to degraded performance in tasks like node classification. To overcome this, the authors propose Neighborhood Transformer (NT), a novel architecture that leverages local self-attention within each node's neighborhood, capturing monophily patterns effectively.

NT introduces a neighborhood partitioning strategy, which divides neighborhoods into manageable groups processed via switchable attention mechanisms—either full Transformer or linear attention (Performer). This approach drastically reduces computational costs, enabling scalable training on large graphs. Theoretically, the authors prove NT's expressive power is on par with or exceeds that of conventional message passing GNNs, ensuring no loss in representational capacity.

Extensive experiments across 10 datasets, including heterophilic and homophilic graphs, demonstrate NT's superior accuracy, robustness, and efficiency. Notably, on the Tolokers dataset, training time was cut by over 92%, and memory usage dropped by 95%, illustrating practical benefits. The model excels in heterophilic settings, capturing local monophily features that traditional GNNs often miss.

This work significantly advances graph learning by bridging the gap between expressive power and computational feasibility, especially for large-scale, complex graphs. Its theoretical guarantees and engineering innovations pave the way for broader industrial adoption. Future directions include multi-scale neighborhood modeling, dynamic graph adaptation, and multi-relational extensions, promising a versatile framework for next-generation graph AI.