Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks

Haorui Wang, Haoteng Yin, Muhan Zhang, Pan Li

Standard Graph Neural Networks (GNNs) are the gold standard for graph data, but they often suffer from a fundamental weakness: an "identity crisis." Because they rely on aggregating information from local neighbors, two nodes that occupy identical structural positions (automorphic nodes) will end up with the exact same representation. This makes it nearly impossible for a standard GNN to predict whether a link should exist between two specific nodes if those nodes "look" identical to the algorithm.

To address this, researchers typically rely on either assigning random node IDs (which harms generalization) or calculating the distance between every pair of nodes (which is computationally expensive).

This paper introduces PEG (Positional Encoding Graph), a novel GNN layer that incorporates absolute positional information in a way that is mathematically stable, "rotation equivariant," and highly scalable. PEG allows GNNs to achieve state-of-the-art performance on tasks like link prediction without the massive computational overhead of previous distance-encoding methods.

The GNN Identity Crisis and the PEG Solution

Historically, using absolute coordinates for nodes—known as Positional Encoding (PE), such as Laplacian Eigenmaps—has been criticized. While efficient, PE is often unstable (small changes to the graph cause huge jumps in coordinates) and not "inductive" (hard to apply a model trained on one graph to a totally different one).

The GNN identity crisis and the PEG solution

The authors propose the PEG layer, which overcomes these historical limitations by handling original node features and positional encodings through separate, specialized channels. The core innovation lies in how these channels interact:

  • Permutation Equivariance: The node feature channel remains invariant to how you order the nodes, preserving standard GNN behavior.
  • Rotation Equivariance: The positional channel is designed to be equivariant to rotations ($SO(p)$). Since positional encodings like Laplacian Eigenmaps are essentially eigenvectors, they are only unique up to a rotation or sign flip. By making the GNN layer "rotation-aware," the model doesn't get confused if the coordinate system shifts slightly.
  • Relative Distance Updates: The PEG layer updates node features by looking at the distance between node encodings in the coordinate space, rather than the absolute coordinates themselves. This ensures that the model learns the relative structure of the graph, aiding in generalization.

Key Insights and Stability

One of the most significant theoretical contributions of this paper is its proof of stability. Previous PE methods were unstable because their error depended on the smallest gap between any two eigenvalues in the graph's structure.

The authors mathematically prove that PEG’s stability only depends on the gap between the $p$-th and $(p+1)$-th eigenvalues. This makes the model significantly more robust to noise and small graph perturbations. Furthermore, the authors demonstrate that their framework isn't limited to Laplacian Eigenmaps; it can be generalized to other popular embedding techniques like DeepWalk and LINE by viewing them as matrix factorization problems.

Experimental Results

The researchers evaluated PEG across a wide variety of benchmarks, including citation networks (Cora, CiteSeer, Pubmed), social/web networks (Twitch, Chameleon), biological networks (PPI), and large-scale Open Graph Benchmark (OGB) datasets.

  • Link Prediction Power: On the OGB ddi dataset, PEG-based models (like PE-SAGE) achieved a Hit@20 of ~56%, significantly outperforming standard GCNs (~37%) and approaching the performance of much slower, computationally heavy models like SEAL.
  • Efficiency: Unlike Distance Encoding methods that require heavy computation for every pair during inference, PEG computes positional encodings just once. This makes PEG significantly faster during the testing phase.
  • Domain-Shift Success: In transfer learning tasks (e.g., training on a Twitch network in English and testing on one in Russian), PEG showed remarkable generalization. It outperformed baselines like VGAE by large margins, proving that its learned "spatial" rules transfer effectively across different networks.

Limitations and Future Work

While PEG is vastly more stable than previous PE methods, it still relies on an initial matrix factorization or eigenvalue decomposition step. For extremely large, highly dynamic graphs, re-computing these encodings could still present a bottleneck.

The current work focuses primarily on link prediction. However, the authors suggest that future research could extend the PEG framework to other complex node-set tasks, such as motif counting or predicting higher-order interactions in hypergraphs.

Summary updated

Abstract

Graph neural networks (GNN) have shown great advantages in many graph-based learning tasks but often fail to predict accurately for a task-based on sets of nodes such as link/motif prediction and so on. Many works have recently proposed to address this problem by using random node features or node distance features. However, they suffer from either slow convergence, inaccurate prediction, or high complexity. In this work, we revisit GNNs that allow using positional features of nodes given by positional encoding (PE) techniques such as Laplacian Eigenmap, Deepwalk, etc. GNNs with PE often get criticized because they are not generalizable to unseen graphs (inductive) or stable. Here, we study these issues in a principled way and propose a provable solution, a class of GNN layers termed PEG with rigorous mathematical analysis. PEG uses separate channels to update the original node features and positional features. PEG imposes permutation equivariance w.r.t. the original node features and rotation equivariance w.r.t. the positional features simultaneously. Extensive link prediction experiments over 8 real-world networks demonstrate the advantages of PEG in generalization and scalability. Code is available at https://github.com/Graph-COM/PEG.
BibTeX
@inproceedings{wang2022equivariant,
  author = {Haorui Wang and Haoteng Yin and Muhan Zhang and Pan Li},
  title = {{Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks}},
  booktitle = {International Conference on Learning Representations},
  year = {2022},
  url = {https://openreview.net/forum?id=e95i1IHcWj},
}
Figure