NeurIPS 2022

Timezone: »

Generalized Laplacian Positional Encoding for Graph Representation Learning

Sohir Maskey · Ali Parviz · Maximilian Thiessen · Hannes Stärk · Ylli Sadikaj · Haggai Maron

in Symmetry and Geometry in Neural Representations (NeurReps) »

Event URL: https://openreview.net/forum?id=BNhhZwAlVNC »

Graph neural networks (GNNs) are the primary tool for processing graph-structured data. Unfortunately, the most commonly used GNNs, called Message Passing Neural Networks (MPNNs) suffer from several fundamental limitations. To overcome these limitations, recent works have adapted the idea of positional encodings to graph data. This paper draws inspiration from the recent success of Laplacian-based positional encoding and defines a novel family of positional encoding schemes for graphs. We accomplish this by generalizing the optimization problem that defines the Laplace embedding to more general dissimilarity functions rather than the 2-norm used in the original formulation. This family of positional encodings is then instantiated by considering p-norms. We discuss a method for calculating these positional encoding schemes, implement it in PyTorch and demonstrate how the resulting positional encoding captures different properties of the graph. Furthermore, we demonstrate that this novel family of positional encodings can improve the expressive power of MPNNs. Lastly, we present preliminary experimental results.

Keywords: positional encoding · graph neural networks · Graph Laplacian

[ Poster] [ OpenReview]

Author Information

Sohir Maskey (Ludwig-Maximilians University of Munich)

Ali Parviz (New Jersey Institute of technology)

Maximilian Thiessen (TU Wien)

Hannes Stärk (MIT)

I am a first-year PhD student at MIT in the CS and AI Laboratory (CSAIL) co-advised by Tommi Jaakkola and Regina Barzilay. I work on geometric deep learning and physics-inspired ML and applications in molecular biology and other physical systems.

Ylli Sadikaj (Universität Vienna)

Haggai Maron (NVIDIA Research)

I am a PhD student at the Department of Computer Science and Applied Mathematics at the Weizmann Institute of Science under the supervision of Prof. Yaron Lipman. 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 serve as a reviewer for NeurIPS, ICCV, SIGGRAPH, SIGGRAPH Asia, ACM TOG, JAIR, TVCG and SGP.