Distance-Misaligned Training in Graph Transformers and Adaptive Graph-Aware Control
Qinhan Hou, Jing Tang · 2026
Read Distance-Misaligned Training in Graph Transformers and Adaptive Graph-Aware Control by Qinhan Hou, Jing Tang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-22413.txt.
Introduction
Hou and Tang study a failure mode of graph transformers: some tasks need long-range communication, others local interaction. They define distance-misaligned training on a synthetic benchmark: a mismatch between where label information lies and where the model sends communication. They find the preferred distance bias shifts with task locality. An oracle adaptive controller nearly matches the best fixed bias and strongly beats a neutral baseline on mixed and local tasks. A task-agnostic zero-gap controller is weaker, showing adaptation alone is not enough. The control target matters.
Catalog record
| CREATOR | Qinhan Hou, Jing Tang |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 8219 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.22413
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Distance-Misaligned Training in Graph Transformers and Adaptive Graph-Aware Control
Qinhan Hou, Jing Tang
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.
I
Introduction
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
[
7
,
3
,
2
]
.
Recent analyses also suggest that unrestricted graph attention can create
undesirable regimes such as over-globalizing, over-aggregating, and
attention-based oversmoothing
[
6
,
4
,
8
,
5
,
1
]
.
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 structure, we show that
distance-resolved mismatch diagnoses Graph Transformer failures and that a
simple graph-aware intervention can steer training.
Fig. 1:
Results on the synthetic CSBM benchmark. (a) Validation-selected best fixed bias and final target-gap bias shift toward larger positive
\lambda_{dist}
as tasks become more local. (b) Test accuracy of neutral, zero-gap, target-gap, and best fixed settings; zero-gap targets
\mu_{\mathrm{task}}-\mu_{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.
II
Experimental Setup
We use a dense node-level Graph Transformer with a graph-distance bias added to
the attention logits:
\mathrm{logit}_{ij}=\frac{q_{i}^{\top}k_{j}}{\sqrt{d}}+\lambda_{\mathrm{dist}}\,b_{\mathrm{dist}}(\mathrm{spd}(i,j)),
(1)
where
\mathrm{spd}(i,j)
is shortest-path distance and
b_{\mathrm{dist}}(r)=-r
; larger
\lambda_{\mathrm{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
z_{j}
be the latent node signal,
N_{\leq 1}(i)
the 0–1 hop neighborhood of node
i
, and
S_{r^{\star}}(i)
the shell at
distance
r^{\star}
. We define
\displaystyle g_{\mathrm{loc}}(i)
\displaystyle=\frac{1}{|N_{\leq 1}(i)|}\sum_{j\in N_{\leq 1}(i)}z_{j},
(2)
\displaystyle g_{\mathrm{far}}(i)
\displaystyle=\frac{1}{|S_{r^{\star}}(i)|}\sum_{j\in S_{r^{\star}}(i)}z_{j},
standardize these scores over valid nodes to obtain
\hat{g}_{\mathrm{loc}}
and
\hat{g}_{\mathrm{far}}
, and form labels by
s(i)=\beta\hat{g}_{\mathrm{loc}}(i)+(1-\beta)\hat{g}_{\mathrm{far}}(i),\qquad y_{i}=\mathbf{1}[s(i)>0].
(3)
The mixture coefficient
\beta\in[0,1]
controls locality:
\beta=1
is local and
\beta=0
is far/global.
To measure training regime, we compute a task-side distance profile
\pi_{\mathrm{task}}(r)
and a shell-size-corrected attention profile
\pi_{A}(r)
. We summarize mismatch by the mean-distance gap
\mu_{\mathrm{task}}-\mu_{A}
, where
\mu_{\mathrm{task}}=\sum_{r}r\,\pi_{\mathrm{task}}(r)
and
\mu_{A}=\sum_{r}r\,\pi_{A}(r)
, and by the Wasserstein-1 distance
W_{1}(\pi_{\mathrm{task}},\pi_{A})
. We compare neutral training
(
\lambda_{\mathrm{dist}}=0
), fixed-
\lambda_{\mathrm{dist}}
sweeps, a
zero-gap controller that drives
\mu_{\mathrm{task}}-\mu_{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
\lambda_{\mathrm{dist}}
for each
\beta
rather than estimated from model-side
signals during training.
Positive gap indicates under-reaching and negative gap indicates over-globalizing.
III
Results
III-A
Preferred graph-distance bias shifts with task locality
Panel (a) of Fig.
1
shows a monotone shift toward larger
positive
\lambda_{\mathrm{dist}}
as the task becomes more local. The
validation-selected bias is
0.5
at
\beta=0
,
1.0
at
\beta=0.25
, and
2.0
for
\beta\in\{0.5,0.75,1.0\}
. The far-task region is comparatively
flat, so the
\beta=0
point should be read as near neutral; the adaptive
target-gap controller ends at similar final
\lambda_{\mathrm{dist}}
values.
III-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
\beta\in\{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.
III-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
\lambda_{\mathrm{dist}}
varies, and the Wasserstein
mismatch follows the same locality-dependent shift in a sign-free form. For the
far task (
\beta=0
), increasing locality bias pushes the model from mild
over-globalizing behavior into strong under-reaching. For the local task
(
\beta=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
\beta
increases.
IV
Conclusion
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