Neighbourhood Transformer: Switchable Attention for Monophily-Aware Graph Learning

Yi Luo; Xu Sun; Guangchun Luo; Aiguo Chen

cs.LGApr 10, 2026

Neighbourhood Transformer: Switchable Attention for Monophily-Aware Graph Learning

Authors: Yi Luo, Xu Sun, Guangchun Luo, Aiguo Chen

Organizations: Laboratory of Intelligent Collaborative Computing, University of Electronic Science and Technology of China · School of Computer Science and Engineering, University of Electronic Science and Technology of China · Ubiquitous Intelligence and Trusted Services Key Laboratory of Sichuan Province, China

Abstract

Graph neural networks (GNNs) have been widely adopted in engineering applications such as social network analysis, chemical research and computer vision. However, their efficacy is severely compromised by the inherent homophily assumption, which fails to hold for heterophilic graphs where dissimilar nodes are frequently connected. To address this fundamental limitation in graph learning, we first draw inspiration from the recently discovered monophily property of real-world graphs, and propose Neighbourhood Transformers (NT), a novel paradigm that applies self-attention within every local neighbourhood instead of aggregating messages to the central node as in conventional message-passing GNNs. This design makes NT inherently monophily-aware and theoretically guarantees its expressiveness is no weaker than traditional message-passing frameworks. For practical engineering deployment, we further develop a neighbourhood partitioning strategy equipped with switchable attentions, which reduces the space consumption of NT by over 95% and time consumption by up to 92.67%, significantly expanding its applicability to larger graphs. Extensive experiments on 10 real-world datasets (5 heterophilic and 5 homophilic graphs) show that NT outperforms all current state-of-the-art methods on node classification tasks, demonstrating its superior performance and cross-domain adaptability. The full implementation code of this work is publicly available at https://github.com/cf020031308/MoNT to facilitate reproducibility and industrial adoption.

Figures & tables

Panel of Figure 1 — Figure 1: An illustration of computing representations for node $v_{1}$ (represented by a double-lined circle) using various mechanisms. (a) Message Passing : Messages from different nodes (e.g., $v_{3},v_{4},v_{5},v_{6}$ ) are propagated along edges towards node $v_{1}$ to compute its representation, but are diluted and over-squashed when passing through heterophilic bottlenecks (e.g., $v_{2}$ ). (b) Graph Transformers : Node $v_{1}$ aggregates messages from all nodes using self-attention. This approach may inadvertently downplay the importance of information from nearby nodes due to a reduction in the influence of topological structure. (c) Neighbourhood Transformers (Ours) : Node $v_{1}$ exchanges messages (depicted as squares) in each of its constituent neighbourhoods through self-attention, thereby acquiring attentive and structure-aware representations.

Figure 2: Unevenly distributed neighbourhood sizes. ① Paralleled Processing pads node features of all neighbourhoods and processes the padded tensor in a single operation, occupying excessive memory when the node degree distribution is long-tailed. ② Sequential Processing organizes neighbourhoods by size and processes node features group by group, consuming prohibitive time when the node degree distribution is dispersed.

Figure 3: In directed graphs, the source nodes ( $v_{2},v_{3},v_{4}$ ) to the central node ( $v_{1}$ ) and its destination nodes ( $v_{5},v_{6}$ ) construct different neighbourhoods.

Figure 4: Partitioning neighbourhoods into multiple groups for space and time efficiency. We partition neighbourhoods into two groups based on the degrees of their central nodes. Neighbourhoods with more than $n$ nodes will be processed by Performer for efficiency and other small neighbourhoods will be processed by Transformer for accuracy. Each group of neighbourhoods is recursively partitioned into two approximately equal halves in terms of area ( $s_{1}\approx s_{2}$ ), provided that the partitioning leads to a considerable compression rate $\alpha$ .

	Roman Empire	A-ratings	Minesweeper	Tolokers	Questions
#Nodes	22,662	24,492	10,000	11,758	48,921
#Edges	32,927	93,050	39,402	519,000	153,540
Mean Deg.	2.91	7.60	7.88	88.28	6.28
#Features	300	300	7	10	301
#Classes	18	5	2	2	2
Homophily	-4.68%	14.02%	0.94%	9.26%	2.07%

Table 1: Averaged accuracy scores and the standard deviations in 10 runs on heterophilic graphs. The best score for each dataset is bolded , and the second best is underlined .

	A-computer	A-photo	CoauthorCS	CoauthorPhy	WikiCS
#Nodes	13,752	7,650	18,333	34,493	11,701
#Edges	245,861	119,081	81,894	247,962	216,123
Mean Deg.	35.76	31.13	8.93	14.38	36.85
#Features	767	745	6,805	8,415	300
#Classes	10	8	15	5	10
Homophily	68.23%	78.50%	78.45%	87.24%	57.90%

Table 2: Averaged accuracy scores and the standard deviations in 10 runs on homophilic graphs. The best score for each dataset is bolded , and the second best is underlined .

Figure 5: Ablation studies on the neighbourhood partitioning strategy. Bars represent memory footprints and curves are time consumptions. We compare paralleled processing (the first bar/point), partitioning neighbourhoods by size (the second bar/point), by both size and area with $\alpha=0.1,0.2,\ldots,0.9$ (the hollow bars/points), and sequential processing (the last bar/point).

Figure 6: Accuracy scores (%, the horizontal axes) in 10 runs with different attention modules: Transformer with self-attention, Performer with linear-attention, and our switchable attention module. The middle line in each violin plot represents the average score.

Figure 7: Accuracy scores (%, the horizontal axes) in 10 runs with different aggregators. The middle line in each violin plot represents the average score.

	Roman Empire	A-ratings	Minesweeper	Tolokers	Questions
GCN	73.69±0.74	48.70±0.63	89.75±0.52	83.64±0.67	76.09±1.27
Dir-GNN	91.23±0.32	47.89±0.39	87.05±0.69	81.19±1.05	76.13±1.24
NT	91.71±0.57	54.25±0.50	97.42±0.50	85.69±0.54	78.46±1.10
Dir-NT	94.77±0.31	49.43±0.62	93.92±0.59	85.02±0.77	77.99±1.00

Table 3: Averaged accuracy scores and the standard deviations in 10 runs on heterophilic graphs.

Figure 8: Accuracy scores (%, the horizontal axes) in 10 runs with and without the separation of ego- and neighbour-embeddings. The middle line in each violin plot represents the average score.

Figure 9: Accuracy scores (%, the horizontal axes) in 10 runs with and without self-loops. The middle line in each violin plot represents the average score.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

	Aggregator	#dimensions	#heads	#layers	Dropout
Roman Empire	$\mathrm{sum}$	32	6	5	0.4
A-ratings	$\mathrm{mean}$	40	8	1	0.3
Minesweeper	$\mathrm{sum}$	53	1	5	0.2
Tolokers	gated- $\mathrm{sum}$	30	2	5	0.1
Questions	$\mathrm{sum}$	32	4	1	0.2
Roman Empire (directed)	$\mathrm{max}$	36	5	5	0.4

Appendix

Table 4: Hyperparameters of NT on 10 graphs.

	Figure 5	Figure 6	Figure 7	Figure 9
Aggregator	$\mathrm{mean}$	weighted- $\mathrm{mean}$	—	weighted- $\mathrm{mean}$
#dimensions	8	8	8	8
#heads	4	4	8	8
#layers	1	1	2	2
Dropout	0	0.2	0.2	0.2
Learning rate	0.01	0.01	0.01	0.01

Appendix

Table 5: Experimental settings of NT on ablation studies.

Dataset	Descrepency
Roman Empire	3.5%
A-ratings	5.3%
Minesweeper	0.6%
Tolokers	8.8%
Questions	3.9%
A-computer	6.5%

Appendix

Table 6: The descrepencies of neighbourhood sizes in training and in inference.

	Roman Empire	A-ratings	Minesweeper	Tolokers	Questions
GraphGPS	82.00±0.61	53.10±0.42	90.63±0.67	83.71±0.48	71.73±1.47
NAGphormer	74.34±0.77	51.26±0.72	84.19±0.66	78.32±0.95	68.17±1.53
Exphormer	89.03±0.37	53.51±0.46	90.74±0.53	83.77±0.78	73.94±1.06
NodeFormer	64.49±0.73	43.86±0.35	86.71±0.88	78.10±1.03	74.27±1.46
DIFFormer	79.10±0.32	47.84±0.65	90.89±0.58	83.57±0.68	72.15±1.31
GOAT	71.59±1.25	44.61±0.50	81.09±1.02	83.11±1.04	75.76±1.66

Appendix

Table 7: Averaged accuracy scores and the standard deviations in 10 runs on heterophilic graphs. The best score for each dataset is bolded , the second best is underlined , and the third is italic .

	A-computer	A-photo	CoauthorCS	CoauthorPhy	WikiCS
GraphGPS	91.19±0.54	95.06±0.13	93.93±0.12	97.12±0.19	78.66±0.49
NAGphormer	91.22±0.14	95.49±0.11	95.75±0.09	97.34±0.03	77.16±0.72
Exphormer	91.47±0.17	95.35±0.22	94.93±0.01	96.89±0.09	78.54±0.49
NodeFormer	86.98±0.62	93.46±0.35	95.64±0.22	96.45±0.28	74.73±0.94
DIFFormer	91.99±0.76	95.10±0.47	94.78±0.20	96.60±0.18	73.46±0.56
GOAT	90.96±0.90	92.96±1.48	94.21±0.38	96.24±0.24	77.00±0.77

Appendix

Table 8: Averaged accuracy scores and the standard deviations in 10 runs on homophilic graphs. The best score for each dataset is bolded , the second best is underlined , and the third is italic .

Graph Transformer

Graph Transformers adapt self-attention to represent relationships, topology, and long-range dependencies in graph-structured data.

See all 100 papers

Inductive Subgraphs as Shortcuts: Causal Disentanglement for Heterophilic Graph Learning
Apr 21, 2026Xiangmeng Wang, Qian Li, Haiyang Xia +3Disentangled Representation Learning Graph Neural Networks
Curtin University Perth, Australia · The Education University of Hong Kong New Territories, Hong Kong
Revealing the Pitfalls and Re-Evaluating the Advancement of Heterophilic Graph Learning
Sep 9, 2024Sitao Luan, Qincheng Lu, Chenqing Hua +3Graph Neural Networks Node Classification
Mila - Quebec Artiﬁcial Intelligence Institute · 1McGill University
Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation
May 8, 2026Md Sazzad Hossen, Avimanyu SahooGraph Heterophily Over-Squashing
University of Alabama in Huntsville, Huntsville, AL, USA.

Apr 21, 2026J/K move · Enter open · S save

Inductive Subgraphs as Shortcuts: Causal Disentanglement for Heterophilic Graph Learning

Xiangmeng Wang, Qian Li, Haiyang Xia, Hao Miao+2

Curtin University Perth, Australia · The Education University of Hong Kong New Territories, Hong Kong

Disentangled Representation Learning Graph Neural Networks Causal Representation Learning Graph Heterophily

Open paper AskPDF arXiv

Heterophily is a prevalent property of real-world graphs and is well known to impair the performance of homophilic Graph Neural Networks (GNNs). Prior work has attempted to adapt GNNs to heterophilic graphs through non-local neighbor extension or architecture refinement. However, the fundamental reasons behind misclassifications remain poorly understood. In this work, we take a novel perspective by examining recurring inductive subgraphs, empirically and theoretically showing that they act as spurious shortcuts that mislead GNNs and reinforce non-causal correlations in heterophilic graphs. To address this, we adopt a causal inference perspective to analyze and correct the biased learning behavior induced by shortcut inductive subgraphs. We propose a debiased causal graph that explicitly blocks confounding and spillover paths responsible for these shortcuts. Guided by this causal graph, we introduce Causal Disentangled GNN (CD-GNN), a principled framework that disentangles spurious inductive subgraphs from true causal subgraphs by explicitly blocking non-causal paths. By focusing on genuine causal signals, CD-GNN substantially improves the robustness and accuracy of node classification in heterophilic graphs. Extensive experiments on real-world datasets not only validate our theoretical findings but also demonstrate that our proposed CD-GNN outperforms state-of-the-art heterophily-aware baselines.

Abstract

Graph Transformer

Explore similar work

Inductive Subgraphs as Shortcuts: Causal Disentanglement for Heterophilic Graph Learning

Revealing the Pitfalls and Re-Evaluating the Advancement of Heterophilic Graph Learning

Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation