Extrapolating paths with graph neural networks
This addresses path prediction for agents in networks, such as drivers or users, but is incremental as it builds on existing graph neural network methods.
The paper tackles the problem of path inference, predicting missing nodes in a path prefix, focusing on natural paths like GPS traces or Wikipedia navigation, and introduces Gretel, a graph neural network that efficiently extrapolates paths and shows favorable performance in experiments.
We consider the problem of path inference: given a path prefix, i.e., a partially observed sequence of nodes in a graph, we want to predict which nodes are in the missing suffix. In particular, we focus on natural paths occurring as a by-product of the interaction of an agent with a network---a driver on the transportation network, an information seeker in Wikipedia, or a client in an online shop. Our interest is sparked by the realization that, in contrast to shortest-path problems, natural paths are usually not optimal in any graph-theoretic sense, but might still follow predictable patterns. Our main contribution is a graph neural network called Gretel. Conditioned on a path prefix, this network can efficiently extrapolate path suffixes, evaluate path likelihood, and sample from the future path distribution. Our experiments with GPS traces on a road network and user-navigation paths in Wikipedia confirm that Gretel is able to adapt to graphs with very different properties, while also comparing favorably to previous solutions.