Random Graph Matching at Otter’s Threshold via Counting Chandeliers

Network alignment or graph matching—figuring out how vertices across different networks correspond to each other—is a key challenge in many fields, from protecting online privacy to mapping biological data, improving computer vision, and even understanding languages. However, this problem falls into the class of notoriously difficult quadratic assignment problems, which are NP-hard to solve or approximate. Despite these challenges, researchers Mao, Wu, Xu, and Yu have made a major breakthrough. In their paper, “Random Graph Matching at Otter’s Threshold via Counting Chandeliers,” they introduce an innovative algorithm that can successfully match two random networks whenever the square of their edge correlation exceeds Otter’s constant (≈0.338). Their key innovation lies in counting chandeliers—specially designed tree-like structures—to identify corresponding vertices across the networks. The algorithm correctly matches nearly all vertices with high probability and even achieves perfect matching whenever the data allows. This is the first-ever polynomial-time algorithm capable of achieving perfect and near-perfect matching with an explicit constant correlation for both dense and sparse networks, bridging a long-standing gap between statistical limits and algorithmic performance.

Duke Scholars

Author Jiaming Xu Fuqua School of Business