TY - CPAPER
AB - 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.
T1 - Extrapolating Paths with Graph Neural Networks
DA - 2019-08-10
AU - Cordonnier, Jean-Baptiste
AU - Loukas, Andreas
PB - IJCAI, Inc.
ID - 267851
KW - graph neural networks
KW - machine learning
KW - paths
KW - data science
KW - wikispeedia
KW - ml-ai
UR - http://infoscience.epfl.ch/record/267851/files/Extrapolating%20Paths%20with%20Graph%20Neural%20Networks.pdf
ER -