Generalized Laplacian Positional Encoding for Graph Representation Learning
This work addresses fundamental limitations in graph neural networks for researchers and practitioners in graph-structured data processing, though it appears incremental as it builds on existing Laplacian-based positional encoding ideas.
The paper tackles the limitations of Message Passing Neural Networks (MPNNs) in graph representation learning by introducing a novel family of positional encodings based on generalizing Laplacian embeddings to p-norms, which improves the expressive power of MPNNs as demonstrated in preliminary experiments.
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.