Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks
Authors: Ching-Yao Chuang
Stefanie Jegelka
Venue: NeurIPS 2022 Accept (2022)
Keywords: generalization of graph neural networks
stability
graph metrics

Abstract: Understanding generalization and robustness of machine learning models fundamentally relies on assuming an appropriate metric on the data space. Identifying such a metric is particularly challenging for non-Euclidean data such as graphs. Here, we propose a pseudometric for attributed graphs, the Tree Mover's Distance (TMD), and study its relation to generalization. Via a hierarchical optimal transport problem, TMD reflects the local distribution of node attributes as well as the distribution of local computation trees, which are known to be decisive for the learning behavior of graph neural networks (GNNs). First, we show that TMD captures properties relevant for graph classification: a simple TMD-SVM can perform competitively with standard GNNs. Second, we relate TMD to generalization of GNNs under distribution shifts, and show that it correlates well with performance drop under such shifts.

Tree Mover's Distance: Bridging Graph Metrics and Stability of Graph Neural Networks
Ching-Yao Yao Chuang MIT CSAIL cychuang@mit. edu
Stefanie Jegelka MIT CSAIL steffee@iit. edu
Abstract
Understanding generalization and robustness of machine learning models funda- mentally relies on assuming an appropriate metric on the data space. Identifying such a metric is particularly challenging for non-Fuclidean data such as graphs. Here, we propose a pseudometric for attributed graphs, the Tree Mover's Distance (TMD), and study its relation generalization. Via a hierarchical optimal transport problem, TMD reflects the local distribution of node attributes as well as the distri- bution of local computation trees, which are known to be decisive for the learning behavior of graph neural networks (GNNs). First, we show that TMD captures properties relevant to graph classification: a simple TMD-SVM performs competi- tively with standard GNNs. Second, we relate TMD to generalization of GNNs under distribution shifts, and show that it correlates well with performance drop under such shifts. The code is available at https: / //ggttttubb com/ chingyaoc/TTM.
Introduction
Understanding generalization under distribution shifts theoretically and empirically relies on an appropriate measure of divergence between data distributions. This, in turn, typically demands metric on the data space that indicates what kinds of data points are "close" to the training data. While such metrics may be readily available for Fuclidean spaces, they are more challenging to determine for non-Euclidean data spaces such as graphs with attributes in IR" which underlie graph learning methods. this work, we study the question of suitable metric for message passing graph neural networks (GNNs).
An "ideal" metric for studying input perturbations captures the invariances and inductive biases of the model we are examining. For instance, since graph isomorphism is difficult problem [18], this metric is expected to be pseudometric, i.e., will fail to distinguish certain graphs. These "failures" should be aligned with the GNNs' invariances. Moreover, several recent works highlight the importance of local structures - computation trees resulting from unrolling the message passing process for the approximation power of GNNs and their inability to distinguish certain pairs of graphs [2. 20, 34, 55). Works on out-of-diitribution generalization of GNNs mostly focus on specific types of instances where trained model may fail miserably [58, 54], without specifying the behavior for gradual shifts in distributions. Yehudai et al. [58] show that sufficiently large, unrestricted GNN may predict arbitrarily previously unseen computation trees. In practice, we may observe more gradual change, depending on the magnitude of change of the tree, terms both structure and node attributes, and the capacity of the aggregation function. In summary, reflects the structure of computation trees and the distribution of node attributes within trees. Many distances and kernels between graphs have been proposed [7], several based on local structures [21], and some using structure and attributes [44]. Closest to our ideal is the Wasserstein Weisfeiler-Leman pseudometric [46], which computes optimal transport distance between node embeddings of two graphs. The embeddings are computed via message passing, which aligns with the computation of GNNs, but loses structural information within trees.
desire metric that
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Hence, we propose the Tree Mover's Distance (TMD), a pseudometric on attributed graphs that considers both the tree structure and local distribution of attributes. It achieves this via a hierarchical optimal transport problem that defines distances between trees. First, we observe that the TMD captures properties that capture relationships between graphs and common labels: a simple SVM based on TMD performs competitively with standard GNNs and graph kernels on graph classification benchmarks. Second, we relate TMD to the performance of GNNs under imput perturbations. We determine Lipschitz constant of GNNs with respect to TMD, which enables bound on their target risk under domain shifts, i.e., distribution shifts between training and test data. This bound uses the metric in two ways: to measure the distribution shift, and to measure perturbation robustness via the Lipschitz constant. Empirically, we observe that the TMD correlates well with the performance of GNNs under distribution shifts, also when compared to other distances. We hence hope that this work inspires further empirical and theoretical work on tightening the understanding of the performance of GNNs under distribution shifts.
In short, this work makes the following contributions:
We propose a new graph metric via hierarchical optimal transport between computation trees of graphs, which, in an SVM, leads to a competitive graph learning method;
We bound the Lipschitz constant of message-passing GNNs with respect to TMD, which allows to quantify stability and generalization;
We develop generalization bound for GNNs under distribution shifts that correlates well with empirical behavior.
2 Related Works
Graph Metrics and Kernels Measuring distances between graphs has been a otag-standing goal in data analysis. However, proper metrics that distinguish non-isomorphic graphs polynomial time are not known. For instance, Vayer et al. [49] propose graph metric by fusing Wassestein distance (50) and
distance [32]. Similar to classic graph metrics [9, 40), the proposed metric requires approximation. Closely related, graph kernels [52, 7] have gained attention. Most graph kernels lie in the framework of RR-convolutional [21], and measure similarity by comparing substructures. Many R-convolutional kernels have limited expressive power and sometimes struggle to handle continuously attributed graphs [46]. In comparison, TMD is as powerful as the WL graph isomorphism test [53] while accommodating graphs with high dimensional node attributes. Importantly, TMD captures the stability and generalization of
GNNs [27,55].
Stability and Generalization of Graph Neural Networks A number of existing works study stability of GNNs to input perturbations. Spectral GNNs are known be stable to certain per- turbations, e.g., size, if the overall structure is preserved [19, 25, 26, 19]. For message passing GNNs, Yehudai al. [57] study perturbations of graph size, and demonstrate the importance of local computation trees. Xu et al. [54] study how the dut-of-distribution behavior of aggregation functions may affect the GNN's prediction. These studies motivate to include both computation trees and inputs to aggregation functions in the TMD. Finally, a number of works study within-distribution generalization [15, 20, 28, 42).
3 Background on Optimal Transport
We begin with a brief introduction to Optimal Transport (OT) and earth mover's distance. The earth mover's distance, also known as Wasserstein distance, is a distance function defined via the transportation cost between two distributions. Let X = {m and Y {ı }/ be two multisets of m elements each. Let C' E R be the transportation cost for each pair: Cjj d(z;, yj) where is the distance between I; and V/- The earth mover's distance solves the following OT problem:
min O (X,Y) yY)(X.y)
(C,7)/m, T(X,Y) (r E RmXm 71mm = 1, 1m (1)
where I' is the set of transportation plans that satisties the flow constrain 71m = T 1mm = 1m In this work, we adopt the unnormalized version of the earth's mover distance:
OTa(X,Y) == min (C,7) = m (X, ().
(2)
,Er(x,Y)
Comparing to classic OT, unnormalized OT preserves the size information of multisets X and Y.

---

Tree Distance
Root Difference
Subtree Difference
TD
+ Ot
+TD
+TD
Figure 1: Tree Distance via Hierarchical OT. The weight w(+) is set to simplify visualization. The distance between two trees can be decomposed into (a) the distance between roots and (b) the OT cost between subtrees, where the cost function of OT again the distance between two trees. This formulates a hierarchical OT problem, where solving the OT between trees requires solving the OT between subtrees.
Tree Mover's Distance: Optimal Transport on Graphs
Next, we introduce free mover's 's distance, a new distance for graphs. Let G = (V, E) denote graph with sets of nodes V and edges E. The graph may have node features Ze R for v E V. If not, we simply set the node feature to a scalar T. for all E V.
Local structures of graphs characterized by computation trees [23]. In particular, computation trees are constructed by connecting adjacent nodes recursively.
Definition 1 (Computation Trees). Given a graph G (V, E), ler
and let T be the depth-L L
computation free of node u constructed by connecting the neighbors of the leaf nodes of T!. free. The multiset of depth-T. computation Irees defined by G is denoted by T ==
of.-1 to the { Joev.
Figure illustrates an example of constructing computation trees. Computation trees, also referred to as subtree patterns, have been central in graph analysis [38, 53] and graph kernels [39, 44]. Intuitively, the computation tree of node encodes local structure by appending the neighbors to the tree each level. If depth-T, computation trees are the same for two nodes, they share similar neighborhoods up to I. steps away. Therefore, an intuitive way to compare two graphs is by measuring the difference of their nodes' computation trees [44, 53]. In this work, we adopt optimal transport, a natural way to compute the distance between two sets of objects with, importantly, an underlying geometry. We will begin by defining the transportation cost between two computation trees. The cost then gives rise to the tree mover's distance, an extension earth mover's distance to multisets of trees.
4.1 Distance between Trees via Hierarchical OT
Let T = (V, F) denote a rooted tree. We further let T. be the multiset of computation trees of the node which consists of trees that root at the descendants of v. Determining whether two trees similar requires iteratively examining whether the subtrees in each level are similar. For instance, two trees T. and Ti, with roots Ta and 7 are the same if xr, Ir, and T._ = Trg This motivates us to define the distance between two trees by recursively computing the optimal transportation cost between their subtrees. Nevertheless, the number of subtrees could be different for ra and rb, i.e., [Tr.. } |Tr, (see Figure left). To compute the OT between sets with different sizes, unbalanced [11, 41] partial OT [10] are usually adopted. Inspired by [10], we augment the smaller set with blank trees.
Definition (Blank Tree), blank tree To is a tree (graph) that contains single node and no edge, where the node feature is the zero vector Op E RP, and To denotes multiset of n blank trees. Definition 3 (Blank Tree Augmentation). Given two multisets of trees Ta, Te, define p be a function that augments a pair of trees with blank trees as follows:
p: (T., Tw) + ( TT. Tu UTMMa -T=.))))) .0).
If [Tu| [Tull P augments T, by [Tu| T -TT blank trees to make the two multisets contain the same number of trees, and hence allows to define transportation cost between two multisets of trees with different sizes. particular, the transportation costs of additional trees are simply the distance to the blank trees. The distance between tree and a blank tree can be interpreted as the norm of the free. In our case, the blank tree can be viewed as the origin, as it a tree with the simplest structure and zero feature vector. Equipped with p, define the distance between two rooted trees follows.
3

---

Definition 4 (Tree Distance). The distance between two trees Ta, To is defined recursively as
|it.. Ir.. (r.ll+w(D) OTTD. (M(Tr, Tr.))
iL
TD (Tu. =
Irra Ira!l
otherwise,
where L max(Depth((Ta)) (T)) and N - R+ is depth-dependent weighting function.
Here, TT..... is the OT distance defined in (2) with TD., as the metric. Figure gives an illustration of computing tree distances. The tree distance TD... (Ta, Tb) aims to optimally align two trees Ta and T3 by recursively comparing their roots and subtrees. Calculating TD.,. a, Th) requires calculating the OT between augmented subtrees p(Tr.: Tr.)) where the cost function of OT is TD again. This formulates a hierarchical optimal transport problem: the distance of two trees is defined via the distances of subtrees, where the importance of each level is determined by the weight w(-). Increasing w+)) upweights the effect of nodes in the subtrees. While the weights may be arbitrary, we found that for many applications, using a single weight for all depths yields good empirical performance, as section 4.3 shows. The role of weights will be more significant when we use TMD to bound the stability of GNNs.
4.2 From Tree Distance to Graph Distance
Next, we extend the distance between trees to a distance between graphs. By leveraging the tree distance (t:-)::). we introduce the tree mover's 's distance (TMD), distance for graphs, by calculating the optimal transportation cost between the graphs' computation trees.
Definition 5 (Tree Mover's Distance). Given two graphs Ga, Go and w, L 2 0, the tree mover's distance between G. and G2 is defined as
T., OTD (TD. TG.)).
where TV, and andTT, are multisets of the depth-T. I. computation trees of graphs G2 and G respectively.
Figure 2 illustrates the computation of TMD. Intuitively, TMD is the minimum cost required to transport node-wise computation trees from one graph another. The blank tree augmentation p is again adopted to handle graphs with different numbers of nodes. The next theorem shows that TMD is pseudometric attributed graphs.
Theorem (Pseudometric). The tree mover's distance TMD uo
is a pseudometric for finite 0.
In particular, the tree mover's distance satisfies (1) TMD (G., Ga) = 0, (2) TMD (Ga, Gb) TMD (Go, Ga), and (3) TMD" Gb) & TMD w (Ga, G.) TMD Gb) for any graphs Ga, G2, Ge. However, in some cases, the distance TMD Gb) can zero even if G. & G This is reasonable, as computing graph isomorphism is not known to be solvable in polynomial time. Nevertheless, TMD can provably distinguish graphs that are identifiable by the (1-dimensional) Weisfeiler-Leman graph isomorphism test [53].
Theorem 7 (Discriminative Power of TMD). If two graphs Ga. Go are determined to be non- isomorphic in WL iteration L and (I) > 0 for all 0 < I L then TMDL-1 Gt) > 0.
The unnormalized OT and blank tree augmentation are essential to prove Theorem 16. The tree mover's 's distance can be exactly computed by solving optimal transport. In addition, TMD remains highly expressive graphs with high dimensional continuous attributes, where most R-convolutional graph kernels struggle [46]. The discriminative power of TMD can be further strengthened by augmenting node attributes e.g. with positional encodings [16, 29].
The OT cost between node representations in different graphs is reminiscent of the recently proposed Wasserstein WL (WWL) [46]. WWL uses the distance of node embeddings as a ground metric, where the node embeddings are computed via iterations of message passing with veeage-aggregatiin in contrast, TMD computes distance that aligns the trees, retaining more structural information. Even though an aggregation with nonlinearities can retain tree isomorphism information [55], similar to the hashing applied in the WI. test (WWL uses only linear aggregations). the hierarchical OT more direct graded distance measure of trees. Vayer et [49] define a metric that uses Gromov-Wasserster Wasserstein distance [32] between nodes, but need to approximate the GW computation.

---

To
Optimal Transport
Depth -
Go
TG.
TG.
Gb
Figure 2: Illustration of Computation Trees and Tree Mover's Distance. The computation trees of nodes are constructed by iteratively connecting the neighbors to the trees, and each graph will define multiser of node-wise computation trees. Tree mover's distance then defined as the optimal transport cost between the computation trees of two graphs
MUTAG
PTC
PROTEINS
NCT1
NCT109
BZR
COX2
TMD L=1
89.4
63.315.8
73.91288
68.3-2,0
1.
83.817.2
77.815.0
TMD L=2
90.0+5.7
67.4+7.7
74.8+2.8
80.8+1.8
78.9+2.3
84.5++6.9
79.1+5..2
TMD L=3
91.1=5.4
68.5+t.11
74.6+2..6
83.3+1.1
82.3+2.5
85.5+-6.2
78.5+5599
TMD L=4
92.2++.00
66.5+7.1
75.2+
84.
82.8+2.1
84.5+6.4
76.1+6.1
WWL [46]
17.
6..3+1.2
74.3++0.6
86.1+00.3
84.4+:2.0
78.3++0..5
FOW [49]
88.445.6
65.3
74.5+2277
86.4
85.11:4.2
77.2:1.99
WL [44]
90.455.7
59.914.3
75.013.1
86.0=
82.46:10.2
N/A
N/A
R&G [39]
85.7=0.4
58.510099
70.7:10.4
61.910.3
61.7:10.2
N/A
N/A
GIN [55]
89,455.6
64.617.0
76.2:t2.88
82.7=1.7
1..2
83.5+6.0
79,0=5.33 77.1
GCN [27]
85.6=
64.2
76.0#:3.2
80.2=2.0
84.6
Table 1:
Classification TU Dataset. TMD outperforms matches the state-of-the-an graph kernels or GNNs. Note that WL [44] and R&G [39] are not applicable to continuously attributed graphs such as BZR and COX2.
Numerical Computation with Dynamic Programming One can numerically compute TMD with dynamic programming. Starting with pair-wise distances (TMD/=1) between node features across the two graphs, we then iteratively compute TMD between depth-k: computation trees from to L according to Definition 4. Let D be the maximum degree of node in the two graphs and ((m) be the complexity of computing OT between sets of cardinality m. each level, we have to perform OT of sets contain at most D elements for N nodes. Including the last OT between nodes of graph, the overall time complexity of computing TMD is O(r(N) + LNr(D)). The time complexity for exact OT by solving linear programming r(m) Om log(m)) [17]. One can use faster approximation of OT, e.g., near linear time complexity [1], but we use exact OT throughout all the experiments, implemented with the POT library [17].
4.3 Experiments
verify whether the tree mover's distance aligns with the labels of graphs in graph classification tasks: the TUDatasets [35], which contain graphs with discrete node attributes (MUTAG, PTC-MR, PROTEINS, NCII, NCI109) and graphs with continuous node attributes (BZR, COX2). Specifically, we run support vector classifier (C=1) with indefinite kernel e which can be viewed as noisy observation of the true positive semidefinite kemnel [31]. The is selected via cross-validation from {0.01, 0.05, 0.1} and the weights w(-)) are set to 0.5 for all depths. For comparison, we use graph kernels based graph subtrees: Ramon & Gärtner kernel [39], WL subtree kernel [44]; two aidely-adopted GNNs: graph isomorphism network (GIN) [55], graph convolutional networks (GCN) [27]; and the recently proposed graph metrics FGW [49] and WWL [46]. Table I reports the mean and standard deviation over 10 independent trials with 90%/10% train-test split. The performances of the baselines are taken from the original papers. TMD outperforms state-of-the-an GNNs, graph kernels, and metrics, implying that it captures meaningful structural properties of graphs. Appendix C shows further graph clustering and t-SNE visualization [48] results.
matches the performances of
5

---

Computation Complexity To examine the computation complexity, we compare the runtime between Weisfeiler- Lehman (WWL.) kernels, TMD, and a parallel version of TMD on DD and NCT1 datasets [35], where DD contains large graphs (avg. #node: 284.32, avg. #edge: 715.66) and NCII contains small graphs (avg. #node: 29.87, avg. #rdge: 32.30). Here, we additionally consider parallel version of TMD, where the tree OTs in each level are executed simultaneously with 3 processes. The average runtime over 200 pairs is shown in Table 2. Note that the time complexity of WWL is (mm) Om log(m)). The runtime of parallelized TMD is roughly three times larger than WWL on DD, which is much faster than the (worst case) theoretical Big-O analysis. In datasets contain small graphs such NC11, TMD without parallelization works well.
WWL
TMD
TMD Parallel
DD NCI1
7.92
32.07
24.44
0.11
0.34
0.81
Table 2: Runtime Comparison. The av-
erage runtime (sec/pair) of TMD is much faster than the (worst case) theoretical Big-O analysis.
5 TMD and Stability of Graph Neural Networks
Next, we relate TMD to the perturbation stability of message passing GNNs. In particular, we use the Lipschitz constant, which relies on an underlying metric here, a metric over graphs. We observe that TMD is a meaningful pseudometric in this case. The resulting Lipschitz allows analyze the stability of GNNs under perturbations and generalization bounds under distribution shifts.
5.1 Lipschitz Constant of Message Passing Graph Neural Networks
For simplicity, we consider graph binary classification with the Graph Isomorphim Network (GIN) [55], one of the most widely applied and powerful GNNs. In particular, we consider the following message passing rules of a L--ayer GIN:
Message -1)) = =0))
Passing
20
(1-1) +E
Σ
zu
(1-1)
Readout
Graph h(G) = (((+1)
Σ (L) NEV
(EN(1))
where d()) IRd Rd and d((++), IRd IR are learnable functions with Lipschitz constant K and
the initial state is set to the node feature 20 F.. The > 0 is weighting term between the center node and the neighbors. Note that the original formulation of GIN [55] weights the center node with layer dependent e instead of neighbors. We adopt the form above with the purpose simplify the notation of TMD. One can easily derive an equivalent form by changing the weight function w(-) of TMD to recover the original formulation of GIN. For simplicity, we set in all experiments. This does not affect the empirically performance of GIN as the original paper shows [55]. A graph level binary classifier is constructed based on the logits h(G).
The next theorem bounds the Lipschitz constant of GIN with respect to TMD. Although TMD is a pseudometric, satisfies that TMD u (Ga, Gb) > 0 if Ga, Gb, are distinguished by L iterations of the WL test. Since GIN(Ga) GIN(G.) * GIN(G,) then TMD (G., Gb)) > 0. That is, for all triples of graphs that GIN distinguishes pairwise, TMD a metric.
GIN(G,) for all graphs where WL fails, it holds that, if
Theorem 8 (Lipschitz Constant of GIN). Given an L-layer graph neural network h X + R and two graph Ga. Gb E G. we have
L+1
[MM(Ga) MGGII s
II K
TMD (Ga; Gt),
1=1
where w())=e- PI:p1/P441o0 for all 1 S L and PL is the 1-th number at level L of Pascal's triangle.
The result can be extended to other GNNs (Appendix B). Interestingly, the weights in each level follow a simple rule determined by Pascal's triangle. Figure 3 illustrates the weights when L 4, where the weights wel) gradually decrease from 4e to e/4 as / becomes smaller. Note that the hyperparameter w of TMD is independent of the parameters of the GNN. Moreover, Theorem shows that the Lipschitz constant of GNNs L+11 k!! the product of Lipschitz constants across layers, similar to fully connected networks [33, 37].
1
1
2
1
1
4
4
1
4
6
4
I. weights
under TMD admits a simple form |
4
6
4
Figure 3:
Example of
Pascal's triangle (E = 1).

---

3 Layers
Layers
Layers
Layer
== 0.76
15.0
0.81
r= 0.85
0.83
[MG MG
12.5
(a) TMD
75
50.
200
000
100
150
200
292
TMDEG, (%)
TMD(C,, G4)
G4)
TMDEC, (b)
p-r= 0.38
0.46
0.49
0.43
[[CG MGG
WWL
24 WWL
G.)
GWL.G,
WWL.G, Gy)
Figure 4: Correlation between GNNS and TMD / WWL. The Pearson correlation coefficient between [lh(G,) - [ and TMD/ / WWL are showed on the upper left of the figures. The output variation is highly correlated with TMD, while WWL barely captures the behavior of GNNs with different number of message-passing layers.
5.2 Stability of GNNs under Graph Perturbation
The Lipschitz constant is common criterion to assess the stability of the neural networks to small perturbations [51]. Theorem 8 implies that the output variation of GNNs under graph perturbation can be bounded via the TMD between the original graph and the perturbed one. In this section, we analyze the stability of GNNs more detail by dissecting TMD under three types of graph perturbation: (1) node drop; (2) edge drop; and (3) node feature perturbations.
Proposition 9 (Node Drop). Given graph G (V. E), let G' be the graph where node v E V dropped. Then the tree mover's distance between G and G' can be bounded by
TG. S Σ d 1=1
A-Width; (T.-L Te),
Tree Size
Tree Norm
where Width; (T) is the width of 1-th level of tree T and \ = 1, X =
II w (1+++11
The bound is controlled two factors: (1) tree size and (2) tree norm (distance from the blank tree) of the computation tree by. A node with a large computation tree size implies that many nodes can be reached from v. Deleting from the graph then significantly changes the computation trees of those reachable nodes, while the magnitude of the variation is controlled by the tree norm.
Proposition (Edge Drop). Given a graph G (V, E), let G' be the graph where edge (u, v) E E is dropped. The free mover's distance between G and G" can be bounded by
TMD (G. A411 - (Widthy(T++) TD (TH- (ort-1.10 Tb) Width; (TH-
The bound takes a similar form as with the node drop, but includes the effects of both node e and u. In particular, the tree size of u (u) will control how many computation trees of u (v) will be dropped. By using Proposition and 10, one can derive bounds for dropping multiple nodes and edges, or even edge rewiring. Note that adding nodes or edges is equivalent to the analysis above.
Proposition 11 (Node Perturbation). Given a graph = (V, E), let G' be the graph where node feature F, is perturbed to x'y. The tree mover's 's distance between G and G' is equal to
TMD (G, G') S Σ d Width; Width ||., x'
1=1
Different from Proposition 9, the magnitude of the perturbation is controlled by the norm of the perturbation instead of the norm of the computation tree.
7

---

Node Drop
Edge Drop
Node Perturbation
dhagaaate dray partl
deg rond ars puii
penstl sared persat, peraat, parted
[MG]] - MGG)il
M(G.))l
[k(Gg) (GG)
12.
Bound
Bound
300
50
322
252
TMD(G., Gt)
TMD(G,, G.)
TM, Gs)
Figure 5: Robustness under Graph Perturbation. The empirical Lipschitz bounds (dash lines)
successfully upper bound the output variation of GNNs under different graph perturbations.
5.3
Experiments
Correlation between TMD and GNN output perturbation We now empirically examine the theoretical analysis with experiments the MUTAG dataset [14]. Results for other datasets can be found in Appendix C. In particular, we measure to what extent candidate graph distances capture imput perturbations that lead to output perturbations the GNN. We train graph isomorphism networks [55] with varying numbers of message passing layers and plot the relation between input variation TMD (G., G5) and output variation [l((G,) h(,,)] for randomly sampled pairs (Ga, Gb) in Figure 4. For comparison, we also plot the input variations measured by the recently proposed graph metric WWL [46]. We can see that TMD strongly correlates with the output variation with large Pearson correlation coefficient, supporting the approach of defining the Lipschitz constant with respect to TMD, as in Theorem 8. In contrast, WWL barely captures the input graph perturbations that lead output variation of GNNs.
Stability under small Perturbations Next, we plot the output variation of 3-layer GNNs and the TMD under random graph perturbations in Figure 5. For node perturbations, change the discrete node attribute for randomly sampled nodes. We additionally plot the Lipschitz bound with empirical estimated Lipschitz constant MaXGG..G,ES [G.G.. (.)Il/TMMD L+1 (Ga, G.), where S is a set of samples. We refer reader to [36, 47] for analyses approximation error of estimating Lipschitz constants from finite samples. We can see that the bound is reasonably tight and estimates the effect of perturbations across different degrees.
6 Generalization of GNNs under Distribution Shifts
Finally, we relate the Lipschitz condition of GNNs to the generalization error under distribution shifts by extending the results from [43]. Consider binary classification task with input space X' and output space V. In domain adaptation [13], a pair of source and target distributions μs μTT over X x y are given. Let ps and pr denote the respective marginals on the input space X. In unsupervised domain adaptation, the learning algorithm obtains labelled source samples from μs and unlabelled target samples from pr- To estimate the adaptability of hypothesis h, i..., its generalization to the target distribution, we aim to bound the target risk (r) Ez,ywur [1n(a)) relative to the source risk (h) z.ywuu [w)
[5, 13, 60]. For instance, Shen al. [43] bound the target risk via the source risk and the Wasserstein- distance Wi between source and target distributions.
Theorem 12 (Shen et [43]). For all hypothexes h E H. the target risk is bounded as
Ry (h) < Rg(h) + 2KWW(pss, PT) + Xx= where K the Lipschitz constant of h and Ay is the best joint risk Ay == (Rf (r
This bound relies on being able to measure Wasserstein distance between the two data distributions, which demands ground metric on the data space, and an associated Lipschitz constant of the model h. The TMD and the resulting Lipschitz constant in Section 5.1 make this bound applicable to message passing GNNs, too. In particular, for GNNs that satisfy the Lipschitz constant in Theorem the domain discrepancy Wi (ps, is defined as
inf Wi rell(ps.Pr)
IMDL++(Gas Gu)dd Gb),
(3)
8

---

Figure Accuracy
Drop and Distances. Wasserstein distance based on TMD highly correlates (r 0.712) with the accuracy drops, while WWL fails predict the generalization.
MM
3.00
44.C7
42.91
0.06
0.00
0.11
0.10
MR FR
12.74
12.05
0.00
11.24
$2.75
+4.07
0.00
20:81
0.04
0.11
0:00
17:15
18.10
7:25
0.00
34.54
62.51
20.81
0.00
0.10
0.07
0.00
FM
MM
FR
MR
FM
MM
FR
MR
FM
MM
FR
MR
(a) Accuracy Drop
(b) TMD (r: 0.712)
(c) WWL (r: 0,489)
where L is the number of message message-passing layers in Since Wi (ps.Pr) can be estimated without labels, Theorem 12 applies to unsupervised domain adaptation. Assuming that there is model that performs well in both source and target domain, i.e., dy is small, we may empirically estimate the discrepancy between source and target risk via the GNN Lipschitz constant and Wi (ps, pr).
6.1
Experiments
Domain Shifts We first verify our analysis on the PTC dataset [22], which contains carcinogenicity labels of chemical structures for four groups of rodents: male mice (MM), male rats (MR), female mice (FM) and female rats (FR). We train 3-layer GINs [55] on group and examine the empirical performance drop on the remaining groups. Figure shows the Wasserstein distance between groups and the corresponding performance drops. As baseline, compute the Wasserstein distance with WWL transportation cost [46]. The W1 distance based on TMD highly correlates with the accuracy drop (Pearson correlation 00.712), while WWL-WW only achieves =0.489.
Size Generalization A known challenge for GNNs is generalizing to graphs of different size [58, 56]. To evaluate TMD on this problem, we sort the PROTEINS dataset [8] based on the number of nodes and bin it into 8 subsets, each containing 125 graphs. We again train 3-layer GINs the smallest and the largest bins and examine the accuracy drops on the remaining ones. Figure plots the accuracy drops with respect to different subsets and the corresponding Wasserstein distance based on TMD and WWL. TMD correlates with the accuracy drop surprisingly well when the models are trained on large graphs and tested smaller graphs when the models are trained on small graphs and tested on large graphs (r 0.83). Yet, TMD shows much more gradual change in distance, in agreement with the gradual change in drop, than WWI., and hence reflects the overall behavior better.
0.97). The correlation is slightly weaker
Figure 7: Size Generalization. Index denotes the bin of small- est graphs and index 8 the largest graphs. For better visualization, the Wasserstein distances are nor- malized make the maximal dis- tance equal to the greatest per- formance drops, the absolute scales of distances are less impor- tant. The models in (a) (b) trained on subset / 8, respec- tively.
50-
40-
30
30-
20-
Drop
10-
Drop IND
10
TMD (1:0.331
WWL (r-0.831
WWL (rm0.01)
Test Subset
Test Subset
(a) Train on Small Graphs
(b) Train on Large Graphs
7 Conclusion
In this work, we introduce Tree Mover's Distance (TMD), new graph distance based on optimal transport between computation trees. First, TMD captures the structural and attribute properties that are important for many graph classification tasks. Second, it reflects the patterns that determine generalization behavior of message passing graph neural networks, and, hence, offers a suitable tool to predict the perturbation stability and out-of-domain generalization capability of such GNNs. Hence, bears promise in applications, both for graph learning tasks and predicting reliability of graph learning models, and, in theory, tool for new tighter analyses of generalization in GNNs.

---

This work was in part supported by NSF BIGDATA IIS 1741114 NSF AI Institute TILOS, NSF CAREER 1553284. CC is supported by a IBM PhD Fellowship.
Acknowledgements
References
[1] Jason Altschuler, Jonathan Niles-Weed, and Philippe Rigollet. Near-linear time approxima- tion algorithms for optimal transport via sinkhorn iteration. Advances in neural information processing systems, 30, 2017.
[2] Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On weisfeiler-leman invariance: Subgraph counts and related graph properties. In Journal of Computer and System Sciences, volume 113, pages 42-59. Elsevier, 2020.
[3] Paolo Baldan, Filippo Bonchi, Henning Kerstan, and Barbara König. Coalgebraic behavioral metrics. arXiv preprint 17Xiv:17/2.07511, 2017.
[4] Solon Barocas, Moritz Hardt, and Arvind Narayanan. Fairness in machine learning. Nips nutorial, 1:2, 2017.
[5] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79(1): 151-175, 2010.
[6] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In International Conference on Machine Learning, pages PMLR, 2020.
[7] Karsten Borgwardt, Elisabetta Ghisu, Felipe Llinares-López, Leslie O' O'Bray, and Bastian Rieck. Graph Kernels: State-of-the-Art and Future Challenges. Now Foundations and Trends, 2020.
[8] Karsten M Borgwardt, Cheng Soon Ong, Stefan Schönauer, SVN Vishwanathan, Alex Smola, and Hans-Peter Kriegel. Protein function prediction via graph kernels. Bioinformatics, 21 (suppl_I))a 1):447-i56, 2005.
[9] Horst Bunke and Kim Shearer. A graph distance metric based on the maximal common subgraph. Puttern recognition letters, (9(3-)):255-259 1998.
[10] Laetitia Chapel, Mokhtar Z. Alaya, and Gilles Gasso. Partial optimal tranport with applications on positive-unlabeled learning. Advances in Neural Information Processing Systems, 33:2903- 2913, 2020.
[11] Lenaic Chizat, Gabriel Peyré, Bernhard Schmitzer, and François- Vialard. Unbalanced optimal transport: geometry and kantorovich formulation. 2015.
[12] Ching- Yao Chuang and Youssef Mrouch. Fair mixup: Fairness via interpolation. In International Conference on Learning Representations, 2020.
[13] Ching Yao Chuang, Antonio Torralba, and Stefanie Jegelka. Estimating generalization under distribution shifts via domain-invariant representations. International Conference on Machine Learning, 2020.
[14] Asim Kumar Debnath, Rosa I. Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. drructur-activite relationship of mutagenic aromatic and hetcroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-797, 1991.
[15] Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in neural information processing systems, 32, 2019.
[16] Vijay Prakash Dwivedi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Graph neural networks with learnable structural and positional representations. arXiv preprint 1700::2110.7785.. 2021.
10

---

[17] Rémi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z Alaya, Aurélie Boisbunon, Stanislas Chambon, Lactitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, al. Pot: Python optimal transport. Journal of Machine Learning Research, 22(78): 2021.
[18]
Scott Fortin, The graph isomorphism problem. 1996.
[19] Fernando Gama, Joan Bruna, and Alejandro Ribeiro. Stability properties of graph neural networks. IEEE Transactions Signal Processing, 68:5680-5565 5695, 2020.
[20] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference Machine Learning, pages 3419-3430. PMLR, 2020.
[21] David Haussler. Convolution kernels on discrete structures. Technical report, Technical report, Department of Computer Science, University of California... ..., 1999.
[22] Christoph Helma, Ross D. King, Stefan Kramer, and Ashwin Srinivasan. The predictive toxicology challenge 2000-2001 Bioinformatics, 17(1):107-108, 2001.
[23] Stefanie Jegelka. Theory of graph neural networks: Representation and learning. arXiv preprint arXiv:2204.07697, 2022.
[24] Leonard Kaufman and Peter J Rousseeuw. Partitioning around medoids (program pam). Finding groups in data: introduction to cluster analysis, 344:68-125, 1990.
[25] Henry Kenlay, Dorina Thanou, and Xiaowen Dong. On the stability of polynomial spectral graph filters. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 5350-5354. IEEE, 2020.
[26] Henry Kenlay, Dorina Thano, and Xiaowen Dong. On the stability of graph convolutional neural networks under edge rewiring. In ICASSP 202/-2021 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 8513-8517. IEEE, 2021.
[27] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
(28) Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. In International Conference on Learning Representations, 2020.
[29] Derek Lim, Joshua Robinson, Lingxiao Zhao, Tess Smidt, Suvrit Sra, Haggai Maron, and Stefanie Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202. 13013, 2022.
[30] Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28 (2),129-137, 1982.
[31] Ronny Luss and Alexandre d' Aspremont. Support vector machine classification with indefinite kernels. Advances in neural information processing systems, 20, 2007.
[32] Facundo Mémoli. Grosov-wasserstein distances and the metric approach to object matching. Foundations of computational mathematisss 11(4):477-477, 201
[33] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference Learning Representations, 2018.
[34] C. Morris, M. Ritzert, M. Fey, W. L. Hamilton, J. E. Lenssen, G. Rattan, and M. Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks. 2019.
[35] Christopher Morris, Nils M Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs arXiv preprint 2wXiv:2007.08663. 2020.

---

[36] Assaf Naor and Yuval Rabani. On lipschitz extension from finite subsets. Israel Journal of Mathematics, 21- 2017.
[37] Adam M Oberman and Jeff Calder. Lipschitz regularized deep neural networks generalize. 2018.
[38]
Karl Pearson. The problem of the random walk. Nature, 72(1865):29--244, 1905.
[39]
Jan Ramon and Thomas Gärtner. Expressivity versus efficiency of graph kernels. In Proceedings of the first international workshop mining graphs, trees and sequences, pages 65-74, 2003.
[40] Alberto Sanfeliu and King-Sun Fu. A distance measure between attributed relational graphs for pattern recognition. IEEE transactions on systems, man, and cybernetics, (3):353-362, 1983,
[41] Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Fast unbalanced optimal transport on a tree. Advances in neural information processing systems, 19:19,,9-19051, 2020.
[42] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The sapnik-chervonenkee dimension of graph and recursive neural networks. Neural Networks, 108:248 259, 2018.
[43] Jian Shen, Yanru Qu, Weinan Zhang, and Yong Yu. Wasserstein distance guided representation learning for domain adaptation. In Thirty-second AAAI conference on artificial intelligence, 2018.
[44] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfeiler-lchman graph kernels. Journal of Machine Learning Research, 12(9). 2011.
[45] Shashank Singh and Barnabás Póczos. Minimax distribution estimation in wasserstein distance. arXiv preprini /802008880. 2018.
[46] Matteo Togninalli, Elisabetta Ghisu, Felipe Llinares-López, Bastian Rieck, and Karsten Borg- wardt. Wasserstein weisfeiler-lehman graph kernels. Advances in Neural Information Processing Systems, 32, 2019.
[47] Adrien Vacher, Boris Muzellec, Alessandro Rudi, Francis Bach, and Francois-Xavia Xavier Vialard. dimension-free computational upper-bound for smooth optimal transport estimation. In Conference on Learning Theory, pages 4143-4173. PMLR, 2021.
[48] Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(11) 2008.
[49] Titouan Vayer, Lactitia Chapel, Rémi Flamary, Romain Tavenard, and Nicolas Courty. Optimal transport for structured data with application on graphs. In ICML 2019-36th International Conference Machine Learning, pages 1-16, 2019.
[50] Cédric Villani. Optimal transport: old and new, volume 338. Springer, 2009.
[51] Aladin Virmaux and Kevin Scaman. Lipschitz regularity of deep neural networks: analysis and efficient estimation. Advances Neural Information Processing Systems, 31, 2018.
[52] S Vichy N Vishwanathan, Nicol Schraudolph, Risi Kondor, and Karsten M Borgwardt. Graph kernels. Journal of Machine Learning Research, 1 11:12111222, 2010.
[53] Boris Weisfeiler and Andrei Leman. The reduction of a graph to canonical form and the algebra which appears therein. NTI, Series, 229): 1968.
[54] K. Xu, M. Zhang, J. Li, S. Du, K. Kawarabayashi, and S. Jegelka. How neural networks extrapolate: From feedforward to graph neural networks. 2021.
[55] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2018.
[56] Keyulu Xu, Mozhi Zhang, Jingling Li, Simon Shaolei Du, Ken-Ichi Kawarabayashi, and Stefanie Jegelka. How neural networks extrapolate: From feedforward graph neural networks. In International Conference Learning Representations, 2020.
12

---

[57] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. On size generaliza- tion in graph neural networks. 2020.
[58] Gilad Yehudai, Ethan Fetaya, Eli Meirom, Gal Chechik, and Haggai Maron. From local structures size generalization in graph neural networks. In International Conference Machine Learning, pages 1 11975-11986. PMLR, 2021.
[59] Rich Zemel, Yu Wu, Kevin Swersky, Toni Pitassi, and Cynthia Dwork, Learning fair representa- tions. In International conference machine learning, pages 325-333. PMLR, 2013.
[60] Han Zhao, Remi Tachet Des Combes, Kun Zhang, and Geoffrey Gordon. On learning invariant representations for domain adaptation. In International Conference on Machine Learning, pages 7523-7532. PMLR, 2019,
13

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], , or [N/A] . You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section ??.
Did you include the license the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below,
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(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]
(b) Did you include complete proofs of all theoretical results? [Yes] See the Appendix
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] In the zip file
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See the Appendix
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material or as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
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]
14


Reviews:
[{"review_id": "x0unAcOz-ke", "reviewer": "Reviewer_QSky", "summary": "The authors first propose TMD, a pseudometric for comparing graphs to each other. TMD compares graphs to each other by recursively solving a series of optimal transport problems which minimizes distances of subtree patterns. The proposed pseudometric is evaluated in graph classification (distances fed to an indefinite kernel and then to SVM). The results indicate that TMD performs on par with the best performing baselines. The authors also provide some theoretical results. First, they bound the Lipschitz constant of the GIN model with respect to TMD, and also analyze the stability of GIN under node deletions, edge deletions and perturbations of node features. Finally, they provide a result about the generalization error of GIN under distribution shifts.", "questions": "For the graph classification task, it is not clear to me why an SVM classifier with indefinite kernel is employed. Since TMD computes distances, the natural way to perform classification would be to employ the k-nn classifier. Did the authors experiment with that classifier and how does it compare to the SVM classifier?\n\nTypos:\\\nl.205: \"the empirically performance\" --> \"the empirical performance\"\n", "limitations": "The authors discuss the limitations and potential negative societal impact of their work.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- In my view, the originality of the paper is high. The proposed TMD distance is novel. Previous studies have applied optimal transport techniques on the labels produced by the WL algorithm, but in my understanding, the proposed recursive definition is different from previous work.\n\n- I really like the results about the stability of graph neural networks. Most previous studies have focused on a different problem: whether a graph neural network can distinguish classes of non-isomorphic graphs or not. Not much work has been done on the distance between the graph representations. I am not thought sure how useful the experiments of subsection 5.3 are. What's the purpose of showing that the correlation between TMD and a graph neural network is high? Furthemore, does this hold for all datasets?\n\nWeaknesses:\n- The computational complexity of the proposed distance function is very high since it needs to solve a series of optimal transport problems. This renders the method practically infeasible for datasets that contain large graphs (such as REDDIT-BINARY) and datasets that contain many samples (such as the OGB graph property prediction datasets). Of course, for the optimal transport problem, one could use some approximate algorithm, but still I don't think the proposed method can be applied to large datasets.\n\n- As one can see in Table 1, the proposed method provides only marginal improvements in accuracy over the baselines. Furthermore, TMD is not compared against several state-of-the-art graph neural networks. It is only compared against GIN and GCN which are at most as expressive as 1-WL. It would be nice if the authors could also report the running time of TMD and compare it against that of the Wasserstein WL function.\n\n- The message passing scheme of GIN given in subsection 5.1 is different from the one provided in the original paper, i.e., $z_v^{(l)} = \\phi^{(l)} ((1+\\epsilon^{(l)})z_v^{(l-1)} +\\sum_{u \\in \\mathcal{N}(v)} z_u^{(l-1)})$. Furthermore, both for the experiments and for the proof of Theorem 8, the authors set $\\epsilon=1$. GIN is known to be less expressive than 1-WL when $\\epsilon=1$. Furthermore, the message passing scheme of GCN given in Appendix B.1 is not correct. Thus, I wonder whether the Lipschitz constant of any message passing graph neural network can be bounded under TMD or are there some conditions that need to be satisfied?\n\n- Even though TMD is sufficiently different from the Wasserstein WL pseudometric, I would suggest the authors provide more details about how the two methods differ from each other and also compare the complexities of the two approaches to each other.", "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": "DiVioYu8vS", "reviewer": "Reviewer_DmtC", "summary": "This paper introduces a graph pseudo-metric based on the hierarchical Optimal Transport , to understand the generalization of machine learning models on graphs. They show that the proposed TMD captures properties relevant to graph classification and can be related to generalization of GNNs under distribution shifts.  ", "questions": "1. Can the authors provide an example regarding “the distance $TMDLw(Ga, Gb)$ can be zero even if $Ga = Gb$”.\n2.  The notation in Definition 4 is confusing. What is the $OT_{TD_w}$?\n3. The complexity of iteratively calculating the distance between the L-depth trees is high. The running time of baselines and the proposed methods shall be added.\n", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is well-written and easy to follow, although there exist some unclear descriptions.\n2. This paper proposes a new OT distance for graphs. Using the computation trees of the graph to calculate the distance between two graphs is direct and reasonable.\n3. The Lipschitz Constant and Stability analysis of GNNs seem to be useful and meaningful.\n\nWeaknesses:\n\n1. ”TMD can provably distinguish graphs that are identifiable by the (1-dimensional) Weisfeiler-Leman graph isomorphism test”. The authors say it can be further strengthened by augmenting node attributes e.g. with positional encodings, but they have not provided the details. Since expressive power is very important for graph representation learning.\n2.  The computational complexity of TMD is high. The authors only implement it on CPU (POT package). It is unclear whether the method can be accelerated by GPUs.\n3. Some baselines on graph OT are missing, for example, [1] [2] bellow.  \n\n\n[1] GOT: An Optimal Transport framework for Graph comparison\n[2] COPT: Coordinated Optimal Transport on Graph.\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": "7fdciPm0uDy", "reviewer": "Reviewer_tWYt", "summary": "Authors introduce a new (pseudo) distance on attributed graphs, the Tree Mover's distance (TMD). They first introduce Then authors introduce a distance between trees (TD) which aims at recursively comparing their roots, through their respective attributes, and their subtrees using optimal transport (OT) to get hard assignments between these induced subtrees to pursue the recursion i.e comparing trees of smaller respective depth. TMD then naturally comes from TD by modeling graphs as multisets of trees rooted in each node of each graph. TMD is shown to define a proper pseudo-metric for which the axiom of discernability is closely related to the Weisfeiler-Lehman graph isomorphism test. After investigating the revelance of TMD for graphs classification, authors further study its relevance to quantify stability and generalization abilities of the well-known Graph Isomorphism Networks (GIN), being SOTA graph neural networks.", "questions": "For clarity and conciseness my questions/doubts have been clearly stated in the \"Strengths and weaknesses\" section.\n\n", "limitations": "A few limitations of their work have not really been addressed as illustrated by my elaboration on the \"weaknesses/points for clarification\" paragraph. The authors have adequately addressed the potential negative societal impact of their work in the supplemental material.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "$\\textbf{Strengths}$:\n\n- Overall the paper is well-written and the design of TMD is elegant/original. The authors have managed to clearly address a wide variety of concepts, from kernels to GNNs. An obvious pedagogical effort has been made in several proofs of the results provided, which is appreciable.  \n\n- TMD is interesting by its flexibility suggested by its dependencies to a depth-dependent weighting function and to cost functions inherent to used OT (on nodes). \n\n- TMD seems competitive as a kernel in graphs classification and mostly shines on the study of GIN.\n\n$\\textbf{Neutral about}$:\n\n- Without a clear characterization of TMD balls in the space of attributed graphs (or at first, unattributed graphs), I find it difficult to envision how TMD can guide GNN to further improvements, but given the difficulty of this task, the empirical evidence provided in Sections 5 and 6 supports the relevance of TMD for this purpose.  \n\n$\\textbf{Weaknesses / points to clarify}$:\n\n- Authors exploit specific properties of the Kantorovich formulation of OT (especially its relation to Monge's formulation) which are eluded in the paper and clearly not straightforward so, to improve the clarity of the document e.g the need for definitions 2 and 3, it would be good to mention them (Also the caption of figure 1 can be improved for this purpose).\n\n- Theorem 7: From your proof I would say that the stated implication is actually an equivalence. Could you elaborate on this ?\n\n- On the graphs classification benchmark : I am not sure to understand your validation scheme from your explanations. From my understanding you did a cross-validation for TMD, while e.g authors of FGW reported a 10-fold nested cross-validation in their paper  (Which better quantifies generalization abilities and is more natural for graph kernel methods as the computational bottleneck lies in the computation of the kernel matrix). Therefore I suggest harmonizing the validation scheme on kernel methods instead of just reporting the performance of the respective papers. Moreover, could you complete the benchmark on graphs classification with a benchmark in terms of runtimes ?\n\n- On subsection 5.1: There is a difference between your formulation of message-passing and the one from GIN (see equation 4.1 of [48]), $\\epsilon$ is not handled in the same way. As you set $\\epsilon=1$ for your experiments they are still valid, but the implications of this change for the theoretical results in your paper and the ones in GIN's paper are not clear to me, even if it seems minor. Could you elaborate on this ?  \n\n- There is no reference to the figure 4 and 5 in the main paper.\n\n**Modification:** I increased my initial grade from 5 (borderline accept) to 6 (weak accept) after a convincing rebuttal and discussion by the authors.", "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": "4pJei-RM_sE", "reviewer": "Reviewer_pkBn", "summary": "A metric on the set of graphs is defined using concepts from optimal transport.  It is shown both analytically and by experiment that graph neural networks define Lipschitz continuous functions in the metric.\n", "questions": "Let me check in an example that I understand how the definition works for graphs without features.  \nLet T_N be the tree with a root and N children.  The distance TD(T_m,T_n)=|n-m| because\nthe distance between a blank tree (feature vector = 0) and a generic vertex (feature vector = 1) is 1.\n\nIf so then for graphs with features, the definition depends on the point 0 chosen for the blank tree feature.\nThis should be mentioned more explicitly.", "limitations": "Technical results with no immediate societal impact.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The proposal is clear and well motivated, and has evident applications.  The evaluation is adequate for a first work.\n\nWeakness: Graph metrics are a much studied field and there is little comparison with previous work.", "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