Schedule for: 22w5185 - Learning in Networks: Performance Limits and Algorithms

There is a growing collection of average-case reductions starting from Planted Clique (or Planted Dense Subgraph) and mapping to a variety of statistics problems, sharply characterizing their computational phase transitions. These reductions transform an instance of Planted Clique, a highly structured problem with its simple clique signal and independent noise, to problems with richer structure. In this talk we aim to make progress in the other direction: to what extent can these problems, which often have complicated dependent noise, be transformed back to Planted Clique? Such a bidirectional reduction between Planted Clique and another problem shows a strong computational equivalence between the two problems. As a concrete instance of a more general result, we consider the planted clique (or dense subgraph) problem in an ambient graph that has dependent edges induced by randomly adding triangles to the Erdos-Renyi graph G(n,p), and show how to successfully eliminate dependence by carefully removing the triangles while approximately preserving the clique (or dense subgraph). In order to analyze our reduction we develop new methods for bounding the total variation distance between dependent distributions. Joint work with Chenghao Guo and Yury Polyanskiy.

Many networks exhibit community structure, meaning that there are two or more groups of nodes which are densely connected. Identifying these communities gives valuable insights about the latent features of the nodes. Community detection has been used in a wide array of applications including online advertising, recommender systems (e.g., Netflix), webpage sorting, fraud detection, and neurobiology. I will present my work on algorithms for community detection in two contexts, each with an underlying probabilistic generative model. (1) Censored networks: How can we identify communities when some connectivity information is missing? Here we consider recovery from the Censored Stochastic Block Model. (Joint work with Souvik Dhara, Elchanan Mossel, and Colin Sandon) (2) Higher-order networks: Beyond pairwise relationships. Here we consider recovery from the Hypergraph SBM, where we are given access to the "similarity matrix" of the hypergraph. (Joint work with Nirmit Joshi) We show that simple spectral algorithms achieve the information-theoretic thresholds of both exact recovery problems.

The Perceptron model was proposed as early as the 1950's as a toy model of a one-layer neural network. The basic model consists of a set of solutions (either the Hamming cube or the sphere of dimension n) and a set of constraints given by n-dimensional Gaussian vectors. The constraints are that the inner product of a solution vector with each constraint vector scaled by sqrt{n} must lie in some interval on the real line. Probabilistic questions about the model include the satisfiability threshold (or the "storage capacity") and questions about the typical structure of the solution space. Algorithmic questions include the tractability of finding a solution (the learning problem in the neural network interpretation). I will survey the model, the main problems, and recent progress.

In today's computing systems, there is a strong contention between achieving high server utilization and accommodating the time-varying resource requirements of jobs. Motivated by this problem, we study a stochastic bin packing formulation with time-varying item sizes, where bins and items correspond to servers and jobs, respectively. Our goal is to answer the following fundamental question: How can we minimize the number of active servers (servers running at least one job) given a budget for the cost associated with resource overcommitment on servers? We propose a novel framework for designing job dispatching policies, which reduces the problem to a policy design problem in a single-server system through policy conversions. Through this framework, we develop a policy that is asymptotically optimal as the job arrival rate increases. This is a joint work with Yige Hong at Carnegie Mellon University and Qiaomin Xie at the University of Wisconsin–Madison.

The Paley graph is a number-theoretic construction of a graph on the vertex set of a finite field of prime order p that in many ways behaves "pseudorandomly." One manifestation of pseudorandomness is that the clique number of the Paley graph is widely believed to be polylogarithmic in p. In contrast, the best known upper bounds are only of order square root of p; it is a long-standing open problem in number theory to improve on this scaling. I will present several pieces of recent and ongoing work studying approaches to this question based on convex optimization and spectral graph theory, which involve understanding the extent to which the Paley graph is "spectrally pseudorandom" in various senses. First, I will show that the degree 4 sum-of-squares relaxation of the clique number of the Paley graph has value at least the cube root of p, derandomizing an analogous result for Erdos-Renyi random graphs due to Deshpande and Montanari (2015). On the other hand, I will offer some evidence that this relaxation may in fact yield bounds of polynomial scaling between the square and cube roots of p, thanks to the spectrum of the Paley graph being sufficiently different from that of an Erdos-Renyi graph. Second, I will show that certain deterministic induced subgraphs of the Paley graph have the same limiting spectrum as induced subgraphs on random sets of vertices of the same size. I will outline how stronger results of this form would also lead to clique number bounds improving on the state of the art. Based partly on joint work with Xifan Yu.

I will discuss statistical inference problems on edge-correlated stochastic block models. We determine the information-theoretic threshold for exact recovery of the latent vertex correspondence between two correlated block models, a task known as graph matching. As an application, we show how one can exactly recover the latent communities using multiple correlated graphs in parameter regimes where it is information-theoretically impossible to do so using just a single graph. Furthermore, we obtain the precise threshold for exact community recovery using multiple correlated graphs, which captures the interplay between the community recovery and graph matching tasks. This is based on joint work with Julia Gaudio and Anirudh Sridhar

In the study of Ising models on large locally tree-like graphs, in both rigorous and non-rigorous methods one is often led to understanding the so-called belief propagation distributional recursions and its fixed point (also known as Bethe fixed point, cavity equation, 1RSB etc). In this work we prove there is at most one non-trivial fixed point for Ising models for both zero and certain random external fields. As a concrete example, consider a sample A of Ising model on a rooted tree (regular, Galton-Watson, etc). Let B be a noisy version of A obtained by independently perturbing each spin as follows: B_v equals to A_v with some small probability δ and otherwise taken to be a uniform +-1 (alternatively, 0). We show that the distribution of the root spin A_ρ conditioned on values B_v of all vertices v at a large distance from the root is independent of δ and coincides with δ=0. Previously this was only known for sufficiently ``low-temperature'' models. Our proof consists of constructing a metric under which the BP operator is a contraction (albeit non-multiplicative). I hope to convince you our proof is technically rather simple. This simultaneously closes the following 5 conjectures in the literature: uselessness of global information for a labeled 2-community stochastic block model, or 2-SBM (Kanade-Mossel-Schramm'2014); optimality of local algorithms for 2-SBM under noisy side information (Mossel-Xu'2015); independence of robust reconstruction accuracy to leaf noise in broadcasting on trees (Mossel-Neeman-Sly'2016); boundary irrelevance in broadcasting on trees (Abbe-Cornacchia-Gu-P.'2021); characterization of entropy of community labels given the graph in 2-SBM (ibid). Joint work with Qian Yu (Princeton).

Recovery of the causal structure of dynamic networks from noisy measurements has long been a problem of intense interest across many areas of science and engineering. Many algorithms have been proposed, but there is no work that compares the performance of the algorithms to converse bounds in a non-asymptotic setting. As a step to address this problem, this talk discusses lower bounds on the error probability for causal network support recovery in a linear Gaussian setting. The bounds are based on the use of the Bhattacharyya coefficient for binary hypothesis testing problems with mixture probability distributions. Comparison of the bounds and the performance achieved by two representative recovery algorithms are given for sparse random networks based on the Erdős–Rényi model. A related problem of estimating the error probabilities for a binary hypothesis testing problem from likelihood ratio samples is also discussed.

Participants will be invited to present open problems.

We consider the graph alignment problem, where the goal is to identify the vertex/user correspondence between two correlated graphs. Existing work mostly recovers the correspondence by exploiting the user-user connections. However, in many real-world applications, additional information about the users, such as user profiles, might be publicly available. In this talk, we introduce the attributed graph alignment problem, where additional user information, referred to as attributes, is incorporated to assist graph alignment. We establish both the information-theoretic limits and the feasible region by polynomial-time algorithms for the attributed graph alignment. Our results span the full spectrum between models that only consider user-user connections and models where only attribute information is available.

Tensor decomposition is an algorithmic primitive with applications in many machine learning tasks, including community detection and its mixed-membership or multi-layer variants. We consider a simple model for tensor decomposition: suppose we are given a random rank-r order-3 tensor---that is, an n-by-n-by-n array of numbers that is the sum of r random rank-1 terms---and our goal is to recover the individual rank-1 terms. In principle this decomposition task is possible when r < cn^2 for a constant c, but all known polynomial-time algorithms require r << n^{3/2}. Is this a fundamental barrier for efficient algorithms? In recent years, the average-case complexity of various high-dimensional statistical tasks has been resolved in restricted-but-powerful models of computation such as statistical queries, sum-of-squares, or low-degree polynomials. However, tensor decomposition has remained elusive, largely because its hardness is not explained by a "planted versus null" testing problem. We show the first formal hardness for average-case tensor decomposition: when r >> n^{3/2}, the decomposition task is hard for algorithms that can be expressed as low-degree polynomials in the tensor entries.

We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two ER graphs $\mathcal{G}(n,q)$ whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that $nq\to\infty$ and the edge correlation coefficient $\rho$ satisfies $\rho^2>\alpha \approx 0.338$, where $\alpha$ is Otter's tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is information-theoretically necessary. This is the first polynomial-time graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs. In comparison, previous methods either require $\rho=1-o(1)$ or are restricted to sparse graphs. The crux of the algorithm is a carefully curated family of rooted trees called chandeliers, which allows effective extraction of the graph correlation from the counts of the same tree while suppressing the undesirable correlation between those of different trees. Based on joint work with Cheng Mao (Gatech), Yihong Wu (Yale), and Sophie H. Yu (Duke). Preprint available at https://arxiv.org/pdf/2209.12313.pdf

We consider the problem of ranking n players from partial pairwise comparison data under the Bradley-Terry-Luce model. For the first time in the literature, the minimax rate of this ranking problem is derived with respect to the Kendall's tau distance that measures the difference between two rank vectors by counting the number of inversions. The minimax rate of ranking exhibits a transition between an exponential rate and a polynomial rate depending on the magnitude of the signal-to-noise ratio of the problem. To the best of our knowledge, this phenomenon is unique to full ranking and has not been seen in any other statistical estimation problem. To achieve the minimax rate, we propose a divide-and-conquer ranking algorithm that first divides the n players into groups of similar skills and then computes local MLE within each group. The optimality of the proposed algorithm is established by a careful approximate independence argument between the two steps.

Approximate Message Passing (AMP) algorithms provide a valuable tool for studying mean-field approximations and dynamics in a variety of applications. Although usually derived for matrices having independent Gaussian entries or satisfying rotational invariance in law, their state evolution characterizations are expected to hold over larger universality classes of random matrix ensembles. We develop several new results on AMP universality. For AMP algorithms tailored to independent Gaussian entries, we show that their state evolutions hold over broadly defined generalized Wigner and white noise ensembles, including matrices with heavy-tailed entries and heterogeneous entrywise variances that may arise in data applications. For AMP algorithms tailored to rotational invariance in law, we show that their state evolutions hold over matrix ensembles whose eigenvector bases satisfy only sign and permutation invariances, including sensing matrices composed of subsampled Hadamard or Fourier transforms and diagonal operators. We establish these results via a simplified moment-method proof, reducing AMP universality to the study of products of random matrices and diagonal tensors along a tensor network. As a by-product of our analyses, we show that the aforementioned matrix ensembles satisfy a notion of asymptotic freeness with respect to such tensor networks, which parallels usual definitions of freeness for traces of matrix products. The talk will be based on arxiv.org/abs/2206.13037, joint work with Tianhao Wang and Xinyi Zhong.

Jerrum in 1992 (co-)introduced the planted clique model by proving the (worst-case initialization) failure of the Metropolis process to recover any o(sqrt(n))-sized clique planted in the Erdos-Renyi graph G(n,1/2). This result is classically cited in the literature of the problem, as the “first evidence” the o(sqrt(n))-sized planted clique recovery task is “algorithmically hard”. In this work, we show that the Metropolis process actually fails to work (under worst-case initialization) for any o(n)-sized planted clique, that is the failure applies well beyond the sqrt(n) “conjectured algorithmic threshold”. Moreover we also prove, for a large number of temperature values, that the Metropolis process fails also under “natural initialization”, resolving an open question posed by Jerrum in 1992. This is joint work with Zongchen Chen and Elchanan Mossel.

Planted dense cycles are a type of latent structure that appears in many applications, such as small-world networks in social sciences and sequence assembly in computational biology. We consider a model where a dense cycle with expected bandwidth $n \tau$ and edge density $p$ is planted in an Erd\H{o}s--R\'enyi graph $G(n,q)$. We characterize the computational thresholds for the associated detection and recovery problems for the class of low-degree polynomial algorithms. In particular, a gap exists between the two thresholds in a certain regime of parameters. For example, if $n^{-3/4} \ll \tau \ll n^{-1/2}$ and $p = C q = \tilde \Theta(1)$ for a constant $C>1$, the detection problem is computationally easy while the recovery problem is hard.

A message passing algorithm is derived for recovering communities within a graph generated by a variation of the Barabási-Albert preferential attachment model. The estimator is assumed to know the arrival times, or order of attachment, of the vertices. The derivation of the algorithm is based on belief propagation under an independence assumption. Two precursors to the message passing algorithm are analyzed: the first is a degree thresholding (DT) algorithm and the second is an algorithm based on the arrival times of the children (C) of a given vertex, where the children of a given vertex are the vertices that attached to it. Comparison of the performance of the algorithms shows it is beneficial to know the arrival times, not just the number, of the children. The probability of correct classification of a vertex is asymptotically determined by the fraction of vertices arriving before it. Two extensions of Algorithm C are given: the first is based on joint likelihood of the children of a fixed set of vertices; it can sometimes be used to seed the message passing algorithm. The second is the message passing algorithm. Simulation results are given.