skip to content

Timetable (SNAW05)

Bayesian methods for networks

Monday 25th July 2016 to Wednesday 27th July 2016

Monday 25th July 2016
09:00 to 09:50 Registration
09:50 to 10:00 Welcome from Christie Marr (INI Deputy Director) INI 1
10:00 to 11:00 Peter Hoff
Bayesian Methods for Networks
Statistical analysis of social network data presents many challenges: Realistic models often require a large number of parameters, yet maximum likelihood estimates for even the simplest models may be unstable. Furthermore, network data often exhibit non-standard statistical dependencies, and most network datasets lack any sort of replication.

Statistical methods to address these issues have included random effects and latent variable models, and penalized likelihood methods. In this talk I will discuss how these approaches fit naturally within a Bayesian framework for network modeling. Additionally, we will discuss how standard Bayesian concepts such as exchangeability play a role in the development and interpretation of probability models for networks. Finally, some thoughts on the use of Bayesian methods for large-scale dynamic networks will be presented.
11:00 to 11:30 Morning Coffee
11:30 to 12:00 Alisa Kirichenko
Function estimation on large graphs with missing data
Co-author: Harry van Zanten (University of Amsterdam)

There are various problems in statistics and machine learning that involve making an inference about a function on a graph. I will present a Bayesian approach to estimating a smooth function in the context of regression and classification problems on graphs. I will discuss the mathematical framework that allows to study the performance of nonparametric function estimation methods on large graphs. I will review theoretical results that show how to achieve asymptotically optimal Bayesian regularization under geometry conditions on the families of the graphs and the smoothness assumption on the true function. Both assumptions are formulated in terms of graph Laplacian. I will also discuss the case of "uniformly distributed" missing observations and investigate the generalization performance for various missing mechanisms.
12:00 to 12:30 Sergio Bacallado
Bayesian sequential design in matrix factorisation models
Co-author: Annie Marsden (University of Cambridge)

Many problems in high-dimensional statistics rely on low-rank decompositions of matrices. Examples include matrix completion, recommender systems or collaborative filtering, and graph clustering or community detection. Most commonly, estimates are obtained by solving an optimisation problem through SDP relaxations, expectation maximisation, or projected gradient descent algorithms. Bayesian analogs of these procedures provide estimates of uncertainty, but these are rarely exploited in practice. In this talk, we explore how the posterior distribution in matrix factorisation models can be put to use in sequential design problems. Bayesian procedures such as Thompson sampling and the Bayesian UCB have been shown to achieve optimal regret in Multi-Arm Bandit problems. We present a simulation study supporting similar strategies in recommender systems.
12:30 to 13:30 Lunch @ Wolfson Court
13:30 to 14:00 Harry Crane
Edge exchangeability: a new foundation for modeling network data
Exchangeable models for vertex labeled graphs cannot replicate the large sample behaviors of sparsity and power law degree distributions observed in many network datasets. To address this issue, we introduce the principle of edge exchangeability, which is more natural for most applications and admits models for networks with sparse and/or power law structure. The vertices in an edge exchangeable network arrive in size-biased order according to their degree, further explaining why vertex exchangeability is an untenable assumption for many applications.

Our discussion settles a longstanding question of statistical network modeling and presents a new framework within which to develop future theory and methods.

Joint work with Walter Dempsey.
14:00 to 14:30 Cameron Freer
Exchangeable constructions of countable structures
Co-authors: Nathanael Ackerman (Harvard University), Diana Cai (University of Chicago), Alex Kruckman (UC Berkeley), Aleksandra Kwiatkowska (University of Bonn), Jaroslav Nesetril (Charles University in Prague), Rehana Patel (Franklin W. Olin College of Engineering), Jan Reimann (Penn State University)

The Aldous-Hoover-Kallenberg theorem and the theory of graph limits connect three kinds of objects: sequences of finite graphs, random countably infinite graphs, and certain continuum-sized measurable "limit" objects (graphons). Graphons induce exchangeable countably infinite graphs via sampling, and all exchangeable graphs arise from a mixture of such sampling procedures -- a two-dimensional generalization of de Finetti's theorem.

This naturally leads to the question of which countably infinite graphs (or other structures) can arise via an exchangeable construction. More formally, consider a random structure with a fixed countably infinite underlying set. The random structure is exchangeable when its joint distribution is invariant under permutations of the underlying set. For example, the countably infinite Erdős–Rényi graph is exchangeable; moreover, it is almost surely isomorphic to a particular graph, known as the Rado graph, and so we say that the Rado graph admits an exchangeable construction. On the other hand, one can show that no infinite tree admits an exchangeable construction.

In joint work with Ackerman and Patel, we provide a necessary and sufficient condition for a countably infinite structure to admit an exchangeable construction. We also address related questions, such as what structures admit a unique exchangeable construction, and give examples involving graphs, directed graphs, and partial orders.

Joint work with Nathanael Ackerman, Diana Cai, Alex Kruckman, Aleksandra Kwiatkowska, Jaroslav Nešetřil, Rehana Patel, and Jan Reimann. 
14:30 to 15:30 Afternoon Tea
15:30 to 16:00 Lise Getoor
Statistical Relational Learning: Review and Recent Advances
Statistical relational learning (SRL) is a subfield of machine learning that combines relational representations (from databases and AI) with probabilistic modeling techniques (most often graphical models)for modeling network data (typically richly structured multi-relational and multi-model networks).  In this talk, I will briefly review some SRL modeling techniques, and then I will introduce hinge-loss Markov random fields (HL-MRFs), a new kind of probabilistic graphical model that supports scalable collective inference from richly structured data.  HL-MRFs unify three different approaches to convex inference: LP approximations for randomized algorithms, local relaxations for probabilistic graphical models, and inference in soft logic.  I will show that all three lead to the same inference objective.  This makes inference in HL-MRFs highly scalable.   Along the way, I will describe several successful applications of HL-MRFs and I will describe probabilistic soft logic, a declarative language for defining HL-MRFS.
16:00 to 16:30 Nial Friel
Optimal Bayes estimators for block models
In cluster analysis interest lies in probabilistically capturing partitions of individuals, items or nodes of a network into groups, such that those belonging to the same group share similar attributes or relational profiles. Bayesian posterior samples for the latent allocation variables can be effectively obtained in a wide range of clustering models, including finite mixtures, infinite mixtures, hidden markov models and block models for networks. However, due to the categorical nature of the clustering variables and the lack of scalable algorithms, summary tools that can interpret such samples are not available. We adopt a Bayesian decision theoretic approach to define an optimality criterion for clusterings, and propose a fast and context-independent greedy algorithm to find the best allocations. One important facet of our approach is that the optimal number of groups is automatically selected, thereby solving the clustering and the model-choice problems at the same time. We discuss the choice of loss functions to compare partitions, and show that our approach can accommodate a wide range of cases. Finally, we illustrate our approach on a variety of real-data applications for the stochastic block model and latent block model.  

This is joint work with Riccardo Rastelli. 
16:30 to 17:30 Welcome Wine Reception
Tuesday 26th July 2016
09:00 to 09:30 Adrian Raftery
Interlocking directorates in Irish companies using bipartite networks: a latent space approach
Co-authors: Nial Friel (University College Dublin), Riccardo Rastelli (University College Dublin), Jason Wyse (Trinity College Dublin)

We analyze the temporal bipartite network of the leading Irish com- panies and their directors from 2003 to 2013, encompassing the end of the Celtic Tiger boom and the ensuing nancial crisis in 2008. We focus on the evolution of company interlocks, whereby a company director simultaneously sits on two or more boards. We develop a novel statistical model for this dataset by embedding the positions of companies and directors in a latent space. A useful aspect of our modelling approach is that it accommodates the development of metrics which can be used to assess the extent of interlocking over time.
09:30 to 10:00 Pierre Latouche
Goodness of fit of logistic models for random graphs
We consider  binary networks along with covariate information on the edges. In order to take these covariates into account, logistic-type models for random graphs are often considered. One of the main questions which arises in practice is to assess the goodness of fit of a  model. To address this problem, we add a general term, related to the graphon function of W-graph models, to the logistic models. Such an extra term can be approximated from a blockwise constant function obtained using  stochastic block models with increasing number of clusters. If the given network is fully explained by the covariates, then a sole block should be estimated from data. This framework allows to derive a testing procedure from a model based selection context. Bayes factors or posterior odds can then be used for decision making. Overall, the logistic model considered necessitates two types of variational approximations to derive the model selection approach. 
10:00 to 10:30 Simon Lunagomez
Network Models with Dynamic Vertex Sets
Many models of dynamic network data assume that the set of nodes (social actors) remains constant over time. By contrast, we propose a framework that allows for models where both the set of nodes and the social ties connecting them change over time.  We depart from the conventional setup where the distribution of the vertex set is a point mass, and instead model its evolution via a stochastic process.  Our approach is modular, in the sense that joint distribution of the vertex sets over time can be modeled marginally and then the joint distribution of the edge sets can be specified, conditionally upon it. The conditional independence statements implied by our approach then mean that posterior sampling for the parameters corresponding to these factors (joint distribution of the vertex sets, joint distribution of the edge sets) can be performed separately. We illustrate our methodology via both simulation studies and data analysis. 
Joint work with Sofia Olhede and Patrick Wolfe.

10:30 to 11:30 Morning Coffee
11:30 to 12:00 Brendan Murphy
Latent Space Stochastic Block Model for Social Networks
A large number of statistical models have been proposed for social network analysis in recent years. In this paper, we propose a new model, the latent position stochastic block model, which extends and generalises both latent space model (Hoff et al., 2002) and stochastic block model (Nowicki and Snijders, 2001). The probability of an edge between two actors in a network depends on their respective class labels as well as latent positions in an unobserved latent space. The proposed model is capable of representing transitivity, clustering, as well as disassortative mixing. A Bayesian method with Markov chain Monte Carlo sampling is proposed for estimation of model parameters. Model selection is performed by directly estimating marginal likelihood for each model and models of different number of classes or dimensions of latent space can be compared. We apply the network model to one simulated network and two real social networks.
12:00 to 12:30 Konstantina Palla
A Bayesian nonparametric model for sparse dynamic networks
Co-authors: Francois Caron (Univ of OXford), Yee Whye Teh (Univ of Oxford)

We propose a Bayesian nonparametric prior for time-varying networks. To each node of the network is associated a positive parameter, modeling the sociability of that nodes. Sociabilities are assumed to evolve over time, and are modeled via a dynamic point process model. The model is able to (a) capture smooth evolution of the interactions between nodes, allowing edges to appear/disappear over time (b) capture long term evolution of the sociabilities of the nodes (c) and yields sparse graphs, where the number of edges grows subquadratically with the number of nodes. The evolution of the sociabilities is described by a tractable time-varying gamma process. We provide some theoretical insights into the model, describe a Hamiltonian Monte Carlo algorithm for efficieent exploration of the posterior distribution and present results on synthetic and real world dataset.
12:30 to 13:30 Lunch @ Wolfson Court
13:30 to 14:00 Tyler McCormick
Multiresolution network models
Social networks exhibit two key topological features: global sparsity and local density.  That is, overall the propensity for interaction between any two randomly selected actors is infinitesimal, but for any given individual there is massive variability in the propensity to interact with others in the network.  Further, the relevant scientific questions typically differ depending on the scale of analysis.  In this talk, we propose a class of multiresolution statistical models that model network structures on multiple scales to enable inference about relevant population-level parameters.  We capture global graph structure using a mixture over projective models that capture local graph structures. This approach is advantageous as it allows us to differentially invest modeling effort within subgraphs of high density, while maintaining a parsimonious structure between such subgraphs. We illustrate the utility of our method using simulation and data on household relations from Karnataka, India.  This is joint work with Bailey Fosdick (CSU) and Ted Westling (UW).  
14:00 to 14:30 Yee Whye Teh
Bayesian Hierarchical Community Discovery
Co-author: Charles Blundell (Google DeepMind)

We propose an efficient Bayesian nonparametric model for discovering hierarchical community structure in social networks. Our model is a tree-structured mixture of potentially exponentially many stochastic blockmodels. We describe a family of greedy agglomerative model selection algorithms whose worst case scales quadratically in the number of vertices of the network, but independent of the number of communities. Our algorithms are two orders of magnitude faster than the infinite relational model, achieving comparable or better accuracy.

Related Links
14:30 to 15:00 Daniel Roy
From Graphon to Graphex: Models and Estimators for Sparse Networks using Exchangeable Random Measures
A major challenge for Bayesian network analysis is that we lack general nonparametric models of sparse graphs. To meet this challenge, we introduce and study the general class of random graphs defined by the exchangeability of their real-valued vertex labels, an idea inspired by a model due to Caron and Fox. A straightforward adaptation of a result by Kallenberg yields a representation theorem: every such random graph is characterized by three (potentially random) components: a nonnegative real I, an integrable function S : R+ to R+, and a symmetric measurable function W: R+^2 to [0,1] that satisfies several weak integrability conditions. We call the triple (I,S,W) a graphex, in analogy to graphons, which characterize the (dense) exchangeable graphs on the naturals. I will present some results about the structure and consistent estimation of these random graphs. This is joint work with Victor Veitch.
15:00 to 16:00 Afternoon Tea
19:30 to 22:00 Formal Dinner at Emmanuel College
Wednesday 27th July 2016
09:30 to 10:00 Gesine Reinert
Estimating the number of communities in a network
Community detection has been a main topic in the analysis of networks. While there exist a range of powerful and flexible methods for dividing a network into a specified number of communities, it is an open question how to determine exactly how many communities one should use. We answer this question based on a combination of methods from Bayesian analysis and statistical physics. We demonstrate the approach on a range of real-world examples with known community structure, finding that it is able to determine the number of communities correctly in every case.  

This is joint work with Mark Newman (University of Michigan) 
10:00 to 10:30 Mike West
Bayesian dynamic modelling of network flows
I discuss Bayesian dynamic modelling for sequential analysis of network flow count data, linking two classes of models which allow fast, scalable and interpretable Bayesian inference. The first class involves sets of "decoupled" univariate state-space models for streaming count data, able to adaptively characterize and quantify network dynamics in real-time. These are then "recoupled" to define "emulation" of a second class of more structured, time-varying gravity models that allow closer and formal dissection of network dynamics and interactions among network nodes. Evolving internet flows on a defined network of web domains in e-commerce applications provide context, data and examples. Bayesian model monitoring theory defines a strategy for sequential model assessment and adaptation in cases of signaled departures of network flow data from model-based predictions.

This work builds on the more general concepts and strategy of "decouple/recouple" for Bayesian model emulation. That is, we use decoupled, parallel and scalable analyses of a set of simpler and computationally efficient univariate models, then recouple- on a sound theoretical basis- to rebuild the larger multivariate process for more formal inferences.

Co-authors: Xi Chen (Duke University), Kaoru Irie (University of Tokyo), David Banks (Duke University), Jewell Thomas (MaxPoint Interactive Inc.), and Rob Haslinger (The Sync Project).

10:30 to 11:30 Morning Coffee
11:30 to 12:00 Benjamin Bloem-Reddy
Random walk models of networks: modeling and inferring complex dependence
A signature of many network datasets is strong local dependence, a phenomenon that gives rise to frequently observed properties such as transitive triples, pendants, and structural heterogeneity. One difficulty in modeling such dependence is that the notion of locality may not be well-defined, and it is likely to be heterogeneous throughout the network. Furthermore, models that do not assume some form of conditional independence on the edges typically are intractable or too simplistic to serve as useful statistical models. We introduce a class of models, based on random walks, that allows the scale of dependence to vary; it is able to generate a range of network structures faithful to those observed in real data, and it admits tractable inference procedures.

This is joint work with Peter Orbanz.
12:00 to 12:30 Diana Cai
Edge-exchangeable graphs, sparsity, and power laws
Many popular network models rely on the assumption of (vertex) exchangeability, in which the distribution of the graph is invariant to relabelings of the vertices. However, the Aldous-Hoover theorem guarantees that these graphs are dense or empty with probability one, whereas many real-world graphs are sparse. We present an alternative notion of exchangeability for random graphs, which we call edge exchangeability, in which the distribution of a graph sequence is invariant to the order of the edges. We characterize the class of edge exchangeable models with a paintbox construction, and we demonstrate that edge-exchangeable models, unlike models that are traditionally vertex exchangeable, can exhibit sparsity and power laws. To do so, we outline a general framework for graph generative models; by contrast to the pioneering work of Caron and Fox (2014), models within our framework are stationary across steps of the graph sequence. In particular, our model grows the graph by instantiating more latent atoms of a single random measure as the dataset size increases, rather than adding new atoms to the measure.

Joint work with Trevor Campbell and Tamara Broderick.

12:30 to 13:30 Lunch @ Wolfson Court
14:00 to 14:30 Natalia Bochkina
Selection of the Regularization Parameter in Graphical Models using Network Characteristics
We study gene interaction networks using Gaussian graphical models that represent the underlying graph structure of conditional dependence between random variables determined by their partial correlation or precision matrix. In a high dimensional setting, the precision matrix is estimated using penalized likelihood by adding a penalization term which controls the amount of sparsity in the precision matrix and totally characterizes the complexity and structure of the graph. The most commonly used penalization term is the L1 norm of the precision matrix scaled by the regularization parameter which determines the tradeoff between sparsity of the graph and fit to the data. We propose several procedures to select the regularization parameter in the estimation of graphical models that focus on recovering reliably the appropriate network characteristic of the graph, and discuss their Bayesian interpretation. Performance is illustrated on simulated data as well as on colon tumor gene expression data. This work is extended to reconstructing a differential network between two paired groups of samples.    

This is joint work with with Adria Caballe Mestres (University of Edinburgh and Biomathematics and Statistics Scotland) and Claus Mayer (Biomathematics and Statistics Scotland).
14:30 to 15:00 Mikkel Schmidt
Inference in the infinite relational model
The infinite relational model and similar related non-parametric mixture models are very powerful for characterizing the structure in complex networks. But (approximate) inference can be challenging, especially for large networks, and both MCMC and variational inference is often hampered by local optima in the posterior distribution. These issues are discussed in the context of learning a high resolution parcellation of human brain structural connectivity network.
15:00 to 15:30 Sonia Petrone
On asymptotic exchangeability and graph evolution
Co-author: Sandra Fortini (Bocconi University, Milano)

Reinforced processes are of interest in probability and in many related fields, and as preferential attachment schemes in graph modeling. In this talk, I will discuss some classes of reinforced processes with a random reinforcement. Randomly reinforced processes allow to extend the spectrum of application, to incorporate non stationary evolution, competition, selection and other forms of asymmetry. I will present some underlying theory and limit properties, including asymptotic exchangeability, and potential applications as weighted preferential attachment schemes in graph modeling. An interesting aspect is that, depending on the random weights' structure, a sub-region of the sample space may tend to dominate, possibly explaining sparsity phenomena in exchangeable graphs.
15:30 to 16:30 Afternoon Tea
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons