  Current Graph Neural Networks (GNN) architectures generally rely on two
important components: node features embedding through message passing, and
aggregation with a specialized form of pooling. The structural (or topological)
information is implicitly taken into account in these two steps. We propose in
this work a novel point of view, which places distances to some learnable graph
templates at the core of the graph representation. This distance embedding is
constructed thanks to an optimal transport distance: the Fused
Gromov-Wasserstein (FGW) distance, which encodes simultaneously feature and
structure dissimilarities by solving a soft graph-matching problem. We
postulate that the vector of FGW distances to a set of template graphs has a
strong discriminative power, which is then fed to a non-linear classifier for
final predictions. Distance embedding can be seen as a new layer, and can
leverage on existing message passing techniques to promote sensible feature
representations. Interestingly enough, in our work the optimal set of template
graphs is also learnt in an end-to-end fashion by differentiating through this
layer. After describing the corresponding learning procedure, we empirically
validate our claim on several synthetic and real life graph classification
datasets, where our method is competitive or surpasses kernel and GNN
state-of-the-art approaches. We complete our experiments by an ablation study
and a sensitivity analysis to parameters.
