LocalFormer: Mitigating Over-Globalising in Transformers on Graphs with Localised Training
Authors: Naganand Yadati
Venue: Accepted by TMLR ()

Abstract: As Transformers become more popular for graph machine learning, a significant issue has recently been observed. Their global attention mechanisms tend to overemphasize distant vertices, leading to the phenomenon of ``over-globalising.'' This phenomenon often results in the dilution of essential local information, particularly in graphs where local neighbourhoods carry significant predictive power. Existing methods often struggle with rigidity in their local processing, where tightly coupled operations limit flexibility and adaptability in diverse graph structures. Additionally, these methods can overlook critical structural nuances, resulting in an incomplete integration of local and global contexts. This paper addresses these issues by proposing LocalFormer, a novel framework, to effectively localise a transformer model by integrating a distinct local module and a complementary module that integrates global information. The local module focuses on capturing and preserving fine-grained, neighbourhood-specific patterns, ensuring that the model maintains sensitivity to critical local structures. In contrast, the complementary module dynamically integrates broader context without overshadowing the localised information, offering a balanced approach to feature aggregation across different scales of the graph. Through collaborative and warm-up training strategies, these modules work synergistically to mitigate the adverse effects of over-globalising, leading to improved empirical performance. Our experimental results demonstrate the effectiveness of LocalFormer compared to state-of-the-art baselines on vertex-classification tasks.

Published in Transactions on Machine Learning Research (05/2025)
LocalFormer: Mitigating Over-Globalising in Transformers on Graphs with Localised Training
Naganand Yadati Independent Researcher
y.nogenand@gmail.com com
Reviewed on OpenReview:
Abstract
As Transformers become more popular for graph machine learning, significant issue has recently been observed. Their global attention mechanisms tend overemphasize distant vertices, leading to the phenomenon of "ever-goobalising." This phenomenon often results in the dilution of essential local information, particularly in graphs where local neighbour- hoods carry significant predictive power. Existing methods often struggle with rigidity in their local processing, where tightly coupled operations limit flexibility and adaptability in diverse graph structures. Additionally, these methods can overlook critical structural muancos, resulting an incomplete integration of local and global contexts. This paper addresses these issues by proposing LocalFormer, a novel framework, to effectively localise transformer model by integrating distinet local module and complementary module that integrates global information. The local module focuses on capturing and preserving fine-grained, neighbourhood-specifft patterns, ensuring that the model maintains sensitivity to critical local structures. In contrast, the complementary module dynamically integrates broader context. without overshadowing the localised information, offering a balanced ap- proach to feature aggregation across different scales the graph. Through collaborative and warm-up training strategies, these modules work synergistically to mitigate the adverse effects of over-globalising, leading to improved empirical performance. Our experimental results demonstrate the effectiveness of LocalFormer compared to state-of-the-art baselines on vertex-classifiattion lasks.
1 Introduction
enables the extraction of meaningful patterns and relation- ships from grapb-structured data, which is prevalent in many real-world applications such social networks, biological networks, and transportation systems. Graph Neural Networks (GNNs) Kipf and Welling (2017):
Graph representation learning Hamilton (020)
Veličković et al. 20188; Hamilton et al. (2017); Xu et al. (2019) effectively extract information from graph data Wu et al. (2022a) Ma and Tang 2020) but struggle with over-smoothing Li et al. (2018) and over- squashing Alon and Yahay] (2021). limiting their receptive fields. In contrast, Transformers Vaswani et al.
(2017), with their global attention mechanism, offer a promising solution by naturally considering all vertex pairs and adaptively learning interaction relationships from graph data Müller al. 2024)..
The remarkable success of transformers graphs in graph-level tasks (e.g., molecular property prediction) Kreuzer et al. (2021 Ying et al. (2021); Rampasek et al. (002aa); Wu et al. (2023a) is mainly attributed to their global attention mechanism, which offers enhanced global perception. However, efforts to apply this mechanism to vertex-level (asks have recently revealed the issue of over-globalising Xing el al. (2024). where the attention mechanism disproportionately focuses on higher-order nodes, neglecting more informative lower-order nodes (i.c., local neighbourhoods). Empirical and thcorctical analysos indicate that an excessively expanded receptive field can diminish the effectiveness of the global attention mechanism, suggesting the need for more balanced approach to optimise transformer performance graphs.

---

Published in Transactions on Machine Learning Research (05/2025)
Identifying the weakness of the global attention mechanism of transformers on graphs naturally raises the question of how to improve it to prevent over-globalising while still extracting valuable information from high-order nodes. Integrating a local module, such as GNNs, can alleviate this issue ZHHAG et al. (2022);
Kong ct al.] (2023); Liu et al. (2023): : Chen et al. (2022); Wu et al. (2021), but the differing propertics of local smoothing in GNNs and over-globalising in Graph Transformers complicate the influence on verlex representations. Additionally, the common practice of fusing local and global information through lincar combination inadequate and leads incorrect predictions Xing al. (0024), even when either local or global information alone could have been accurate.
To effectively mitigate the over-globalising problem in graph transformers, a balanced approach is crucial: one that integrates a focused local module with a complementary module that focuses on global information trained and optimised collaboratively. This collaborative training allows for the preservation of fine- braegrained, neighborhoodd-peeifie details while simultancously capturing broader patterns. CoBFormer Xing et al. (2024) adopts this strategy by employing a graph convolutional network (GCN) alongside intra- and inter-cluster transformers to manage local and global information.
Despite these innovations, existing methods face notable limitations. Specifically, the coupled nature of the GCN-based local module restricts flexibility, preventing adaptation to diverse graph structures and limiting the ability to skip irrelevant local information (e-g., less informative one-hop neighbours on heterophilic tasks). To overcome these limitations and address the over-globalising problem, we present the following contributions:
We introduce LocalFormer, a novel training framework designed to localise a transformer on graphs, and demonstrate that the only existing method is a specific instance of LocalFormer.
To address the over-globalising issue in transformers graphs explore novel training strategies of LocalFormer, featuring ideas such as collaborative and warm-up training strategies.
We conduct extensive experimenlation on vertex classification datasets to demonstrate the effective- ness of LocalFormer in mitigating over-globalising compared to state-of-the-art baselines.
2
Related Work
Graph Neural Networks (GNNs) Wu et al. (2022a] are designed to compute vertex reprosentations by
recursively aggregating and combining information from neighbouring vertices through message-psssngg
framework Gilmer et al. (2017). Prominent examples of GNNs include Graph Convolutional Network (GCN)
Kipf and Welling (017)) Graph Attention Networks (GAT) Veličković et al. (2018), Graph Sample and
Aggregate (GraphSAGE) Hamilton et al. (2017). and Graph Isomorphism Network (GIN Xu et al. (2019)
The issues of over-smoothhig Li et al. (2018) and over-squashing AAlon and Yahav (2021) hinder GNNs from
effectively stacking multiple layers, thereby limiting their ability to capture information from distant vertices. Furthermore, the initial designs of GNNs were based the homophily assumption Zhu et al. (2020), which posits that connected vertices belong to the same type. Although many GNNs have been designed to handle heterophilic graphs including the most recent methods Wang et al. (2024)); Liang et al. (2024): Wang et al.
(2024b); Yu et al. (2024). they continue to encounter challenges such as over-smoothing Park et al. (2024).
Transformers Vaswani et al. (0117) utilise global attention mechanisms, effectively constructing fully con- nected computation graphs with adjustable and learnable edge weights Extensive research Kreuzer et al. (2021 ; Ying et al. (2021); Rampasek et al. (2022a) has achieved remarkable success in graph-level tasks, primarily due to their global awareness capability. Building these, researchers are exploring how to inte- grate global attention mechanisms into vertex-level tasks Wu et al. (2023a] 2022b); Kong et al. (2023) Liu
ct al. 2023 Chen et al. (2022); Wu et al.] (2021). Despite the benefits, ever-globalising can Icad to a loss of important local details. Effective stralegies are needed to maintain a balance between global and local information Xing et al. (2024). This research precisely focuses on exploring effective approaches, striving to achieve an optimal balance between global and local information. While existing works [1,2,3] demonstrate that proper positional encoding can ensure expressivity and capture specific graph structures, they primarily focus on architectural modifications rather than the training process itself.
2

---

Published in Transactions on Machine Learning Research (05/2025)
Positioning the Contributions of Our Paper. While existing transformers, surveyed extensively Müller ct al. (024): Shehzad et al. 2024], demonstrate that proper positional encoding can ensure expressivity and capture specific graph structures, they primarily focus on architectural modifications rather than the training process itself. Our paper introduces Collaborative.ocalFooo
(CLF) and WarmLocalFormer (WLF), which systematically mitigate the over-globalising issue in Graph Transformers an aspect that prior studies have overlooked. Fundamentally, all Graph Transformer architectures inherently suffer from the over-globalising issue due to the nature of the global attention mechanism, which distributes focus across all nodes rather than emphasizing essential local structures Xing et al. (2024). This phenomenon persists regardless of architectural modifications, as global alteioon mechanisms tend to dilute important local relationships, leading to suboptimal learning. Our primary objective in this paper is to explicitly mitigate this issue through carefully designed training strategics rather than architectural alterations. The superior performance observed in our experimental results is a direct consequence of effectively alleviating this issue, ensuring a more balanced integration of local and global information in Graph Transformers.
3
Problem: Over-Globalising of Transformers in Graphs
3.1
Notations
We are given an input graph denoted as G = EV, where the set of vertices V contains n nodes and the set of edges & contains mn edges. The edges of the graph are encoded by an adjacency matrix A = [Awa] E {0, 10,1) 1 where Auv = 1 if there exists an edge from vertex u to v, and 0 otherwise. We use d, to denote the degree of each vertex u E V, so d, = =nev Aou- Often independent of the structural information in the edges of &, we are also given imput vertex features encoded in the matrix X = [xx] E Raxd, where X, is a dimensional leature vector of vertex u.
Let the number of output features for a general task be In the vertex classification task, vertices are labelled from label set denoted y. Vertex labels are represented with a label matrix Y = [y,] E R"*e, where y. is the one-hot label of vertex Let the classes or labels be ,..... We denote matrices with bold uppercase letters and vectors with bold lowercase letters.
Transformers on graphs allow each verlex in a graph to atlend to all other vertices through their global self-attention mechanism as follows:
QKT
Attn(H (H) Softmax
V,
h
(1)
Q HW q K HW K. V HWv.
where H E Baxh denotes the hidden representation matrix and h is the hidden representation dimension. We, WK, Wv E gixh are trainable query, key, and value weight matrices of linear projection layers. The attention score matrix is Å = Softmax
QK"
E [0, 1]=x", containing the attention scores of all vertex
VA
pairs. Let Our be the element of Å representing the attention score between vertex u and v. Transformers graphs update vertex representations globally by multiplying the attention score matrix À with the vertex representation matrix V.
3.2 Graph Property: k-hop Homophily
primarily capture the overall tendency of vertices to share the same label, they fail to provide insights into the varying label similarities across different hops In the context of over-globalising, il is crucial lo identify al which hop distances neighbours contribute the most useful information for label inference. To address this, we introduce the k-hop homophily metric, which systematically quantifics the label consistency across different neighborhood ranges. This allows visualise and analyse how attention should idcally be distributed in Graph Transformers, ensuring that models do not excessively focus on distant vertices the cost of local structures.
While existing homophily metrics Mironov and Prokhorenkova (024
3

---

Published in Transactions on Machine Learning Research (05/2025)
To demonstrate the over-globalising issue of transformers graph datasets, consider two types of graph
datasets: heterophilic and homophilic datasets. To measure the homophily level of any type of graph dataset, we adopt the "adjusted homophily" metric of prior work Platonov et al. (2023a bJ. It is defined
as = Bedge
where Medge is the edge homophily defined as Nedde = H(u.)e v.=w]l El
WO d2/(2181)2
"Ajuusted" homophily is a refined measure that captures the tendency of vertices in graph to connect with vertices that have the same label, while adjusting for biascs such as class imbalances and differences in the number of vertices per class Platonov et al. [2023a] b).
We extend the definition to incorporate vertices in the k-hop neighbourhood. We define de as the number of unique vertices exactly k-hops away from the vertex u in the graph g and & as the set of all paths connecting two vertices of length k. We propose the k-hop homophily as follows:
Redge,k -ii= Evans / (2(Ex))
Kiu o) E Ek.
yo = yo
Thk 1 2j=1 Eoy.,, (2|
nedge,
(2)
[&
Notice that when k == 1, we get adjusted homophily, i.e., 7n = 17 and Medge.1 = Medge- has the following unique advantages in terms of the interpretation of its value:
The proposed metric
When mh > O, it means that vertices that are k hops away are more likely to share the same label Ihan would be expected by chance.
Th = indicates that there is no specific tendency for vertices at distance of ls to either be similar or dissimilar in terms of their labels.
When T < 0, it means that vertices that are hops away exhibit heterophilous tendencies, meaning that vertices at a distance of l are more likely to have different labels than would be expected in a random graph.
Data-driven Analysis To clarify the nuanced interpretation of the proposed metric, we analyse sev- eral graph datasets. We examine six datasets in this section. Please see the appendix Section A.4 for more datasets. These include three heterophilic datasets: amazon-ratings, minesweeper, and roman-emping pire Platonov et al.] [2023a b). The remaining three are homophilic datascts: amazon-photo, coauthor-cs Shchur et al. 2018), and wikies Mernyei and Cangea (2020). It is important to note that previous research Xing 2024) has examined over globbaliiiiiing with respect to homophily using values between 0 and with no specific interpretation for the value of 0.5. In contrast, our proposed k-hop homophily metric takes on values between -1 and +1 with clear interpretations for positive, zero, and negative values.
et al.
Figure 1 shows the proposed k-hop homophily values on the datasets for varying k from 1 Firstly, across all datasets, the k-hop homophily score shows a downward trend from k = onwards, suggesting that vertices farther away are less likely to share the same label. More important, the downward trend levels off at zero, with 7/ < 0 observed only once (in the roman-empire dataset at k = 1). This indicates no specific tendency for vertices at a distance of large k to be either similar or dissimilar in terms of their labels.
Interestingly, the k-hop homophily values show a peak at = 2 in heterophilic datasets and at = 1 in homophilic datasets. This suggests that in heterophilic datasets, direct neighbours are more likely to have different labels (heterophily), but socond neighbours are more likely have similar labels (homophily). In homophilic graphs, label similarity is strongest. locally. Direct neighbours are highly likely to share the same label, but as move farther, label similarity drops off.
The proposed k-hop homophily metric effectively captures the main differences between homophilic and heterophilic graph datasets in this paper, offering a nuanced understanding of label dynamics. Specifically, in homophilic graphs, the metric ezhibits a consistent downward trend from the first hop, reflecting the diminishing influence of localized label similarity as neighborhoods expand. In contrast, the three heterophilic graphs considered demonstrate an initial upward trend, followed by downward trajectory as demonstrated in Part A of Figure] 1
4

---

Published in Transactions on Machine Learning Research (05/2025)
Heterophilic Graphs
Heterophilic Graphs
Distribution of Attn Distribution of Attn-k
k-hop Homophily
amazon-ratings
0.2
amagsn-rating minesooeper
minesweeper
0.1
roman-empire
0.1
0.0
2
4
6
8
Hop Size k
2
4
6
8
Hop Size
Homophilic Graphs
Homophilic Graphs
k-hop Homophily
amazon amazon-photo photo coauthor-cs
0.2
amazon-pheta coaitoores
0.5
wikics
0.1
0.0
2
0.0
2
4
6 Hop Size k
8
Hop Size k
A. k-hop homophily across hop sizes k.
B. Attn-k Distribution in NodeFormer vs. k.
Figure (Best seen in colour) Empirical observations to demonstrate the over-globalising issue het- erophilic and homophilic graphs. The figures show k-hop homophily scores (A) and Attn-k (B) of Node- Former Wu et al. (2022b) for hetcrophilic (top) and homophilic (bottom) datasets across varying hop sizes k. The plots highlight how homophily decreases with hop sizes, while allention is overly allocated to distant vertices, demonstrating the over-globalising issuc. Please see Section 3.2 for details.
3.3 Over-Globalising of Transformers on Graphs
In this section, we describe the issue over-globalising by examining the distribution of allention scores aue in the matrix À of a well-trained toaee--o-thheartt Transformer on graphs Wu et al. (002b)). We observed that vanilla transformers and most other well-trained transformers on graphs with globabl self-attention mechansism followed the same trends observed for NodeFormer Wu et al. (202bb). We adopt the average attention score Attn-k of prior work Xing et al. (2024), defined as Attn-k
Evev EuEA... Onn.
Figure [ shows the visualisation of Attn-k distributions of the well-trained NodeFormer Wu et al. 2022b) the heterophilic (top right) and homophilic (bottom right) datasets. A higher Attn-k value indicates that the model focuses more on the information from the k-th hop. We expect the trends of Attn-k to be roughly similar to those of k-hop homophily values (shown correspondingly on the left). However, the situation is different than expected, as the observed results do not align with our expectations.
To begin with, the Attn-k value is lowest at k = 1 across all datasets, indicating that there is minimal attention given to the one-hop neighbouring vertices. The observation that Attn nearly zero homophilic datasets, rises sharply to a peak at k = 2, and then shows a slight decline suggests tendency towards globalloaa when compared to the related k-hop homophily values. More importantly, datasets, the variation is much more erratic with values of k = 5 (minesweeper), and h 6 (amazon ralings and roman-empire) getting very high Attn-k values, suggesting much more severe form of over-globalising.
heterophilic
Why NodeFormer Was Selected. NodcFormer's design Wu et al. (022bb represents a statc-of-the-it approach to atlention mechanisms in graph transformers, offering scalab scalability and efficiency, which makes it a relevant choice for analyzing attention score distribution trends. Although trivial non non-graph transformers exhibit over-globalising, it noteworthy- not immodiately apparent- that even statc-of-the-art methods are affected by this issue. Selecting model that yields unsatisfactory results (please see Tables and 2 on datasets makes over-globalising obvious in simple attention score visualization, visible to the naked eye.
5

---

Published in Transactions on Machine Learning Research (05/2025)
Local Module
C 6) (1 (f. e)
Global Module
35
CLF
Z' (AAX))
2 A,
WLF
Local Module
Global Module
5
1
(a)
z' X)
2 Del (
Figure 2: (Best seen colour) Overview of Collaborative and Warm-up Training Strategics in LocalFormer. In the CollaboratveeLoalFFonerr (CLF) approach, the local and global modules are trained simultaneously, mutually benefiting from each other's learning through collaborative loss Lco. In the WarmupLocalFormer (WLF) approach, the local module is trained independently for the initial epochs, followed by the integra- tion of global information from the global module to refine vertex representations, progressively balancing local and global insights. Please see Section for details.
4 LocalFormer: Enabling Localised Training in Global Transformers
Considering the findings from the previous section, tackling the over-globalising issue necessitates a balanced strategy that thoughtfully combines both local and global information, ensuring that distant relationships are not given undue priority.
Two Schemes for Localised Training
The proposed LocalFormer integrates a local module Jo(AXX) (e.g., sparse attention) to address over- globalising in transformers on graphs. Let ge represent the global transformer function parameterised by O. Unlike the vanilla transformer, which uses only X as input, graph transformers with a global self-attention mechanism such as NodcFormer Wu et al. (202bb) utilise both the adjacency matrix A and vertex features X. We denote this global module as ge A, X). It is crucial to note that the local module fo, and the global module ge, do not share any information at the hidden layers, Consequently, there is no parameter sharing between f and e.
The outputs of the local and global modules are integrated at the loss function level, using the collaborative loss L.o. This integration allows both modules to independently learn complementary representations while contributing to the overall optimisation objective.
Let the output features of J and g be z [2/] and Z [2g]- We investigate two training schemnes to mitigate the over-globalising of ge by incorporating fo- Since f is a local module, we refer to this process as "localised training".
Scheme 1: Collaborative Training In this setup, two models are simultaneously trained on the same training data to improve generalisation capabilities [Song and Chai (2018). Within the context of graph machine learning, we train the local f and the global g in a way that they can benefit from cach other's learning process. More formally, the collaborative training setup considers two loss functions: a task-specific loss (f. θ) and collaborative loss (0, ④) that is designed to encourage mutual supervision between f and g. Mathematically,
Z' fo X) RaxC Z 9o R
(3)
0 = arg min o aLask + (1 a)

---

Published in Transactions on Machine Learning Research (05/2025)
where is hyperparameter used to balance the contributions of Ltask and Loo. We call this training strategy with the local f and the global g, "CollaboraaivelocaPPoooer (CLF).
Intuition and Details of the Collaborative Loss Function. Firstly in Equation B there is local module So and global module ge trained collaboritively. Intuitively, the collaborative loss Cco ensures that the two modules communicate with each other by exchanging their expectations about unlabelled data. By considering the confidence certainty that one module places in its predictions, the other module can reinforce its own learning approach. Mathematically, the loss function Lco can be broken down into two terms as follows:
= = (0, +
The purpose is to create two-way communication: f learns from g and g learns from f. The first term represents a learning mechanism where the local module f encouraged to align its predictions with those of the global module 9, particularly for unlabelled verlices. Intuitively, this means that module g acts as teacher, providing soft predictions for vertices where labels are unavailable. The local module f then adjusts its outputs to be more consistent with these predictions. Mathematically, the first term is given by:
10.0~1(0,0) = -Bgg, log(z!).
Here, Vy denotes the set of unlabelled vertices and we consider each vertex v E Vy. The subscript g + f indicates that module g is guiding module f. The term z the soft prediction made by module g for an unlabelled vertex u. The term log(z!) is the logarithm of the prediction that module makes for the same vertex. The logarithmic term ensures that the loss is higher when ʃ siguifieantly deviates from g. pushing f to refine its understanding in way that incorporates the global perspective while maintaining local structural awareness. The other term has similar form as follows:
1g = -E V log(2g).
Intuitively, this term works by having module g adjust its predictions a way that is consistent with the confidence provided by module f. This helps module g refine its predictions based on what module f predicts about the data. The term Leask in Equation represents the primary objective function that ensures both and the global module ge learn to perform the main predictive task effectively. It is typically defined based on supervised learning criteria, such as cross-entropy loss for classification or mean squared error for regression, guiding the models to optimise their outputs towards the ground-truth labels.
the local module fo
Theorem 4.1. CoBFormer Xing et al. 2024) mitigate over- ner-globalising an instonce of our CLF.
Proof. The specific instantiation is obtained by setting So to the GCN module Kipf and Welling 2017 and ge to the Bi-level Global Attention (BGA) module Xing et al. (2024). In the task of vertex classification, the set of vertices V is partitioned into labelled vertices and unlabelled vertices, so, V = Vz U Vy. The task-specific loss, Lrask is typically cross-entropy, Lrosk θ) = (Ey,.vev, log(z!) + Ey..veve log(z?)) The collaborative loss function is designed to encourage mutual supervision between f and g on the unlablled set Vo, given by (0. = (E (Eg, log(z!) + ver log(z)))
Scheme 2: Warm-up Training This scheme is inspired from techniques that gradually increase the learning rate, starting from a very small value Vaswani et al. (2017); Kalra and Barkeshli (2024). The learning rate slowly reaches a desired level over several iterations or epochs during a "warm-up" phase.
Based on the strong local tendencies of k-hop homophily observed in Figure [ we propose using only the local module fo for the initial warm-up period of 7 epochs. Afterwards, we refine the vertex representations from the local module fo using ge in sequential manner. Mathematically, letting t to be the training epoch

---

Published in Transactions on Machine Learning Research (05/2025)
Table I: Averaged vertex classification results over 10 runs on heterophilic datasets for roman-empire and amazon- -aatinns and ROC AUC is reported for minesweeper, tolokers, and ques- tions. We highlight the first and the second best results on each dataset.
Accuracy is reported
roman-empire
amazon-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
DiFForrer
79.10 0.32
47.84 0.65
90.89 + 0.58
83.57
72.15 1.31
GOAT
71.59 +: 1.25
44.61 + 0.50
81.09 + 1.02
83.11 1.11:100 1.04
75.76 = 1.66
SGFormer
88.62 0.50
53.06 0.29
90.30
83.33 0.68
73.54 + 0.65
CobFormer-G
88.27 + 0.37
52.79 0.30
89.97 + 0.49
83.00 + 0.56
73.23 - 0.59
CobFormer-TT
88.56 + 0.45
53.04 0.50
90.30 + 0.57
83.36 + 0.52
73.48 - 0.44
CLF (Ours)
91.36 + 0.39
53.54 + 0.24
96.20 + 0.68
$4.09 + 0.40
77.23 + 0.66
WLF (Ours)
91.71 + 0.68
54.02 0.40
96.53 0.64
84.34 0.67
77.52 + 0.55
of the optimisation algorithm and the vertex classification task to be VCT.
z' = So(A, TRx
Z (,, Z') TRax 0" "" arg min Liasks
8,0
Liask (0) (task(0, if
i
VCT { Linnk (0) = =1y,,vv log(z!) Clast (6, Q) E ey log(z!) if
if
(4)
We refer to this training strategy WLF, which stands for Faameerrl with a warm-up period of t epochs. Naturally, WLF with t 0 corresponds to the typical sequential model where the vertex representations from the local module fo are sequentially refined by ge to produce the output Z
Please see Appendix Section for an analysis of computational complexity.
5 Experiments
We thoroughly assess LocalFormer to mitigate globbaliigi by comparing it with the latest graph trans- former models on both homophilic and heterophilic graphs. It is important to note that our primary emphasis in the paper is to mitigate over-globalising and not to achieve state-of-the-e on the datasets we evaluated. fact, because over-globalising is a phenomenon specific to transformers and not to neighbourhood message- passing models, we chose not to include GNN basclines in some of our analysis (e.g., comparison of test accuracy datasets). Additionally, ponents of LocalFormer. We also analyse the attention score distribution of LocalFormer to demonstrate its capability in miligaling over-globalising.
conduct ablation studies to evaluate the effectiveness of all the
5.1 Performance Comparison with Existing Transformers
We choose a total of ten datasets for our evaluation. Five of them are the homophilic graphs Computer, Photo, CS, Physics [Shchur et al. (2018), and WikiCS Mernyei and Cangca (2020). The remaining five are the heterophilic graphs roman-empire, amazon--arings, minesweeper, tolokers, and questions Platonov et al.) (2023 b). We utilise the public splits from prior work for these datasets. These splits are divided into training, validation, and test sets, maintaining a 50%:25%:25% ratio. Please Appendix Section A.1 for more details on the datasets.
Baselines. We compare our proposed methods with eight transformer baselines: GraphGPS Rampasek ct al. (2022b). NAGphormer Chen al. (2023). Exphormer Shirzad et al. (2023). NodeFormer
Wu et al. (2024), and
(2022b), FoFFormer Wu et (2023b), GOAT Kong et (2023), CoBFormer Xing al.
SGFormer Wu et al. (2023a). Please Section A.2 for details the hyperparameters.
8

---

Published in Transactions on Machine Learning Research (05/2025)
Table 2: Averaged vertex classification accuracy (%) + std over 10 runs on homophilic datasets. We highlight the first and the second best results on each dataset.
Computer
Photo
CS
Physics
WikiCS
GraphGPS
91.19 1 0.54
95.06 0.13
93.93 + 0.12
97.12 + 0.19
78.66 1 0.49
NAGphormer
91.22 1 0.14
95.49 1 0.11
95.75 1 0.09
97.34 0.03
77.16 + 0.72
Exphormer
91.47 1 0.17
95.35 1 0.22
94.93 1 0.01
96.89 + 0.09
78.54 1 0.49
NodeFormer
86.98 + 0.62
93.46 + 0.35
15.64:00 0.22
96.45 + 0.28
74.73 1 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 0.38
96.24 = 0.24
77.00 + 0.77
SGFormer
01.70
94.85 0.45
94.57 0.40
96.40 = 0.52
73.23 + 0.58
CoBFormer-G
91.53 0.24
94.65 + 0.22
94.35 0.40
96.16 = 0.54
73.02 = 0.64
CoBFormer-T
91.81 + 0.33
94.61 0.22
94.39 + 0.27
96.57 + 0.68
73.97 + 0.76
CLF (Ours)
92.18 + 0.29
95.46
0.20
95.53
0.16
97.02 + 0.18
78.74 + 0.17
WLF (Ours)
92.69 + 0.41
95.63 0.14
95.98 + 0.35
97.25 + 0.15
79.04 + 0.44
We report the best models across hyperparameters in Section A.2 CLF generates two predictions: from the local module f and another from the global module g. We present the superior result of the two. Please see Appendix and for an analysis of CLF's two modules with different a.
Performance on Heterophilic Graphs. The empirical results on heterophilic datasets, shown Table ! compare the performance of various graph transformer models on vertex classification tasks. The models include the proposed Collaborative LocalFormer (CLF) and Warm-up LocalFormer (WLF). The evaluation metrics are accuracy for roman-empire and amazon-ratings, and ROC AUC scores for minesweeper, tolokers, and questions.
Both CLF and WLF consistently outperform state-of-the-art graph transformer baselines across all het- erophilic datasets, with WLF showing the best performance overall, slightly ahead of CLF. This highlights LocalForrerrs s effectiveness in addressing the over-globalising issue in heterophilic graphs.
The superior performance of CLF and WLF is due their ability to balance local and global information, avoiding the problem of high attention scores being assigned to distant, often irrelevant nodes in heterophilic graphs.
The k-hop homophily plots essentially show that vertices in the 2-hop neighbourhood are the most usefuul for classification in heterophilic graphs 2-hop neighbourhoods are still local because they retain meaningful label structure around cach vertex without requiring full global attention. Our LocalFormer methods outperform previous methods because dynamically selects the most. relevant local information.
Performance on Homophilic Graphs. Table shows empirical performance on homophilic datasets. The experimental results demonstrate that FormeFormer effectively addresses the issue of over-globalising in transformers on graphs. The empirical results homophilic datasets validate the observations made earlier regarding the strong local tendencies in homophilic graphs.
Experiments on More Non-Homophilic Datasets. We conduct experiments on more non-homophilic datasets Appendix Section A.5 The WebKB datasets (Texas, Cornell, and Wisconsin) exhibit fluctuating k-hop homophily trends as shown in Figure g with values neither consistently decrcasing nor following the heterophilic pattern we previously observed (initial increase followed by decline). The Wikipedia dalasets (Chameleon, Actor, and Squirrel) present intriguing k-hop homophily patterns shown in Figure g with values fluctuating close to zero across different hop sizes.
We selected the three best-performing transformer baselines (Exphormer, SGFormer, CoBFormer) on the initial three heterophilic datasets as baselines for comparison in this new study. We found that our proposed mothods (CLF and WLF) performed competitively across all six datasets, though the performance differences were less pronounced than in the three heterophilic datasets initially examined in the paper. Please see A Appendix Section A.5 for more details.
9

---

Published in Transactions on Machine Learning Research (05/2025)
5.2
centermanne-Effcciennne Tradeoff Analysis
InformmanceEEficienee Tradeoff
Figure evaluates the performance of several graph transformer models by plotting test per- formance (in terms of ROC-AUC) against rela- tive training time on the questions dataset. The aim visualise which models strike the best balance between training efficiency and predic- tive performance. CLF and WLF both achieve strong balance, with high ROC-AUC scores and moderate relative training times compared to other models. This positions both models as strong candidates for tasks requiring fast yet re- liable performance, making them ideal for practi- cal applications where both speed and accuracy crucial. The visualisation clearly highlights their efficiency and effectiveness in comparison to other existing transformer models.
78
Test ROC-AUC questions
76
GOAT
NodeFormrr Exphormer
74
SGFormar
CoaFormer
DiFformer
72
70
NAGphormer
68
10P
10a
Relative Training Time
Figure 3: (Best seen in colour) Comparison of ROC-AUC versus relative training time on the questions dataset. Please see Section 5.2 for details.
5.3 Ablation Analyses
SOTA Baseline
Local Module (f)
Global Module (g)
WLF
roman-empire
minesweeper
amazon-photo
wikics
92
96
96.0
Accuracy
79
94
95.5
90
92
95.0
78
88
90
94.5
Figure 4: (Best seen in colour) Ablation study on the roman-empire, minesweeper (heterophilic), amazon- photo, and wikies (homophilic) datasets. The results compare the performance of the state-of-the-art (SOTA) baseline, Local Module alone, Global Module alone, and the WarmLocalFormer (WLF) method, showing how integrating both local and global information achieves superior results across different graph types. Please see Section 5.3 for details.
Ablation of Local and Global Modules Figure evaluates the impact of the Local Module, Global Module, and their combination in the WarmLocalFormer (WLF) training strategy heterophilic (roman- empire, minesweeper) and homophilic (amazon-photo, WikiCS) graphs. This ablation study supports the key claim that over-globalixing in transformers can dilute critical local information. By showing the individual contributions of both modules, it highlights the necessity of a balanced approach. The superior performance of WL.,, especially on heterophilic datasots, demonstrates how combining these modules effectively integrates fine- gra-grained, neighborhood-specin patterns with broader graph-wide context, reinforcing the efficacy of LocalFormer. Please see Appendix Figure and Figure for detailed analysis of the components of CLF.
10

---

Published in Transactions on Machine Learning Research (05/2025)
Figure 7 illustrates scenarios where both local and global modules were trained without Lco in Equation 3 They were trained with the task-specific cross-entropy loss Ltask- The CLF model, trained with aL (1-a0 (1-a)Cco Ceo. outperforms these ablated models, highlighting the critical role of Loo. Figure examines how the hyperparamoter a balances Lco for unlabelled vertices and Ltask for labelled vertices. Results indicate that a = 0.8 yields optimal performance, with a = 0.7 as a close contender.
A Allation of the Number of Warm-Up Epochs 7 S the performance of the WarmLocal- Former (WLF) method across different datasets with varying warm-up epochs (r 10, 50, 100, 200) over fixed 1000 epochs. The warm-up period allows the local module to learn independently before introducing the global module. The study demonstrates that a balanced warm-up period optimises performance by stabilising local features before integrating global information. Shorter warm-ups miss local details, while longer ones can hinder efficient global feature integration.
No Warm-up
10-epoch Warm-up
50-epoch Wammup
100-epoch Warmup
200-epoch Warm-up
roman-empire
minesweeper
amazon-photo
wikics
92
96
96.0
Accuracy
79
94
95.5
90
92
95.0
78
88
90
94.5
Figure 5: (Best seen in colour) Impact of varying the number of warm-up epochs on the accuracy of the roman- roman-empire, empire, minesweeper, amazon-photo, and WikiCS datasets. Results compare models with no warm- up, 7 = 10, r = 50, r = 100, and r = 200 warm-up epochs, illustrating the optimal balance between local and global information at different stages of training. Please see Section 5.3
5.4 Attention Score Distribution of LocalFormer Training Strategies
Figure 6 shows the Attn-k distribution plots for both CLF and WLF, validating the strategies employed by these methods in addressing the ever-globalising problem. The collaborative learning in CLF between the local and global modules is evident in the attention distribution, particularly on heterophilic datascts. CLF effectively balances between local and global attention, but it focuses more semi-distant nodes (3-5 hops), which helps capture cross-cluster relationships crucial for heterophilic graphs. The warm-up strategy of WLF allows the model to first prioritize local information and then gradually integrate global context. The smoother attention distribution across all hop sizes demonstrates the strength of this approach. The attention distributions also show how WLF mitigates the attention spikes observed in existing transformers, offering a more consistent and balanced approach to local-global integration.
The comparison between CLF and WLF highlights their distinct yet complementary strategies in overcoming the over-globalizing challenge in attention mechanisms. By emphasizing semi-distant nodes, CLF enhances the model's ability to capture nuanced relationships across clusters, which is particularly beneficial for heterophilic graphs where nodes differ significantly. In contrast, WLF's gradual integration of global context ensures a smoother transition and a more balanced attention distribution, reducing the potential for attention spikes that can cause instability the model's focus. These findings imply that leveraging both local and global contexts in balanced manner can significantly improve the model's performance on complex graph structures by addressing inherent. biases and promoting comprehensive understanding of the data.
11

---

Published in Transactions on Machine Learning Research (05/2025)
Average Attn-k in CLF
0.2
amazon-ratings minesweeper
Average Attn-k WLF
amazon-ratings minesweeper
roman-emmire
roman empire
0.1
0.1
0.0
0.0
2
6
8
2
4
6
8
Hop Size
Hop Size
Average Attn-k in CLF
Average Attn-k WLF
amazon-photo coauthor-cs wikics
amazon-phore photo
0.15
coauthor-cs
0.15
wikics
0.10
0.10
0.05
0.05
6
4
Hop Size
Hop Size
A. Attn-k Distribution in CLF.
B. Attn-k Distribution in WLF.
Figure 6: (Best seen colour) Average attention distribution of CLF and WLF across different hop sizes (1-9) 9) for heterophilic datasets (amazon-ratings, minesweeper, roman-empire) and homophilic datasets (amazon-photo, coauthor-cs, wikics). Please see Section 5.4 for details.
6 Limitations and Future Work
In conclusion, our proposed LocalFormer effectively addresses the issue of over-globalising in graph trans- formers by introducing two training strategies: collaborative training and warm-up training. This method enhances the selectivity of attention distributions, allowing vertices to prioritise local, relevant informa- tion over distant, less pertinent data on both homophilic and heterophilic data. Our paper can be further developed in several directions, particularly by addressing its current limitations.
Addressing Structural Dynamics in Graph Data: Heterophilic and more generally non- homophilic datasots can exhibit counter-intuitive positive homophily values as in Figures || and 10 which believe result. from structural factors such as localised homophilic substructures and degree heterogeneity. Investigating these sophisticated dynamics could lead to refined under- standing of graph metrics. This direction warrants further exploration.
Theoretical Understanding of Homophily Metrics: While the paper focuses overcoming the issue of over-globalising in graph transformers, future rescarch could delve into refining homophily metrics for deeper structural insights. Exploring this comprehensive theoretical analysis can offer a broader perspective on existing measures, informed by recent studies that critically assess and propose new homophily metrics Mironov and Prokhorenkova 2022)..
Mitigating Over-Globalising Specifically On Heterophilic Graph Datasets: Future work
will explore transformer architectures specifically tailored to heterophilic graphs, particularly focus- ing on the most informative 2-hop homophily, observed in Figure
Scalability: As transformer models expand to handle larger homophilic Hu et al. 2020 and het- erophilic Lim al. (2021) graphs, scalability becomes crucial. Future work will focus on developing scalable algorithms to mitigate over-globalising such sampling-based methods.
Metrics for Over-Globalising: Another key area for future work the development of quantita- tive metrics to assess the over-globalising issue in transformers with global self-attention modules.
12

---

Published in Transactions on Machine Learning Research (05/2025)
References
William L. Hamilton. Graph Representation Learning. Synthesis Lectures Artificial Intelligence and Machine Learning, 14(3)_1159, 2020.
Thomas N Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Represenlations (ICLR), 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference on Learning Representations (ICLR), 2018
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive Representation Learning On Large Graphs. In Advances in Neural Information Processing Systems (NeurIPS) 30, pages 1024-1034. Curran Associates, Inc., 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful Are Graph Neural Networks? In International Conference on Learning Representations (ICLR), 2019.
Lingfei Wu, Peng Cui, Jian Pei, and Liang Zhao. Graph Neural Networks: Foundations, Frontiers, and Applications. Springer Singapore, 2022a.
Yao Ma and Jiliang Tang. Deep Learning On Graphs. Cambridge University Press, 2020.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper Insights Into Graph Convolutional Networks for Semi- Supervised Learning. In Proceedings of the Thirly-Second Conference on Associalion for the Advancement of Artificial Intelligence (AAAI), pages 3538 3545, 2018.
Uri Alon and Eran Yahav. On the Bottleneck of Graph Neural Networks and Its Practical Implications. In International Conference on Learning Representations (ICLR), 2021.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention Is All You Need. In Advances in Neural Information Processing Systems (NeurIPS), pages 5998-6008. Curran Associates, Inc., 2017.
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampášck. Attending Graph Transformers. Transactions on Machine Learning Research, 2024. ISSN 2835-8856.
Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking Graph Transformers With Spectral Attention. In Advances in Neural Information Processing Systems Curran Associates, Inc., 2021.
(NeurIPS) 34, pages
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di Hc, Yanming Shon, and Tic- Yan Liu. Do Transformers Really Perform Badly For Graph Representation? In Advances in Neural Information Processing Systems (NeurIPS) 34, pages 28877-28888, Curran Associates, Inc., 2021.
Ladislav Rampasek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe For General, Powerful, Scalable Graph Transformer. In Advances in Neural Information Processing Systems (NeurIPS) 35, pages 14501-14515. Curran Associates, Inc., 2022a.
Qitian Wu, Wentao Zhao, Chenxiao Yang, Hengrui Zhang, Fan Nie, Haitian Jiang, Yatao Bian, and Junchi Yan. SGFormer: Simplifying and Empowering Transformers for Large-Graph Representations. In Advances in Neural Information Processing Systems (NeurIPS), pages 14753-64777 2023a.
Yujie Xing, Xiao Wang, Yibo Li, Hai Huang, and Chuan Shi. Less is More: On the OlobaGlogg Problem in Graph Transformers. In Proceedings of the 1s International Conference Machine Learning (ICML), pages 54656 54672, 2024.
Zaixi ZHANG, Qi Liu, Qingyong Hu, and Chee-Kong Lec. Hicrarchical Graph Transformer With Adaptive Node Sampling. In Advances Neural Information Processing Systems (NeurIPS) 35, pages 21171-21183. Curran Associates, Inc., 2022.
13

---

Published in Transactions on Machine Learning Research (05/2025)
Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C. Bayan Bruss, and Tom Goldstein. GOAT: A Global Transformer On Large-scale Graphs. In Proceedings of the 40th International Conference Machine Learning (ICML), pages 17375 17390, 2023.
Chuang Liu, Yibing Zhan, Xueqi Ma, Liang Ding, Dapeng Tao, Jia Wu, and Wenbin Hu. Gapformer: Graph Transformer With Graph Pooling For Node Classification. In Proceedings of the Thirty-Second International Joinl Conference on Artificial Intelligence (IJCAT), pages 2196 2205, 2023.
Dexiong Chen, Leslie O'Bray, and Karsten Borgwardt. Structure- Transformer For Graph Represen- tation Learning. In Proceedings of the 39th International Conference on Machine Learning (ICML), pages 3469-3489, 2022.
Zhanghao Wu, Paras Jain, Matthow Wright, Azalia Mirhoscini, Joseph E Gonzalez, and Ion Stoica. Repre- senting Long-Range Context For Graph Neural Networks With Global Attention. In Advances in Newral Information Processing Systems (NeurIPS) 94, pages 13266-13279. Curran Associates, Inc., 2021.
Justin Gilmer, Samuel S. Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural Message Passing For Quanturn Chemistry. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 1663-122,, 2017.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra, Beyond Homophily In Graph Neural Networks: Current Limitations And Effective Designs. In Advances in Neural Information Processing Systems (NeurIPS) 33, pages 7793 7804. Curran Associates, Inc., 2020.
Kun Wang, Guibin Zhang, Xinnan Zhang, Junfeng Fang, Xun Wu, Guohao Li, Shirui Pan, Wei Huang, and Yuxuan Liang. The Heterophilic Snowflake Hypothesis: Training And Empowering GNNs For Heterophilic Graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD), pages 3164-3175, 2024a.
Langzhang Liang, Sunwoo Kim, Kijung Shin, Zenglin Xu, Shirui Pan, and Yuan Qi. Sign Is Not A Remedy: Molliseetto-Muulisse Message Passing For Learning On Heterophilic Graphs. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages
2024.
Junfu Wang, Yuanfang Guo, Liang Yang, and Yunhong Wang. Understanding Heterophily For Graph Noural Networks. In Proceedings of the 4 1sst International Conference on Machine Learning (ICML), pages 50489 50529, 2024b.
Zhishi Yu, Bin Feng, Dongxiao He, Zizhen Wang, Yuxiao Huang, and Zhiyong Feng. LG-GNN: Local-Global Adaptive Graph Neural Network For Modeling Both Homophily And Heterophily. In Proceedings of the Thirty- Third International Joint Conference on Artificial Intelligence (IJCAT), pages
2024.
Moonjcong Park, Jacseung Hoo, and Dongwoo Kim. Mitigating Oversmoothing Through Reverse Process Of GNNs For Heterophilic Graphs. In Proceedings of the 41st International Conference on Machine Learning (ICML), pages 39667-3999 39681, 2024.
Qitian Wu, Wentao Zhao, Zenan Li, David P Wipf, and Junchi Yan. NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification. In Advances in Neural Information Processing Systems (NeurIPS) 35, pages 27387-27400 Curran Associates, Inc., 2022b.
Ahsan Shelzad, Feng Xia, Shagufta Abid, Ciyuan Peng, Shuo Yu, Dongyu Zhang, and Karin Verspoor. Graph Transformers: A Survey. arXiu preprint 00700:4477009771, 2024.
Mikhail Mironov and Liudmila Prokhorenkova. Revisiting Graph Homophily Measures. In The Third Learn- ing on Graphs Conference (LoG), 2024.
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. Critical Look At Evaluation Of GNNs Under Heterophily: Are We Really Making Progress? In International Conference on Learning Represendations (ICLR), 2023a.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. Characterizing Graph Datasets For Node Classification: Homophiy--Httroohiiy Dichotomy And Beyond. In Advances in Newral Information Processing Systems (NewrIPS), pages 523 548, 2023b.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls Of Graph Neural Network Evaluation. In Relational Represenlation Learning Workshop, R2T, 2018.
Péter Mernyei and Cätälina Cangea. Wiki-CS: A Wikipedia-Based Benchmark For Graph Neural Networks. Graph Representation Learning and Beyond workshop. 2020.
Guocong Song and Wei Chai Collaborative Learning For Deep Neural Networks. In Advances in Newral Information Processing Systems (NeurIPS), pages 1837-1846. Curran Associates, Inc., 2018.
Dayal Singh Kalra and Maissam Barkeshli. Why Warmup the Learning Rate? Underlying Mechanisms And Improvements. arXiv preprint or Xiw::240600440, 2024.
Ladislav Rampasek, Mikhail Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe For A General, Powerful, Scalable Graph Transformer. In Advances in Neural Information Processing Systems (NeurIPS) 95, pages 14501-14515. Curran Associates, Inc., 2022b.
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. NAGphormer: A Tokenized Graph Transformer For Node Classification In Large Graphs. In International Conference on Learning Representations (ICLR), 2023.
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse Transformers For Graphs. In Proceedings of the 40th International Conference on Machine Learning (ICML), pages 31613 31632, 2023.
Qitian Wu, Chenxiao Yang, Wentao Zhao, Yixuan He, David Wipf, and Junchi Yan. DIFFormer: Scalable (Graph) Transformers Induced By Energy Constrained Diffusion. In International Conference on Learning Representations (ICLR), 2023b.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In Advances in Newral Information Processing Systems (NewrIPS) 33, pages 22118 22133. Curran Associates, Inc., 2020.
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large Scale Learning on Nom-hoooph Graphs: New Benchmarks and Strong Simple Methods. In Advances in Neural Information Processing Systems (NewrIPS) 34, pages 20887 20902. Curran Associates, Inc., 2021.
Mark Craven, Dan DiPasquo, Dayne Freitag, Andrew McCallum, Tom Mitchell, Kamal Nigam, and Scán Slattery. Learning To Construct Knowledge Bases From The World Wide Web. Artif. Intell., pages 69-113, 2000.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang, Geom-(gen): Geometric Graph Convolutional Networks. In International Conference on Learning Representations (ICLR), 2020.
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social Inffuence Analysis In Largo-Scale Networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 807-816, 2009.
Benedek Rozemberezki, Carl Allen, Rik Sarkar, and xx Thilo Gross, Multi-Scale Attributed Node Embed- ding. Journal of Complez Networks, pages 1-22, 2021.
15

---

Published in Transactions on Machine Learning Research (05/2025)
A Appendix
A.1 Dataset Details
Table 3 presents the statistics for all 10 datasets utilised in our experiments. The homophily score is calculated using an existing metric Lim et al. (2021), where a higher score indicates greater homophily.
Train/ Saain//alid/eeoee splits. For the Computer, Photo, CS, and Physics datascts, we follow the standard practice randomly splitting the vertices into training (60%), validation (20%), and lest (20%) sets Chen
al. (2023); Shirzad al. (2023). For the other datasets, we use the official splits provided in previous
studies Platonov al. 2023a
Table 3: Statistics of datasets used in our experiments.
Dataset
Type
Homophily Score
Nodes
Edges
Classes
Features
Computer
Homophily
0.700
13, 752
245, 861
10
767
Photo
Homophily
0.772
7, 650
119, 081
8
745
CS
Homophily
0.755
18, 333
81, 894
15
6,805
Physics
Homophily
0.847
34, 493
247, 962
5
8, 4.415
WikiCS
Homophily
0.568
11,
216, 123
10
300
roman-cmmirr
Heterophily
0.023
22,
32, 927
18
amnzon-ralings
Heterophily
0.127
24.492
93, 050
5
300
mineswoeper
Heterophily
0.009
10. 000
39, 402
7
tolokers
Heterophily
0.187
11. 758
519, 000
2
10
questions
Heterophily
0.072
48, 921
153, 540
A.2 Hyperparameter Details
For all models, including our proposed model and the baseline models, we tune the hyperparameters using a grid search approach. The hyperparameter values that yield the best performance on the validation set are selected.
GraphGPS Rampasek et al. (2022b). We choose GAT the MPNN layer type and Performer as the global attention layer type. We set the number of layers to 2, the number of heads to 8, the hidden dimension to 64, and the number of epochs to 2000. We perform herrparameeeer tuning on the learning rate from {10- x 10-3,, and the dropout rate from {0.0, 0.1, 0.2, 0.3, 0.4, 0.5}.
NAGphormer Chen et al. (2023). We set the hidden dimension to 512, the learning rate to 0.001, the batch size to 2000, and the number of epochs to 500. We perform hyperparameter tuning on the number of layers from {1, 2, 3), the number of heads from (1,8), the number of hops from {3, 7, 10), and the dropout rate from (0.0, 0.1, 0.2, 0.3, 0.4, 0.5).
Exphormer Shirzad et al. (0023 We choose GAT as the local model and Exphormer as the global model. We set the number of epochs to 2000 and the number of heads to 8. We perform hyperparameter tuning on the learning rate from f10--,10 10-3), the number of layers from {2, 4}, the hidden dimension form [64, 80, 96), and the dropout rate from 0.1,0.1,,.2.. 0.3, 0.5.
NodcFormer Wu al. (2022b). We set the number of epochs 2000. Additionally, we per- form hyperparameter tuning the learning rate from {10-4 10-3 10-2), the number of layers from 3), the hidden dimension from {32, 64, 128), the number of heads from {1,4], M from (30,50), K from (5, 10), rb order from {1,2}, the dropout rate from f0.0, 0.3). and the temperature 7 from {0.10, 0.15, 0.20, 0.25, 0.30, 0.40, 0.50).
DIFFormer Wu et al. (2023b). We use the "simple" kernel type. We perform hyperparameter tuning on the learning rate from {10- 10-3, 10-3100-7 10-2), the number of epochs from (500, 2000}. the number of layers from {2, 3), the hidden dimension form (64, 128), the number of heads from {1. (1,8). from (0.1, 0.3). and the dropout rate from (0.0, 0.2, 0.3, 0.5).
16

---

Published in Transactions on Machine Learning Research (05/2025)
Table 4: Hyperparameters of LocalFormer per dataset.
Warm-up Epochs
Local-to-Globe Epochs
Tocal Layers
Global Layers
Dropout
Computer
200
1000
Photo
100
1000
7
2
0.7
CS
100
1500
2
Physics
100
1500
5
4
0.5
WikiCS
100
1000
2
0.5
roman-empire
100
2500
10
2
0.3
amazon-ratings
200
2500
10
1
0.3
minesweeper
100
2000
10
3
0.3
tolokers
100
800
2
0.5
questions
200
1500
5 3
0.2
GOAT Kong et al. (2023). We set the "conv type" to "full", the number of layers to (fixed by GOAT); the number of epochs to 200, the number of centroids to 4096, the hidden dimension to 256, the dropout of feed forward layers to 0.5, and the batch size to 1024. We perform hyperparameter tuning on the learning from {10 10-3 10-2), the global dimension from {128, 256}, and the attention dropout rate from (0.0, 0.2, 0.3, 0.4, 0.5).
SGFormer Wu et al.
(2023a). We perform tuning the learning rate in {0.001, 0.005, 0.01, 0.05, 0.1), 10 4,5 x 10 10-3 11-03.10-2 1000). hidden size within {32, 64, 128, 256), dropout within {0, 00,0.2,033 0.3, 0.5), and the number of layers from 21.
weight decay from {10
perform hyperparameter tuning on the learning rate from the set x5x 1101,1000000 1,,00,5,,0000 10 10 2,5 2,5x x 10 10-2), weight decay of the GCN module from {10-4.5 x 10 10 10-3, 10-3, 10-3,10-20 19,10-2),, 2), weight decay of the BGA module from {10-5, 1,05,,5 x 10 5, 10-4, 5 10 1.10-3 100-3, number of clus- ters within {80,90 96, 112, 128, 144, 160, 192, 224, 256), the loss balancing parameter in {0.9, 0.8, 0.7) and the lemperature from {0.9, 0.7, 0.5, 0.3).
CoBFormer Xing et al. (0024).
CLF. The hyperparameters are the same as the CoBFormer model. The main difference is that the local module fo is a 10-layer GAT model with 8 attention heads.
WLF. The local module So contains GAT layers Veličković et al. (0018) with 8 attention heads. The other hyperparameters are shown in Table 4
Justification of the Choices of the Modules. GAT Veličković (2018) is employed as the lo- cal module due to its reliability, while BilevelGloballAttentioo (BGA) Xing al. (2024) advanced mechanism designed to extract global information.
These choices are supported by comprehensive real-world experiments and ablation studies in the paper. In particular, Figure g explores the effects of training GAT and BGA individually. The results highlight that the novel WarmLocalFoorer (WLF) outperforms the use of GAT and BGA trained independently as standalone models. In WLF, a 'warm-up' phase is incorporated that focuses exclusively on GAT followed by a sequential phase of refining GAT embeddings with BGA.
Figure shows that CollaborativeLocallloooo independently of each other. CLF also oulperforms the CoBPormer baseline [3], which combines GCN and BGA with a collaborative loss function. Experiments on heterophilic (Table 1) and homophilic datasets (Table 2) confirm that both WLF and CLF are more effective than CoBFormer, justifying the choice of using GAT and BGA in LocalFormer.
(CLF) performs more effectively than GAT and BGA trained
A.3 Computational Complexity Analysis.
Given graph with vertices and edges, suppose the hidden dimension is d &
17

---

Published in Transactions on Machine Learning Research (05/2025)
Complexity of the Local Module The local attention module fa, which is responsible for local infor- mation aggregation, has complexity of O(md + nd²). This breakdown can be understood as:
((md): This term arises from the need to process each edge the graph, considering the hidden dimensions. Every edge contributes d-dimensional information during aggregation. We assumne that the number of hidden layers is a constant (i.c. independent of other variables such as d,
O(nd²): This term is introduced by the ferd-forward transformations applied to each vertex in the graph. We assume that the number of input dimensions and the number of output dimensions of the feed-forward layer is at most d.
Complexity of the Global Module Without any modifications, a standard transformer's global atten- tion mechanism has a complexity of O(n²d), which quadratic in the number of vertices. This scaling can become prohibitive for large graphs, especially when is very large. To address the scalability issues, LocalFormer leverages the kernel trick (as used in NodeFormer Wu et al. (2022b)) linearise the global attention computation. This reduces the global attention complexity O(nd)), avoiding the quadratic term with respect to
Kernel Trick: This trick approximates the softmax attention, which usually requires computing pair- wise attention scores between all nodes, resulting On²²) operations. By applying kernel methods, LocalFormer can bypass the nced for pairwise comparisons, achieving a linear approximation of the atlention mechanism.
Complexity of Baselines All baseline transformers considered in this work use linear attention mecha- nisms. Consequently, the complexity O(nd)) and hence is not quadratic in n.
A.4
Ablation on Collaborativelocalformeer (CLF)
SOTA Baseline
Local Module
Global Module
CLF
roman-empire
minesweeper
amazon-photo
wikics
92
79.5
96
96.0
79.0
Accuracy
94
95.5
90
78.5
92
95.0
78.0
88
90
94.5
Figure 7: (Best seen in colour) Ablation study comparing the performance of state-of-the-art (SOTA) base- line, Local Module (fe), Global Module (ge), and CLF. The local and global modules are trained indepen- dently. CLF is trained collaboratively, and we report the better-performing result.
Figure 7 illustrates the ablation study on the local and global modules in CLF. The Local Module achieves high accuracy on homophilic datasets like amazon-pholo and wikies, where local information is critical. How- ever, on heterophilic datasets like roman-empire and minesweeper, the Global Module more competitive, emphasizing the importance of global context. The CLF model outperforms both individual modules across all datasets. highlighting the advantage of combining local and global insights for better overall accuracy. This demonstrates the model's flexibility and robustness in handling diverse data characteristics. Moreover,
18

---

Published in Transactions on Machine Learning Research (05/2025)
the integration of both modules allows the CLF model to adapt dynamically to varying dataset properties, which can be vantageous in real-world applications where dataset homophily and heterophily can fluctuate.
CLF-f with alpha=0.8
CLF-g with alpha=0.8
CLF-f with alpha=0.7
CLF-g with alpha=0.7
roman-empire
minesweeper
amazon-photo
wikics
92
97
79.5
96.0
79.0
Accuracy
95.5
96
91
78.5
95.0
78.0
90
95
94.5
Figure 8: (Best seen in colour) Impact, test accuracy, of varying the balancing parameter in (0.7, 0.8} CLF-f (i.c., local information from fo) and CLF-g (global information from ge). Note that when two models share the same a, they were trained collaboratively.
Figure 8 shows the effect of for the performance of CLF. For heterophilic datasets like roman-empire and minesweeper, using = 0.8 leads to slightly better performance, suggesting that emphasising the global module is beneficial for these datasets. For homophilic datasets like amazon-photo and wikics, both a values yield similar results. These findings indicate that the parameter a crucial in tuning the balance between local and global information, helping optimize the model for specific dataset characteristics. This adaptability underscores the utility of CLF in various contexts, as it can be finely adjusted leverage the most relevant information type for improved accuracy and performance case- caso-by-case by-case basis.
A.5
Experiments More Non-Homophilic Datasets
A.5.1
Experiments WebKB Datasets
WebKB Graphs
k-hop Homophily
0.4
Texas
Cornell
Wisconsin
Comell Wisconsin
0.2
Exphormer
77.78 + 2.45
76.06 3.83
77.77 + 2.62
SGFormer
76.15 1.99
74.97 4.31
78.79 2.89
0.0
CoBFormer
76.92 + 2.51
76.02 + 4.43
77.69 + 1.93
-0.2
CLF (Ours)
77.32 1 2.53
76.31 1 3.84
78.01 2.03
WLF (Ours)
77.86 + 2.48
76.27 3.91
78.62 1.97
2
4 Hop Size
Table 5: Averaged vertex classification accuracy over runs on WebKB datasets. We highlight the first. and second best results on each dataset.
Figure 9: (Best seen in colour) The k-hop ho- mophily metric for WebKB datasets exhibits fluctuating trends.
In this section, we report experimental results on more datasets.
WebKB A dataset of web pages gathered by Carnegic Mellon University Craven et al. (2000) from the computer science departments of various universities. We focus on three subsets: Cornell, Texas, and Wisconsin. In these subsets, each vertex represents web page and edges represent hyperlinks between
19

---

Published in Transactions on Machine Learning Research (05/2025)
them. The features of each vertex are represented using the bag-of-words model of the web pages' content. These web pages are manually classified into five categories: student, project, course, staff, and faculty.
Analysis of k-hop Homophily Figure g shows k-hop homophily values across varying k on the three WebKB datasets. The k-hop homophily trends for the WebKB datasets (Texas, Cornell, Wisconsin) reveal a complex structural composition, diverging from traditional homophilic and strongly heterophilic behaviours.
Unlike homophilic graphs, where label similarity steadily decreases as neighborhood size expands, these datasets exhibit a more erratic pattern. Specifically, k-hop homophily does not show a monotonic decline but rather fluctuates across different hop distances. This suggests that local label similarity may be preserved within small substructures while connectivity beyond these regions introduces greater label diversity.
Comparod to strongly hetcrophilic graphs, which typically display initial increase in k-hop homophily followed by a subsequent decline, the WebKB datasets do not consistently follow this pattern. The three WebKB datasets do not exhibit strong homophily, but their label similarity dynamics suggest mixed or weakly heterophilic structure.
Experimental Results We closely follow the experimental setup of prior work Pei et al. soaniin-vvaiddation-eeen split ratios. The classification performance of our proposed methods, CLF and WLF, is evaluated against the three best tranasformer baselines (Exphormer, SGFormer, and CoBFormer) on the WebKB datasets (Texas, Cornell, and Wisconsin). The results, presented in Table 5 show that our approaches consistently achieve competitive or superior accuracy across all datasots. The experimental results indicate that. WLF is the strongeet--eeroomming method across all three WebKB datasets, followed closely by CLF. These results highlight the efficacy of our proposed approaches in handling weak label correlations and complex structural patterns in WebKB graphs.
(0020) for
A.5.2
Experiments on Wikipedia Datasets
Wikipedia Graphs
k-hop Homophily
squirrel
Squirrel
Chameleon
Actor
0.02
chameleon
Exphormer
65.08 + 1.68
66.71 1.48
36.58 1.39
SGFormer
65.69 + 1.87
66.82 1.41
37.05 1.54
0.00
CobFormer
64.12 + 1.39
66.94 + 1.96
36.52 1.42
CLF (Ours)
64.18 1.47
68.06 1.29
36.97
1.38
-0.02
WLF (Ours)
65.84 + 1.93
68.92 + 1.38
36.92 1.46
6
Hop Size
Table 6: Averaged vertex classification accuracy over 10 runs on Wikipedia datasets. We highlight the first and the second best results on each datasct.
Figure 10: (Best seen in colour) The k-hop ho- mophily metric for Wikipedia datasets fluctu- ates near zero.
We also conduct experiments on the following datasets:
Actor This dataset represents actor co-occurrence network. It is derived as the actor-only subgraph network Tang et al. (2009p. Each vertex represents an actor, and an edge
from the fimm-irecctor-cctor-vee between two vertices indicates that the actors co-appear on the same Wikipedia page. Vertex features are extracted based on cortain keywords from these Wikipedia pages. The actors (nodes) are classified into five calegories based on the terms found in their Wikipedia entries.
Squirrel and Chameleon These datasets are two page-lo-page networks focused on specific Wikipedia topics Rozemberczki et al. (2021). In these datasets, vertices represent individual web pages, while edges represent mutual links between them. The features of each verttex are based on several informative nouns found within the Wikipedia pages. The vertices are categorised into five groups based on the average monthly traffic each page receives.
20

---

Published in Transactions on Machine Learning Research (05/2025)
Analysis of k-hop Homophily The k- k-hop homophily metric for Wikipedia datasets (squirrel, chameleon, actor) fluctuates near wero, indicating lack of strong homophilic or heterophilic patterns. Unlike homophilic graphs, the metric does not show consistent downward trend, nor does it exhibit the expected increase in carly hops characteristic of the three heterophilic graphs in Figure These datasets likely contain mixed label interactions with no dominant structural bias.
This behavior indicates that vertices in these graphs do not predominantly connect either similar dissimilar labeled vertices, but rather exhibit more mixed structure. Possible explanations for these trends include high structural diversity, the presence of both homophilic and heterophilic subregions, degree heterogeneity Icading to variations in neighborhood composition. The results suggest that defining these datasets purely as heterophilic may be an ovensimplification, and further analysis of their structural properties could provide a clearer understanding their label connectivity dynamics.
Experimental Results We closely follow the experimental setup of prior work Pei et al. (2020) for these datasets too. Table 6 iillustrates that our methods consistently deliver competitive performance, with WLF achieving the best results across all datasets. These findings highlight the efficacy of our proposed ap- proaches in capturing structural properties, leveraging weak label dependencies, and improving classification performance in non-homophilic graphs. The consistent gains over transformer-based baselines validate the robustness and generalisability of our methods for Wikipedia datasets.
21


Reviews:
[{"review_id": "1cL4JLvl2i", "reviewer": "Reviewer_mRfw", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written and easy to follow.\n\n2. The performance of the proposed method is impressive.\n\n3. The proposed method makes sense and follows a simple formulation. \n\nWeaknesses: Please see the requested changes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of over-globalising in Transformers for graphs. The authors propose LocalFormer, a novel framework that includes collaborative and warm-up training strategies, to integrate local information into global computation. Empirical experiment results justify the effectiveness of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. It is still not clear why the proposed method works better than existing methods, especially on heterophilic graphs. I think the proposed method emphasizes local graph information, which should be contradictory to a successful learning of a heterophilic graph.\n\n2. I am wondering what the performance of the proposed method is on some simple and basic heterophilic graphs, such as Chameleon, Actor, Squirrel, Wisconsin, etc., used in Geom-GCN.\n\n3. I think your paper may claim an interesting thing, i.e., the training scheme beyond the architecture itself can further benefit graph learning with Transformers. Existing works [1,2,3] prove that a proper positional encoding is expressive enough or guaranteed to learn a specific graph structure. What is the connection between these works and your study? Can you elaborate more about what they miss in their study that you mainly improve?\n\n[1] Ying et al., Do transformers really perform badly for graph representation? Neurips 2021.\n\n[2] Chen et al., NAGphormer: A tokenized graph transformer for node classification in large graphs. ICLR 2023.\n\n[3] Li et al., What Improves the Generalization of Graph Transformers? A Theoretical Dive into the Self-attention and Positional Encoding. ICML 2024.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qbAemwjDcL", "reviewer": "Reviewer_uR7J", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1) The paper is well-written and accessible, making it easy to follow. \n\n2) The claims are well-supported with clear and effective visual evidence. \n\n3) The proposed method is intuitive and straightforward to understand. \n\n\nWeakness and requested changes: \n\n1) The interpretation of the proposed homophily measure requires stronger justification. It would benefit from a thorough theoretical analysis, including the metric's value range and its interpretation. For instance, while negative values are said as evidence of heterophily in a dataset, only one of the heterophilic datasets (roman-empire) shows negative homophily values in one hop, and even that is near zero. The remaining heterophilic datasets in Figure 1 A all exhibit positive homophily values, which raises questions about the consistency of the metric and reliability in distinguishing heterophilic and homophilic datasets. \n\n2) Provide a clear justification for selecting NodeFormer as the example attention mechanism in Figure 1B to support the generalization of the observations in Section 3. This is particularly important since the experimental results indicate that NodeFormer performs very poorly on both heterophilic and homophilic datasets. \n\n3) LocalFormer is instantiated using GCN and the BGA model without sufficient analysis or justification.  \n\n4) Clarify the concept of mutual supervision in the collaborative loss defined in Equation 3. In the proof on page 6, the CO loss is expressed as the sum of expectations of the log values of embeddings of the unlablled nodes learned by the local and global modules. What is the underlying interpretation of this formulation? Does it imply that larger embedding values lead to a smaller CO loss, or is the primary goal to enforce similarity between the embeddings produced by the local and global modules? If the latter, could this enforced similarity contribute to the “over-globalization” issue? Provide a detailed analysis and justification for this design decision.  \n\n5) Correct typographical errors, such as the one on page 3 under Equation 1, where \"matix\" should be corrected to \"matrix.\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper addresses the problem of \"over-globalization\" when applying transformers to graph machine learning, where the models tend to overly focus on higher-order neighborhoods. The authors analyze homophily in single-label graph datasets and provide an example attention mechanism in visualization to support their claims. \n\nTo tackle the over-globalization issue, the authors propose LocalFormer, a method that integrates local and global modules. The proposed method can be applied in two training settings: (1) a collaborative training setting where the local and global modules are jointly trained, and (2) a warm-up training setting where only the local module is trained during the initial epochs. \n\nIn their experiments, the authors instantiate the local module using GCN and the global module using the BGA module. LocalFormer is evaluated on 10 datasets, demonstrating consistent improvements over SOTA baseline models. Additionally, the authors conduct ablation studies to analyze the effectiveness of the local and global modules, the impact of warm-up epochs on final performance, and the attention scores learned by LocalFormer.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "see above in the weakness.", "broader_impact_concerns": "No", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "EzawKs3jQE", "reviewer": "Reviewer_AtT1", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n-The paper visualizes the homophily and attention distribution over multiple hops, effectively highlighting the \"over-globalising\" issue for graph transformers.\n\n-The proposed model generates competitive results, particularly on heterophilic datasets.\n\n-The Performance-Efficiency Tradeoff Analysis plot offers an intuitive way to evaluate the balance between performance and computational efficiency.\n\nWeakness and Questions:\n\n\n-The structural integration of a global graph transformer and a local GNN (GAT in the paper) is not clearly explained. It is unclear whether these components share information at each layer or they are only combined at the loss function. Additionally, the mathematical definition of the collaborative loss Lco is not clear.\n\n-Combining a global transformer with a local GNN is not a novel approach. It seems that the collaborative loss Lco is the key factor for the improved performance of the CLF scheme. To validate this, an ablation study of Lco would be highly beneficial. Although Figure 7 compares CLF with the SOTA model, the structure of the SOTA model may be different from the proposed model.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the problem of \"over-globalising\" in graph transformers, which can lead to suboptimal performance in vertex classification tasks. It provides visualizations to illustrate this issue and proposes a solution that performs better than existing SOTA models.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See Weakness and Questions.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors have made significant efforts to address all review comments, and all reviewers are satisfied with the revised submission.
Decision: Accept (poster)