Towards Efficient and Accurate NP-hard Graph Matching Tasks

Abstract

Graph deep learning models have been popular in graph based applications such as node classification, link prediction, community detection, etc. The expressive power of deep learning models combined with the increasing amount of graph data enables researchers to solve graph tasks that are traditionally done via algorithmic approaches. However, how to perform graph matching related tasks such as Graph Edit Distance (GED) computation, Maximum Common Subgraph (MCS) detection, still requires careful design and utilization of graph deep learning models, due to the unique challenges posed by these NP-hard problems.

In this talk, I present several recent works on tacking graph similarity computation and Maximum Common Subgraph (MCS) detection. I start with presenting SimGNN, a graph deep learning model aiming to approximate any graph similarity measure, such as GED, MCS, domain-specific similarity signals, etc. I then show our such model can be extended to real-world scenario where a large graph database is given, and a learned indexing is needed to perform fast and accurate search. The method is called GHashing. Finally, I discuss about GLSearch, an reinforcement learning based graph deep learning model enhanced with a branch-and-bound algorithm to detect the Maximum Common Subgraph between any input graphs in an accurate way under limited search budget.

Bio:

Yunsheng Bai is an 5-th year PhD student at the University of California, Los Angeles (UCLA) whose advisors are Professor Yizhou and Professor Wei Wang. His research focuses on developing novel methods for graph-related tasks. He is especially interested in graph neural networks for graph-level tasks including graph similarity, graph matching, graph- level representation learning, etc. Before joining UCLA, he completed his BS from the University of Michigan, Ann Arbor. His publications have appeared in conferences of domains ranging from data mining to artificial intelligence and machine learning, including WSDM, KDD, IJCAI, AAAI, ICML, etc.

Please join meeting in Halligan 102 or via Zoom.

Join Zoom Meeting: https://tufts.zoom.us/j/97183120811

Meeting ID: 971 8312 0811

Password: See colloquium email

Dial by your location: +1 646 558 8656 US (New York)

Meeting ID: 971 8312 0811

Passcode: See colloquium email