Implementation of the paper Extrapolating paths with graph neural networks,
by Jean-Baptiste Cordonnier and Andreas Loukas.
Illustration by Arthur Rackham, 1909
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 in path inference is due to 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.
Install a conda environment and the dependencies with ./create_env.sh env_name
.
Data can be downloaded from zenodo and is contained in workspace.zip
.
You can format your own data following the format defined in main.py:load_data()
documentation.
.
├── gretel
| ├── config
| ├── wiki_nll
| └── ...
└── workspace
| ├── chkpt
| ├── trained_model1
| └── ...
| ├── mesh
| ├── planar
| ├── gps
| ├── gps-rnn
| └── wikispeedia
Run
python main.py config/wiki...
If you find this useful, please consider citing the following:
@article{DBLP:journals/corr/abs-1903-07518,
author = {Jean-Baptiste Cordonnier and Andreas Loukas},
title = {Extrapolating paths with graph neural networks},
journal = {CoRR},
volume = {abs/1903.07518},
year = {2019},
url = {https://arxiv.org/abs/1903.07518},
archivePrefix = {arXiv},
eprint = {1903.07518},
timestamp = {Mon, 18 Mar 2019 15:47:28 UTC},
}