Wasserstein Weisfeiler-Lehman Graph Kernels

2 Background

2.1 Graph Kernel

Weisfeiler-Lehman (WL) subtree 是通过将node representation求个sum来得到graph-level representation。然后引用了optimal transport theory，比如Wasserstein distance。

2.2 Wassertein distance

$$Wp(\sigma, \mu) = \big(\inf{\gamma \in \tau(\sigma, \mu)} \int_{M \times M} d(x,y) ^p d\gamma (x,y) )\big)^{1/p}$$

$$\Gamma (\sigma, \mu)$$是所有transportation plans，over $$M \times M$$ 且两个marginal分别是$$\sigma$$和 $$\mu$$。

如果$$d$$是一个metric，那么wasserstein也符合metric定理。

这篇paper里面，我们处理的是set of node embeddings，not with continuous prob distributions。因此我们可以将wasserstein distance重写为sum，而不是integral。两个vector set之间的distance定义为

$$ W1(X, X') = \min{P \in \Gamma(X, X')} \langle P, M \rangle

$$

3 Wasserstein distance on graphs

3.1 Generating node embeddings

用Weisleifer-Lehman scheme，定义

$$l^{h+1}_{v} = hash(l^h_v, \mathcal{N}^h(v))$$

但上述的特征是离散的，我们为了是的他能够连续，提升了WL refinement step。

$$a^{h+1}v = \frac{1}{2} \Big( a^h_v + \frac{1}{deg(V)} \sum{u \in \mathcal{N}(v)} w(v,u) \cdot a^h_u \Big)$$

有了以上，可以顺带提出WL-based graph embedding。对于某一层，有graph embedding是每一个node embedding的concatentation。而后把所有层的graph embedding concat即可。

3.2 Computing the Wasserstein distance

对于categorical node features，使用Hamming distance。

对于cts node features，使用Euclidean distance。

然后将这个distance放到matrix $$D$$中。

4 From Wasserstein distance to kernels

有了Wasserstein distance，就可以计算kernel。

$$K{WWL} = e^{- \lambda D_W^{f{WL}}}$$