Wasserstein Graph Distance based on L1-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees
Wasserstein Graph Distance based on L1-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees
复制标题
DOI：
10.48550/arxiv.2207.04216
复制
发表时间：
2022-07
期刊：
影响因子：
--
通讯作者：
Zhongxi Fang;Jianming Huang;Xun Su;Hiroyuki Kasai
中科院分区：
文献类型：
--
作者：
Zhongxi Fang;Jianming Huang;Xun Su;Hiroyuki Kasai
Weisfeiler-Lehman（WL）测试是图机器学习中广泛使用的算法，包括图内核，图度量和图神经网络。然而，它只关注图的一致性，这意味着它无法检测到细微的结构差异。因此，这限制了它捕获结构信息的能力，这也限制了依赖WL测试的现有模型的性能。这种限制对于WL测试定义的传统指标尤其严重，因为它无法精确地捕捉细微的结构差异。在本文中，我们提出了一种新的图形度量称为Wasserstein WL子树（WWLS）距离来解决这个问题。我们的方法利用WL子树作为节点邻域的结构信息，并使用WL子树节点之间的L1近似树编辑距离（L1-TED）定义节点度量。随后，我们结合联合收割机的Wasserstein距离和L1-TED定义的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 L1-approximated tree edit distance (L1-TED) between WL subtrees of nodes. Subsequently, we combine the Wasserstein distance and the L1-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.