Title:

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

Abstract:

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. 

Here is the paper link: https://arxiv.org/pdf/2209.12313.pdf. 

Bio: 

Sophie Yu is a fifth-year Ph.D. Candidate in the field of Decision Sciences in the Fuqua School of Business at Duke University, under Prof. Jiaming Xu. She visited the Simons Institute for the Theory of Computing as a visiting graduate student in Fall 2021. She received her MS in statistical and economic modeling under Prof. Jerry Reiter from Duke University in 2017, and her BS in Economics from Renmin University of China in 2015.

Her research interests focus on data analysis, algorithm design, and performance evaluation in large-scale networks and stochastic systems. Her works draw inspiration from real-world business, engineering, and natural sciences problems that can be modeled into large and complex networks. She has explored a range of topics, from the fundamental limits and efficient algorithms on network alignment to online platform policy design with bounded regret and data confidentiality protection.