Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks

Haorui Wang, Haoteng Yin, Muhan Zhang, Pan Li

TL;DR

This paper introduces PEG, a novel Graph Neural Network (GNN) layer that enhances performance on node-set prediction tasks by incorporating positional encodings (PE) in a principled, stable, and equivariant manner. PEG achieves state-of-the-art results on link prediction, demonstrating superior generalization and scalability compared to existing methods.

What Problem Does This Paper Address?

Graph Neural Networks (GNNs) excel at many graph-based learning tasks but struggle with tasks involving sets of nodes, such as link or motif prediction. This limitation stems from GNNs' inherent inability to distinguish between nodes that are structurally equivalent under graph automorphisms. While previous approaches have tried to address this by augmenting node features with random features or distance encodings, these methods often suffer from slow convergence, inaccurate predictions, or high computational complexity. This paper aims to provide a more robust and efficient solution by developing GNN layers that are both permutation equivariant and stable when using positional encodings.

Methods

The core contribution is the PEG (Positional Encoding Guided) layer. PEG addresses the node ambiguity problem by treating original node features and positional features in separate channels. Crucially, it enforces:

  • Permutation Equivariance for the original node features.
  • Orthogonal Group ($O(p)$) Equivariance for the positional features.

This dual equivariance ensures that the model's predictions are consistent regardless of node ordering and stable with respect to variations in positional feature representations. The authors provide rigorous mathematical analysis to prove these properties, particularly focusing on stability derived from the eigenspace of graph Laplacians. They also demonstrate that PEG can be applied to various PE techniques, including Laplacian Eigenmaps (LE) and Deepwalk.

Datasets

The paper evaluates PEG on several real-world datasets for link prediction tasks:

  • Citation Networks: Cora, CiteSeer, Pubmed
  • User-Interaction Networks: Twitch (RU, EN, ES, FR, PT, RU)
  • Biological Networks: Chameleon, PPI
  • Open Graph Benchmark (OGB): ogbl-ddi, ogbl-collab

They also conduct experiments on random graph models (stochastic block models) to specifically test generalization capabilities.

Key Insights and Ideas

  • Node Ambiguity is the Root Cause: The paper clearly articulates that the failure of GNNs in node-set prediction tasks is due to their inability to differentiate structurally equivalent nodes.
  • Equivariance and Stability are Key: The authors establish that for GNNs to generalize well and be robust to perturbations, they must be both permutation equivariant (for node features) and stable (for positional features).
  • Eigenspace Stability is Crucial: They show that stability is not just about individual eigenvectors but about the stability of the eigenspace, which is less sensitive to small perturbations in the graph structure. This is a key theoretical insight.
  • Separate Channels for Features: Using separate channels for original node features and positional features allows PEG to maintain distinct inductive biases for each type of information.
  • $O(p)$ Equivariance for Positional Features: This is a novel approach that ensures robustness to different representations of positional information.

Key Results

  • State-of-the-Art Link Prediction: PEG consistently outperforms strong baselines, including those using distance encodings (like SEAL), on various real-world datasets for link prediction.
  • Superior Generalization: In domain-shift link prediction tasks and experiments on random graphs, PEG demonstrates significantly better generalization capabilities than GAE/VGAE variants.
  • Scalability and Efficiency: PEG achieves comparable or better performance than distance-encoding methods (like SEAL) with much lower training and inference complexity.
  • Robustness to Perturbations: Experiments show PEG is highly resilient to graph perturbations (adding/dropping edges), outperforming GAE/VGAE models in stability.
  • Node Classification Performance: Preliminary results on node classification also show PEG performing competitively with GAT.

Limitations and Future Work

  • Hyperparameter Tuning: While PEG performs well, the authors suggest that more extensive hyperparameter tuning could yield even better results.
  • Generalization to Other PE Techniques: The paper focuses on Laplacian Eigenmaps and Deepwalk for PE. Further work could explore a broader range of PE techniques and their theoretical guarantees.
  • Combining with Attention: The authors suggest that PEG could be further combined with attention mechanisms for even better performance, particularly in node classification tasks.
  • Extensive Study of Instability: The paper notes that the instability issue observed in prior works might be more severe for larger graphs and smaller training sets, suggesting this as a direction for future research.

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 imposes $O(p)$ (orthogonal group) equivariance w.r.t. the positional features simultaneously, where $p$ is the dimension of used positional features. Extensive link prediction experiments over 8 real-world networks demonstrate the advantages of PEG in generalization and scalability.
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