The problem of graph matching consists in matching the vertices of two unlabeled, edge-correlated graphs so that their edges are maximally aligned. The above two graphs on the left are edge-correlated but their vertices are unmatched, so they appear to be quite different. On the right-hand side, the two graphs are optimally aligned so that there are only a few misaligned edges (dotted red lines). In the following papers, we developed a full-rank spectral method for graph matching, which is implemented here.
Spectral Graph Matching and Regularized Quadratic Relaxations Part I, Part
II, and conference version
Zhou Fan, Cheng Mao, Yihong Wu and Jiaming Xu
Foundations of Computational Mathematics, to appear (2022)
Random Graph Matching with Improved Noise Robustness
Cheng Mao, Mark Rudelson and Konstantin Tikhomirov
COLT 2021
Exact Matching of Random Graphs with Constant Correlation
Cheng Mao, Mark Rudelson and Konstantin Tikhomirov
Testing Network Correlation Efficiently via Counting Trees
Cheng Mao, Yihong Wu, Jiaming Xu and Sophie H. Yu
Random graph matching at Otter's threshold via counting chandeliers
Cheng Mao, Yihong Wu, Jiaming Xu and Sophie H. Yu
Mixture models are used to represent data from heterogeneous populations. This research in progress aims to develop algorithmic and analytic tools for both mixtures in the Euclidean space and mixtures of permutations.
Learning Mixtures of Permutations: Groups of Pairwise
Comparisons and Combinatorial Method of Moments
Cheng Mao and Yihong Wu
Annals of Statistics, to appear (2022)
Ranking from pairwise comparisons, as the name suggests, is the task of aggregating a set of comparisons between pairs of items to produce a ranking of the items. I have particularly worked on a class of permutation-based models with co-authors in the following works.
Minimax Rates and Efficient Algorithms for
Noisy Sorting
Cheng Mao, Jonathan Weed and Philippe Rigollet
ALT 2018
Towards Optimal Estimation of Bivariate Isotonic Matrices
with
Unknown Permutations
Cheng Mao, Ashwin Pananjady and Martin J. Wainwright
Annals of Statistics, Vol. 48, No. 6 (2020), 3183-3205
Worst-case vs Average-case Design for
Estimation
from Partial
Pairwise Comparisons
Ashwin Pananjady, Cheng Mao, Vidya Muthukumar, Martin J. Wainwright and Thomas A. Courtade
Annals of Statistics, Vol. 48, No. 2 (2020), 1072-1097
Some of my other research also concerns statistical estimation with latent combinatorial structure and/or shape constraints.
Optimal Rates of Statistical Seriation
Nicolas Flammarion, Cheng Mao and Philippe Rigollet
Bernoulli, Vol. 25, No. 1 (2019), 623-653
Estimation of Monge Matrices
Jan-Christian Hütter, Cheng Mao, Philippe Rigollet and Elina Robeva
Bernoulli, Vol. 26, No. 4 (2020), 3051-3080
Optimal Rates for Estimation of Two-dimensional Totally
Positive Distributions
Jan-Christian Hütter, Cheng Mao, Philippe Rigollet and Elina Robeva
Electronic Journal of Statistics, Vol. 14, No. 2 (2020), 2600-2652