PP-GNN: Pretraining Position-aware Graph Neural Networks with the NP-hard metric dimension problem

On a graph G = (V, E), we call S c V resolving if for all u, v is an element of V with u # v, there exists w is an element of V such that d(u, w) # d(v, w). The smallest possible cardinality of S is called the metric dimension, computing which is known to be NP-hard. Solving the metric dimension problem (MDP) and the associated minimal resolving set has many important applications across science and engineering. In this paper, we introduce MaskGNN, a method using a graph neural network (GNN) model to learn the minimal resolving set in a self-supervised manner by optimizing a novel surrogate objective. We provide a construction showing the global minimum of this objective coincides with the solution to the MDP. MaskGNN attains 51%-72% improvement over the best baseline and up to 98% the reward of integer programming in 0.72% of the running time. On this foundation, we introduce Pretraining Position-aware GNNs (PP-GNN) and evaluate on popular benchmark position-based tasks on graphs. PP-GNN's strong results challenge the currently popular paradigm - heuristic-driven anchor-selection - with a new learning-based paradigm - simultaneously learning the metric basis of the graph and pretraining position-aware representations for transferring to downstream position-based tasks.