信息来源：人大高瓴人工智能学院 发布日期：2026年6月12日

讲座信息

讲座时间：2026年6月16日10：00-12：00

报告人：Sophie H. Yu，宾夕法尼亚大学沃顿商学院助理教授

邀请人：祁琦，高瓴人工智能学院长聘副教授

报告题目:

Efficient network alignment at Otter's tree-counting threshold via counting chandeliers

报告摘要:

Given a pair of networks, the problem of network alignment or graph matching refers to finding the underlying vertex correspondence that maximally aligns the edges. This is a ubiquitous problem arising in a variety of applications across diverse fields, such as network privacy, computational biology, computer vision, and natural language processing. Network alignment is an instance of the notoriously difficult quadratic assignment problem (QAP), which is NP-hard to solve or approximate.

Despite the worst-case computational hardness of QAP, I will present a computationally efficient network alignment algorithm based on counting a special family of trees. When the two networks are Erdős–Rényi random graphs with correlated edges through the hidden vertex correspondence, we show that our algorithm correctly matches all but a vanishing fraction of vertices with high probability as soon as the edge correlation exceeds the square root of Otter's constant. Moreover, we further upgrade the almost exact recovery to exact recovery whenever it is information-theoretically possible. This is the first polynomial-time algorithm that achieves exact and almost exact matching with an explicit constant correlation for both dense and sparse networks.

报告人简介:

Sophie H. Yu is an assistant professor at The Wharton School of the University of Pennsylvania. She was a postdoctoral scholar in Management Science and Engineering at Stanford University. She holds a Ph.D. in Decision Sciences from Duke University's Fuqua School of Business in 2023, an M.S. in Statistical and Economic Modeling from Duke University in 2017, and a B.S. in Economics from Renmin University of China in 2015. Her research focuses on matching, inference, and algorithm design in large-scale networks and stochastic systems. Her research has been recognized by the Thomas M. Cover Dissertation Award from IEEE Information Theory Society, the Fuqua School of Business Best Dissertation Award, and a finalist for the George Nicholson Student Paper Competition.