Timezone: »

 
Poster
Graph Positional Encoding via Random Feature Propagation
Moshe Eliasof · Fabrizio Frasca · Beatrice Bevilacqua · Eran Treister · Gal Chechik · Haggai Maron

Tue Jul 25 05:00 PM -- 06:30 PM (PDT) @ Exhibit Hall 1 #328
in Poster Session 2 »

Two main families of node feature augmentation schemes have been explored for enhancing GNNs: random features and spectral positional encoding. Surprisingly, however, there is still no clear understanding of the relation between these two augmentation schemes. Here we propose a novel family of positional encoding schemes which draws a link between the above two approaches and improves over both. The new approach, named Random Feature Propagation (RFP), is inspired by the power iteration method and its generalizations. It concatenates several intermediate steps of an iterative algorithm for computing the dominant eigenvectors of a propagation matrix, starting from random node features. Notably, these propagation steps are based on graph-dependent propagation operators that can be either predefined or learned. We explore the theoretical and empirical benefits of RFP. First, we provide theoretical justifications for using random features, for incorporating early propagation steps, and for using multiple random initializations. Then, we empirically demonstrate that RFP significantly outperforms both spectral PE and random features in multiple node classification and graph classification benchmarks.

[ PDF]  [ Poster] 

Author Information

Moshe Eliasof (Ben-Gurion University of the Negev)
Fabrizio Frasca (Imperial College London)
Beatrice Bevilacqua (Purdue University)
Eran Treister (Ben-Gurion University of the Negev)
Gal Chechik (NVIDIA / Bar-Ilan University)
Haggai Maron (NVIDIA Research)

I am a Research Scientist at NVIDIA Research. My main fields of interest are machine learning, optimization, and shape analysis. More specifically, I am working on applying deep learning to irregular domains (e.g., graphs, point clouds, and surfaces) and graph/shape matching problems. I completed my Ph.D. in 2019 at the Department of Computer Science and Applied Mathematics at the Weizmann Institute of Science under the supervision of Prof. Yaron Lipman.

More from the Same Authors