- This event has passed.
CANCELLED: Graph Limits
Apr 6, 2020 - Apr 9, 2020
CANCELLED due to Corona Virus
Summary
The workshop will address both the basic theory and the applications of graph limits, focusing on graphons and graphexes, as well as various applications. In the last few years several beautiful and exciting developments have taken place in this area. It is therefore time to bring together researchers from different fields, including probability theory, combinatorics, statistics and algorithmics.
The workshop will run from Monday morning 09.00 am till Thursday afternoon 17.00 pm
Sponsors
Organisers
| Christian Borgs | University of California, Berkeley |
| Jennifer Chayes | University of California, Berkeley |
| Souvik Dhara | MIT Mathematics and Microsoft Research |
| Remco van der Hofstad | NETWORKS (TU Eindhoven) |
| Frank den Hollander | NETWORKS (Leiden University) |
| Viresh Patel | NETWORKS (University of Amsterdam) |
Speakers
| Siva Athreya | Indian Statistical Institute, Bangalore |
| Morgane Austern | Microsoft Research |
| Agnes Backhausz | Eötvös Loránd University |
| Sourav Chatterjee | Stanford University |
| Péter Csikvári | Eötvös Loránd University |
| Jan Hladky | Czech Academy of Sciences |
| Olga Klopp | CNRS |
| Daniel Kral | Masaryk University and University of Warwick |
| Joonkyung Lee | Universität Hamburg |
| László Lovász | Eötvös Loránd University |
| Asaf Nachmias | Tel Aviv University |
| Sofia Olhede | University College London |
| Kavita Ramanan | Brown University |
| Adrian Roellin | National University of Singapore |
| Subhabrata Sen | Harvard University |
| Joel Spencer | New York University |
| Jan Volec | Masaryk University |
| Mei Yin | Denver University |
| Christina Lee Yu | Cornell University |
| Ilias Zadik | New York University |
Abstracts
Graphon dynamics from population genetics
In this talk we shall discuss a natural class of dynamics in dense networks arising from resampling in multi-type populations. We consider sequence of finite graphs whose dynamics are governed by the empirical type distribution of the whole population at that time and in the large-population-size limit this dynamics converges to a random process in the space of graphons.
(joint work with Frank den Hollander and Adrian Rollin)
Limit theorems for group invariant random objects, with applications to random graphs
Limit theorems are the theoretical foundation of statistical inference and are ubiquitous in probability theory. Essential examples of these are the central limit theorem and the Wigner semi-circular law. In this talk, we will greatly extend them–and related theorems–to many “structured” random objects, motivated by the observation that exchangeable graphs, and sparse-exchangeable graphs, are examples of random objects whose distribution is invariant under the action of a group.
Firstly, under mild moment and mixing conditions, we prove a series of universal sec-ond and third order limit theorems for empirical averages of structured random objects: central-limit theorems, concentration inequalities and Berry-Esseen bounds. Secondly, by extending the free central limit theorem beyond the classical setting of free indepen-dence, we generalize the Wigner semi-circle law to a large class of dependent objects. We draw on tools from ergodic theory, free probability, and the Stein method.
We demonstrate the utility of these results in network theory by a series of examples.
Action convergence of graphs and random matrices
The notion of action convergence was proposed to find limit objects for certain sequences of (either deterministic or random) graphs and matrices, which are far from being sparse and dense as well. This approach unifies several concepts of graph limit theory (e.g. local-global convergence of bounded degree graphs, and dense graph convergence), associates limit objects to graph sequences of intermediate density (e.g. hypercubes). Moreover, it can be applied to solve problems about the eigenvectors of random sign matrices (in which all entries are independent, but the norm of the matrix is much smaller than the norm of the adjacency matrix of an Erdos–Renyi graph). The goal of the talk is to present this convergence notion, the limit objects (which are bounded operators of a special form, and general representations of graphons and graphings) and connections to random matrices. Joint work with Balazs Szegedy.
Graphons as weak* limits
Around 2004, Lovasz and Szegedy came up with a certain compactification of the space of finite graphs. More precisely, they proved that the so-called the cut distance yields a compact topology. Their proof of compactnes relies on the Szemeredi regularity lemma. I will talk about approaching the cut norm topology via the weak* topology. This approach gives a new view of many properties, and in particular yields a quick and elementary proof of the Lovasz-Szegedy theorem. As an application of this theory, we prove that a connected graph is weakly norming if and only if it has the “step Sidorenko property”.
A variant of the proof also yields the same statements for hypergraphons.
(joint work with Martin Dolezal, Jan Grebik, Jon Noel, Diana Piguet, Israel Rocha, Vaclav Rozhon, Maria Saumell)
Link Prediction in Sparse Graphon Model
Our work focuses on the study of networks generated under the sparse graphon model with missing observations. In this setting, the problem of es- timating the matrix of connections probabilities is of particular interest. Our results find a natural application in predicting the existence of non-observed edges, a commonly encountered problem called link prediction. Interaction net- works are often incomplete, as detecting interactions can require significant experimental effort. Instead of exhaustively testing for every connection, we deduce the pairs of agents which are most likely to interact based on the relations already recorded and on available covariates. When these estimations are precise enough, testing for these interactions would enable scientists to establish the network topology while substantially reducing the costs.
Uniqueness of combinatorial limits
We will present several results concerning combinatorial structures that are determined by finitely many density constraints. First, we will show that such graph limits can have arbitrarily complex structure in a strong sense. We use this result to provide a counterexample to a conjecture of Lovasz that optimal solutions to extremal graph theory problems can be made asymptotically unique by introducing finitely many additional constraints.
At the end of the talk, we focus on limits corresponding to quasirandom combinatorial structures. For graphs, it is well-known that quasirandomness is characterized by the edge density and the density of C_4. An analogous result holds for permutation: a permutation is quasirandom if and only if the density of every 4-pattern is 1/24+o(1). We strengthen the results by showing that a permutation is quasirandom if and only if the sum of the densities of eight specific 4-patterns is 1/3+o(1), and we characterize all sets of 4-patterns with this property.
(joint with T. Chan, J. Cooper, A. Grzesik, L. M. Lovasz, T. Martins, J. Noel, Y. Pehova, M. Sharifzadeh, J. Sosnovec and J. Volec)
Convex graphon parameters and graph norms
Sidorenko’s conjecture states that the number of copies of a bipartite graph H in a graph G is asymptotically minimised when G is a quasirandom graph. A notorious example where this conjecture remains open is when H=K_{5,5}∖C_{10}. It was even unknown whether this graph possesses the strictly stronger, weakly norming property.
We take a step towards understanding the graph K_{5,5}∖C_{10} by proving that it is not weakly norming. More generally, we show that ‘twisted’ blow-ups of cycles, which include K_{5,5}∖C_{10} and C_{6}□K_{2}, are not weakly norming. This answers two questions of Hatami. The method relies on the analysis of Hessian matrices defined by graph homomorphisms, by using the equivalence between the (weakly) norming property and convexity of graph homomorphism densities. We also prove that K_{t,t} minus a perfect matching, proven to be weakly norming by Lovász, is not norming for every t>3.
(joint work with Bjarne Schülke)
Limits of graph sequences of intermediate density
Convergence and limit objects have been defined mainly in the two extreme cases: dense graphs and bunded-degree graphs. The intermediate cases have attracted considerable interest, but it has been difficult to obtain satisfactory results. Recently it has emerged that Markov chains on measurable spaces, perhaps endowed with some additional structure like a measure on the underlying set, can capture many limiting properties of growing graph sequences. Furthermore, one can extend several graph theoretical concepts and basic theorems (on flows, harmonic functions, mixing of random walks, etc.) to this general setting.
(joint work with Agnes Backhausz, David Kunszenti-Kovács, and Balazs Szegedy)
Uniform spanning trees and graphons
We show that if {G_n} is a sequence of connected graphs with linear degrees that converges to a graphon W, then the uniform spanning tree (UST) of G_n locally converges to a multi-type branching process defined in terms of W. In other words, for any fixed rooted tree F of height r we compute the asymptotic density of vertices of G_n in which their r-neighborhood in the UST is isomorphic to F. A curious corollary is that in any connected graph with linear degrees the density of leaves in a UST is at least exp(-1) – o(1), the density of degree 2 vertices is at most exp(-1) + o(1), and the density of degree k>2 vertices is at most (k-2)^{k-2}exp(2-k)/(k-1)!+o(1), with high probability. The proof illustrates how to combine Szemeredi-like partition theorems with Kirchhoff’s electric network theory.
(joint work with Jan Hldaky and Tuan Tran)
Modeling Networks and Network Populations via Graph Distances
Networks have become a key form of data. Networks allow us to dependence between nodes or actors. Understanding the difference between two networks is also challenging unless they share nodes and are of the same size. We shall discuss how we may compare networks and also consider the regime where more than one network is observed.
We shall also discuss how to parametrize a distribution on labelled graphs in terms of a Frechét mean graph (which depends on a user-specified choice of metric or graph distance) and a parameter that controls the concentration of this distribution about its mean. Entropy is the natural parameter for such control, varying from a point mass concentrated on the Frechét mean itself to a uniform distribution over all graphs on a given vertex set.
Networks present many new statistical challenges. We shall discuss how to resolve these challenges respecting the fundamental non-Euclidean nature of network observations.
(joint work with Simon Lunagomez (Lancaster University) and Patrick Wolfe (Purdue University))
Higher-order fluctuations in dense graph limit theory
Dense graph limit theory is now a well-established approach to describe the structure of large dense networks. While this theory is mainly concerned with the first-order behaviour of graphs in the same way as the Law of Large Numbers describes the first order behaviour of sums of random variables in classical limit theory, a theory to describe second or even higher-order fluctuations around those first order limits has not yet been developed. However, we argue that the tools to understand these fluctuations have already been around since the 90s, although in the more abstract form of generalised U-statistics. We discuss how this theory can be used to describe fluctuations of large graphs, and we complements these results with rates of convergence using Stein’s method and with generalisations that go beyond the framework of generalised U-statistics, but which are still relevant to dense graph limit theory.
Large deviations for dense random graphs: beyond mean-field
In a seminal paper, Chatterjee and Varadhan derived an LDP for the dense Erdös-Rényi random graph, viewed as a random graphon. This directly provides LDPs for continuous functionals such as subgraph counts, spectral norms, etc. In contrast, very little is understood about this problem if the underlying random graph is inhomogeneous or constrained. In this talk, we will take some preliminary steps in this direction, and study large deviations for uniform random graphs with given degrees.
(joint work with Souvik Dhara)
(Some) Finitely Forcible Graphon
Quasirandomness is a robust concept which is implied by the “correct” counts of edges and 4-cycles for G(n,p). We discuss the seminal work of Chung, Graham and Wilson. We give a relatively simple argument that random multipartite graphs are finitely forcible.
Perspectives on exponential random graphs
Exponential random graphs are powerful in the study of modern networks. By representing a complex global configuration through a set of tractable local features, these models seek to capture a wide variety of common network tendencies. This talk will look into the asymptotic structure of weighted exponential random graphs and formulate a quantitative theory of phase transitions. The main techniques that we use are variants of statistical physics. Based on joint work with multiple collaborators.
Tensor Estimation with Nearly Linear Samples
There is a conjectured computational-statistical gap in terms of the number of samples needed to perform tensor estimation. In particular, for a low rank 3-order tensor with \Theta(n) parameters, Barak and Moitra conjectured that \Omega(n^{3/2}) samples are needed for polynomial time computation based on a reduction of a specific hard instance of a rank 1 tensor to the random 3-XOR distinguishability problem. In this paper, we take a complementary perspective and characterize a subclass of tensor instances that can be estimated with only \Omega(n^{1+\kappa}) observations for any arbitrarily small constant \kappa > 0, nearly linear. If one considers the class of tensors with constant orthogonal CP-rank, the “hardness” of the instance can be parameterized by the minimum absolute value of the sum of latent factor vectors. If the sum of each latent factor vector is bounded away from zero, we present an algorithm that can perform tensor estimation with \Omega(n^{1+\kappa}) samples for a t-order tensor, significantly less than the previous achievable bound of \Omega(n^{t/2}), and close to the lower bound of \Omega(n). This result suggests that amongst constant orthogonal CP-rank tensors, the set of computationally hard instances to estimate are in fact a small subset of all possible tensors.
The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property
In this talk, we will focus on the planted clique model, denoted by G(n, 1/2, k),
which is originally introduced by Jerrum in 1992, and independently by Kucera in 1996. An instance of G(n, 1/2, k) is generated by planting a clique of size k uniformly at random in a vanilla Erdös-Rényi graph G(n, 1/2). The inference goal is to recover the vertices of the planted clique from an instance of G(n, 1/2, k). The study of the model have been the focus of a large line of work arising from the probability theory, computer science and statistics communities. While we know that as long as k >(2 + ε) log2 n, for some ε > 0, the clique is recoverable via brute-force methods, no polynomial-time method is proven to succeed unless k > c√n for some c > 0. A convincing explanation for the failure of polynomial-time methods in the regime where k is much smaller than √n is currently missing in the literature of the model.
We are going to discuss some new results on the geometry of the dense subgraphs in an instance of G(n, 1/2, k). Our results suggest that k = Θ (√n) admits an explanation as the phase transition point for the presence of a certain Overlap Gap Property (OGP) on the space of dense subgraphs. OGP is a disconnectivity notion which originates in spin glass theory and is known to suggest algorithmic harness when it appears. Finally, we show that OGP implies the failure of a large family of MCMC methods to recover the clique when k is much smaller than √n.
(joint work with David Gamarnik)
More information will follow as it becomes available.
Registration