Learning Laplacian Positional Encodings for Heterophilous Graphs
Michael Ito, University of Michigan
While graph positional encodings (PEs) have been shown to improve node classification in GNNs on homophilous graphs where nodes of the same label tend to be close, we find that they are not as beneficial in heterophilous graphs, where nodes that are close tend to have different labels. This limitation is critical as many real-world networks exhibit heterophily, and even highly homophilous graphs can contain local regions of strong heterophily. We address this gap by exploring PEs in the context of node classification for homophilous and heterophilous graphs. Our analysis reveals that popular PEs may not capture relevant graph structure in heterophilous settings. To address this limitation, we propose Learnable Laplacian Positional Encodings (LLPE), a new PE that leverages the full spectrum of the graph Laplacian, enabling them to capture graph structure on both homophilous and heterophilous graphs. Theoretically, we prove LLPE's ability to approximate a general class of graph distances and demonstrate its generalization properties. Empirically, we evaluate on 12 benchmarks and demonstrate that LLPE improves accuracy by up to 35% and 14% on synthetic and real-world graphs, respectively. Going forward, our work represents a significant first step towards developing data-driven PEs that effectively capture complex structures in heterophilous graphs.