Weisfeiler-Lehman Graph Kernels
Weisfeiler-Lehman Graph Kernels
Nino Shervashidze, etc.
Intro
提出了一类kernel方法，在大型图上的discrete label。
求graph isomorphism是NP问题，但是还没有被证明是否为NP－complete或者能够在polynomical－time内求解。
Review of Graph Kernels
walk是图上的一条通路。path是不包含相同节点的walk。
graph kernel大致能够分为三类：
- based on walks: 计算两个图之间walk一样的个数。 morgan fingerprints就是一类walk-based graph kernel。
- based on limited-size subgraphs：包括kernel based on graphlets，是讲一个图表示为subgraph的计数。
- based on subtree patterns：为了比较两张图，这类kernel会迭代的比较两张图的两个节点之间的neighbors。
这些graph kernels很难用到超过100个节点的大图上，这也使得large labeled graph的问题未解决。
Weisfeiler-Lehman Test of Isomorphism
算法的核心想法是：将每一个节点的label augmented by the sorted neighbor labels，然后将augmented label压缩到新的label。
The General Weisfeiler-Lehman Kernels
Weisfeiler-Lehman Kernel只是一个计算kernel的框架，更具体的操作还得看base kernel。