  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.
