Classical Physics - Lecture 221003
PIRSA:22100058
4357 - 4368 of 20126 Results
Format results
Optimality of Variational Inference for Stochastic Block Model
Olga Klopp (ESSEC Business School)Machine Learning on Large-Scale Graphs
Luana Ruiz (University of Pennsylvania)Long Range Dependence in Evolving Networks
Shankar Bhamidi (University of North Carolina, Chapel Hill)Indigenizing the Drake Equation: exploring the question of life in our Galaxy through an Indigenist lens.
Hilding Neilson Memorial University of Newfoundland
Stochastic Processes on Sparse Graphs: Hydrodynamic Limits and Markov Approximations
Kavita Ramanan (Brown University)Large Deviation Principle for the Norm of the Adjacency Matrix and the Laplacian Matrix of Inhomogeneous Erd\H{o}s-R\'enyi Random Graphs
Frank den Hollander (Leiden University)Diamagnetic response and phase stiffness for interacting isolated narrow bands
Dan Mao Massachusetts Institute of Technology (MIT)
Two aspects of quantum information theory in relation to holography
Rene Meyer Max-Planck Gesellschaft
Longitudinal Network Models, Log-Linear Multigraph Models, and Implications to Estimation and Testing Model Fit
Sonja Petrović (Illinois Institute of Technology)
Classical Physics - Lecture 221003
PIRSA:22100058Optimality of Variational Inference for Stochastic Block Model
Olga Klopp (ESSEC Business School)Abstract Variational methods are extremely popular in the analysis of network data. Statistical guarantees obtained for these methods typically provide asymptotic normality for the problem of estimation of global model parameters under the stochastic block model. In the present work, we consider the case of networks with missing links that is important in application and show that the variational approximation to the maximum likelihood estimator converges at the minimax rate. This provides the first minimax optimal and tractable estimator for the problem of parameter estimation for the stochastic block model. We complement our results with numerical studies of simulated and real networks, which confirm the advantages of this estimator over current methods.Machine Learning on Large-Scale Graphs
Luana Ruiz (University of Pennsylvania)Abstract Graph neural networks (GNNs) are successful at learning representations from most types of network data but suffer from limitations in large graphs, which do not have the Euclidean structure that time and image signals have in the limit. Yet, large graphs can often be identified as being similar to each other in the sense that they share structural properties. Indeed, graphs can be grouped in families converging to a common graph limit -- the graphon. A graphon is a bounded symmetric kernel which can be interpreted as both a random graph model and a limit object of a convergent sequence of graphs. Graphs sampled from a graphon almost surely share structural properties in the limit, which implies that graphons describe families of similar graphs. We can thus expect that processing data supported on graphs associated with the same graphon should yield similar results. In this talk, I formalize this intuition by showing that the error made when transferring a GNN across two graphs in a graphon family is small when the graphs are sufficiently large. This enables large-scale graph machine learning by transference: training GNNs on moderate-scale graphs and executing them on large-scale graphs.Survey on Sparse Graph Limits + A Toy Example
Mei Yin (University of Denver)Abstract The theory of graph limits is an important tool in understanding properties of large networks. We begin the talk with a survey of this theory, concentrating in particular on the sparse setting. We then investigate a power-law random graph model and cast it in the sparse graph limit theory framework. The distinctively different structures of the limit graph are explored in detail in the sub-critical and super-critical regimes. In the sub-critical regime, the graph is empty with high probability, and in the rare event that it is non-empty, it consists of a single edge. Contrarily, in the super-critical regime, a non-trivial random graph exists in the limit, and it serves as an uncovered boundary case between different types of graph convergence.Long Range Dependence in Evolving Networks
Shankar Bhamidi (University of North Carolina, Chapel Hill)Abstract The goal of this talk is to describe probabilistic approaches to three major problems for dynamic networks, both of which are intricately connected to long range dependence in the evolution of such models: 1.Nonparametric change point detection: Consider models of growing networks which evolve via new vertices attaching to the pre-existing network according to one attachment function $f$ till the system grows to size $τ(n) < n$, when new vertices switch their behavior to a different function g till the system reaches size n. The goal is to estimate the change point given the observation of the networks over time with no knowledge of the functions driving the dynamics. We will describe non-parametric estimators for such problems. 2. Detecting the initial seed which resulted in the current state of the network: Imagine observing a static time slice of the network after some large time $n$ started with an initial seed. Suppose all one gets to see is the current topology of the network (without any label or age information). Developing probably efficient algorithms for estimating the initial seed has inspired intense activity over the last few years in the probability community. We will describe recent developments in addressing such questions including robustness results such as the fixation of so called hub vertices as time evolves. 3. Co-evolving networks: models of networks where dynamics on the network (directed random walks towards the root) modifies the structure of the network which then impacts behavior of subsequent dynamics. We will describe non-trivial phase transitions of condensation around the root and its connection to quasi-stationary distributions of 1-d random walks.Indigenizing the Drake Equation: exploring the question of life in our Galaxy through an Indigenist lens.
Hilding Neilson Memorial University of Newfoundland
The Drake Equation is a thought experiment whose purpose is to understand the ingredients necessary for life and advanced technological civilizations to exist on other worlds in our galaxy. However, beyond reflecting on life on Earth we have no knowledge of many of these ingredients, such as the number of planets that have life, the number of with intelligent life, the number with advanced civilizations, and the lifetimes of these civilizations. In this talk I will review the Drake Equation and the biases that scientists have traditionally had in discussing this equation and how it has led to the current searches of biological and technological signatures. I will discuss how the Drake Equation looks different if we consider it through the lens of Indigenous methods and sciences and how these methods would lead to a dramatically different view of life in our Galaxy.
Zoom link: https://pitp.zoom.us/j/95952883179?pwd=a2lzaEc2UWJER2k2VmwzRVgvMVpoQT09
Stochastic Processes on Sparse Graphs: Hydrodynamic Limits and Markov Approximations
Kavita Ramanan (Brown University)Abstract We consider interacting particle systems on suitable convergent sequences of sparse (or heterogeneous graphs) and show that the limiting dynamics of the associated neighborhood empirical measure process (the so-called hydrodynamic limit) can be autonomously characterized in terms of a non-Markovian process. We then describe Markovian approximations to the latter and provide examples where they are exact. This includes joint work with G. Cocomello and A. Ganguly.Large Deviation Principle for the Norm of the Adjacency Matrix and the Laplacian Matrix of Inhomogeneous Erd\H{o}s-R\'enyi Random Graphs
Frank den Hollander (Leiden University)Abstract We consider an inhomogeneous Erd\H{o}s-R\'enyi random graph $G_N$ with vertex set $[N] = \{1,\dots,N\}$ for which the pair of vertices $i,j \in [N]$, $i\neq j$, is connected by an edge with probability $r(\tfrac{i}{N},\tfrac{j}{N})$, independently of other pairs of vertices. Here, $r\colon\,[0,1]^2 \to (0,1)$ is a symmetric function that plays the role of a reference graphon. (1) Let $\lambda_N$ be the maximal eigenvalue of the \emph{adjacency matrix} of $G_N$. It is known that $\lambda_N/N$ satisfies an LDP with rate $N$ as $N \to \infty$. The associated rate function $\psi_r$ is given by a variational formula that involves the rate function $I_r$ of a large deviation principle on graphon space. We analyse this variational formula in order to identify the basic properties of $\psi_r$, especially when the reference graphon $r$ is of rank 1. (2) Let $\hat\lambda_N$ be the maximal eigenvalue of the \emph{Laplacian matrix} of $G_N$. We show that $\hat\lambda_N/N$ satisfies a downward LDP with rate $\binom{N}{2}$ and an upward LDP with rate $N$. The associated rate functions $\hat\psi_r$ and $\hat\psi^*_r$ are those of the downward LDP and upward LDP for the maximal degree in the graph. We identify the basic properties of both $hat\psi_r$ and $\hat\psi^*_r$.Diamagnetic response and phase stiffness for interacting isolated narrow bands
Dan Mao Massachusetts Institute of Technology (MIT)
Superconductivity in electronic systems, where the non-interacting bandwidth for a set of isolated bands is small compared to the scale of the interactions, is a non-perturbative problem. Here we present a theoretical framework for computing the electromagnetic response in the limit of zero frequency and vanishing wavenumber for the interacting problem, which controls the superconducting phase stiffness, without resorting to any mean-field approximation. Importantly, the contribution to the phase stiffness arises from (i) ``integrating-out" the remote bands that couple to the microscopic current operator, and (ii) the density-density interactions projected on to the isolated bands. We also obtain the electromagnetic response directly in the limit of an infinite gap to the remote bands, using the appropriate ``projected" gauge-transformations. These results can be used to obtain a conservative upper bound on the phase stiffness, and relatedly the superconducting transition temperature, with a few assumptions. In a companion article, we apply this formalism to a host of topologically (non-)trivial ``flat-band" systems, including twisted bilayer graphene.
Zoom link: https://pitp.zoom.us/j/99631762791?pwd=dU4yaU1wKzJNTisrazJjaUF2ODlXUT09
Two aspects of quantum information theory in relation to holography
Rene Meyer Max-Planck Gesellschaft
The fact black holes carry statistical entropy proportional to their horizon area implies that quantum information concepts are geometrized in gravity. This idea obtains a particular manifestation in the AdS/CFT correspondence, where it is believed that the quantum information content in the dual field theory state can be used to reconstruct the bulk space-time geometry. The calculation of entanglement entropy from geodesics in the bulk space-time have clarified this idea to some extend.
In this talk, I will consider two aspects of quantum information theory in relation to holography: First, I will discuss a refinement of entanglement entropy for systems with conserved charges, the so-called symmetry resolved entanglement. It measures the entanglement in a sector of fixed charge. I will present how to calculate the symmetry-resolved entanglement entanglement in two-dimensional conformal field theories with Kac-Moody symmetry, and also within W_3 higher spin theory. I will also discuss the geometric realization in the dual AdS space-time, and how the independent calculation there leads to a new test of the AdS3/CFT2 correspondence.
Second, I will discuss the large N limit of Nielsen's operator complexity on the SU(N) manifold, with a particular choice of cost function based on the Laplacian on the Lie algebra, which leads to polynomial (instead of exponential) penalty factors. I will first present numerical results that hint to the existence of chaotic and hence ergodic geodesic motion on the group manifold, as well show the existence of conjugate points. I will then discuss a mapping between the Euler-Arnold equation which governs the geodesic evolution, to the Euler equation of two-dimensional idea hydrodynamics, in the strict large N limit.Longitudinal Network Models, Log-Linear Multigraph Models, and Implications to Estimation and Testing Model Fit
Sonja Petrović (Illinois Institute of Technology)Abstract Consider longitudinal networks whose edges turn on and off according to a discrete-time Markov chain with exponential-family transition probabilities. We characterize when their joint distributions are also exponential families with the same parameter, and show that the permutation-uniform subclass of these chains permit interpretation as an independent, identically distributed sequence on the same state space. We apply these ideas to temporal exponential random graph models, for which permutation uniformity is well suited, and discuss mean-parameter convergence, dyadic independence, and exchangeability. The framework facilitates applying standard tools to longitudinal-network Markov chains from either asymptotics or single-observation exponential random graph models. The latter are often in log-linear form, allowing us to frame the problem of testing model fit through an exact conditional test whose p-value can be approximated efficiently in networks of both small and moderately large sizes. An important extension of this theory is to latent-variable blockmodels, an application which will be briefly discussed. This talk is based on joint work with William K. Schwartz, Hemanshu Kaul, Despina Stasi, Elizabeth Gross, Debdeep Pati, and Vishesh Karwa.Graphon Games
Francesca Parise (Cornell University)Abstract Many of today’s most promising technological systems involve very large numbers of autonomous agents that influence each other and make strategic decisions within a network structure. Examples include opinion dynamics, targeted marketing in social networks, economic exchange and international trade, product adoption and social contagion. While traditional tools for the analysis of these systems assumed that a social planner has full knowledge of the underlying game, when we turn to very large networks two issues emerge. First, collecting data about the exact network of interactions becomes very expensive or not at all possible because of privacy concerns. Second, methods for designing optimal interventions that rely on the exact network structure typically do not scale well with the population size. To obviate these issues, in this talk I will consider a framework in which the social planner designs interventions based on probabilistic instead of exact information about agent’s interactions. I will introduce the tool of “graphon games” as a way to formally describe strategic interactions in this setting and I will illustrate how this tool can be exploited to design asymptotically optimal interventions for general classes of network games, beyond the linear quadratic setting.