kernel 与 Wassertein distance"/>
graph kernel 与 Wassertein distance
graph kernel 与 Wassertein distance
- Wasserstein Weisfeiler-Lehman Graph Kernels
- 解决的问题
- 本文的贡献
- 符号说明及定义
- Wasserstein distance on graphs and graph kernel
最近读了两篇将 OT 应用于 graph kernel 的论文,有一些收获,在此总结一下。1999年 David Haussler 等人写的论文 Convolution Kernels on Discrete Structures 是介绍核函数的定义以及机器学习中经典核函数的经典论文,可以阅读此文章了解核函数的基础知识。同时,核函数在机器学习中的应用可以参考论文 核方法在分类、回归于聚类方面的研究及应用。对机器学习比较了解的同学们可以从论文的2.2看起。
话不多说,直接上干货。
Wasserstein Weisfeiler-Lehman Graph Kernels
解决的问题
提出一个更好的 graph kernel 来度量两个图之间的相似度,可用于图分类问题。目前的graph kernel 大部分是基于 R-Convolution kernel,它们存在一些问题:
- 目前大部分的 graph kernel 使用的是子结构集合的 naive aggregation (e.g. sum or average),这样会丢掉个体分布的重要信息。
- 仅仅有一小部分 graph kernel方法可以扩展到连续的 attributed graph 中(大部分的 graph kernel 只能用于 labeled graph)。
本文的贡献
- 基于两个图 node feature representations,提出了两个图之间的 graph Wasserstein distance。
- 受 Weisfeiler-Lehman 启发,并且融入了 Wasserstein distance(两个 graph 的 node feature vector distribution 之间),提出了图嵌入方案(对于 categorically labelled graph 和 continuously attributed graph 都有用),改进了图分类任务的预测性能。
- 对于带 continuous attributes 的图分类问题,建立了一个新的 graph kernel。
我们的方法依赖于以下几步:
(1) 将每个图像转化为 node embedding 集合;
(2) 度量每对图之间的距离;
(3) 计算可以用于后续学习算法的相似度矩阵;
符号说明及定义
一个图可以表示为 G = ( V , E ) G=(V, E) G=(V,E)。其中 V V V 为点集, E E E 为边集。
n G = ∣ V ∣ n_G=\vert V \vert nG=∣V∣, m G = ∣ E ∣ m_G=\vert E \vert mG=∣E∣。
A graph is labelled if its nodes have categorical labels. 也就是说图上每个节点都有一个函数 l : V → Σ l: V \to \Sigma l:V→Σ,其中 Σ \Sigma Σ 是有限的标签集。
A graph is attributed if for each node v ∈ V v \in V v∈V there exists an associated vector a ( v ) ∈ R m a(v) \in R^m a(v)∈Rm.
A graph has weighted edges if it has the function w : E → R w: E \to R w:E→R。
a ( v ) a(v) a(v) 为节点的 attributes,为一个整数, l ( v ) l(v) l(v) 为节点的分类标签,为高维的连续向量。
Wasserstein distance on graphs and graph kernel
在图中,每个点的嵌入向量为有限维,在两个向量集合 X ∈ R n × m X \in R^{n \times m} X∈Rn×m 和 X ′ ∈ R n ′ × m X' \in R^{n' \times m} X′∈Rn′×m 之间的 Wassertein distance 为
W 1 ( X , X ′ ) = min p ∈ Γ ( X , X ′ ) < P , M > W_1(X,X')=\min_{p \in \Gamma(X,X')} <P, M> W1(X,X′)=p∈Γ(X,X′)min<P,M>
其中 M M M 为 distance matrix, P ∈ Γ P \in \Gamma P∈Γ 为 transport matrix。
假设 需要被运输的 mass 之和为1,并且在 X X X 和 X ′ X' X′ 上均匀分布,因此 P P P 的行和与列和分别为 1 / n 1/n 1/n 和 1 / n ′ 1/n^{'} 1/n′。
我们的方法依赖于以下几步:
1. 将每个图像转化为 node embedding 集合;
对于 labelled node 可以借用 Weisfeiler-Lehman(WL) scheme 来获得节点嵌入。WL scheme 是通过聚集节点及其邻居的 label,不断迭代得到一系列字符串的过程。设 l h ( v ) l^h(v) lh(v)第 h h h次迭代结果,观察邻居节点集合 N h ( v ) = { u 0 h , … , u d e g ( v ) − 1 h } N^h(v)=\{ u_0^h, \dots, u_{deg(v)-1}^h \} Nh(v)={u0h,…,udeg(v)−1h}
l h + 1 ( v ) = h a s h ( l h ( v ) , N h ( v ) ) l^{h+1}(v)= hash(l^{h}(v), N^h(v)) lh+1(v)=hash(lh(v),Nh(v))
l 0 ( v ) = l ( v ) l^0(v)=l(v) l0(v)=l(v)
对于 continuous attributes node a ( v ) ∈ R m a(v)\in R^m a(v)∈Rm ,对 WL scheme 进行扩展,得到适应于具有连续特征的节点嵌入 。
a h + 1 ( v ) = 1 2 ( a h ( v ) + 1 d e g ( v ) ∑ u ∈ N ( v ) w ( ( u , v ) ) ⋅ a h ( u ) ) a^{h+1}(v)=\frac{1}{2} (a^h (v) + \frac{1}{deg(v)} \sum_{u \in N(v)} w((u,v)) \cdot a^h(u) ) ah+1(v)=21(ah(v)+deg(v)1u∈N(v)∑w((u,v))⋅ah(u))
a 0 ( v ) = a ( v ) a^0(v)=a(v) a0(v)=a(v)
如果边权重不存在,则令 w ( u , v ) = 1 w(u,v)=1 w(u,v)=1。
根据上述节点嵌入后,我们可以得到图嵌入。也就是说图嵌入矩阵的每一行就是一个节点的前H次嵌入向量的拼接。
2. 度量每对图之间的距离;
首先定义两个节点对之间的 ground distance。
对于节点的分类特征,使用 normalized Hamming distance:
(两个节点的距离等于每个特征的距离的平均值)
对于节点的连续特征,使用 Euclidean distance:
将 ground distance 带入 Definition 1,使用 network simplex method 计算 Wasserstein distance。
3. 计算可以用于后续学习算法的相似度矩阵;
这是一个 Laplacian kernel。具体的算法如下:
WWL kernel 的性质如下:
(1) 用于分类特征的 WWL kernel 对于所有的 λ > 0 \lambda>0 λ>0 都是正定的。
(2) 在更一般的情况下,WWL kernel 不一定为一个正定核。
由于 WWL kernel 是不定核,我们将 WWL kernel 用于 Krein space 空间的学习算法。在使用 Krein SVM 的分类任务中 WWL kernel 表现良好。
更多推荐
graph kernel 与 Wassertein distance
发布评论