Computer Science

Abstract Consider the subgraph sampling model, where we observe a random subgraph of a given (possibly non random) large graph $G_n$, by choosing vertices of $G_n$ independently at random with probability $p_n$. In this setting, we study the question of estimating the number of copies $N(H,G_n)$ of a fixed motif/small graph (think of $H$ as edges, two stars, triangles) in the big graph $G_n$. We derive necessary and sufficient conditions for the consistency and the asymptotic normality of a natural Horvitz-Thompson (HT) type estimator. As it turns out, the asymptotic normality of the HT estimator exhibits an interesting fourth-moment phenomenon, which asserts that the HT estimator (appropriately centered and rescaled) converges in distribution to the standard normal whenever its fourth-moment converges to 3. We apply our results to several natural graph ensembles, such as sparse graphs with bounded degree, Erdős-Renyi random graphs, random regular graphs, and dense graphons. This talk is based on joint work with Bhaswar B. Bhattacharya and Sayan Das.

Abstract For any given graph $H$, one may define a natural corresponding functional $\|.\|_H$ for real(or complex) valued functions by using the homomorphism density of $H$. We say that $H$ is \emph{norming} if $\|.\|_H$ is a norm. This generalises the Gowers octahedral norms, a widely used tool in extremal combinatorics to quantify quasirandomness. In 2008, Lov\'{a}sz asked what graphs are norming. This has been a central question in the theory of dense graph limits and also connects to Sidorenko's conjecture, a major open problem in extremal graph theory. For the recent few years, there have been interesting developments on the Lovász question, where algebraic combinatorics, extremal graph theory and functional analysis meet. In this talk, I will discuss some of the progress. Based on joint work with David Conlon, Frederik Garbe, Jan Hladk\'{y}, Bjarne Sch\"{u}lke, and Sasha Sidorenko.

The degree-restricted random process is a natural algorithmic model for generating graphs with degree sequence D_n=(d_1,...,d_n): starting with an empty n-vertex graph, it sequentially adds new random edges so that the degree of each vertex v_i remains at most d_i.  It is natural to ask whether the final graph of this process is similar to a uniform random graph with degree sequence D_n (for d-regular degree sequences D_n this was already raised by Wormald in the mid 1990s). We show that, for degree sequences D_n that are not nearly regular, the final graph of the degree-restricted random process differs substantially from a uniform random graph with degree sequence D_n.  Our proof uses the switching method, which is usually only applied to uniform random graph models -- rather than to stochastic processes. Based on joint work with Mike Molloy and Erlang Surya.

Abstract For a given graph H we are interested in the critical value of p so that a sample of an Erdos-Renyi graph contains a copy of H with high probability,  Kahn and Kalai in 2006 conjectured that it should be given (up to a logarithm) by the minimum p so that in expectation all subgraphs H' of H appear in G(n,p). In this work, we will present a proof of a modified version of this conjecture. Our proof is based on a powerful "spread lemma", which played a key role in the recent breakthroughs on the sunflower conjecture and the proof of the fractional Kahn-Kali conjecture. Time permitting, we will discuss a new proof of the spread lemma using Bayesian inference tools. This is joint work with Elchanan Mossel, Jonathan Niles-Weed and Nike Sun

Abstract It is well known that sparse random graphs (where the number of edges is of the order of the number of vertices) contain only a small number of triangles. On the other hand, many networks observed in real life are sparse but contain a large number of triangles. Motivated by this discrepancy we ask the following two questions: How (un)likely is it that a sparse random graph contains a large number of triangles? What does the graph look like when it contains a large number of triangles? We also ask a related question: What is the probability that in a sparse random graph a large number of vertices are part of some triangle? We discuss these questions, as well as some applications to exponential random graph models.

Abstract   In many domains, we are interested in estimating the total causal treatment effect in the presence of network interference, where the outcome of one individual or unit is affected by the treatment assignment of those in its local network. Additional challenges arise when complex cluster randomized designs are not feasible to implement, or the network is unknown and costly to estimate. We propose a new measure of model complexity that characterizes the difficulty of estimating the total treatment effect under the standard A/B testing setup. We provide a class of unbiased estimators whose variance is optimal with respect to the population size and the treatment budget. Furthermore, we show that when the network is completely unknown, we can still estimate the total treatment effect under a richer yet simple staggered rollout experimental design. The proposed design principles, and related estimator, work with a broad class of outcome models. Our solution and statistical guarantees do not rely on restrictive network properties, allowing for highly connected networks that may not be easily clustered. This is joint work with Edoardo Airoldi, Christian Borgs, Jennifer Chayes, Mayleen Cortez, and Matthew Eichhorn

Abstract A random structure exhibits symmetry if its law remains invariant under a group of transformations. Exchangeability (of graphs, sequences, etc) and stationarity are examples. Under suitable conditions, the transformation group can be used to define an estimator that averages over an instance of the structure, and such estimators turn out to satisfy a law of large numbers, a central limit theorem, and further convergence results. Loosely speaking: The large-sample theory of i.i.d averages still holds if the i.i.d assumption is substituted by a suitable symmetry assumption.  Joint work with Morgane Austern.

Abstract Dense graph limit theory is mainly concerned with law-of large-number type of results. We propose a corresponding central limit theorem - or rather fluctuation theory - based on Janson's theory of Gaussian Hilbert Spaces and generalised U-statistics from the 1990s. Our approach provides rates and allows for proper statistical inference based on subgraph counts.

Abstract   The problem of completing a large low rank matrix using a subset of revealed entries has received much attention in the last ten years. I will give a necessary and sufficient condition, stated in the language of graph limit theory, for a sequence of matrix completion problems with arbitrary missing patterns to be asymptotically solvable. I will also present an algorithm that is able to approximately recover the matrix whenever recovery is possible.

Abstract Ramsey's Theorem states that for every graph H, there is an integer R(H) such that every 2-edge-coloring of R(H)-vertex complete graph contains a monochromatic copy of H. In this talk, we focus on a natural quantitative extension: how many monochromatic copies of H can we find in every 2-edge-coloring of K_N, and what graphs H are so-called common, i.e., the number of monochromatic copies of H is asymptotically minimized by a random 2-edge-coloring. A classical result of Goodman from 1959 states that the triangle is a common graph. On the other hand, Thomason proved in 1989 that no clique of order at least four is common, and the existence of a common graph with chromatic number larger than three was open until 2012, when Hatami, Hladky, Kral, Norin and Razborov proved that the 5-wheel is common. In this talk, we show that for every k>4 there exists a common graph with chromatic number k. This is a joint work with D. Kral and F. Wei

Abstract We initiate a study of large deviations for block model random graphs in the dense regime. Following Chatterjee and Varadhan (2011), we establish an LDP for dense block models, viewed as random graphons. As an application of our result, we study upper tail large deviations for homomorphism densities of regular graphs. We identify the existence of a "symmetric'' phase, where the graph, conditioned on the rare event, looks like a block model with the same block sizes as the generating graphon. In specific examples, we also identify the existence of a "symmetry breaking'' regime, where the conditional structure is not a block model with compatible dimensions. This identifies a "reentrant phase transition'' phenomenon for this problem---analogous to one established for Erdős–Rényi random graphs (Chatterjee and Dey (2010), Charrerjee and Varadhan (2011)). Finally, extending the analysis of Lubetzky and Zhao (2015), we identify the precise boundary between the symmetry and symmetry breaking regimes for homomorphism densities of regular graphs and the operator norm on Erdős–Rényi bipartite graphs. Joint work with Christian Borgs, Jennifer Chayes, Subhabrata Sen, and Samantha Petti

Abstract Variational approximations provide an attractive computational alternative to MCMC-based strategies for approximating the posterior distribution in Bayesian inference. Despite their popularity in applications, supporting theoretical guarantees are limited, particularly in high-dimensional settings. In this talk, we will study bayesian inference in the context of a linear model with product priors, and derive sufficient conditions for the correctness (to leading order) of the naive mean-field approximation. To this end, we will utilize recent advances in the theory of non-linear large deviations (Chatterjee and Dembo 2014). Next, we analyze the naive mean-field variational problem, and precisely characterize the asymptotic properties of the posterior distribution in this setting. The theory of graph limits provides a crucial ingredient to study this high-dimensional variational problem. This is based on joint work with Sumit Mukherjee (Columbia University).