  Most existing graph neural networks (GNNs) learn node embeddings using the
framework of message passing and aggregation. Such GNNs are incapable of
learning relative positions between graph nodes within a graph. To empower GNNs
with the awareness of node positions, some nodes are set as anchors. Then,
using the distances from a node to the anchors, GNNs can infer relative
positions between nodes. However, P-GNNs arbitrarily select anchors, leading to
compromising position-awareness and feature extraction. To eliminate this
compromise, we demonstrate that selecting evenly distributed and asymmetric
anchors is essential. On the other hand, we show that choosing anchors that can
aggregate embeddings of all the nodes within a graph is NP-hard. Therefore,
devising efficient optimal algorithms in a deterministic approach is
practically not feasible. To ensure position-awareness and bypass
NP-completeness, we propose Position-Sensing Graph Neural Networks (PSGNNs),
learning how to choose anchors in a back-propagatable fashion. Experiments
verify the effectiveness of PSGNNs against state-of-the-art GNNs, substantially
improving performance on various synthetic and real-world graph datasets while
enjoying stable scalability. Specifically, PSGNNs on average boost AUC more
than 14% for pairwise node classification and 18% for link prediction over the
existing state-of-the-art position-aware methods. Our source code is publicly
available at: https://github.com/ZhenyueQin/PSGNN
