FDphormer: Beyond Homophily with Feature-Difference Position Encoding

Graph Transformers have garnered significant attention due to their ability to address the challenges of long-distance interactions in previous GNNs. However, most current graph Transformers face difficulties when dealing with heterophilic graphs. To investigate this issue, we first analyzed the distribution of attention weights for homophilic and heterophilic graphs. We discovered that heterophily interferes with the allocation of attention weights, leading to errors in node classification. Further investigation revealed that the root cause may be the difficulty of current graph Transformers in capturing the difference between the features of each node and its neighbors. To alleviate this issue, we propose a position encoding strategy called DiSP to better capture the feature difference and introduce FDphormer, a new efficient and simple graph Transformer model based on DiSP. Additionally, we analyze the generalization error of existing graph Transformer models and provide an upper bound on the generalization error of current graph Transformers with the introduction of DiSP. Extensive experiments demonstrate that FDphormer not only outperforms state-of-the-art methods on diverse heterogeneous datasets but also exhibits competitive performance under homophily.