Kickoff Workshop: Inference and Data Science on Networks

About the Series

The IDEAL workshop series brings in four experts on topics related to the foundations of data science to present their perspective and research on a common theme. Chicago area researchers with an interest in the foundations of data science. The series will be remote while our universities and local government advise avoiding non-essential meetings. The virtual format will have two talks before lunch, two talks after lunch, and an early evening panel discussion (where appropriate).

Part of the Special Quarter on Inference and Data Science on Networks.

Synopsis

Over the past decade or so, many diverse communities have become increasingly interested in networks as a way of understanding the role of interconnections between various entities. For example, economists, social scientists and policy researchers have studied how the social and economic ties between agents drive important economic phenomena such as income inequality, human capital accumulation, the dynamics of the business cycle and research productivity. Likewise, there has been interest from computer scientists and engineers in understanding the network structures that emerge in the Internet, the World Wide Web and online social networks. However, the empirical literature has been limited by the fact that networks are inherently high-dimensional objects, which makes it intractable to directly assess the importance of network structure without a substantial amount of unrealistic functional form assumptions. These present several new and exciting statistical and algorithmic challenges at the interface of network science, econometrics and machine learning.

In this workshop several of the coorganizers of the special quarter will speak about their vision for the theme. Talks will be by Eric Auerbach, Randall Berry, Ozan Candogan, and Aravindan Vijayaraghavan.

Logistics

Date: Tuesday, May 5, 2020.
Location: Zoom participation (register below), Panopto streaming.
Registration: Registration form. Registered participants will get a Zoom link to the workshop by email.

Schedule

10:55-11:00: Opening Remarks
11:00-11:40: Eric Auerbach (Northwestern U, Economics)
Measuring differences in stochastic network structure.
11:45-12:25: Randall Berry (Northwestern University, Electrical and Computer Engineering)
Social Learning with Corrupted Observations.
12:30-1:30: Lunch Break
1:30-2:10: Aravindan Vijayaraghavan (Northwestern U, Computer Science)
Provably Efficient Algorithms for Probabilistic Inference in the Real World.
2:15-2:55: Ozan Candogan (University of Chicago, Booth):
Persuasion in Networks: Public Signals and k-Cores.
3:00-4:00: Afternoon Break
4:00-5:00: Open Problems Session (for members of the institute)

Titles and Abstracts

Speaker: Eric Auerbach, Northwestern University

Title: Measuring differences in stochastic network structure.

Abstract: How can on determine whether a community-level treatment, such as the introduction of a social program or trade shock, alters agents’ incentives to form links in a network? This paper proposes analogues of a two-sample Kolmogorov-Smirnov test, widely used in the literature to test the null hypothesis of “no treatment effects,” for network data. It first specifies a testing problem in which the null hypothesis is that two networks are drawn from the same random graph model. It then describes two randomization tests based on the magnitude of the difference between the networks’ adjacency matrices as measured by the 2→2 and ∞ →1 operator norms. Power properties of the tests are examined analytically, in simulation, and through two real-world applications. A key finding is that the test based on the ∞ →1 norm can be substantially more powerful than that based on the 2→2 norm for the kinds of sparse and degree-heterogeneous networks common in economics.

Speaker: Randall Berry, Northwestern University

Title: Social learning with corrupted observations

Abstract: Social learning refers to situations in which agents learn from observing the action of others. Such situations have been well studied as dynamic Bayesian games. Here we describe some recent work on these topics in which the observations of agents is corrupted by either adding “noise” or through the actions of “fake agents.” For these models we show that in some cases this corruption may actually benefit the agents.

Speaker: Aravindan Vijayaraghavan, Northwestern

Title: Provably Efficient Algorithms for Probabilistic Inference in the Real World

Abstract: Probabilistic graphical models are widely used in statistical inference for describing complex dependencies in data, and for several machine learning tasks like prediction, classification, clustering. A fundamental inference problem underlying many of these applications of graphical models is to find the most likely configuration of the probability distribution, called the maximum a posteriori (MAP) assignment. MAP inference problems for graphical models often reduce to well-studied combinatorial optimization problem that are known theoretically to be NP-hard in the worst-case. However, practitioners have made significant strides in designing heuristic algorithms to perform real-world inference accurately and efficiently. In this talk, I will talk about some recent work that tries to reconcile this disconnect, by giving provably polynomial time guarantees using some paradigms that go “beyond worst-case analysis”.

Speaker: Ozan Candogan, University of Chicago

Title: Persuasion in Networks: Public Signals and k-Cores

Abstract: We consider a setting where agents in a social network take binary actions, which exhibit local strategic complementarities. The agents are a priori uninformed about an underlying payoff-relevant state. An information designer wants to maximize the expected number of agents who take action 1, and she can commit to a signaling mechanism which upon the realization of the state sends an informative signal to all the agents. We study the design of the optimal public signaling mechanisms and explore their dependence on the network structure.