[4S1-IS-2f] Machine learning

[4S1-IS-2f-03] A Novel Distance between Graph Structures Based on the Weisfeiler-Lehman Algorithm

〇Zhongxi Fang¹, Jianming Huang¹, Hiroyuki Kasai¹ (1. WASEDA University)

Regular

Keywords:graph machine learning, network similarity, graph classification

Defining a valid graph distance is a challenging task in graph machine learning because we need to consider the theoretical validity of the distance, its computational complexity, and effectiveness as a distance between graphs. Addressing the shortcomings of the popular Weisfeiler-Lehman (WL) algorithm in graph kernels, this paper proposes a novel distance between graph structures. More specifically, we first analyze the WL algorithm from a geometric point of view and argue that discriminating nodes based on only the consistency of categorical labels do not fully capture important structural information. Therefore, instead of using such categorical labels, we define a node distance between WL subtrees with tree edit distance and propose an efficient calculation algorithm. We then apply the proposed node distance to define a graph Wasserstein distance on tree edit embedding space exploiting Optimal Transport framework. To summarize, we define tree edit distance between nodes and reflect it at the graph level. Numerical experimentations on graph classification tasks show that the proposed graph Wasserstein distance performs equally or better than conventional methods.