arXiv:2604.22413v1 [cs.LG] 24 Apr 2026
Distance-Misaligned Training in Graph Transformers and Adaptive Graph-Aware Control Qinhan Hou
Jing Tang
University of Helsinki Helsinki, Finland [email protected]
University of Helsinki Helsinki, Finland [email protected]
Abstract—Graph Transformers can mix information globally, but this flexibility also creates failure modes: some tasks require long-range communication while others are better served by local interaction. We study this through a synthetic node-classification benchmark on contextual stochastic block model graphs, where labels are generated by a controllable mixture of local and far-shell signals. We define distance-misaligned training as a mismatch between where label-relevant information lies and where the model allocates communication over graph distance. On this benchmark, we find three points. First, the preferred graph-distance bias changes systematically with task locality. Second, an oracle adaptive controller, given offline access to the task-side distance target, nearly matches the best fixed bias across regimes and strongly improves over a neutral baseline on mixed and local tasks. Third, a task-agnostic zero-gap controller is weaker, indicating that adaptation alone is not enough and that the control target matters. These results suggest that distance-resolved diagnosis is useful for understanding Graph Transformer failures and for designing graph-aware control. Index Terms—graph transformers, graph signal processing, training dynamics, structural bias, adaptive control
I. I NTRODUCTION Graph Transformers have emerged as a competitive family of graph learners, but their performance depends strongly on how structural bias is injected into dense attention [1]–[3]. Recent analyses also suggest that unrestricted graph attention can create undesirable regimes such as over-globalizing, over-aggregating, and attention-based oversmoothing [4]–[8]. These observations motivate a training-dynamics question: when should a model communicate broadly across the graph, and when should it remain local? We study this question through the lens of distance misalignment. The key idea is to separate two distributions over graph distance: task dependence, which captures where label-relevant information lives, and model utilization, which captures where the trained model allocates communication. A run is under-reaching when the task depends on larger graph distances but the model stays too local, and over-globalizing when the task is mostly local but the model allocates too much mass to distant nodes. Our viewpoint is complementary to prior work on Graph Transformer architectural bias: instead of proposing a new attention mechanism, we ask whether training itself can be diagnosed and steered in graph-distance space. Our contribution is empirical. On a controlled synthetic benchmark with explicit local and far-range supervision struc-
ture, we show that distance-resolved mismatch diagnoses Graph Transformer failures and that a simple graph-aware intervention can steer training. II. E XPERIMENTAL S ETUP We use a dense node-level Graph Transformer with a graphdistance bias added to the attention logits: qi⊤ kj + λdist bdist (spd(i, j)), logitij = √ d
(1)
where spd(i, j) is shortest-path distance and bdist (r) = −r; larger λdist favors local communication, while smaller (or negative) values favor more global communication. The benchmark uses contextual stochastic block model graphs and a two-signal node-classification task. Let zj be the latent node signal, N≤1 (i) the 0–1 hop neighborhood of node i, and Sr⋆ (i) the shell at distance r⋆ . We define gloc (i) = gfar (i) =
1
X
|N≤1 (i)| 1 |Sr⋆ (i)|
zj ,
j∈N≤1 (i)
X
(2)
zj ,
j∈Sr⋆ (i)
standardize these scores over valid nodes to obtain ĝloc and ĝfar , and form labels by s(i) = βĝloc (i) + (1 − β)ĝfar (i),
yi = 1[s(i) > 0]. (3)
The mixture coefficient β ∈ [0, 1] controls locality: β = 1 is local and β = 0 is far/global. To measure training regime, we compute a task-side distance profile πtask (r) and a shell-size-corrected attention profile πA (r). We summarize mismatch P by the mean-distance gap µ − µ , where µ = task A task r r πtask (r) and µA = P r r πA (r), and by the Wasserstein-1 distance W1 (πtask , πA ). We compare neutral training (λdist = 0), fixed-λdist sweeps, a zero-gap controller that drives µtask − µA toward 0, and an oracle target-gap controller, where oracle means that the target gap is supplied offline from the validation-selected best fixed λdist for each β rather than estimated from model-side signals during training. Positive gap indicates under-reaching and negative gap indicates over-globalizing.
(a) Bias vs task locality
(b) Accuracy vs task locality
2.0
1.0 0.5
best static adaptive final
0.00
0.25
0.50
task locality (c) Mean-distance gap vs bias
0.75 0.70 0.65
1.00
0.00
4 1
0.50
0.75
0
1
2
dist
1.00 =0 = 0.5 =1
5
2
2
0.25
task locality (d) Wasserstein mismatch vs bias W1( task, A)
A
gap task
0
target-gap fixed best
0.80
far task = 0 local task = 1
4 2
0.75
test accuracy
dist
1.5
0.0
neutral zero-gap
0.85
4 3 2 1 0
2
1
0
1
2
dist
Fig. 1. Results on the synthetic CSBM benchmark. (a) Validation-selected best fixed bias and final target-gap bias shift toward larger positive λdist as tasks become more local. (b) Test accuracy of neutral, zero-gap, target-gap, and best fixed settings; zero-gap targets µtask − µA = 0, while target-gap targets the oracle gap of the best fixed sweep. (c) Mean-distance gap shows how the same bias knob traverses over-globalizing and under-reaching regimes. (d) Wasserstein mismatch shows the same locality-dependent shift without sign.
III. R ESULTS A. Preferred graph-distance bias shifts with task locality Panel (a) of Fig. 1 shows a monotone shift toward larger positive λdist as the task becomes more local. The validationselected bias is 0.5 at β = 0, 1.0 at β = 0.25, and 2.0 for β ∈ {0.5, 0.75, 1.0}. The far-task region is comparatively flat, so the β = 0 point should be read as near neutral; the adaptive target-gap controller ends at similar final λdist values. B. Oracle target-gap control tracks the best fixed sweep Panel (b) of Fig. 1 gives the main performance comparison. The neutral model is competitive only on the most global task; as locality increases, its regret grows, while the oracle target-gap controller remains close to the best fixed setting. For β ∈ {0.5, 0.75, 1.0}, target-gap control reaches 0.704, 0.789, and 0.842, compared with 0.655, 0.667, and 0.664 for fixed neutral, 0.659, 0.674, and 0.792 for zero-gap, and 0.713, 0.815, and 0.860 for the best fixed runs. This indicates that adaptation helps most when it targets a task-appropriate distance regime. C. Mismatch curves identify opposite failure modes Panels (c) and (d) of Fig. 1 provide the mechanistic interpretation of the sweep. The mean-distance gap behaves differently
for far and local tasks as λdist varies, and the Wasserstein mismatch follows the same locality-dependent shift in a signfree form. For the far task (β = 0), increasing locality bias pushes the model from mild over-globalizing behavior into strong under-reaching. For the local task (β = 1), the trend is reversed: weak or negative bias is strongly over-globalizing, while larger positive bias moves the model toward a small positive gap near the best-performing region. This is the main mechanistic evidence that the same control knob traverses distinct distance-misaligned regimes. The Wasserstein panel shows the complementary summary on representative far, mixed, and local tasks: its minimum shifts from weak or negative bias toward larger positive bias as β increases. IV. C ONCLUSION On this synthetic benchmark, distance-resolved mismatch provides a compact diagnostic of whether a Graph Transformer is over-globalizing or under-reaching, and graph-distance bias provides an effective control knob beyond aggregate accuracy alone. The future work is to replace the oracle target with an observable regime estimator built from model-side training signals and use it for online scheduling that avoids poor training regimes. Moreover, the impact of the self-bias term is still underexplored.
ACKNOWLEDGMENT This study was funded by the European Union (DTRIP4H, No. 101188432) and iCANDOC Precision Cancer Medicine (PCM) pilot program from the Research Council of Finland. R EFERENCES [1] Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do Transformers Really Perform Badly for Graph Representation? In Advances in Neural Information Processing Systems, volume 34, pages 28877–28888. Curran Associates, Inc., 2021. [2] Ladislav Rampášek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for a General, Powerful, Scalable Graph Transformer. Advances in Neural Information Processing Systems, 35:14501–14515, 2022. [3] Hongkang Li, Meng Wang, Tengfei Ma, Sijia Liu, Zaixi Zhang, and Pin-Yu Chen. What improves the generalization of graph transformers? a theoretical dive into the self-attention and positional encoding. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of ICML’24, pages 28784–28829. JMLR.org, 2024. [4] Yujie Xing, Xiao Wang, Yibo Li, Hai Huang, and Chuan Shi. Less is More: on the Over-Globalizing Problem in Graph Transformers, 2024. arXiv:2405.01102 [cs]. [5] Junshu Sun, Wanxing Chang, Chenxue Yang, Qingming Huang, and Shuhui Wang. Relieving the over-aggregating effect in graph transformers. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. [6] Jiaming Zhuo, Ziyi Ma, Yintong Lu, Yuwei Liu, Kun Fu, Di Jin, Chuan Wang, Wenning Wu, Zhen Wang, Xiaochun Cao, and Liang Yang. A closer look at graph transformers: Cross-aggregation and beyond. In The Thirty-ninth Annual Conference on Neural Information Processing Systems, 2025. [7] Xinyi Wu, Amir Ajorlou, Zihui Wu, and Ali Jadbabaie. Demystifying oversmoothing in attention-based graph neural networks. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 35084–35106. Curran Associates, Inc., 2023. [8] Gbetondji Jean-Sebastien Dovonon, Michael M. Bronstein, and Matt Kusner. Setting the Record Straight on Transformer Oversmoothing. Transactions on Machine Learning Research, 2024.