Presentation information

International Session

International Session » ES-2 Machine learning

[4S1-IS-2f] Machine learning

Fri. Jun 17, 2022 10:00 AM - 11:20 AM Room S (Online S)

Chair: Hisashi Kashima (Kyoto University)

10:40 AM - 11:00 AM

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

〇Zhongxi Fang1, Jianming Huang1, Hiroyuki Kasai1 (1. WASEDA University)


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.

Authentication for paper PDF access

A password is required to view paper PDFs. If you are a registered participant, please log on the site from Participant Log In.
You could view the PDF with entering the PDF viewing password bellow.