Message Passing Graph Kernels

Message Passing Graph Kernels

Giannis Nikolentzos, Michalis Vazirgiannis

Intro

在bioinformatics，social networks，和cybersecurity中，有非常多的graph-structured data。过去几年，graph classification在chemoinformatics，malware detection，和text categorization有很多影响。

graph kernel是定义在graph space上的positive semidefinite函数，这个函数同时也是某个希尔伯特空间的内积函数。（希尔伯特空间这里可以理解为特征空间）。已有的方法无法很好scale到graph with tens of vertices。

这篇paper提出了设计graph kernel的一个框架，叫Message Passing graph kernels （MPGK）。有两部分组成： 1. vertice之间的kernel 2. graph之间的kernel

Preliminaries

保证vertix-level的order invariant。

目前message passing neural network使用的都是sum up：将每一个vertex的neighbor信息求一个sum。这的确保证了order invariant，但是同时也会限制了这类模型的representation power。

Message Passing Graph Kernels

因为使用了更加复杂的permutation invariant kernel，所以这个框架会比一般的neural network更加慢。

$$kv$$表示vertices之间的kernel，$$k{\mathcal{N}(v)}$$表示neighbors之间的kernel。然后提出的框架会迭代式地计算任意两个vertices之间的kernel $$k_v^t$$。更新的方式如下

$$ kv^{t+1} (v_1, v_2) = \alpha k_v^t(v_1, v_2) + \beta k{\mathcal{N}(v)}(\mathcal{N}(v_1), \mathcal{N}(v_2))

$$

将以上执行了T步之后，graph之间的kernel可以表示为

$$ k_G(G_1, G_2) = k_V(V_1, V_2)

$$

其中 $$k_V$$ 表示的是vertices set之间的kernel。

为了计算上述两个kernel，我们用两个kernel设计中常用的design paradigms 1. R-convolution framework 2. theory of valid optimal assignment kernel

给定两个vertices set，提出以下R-convolution kernel

$$ kV(V_1, V_2) = \sum{v1 \in V_1} \sum{v2 \in V_2} k_v(v_1, v_2)

$$

和assignment kernel

$$ kV(V_1, V_2) = \max{B \in \mathcal{B}(V1, V_2)} \sum{(v_1,v_2)\in B} k_s(v_1, v_2)

$$

这两个kernel都满足permutation invariant，因此可以考虑用来比较两个graph/vertice neighbor。

由此可以得到更新vertex kernel的函数：

$$ kv^{t+1} (v_1, v_2) = \alpha k_v^t(v_1, v_2) + \beta \sum{u1\in\mathcal{N}(v_1)} \sum{u_2\in\mathcal{N}(v_2)} k_v^t(u_1, u_2)

$$

和

$$ kv^{t+1} (v_1, v_2) = \alpha k_v^t(v_1, v_2) + \beta \max{B\in\mathcal{B}(\mathcal{N}(v1), \mathcal{N}(v_2))} \sum{(u_1,u_2)\in B} k_s^t(u_1, u_2)

$$

而graph kernel就变为(T step之后)

$$ kG(G_1, G_2) = \sum{v1 \in G_1} \sum{v_2 \in G_2} k_v^T(v_1, v_2)

$$

和

$$ kG(G_1,G_2) = \max{B\in\mathcal{B}(G1,G_2)} \sum{(v_1,v_2) \in B} k_s^T(v_1,v_2)

$$

在vertex-level和graph-level选择不同的kernel，对应四种方式。表示为MPGK RR/RA/AR/AA。

离散label，使用delta kernel；连续label使用linear kernel。后续有一部分引用了15的做法：定义了一个hierarchy $$H(T,w)$$，其中包含了strong kernel $$k_s$$。为了构造这个hierarchy，我们使用clustering方法。其中的similarity使用的即为上一步的kernel。weighting function $$w$$则如下定义：root $$r$$设置为1。其他非root节点$$v$$则设置为$$w(v) = (sp(v,r)-1) / sp(v,r)$$，其中$$sp(v,r)$$是r到v最短路径的长度。

和Weisfeiler-Lehman Subtree Kernel的相似性。

Low Rank Approximation

Appendix

15 On Valid Optimal Assignment Kernels and Applications to Graph Classification

对于neighbor的利用性质？对于graph结构的利用还不够。