Graphons: From Graph Limits to Modeling and Estimation of Sparse Networks at Scale: Neyman Seminar

Seminar | October 7 | 4-5 p.m. | Doe Library, BIDS Room

 Christian Borgs, Microsoft Research

 Department of Statistics

There are many examples of sparse network at scale, e.g., the WWW, online social networks, and large bipartite networks used for recommendations. How do we model and learn these networks? In contrast to conventional learning problems, where we have many independent samples, it is often the case for these networks that we can get only one independent sample. How do we use a single snapshot today to learn a model for the network, and therefore be able to predict a similar, but larger network in the future? In the case of relatively small or moderately sized networks, it’s appropriate to model the network parametrically, and attempt to learn these parameters. For networks at scale, a non-parametric representation is more appropriate. In this talk, I first review the theory of graphons, developed over the last 15 years to describe limits of dense graphs, and the more recent theory describing sparse graphs of unbounded average degree, including power-law graphs. I show how to use these graphons as non-parametric models for sparse networks. I then show how to get consistent estimators of these non-parametric models, and moreover how to do this in a way that protects the privacy of individuals on the network. Finally, I briefly touch on recommendation algorithms based on these models, with applications to sparse bipartite networks such as Netflix.

 Berkeley, CA 94720, 5106422781