Detection and recovery of hidden structures in high-dimensional data

This line of research focuses on the detection and recovery of hidden structures in high-dimensional data, especially those in random graphs or statistical networks. Particularly, several works in this category use the framework of low-degree polynomial algorithms.

• Detection of Dense Subhypergraphs by Low-Degree Polynomials
• Detection-Recovery Gap for Planted Dense Cycles
• Information-Theoretic Thresholds for Planted Dense Cycles
• Impossibility of Latent Inner Product Recovery via Rate Distortion
• Optimal Spectral Recovery of a Planted Vector in a Subspace

Graph matching (a.k.a. network alignment)

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
• Random Graph Matching with Improved Noise Robustness
• Exact Matching of Random Graphs with Constant Correlation
• Testing Network Correlation Efficiently via Counting Trees
• Random Graph Matching at Otter's Threshold via Counting Chandeliers

Models for pairwise comparisons

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 mixture models, used to represent data from heterogeneous populations, and permutation-based models, extending traditional parametric ranking models.

• Learning Mixtures of Permutations: Groups of Pairwise Comparisons and Combinatorial Method of Moments
• Sharp Analysis of EM for Learning Mixtures of Pairwise Differences
• Minimax Rates and Efficient Algorithms for Noisy Sorting
• Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
• Worst-case vs Average-case Design for Estimation from Partial Pairwise Comparisons

Estimation with latent permutations and shape constraints

Some of my earlier research also concerns statistical estimation with latent permutations. One particular class of such problems is known as seriation. This set of works also falls within the scope of shape-constrained estimation in nonparametric statistics.

• Optimal Rates of Statistical Seriation
• Estimation of Monge Matrices
• Optimal Rates for Estimation of Two-dimensional Totally Positive Distributions