The Simons Institute for the Theory of Computing had a workshop last month on the Unifying Theory and Experiment for Large-Scale Networks. The videos are in (I am highlighting some videos in this post, for the others, click-through the title of the talk):
Monday, November 18th, 20138:30 am – 8:50 am
Coffee and Check-In
8:50 am – 9:00 am
Opening Remarks
9:00 am – 9:10 am
Overview: Graph Models
Michael Kearns, University of Pennsylvania
9:10 am – 9:35 am
Limiting Behavior in Large Networks
Patrick Wolfe, University College London
How do we simplify and understand a rigid combinatorial object (a finite, discrete graph) in terms of an infinite-dimensional limiting object (a function)? What types of limiting behaviors should we expect empirically? What types do we need mathematically, to ensure consistent inference (leading to algorithms with provable properties, and hence to defensible data-analytic conclusions)?
Practice is Better than Theory: Using Approximate Counting to Mine Large Graphs
Sebastiano Vigna, University of Milan
Algorithms developed in the last decade to analyze large networks (centrality, neighbourhood functions, distance distributions) use approximate set representations. The ways in which these approximate set representation are used give no theoretical guarantee, yet the computations are extremely precise (when compared with a ground truth) and even outperform the theoretical precision of the set representations themselves. It would be interesting to understand why.
Break
10:30 am – 10:55 am
Bayesian Models for Graph Data and the Open Problem of Invariance in Networks
Peter Orbanz, Columbia University
10:55 am – 11:20 am
Know Your Epidemic: But How?
Matt Salganik, Princeton University
11:20 am – 12:00 pm
Discussion
12:00 pm – 1:30 pm
Lunch Break
1:30 pm – 1:40 pm
Overview: Clustering
Jennifer Neville, Purdue University
1:40 pm – 2:05 pm
Asymptotic Analysis of Unlabelled Networks
Peter Bickel, UC Berkeley
2:05 pm – 2:30 pm
Finding Small Structures in Large Datasets
Andrea Montanari, Stanford University
The term 'relational dataset' refers generically to graphs, matrices, networks. I will review a number of examples coming from different communities (machine learning, statistics, computer science) in which it is desirable to find a small structure in such datasets. Some fundamental computational obstructions appear to emerge in each of these domains, and I will discuss their connections.
Break
3:00 pm – 3:25 pm
Local Clustering and the Blessing of Transitivity
Karl Rohe, University of Wisconsin-Madison
3:25 pm – 3:50 pm
Large-scale Graph Clustering and Message-passing-based Distributed Framework
Vahab Mirrokni, Google
3:50 pm – 4:30 pm
Discussion
Tuesday, November 19th, 20138:30 am – 9:00 am
Coffee and Check-In
9:00 am – 9:10 am
Overview: Network Formation
Ashish Goel, Stanford University
9:10 am – 9:35 am
Challenges of Modeling Network Formation in Tractable Ways
Arun Chandrasekhar, Stanford University
9:35 am – 10:00 am
Relating Developmental Transcription Factors (TFs) Based on Fruitfly Embryoic Images
Bin Yu, UC Berkeley
10:00 am – 10:30 am
Break
10:30 am – 10:55 am
Issues in Developing Estimable Models of Strategic Network Formation
Matt Jackson, Stanford University
10:55 am – 11:20 am
Behavioral Experiments in a Network Formation Game
Michael Kearns, University of Pennsylvania
11:20 am – 12:00 pm
Discussion
12:00 pm – 2:00 pm
Lunch Break
2:00 pm – 2:10 pm
Overview: Causality/Experiments
Matt Jackson, Stanford University
2:10 pm – 2:35 pm
Are Observational Studies of Social Contagion Doomed?
Cosma Shalizi, Carnegie Mellon University
2:35 pm – 3:00 pm
On Sampling in Dynamic Networks for Inference, Experiments, and Interventions
Steve Thompson, Simon Fraser University
3:00 pm – 3:30 pm
Break
3:30 pm – 3:55 pm
The Effect of Social Media on News Consumption
Markus Mobius, Microsoft Research New England
3:55 pm – 4:30 pm
Discussion
4:30 pm – 5:30 pm
Reception
Wednesday, November 20th, 20138:30 am – 9:00 am
Coffee and Check-In
9:00 am – 9:10 am
Overview: Label Prediction/Diffusion
Michael Kearns, University of Pennsylvania
9:10 am – 9:35 am
Semi-supervised Learning on Graphs, Using Observed Correlation Structure
Art Owen, Stanford University
9:35 am – 10:00 am
How Predictable are Online Cascades
Lada Adamic, Facebook
10:00 am – 10:30 am
Break
10:30 am – 10:55 am
The Impact of Network Structure on Relational Learning and Inference
Jennifer Neville, Purdue University
10:55 am – 11:20 am
The Emergence of Convention: An Experimental Study of Social Order
Damon Centola, Massachusetts Institute of Technology
11:20 am – 12:00 pm
Discussion
12:00 pm – 1:30 pm
Lunch Break
1:30 pm – 1:40 pm
Overview: Networks Over Time
Patrick Wolfe, University College London
1:40 pm – 2:05 pm
Estimating Time-Varying Networks
Mladen Kolar, Carnegie Mellon University
2:05 pm – 2:30 pm
Pre-Processing of Dynamic Networks: Its Impact on Analytics
Sofus Macskássy, Facebook
2:30 pm – 3:00 pm
Break
3:00 pm – 3:25 pm
Graph Streams and Sketches: What Can and Can't Be Done
Andrew McGregor, University of Massachusetts Amherst
3:25 pm – 3:50 pm
The Trials and Tribulations of Tractably Counting Triangles
C. Seshadhri, Sandia National Laboratories
3:50 pm – 4:30 pm
Discussion
Thursday, November 21st, 20138:30 am – 9:00 am
Coffee and Check-In
9:00 am – 9:10 am
Overview: Scalability/Practical Challenges
Deepak Agarwal, LinkedIn
I will summarize some architectures that are currently used in practice (distributed streaming, single large memory or flash machines, Hadoop, sharded key-value stores, etc). I will outline some graph algorithms that run well on these architectures, and describe some problems for which no good combination of algorithm and architecture is currently known.
On Unifying Asymptotic Complexity with Real-world Performance in Matrix-based Network Computations
David Gleich, Purdue University
Many network analysis questions can be posed as solving a system of linear equations with a stochastic random-walk matrix, e.g. PageRank. Monte Carlo methods often have the best asymptotic complexity for these problems. Yet, those same methods are notoriously slow to find high precision answers. In this talk, we pose some questions on unifying asymptotic complexity with real-world performance.
We consider the following computational model on graphs that slowly change over time. At each time step, the graph incurs a unit update and an algorithm has to periodically probe the graph to learn about the update and modify its solution accordingly. We discuss algorithms in this model for basic graph questions including path connectivity, minimum spanning trees, and PageRank.
10:55 am – 11:20 am
Theoretical and Practical Challenges of Recommending Content to Users in a Social Network
Deepak Agarwal, LinkedIn
Classical Recommender Systems provide serving schemes that display items to users to optimize some user satisfaction metrics. But what happens when such users are connected to each other as in social media platforms like Facebook, LinkedIn and Twitter? Content in such a network is produced by nodes (users) and flows through edges in the graph. This gives rise to challenging and brand new issues when dealing with classical problems like recommending content to users. I will talk about such issues, based on my experience working with feed recommendation problems at LinkedIn.
Liked this entry ? subscribe to Nuit Blanche's feed, there's more where that came from. You can also subscribe to Nuit Blanche by Email, explore the Big Picture in Compressive Sensing or the Matrix Factorization Jungle and join the conversations on compressive sensing, advanced matrix factorization and calibration issues on Linkedin.
No comments:
Post a Comment