Template based Graph Neural Network with Optimal Transport Distances
Authors: Cédric Vincent-Cuaz
Rémi Flamary
Marco Corneli
Titouan Vayer
Nicolas Courty
Venue: NeurIPS 2022 Accept (2022)
Keywords: Optimal Transport
Graph Neural Networks
Graph classification
Graph Representation Learning

Abstract: 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.

Template based Graph Neural Network with Optimal Transport Distances
Cédric Vincent-Cuaz
Rémi Flamary
Univ. Côte d' Azur, INRIA, CNRS, LJAD F-06100 Nice
IP Paris, CMAP, UMR 7641 F-91 120 Palaiseau
www.eeiiiiniiiiieccccccccmoc wwwz@inria.a.....mmcm fr
remi Semi.flamme y
Marco Corneli
Titouan Vayer Univ. Lyon, INRIA, CNRS, ENS de Lyon LIP UMR 5668, F-69342 Lyon titouan. wwyer
Univ. Côte Azur, INRIA, CNRS, LJAD F-06100 Nice
marco. corcoe.oomeliiinnee
Nicolas Courty Univ. Bretagne-Sud, CNRS, IRISA
F-56000 Vannes
nicolas. courtyeirisa.fr
Abstract
Current Graph Neural Networks (GNN) architectures generally rely on two impor- tant components: node features embedding through message passing, and aggrega- tion with a specialized form pooling. The structural (or topological) information is implicitly taken into account in these two steps. We propose in this work 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 (FGW) distance,
to an optimal transport distance: the Fused Gromov which encodes simultaneously feature and structure dissimilarities by solving a soft graph-matchine matching problem. We postulate that the vector of FGW distances to set of template graphs has strong discriminative power, which then fed 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 also learnt in end-to-end fashion by differentiating through this layer. After describing the corresponding learning procedure, validate our claim on several synthetic and real life graph classification datasets, where our method is competitive surpasses kernel and GNN state-of-the-art approaches. We complete our experiments by an ablation study and a sensitivity analysis to parameters.
empirically
Introduction
Attributed graphs are characterized by i) the relationships between the nodes of the graph (structural
topological information) and ii) specific features attributes endowing the nodes themselves.
Learning from those data is ubiquitous in many research areas 3 e.g. image analysis [21] 8].
brain connectivity (30]. biological compounds (23] social networks [69], to name few. Various
methodologies approach the inherent complexity of those data, such as signal processing [54]
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

TFGW layer
(C Fy. [1)
Learnable
FGW.
V/
CC2. Fx, bu)
(C...(F.) h.
PGW.
Di
MLP
Qu
FGW.
RR
Templates (Cx. Fic
GNN
Figure 1: Illustration of the proposed model. (left) The input graph is represented as triplet (C,, F., h4) where the matrix C, encodes the structure, F, the features, h, the nodes' weights. A GNN &n is applied to the raw features in order to extract a meaningful node representations. (center) The TFGW layer is applied to the filtered graph and provides vector representation as FGW distances to templates. (right) a final MLP vo is applied to this vector in order to predict the final output of the model. All objects in red are parameters that are learned from the data.
Bayesian and kernel methods on graphs 41 29 or more recently Graph Neural Networks (GNN) 664 in the framework of the geometric deep learning 7
We interested in this work in the classification of attributed graphs at the instance level. One existing approach consists in designing kernels that leverage topological properties of the observed graphs 17 9 (3). For instance, the popular Weisfeiler-Lehman (WL) kernel [52] iteratively aggregates for each node the features of its k-hop neighborhood. Alternative approaches aim at learning vectorial representations of the graphs that can encode the graph structure (i.e. graph representation learning (10)). In this domain, GNN lead to state-of- oof-the-ttttrr-t- art performances with end- to-end learnable embeddings (64). At a given layer, these architectures typically learn the node embeddings via local permutation invariant transformations aggregating its neighbour features [37 25 20 67 In order obtain representation of the whole graph suitable for classification, GNNs finally operate pooling 226 40) of the node embeddings, either global (e.g summation over nodes 67
or hierarchical (e.g by iteratively clustering nodes [71 70 32).
Another line of works targets the construction of meaningful distances that integrate simultaneously the structural and feature information, and that are based on optimal transport (OT) 66 46). Originally designed to compare probability distributions based on a geometric notion of optimality, it allows defining very general loss functions between various objects, modeled as probability distributions. In a nutshell, it proceeds by constructing coupling between the distributions that minimizes a specific cost. Some approaches dealing with graphs rely on non- parameerree models that first embed the graphs into a vectorial space and then match them via OT 43
56 27 35]. Recently [ proposed the OT-GNN model, that embeds a graph as a vector of the Wasserstein distances between the nodes' embeddings (after GNN pre- (re-processing) and learnt point clouds, acting as templates.
Building further from OT variants, the Gromov-Wassersee Wasserstein (GW) distance (39] directly handles graphs through the symmetric matrix C' that encodes the distance/similarigy between every pairs of nodes (e.g. adjacency, shortest path) and weight vector h the nodes encoding the nodes' relative
importance. GW has proven to be useful for tasks such as graph matching and partitioning [66] [5]
or unsupervised graph dictionary learning 65 63 62
GW has been also extended directed graphs (14) and to attributed graphs via the Fused Gromov-Wasserstch Wasserstein (FGW) distance [59 (58).
that realizes a trade-off between an OT distance with a cost on node features and the GW distance between the similarity matrices. Despite its recent successes on complex unsupervised tasks such as graph clustering [65] 63 62]. FGW has never been explored as part of an end-to-end model for graph classification. In this work, we fill this gap by introducing a novel "layer" that embeds an attributed graph into vector, whose coordinates are FGW distances to few (learned) graph templates. While FGW can be performed directly on raw data (i.e. the input structured graph without any pre-procsssing). we also consider the case where features representations are learnt from a GNN, similarly to OT-GNN M. and thus also realizing a particular type of aggregation.

---

Contributions. We introduce a new GNN layer, named TFGW for Template-based FGW and illustrated in the center of Figure From an input graph, it computes vector of FGW distances to learnable graph templates. This layer that can be seen as an alternative to global pooling layers and can be integrated into any neural network architecture. We discuss its properties and the associated invariances. We detail the optimization strategy that enables learning simultaneously GNN pre- processing layers and graph templates relevant for a downstream task in an end-to-end fashion. We empirically demonstrate the relevance of our model in terms of performances compared to several state-of-the-arr architectures. Remarkably, we show that a simple GNN model leveraging on our new layer can surpass oate-offttheart performances by relatively large margin. Finally, we also provide some illustrative interpretations of our method and a sensitivity analysis of our model parameters.
Fused Gromov- Wasserstein template based layer
In order to describe our novel template-based GNN layer we first introduce more formally the FGW distance and its properties. In the following denote by Σ, {h E R Σ, h2 1} the probability simplex with n-bins, and by (A) the set of symmetric matrices of size n taking values in A R.
2.1 Fused Gromov-Wassee Wasserstein distance
An undirected attributed graph 9 with n nodes can be modeled in the OT context as tuple (C, F. h). where E S, (R) is a matrix encoding relationships between nodes, = (fi, fn) E Raxd is node feature matrix and h E Σ,, is vector of weights modeling the relative importance of the nodes within the graph (Figure [T] left). Without any prior knowledge, uniform weights can be chosen (h 1n)n). The matrix C' can be the graph adjacency matrix, the shortest- path matrix any other description of the node relationships (i.e. the topology) of the graph [47] [1).. Let us now consider two such graphs (C, F, h) and (C, F, h), of respective sizes n and πi (with possibly n + π). The Fused Cromov-Wassersee (FGW) distance is defined for E [0, 1] as [58] [5]]
F.W.CCCFF,,..FFF.. = min Teu ijht
[a((Ci - -Ma)²
2 + (1 a) IalB) TueT (I)
1, = - h} is the set of admissible coupling between h and h. FGW aims at finding an optimal coupling T* by minimizing a trade-off cost, via a, between a Wasserstein (W) cost the features and both sharing the same coupling. The optimal coupling T' acts as a soft matching of the nodes, which tends to associate pairs of nodes that have similar pairwise relations C and C (GW cost), and similar features in F and F (W cost).
where (h, h= : ER
(GW) cost the similarity matrices,
Interestingly, FGW defines a metric on the space of attributed graphs. In particular, if C and C phottest-path matrices, the FGW distance vanishes if and only if the two attributed graphs are the same up to a permutation [59] Theorem 3.2]. Such invariance involves that two graphs strongly isomorphic according to Weisseiler-Lehman base tests [33 56) will have zero FGW distance for any a and, more importantly, F FGW,, & = 0 implies that the graphs are strongly isomorphid) When C, C are any symmetric matrices, we can mention that GW (a = 1) also defines a pseudo-distanee
155
Theorem 5.8] with respect the notion of weak isomorphism [55] 15
Solving for FGW. The optimization problem T is a non-convex quadratic program (59 equation 6]. whose non-convexity comes from the GW cost. A possible optimization procedure to solve this problem is a Conditional Gradient (CG) algorithm. which is known to converge to a local optimum 31]. The computational complexity of each iteration is O + 7²n)) [47] Thus, if two graphs of considerably different sizes are considered, the complexity is quadratic with respect to the largest size. Existing attempts reduce this computational cost either exploit entropic regularization of OT
47 50
or graph partitioning 666 13
$ 'Two graphs (C, F, h) and (C,F,, F,h) are strongly isomorphic 72 and there exists a permutation
matrix P E {0, 1)axn such that C PCP F PF and h = Ph
3

---

2.2 Template-based (T)EGW Graph Neural Networks
Building upon the FGW distance and its properties, we propose simple layer for GNN that takes a graph (C, F, h) as input and computes its FGW distances to a list of K template graphs
G = (Ck, FE, hxx) kEeeK] as follows:
TFGW G. FC) = (C, FR,h))) K
(2)
We postulate that this graph representation can be discriminant between the observed graphs due to FGW. This claim relies on the theory of [2] allowing one to learn provably strongly discriminant classifiers based on the distances from the observed graphs and templates that are sampled from the dataset (see e.g. [48] adopting the Wasserstein distance). However such an approach often requires a large amount of templates which might be prohibitive if the distance is costly compute. Instead, we propose to learn the graph templates G in supervised manner. In the same way, we also learn the trade-off parameter a on the data. As such, the TFGW layer can automatically adapt to the data whose discriminating information can be discovered either in the features in the structure of the graphs, or a combination of the two. Moreover, the template structures can leverage on any type of input representation C, since they are learnt directly from the data. Indeed, in the numerical experiments we implemented the model using either adjacency matrices (ADJ) that provide more interpretable templates (component Cij E [0, 1] can be seen as a probability of link between nodes) or shortest path matrices (SP) that are more complex to interpret but encode global relations between the nodes.
The TFGW layer can be used directly as a first layer to build a graph representation feeding a fully connected network (MLP) for e.g. graphs classication. In order to enhance the discriminating power of the model, we propose to put a GNN (denoted by ou and parametrized by u) on top of the TFGW layer. We assume in the remainder that this GNN model o. is injective in order preserve isomorphism relations between graphs (see (67] for more details). With a slight abuse of notation, we write du (F) denote the feature matrix of observed graph after being processed by the GNN.
Learning with TFGW-GNN. We focus on a classification task where we observe a dataset of I graphs {9,- (C2, Fú, h4) het with variable number of nodes {n, hee( and where each graph is assigned to a label y/s E y, with y a finite set. The full model is illustrated in Figure []] We first process the features of the nodes of the input graphs via the GNN ou. then use the TFGW layer to represent the graphs as vectors in IR K Finally we use the final MLP model th R -> y parameterized by v, to predict the label for any input graph. The whole model is learned in
end-to-end fashion by minimizing the cross-entropy loss on the whole dataset leading to the following optimization problem
I i
Σ
C (u (TRGW (Ci, du (Fi) (F).))))))) hi))
min
u.u. (...
Notable parameters of (3) are the template graphs in the embeddings (CC,, hw)) and more precisely their pairwise node relationship Ck. node features F; and the distribution on the nodes hg on the simplex. The last parameter reweighs individual nodes in each template and performs nodes selection when some weights are exactly 0 (3 62). Finally, the global parameter a is also learnt from the whole dataset. Although it is possible to learn a different a per template, we observed that this extra level of flexibility prone to overfitting, and we will not consider in the experimental section.
Optimization and differentiation TFGW. We propose to solve the optimization problem in 33 using stochastic gradient descent. The FGW distances are computed by adapting the conditional gradient solver implemented in the POT toolbox [18]. The solver was designed to allow backward propagation of the gradients w.r.f. all the parameters of the distance and was adapted to also compute the gradient w.r.t. the parameter a. The gradients are obtained using the Envelop Theorem M allowing to keep T constant. We used Pytorch [45 to implement the model. The template structure Ct, node weights h and are updated with projected gradient respectively on the set of symmetric matrices Sn, (R+) (Sm, ([0, 1)) when C, are adjacency matrices), the simplex Exx, and [o, 1). The projection onto the probability simplex of the node weights leads to sparse solutions [16), therefore

---

the size of each (Ck, Fx.h)) can decrease along iterations hence reducing the effective number of their parameters optimize. This way the numerical solver can leverage on the fact that many computations are unnecessary as soon as the weights are set to zero. Note that the FGW solver from POT uses an OT solver implemented in C++ on CPU which means that comes with some overhead (memory transfer between GPU and CPU) when training the model on GPU. Still the multiple FGW distances computation has been implemented in parallel on CPU with a computational time that remains reasonable in practice (see experimental section 3.3). While GPU solver can be found when using entropy regularized FGW, it introduces a new parameter related to the regularization strength which is more cumbersome to set, and that we did not consider it in the experiments.
Properties of the TFGW layer. We now discuss property of the proposed layer resulting from the properties of FGW (see Section 2.Ib. We have the following result:
Lemma The TFGW embeddings are invariant strong isomorphism.
This lemma directly stems from the fact that FGW is invariant strong isomorphism of one of its inputs. This proposition implies that two graphs with any aforementioned representation which only differ by permutation of the nodes will share the same TFGW embedding. Moreover such property holds for any mapping dh which is injective, such as a Multi-Layer Perceptron (MIP) [2 or any GNN with
aggregation scheme as described in 67
Moreover, the optimal coupling T resulting from TFGW between (Ci, Pu (F)); h;) and the tem-
plate (C&, Fs, hg), will encode correspondances between the nodes of the graph and the nodes of the template that will be propagated during the backward operation. The size of the inputs, the size of the templates and their respective weight hgg will play crucial role regarding this operation. Also note that, since the templates are estimated here to optimize a supervised task, they will promote discriminant distance embedding instead of graph reconstruction quality as proposed in other FGW unsupervised learning methods 63 62).
3 Numerical experiments
This section aims at illustrating the performances of our approach for graph classification in synthetic and real-world datasets. First, we showcase the relevance of our TFGW layer on existing synthetic datasets known to require expressiveness beyond the WL-test (Section 3.1. Then we benchmark our model with state-of-the-an approaches on well-known real-world datasets (Section 3.2p. discuss our results through sensitivity analysis of our models (Section 3.3
We finally
3.1 Synthetic datasets beyond WL test
Identification of graphs beyond the WL. test is one impor-
Table 1: Average accuracy on synthetic datasets (10 simulations).
tant challenge faced by the GNN community. to test the ability of TFGW to handle such fundamen- tally difficult problems we consider two synthetic datasets: contains graphs with (possibly) dis- connected cycles where the label y; is the presence of cycle of length 4; SKIP-CIRCLES
order
model 4CYCLLS
SKIP-CIRCLES
TFGW
0.99(0.03)
1.00(0.00)
4-CYCLES 34 44
TFGW-fix
0.63(0.11)
1.00(0.00)
GIN
0.50(0.00)
O. 10K00,000
DropGIN
1.00(0.01)
0.82(0.28)
[12] contains cir-
cular graphs with skip links and the labels (10 classes) are the lengths of the skip links among 3, 5, 6, 9, 11, 12, 16).
We compare the performances of the TFGW layer for embedding such graphs with GIN designed to be at least as expressive as the WL test, and DropGIN [44] which proposed successful dropout technique to overcome some drawbacks of GIN. We replicate the benchmark of [44) by considering for both GIN and DropGIN, 4 GIN layers for 4-CYCLES, and 9 GIN layers for SKIP- CIRCLES as the skip links can form cycles of up to 17 hops. Since the graphs do not have features we use directly the TFGW on the raw graph representation with = I hence computing only the GW distance. The GNN methods above artificially adds a feature equal to 1 on all nodes as they have the same degree. For these experiments use adjacency matrices for C, and we
Code available
5

---

Table 2: Test set classification accuracies from 10-fold CV. The first (resp. second) best performing method is highlighted bold (resp. underlined).
Calegory
model
MUTAG
PTC
ENZYMES
PROTEIN
NCT
IMDB B
IMDIEM
COLLAB
Chirs
TFGW ATI (2)
96.3(3.3)
72.415771
75.844.0)
82.92.7
88.(22.5
78.3(3.7)
56.8(3.1)
84.3(2.6)
TFGW SP (L=2)
94.8(3.5)
70.866.3)
75.155.0)
82.03.0)
86.1(2
74.1(5
54.90399)
80.9(3.1)
OEGGNN (1:22)
91.604.0
68.01 .5]
66.9(3.8)
76.64.))
82.9(211)
67.5(33)
52.1(3.0)
N0.7(2.9)
OT-GNN (l=4)
92.1(3.7)
65.4(9.6)
67.3(4.3)
78.05.1)
83.6(255
69. 1(4.4)
51.9(2.8)
82.1
WRGI.
91.0K3.4)
66.012.4) 4)
60.0(2.8)
73.7(1.9)
75.5(1.4)
66.4(2.1)
50.3(1.0)
79.6(0.5)
GNN
PATCHYSAN
91.66.0)
58.9137)
55.044.5)
75.105.3)
76.9(2.3
02.9(3.9)
45.942.51
12277
GIN
(0.1(4.4)
(3.9(
62.2(3.6)
76.2(288)
82.2(008)
(4.3(3.1)
50.9(1.7)
79.3(1.71
DropGIN
89.816.2)
62.3(6.8)
65.8(2.7)
76.9K4.3)
81.9(2.5)
66.3(4.5)
51.6(3.2)
80.1(2.8)
PPGN
90.4(5.6)
63.6(6.0)
66.9X4.3)
77.1(4.0)
82.7(1.8)
67.2(4.1)
51.342.8)
81.0(211)
DIFFPOOL
86.1(2.0)
45.065.2)
61.0(3.1)
7L7(1.4)
80.9K0.7)
6(.1(2.0)
45.8(1.4)
(0.8(1))
Kemels
FGW ADJ
82.67.22
58.368.0)
72.2(4.0)
72.4(4.7)
74.4(21)
7..8
48.9(1.9)
80.011
FGW SP
84.4(7.3)
55.5(7.0)
70.566.2)
74.3(3.3
72.5(1.5)
65.0(4.7)
47.8(3.8)
77.8(2.4)
WL
87.4(5-4)
56.0(3.9)
69.5(3.2)
74.4(2.6)
85.6(1.2)
67.5(4.0)
(8.5544.2
78.5(1.7)
WWL
86,3(7.9)
52.6(6.8)
71.445.1)
73.1(1.4)
85.7(0.8)
71.6(3.8
52.6(3.0)
81.4(2.))
Gain with TFOW
4.3
4,4
2.9
4,9
2.4
5.3
4.2
2.9
investigate two flavours of TFGW: 1) in TFGW-fx we fix the templates by sampling one template
per class from the training dataset (this can be seen as a simpler FGW feature extraction); 2)
for TFGW learn the templates from the training data (as many
the number of classes) as proposed in the previous sections. Results are
4CYCLES: accuracies over K
averaged over 10 runs and reported in Table T TFGW based methods perform very well on both datasets with impressive results on SKIP- CIRCLE when GNN have limited performances. This is due the fact that different samples from one class of SKIP-CIRCLE are generated by permuting nodes of the same graph and FGW distances are invariant to these permutations. 4-CYCLES has more complex structure with intra-class heterogeneity and requires more than two templates to perform as good as DropGIN. To illustrate this we have computed the accuracy on this dataset as function of the number of templates in Figure for
1.0
0.8
0.6
TFOW
TFGW-Ix
Figure 2: Test accuracy distributions by number of templates either fixed or learned.
2 We can see that a perfect classification is reached up to K TFGW, while TFGW-fix still struggles to generalize at = 20. This illustrates that learning the templates is essential to keep K (and numerical complexity) small while ensuring good performances.
3.2 Graph classification benchmmark
We now evaluate and compare the performances of our TFGW GNN with number of state-of-the-art graph classifiers, from kernel methods GNN. The numerical experiments are conducted on real life graph datasets to provide a fair benchmark of all methods on several heterogeneous graph structures.
Datasets. We use 8 well-known graph classification datasets 24) 5 bioinformatics datasets among which 3 have discrete node features (MUTAG, PTC, NCII 28 52 and 2 have continuous node features (ENZYMES, PROTEINS (6) and 3 social network datasets (COLLAB, IMDB-B, IDBM-M 669) In order to analyse them with all methods, we augment unattributed graphs from social networks with node degree features. Detailed description and statistics on these datasets are reported in the supplementary material.
Baselines. We benchmark our approaches the following state-of-the-art baselines for graphs classification, split into 3 categories: i) kernel based approaches. including FGW [59] operating on adjacency and shortest-path matrices, the WL subtree kernel [52] WL] and the Wasserstein WL kernel [56) WWL]. For these methods that do not require a stopping criterion dependent on validation set, we report results using for parameter validation 10-fold nested crossvvalidation [59] 29 repeated 10 times. ii) OT based representation learning models, including WEGL [27] and OT-GNN [I]. iii) GNN models, with global or more sophisticated pooling operations, including PATCHY-SAN (4 DIFFPOOL [70]. PPGN (36]. GIN [67] and its augmented version through structure perturbations DropGIN 44 For all these methods, we adopt the hyper-parameters suggested in the respective papers, but with slightly different model selection scheme, as detailed in the next paragraph.

---

Benchmark settings. Recent GNN literature [37 67 36 44 successfully addressed many limita- tions in terms of model expressiveness compared the WL tests. Within that scope, they suggested to benchmark their models using a 10-fold cross- volss-valiationn (CV) where the best average accuracy on the validation folds was reported. We suggest here to quantify the generalization capacities of GNN based models by performing 10-fold cross validation with a holdout test set never seen during training. For each split, we track the accuracy on the validation fold every 5 epochs, then the model whose parameters maximize that accuracy is retained. Finally, the model used to predict the holdout test set is the one with maximal validation accuracy averaged across all folds. This setting is more realistic than simple 10-fold CV and allows a better understanding of the generalization performances [4). This point explains why some existing approaches have here different performances than those reported in their original paper.
For all the TFGW based approaches we empirically study the impact of the input structure represen- tation by considering adjacency (ADJ) and shortest-path (SP) matrices C, For all template based models, we set the size of the templates to the median size of the observed graphs.
We validate the number of templates K in { with 3 E {2, 6,8} and | the number of classes. Only for ENZYMES with 6 classes of 100 graphs each, we validate 3 E {1, 2, 4]. All
parameters of our TFGW layers highlighted in red in Figure [ are learned while Φu is a GIN
architecture [67] composed of L layers aggregated using the Jumping Knowledge scheme [68] known to prevent overfitting in global pooling frameworks. For OT-GNN we validate the number of GIN layers in {2, 4). Finally for fairness, we validate the number of hidden units within the GNN layers and the application of dropout on the final MLP for predictions, similarly to GIN and DropGIN.
Results analysis. The results of the comparisons in terms of accuracy are reported in Table 2 Our TFGW approach consistently outperforms with significant margins the state-of-the-art approaches from all categories. Even if most of the benchmarked models can perfectly fit the train sets by learning implicitly the graphs structure [67 44, 36), enforcing such knowledge explicitly as our TFGW W layer does (through FGW distances) leads to considerably stronger generalization performances. On 7 out of 8 datasets, TFGW leads to better performances while operating on adjacency matrices (TFGW ADJ) than shortest-path ones (TFGW SP). Interestingly, this ranking with respect those rep- resentations does not necessarily match the one of the FGW kernel which extracts knowledge from the graph structures C, through FGW, our TFGW layer. These different dependencies to the provided inputs may be due to the GNN pre-processing of node features which suggests the study of its ablation.
Finally to complete this analysis, we report in Table 3 the number of parameters of best selected models across various methods, for the dataset PTC. We refer the reader interested in an extended benchmark to the supplemen- tary material. Our TFGW leads to better classification performances while having comparable number of param- eters than these competitors. We also reported for these models, their averaged prediction time per graph. These measures were taken on CPUs (Intel Core i9. 99-9900K CPU, 3.60 GHz) in order to fairly compare the numerical com- plexity of these methods, as OT solver used in TFGW and OT-GNN are currently limited to these devices (see the detailed discussion in Section 2. Although the theoretical complexity of our approach at most cubic the number of nodes, we still get in practice a fairly good speed for classifying graphs, in comparison to the other competitive methods.
Table 3: Number of parameters and av- eraged prediction time per graph.
model
PTC
parameters
runtimes (ms)
(ours) TFGW
25.
12.1
OT-GNN
30.8k
7.6
GIN
29.9k
0.19
DropGIN
44.1k
14,3
3.3 Ablation study, sensitivity analysis and discussions
In this section we inspect the role of some of the model parameters (a in FGW, weights estimation in the templates, depth of the GNN Φi)) in terms of the classification performance. To this end, we first conduct on all datasets an ablation study on the graph template weights he and the number of GIN layers in du. Then, we take a closer look at the estimated trade-off parameters a and provide a sensitivity analysis w.r.f. the number of templates and the number of GIN layers.
we benchmark the following settings for our TFGW models: for adjacency (ADJ) and shortest path (SP) representations C,, we
Ablation Study. Following the same procedure as Section 3.2
7

---

Table 4: Classification results from 10-fold cross-validation of our TFGW models in various
scenarios: for I. E {0, 1, GIN layers, we either fix templates weights h2 to uniform distributions
or learn them. The first and second best performing method are respectively highlighted in bold and underlined.
model
inputs
hy
MUTAG
ENZYMES
PROTEIN
NCI1
IMDB
IMDB
COLLAB
TFGW (L=))
AD]
uniform
(4.35
63.0(5.0)
67.4(7.)
78.02.0)
80.3(1.5
69.512.5)
49.7(4 1)
78.7(3.1)
ADJ
leamt
94.2(3.0)
64.9(4.1)
72.1(5.5)
78.8(2.2)
82.1(2.5)
71.3(4.3)
52.M2.5)
80.9(2.7)
SP
uniform
94.8(3.7)
66.5(6.7)
72.7(6.9)
77.5(2.4)
79.6(3.7)
68.104.4)
48
78.4(3.4)
SP
leamt
95.964.1)
67.915.8)
75.1(5.6)
79,5(2.9)
83.9(2.0)
72.66311)
53.1(2.5)
79.8(2.5)
TFOW(E=))
ADJ
learni
94.8(3.1)
68.7(5.8)
72.7(5.1)
81.3(288
85.4
76.30439
55.912
82
SP
leamt
95.4(3.5)
70.915.5)
74.944.8
82.1(3.4)
85.7(3.1)
73.8(4.8)
54.2(3.3)
12.55
TFOW (L=2)
ADJ
learnt
96.4(3.3)
72.4(5.7)
73.8(4.6)
82.9(2.7)
88.1(2.5)
78.3(3.7)
56.8(3.1)
84.3(2.6)
SP
leart
94.8(3.5)
70.8(6.3)
(5.1(5.0)
82.03300
26.1
74.105.4)
54.9(3.9)
80.9(3.1)
unbeddding
layers
Sampto
tompletas
SeT pldda
40
20
32
10
033
15 1E
-02.03
Figure 3: PCA projections of the template based embeddings for different models and number of templates. (need to debug colors)
learn the distance layers either directly, on the raw data (i.e. L L= 0, ou = id), or after embedding the data with (L = 1) or (L 2) GIN layers. For L we either fix the graph template weights h& uniformly or learn them. The results (test accuracy) are reported in Table Learning the weights systematically improves the generalization capabilities of our models of at least 1% or 2% for both ADJ and SP graph representations. For a given number of graph templates, the weights learning allows better fit the specificities of the classes (e.g. varying proportion of nodes in different parts of the graphs). Moreover, as weights can become sparse in the simplex during training they also allow the model to have templates whose number of nodes adapts to the classification objective, while bringing computational benefits as discussed in Section 2.2 Those observations explain why we learnt them by default in the benehmark of the previous subsection.
Next, we see in Table 4 that using GNN layers as preppoceesiing for our TFGW layer enhances generalization powers our models, whose best performances are obtained for 2. Interestingly, for L = 0, TFGW with SP matrices outperforms TFGW with ADJ matrices, meaning that the shortest path distance brings more discriminant information on raw data. But when L > 1 (i.e. when GNN pre-prccesses the node features), TFGW with ADJ matrices improves the accuracy. An explanation could be that the GNN ou can somehow replicate (and outperform) a SP metric between nodes. This emphasizes that the strength of our approach clearly exhibited in Table 2 lies in the inductive bias of our FGW distance embedding. This last point is further reinforced by additional experiments reported in the supplementary material, where GIN layers (used by default for our TFGW model) are replaced by GAT layers [60]
Importance of the structure/feature aspect of FGW. To the best of our knowledge we are the first to actually learn the trade-off parameter of FGW in supervised way. For this matter,
Leartt alphas on PTC for Km4
Leamt alphas on IMD6-8 for K-4
Lwg
0.7
0.6-
Lx2
0.5
we verify that our models did not converge to degenerated solutions where either the structure are omitted. To this end we report in Figure T the distributions of the estimated a for some models learnt on datascts PTC and IMDB-B BB, where features are respectively existing in the datasct or created using
0.4
0.3
0,5
0,4
0.1
(a = 0) or the features (a
ADJ
SP
ADJ
SP
Figure 4: Distributions of estimated a.
8

---

node degrees. We can see that for both kinds of input graph representations, parameters are strictly between 0 and 1. One can notice the variances of those distributions illustrating the -onuuquuesssss of this trade-off parameter coming from the non-convexity of our optimization problem (a given value of a can potentially be compensated by the scaling of the GNN output). Unfortunately, the analysis of the real relative importance between structures and features can not be achieved only by looking at those values as the node embeddings and templates are different across models and data splits.
Visualizing the TFGW embedding. In order to interpret the TFGW embedding, we illustrate in Figure 3 the PCA projection of our distance embeddings learned on PTC with L 0 and L templates K varying in {4, 8j. For this experiment, we have chosen the PCA because it allows to have more interpretable low dimensional projection that preserves the geometry compared to local neighbourhood based embeddings such as TSNE [57] or UMAP [8]. As depicted in the figure, the learned templates extreme points in the embedding space of the PCA. This result is particularly interesting because existing unsupervised FGW representation learning methods tend toward estimating templates that belong to the data manifold, to form a "convex enveloppe" of On the contrary, the templates learned through our plane in the PCA space while the samples evolve orthogonally to
and the number
the data to ensure good reconstruction 63 65 approach seem to be located this plane (when the FGW distance increases). In a classification context, this means that the learned templates will not actually represent realistic graphs from the data but might encode "exaggerated" or "extreme" features in order to maximize the margin between classes in the embedding. To reinforce this intuition, added plots of the estimated templates in the supplementary. Finally, in the figure, the samples are coloured w.r.f. their class and the templates are coloured by their predicted class. Interestingly, the classes are already well separated with templates but the separation clearly non-linear whereas using GNN pre-processing and a larger number of templates leads to linear separation of the two classes.
Sensitivity to the number of tem- plates and GNN layers. To illus-
PTC test accuracies depending on and
trate the sensitivity of our TFGW
80
layer to the number of templates K and the number of GNN layers in Φu. we learned our models on the PTC dataset with L varying in {0, 2, 3, 4]. We follow the same procedure than in the benchmark of Section 3.2 regarding the validation of and the learning process, while fixing the number of hidden units in the GNN layers to 16. The test accu- racy distributions for all settings reported in Figure Two phases are clearly distinguishable. The first one for L S 2, where for each L we see that the performance across the number of templates steadily increases, and the second for L > 2 where this performance progressively decreases as a function of L. Moreover, in the first phase performances are considerably dependent on K to compensate for simple node representation, while this dependency is mitigated in the second which exhibits a slight overfitting. Note that these deeper models still lead competitive results in comparison with benchmarked approaches in Table with best averaged accuracies of 70.6 (L- = 3) and 67.4 (L- 4). On one hand, these observations led us set our number of layers to T, = 2 for all benchmarked datasets which lead to strong generalization power. On the other hand, deeper models might be way to benefit from our FGW embeddings with very few templates which can be interesting from a computational perspective on larger graph datasets.
Accuracio es
70
65-
60
50
K=44 Km8
K=12
K-16
3
4
Number of layers L
Figure 5: Test accuracy distributions by number of templates and number of GNN layers.
Conclusion
We have introduced a new GNN layer whose goal is to represent a graph by its distances to template graphs, according to the optimal transport metric FGW. The proposed layer can be used directly on raw graph data as the first layer of GNN or can also benefit from more involved node embedding using classical GNN layers. In a graph classification context, we combined this TFGW layer with

---

simple MLP model. We demonstrated on several benchmark datasets that this approach compared favorably with state-of-the woffthe-art GNN and kernel based classifiers. A sensitivity analysis and an ablation study were presented to justify the choice of several parameters explaining the good generalization performances.
We believe that the new way to represent complex structured data provided by TFGW will open the door to novel and hopefully more interpretable GNN architectures. From a practical perspective, future works will be dedicated to combine TFGW with fast GPU solvers for network flow [51]. This would greatly accelerate our approach and more generally OT based deep learning methods. We also believe that the FGW distance and its existing extensions can be used with other learning strategies including semi-relaxed FGW [62] for sub- uub-graph detection.
Acknowledgements
This work is partially funded through the projects OTTOPIA ANR20-CHIA-0030 and 31A Côte d' Azur Investments ANR-19-P3IA-0000 of the French National Research Agency (ANR). This research was supported by 3rd Programme d' Investisseements d' Avenir ANR-18- T1R-18-EUR-0000--11 This action benefited from the support of the Chair "Challenging Technology for Responsible Energy" led by 1'X- Ecole polytechnique and the Fondation de I'Ecole polytechnique. This work supported by the ACADEMICS grant of the IDEXLYON, project of the Université de Lyon, PIA operated by TER-16-IDEX-0055 This project was supported in part by the AlsegroAssai ANR project ANR-19-CHIP CHIA-0009. The authors are grateful to the OPAL infrastructure from Université Côte Azur for providing resources and support.
References
[1] S. Afriat. Theory of maxima and the method of lagrange. SIAM Journal on Applied Mathematics, 20(3):343-357, 1971.
[2] M.-F Balcan, A. Blum, and N. Srebro. A theory of learning with similarity functions. Machine Learning, 72(1):89-11 112, 2008
[3] P. W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzalez V. Zambaldi, M. Malinowski, A. Tacchetti, D. Raposo, Santoro, R. Faulkner, C. Gulcehre, Song, Ballard, J. Gilmer, G. Dahl, A. Vaswani. K. Allen, C. Nash, V. Langston, C. Dyer, N. Heess, D. Wierstra, P. Kohli, M. Botvinick, O. Vinyals, Y. Li, and R. Pascanu. Relational inductive biases, deep learning, and graph networks, 2018
[4] Y. Bengio and Y. Grandvalet. No unbiased estimator of the variance of k-fold cross-validation. Advances in Neural Information Processing Systems, 16, 2003.
[5] K. M. Borgwardt and H.-P Kriegel. Shortest-path kernels on graphs. In Fifth IEEE international conference on data mining (ICDM'05) pages 8-pp. IEEE, 2005.
[6] K. M. Borgwardt, C. S. Ong, S. Schönauer, S. Vishwanathan, A. J. Smola, and H.-P. Kriegel. 1):47-i56. 2005.
Protein function prediction via graph kernels. Bioinformatics,
[7] M. M. Bronstein, Bruna, T. Cohen, and Velivcković. Geometric deep learning: Grids, groups, graphs, geodesics, and gauges. ArXiv, abs/2104.13478, 2021.
[8] M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18-4) 2017.
[9] L. Buitinck, G. Louppe, M. Blondel, F. Pedregosa, A. Mueller, O. Grisel, V. Niculae, P. Pretten- hofer, A. Gramfort, J. Grobler, R. Layton, J. VanderPlas, A. Joly, B. Holt, and G. Varoquaux. API design for machine learning software: experiences from the scikit-learn project. In ECML PKDD Workshop: Languages for Data Mining and Machine Learning, pages 108-122, 2013.
[10] I. Chami, S. Abu-El-Haija, B. Perozzi, C. Ré, and K. Murphy. Machine learning on graphs: A model and comprehensive taxonomy. Journal of Machine Learning Research, 23(8)) 2022.
10

---

[11] B. Chen, G. Bécigneul, O.-E. Ganea, R. Barzilay, and T. Jaakkola. Optimal transport graph neural networks. arXiv preprint arXiv:2006.04800 2020.
[12] Z. Chen, S. Villar, L. Chen, and J. Bruna. On the equivalence between graph isomorphism testing and function approximation with gnns. Advances in neural information processing systems, 32, 2019.
[13] S. Chowdhury, D. Miller, and T. Needham. Quantized gromov-wasserseee In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 811-827. Springer, 2021.
[14] Chowdhury and F. Mémoli. The Gromov- -nasov-Wasserstein distance between networks and stable network invariants. arXiv:1808.044: 04337 [cs, math], Sept. 2019. arXiv: 1808.04337.
[15] S. Chowdhury and Needham. Generalized spectral clustering via gromov-wasserstenn learning. In International Conference on Artificial Intelligence and Statistics, pages 712-720. PMLR, 2021.
[16] L. Condat. Fast projection onto the simplex and the 11 ball. Mathematical Programming, 158(1):575-585 2016.
[17] A. Feragen, N. Kasenburg. J. Petersen, M. de Bruijne, and K. Borgwardt. Scalable kernels for graphs with continuous attributes. Advances in neural information processing systems, 26, 2013.
[18] R. Flamary, N. Courty, A. Gramfort, M. Z. Alaya, A. Boisbunon, S. Chambon, L. Chapel, A. Corenflos, K. Fatras, N. Fournier, L. Gautheron, N. T. Gayraud, Janati, A. Rakotomamoniy, I. Redko, A. Rolet, A. Schutz, V. Seguy, D. J. Sutherland, R. Tavenard, A. Tong, and T. Vayer. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78): 2021.
[19] T. Gärtner, P. Flach, and S. Wrobel. On graph kernels: Hardness results and efficient alternatives. Learning theory and kernel machines, pages 129-143. Springer, 2003.
[20] W. Hamilton, Z. Ying, and J. Leskovec. Inductive representation learning on large graphs. Advances neural information processing systems, 30, 2017.
[21] Z. Harchaoui and F. Bach. Image classification with segmentation graph kernels. In 2007 IEEE Conference Computer Vision and Pattern Recognition, pages 1-8. IEEE, 2007.
[22] K. Hornik, M. Stinchcombe, and H. White. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-366, 1989.
[23] Jumper, R. Evans, A. Pritzel, Green, M. Figurnov, Ronneherger, K. Tunyasuvunakool, R. Bates, A. Žídek, A. Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-58) 2021.
[24] K. Kersting, N. M. Kriege, C. Morris, P. Mutzel, and M. Neumann. Benchmark data sets for graph kernels, 2016.
[25] N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: (tt:::60000290,, 2016.
[26] B. Knyazev, G. W. Taylor, and M. Amer. Understanding attention and generalization in graph neural networks. Advances neural information processing systems, 32, 2019.
[27] S. Kolouri, N. Naderializadeh, G. K. Rohde, and H. Hoffmann. Wasserstein embedding for graph learning. In International Conference on Learning Representations, 2021.
[28] N. Kriege and P. Mutzel. Subgraph matching kernels for attributed graphs. arXiv preprint arXiv: /206://200.483. 2012.
[29] N. M. Kriege, F. D. Johansson, and C. Morris. survey on graph kernels. Applied Network Science, 5(1):1-42, 2020.

---

[30] S. I. Ktena, S. Parisot. E. Ferrante, M. Rajchl, M. Lee, B. Glocker, and D. Rueckert. Distance metric learning using graph convolutional networks: Application to functional brain networks. In International Conference on Medical Image Computing and Compuler-Asisted Intervention, pages 469-477. Springer, 2017.
[31] S. Lacoste-Julien, Convergence rate of frank-wolfe for non-convex objectives. arXiv preprint arXiv:1607.00345, 2016.
[32] J. Lee, I. Lee, and J. Kang. Self-attention graph pooling. In International conference machine learning, pages 3734-3743. PMLR, 2019.
[33] A. Leman. The reduction of graph to canonical form and the algebra which appears therein. 2018.
[34] A. Loukas. What graph neural networks cannot learn: depth width. In International Conference on Learning Representations, 2020.
[35] H. P. Maretic, M. EI Gheche, G. Chierchia, and P. Frossard. Got: an optimal transport framework for graph comparison. In Advances in Neural Information Processing Systems, pages 13876- 13887, 2019.
[36] H. Maron, H. Ben-Hamu, H. Serviansky, and Y. Lipman. Provably powerful graph networks. Advances in neural information processing systems, 32, 2019.
[37] H. Maron, H. Ben-Hamu, N. Shamir, and Y. Lipman. Invariant and equivariant graph networks. In International Conference on Learning Representations, 2019.
[38] L. McInnes, J. Healy, and J. Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv:1802.034466 2018.
[39] Mémoli. Gromov-wasserstein distances and the metric approach to object matching. Foun- dations of computational mathematics, 11(4):417-487, 2011.
[40] D. Mesquita, A. Souza, and S. Kaski. Rethinking pooling in graph neural networks. Advances in Neural Information Processing Systems, 15:2220-2231, 2020.
[41] Y. C. Ng. N. Colombo, and R. Silva. Bayesian semi-supervised learning with graph gaus- sian processes. In Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018
[42] M. Niepert, M. Ahmed, and K. Kutzkov. Learning convolutional neural networks for graphs. In International conference machine learning, pages
PMLR, 2016.
[43] G. Nikolentzos, P. Meladianos, and M. Vazirgiannis. Matching node embeddings for graph similarity. In Proceedings of the Thirty- hirst AAAI Conference on Artificial Intelligence, February 4-9, 2017, San Francisco, California, USA., pages 2429-2435, 2017.
[44] P. A. Papp, K. Martinkus, L. Faber, and R. Wattenhofer. DropGNN: Random dropouts increase the expressiveness of graph neural networks. In Advances in Neural Information Processing Systems, 2021.
[45] A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. Veto,o, Z. Lin, A. Desmaison, L. Antiga, and A. Lerer. Automatic differentiation in pytorch. 2017.
[46] G. Peyré and M. Cuturi. Computational optimal transport. Foundations and Trends in Machine Learning, 1 11:355-66 1:355-607, 2019.
[47] G. Peyré, M. Cuturi, and J. Solomon. Gromov wasserstein averaging of kernel and distance matrices. In International Conference on Machine Learning, pages 2664-2672, 2016.
[48] A. Rakotomamonjy, A. Traoré, M. Berar, R. Flamary, and N. Courty. Distance measure machines. arXiv preprint arXiv: 00250, 2018.
[49] Santambrogio. Optimal transport for applied mathematicians. Birkäuser, NY, 55(58-63):94,
2015.
12

---

[50] M. Scetbon, G. Peyré, and M. Cuturi. Linear-time gromov wasserstein distances using low rank couplings and costs, 2021.
[51] A. Shekhovtsov and V. Hlaváč. A distributed mincut/maxtlow algorithm combining path augmentation and push-relabel. International journal of computer vision, 104(3)331-335 2013.
[52] N. Shervashidze, P. Schweitzer, E. J. Van Leeuwen, K. Mehlhorn, and K. M. Borgwardt. Weisfeiler-lehman graph kernels. Journal of Machine Learning Research, 12(9), 2011.
[53] N. Shervashidze, S. Vishwanathan, T. Petri, K. Mehlhorn, and K. Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial intelligence and statistics, pages 488-495. PMLR, 2009.
[54] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst. The emerging field of signal processing on graphs: Extending high-dimensional data analysis networks and other irregular domains. IEEE Signal Processing Magazine, 30:83-98, 2013.
[55] K.-T. Sturm. The space of spaces: curvature bounds and gradient flows on the space of metric measure spaces. arXiv preprint arXiv: 221../00.... 0434, 2012.
[56] M. Togninalli, E. Ghisu, F. Llinares- López. B. Rieck, and K. Borgwardt. Wasserstein weisfeiler- lehman graph kernels. In Advances in Neural Information Processing Systems, pages 6436-6446 Curran Associates, Inc., 2019.
[57] L. Van der Maaten and G. Hinton. Visualizing data using t-sne. Journal of machine learning research, 9111). 2008.
[58] T. Vayer, L. Chapel, R. Flamary, R. Tavenard, and N. Courty. Fused gromov-wasserstein distance for structured objects. Algorithms, 13(9):212, 2020.
[59] T. Vayer, N. Courty, R. Tavenard, and R. Flamary. Optimal transport for structured data with application on graphs. In International Conference on Machine Learning, pages 6284.. PMLR, 2019,
[60] Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
[61] C. Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[62] C. Vincent-Cuaz, R. Flamary, M. Corneli, T. Vayer, and N. Courty. Semi-relaxed gromov- wasserstein divergence and applications on graphs. In International Conference on Learning Representations, 2022.
[63] C. Vincent-Cuaz, T. Vayer, R. Flamary, M. Corneli, and N. Courty. Online graph dictionary learning. In Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Muchine Learning Research, pages 10564-10574. PMLR, 18-24 Jul 2021.
[64] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and S. Y. Philip. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 2020.
[65] H. Xu. Grosov-wasserstein factorization models for graph clustering. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 6478 6485, 2020.
[66] H. Xu, D. Luo, and L. Carin. Scalable gromov-wasserstein learning for graph partitioning and matching. Advances in neural information processing systems, 32:3052-3066 2019.
[67] K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:1870.00826, 2018.
[68] K. Xu, C. Li, Y. Tian, T. Sonobe, K.-i. Kawarabayashi, and S. Jegelka. Representation learning on graphs with jumping knowledge networks. International Conference on Machine Learning, pages 5453-5462. PMLR, 2018.
13

---

[69] P. Yanardag and S. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, pages 1365-1374, 2015.
[70] Z. Ying. J. You, C. Morris, X. Ren, W. Hamilton, and J. Leskovec. Hierarchical graph representation learning with differentiable pooling. Advances in neural information processing systems, 31, 2018.
[71] M. Zhang, Z. Cui, M. Neumann, and Y. Chen. An end-to-end deep learning architecture for graph classification. In Thirty-second AAAI conference artificial intelligence, 2018.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Every key points are encapuslated in the contributions
part the end of the introduction.
(b) Did you describe the limitations of your work? [Yes] Yes the limitations of our work mostly lie its computational complexity and the lack of a current implementation
designed for GPU parallelization of the FGW distance solver in section 2.1 and 3.2.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Indeed the full set of assumptions of all theoretical results are in the paper. Few technical definitions which are common in the OT litterature have been reported to the supplementary material.
(b) Did you include complete proofs all theoretical results? [Yes] A simple intuition for Lemma I is given in the paper and more details are provided in the supplementary.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] The code is provided in the supplementary material. A read me has been made to reproduce these experiments more easily.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] For each kind of experiments most settings are provided the core of the paper (see section 3). Complementary details on the experiments are reported in the supplementary material
(c) Did you report error bars (e-g., with respect the random seed after running experi- ments multiple times)? [Yes] Yes, each tables and figures contain such information on the distributions when relevant.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] Our code mostly depends on the POT and Pytorch librairies which are quoted in section 2.2
(b) Did you mention the license of the assets? [Yes] Those assets have been following the format prescribed in their respective websites/papers.
(c) Did you include any new assets either the supplemental material or as URL? [Yes] Some implementations of the methods reproduced in the benchmark section 3.2 depend on assets which were not used initially for our own method. Therefore we quoted them in the supplementary
(d) Did you discuss whether and how consent was obtained from people whose data you're using/eurating? [Yes] Used datasets are public ones, we quoted their designers as sign of consent.
14

---

(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No] Used datasets are well-knowwn public ones that do not contain such content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "h18TAS1Vfn4", "reviewer": "Reviewer_Md5Y", "summary": "The authors study the problem of graph classification. They propose to use the Fused Gromov-Wasserstein (FGW) distance as features for the MLP classifier for graph classification. In the proposed framework, instead of computing pair-wise FGW distances between each pair of graphs, they propose to create some learnable 'templates', which are expected to carry discriminating information either in the features or in the structure of the graphs. Calculating the FGW distance to the templates forms the TFGW layer. The authors also added a GNN layer at the beginning for graph feature transformations. The authors performed various experiments, ablation studies and visualizations to show the superior performance of the proposed framework. ", "questions": "1. I don't quite understand the function of h here. Particularly, it seems the h is used to decide the coupling function. How does the initialization of h change the results? Can you do an ablation study where node weights are not in the framework to see what role it plays?\n\n2. The use of GNN at the beginning: the author chosed GIN as the first layer. GIN itself is very discriminative (expressive) of the graph structure. If I understand correctly, the authors didn't use the pooling layer to get an embedding of the whole graph from GIN, but just updated the features of each node based on message propagation? The authors can clarify better on the process. ", "limitations": "Would like to see a comparison of the computation time for the proposed method and other baselines too.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors leveraged Fused Gromov Wasserstein distance for graph classification. The idea is intuitive, and the authors demonstrated the good performance of the model. However, some of the ideas presented can be better explained (see questions below)\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Lc0rp8Fba9", "reviewer": "Reviewer_c2Hn", "summary": "This work introduces TFGW, a novel graph embedding layer that describes a graph with its Fused-Gromov-Wasserstein distances from a set of learnt templates. TFGW is shown to exhibit strong discriminative power on a wide set of graph classification datasets. ", "questions": "1. If my understanding is correct, the main novelty of TFGW in the context of OT-GNN is its use of the FGW distance instead of OT. In Lines 310-325, it is confirmed experimentally that the trade-off parameter $\\alpha$ is not 0 or 1, so that the use of FGW is justified as it is not reduced back to OT. However, I'm wondering if an ablation study has been done to manually set $\\alpha=0$ in TFGW, which reduces FGW back to OT, and compare its performance with that of learned $\\alpha$? This should further cement the advantage of using FGW in place of OT, which I believe is an important point to make since FGW is more expensive to compute than OT. \n\n2. How does the practical runtime for TFGW compare with other GNNs? I understand that the OT solver used is only implemented on CPU, and TFGW has a competitive speed when benchmarked on CPU. I am wondering if the current TFGW implementation is reasonably efficient on the experimental datasets. \n\n3. The TFGW layer can serve as a drop-in for the global pooling step in any existing GNN model. However, it seems that TFGW is always used with GIN in this work. Have the authors tried TFGW with other GNN node embedding layers? Does TFGW interact better with some compared to others?\n\nMisc.\n1. Figure 1 can be seen from the web preview but cannot be displayed after the PDF file is downloaded and opened with Adobe. I am not sure if this is an issue on my side.", "limitations": "The authors have addressed the limitations of TFGW adequately. ", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall, I found the paper to be clearly-written, well-motivated, and easy to follow. The experiments show meaningful improvements over existent baselines, and the sensitive analysis further substantiates the model's robustness. On the downside, there have been previous prototype-based graph embedding models (e.g. OT-GNN) that also learns the template in an end-to-end fashion, which somewhat limits the novelty of this work. In addition, I have some additional concerns that I hope the authors can clarify.\n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8RldkDCWI6p", "reviewer": "Reviewer_KbbR", "summary": "The authors introduce a novel GNN construction by adding a new GNN layer that is called TFGW for Template-based FGW. FGW is Fused Gromov-Wasserstein distance and it shows the similarity and isomorphism between two graphs. The novel GNN consists of normal GNN layers, a TFGW layer, and an MLP layer, and its structure is shown in Figure 1 of the paper. Furthermore, the properties and the invariances are discussed in the paper. It is illustrated that the TFGW embeddings are invariant to strong isomorphism. The optimization strategy and graph templates relevant for the downstream task are also introduced. The trade-off parameter is learned in the model in a supervised way which appears first. In section 3, the experiment settings and results are shown. The performance of the TFGW is tested in synthetic datasets, several well-known graph classification datasets, and an ablation study.  The results of the sensitivity analysis and an ablation study could show the generalization of the parameters in the model. ", "questions": "It is reported in the paper that for L=0, the TFGW with SP matrices outperforms TFGW with ADJ matrices while for L no less than 1, the TFGW with ADJ matrices shows better performance. Could a more specific explanation be given? Is this phenomenon related to the aggregation function of the GNN itself?\n\nFrom section 2 in the paper, we could see that the trade-off parameter and the templates are learned from the data. Therefore, different templates could appear with different parameters. A direct problem might be how to deal with this phenomenon? \n", "limitations": "From lemma 1 in this paper, we could know that for strong isomorphic graphs, the embeddings are invariant but there is not any description of the performance of the TFGW on weak isomorphic graphs. \n\nIn this paper, the expressiveness of the TFGW is not derived. There should be a WL-test to show the expressiveness of this novel GNN structure.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The language is very fluent and the expression is most appropriate in this paper. The proof and the illustration of the experiment details are very clear. The structure of the Template-based FGW layer is very novel and creative. The FGW distance could express the similarity and isomorphism between two graphs and it appears to be appropriate to construct a layer deeply related to it. The results of the ablation study could also show the outstanding performance of this novel layer. This paper is the first to learn the trade-off parameter in a supervised way. It is not required to adjust the parameter to obtain the best performance for other users and could guarantee the generalization of the proposed Template-based FGW model. In the numerical study in section 3, the authors compare the proposed model with several widely used GNN models. From the results in table 2 and table 4, we could find that the performance of the proposed model is distinguished and could do well in the downstream task.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept