Jiaming Xu

Journal Article Foundations of Computational Mathematics · October 1, 2023 Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally intractable quadratic assignment problem. In this paper, we propose a new spec ... Full text Cite

Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality

Journal Article Foundations of Computational Mathematics · October 1, 2023 We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edge-correlated weighted graphs. Extending the exact recovery guarantees establ ... Full text Cite

Learner-Private Convex Optimization

Conference IEEE Transactions on Information Theory · January 1, 2023 Convex optimization with feedback is a framework where a learner relies on iterative queries and feedback to arrive at the minimizer of a convex function. It has gained considerable popularity thanks to its scalability in large-scale optimization and machi ... Full text Cite

Random graph matching at Otter's threshold via counting chandeliers

Preprint · September 25, 2022 Link to item Cite

Settling the Sharp Reconstruction Thresholds of Random Graph Matching

Journal Article IEEE Transactions on Information Theory · August 1, 2022 This paper studies the problem of recovering the hidden vertex correspondence between two edge-correlated ran3 dom graphs. We focus on the Gaussian model where the two graphs are complete graphs with correlated Gaussian weights and the Erdos-Rényi model wh ... Full text Cite

SeedGNN: Graph Neural Networks for Supervised Seeded Graph Matching

Preprint · May 26, 2022 Link to item Cite

Integrated Online Learning and Adaptive Control in Queueing Systems with Uncertain Payoffs

Journal Article Operations Research · March 1, 2022 We study task assignment in online service platforms, where unlabeled clients arrive according to a stochastic process and each client brings a random number of tasks. As tasks are assigned to servers, they produce client/server-dependent random payoffs. T ... Full text Cite

Random Graph Matching in Geometric Models: the Case of Complete Graphs

Preprint · February 21, 2022 Link to item Cite

The planted matching problem: Phase transitions and exact results

Journal Article Annals of Applied Probability · December 1, 2021 We study the problem of recovering a planted matching in randomly weighted complete bipartite graphs Kn,n. For some unknown perfect matching M∗, the weight of an edge is drawn from one distribution P if e ∈ M∗ and another distribution Q if e ∈/ M∗. Our goa ... Full text Cite

Testing network correlation efficiently via counting trees

Preprint · October 22, 2021 Link to item Cite

Consistent Recovery Threshold of Hidden Nearest Neighbor Graphs

Journal Article IEEE Transactions on Information Theory · August 1, 2021 Motivated by applications such as discovering strong ties in social networks and assembling genome subsequences in biology, we study the problem of recovering a hidden 2k-nearest neighbor (NN) graph in an n-vertex complete graph, whose edge weights are ind ... Full text Cite

A Non-parametric View of FedAvg and FedProx: Beyond Stationary Points

Preprint · June 29, 2021 Link to item Cite

The Power of D-hops in Matching Power-Law Graphs

Journal Article Performance Evaluation Review · June 1, 2021 This paper studies seeded graph matching for power-law graphs. Assume that two edge-correlated graphs are independently edge-sampled from a common parent graph with a power-law degree distribution. A set of correctly matched vertex-pairs is chosen at rando ... Full text Cite

The planted matching problem: Sharp threshold and infinite-order phase transition

Preprint · March 16, 2021 Link to item Cite

Learner-Private Convex Optimization

Preprint · February 23, 2021 Link to item Cite

The Power of $D$-hops in Matching Power-Law Graphs

Preprint · February 23, 2021 Link to item Cite

Efficient random graph matching via degree profiles

Journal Article Probability Theory and Related Fields · February 1, 2021 Random graph matching refers to recovering the underlying vertex correspondence between two random graphs with correlated edges; a prominent example is when the two random graphs are given by Erdős-Rényi graphs G(n,dn). This can be viewed as an average-cas ... Full text Cite

Convex Relaxation Methods for Community Detection

Journal Article Statistical Science · February 1, 2021 This paper surveys recent theoretical advances in convex optimization approaches for community detection. We introduce some important theoretical techniques and results for establishing the consistency of convex community detection under various statistica ... Full text Cite

Settling the Sharp Reconstruction Thresholds of Random Graph Matching

Preprint · January 29, 2021 Link to item Cite

Graph Matching with Partially-Correct Seeds

Journal Article Journal of Machine Learning Research · January 1, 2021 Graph matching aims to find the latent vertex correspondence between two edge-correlated graphs and has found numerous applications across different fields.In this paper, we study a seeded graph matching problem, which assumes that a set of seeds, i.e., pr ... Cite

Seeded graph matching via large neighborhood statistics

Journal Article Random Structures and Algorithms · October 1, 2020 We study a noisy graph isomorphism problem, where the goal is to perfectly recover the vertex correspondence between two edge-correlated graphs, with an initial seed set of correctly matched vertex pairs revealed as side information. We show that it is pos ... Full text Cite

Improved queue-size scaling for input-queued switches via graph factorization

Journal Article Advances in Applied Probability · September 1, 2020 This paper studies the scaling of the expected total queue size in an input-queued switch, as a function of both the load and the system scale n. We provide a new class of scheduling policies under which the expected total queue size scales as, over all n ... Full text Cite

Testing correlation of unlabeled random graphs

Preprint · August 23, 2020 Link to item Cite

Graph Matching with Partially-Correct Seeds

Preprint · April 8, 2020 Link to item Cite

Crosscutting areas hidden Hamiltonian cycle recovery via linear programming

Journal Article Operations Research · February 1, 2020 We introduce the problem of hidden Hamiltonian cycle recovery, where there is an unknown Hamiltonian cycle in an n-vertex complete graph that needs to be inferred from noisy edge measurements. The measurements are independent and distributed according to P ... Full text Cite

The Planted Matching Problem: Phase Transitions and Exact Results

Preprint · December 18, 2019 Link to item Cite

Consistent recovery threshold of hidden nearest neighbor graphs

Preprint · November 18, 2019 Link to item Cite

Optimal query complexity for private sequential learning against eavesdropping

Preprint · September 21, 2019 Link to item Cite

Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality

Preprint · July 20, 2019 Link to item Cite

Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model

Preprint · July 20, 2019 Link to item Cite

The All-or-Nothing Phenomenon in Sparse Linear Regression

Preprint · March 12, 2019 Link to item Cite

Improved queue-size scaling for input-queued switches via graph factorization

Preprint · March 1, 2019 Link to item Cite

Distributed Statistical Machine Learning in Adversarial Settings

Journal Article ACM SIGMETRICS Performance Evaluation Review · January 17, 2019 Full text Cite

Securing Distributed Gradient Descent in High Dimensional Statistical Learning

Journal Article PROCEEDINGS OF THE ACM ON MEASUREMENT AND ANALYSIS OF COMPUTING SYSTEMS · 2019 Full text Cite

Efficient random graph matching via degree profiles

Preprint · November 19, 2018 Link to item Cite

Convex Relaxation Methods for Community Detection

Preprint · September 30, 2018 Link to item Cite

Convexified modularity maximization for degree-corrected stochastic block models

Journal Article The Annals of Statistics · August 1, 2018 Full text Cite

Seeded Graph Matching via Large Neighborhood Statistics

Preprint · July 26, 2018 Link to item Cite

Recovering a hidden community beyond the Kesten-Stigum threshold in O(|E|log*|V) time

Journal Article Journal of Applied Probability · July 15, 2018 Cite

Information-Theoretic Bounds and Phase Transitions in Clustering, Sparse PCA, and Submatrix Localization

Journal Article IEEE Transactions on Information Theory · July 2018 Full text Cite

Statistical Problems with Planted Structures: Information-Theoretical and Computational Limits

Preprint · May 31, 2018 Link to item Cite

Securing Distributed Gradient Descent in High Dimensional Statistical Learning

Preprint · April 26, 2018 Link to item Cite

Submatrix localization via message passing

Journal Article Journal of Machine Learning Research · April 15, 2018 Cite

Hidden Hamiltonian Cycle Recovery via Linear Programming

Preprint · April 15, 2018 Link to item Cite

Rates of Convergence of Spectral Methods for Graphon Estimation

Preprint · September 10, 2017 Link to item Cite

Information Limits for Recovering a Hidden Community

Journal Article IEEE Transactions on Information Theory · August 2017 Full text Cite

Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions

Journal Article IEEE Transactions on Information Theory · October 2016 Full text Cite

Information-theoretic bounds and phase transitions in clustering, sparse PCA, and submatrix localization

Preprint · July 18, 2016 Link to item Cite

Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

Journal Article IEEE Transactions on Information Theory · May 2016 Full text Cite

Mutual Information in Rank-One Matrix Estimation

Preprint · March 28, 2016 Link to item Cite

Semidefinite Programs for Exact Recovery of a Hidden Community

Preprint · February 20, 2016 Link to item Cite

Convexified Modularity Maximization for Degree-corrected Stochastic Block Models

Preprint · December 28, 2015 Link to item Cite

Submatrix localization via message passing

Preprint · October 30, 2015 Link to item Cite

Recovering a Hidden Community Beyond the Kesten-Stigum Threshold in $O(|E| \log^*|V|)$ Time

Preprint · October 9, 2015 Link to item Cite

Reconstruction in the labeled stochastic block model

Journal Article IEEE Transactions on Network Science and Engineering · October 2015 Cite

Information Limits for Recovering a Hidden Community

Preprint · September 25, 2015 Link to item Cite

Density Evolution in the Degree-correlated Stochastic Block Model

Preprint · September 10, 2015 Link to item Cite

Local Algorithms for Block Models with Side Information

Preprint · August 10, 2015 Link to item Cite

Achieving Exact Cluster Recovery Threshold via Semidefinite Programming: Extensions

Preprint · February 26, 2015 Link to item Cite

Clustering and Inference From Pairwise Comparisons

Preprint · February 16, 2015 Link to item Cite

Reconstruction in the Labeled Stochastic Block Model

Preprint · February 11, 2015 Link to item Cite

Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

Preprint · November 24, 2014 Link to item Cite

Edge Label Inference in Generalized Stochastic Block Models: from Spectral Theory to Impossibility Results

Preprint · June 26, 2014 Link to item Cite

Computational Lower Bounds for Community Detection on Random Graphs

Preprint · June 25, 2014 Link to item Cite

Minimax-optimal Inference from Partial Rankings

Preprint · June 21, 2014 Link to item Cite

Statistical-Computational Tradeoffs in Planted Problems and Submatrix Localization with a Growing Number of Clusters and Submatrices

Preprint · February 6, 2014 Link to item Cite

Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices

Journal Article Journal of Machine Learning Research · February 2014 Cite

The Supermarket Game

Journal Article Stochastic Systems · December 2013 A supermarket game is considered with N FCFS queues with unit exponential service rate and global Poisson arrival rate Nλ. Upon arrival each customer chooses a number of queues to be sampled uniformly at random and joins the least loaded sampled q ... Full text Cite