CS224W(1.14)Lecture 2. Traditional Methods for ML on Graphs-针对图的特征工程方法

针对图的特征工程方法主要是核方法(Kernel methods),这里的核方法和SVM中的核方法是一个意思,都是把特征映射到高维空间,在高维空间的特征交互可以用低维空间的核矩阵来表示。

图上的核方法的核心思想是bag-of-words,即统计不同子图(相当于words)的个数,比如下图子图4中是统计不同度的节点的个数,则这里度为k的节点就是一个不同的word,最后得到bag-of-words向量,比如[1,2,1]。前面介绍针对节点的特征工程时,其中的GDV向量本质上是bag of graphlets。

在介绍针对图的特征工程方法时,会介绍两种核方法:Graphlet Kernel和Weisfeiler-Lehman Kernel。

Graphlet Kernel

graph-level的graphlet特征和node-level的graphlet特征不太一样。graph-level的graphlet可以不联通,且没有rooted,所以简单理解就是比如k=3时,graphlet就是3个顶点可以连成的不同形状(不同构)的图,如下图子图2,k=3时,有4个graphlet。

如下子图3,给定这样一个图,k=3时不同graphlets的数目向量为[1,3,6,0]。举个例子,比如算有多少个g2时,只需要保证考察的3个点中只有2条边,至于这3个点和其他点是否有连边,并不影响其是否符合g2这个graphlet,只要被考察的3个点满足只有2条边就行。所以这个图一共可以找出3个g2出来。

类似的,计算有多少个g3时,只需要保证考察的3个点有一条边,有一个孤立点就行,至于这个孤立点和这3个点之外的其他点是否有连边,并不影响其是否符合g3这个graphlet。

得到图的graphlet个数向量之后,相当于得到了图的graph-level的特征向量,graph kernel就是对两个图的graphlet向量进行各种运算了。

Weisfeiler-Lehman Kernel

由于判断子图是否同构是一个NP-Hard问题,计算graphlet向量成本太高了,Weisfeiler-Lehman kernel是一个更加高效的针对图的特征工程方法。

Weisfeiler-Lehman Kernel(WL Kernel)的思想是通过聚合邻居的特征来更新自身节点的特征,已经有GNN的味道了。实现的算法是color refinement算法,具体来说,就是给每个节点一个初始的颜色,然后每次聚合邻居的颜色,然后进行某种HASH运算,得到更新后的颜色;然后再进行聚合;如此循环往复,聚合K次之后,就能得到K-跳邻居的信息了。这不就是GraphSAGE吗哈哈。

如下是课上的一个例子:初始的时候所有节点的颜色都是1,然后通过聚合邻居颜色并hash进行更新,迭代了几轮之后,计算迭代过程中出现过的所有不同颜色的节点的个数,得到WL向量。最后两个图的WL向量就可以进行各种运算了,比如点乘得到49。

WL Kernel的计算很高效,其每一步邻居聚合的时间复杂度和边的数目是线性关系。

小结一下,针对图的特征工程方法中,核心思想是词袋模型,比如Graphlet kernel相当于bag-of-graphlets,而WL kernel相当于bag-of-colors。

1 thought on “CS224W(1.14)Lecture 2. Traditional Methods for ML on Graphs-针对图的特征工程方法

  1. Pingback: 《Inductive Representation Learning on Large Graphs》阅读笔记 | bitJoy

Leave a Reply

Your email address will not be published. Required fields are marked *