论文标题
Wasserstein图形距离基于$ l_1 $ approxtroximated的树编辑weisfeiler-lehman子树之间的距离
Wasserstein Graph Distance Based on $L_1$-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees
论文作者
论文摘要
Weisfeiler-Lehman（WL）测试是图形机学习中广泛使用的算法，包括图内核，图指标和图神经网络。但是，它仅着眼于图的一致性，这意味着它无法检测到轻微的结构差异。因此，这限制了其捕获结构信息的能力，这也限制了依赖WL测试的现有模型的性能。对于由WL测试定义的传统指标，这种限制尤其严重，WL测试无法精确捕获略有结构差异。在本文中，我们提出了一个新的图形指标，称为Wasserstein WL子树（WWLS）距离，以解决此问题。我们的方法利用WL子树作为节点社区的结构信息，并使用节点的WL子树之间的$ L_1 $ - APPROXAPTROXIMATER TROE距离（$ L_1 $ - ted）定义节点指标。随后，我们结合了Wasserstein距离和$ L_1 $来定义WWLS距离，该距离可能会捕获轻微的结构差异，使用常规指标可能难以检测。我们证明，在公制验证和图形分类实验中，提出的WWLS距离胜过基线。
The Weisfeiler-Lehman (WL) test is a widely used algorithm in graph machine learning, including graph kernels, graph metrics, and graph neural networks. However, it focuses only on the consistency of the graph, which means that it is unable to detect slight structural differences. Consequently, this limits its ability to capture structural information, which also limits the performance of existing models that rely on the WL test. This limitation is particularly severe for traditional metrics defined by the WL test, which cannot precisely capture slight structural differences. In this paper, we propose a novel graph metric called the Wasserstein WL Subtree (WWLS) distance to address this problem. Our approach leverages the WL subtree as structural information for node neighborhoods and defines node metrics using the $L_1$-approximated tree edit distance ($L_1$-TED) between WL subtrees of nodes. Subsequently, we combine the Wasserstein distance and the $L_1$-TED to define the WWLS distance, which can capture slight structural differences that may be difficult to detect using conventional metrics. We demonstrate that the proposed WWLS distance outperforms baselines in both metric validation and graph classification experiments.
