This line of research focuses on the detection and recovery of hidden structures in high-dimensional data, especially those presented in the form of random graphs or statistical networks.
Detection of Dense Subhypergraphs by Low-Degree Polynomials
Abhishek Dhawan, Cheng Mao, and Alexander S. Wein
Detection-Recovery Gap for Planted Dense Cycles
Cheng Mao, Alexander S. Wein, and Shenduo Zhang
COLT 2023
Optimal Spectral Recovery of a Planted Vector in a Subspace
Cheng Mao and Alexander S. Wein
The problem of graph matching or network alignment consists in matching the vertices of two unlabeled, edge-correlated graphs so that their edges are maximally aligned. We developed methods for graph matching and detection of correlation between graphs, one of 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 (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
Probability Theory and Related Fields (2023)
Testing Network Correlation Efficiently via Counting Trees
Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu
Annals of Statistics, to appear (2023)
Random Graph Matching at Otter's Threshold via Counting
Chandeliers
Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H. Yu
STOC 2023
Mixture models are used to represent data from heterogeneous populations. This research 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, Vol. 50, No. 4 (2022), 2231-2255
Sharp Analysis of EM for Learning Mixtures of Pairwise
Differences
Abhishek Dhawan, Cheng Mao, and Ashwin Pananjady
COLT 2023
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. We particularly worked on a class of permutation-based models.
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