Scholars@Duke
Jiaming Xu

Jiaming Xu

Associate Professor of Business Administration
Fuqua School of Business

Selected Publications

Random Graph Matching at Otter’s Threshold via Counting Chandeliers

Journal Article Operations Research · April 18, 2025 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 unde ... Full text Cite

Global Convergence of Federated Learning for Mixed Regression

Journal Article IEEE Transactions on Information Theory · January 1, 2024 This paper studies the problem of model training under Federated Learning when clients exhibit cluster structures. We contextualize this problem in mixed regression, where each client has limited local data generated from one of k unknown regression models ... Full text Cite

Spectral Graph Matching and Regularized Quadratic Relaxations I Algorithm and Gaussian Analysis

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

Constant Regret Primal-Dual Policy for Multi-way Dynamic Matching

Journal Article Performance Evaluation Review · June 19, 2023 We study a discrete-time dynamic multi-way matching model. There are finitely many agent types that arrive stochastically and wait to be matched. State-of-the-art dynamic matching policies in the literature require the knowledge of all system parameters to ... Full text Cite

Constant Regret Primal-Dual Policy for Multi-way Dynamic Matching

Conference Sigmetrics 2023 Abstract Proceedings of the 2023 ACM Sigmetrics International Conference on Measurement and Modeling of Computer Systems · June 19, 2023 We study a discrete-Time dynamic multi-way matching model. There are finitely many agent types that arrive stochastically and wait to be matched. State-of-The-Art dynamic matching policies in the literature require the knowledge of all system parameters to ... 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

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

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

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 d ... Full text 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

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

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

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

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

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

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 1, 2018 We study the problem of detecting a structured, low-rank signal matrix corrupted with additive Gaussian noise. This includes clustering in a Gaussian mixture model, sparse PCA, and submatrix localization. Each of these problems is conjectured to exhibit a ... Full text Cite

Submatrix localization via message passing

Journal Article Journal of Machine Learning Research · April 15, 2018 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

Achieving Exact Cluster Recovery Threshold via Semidefinite Programming

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

Reconstruction in the labeled stochastic block model

Journal Article IEEE Transactions on Network Science and Engineering · October 2015 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

MISO broadcast channels with delayed finite-rate feedback: Predict or observe?

Journal Article IEEE Transactions on Wireless Communications · April 2012 Cite

The Supermarket Game

Preprint · February 9, 2012 Link to item Cite

On the Accuracy of the Wyner Model in Cellular Networks

Journal Article IEEE Transactions on Wireless Communications · September 2011 Full text Cite