Learning Laplacian Positional Encodings for Heterophilous Graphs

Michael Ito, Jiong Zhu, Dexiong Chen, Danai Koutra, Jenna Wiens

TL;DR

Standard graph positional encodings (PEs) rely exclusively on the smallest Laplacian eigenvectors, a design choice that fails catastrophically on heterophilous graphs where connected nodes have different labels. To fix this, the authors introduce Learnable Laplacian Positional Encodings (LLPE), which leverages a truncated Chebyshev series to learn from the full Laplacian spectrum. LLPE seamlessly adapts to both homophilous and heterophilous structures, boosting the accuracy of Graph Neural Networks (GNNs) and Graph Transformers by up to 35% on synthetic and 14% on real-world benchmarks.

What Problem Does This Paper Address?

To help Graph Neural Networks (GNNs) and Graph Transformers understand the relative positions of nodes in a network, researchers use Positional Encodings (PEs). The gold standard has long been Laplacian PEs (LPEs), which use the eigenvectors corresponding to the smallest eigenvalues of a graph's Laplacian matrix.

This approach works beautifully for homophilous graphs—networks where connected nodes tend to share the same label (think of a social network where friends share hobbies). However, many real-world networks are heterophilous, meaning connected nodes are likely to have different labels (e.g., protein interactions or fraudulent transaction networks).

The authors mathematically demonstrate that standard LPEs fail on heterophilous graphs. Because they only look at the "low-frequency" (smallest) eigenvalues, they miss the critical "high-frequency" structural information necessary to distinguish different communities in heterophilous settings.

Methods

The authors propose Learnable Laplacian Positional Encodings (LLPE) to automatically discover which parts of the graph spectrum matter most for a given task.

  • Spectral Filtering via Chebyshev Polynomials: Instead of manually selecting the first $k$ eigenvectors, LLPE learns a continuous filter function $h(\lambda)$ that weights the importance of every eigenvector based on its corresponding eigenvalue. To make this function learnable and stable, it is parameterized as a truncated Chebyshev series. The coefficients of this series are optimized directly via backpropagation during GNN training.
  • Sparsity Regularization: The model applies $l_1$ and $l_2$ regularization to the learned weights, encouraging the network to select a sparse, clean subset of relevant eigenvectors.
  • Scaling to Large Graphs: Computing the full eigendecomposition of a giant graph is computationally prohibitive ($O(n^3)$). To scale LLPE, the authors use the Arnoldi iteration algorithm to extract just the first and last $k$ eigenvectors and eigenvalues, dropping the complexity to a manageable $O(k^2n)$.

Datasets

The authors evaluated LLPE across a comprehensive suite of 12 benchmarks:

  • Synthetic Datasets: Binary and multiclass Stochastic Block Models (SBMs) with varying homophily ratios, alongside complex power-law graphs generated via preferential attachment.
  • Real-World Small/Medium Datasets: Texas, Cornell, Cora-ML, Cora, Photo, Amazon-ratings, Tolokers, Cora-full, and Computers.
  • Real-World Large Datasets: Penn94 and Questions (ranging from 40,000 to 50,000 nodes).

Key Insights and Ideas

  • The Spectral Flip: The paper mathematically proves (Theorem 3.2) that while the smallest eigenvalues recover communities in homophilous graphs, the largest eigenvalues (the opposite end of the spectrum) are what perfectly recover community structures in heterophilous graphs.
  • The Danger of Local Heterophily: Even graphs that are globally homophilous (like the Cora citation network) contain local pockets of high heterophily. Standard LPEs actually degrade performance for nodes inside these pockets. LLPE fixes this blind spot by dynamically adapting to local variations.
Performance across local node homophily quintiles on Cora and Amazon-ratings.
  • Implicit Regularization: Why not just feed the entire eigenvector matrix into a standard MLP? The authors point out that an MLP's weight dimensions scale with the number of nodes ($n$), leading to severe overfitting on large, noisy graphs. Because LLPE's Chebyshev coefficients depend only on the polynomial order ($M$) and not $n$, it possesses an inherent architectural regularization that ensures excellent statistical generalization.

Key Results

  • Synthetic Superiority: On heterophilous SBMs, standard LPE baselines perform no better than using no positional encoding at all. LLPE successfully identifies the high-frequency components, matching the performance of specialized baselines on homophilous graphs and vastly outperforming them on heterophilous ones.
Test accuracy on synthetic binary and multiclass SBMs across varying homophily ratios.
  • Real-World Gains: Across small and medium real-world datasets, LLPE achieved the best average rank among all tested PEs. For instance, on medium datasets, LLPE secured an average rank of 1.25, compared to 3.25 for the next-best learnable PE baseline.
  • Substantial Accuracy Boosts: Integrating LLPE into standard architectures like Graph Transformers and GraphSAGE yielded accuracy improvements of up to 35% on synthetic graphs and up to 14% on real-world datasets.

Limitations and Future Work

  • Hyperparameter Tuning: LLPE introduces additional hyperparameters that require careful tuning, notably the order $M$ of the Chebyshev polynomials and the number of extreme eigenvectors $k$ chosen for large graphs. The model can be sensitive to small choices of $M$.
  • The Middle-Spectrum Blind Spot: For massive graphs, the Arnoldi iteration approximation only samples from the absolute boundaries (the lowest and highest ends) of the spectrum. If a complex real-world network hides its structural properties somewhere in the middle eigenvalues, the current large-graph variant of LLPE might miss it. The authors note that searching across the entire spectrum efficiently remains an open direction for future work.

Summary updated

Abstract

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.
BibTeX
@inproceedings{ito2025learning,
  author = {Michael Ito and Jiong Zhu and Dexiong Chen and Danai Koutra and Jenna Wiens},
  title = {{Learning Laplacian Positional Encodings for Heterophilous Graphs}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2025},
  url = {https://openreview.net/forum?id=s6ljg6uX9C},
}
Figure