DNFormer: Differential Attention for Graph Transformers

1 Introduction

Graph Neural Networks (GNNs), a promising paradigm for graph representation learning, have attract much attention lately, owing to their ability to effectively model both node attributes and graph topologies, and have demonstrated strong performance across a wide range of downstream tasks, such as node classification [Kipf and Welling, 2017; Velickovic et al., 2018], link prediction [Zhang and Chen, 2018], and graph classification [Zhang et al., 2018]. Classical GNNs, such as graph convolution networks (GCNs) [Kipf and Welling, 2017] and graph attention networks (GATs) [Velickovic et al., 2018], adopt message passing mechanisms, where node representations are iteratively updated by aggregating the features of their neighbors. While effective, this paradigm imposes inherent constraints: the receptive field grows only linearly with network depth, restricting its ability to capture long-range dependencies [Xu et al., 2019; Li et al., 2018]. Moreover, as layers stack deeper, GNNs often suffer from over-smoothing [Oono and Suzuki, 2020] (i.e., node representations become indistinguishable) and over-squashing [Alon and Yahav, 2021] (i.e., exponentially increasing information from distant nodes is compressed into fixed-size embeddings). These limitations have sparked increased interest in graph Transformer architectures, offering a promising alternative to traditional message-passing GNNs.

* Corresponding author

Graph Transformers (GTs) adapt the Transformer [Vaswani et al., 2017] architecture to graphs by using self-attention mechanism to compute pairwise node interactions and update node representations via weight aggregation [Ying et al., 2021; Dwivedi and Bresson, 2020]. However, early GT variants rely primarily on feature-only attention and lack effective mechanisms to incorporate graph structures, often leading to the omission of critical topological properties. To address these drawbacks, recent studies have proposed structure-aware GTs to explicitly integrate topological information. These GT-based approaches can be grouped into two categories. The first combines GNN-type local propagation with Transformer blocks to jointly leverage both local and global representations, as exemplified by GraphGPS [Dwivedi and Bresson, 2020], CoBFormer [Xing et al., 2024], and DualFormer [Zhuo et al., 2025]. The second category incorporates graph topologies into attention computation via explicit structural priors, including shortest-path distance, Laplacian or positional encodings, and structurebiased attention or attention biases [You et al., 2020; Kreuzer et al., 2021]. Nevertheless, many of these approaches rely predominantly on fully connected selfattention, where the quadratic computation overhead of modeling global interactions among all node pairs becomes prohibitively expensive for large graphs, thus significantly limiting their scalability.

Several attempts have been made to adopt local attention mechanisms for GTs, in which each node attends only to a limited set of neighbors, typically the 1-hop neighborhood or a sampled local subgraph. For instance, Exphormer builds sparse attention patterns using expander graphs together with original graph edges to perform scalable message passing [Shirzad et al., 2023]. NAGphormer constructs neighborhood-aware token sequences (e.g., ego-graphs) and applies attention within these local contexts [Chen et al., 2023]. LargeGT leverages subgraph sampling to restrict attention computation to compact local substructures for large graphs [Dwivedi et al., 2023]. In short, the primary objective of these methods is to reduce computational cost to nearly linear in the number of edges, while maintaining efficiency and preserving structural bias by restricting message exchange to graph's connectivities.

Despite their promising results, local attention in GTs is typically less discriminative than expected, often overemphasizing shared structural patterns while underweighting nodespecific properties. Our close analysis of this phenomenon revealed that attention scores computed within a neighborhood contain a shared, non-discriminative component, which we term common-mode noise. This arises because the neighbors of a given center node frequently share a similar local topology, such as one-hop proximity and recurring motifs like hubs and triangles. When attention scores incorporate topology-aware terms, these terms can contribute similarly across many neighbors, forming a large, shared component in their scores. For example, consider a high-degree node whose neighbors play similar structural roles. If the attention score includes a shared structural bias, many neighbors receive nearly identical topology-related contributions. In such a case, feature-based differences are small relative to the shared component, leading the softmax to produce nearly uniform weights across the neighborhood and causing many neighbors to be weighted similarly. Seriously, this shared component provides little discriminative power, resulting in a low-contrast attention computation. Consequently, the model may overemphasize common structural patterns while overlooking node-specific properties.

To address these serious issues, we propose a DiffereNtial local attention graph transFormer, called DNFormer, which suppresses common-mode topology bias in neighborhoodrestricted attention. In local attention, the logit between a node and its neighbors typically mixes (i) a topologyrelated bias that is similar across many neighbors (e.g., frequent structural patterns) and (ii) smaller neighbor-specific signals. When topology-related terms have large magnitudes and are highly correlated across neighbors, they make the logits within a neighborhood overly similar, leading to lowcontrast softmax weights and reduced discriminability.

Motivated by common-mode rejection, DNFormer computes two topology-aware similarity measures over the same neighborhood and forms a differential logit by subtraction. This subtraction removes the correlated, topology-induced part that many neighbors share, while preserving relative differences across neighbors. Consequently, the attention weights exhibit higher contrast within each neighborhood and are less dominated by frequent structural patterns, enabling more discriminative local aggregation. Then, we further enhance this mechanism with edge-adaptive modulation, where a learnable coefficient λij is predicted from the features of the two endpoint nodes via a lightweight feed-forward network. This coefficient controls how strongly the second score is subtracted on each edge, allowing the model to adapt the degree of common-mode suppression to different local contexts. As a result, DNFormer achieves fine-grained, edge-specific control over attention computation while retaining the scalability of local attention.

We make the following main contributions:

• We identify common-mode noise as an overlooked issue in local attention for GTs, and explain why shared local topology can dominate attention scores.
• We propose a differential local attention mechanism and implement it in DNFormer to suppress shared structural signals and improve neighbor discrimination, without sacrificing efficiency.
• Extensive experiments show that DNFormer consistently improves over representative GT baselines on standard benchmarks.

2 Preliminaries

We first introduce the notations and briefly review Graph Transformers.

2.1 Notations

Let G = (V, E, X) be an attributed graph, where V is the node set with N nodes, E ⊆ V ×V is the edge set, and X ∈ RN×F is the node feature matrix. The feature of node i is denoted as xi ∈ RF . The adjacency matrix is A ∈ {0, 1}N×N , where Aij = 1 if (i, j) ∈ E and 0 otherwise.

We denote the neighborhood of node i as N(i) = {j | (i, j) ∈ E}. More generally, we use S(i) to denote the attention candidate set of node i. For global attention, S(i) = V; for local attention, S(i) is a small subset such as N(i) or a sampled local subgraph.

For node classification, each node i has a label yi ∈ {1, 2, . . . , c}, where c is the number of classes. The goal is to learn a predictor f that maps node features and graph structure to class scores for all nodes.

2.2 Graph Transformers

Graph Transformers extend Transformer to graph data. Given node representations H ∈ RN×d , a single attention head projects them into query, key, and value spaces:

where WQ,WK,WV ∈ Rd×d′ and d′ is the per-head dimension.

For node i, attention scores are computed over a set of nodes S(i), which may correspond to its neighbors or a predefined receptive field. The attention weight from node i to node j is given by

where qi and kj denote the i-th and j-th rows of Q and K, respectively. The term bij is an additive bias that incorporates graph structure into attention computation.

Different Graph Transformers instantiate bij in different ways, such as using edge features, relative positional encodings, shortest-path distance biases, or other structural encodings [Ying et al., 2021; Dwivedi and Bresson, 2020].

The output representation of node i is obtained as a weighted sum of value vectors:

where vj is the j-th row of V. Multi-head attention applies this computation in parallel across multiple heads, followed by standard feed-forward layers and residual connections.

Full attention set S(i) = V, which requires computing all node pairs and is expensive on large graphs. Local attention restricts S(i) to a small set, commonly N(i) or a sampled local subgraph, which reduces computation to be roughly linear in the number of edges [Shirzad et al., 2023]. In many GT variants, local attention is used together with topology-aware terms bij so that attention remains structure-aware while being scalable. It is worth noting that our method builds on this local, topology-aware attention setting.

3 Methodology

In this section, we introduce DNFormer, a graph transformer architecture that computes local attention using differential attention and an edge-adaptive mechanism. The model computes attention by constructing two attention distributions over each neighborhood and combining them through a differential operation. A theoretical analysis of the differential attention mechanism is provided in Sec. 3.3.

3.1 Overview

As shown in Figure 1, given the input node representations H(l) and the graph structure A, DNFormer first applies linear projections to obtain the query, key, and value features. To enable differential local attention, the query and key channels are expanded and split into two parallel subspaces, which produce two attention distributions over the same local neighborhood, denoted as Attn1 and Attn2. DNFormer then combines them through a subtractive operation, where Attn2 is scaled by an edge-adaptive coefficient λij. The coefficient λij is predicted for each edge from the concatenation of its endpoint node features using a lightweight feed-forward network with a positive activation, enabling per-edge (and perhead) modulation of the subtraction strength. The resulting attention weights are used to aggregate value features within the neighborhood, thereby increasing attention contrast and improving neighbor discrimination during local message aggregation. Finally, the aggregated representation is fed into LayerNorm and a feed-forward network (FFN) with residual connections to produce the output H(l+1) .

3.2 Differential AttentionMechanism

Considering that attention weights over a neighborhood may become similar across neighbors after normalization, we introduce a differential attention mechanism for local neighborhood aggregation. Specifically, it computes two distinct attention distributions over the same neighborhood and subtracts one from the other, thereby enhancing the contrast among neighbors and improving discriminative aggregation.

Let X ∈ RN×d denote the input node feature matrix, we project X into query, key, and value projections via learnable linear transformations:

where WQ,WK ∈ Rd×2md′ and WV ∈ Rd×md′ . Here m denotes the number of attention heads and d′ = d/m is the dimension of each head. The query and key projections are intentionally expanded to twice the standard width in order to support two parallel attention pathways.

The projected queries and keys are reshaped into RN×m×2d′ and split along the feature dimension:

where Q(1) ,Q(2) ,K(1) ,K(2) ∈ RN×m×d′ . The query and key projections are split into two subspaces Q(1) ,K(1) and Q(2) ,K(2) , producing two separate sets of attention scores over the same neighborhood.

For each edge (i, j) ∈ E and attention head m, we compute two sets of unnormalized attention scores using scaled dotproducts:

where q(r,m) i and k(r,m) j denote the m-th head embeddings of node i and j in the r-th subspace. The scaling factor 1 √d′ follows standard practice to stabilize optimization. Each set of scores is independently normalized over the neighborhood N (i):

This normalization ensures that both attention branches operate on comparable scales prior to combination. We then define the final attention weight as the difference between two normalized attention distributions:

where λij > 0 is an edge-dependent coefficient that scales the second attention distribution. The coefficient λij scales the second attention distribution on each edge and the computation of λij is described in Sec. 3.4.

The output representation of node i under head m is obtained by aggregating value embeddings using the differential attention weights:h(m)

where v(m) j denotes the m-th head of the value projectionV. In summary, the proposed differential attention mechanism computes attention weights by subtracting two normalized attention distributions to reduce uniformity in attention. By subtracting two attention distributions computed over the same neighborhood, the model mitigates uniform attention patterns in local aggregation. Notably, this design preserves the standard attention aggregation while modifying how attention weights are computed.

3.3 Theoretical Analysis: Common-Mode Noise in Local Attention

In this section, we provide a theoretical justification for the proposed differential attention mechanism. We first formalize the notion of common-mode noise in local attention aggregation. We then show that standard graph attention mechanisms inherently produce such noise. Finally, we prove that the proposed differential attention formulation effectively suppresses this common-mode component.

Definition of Common-Mode Noise

We consider a graph G = (V, E) and focus on a fixed node i ∈ V with neighborhood N(i). For a given attention head m, let a(m) ij denote the normalized attention weight assigned to neighbor j ∈ N(i).

Definition 3.1 (Common-Mode Noise). For node i and attention head m, a common-mode noise component is a function:

such that c(m) i (j) = κ(m) i for all j ∈ N(i), where κ(m) i is a constant independent of j. An attention weight a(m) ij is said to contain common-mode noise if it can be decomposed as:

where ˜a(m) ij captures neighbor-specific relational variation.

This definition characterizes common-mode noise as a constant term that is added uniformly to the attention weights of all neighbors of a node and is independent of the specific neighbor being considered.

Existence of Common-Mode Noise in Local Attention

Here we analyze how standard attention-based graph aggregation can give rise to common-mode components.

Theorem 3.2. Consider a single-head attention mechanism with attention weights computed as:

Assume that the neighborhood features satisfy

where µi represents a shared neighborhood component. Then the resulting attention weights aij admit a decomposition that includes a non-zero common-mode noise component.

Proof. Substituting the decomposition of kj into the attention logits yields:

Let

Then

Using a first-order Taylor expansion of exp(δij) around zero and the assumption E[δij ] = 0, we obtain

The leading term 1 |N(i)| is constant across all j ∈ N(i) and therefore constitutes a common-mode noise component according to Definition 1.

This result shows that softmax normalization introduces a constant term into the attention weights that is identical across all neighbors.

Suppression of Common-Mode Noise via Differential Attention

Here we analyze how the proposed differential attention mechanism attenuates the common-mode component identified above.

Theorem 3.3. Let a(1,m) ij and a(2,m) ij be the two normalized attention scores defined in Section 3.2. Assume that both scores admit decompositions of the form:

where c(m) i is a shared neighborhood-level component. Then the differential attention:

suppresses the common-mode component whenever λij ≈ 1.

Proof. Substituting the decompositions into the differential attention yields:

If λij = 1, the constant term c(m) i is eliminated. If λij is close to 1, the contribution of c(m) i is reduced by the factor (1-λij). In both cases, the attention weight depends less on the constant term shared across neighbors.

This theorem shows that the constant term shared across neighbors is removed when the two attention distributions are subtracted.

3.4 Edge-Adaptive Modulation

To enhance the expressiveness of the differential attention mechanism, we introduce an edge-adaptive module that dynamically modulates the influence of the subtractive attention component. Instead of using a fixed scalar λ across all edges, we learn a structure-aware coefficient λ(m) ij > 0 for each edge Aij and attention head m ∈ {1, . . . , h}. This allows the model to selectively suppress or retain information from neighbors based on their local structure. Formally, for each edge Aij, we construct an edge-specific input by concatenating the source and target node features:

where xi, xj ∈ Rd are the raw node features of node i and j. This concatenated representation zij is passed through a small feed-forward network to predict the adaptive coefficients for all heads:

where W1 ∈ Rd′×2d , W2 ∈ Rh×d′ . The Softplus(·) activation ensures λ(m) ij > 0 for all heads m, preserving the interpretability of the subtraction in the attention formulation. The resulting vector λij = [λ(1) ij , . . . , λ(h) ij ]⊤ is used to scale the second attention component per edge and per head, allowing the model to adaptively determine how much negative influence to apply based on local structural and semantic context.

3.5 Complexity and Stability

DNFormer preserves the edge-linear complexity of neighborhood-restricted attention. For each layer, attention and aggregation are computed only on edges, yielding a time complexity of O(|E|d) (up to a constant factor for multi-head attention), which is of the same order as existing sparse/local Graph Transformers. The edge-adaptive predictor MLPλ operates on concatenated endpoint features and outputs a small vector per edge, introducing only lightweight per-edge computation and negligible overhead in practice.

We adopt several design choices to ensure stable optimization. The edge-adaptive coefficient λij is constrained to be positive (e.g., via a positive activation), which keeps the subtractive fusion well-behaved and avoids unstable scaling of the second attention score. In addition, dropout on attention coefficients mitigates over-confident weighting, while LayerNorm and residual connections in the Transformer block improve gradient flow and reduce training instability. Empirically, DNFormer shows convergence speed comparable to that of standard Graph Transformers and remains robust under noisy or redundant neighborhood connections.

4 Experiments

In this section, we present extensive experiments to evaluate the effectiveness of the proposed DNFormer. We first describe the experimental settings, datasets, and baseline methods, followed by the implementation details and evaluation protocol.

4.1 Experimental Setup

Datasets. We evaluate DNFormer on seven widely used benchmarks, including three citation networks [Sen et al., 2008] (Cora, CiteSeer, PubMed), two co-purchase [McAuley et al., 2015] (Computers, Photo) and two co-authorship graphs [Sinha et al., 2015] (CS, Physics). The detailed statistics of these datasets are summarized in Table 1. The citation networks contain papers as nodes and citation links as edges, with bag-of-words features and topic labels. The copurchase and co-authorship graphs involve product or author nodes connected by purchase or collaboration relations, characterized by richer semantics and denser connectivity.

Baselines. The baseline methods include five representative Graph Neural Networks (GNNs): GCN [Kipf and Welling, 2017], GAT [Velickovic et al., 2018], GraphSAGE [Hamilton et al., 2017], APPNP [Klicpera et al., 2019], and SGC

[Wu et al., 2019], which rely on localized message passing or propagation-based aggregation to learn node representations. In addition, we compare DNFormer with four recent Graph Transformer (GT) architectures, including NodeFormer [Wu et al., 2022], SGFormer [Wu et al., 2023], Polynormer [Deng et al., 2024], and DUALFormer [Zhuo et al., 2025], which adopt efficient attention designs to model long-range dependencies and higher-order interactions on graphs, such as sparse or approximated global attention and hybrid localglobal aggregation schemes. These baselines comprehensively cover both conventional GNN-based and Transformerbased graph learning paradigms, providing a basis for fair comparison.

Implementation Details. All experiments were conducted on a single server equipped with an NVIDIA RTX 4090 GPU (24 GB). The software environment is built on Python 3.10, PyTorch 2.4.1, and PyTorch Geometric 2.6.1. For each dataset, we adopt a fixed data split ratio of 60% / 20% / 20% for training, validation, and testing, respectively. Each experiment is repeated 10 times and we report the mean accuracy and standard deviation to ensure statistical reliability. All models are trained using the Adam optimizer.

4.2 Performance Analysis

We first summarize the main empirical finding: DNFormer delivers stable and competitive accuracy across diverse graphs, with particularly notable gains on datasets whose local neighborhoods exhibit strong structural regularities. These results suggest that improving the discriminability of neighborhood-restricted attention is a key factor for boosting node classification performance in practice.

As shown in Table 2, DNFormer achieves consistently strong performance across all seven benchmarks and outperforms both representative GNN baselines and recent Graph Transformer variants on most datasets. The gains are particularly clear on CiteSeer, CS, and the Amazon co-purchase graphs, where local neighborhoods often contain repeated structural patterns (e.g., hub-centric neighborhoods and triangle-rich regions). In such cases, standard local attention can become less discriminative because many neighbors share similar topology-induced scores, leading to low-contrast attention weights after softmax normalization. DNFormer addresses this issue by using differential local attention to cancel the shared neighborhood-level component in attention scores, making neighbor-specific differences more salient. This results in higher-contrast attention distributions within each neighborhood, which helps the model identify and aggregate more informative local signals. Overall, the results indicate that suppressing common-mode effects in local attention improves node classification across graphs with diverse structural and semantic characteristics.

4.3 Ablation Study

We then verify the contribution of each design choice by ablating the two core components of DNFormer. The ablation results consistently show that both differential local attention and edge-adaptive modulation contribute to the final performance, and they complement each other in improving discriminative local aggregation.

To examine the contribution of each component in DNFormer, we conduct ablation studies by removing (i) the differential attention operation and (ii) the edge-adaptive modulation module. The results are summarized in Table 3. First, removing differential attention (denoted as DNFormerw/o diff) consistently degrades performance across all datasets, with the largest drops observed on CiteSeer and CS. This supports our motivation that differential attention plays a key role in suppressing the shared, topologyinduced component that tends to dominate neighborhoodrestricted attention. Without the subtraction-based formulation, the model reverts to a standard single-sco local attention scheme, where attention weights are more likely to become uniform within a neighborhood, making them less effective at distinguishing informative neighbors. Second, removing edge-adaptive modulation (denoted as DNFormerw/o adapt) also leads to noticeable performance declines, although the magnitude is generally smaller than that observed with differential attention removal. This suggests that learning an edge-specific scaling factor for the subtractive component improves flexibility: different edges and neighborhoods may require different degrees of common-mode suppression, depending on local structure and feature semantics. The effect is more evident on denser graphs such as Computers and Photo, where neighborhoods are larger and structural regularities are stronger. Overall, both components contribute positively and complement each other, and the full DNFormer yields the best results across all benchmarks.

4.4 Hyper-parameter Analysis

We further study the robustness of DNFormer with respect to architectural hyperparameters by varying the number of attention heads and model depth on Computers and Photo.

As shown in Figure 2, for the number of heads, we observe that small head counts (e.g., 1-2 heads) generally perform best, while using many heads (e.g., 8-16) tends to reduce accuracy. A plausible explanation is that excessive head partitioning fragments the feature space and weakens the per-head signal-to-noise ratio in neighborhood-restricted attention, making it harder to preserve meaningful neighborspecific differences after normalization. In contrast, increasing depth provides a consistent improvement trend from 1 to 3-4 layers on both datasets, suggesting that stacking multiple DNFormer layers helps integrate multi-hop context while maintaining discriminative local aggregation through common-mode suppression. The improvement becomes less pronounced beyond 3 layers, indicating diminishing returns. On the whole, the performance landscape is smooth, implying that our proposed DNFormer is relatively stable under moderate hyperparameter perturbations. In practice, we find that 2 heads and 2-3 layers provide a strong trade-off between accuracy and efficiency.

5 RelatedWork

Graph Neural Networks. Graph Neural Networks (GNNs) [Gilmer et al., 2017] are a standard paradigm for graph representation learning, where node representations are updated by aggregating messages from local neighborhoods. Classical models such as GCN [Kipf and Welling, 2017] and GraphSAGE [Hamilton et al., 2017] achieve strong performance, but capturing long-range dependencies often requires deep message passing, which can suffer from over-smoothing [Oono and Suzuki, 2020] and over-squashing [Alon and Yahav, 2021]. These limitations motivate attention-based architectures that model graph interactions more flexibly than fixed neighborhood aggregation. Meanwhile, attention-based models can decouple information mixing from rigid multi-hop propagation, offering a more direct mechanism to integrate distant evidence when equipped with appropriate structural inductive biases.

Graph Transformers. Transformer architectures have been widely applied to various structured and sequential data analysis tasks, such as malicious domain name classification in cybersecurity [Ding et al., 2023]. Graph Transformers (GTs) adapt self-attention to graphs for adaptive interaction modeling [Ying et al., 2021; Dwivedi and Bresson, 2020; Kreuzer et al., 2021]. Many GTs incorporate topology into attention via structural encodings or bias terms, such as shortest-path and centrality biases in Graphormer [Ying et al., 2021], positional encodings and local message passing in GraphGPS [Dwivedi and Bresson, 2020], and structurebiased attention in SAN [Kreuzer et al., 2021]. However, full self-attention over all node pairs is expensive on large graphs, so many recent GTs adopt efficient designs, including sparse, sampled, or neighborhood-restricted (local) attention [Deng et al., 2024; Shirzad et al., 2023] and hybrid local-global schemes [Xing et al., 2024; Wu et al., 2023]. While local attention improves scalability, many neighbors share similar local topology, which can introduce a shared component in attention scores and reduce score contrast after softmax normalization. DNFormer addresses this by subtracting multiple topology-aware scores to cancel the shared component and further uses edge-adaptive modulation to adjust the suppression strength across local contexts.

6 Conclusion

We have proposed DNFormer, a improved Graph Transformer, to introduce differential local attention to mitigate the common-mode effect in neighborhood-restricted attention. The core idea is to compute multiple topology-aware attention scores within the same neighborhood and combine them via a subtractive operation, which cancels the effect of shared topology-induced components and highlights neighbor-specific differences. We further incorporated an edge-adaptive modulation module, enabling the model to adjust the degree of common-mode suppression to different local contexts while retaining the scalability of local attention. Extensive experiments on seven node classification benchmarks demonstrate that DNFormer consistently outperforms representative GNNs and recent Graph Transformers. Future work includes extending DNFormer to heterogeneous and dynamic graphs and exploring its applicability to edge-level and graph-level learning tasks.

Acknowledgments

This work was supported by the National Natural Science Foundation of China (No. 62422210, No. 62276187, No. 62402337 and No. 62261045), the Hong Kong RGC themebased Strategic Target Grant Scheme (STG STG1/M-501/23N), the Hong Kong Global STEM Professor Scheme, and the Hong Kong Jockey Club Charities Trust.