Degraded but Not Entirely Ineffective: PE-Based Deformable Graph Neural Networks

Abstract

Many real-world scenarios can be represented using graph-structured data. However, traditional GNNs that transmit messages based on first-order neighbors have long faced several fundamental contradictions: increasing depth leads to over-smoothing, long-range dependencies cause over-compression, fixed neighborhoods restrict the receptive field, and on heterophilous graphs, topological neighbors become a source of noise. Although many works have addressed these issues individually, few mechanisms can simultaneously alleviate all of these challenges. To address the aforementioned problems, we propose a Position Encoding-Based Deformable Spatial Aggregation Module (PEBDSAM) that solves them all in one step. Specifically, we utilize a deformable mechanism in the position space to identify relevant nodes to supplement the original first-order neighbor information of GNNs, allowing traditional GNNs to adapt to heterophilous scenarios. Through diagnostic experiments, we obtained several major findings: current offsets fail to have any effect; subsequently, we analyzed the causes of offset failure and why model performance still improves even after offset failure, pointing out future research directions. Based on these diagnostic experiments, we streamlined the original PEBDSAM, resulting in a simplified version, which we call the Position Encoding-Based Spatial Aggregation Module (PEBSAM). In addition, we propose a PEBSAM-Speed to adapt to large datasets. Finally, we designed the module to be plug-and-play and applied it to GCN, GAT, GIN, and GraphSAGE, achieving desirable results on three homophilous datasets and six heterophilous graph datasets.