光华讲坛——社会名流与企业家论坛第 期

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

主讲人：北京大学丁剑教授

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

时间：2023年5月26日（周五）下午14:00-15:00

举办地点：柳林校区弘远楼408会议室

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

主讲人简介：

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.

丁剑，北京大学讲座教授。他的主要研究领域是概率论，重点是与统计物理和理论计算机科学的相互作用。他还对“面向应用”问题产生的概率问题有着广泛的兴趣。在加入北京大学之前，他曾在斯坦福大学做博士后，并在芝加哥大学和宾夕法尼亚大学任教，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 correlated Erdős–Rényi graphs, 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.

随机图匹配的基本目标是通过观察这两个未标记的图来恢复这两个具有相关性的图之间的顶点对应关系。随机图匹配是组合统计中一个重要而活跃的话题：一方面，它源于社交网络分析、计算机视觉、计算生物学和自然语言处理等各种应用领域;另一方面，它还有深刻而丰富的理论，是统计学、概率学、组合数学、优化、算法和复杂性理论研究人员所感兴趣的。

近几年，人们投入了大量的精力来研究匹配两个相关的Erdős–Rényi图，这可以说是最经典的图匹配模型。在本次演讲中，主讲人将回顾这方面的一些最新进展，重点是关于（假定的）信息计算差的有趣现象。特别是，主讲人将讨论本领域中共同研究的高效算法的进展。主讲人还将指出一些重要的未来方向，包括开发图模型中依赖最少假设的稳健算法，以及为更实际的随机图模型开发有效的算法。