mlsanityData to 14 Oct 2026

Learning Laplacian Positional Encodings for Heterophilous Graphs

arXiv 2504.20430 ↗First posted 29 Apr 2025cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

In this work, we theoretically demonstrate that current graph positional encodings (PEs) are not beneficial and could potentially hurt performance in tasks involving 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. 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, our evaluation on 12 benchmarks demonstrates that LLPE improves accuracy across a variety of GNNs, including graph transformers, by up to 35% and 14% on synthetic and real-world graphs, respectively. Going forward, our work represents a significant step towards developing PEs that effectively capture complex structures in heterophilous graphs.

Key facts. Cited by 4 papers in the map (data through 14 Oct 2026). Builds on 46 of its 80 references that are in the map. First posted on arXiv 29 Apr 2025.

Builds on

46 of 80 references.

References · 46

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2018How Powerful are Graph Neural Networks?cited by 4,393
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  6. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,089
  7. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  8. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 976
  9. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 826
  10. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  11. 2020A Generalization of Transformer Networks to Graphscited by 661
  12. 2021Rethinking Graph Transformers with Spectral Attentioncited by 473
34 more
  1. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
  2. 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 362
  3. 2023A critical look at the evaluation of GNNs under heterophily: Are we really making progress?cited by 343
  4. 2017Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Rankingcited by 335
  5. 2021Graph Neural Networks with Learnable Structural and Positional Representationscited by 333
  6. 2017Community Detection and Stochastic Block Modelscited by 319
  7. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 311
  8. 2019Position-aware Graph Neural Networkscited by 203
  9. 2020Graph Neural Networks with Heterophilycited by 202
  10. 2021BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximationcited by 195
  11. 2022Structure-Aware Transformer for Graph Representation Learningcited by 194
  12. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  13. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  14. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 179
  15. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  16. 2023Graph Inductive Biases in Transformers without Message Passingcited by 153
  17. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  18. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
  19. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  20. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  21. 2023Graph Positional and Structural Encodercited by 33
  22. 2023Beyond Homophily: Reconstructing Structure for Graph-agnostic Clusteringcited by 29
  23. 2013Impact of regularization on Spectral Clusteringcited by 25
  24. 2015Concentration and regularization of random graphscited by 25
  25. 2014Community detection in sparse networks via Grothendieck's inequalitycited by 21
  26. 2020On the Rademacher Complexity of Linear Hypothesis Setscited by 17
  27. 2022Affinity-Aware Graph Networkscited by 17
  28. 2023On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networkscited by 13
  29. 2024On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networkscited by 10
  30. 2022Restructuring Graph for Higher Homophily via Adaptive Spectral Clusteringcited by 9
  31. 2022Deformable Graph Transformercited by 7
  32. 2024Representation Learning on Heterophilic Graph with Directional Neighborhood Attentioncited by 6
  33. 2024Revisiting Graph Homophily Measurescited by 4
  34. 2015Sparse random graphs: regularization and concentration of the Laplaciancited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 2; 2026: 2.

4 papers.

  1. 2025Random Search Neural Networks for Efficient and Expressive Graph Learningcited by 1
  2. 2025Tab-PET: Graph-Based Positional Encodings for Tabular Transformerscited by 0
  3. 2026Eigenbasis-Independent Learnable Spectral Positional Encodings for Directed Graphs via Hermitian Block Krylov Subspacescited by 0
  4. 2026Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Predictioncited by 0