针对图的特征工程方法主要是核方法（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。