Jiaming Xu

Jiaming Xu

Assistant Professor
Decision Sciences Area
The Fuqua School of Business

Department of Electrical and Computer Engineering (secondary appointment)

Duke University

E-mail: jx77@duke.edu
Office: W313
Phone: 919-660-8061

Address: 100 Fuqua Drive
Durham, NC 27708

CV




About me

I am an assistant professor in the Fuqua School of Business at Duke University.

I received BE (09) from Tsinghua University, MS (11) from UT-Austin, and PhD (14) from UIUC, all in Electrical and Computer Engineering.

I was fortunate to have Prof. Bruce Hajek as my PhD adviser. My thesis "Statistical inference in networks: fundamental limits and efficient algorithms" is available here.

arXiv preprints

Google scholar page


Research interests

My research focus is on the intersection of computation and statistics.
I seek to understand the deep interplay between statistical optimality and
computational complexity in high-dimensional statistical inference problems.
As part of this, I have been working on sharp performance analysis of semidefinite
programming relaxations and belief propagation for community detection.
  • Network science
  • High-dimensional statistical inference
  • Security and privacy
  • Optimization
  • Information theory
  • Queueing games
  • Mean field theory
  • Communications and networking

Preprints

Journal Publications

Conference Publications


My research interests are in the broad area of stochastic systems with emphasis on large scale distributed networks and high-dimensional data analysis.

Random graph matching

Given a pair of graphs, the problem of graph matching or network alignment refers to finding a bijection between the vertex sets so that the edge sets are maximally aligned. This is a ubiquitous problem arising in a variety of applications, including network de-anonymization, pattern recognition, and computational biology. Finding the best matching between two graphs can be cast as a quadratic assignment problem, which is NP-hard to solve or to approximate in the worst case. I have been working on the average-case analysis of graph matchings where the two graphs are randomly generated.




  • Graph matching via degree profiles
Despite the worst-case intractability of graph matching, we develop a nearly linear-time algorithm which perfectly recovers the true vertex correspondence with high probability, provided that the average degree is at least polylog(n) and the two graphs differ by at most 1/polylog(n) fraction of edges. The methodology is based on appropriately chosen distance statistics of the degree profiles (empirical distribution of the degrees of neighbors).

Paper:
  • J. Ding, Z. Ma, Y. Wu, and J. Xu
    Efficient Random Graph Matching via Degree Profiles
    arXiv:1811.07821, Nov. 2018. [SLIDES]

    • Spectral graph matching and regularized quadratic relaxations
    We develop a new spectral method, which computes eigendecomposition of the two graph adjacency matrices and returns a matching based on the pairwise alignments between all eigenvectors of the first graph with all eigenvectors of the second. This spectral method can be equivalently viewed as solving a regularized quadratic programming relaxation of the quadratic assignment problem. We show that this method can return the exact matching with high probability, provided that the average degree is at least polylog(n) and the two graphs differ by at most a 1/polylog(n) fraction of edges. Our analysis exploits local laws for the resolvents of sparse Wigner matrices.

    Papers:
  • Z. Fan, C. Mao, Y. Wu, J. Xu
    Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model
    arXiv:1907.08880, July 2019. [SLIDES]
  • Z. Fan, C. Mao, Y. Wu, J. Xu
    Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality
    arXiv:1907.08883, July 2019.

    • Seeded graph matching via large neighborhood statistics
    We consider a seeded graph matching problem, where an initial seed set of correctly matched vertex pairs is revealed as side information. We show that it is possible to achieve the information theoretic limit of graph sparsity in polynomial-time with n^{eps} seeds. Our algorithm matches vertices if their large neighborhoods have a significant overlap in the number of seeds.

    Paper:
  • E. Mossel and J. Xu
    Seeded Graph Matching via Large Neighborhood Statistics
    arXiv:1807.10262, July 2018. [SLIDES]

  • Community detection in networks

    In many modern systems, e.g. recommender systems, similar objects form hidden clusters and we are interested in recovering the clusters based on observation of pairwise interactions among objects. The data of pairwise interactions can be viewed as a graph consisting of nodes representing objects and edge connections encoding pairwise interactions, and the cluster recovery problem is called community detection, a.k.a. graph clustering.

    I have been working on developing optimal, fast, and robust community detection algorithms, and characterizing the fundamental limits for community detection.


    • Community detection via message passing


    Finding small communities in networks is a notoriously hard problem. We show that a single community can be found in nearly linear time via the belief propagation algorithm in log*(n) iterations if and only if the suitably defined signal-to-noise ratio λ>1/e, while a linear message passing algorithm finds the single community in loglog(n) iterations if and only if λ>1.

    Papers:
  • B. Hajek, Y. Wu, and J. Xu
    Submatrix localization via message passing
    The Journal of Machine Learning Research, Apr. 2018. [SLIDES]
  • B. Hajek, Y. Wu, and J. Xu
    Recovering a hidden community beyond the Kesten-Stigum Threshold in
    Journal of Applied Probability, June 2018.
    [SLIDES]

    • Community detection via SDP relaxations


      The solid curves show the recovery threshold for a single community of size ρn for three values of ρ.

      The two dashed curves correspond to the recovery threshold for two equal-sized clusters
    We show that a semidefinite programming (SDP) relaxation of the maximum likelihood estimator can achieve the sharp threshold for exactly recovering the community structure if and only if the community size is above a certain threshold depending on the network size.

    Papers:
  • B. Hajek, Y. Wu, and J. Xu
    Semidefinite programs for exact recovery of a hidden community
    Conference on Learning Theory (COLT), June 2016. [SLIDES]
  • B. Hajek, Y. Wu, and J. Xu
    Achieving exact cluster recovery threshold via semidefinite programming: Extensions
    IEEE Transactions on Information Theory. Oct. 2016.
    [SLIDES]
  • B. Hajek, Y. Wu, and J. Xu
    Achieving exact cluster recovery threshold via semidefinite programming
    IEEE Transactions on Information Theory, May 2016. [SLIDES]

    • Community detection with degree corrections


      The facebook friendship network formed by students at Caltech. Nodes are colored according to the clustering result of convexified modularity maximization. The 8 clusters found roughly correspond to the 8 dorms at Caltech.

    In real-world networks, the degree distributions are often highly inhomogeneous across nodes, sometimes exhibiting a heavy tail behavior with some nodes having very high degrees (so-called hubs), and some nodes having very small degrees. We introduce a new approach based on a convexification of modularity maximization followed by weighted k-median clustering, and show that our approach improves upon the state-of-the-art both theoretically and empirically.

    Paper:
  • Y. Chen, X. Li, and J. Xu
    Convexified modularity maximization for degree-corrected stochastic block models
    The Annals of Statistics,June 2018. [SLIDES] [CODE]

    • Fundamental limits for community detection


      (1) The impossible regime, where all algorithms fail; (2) the hard regime, where the computationally intractable Maximum Likelihood Estimator (MLE) succeeds; (3) the easy regime, where a convex relaxation of MLE succeeds; (4) the simple regime, where a simple counting/thresholding procedure succeeds.
    We study the fundamental limits of community detection under the stochastic block model. In its simplest form, it consists of n nodes with r K of them partitioned into r clusters of equal size K and the remaining n-r K nodes not in any cluster; each pair of two nodes is connected independently by an edge with probability p if they are in the same cluster and q otherwise. Given a graph generated as above, the goal is to exactly recover the clusters with high probability as n goes to the infinity. In the case with more than one cluster, we show that the space of the model parameters can be partitioned into four disjoint regions in decreasing order of statistical and computational complexities.

    Papers:
  • Y. Chen and J. Xu
    Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices
    The Journal of Machine Learning Research, 2016.. [SLIDES]
  • B. Hajek, Y. Wu, and J. Xu
    Computational lower bounds for community detection on
    random graphs

    Conference on Learning Theory (COLT), July 2015. [SLIDES]
  • B. Hajek, Y. Wu, and J. Xu
    Information limits for recovering a hidden community
    IEEE Trans. Inf. Theory, vol. 63, pp. 4729-4745, Aug. 2017. [SLIDES]
  • Learning user preferences

    Recommender systems sort through massive amounts of data to identify potential user preferences. They have been applied in a variety of applications, including personalized advertisement, online learning, and targeted marketing.

    I have been working on developing and analyzing optimal and fast algorithms for predicting users' inherent preferences from noisy and partial rating or ranking data.


    • Rating predictions: algorithms and limits


    When explicit user ratings are available, there are three popular approaches: (1) nearest neighbor (NN); (2) spectral method (3) convex method. We performed a theoretical analysis of these three methods assuming both users and items exhibit cluster structure. We find that the simple NN method outperforms the other two more sophisticated ones for small cluster sizes if there are abundant observations.

    Papers:
  • J. Xu, R. Wu, K. Zhu, B. Hajek, R. Srikant, and L. Ying
    Jointly clustering rows and columns of binary matrices:
    algorithms and trade-offs

    ACM SIGMETRICS, June 2014. [SLIDES]
  • M. Lelarge, L. Massoulié, and J. Xu
    Edge label inference in generalized stochastic block model: from spectral theory to impossibility results
    Conference on Learning Theory (COLT), June 2014.
    • Inferring preferences from partial rankings


    When only partial rankings are available, little is known about how to learn the individual preferences efficiently, and what is the sample complexity to reach a prescribed estimation accuracy. Our main results revealed important insight on this issue: (1) we propose a clustering and ranking algorithm, which is shown to be order-optimal in sample complexity; (2) we show the estimation error depends on the spectral gap of a comparison graph and the random assignment of items to users is order-optimal among all schemes.

    Papers:
  • B. Hajek, S. Oh, and J. Xu
    Minimax-optimal inference from partial rankings
    Neural Information Processing Systems (NIPS), Dec. 2014.
  • R. Wu, J. Xu, R. Srikant, L. Massoulié, M. Lelarge, and B. Hajek
    Clustering and inference from pairwise comparisons
    ACM SIGMETRICS, June 2015 (short paper).
  • S. Oh, K. K. Thekumparampil, and J. Xu
    Collaboratively learning preferences from ordinal data
    Neural Information Processing Systems (NIPS), Dec. 2015.
  • The supermarket game

    Imagine being a customer in a supermarket where there is a large number of check-out counters, and the queue at each counter is only seen locally. With the goal of minimizing the sum of the waiting cost and the searching cost, how many counters would you prefer to check?

    The above example reflects the spirit of my work on investigating the impact of customers' strategic behavior in queueing systems. The problem described in the example is known as the distributed load balancing problem, and it appears in a diverse set of applications such as network routing, dynamic wireless spectrum access, and cloud computing services.




    We propose a supermarket game model and study it in the large system regime using mean field theory. By assuming Poisson arrival with rate λ and exponential service with unit rate, we show that there always exists a Nash equilibrium for λ < 1 and the Nash equilibrium is unique for λ <=1/sqrt(2).

    Paper:
  • J. Xu and B. Hajek
    The Supermarket game
    Stochastic Systems, Vol. 3, No. 2, 405-441, 2013. [SLIDES]

  • Instructor

    • BA 991: Statistical Inference on Graphs, Duke, Spring 2020.
    • Decision 521Q: Decision Analytics and Modeling, Duke, Spring 2019.
    • MGMT 472: Advanced Spreadsheet Modeling 
and Simulation, Purdue, Fall 2017.
    • MGMT 306: Management Science, Purdue, Spring and Fall 2017.
    • MGMT 690: PhD seminar in Analytics: Topics in High-dimensional Data Analysis, Purdue, Fall 2016.
    • ECE313: Probability with Engineering Applications, UIUC, Summer 2014.

    Invited Seminars and Talks