Playlist: 30 videos
Graph Limits, Nonparametric Models, and Estimation
0:47:56
Peter Orbanz (University College London)
https://simons.berkeley.edu/node/22597
Graph Limits, Nonparametric Models, and Estimation
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.
Visit talk page
https://simons.berkeley.edu/node/22597
Graph Limits, Nonparametric Models, and Estimation
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.
0:45:41
Christina Lee Yu (Cornell University) presenting Virtually
https://simons.berkeley.edu/node/22598
Graph Limits, Nonparametric Models, and Estimation
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
Visit talk page
https://simons.berkeley.edu/node/22598
Graph Limits, Nonparametric Models, and Estimation
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
0:51:26
Suman Chakraborty (Leiden University)
https://simons.berkeley.edu/node/22599
Graph Limits, Nonparametric Models, and Estimation
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.
Visit talk page
https://simons.berkeley.edu/node/22599
Graph Limits, Nonparametric Models, and Estimation
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.
0:54:50
Ilias Zadik (Massachusetts Institute of Technology (MIT)
https://simons.berkeley.edu/node/22600
Graph Limits, Nonparametric Models, and Estimation
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
Visit talk page
https://simons.berkeley.edu/node/22600
Graph Limits, Nonparametric Models, and Estimation
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
0:43:20
Lutz Warnke (UC San Diego)
https://simons.berkeley.edu/node/22601
Graph Limits, Nonparametric Models, and Estimation
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.
Visit talk page
https://simons.berkeley.edu/node/22601
Graph Limits, Nonparametric Models, and Estimation
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.
0:50:0
Joonkyung Lee (Hanyang University)
https://simons.berkeley.edu/node/22602
Graph Limits, Nonparametric Models, and Estimation
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.
Visit talk page
https://simons.berkeley.edu/node/22602
Graph Limits, Nonparametric Models, and Estimation
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.
0:50:55
Morgane Austern (Harvard University)
Graph Limits, Nonparametric Models, and Estimation
Visit talk page
Graph Limits, Nonparametric Models, and Estimation
0:40:30
Gursharn Kaur (University of Virgina)
https://simons.berkeley.edu/node/22604
Graph Limits, Nonparametric Models, and Estimation
In this talk, I will present the multivariate normal approximation for the centered subgraph counts in dense random graphs. The main motivation to investigate these statistics is the fact that they are key to understanding fluctuations of regular subgraph counts since they act as an orthogonal basis of a corresponding L2 space. We also identify the resulting limiting Gaussian stochastic measures by means of the theory of generalised U-statistics and Gaussian Hilbert spaces, which we think is a suitable framework to describe and understand higher-order fluctuations in dense random graph models.
This is joint work with Adrian Roellin.
Visit talk page
https://simons.berkeley.edu/node/22604
Graph Limits, Nonparametric Models, and Estimation
In this talk, I will present the multivariate normal approximation for the centered subgraph counts in dense random graphs. The main motivation to investigate these statistics is the fact that they are key to understanding fluctuations of regular subgraph counts since they act as an orthogonal basis of a corresponding L2 space. We also identify the resulting limiting Gaussian stochastic measures by means of the theory of generalised U-statistics and Gaussian Hilbert spaces, which we think is a suitable framework to describe and understand higher-order fluctuations in dense random graph models.
This is joint work with Adrian Roellin.
0:45:56
Siva Athreya (Indian Statistical Insitute)
https://simons.berkeley.edu/node/22605
Graph Limits, Nonparametric Models, and Estimation
We will present out attempts thus far to develop a theory of graphon-valued stochastic processes. We will present a brief review of theory Graphons and dynamics constructed on the space of graphons. We shall construct and analyse a natural class of such processes arising from population genetics. In conclusion we shall present the challenges in our ongoing work on constructing dynamics where the edges and vertices interact with each other. This is joint work with Frank den Hollander and Adrian Roellin
Visit talk page
https://simons.berkeley.edu/node/22605
Graph Limits, Nonparametric Models, and Estimation
We will present out attempts thus far to develop a theory of graphon-valued stochastic processes. We will present a brief review of theory Graphons and dynamics constructed on the space of graphons. We shall construct and analyse a natural class of such processes arising from population genetics. In conclusion we shall present the challenges in our ongoing work on constructing dynamics where the edges and vertices interact with each other. This is joint work with Frank den Hollander and Adrian Roellin
0:45:21
Valentin Féray (Université de Lorraine)
https://simons.berkeley.edu/node/22606
Graph Limits, Nonparametric Models, and Estimation
Cographs are by definition $P_4$-free graphs, i.e. graphs avoiding the path $P_4$ as induced subgraph. In this talk, we will consider a uniform random cograph with $n$ vertices, for large $n$. We shall describe the (random) graphon limit of this object, which is constructed using a Brownian excursion. Motivated by some probabilistic work around Erdős-Hajnal conjecture, we also consider large independent sets in uniform cographs. For both aspects, cographs behave differently from most other $H$-free random graphs.
Based on joint work with F. Bassino, M. Bouvel, M. Drmota, L. Gerin, M. Maazoun and A. Pierrot.
Visit talk page
https://simons.berkeley.edu/node/22606
Graph Limits, Nonparametric Models, and Estimation
Cographs are by definition $P_4$-free graphs, i.e. graphs avoiding the path $P_4$ as induced subgraph. In this talk, we will consider a uniform random cograph with $n$ vertices, for large $n$. We shall describe the (random) graphon limit of this object, which is constructed using a Brownian excursion. Motivated by some probabilistic work around Erdős-Hajnal conjecture, we also consider large independent sets in uniform cographs. For both aspects, cographs behave differently from most other $H$-free random graphs.
Based on joint work with F. Bassino, M. Bouvel, M. Drmota, L. Gerin, M. Maazoun and A. Pierrot.