AAAI-23 “Wasserstein Graph Distance with L1 TED between WL Subtrees”


2023年2月7日から2月14日にワシントン(米国)で開催される人工知能分野・トップ会議 Thirty-Seventh AAAI Conference on Artificial Intelligence (AAAI-23) に1件の研究論文が採択されました.

  • Wasserstein Graph Distance based on L_1-Approximated Tree Edit Distance between Weisfeiler-Lehman Subtrees

    • Author: Zhongxi Fang (M2, 2nd-year graduate student), Jianming Huang (D1), Xun Su (M2), and HK
    • Abstract: The Weisfeiler-Lehman (WL) test has been widely applied to graph kernels, metrics, and neural networks. However, it considers only the graph consistency, resulting in the weak descriptive power of structural information. Thus, it limits the performance improvement of applied methods. In addition, the similarity and distance between graphs defined by the WL test are in coarse measurements. To the best of our knowledge, this paper clarifies these facts for the first time and defines a metric we call the Wasserstein WL subtree (WWLS) distance. We introduce the WL subtree as the structural information in the neighborhood of nodes and assign it to each node. Then we define a new graph embedding space based on L_1-approximated tree edit distance (L_1-TED): the L_1 norm of the difference between node feature vectors on the space is the L_1-TED between these nodes. We further propose a fast algorithm for graph embedding. Finally, we use the Wasserstein distance to reflect the L_1-TED to the graph level. The WWLS can capture small changes in structure that are difficult with traditional metrics. We demonstrate its performance in several graph classification and metric validation experiments.
    • Paper: arXiv preprint arXiv:2207.04216
    • Source code: GitHub.

Conference information: AAAI

  • The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. (excerpt from the website.) 
  • Google Scholar Metric H5-index: 180 (checked on Nov. 22, 2022)