Georgia Institute of Technology College of Sciences

Designing effective positional encodings for graphs is key to building powerful graph transformers and enhancing message-passing graph neural networks’ expressive power. However, since there lacks a canonical order of nodes in the graph-structure data, the choice of positional encodings for graphs is often tricky. For example, Laplacian eigenmap is used as positional encodings in many works. However, it faces two fundamental challenges: (1) Non-uniqueness: there are many different eigen-decompositions of the same Laplacian, and (2) Instability: small perturbations to the Laplacian could result in completely different eigenvectors, leading to unpredictable changes in positional encoding. This is governed by the Davis-Kahan theorem, which further negatively impacts the model generalization. In this talk, we are to introduce some ideas on building stable positional encoding and show their benefits in model out-of-distribution generalization. The idea can be extended to some other types of node positional encodings. Finally, we evaluate the effectiveness of our method on molecular property prediction, link prediction, and out-of-distribution generalization tasks, finding improved generalization compared to existing positional encoding methods.

I will mainly talk about three papers:

1. Distance Encoding: Design Provably More Powerful Neural Networks for Graph Representation Learning,NeurIPS20, Pan Li, Yanbang Wang, Hongwei Wang, Jure Leskovec

2. Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networks, ICLR22 Haorui Wang, Haoteng Yin, Muhan Zhang, Pan Li

3. On the Stability of Expressive Positional Encodings for Graphs, ICLR24 Yinan Huang, William Lu, Joshua Robinson, Yu Yang, Muhan Zhang, Stefanie Jegelka, Pan Li