报告主题：Subgraph Matching Revisited

报告人： Dr. Jeffrey Xu Yu

报告时间：2026年1月19日 下午 02:00

报告地点：北京大学王选计算机研究所106报告厅

Abstract: Various networks ranging from social networks, collaboration networks to biological networks, have grown steadily. Among many graph algorithms, subgraph matching has been extensively studied, which is to find matchings for a user-given pattern graph p in a large data graph G by subgraph isomorphism. To support subgraph matching, there are native graph approaches and relational-based approaches.  In this talk, we revisit the tree decomposition based approach.  For a complex pattern graph 𝑝, we find its optimal tree decomposition 𝑇 based on the fractional hypertree width, where a node in 𝑇 represents a subgraph of 𝑝, which is also called a bag, and a node in 𝑝 may appear in multiple bags in 𝑇. The tree decomposition based approach initially computes and materializes the matches of subgraphs specified by the bags, then treats these matches as new relations and employs an acyclic join to compute the matches of 𝑝.  We give a new subgraph matching algorithm ASDMatch (Adaptive Shared Decomposition-based matching). We discuss how to find optimal attribute orders for each bag, and how to adaptively materialize to reduce the computation cost.

Bio: Dr. Jeffrey Xu Yu is a Professor in the Data Science and Analytics Thrust at The Hong Kong University of Science and Technology (Guangzhou). His primary research interests include graph algorithms, graph processing systems, graph neural networks, and query processing in database systems. Dr. Yu has held several prestigious roles, including Information Director and member of the ACM SIGMOD Executive Committee (2007–2011), Associate Editor of IEEE Transactions on Knowledge and Data Engineering (TKDE) (2004–2008), and Associate Editor of the VLDB Journal (2007–2013). He currently serves as an Associate Editor for ACM Transactions on Database Systems (TODS) and the WWW Journal, among others. Dr. Yu has been actively involved in the organization and program committees of numerous international conferences and workshops. He has served as PC Co-Chair for conferences such as APWeb'04, WAIM'06, APWeb/WAIM'07, WISE'09, PAKDD'10, DASFAA'11, ICDM'12, NDBC'13, ADMA'14, CIKM'15, Bigcomp'17, DSAA'19, CIKM'19, and DASFAA'20, and as Conference General Co-Chair for APWeb'13, ICDM'18, and ADC'22.