<Weisfeiler-Lehman Graph Kernels>
为衡量GNN的表达能力,我们通常会选用Weisfeiler-Leman算法进行比较,WL算法产被用于做图同构测试(Graph Isomorphism Test)
节点的信息包括结构信息和自身特征信息,WL算法用hash来编码和判断两个节点是否一致:
\[h_l^(t)(u) = HASH(h_l^{t-1}(u), \mathcal F(h_l^{t-1}(v))|v \in N(u)))\]$\mathcal F$是邻居节点的聚合函数,和GraphSAGE很类似,但这里采用了更“无损”的HASH编码。
算法流程是:1. 聚合、编码节点信息, 2. 将节点信息映射到一个实数(向量、符号等,其他也行),重新将这个实数赋给节点。反复迭代,用Jaccard相似度计算两个图节点信息集合的相似性。