1. Weisfeiler-Leman Algorithm

<Weisfeiler-Lehman Graph Kernels>

为衡量GNN的表达能力,我们通常会选用Weisfeiler-Leman算法进行比较,WL算法产被用于做图同构测试(Graph Isomorphism Test)

1.1 算法思路

节点的信息包括结构信息和自身特征信息,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相似度计算两个图节点信息集合的相似性。

2. How powerful are graph neural networks

GNN 教程:GNN 模型有多强? - ArchWalker