Recent progress on random graph matching problems(随机图匹配问题的研究进展)

时间:2023-05-25         阅读:


主 题Recent progress on random graph matching problems(随机图匹配问题的研究进展)

主讲人北京大学 丁剑教授

主持人统计学院 林华珍教授

时间:5月26日 14:00-15:00


主办单位:统计研究中心 统计学院 科研处



Jian Ding is Chair Professor at Peking University. His main research area is in probability theory, with focus on interactions with statistical physics and theoretical computer science. He also has a broad interest in probability questions that arise from "application-oriented" problems. Before joining PKU, he has been a postdoc at Stanford and a faculty member at University of Chicago as well as University of Pennsylvania, after his Ph.D. at UC Berkeley in 2011.




A basic goal for random graph matching is to recover the vertex correspondence between two correlated graphs from an observation of these two unlabeled graphs. Random graph matching is an important and active topic in combinatorial statistics: on the one hand, it arises from various applied fields such as social network analysis, computer vision, computational biology and natural language processing; on the other hand, there is also a deep and rich theory that is of interest to researchers in statistics, probability, combinatorics, optimization, algorithms and complexity theory.

Recently, extensive efforts have been devoted to the study for matching two correlatedErdős–Rényigraphs, which is arguably the most classic model for graph matching. In this talk, we will review some recent progress on this front, with emphasis on the intriguing phenomenon on (the presumed) information-computation gap. In particular, we will discuss progress on efficient algorithms thanks to the collective efforts from the community. We will also point out some important future directions, including developing robust algorithms that rely on minimal assumptions on graph models and developing efficient algorithms for more realistic random graph models.