DNFormer: Differential Attention for Graph Transformers

Abstract

Graph Transformers (GTs) have emerged as a powerful paradigm for graph representation learning, leveraging attention mechanisms to enable flexible information exchange. Recent GTs often adopt local attention to restrict computation to neighborhoods, thereby reducing costs and enhancing scalability. However, local attention computation poses a serious issue that significantly reduces the efficacy of the overall approaches – because computation is restricted to local neighborhoods, node pairs that share topological patterns receive similar attention scores, thereby reducing attention’s discriminative power. Consequently, GT-based models typically overemphasize common structural motifs but fail to capture node-specific properties. To address this problem, we propose DNFormer, a novel GT grounded in differential modeling. We introduce a differential local attention mechanism in DNFormer that computes attention scores as differences across multiple topology-aware similarity measures, rather than relying on a single score. This mechanism suppresses shared topological patterns among neighbors and emphasizes relative node-to-node distinctions. As a result, DNFormer mitigates structural dominance in attention aggregation, better capturing node-specific relational patterns while preserving local structural properties. Extensive experiments confirm DNFormer's superior performance over representative GT baselines.