Bayesian methods for networks
Monday 25th July 2016 to Wednesday 27th 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 (University of Washington) 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 nonstandard 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 largescale dynamic networks will be presented. 
INI 1  
11:00 to 11:30  Morning Coffee  
11:30 to 12:00 
Alisa Kirichenko (Universiteit van Amsterdam) Function estimation on large graphs with missing data
Coauthor: 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. 
INI 1  
12:00 to 12:30 
Sergio Bacallado (University of Cambridge) Bayesian sequential design in matrix factorisation models
Coauthor: Annie Marsden (University of Cambridge)
Many problems in highdimensional statistics rely on lowrank 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 MultiArm Bandit problems. We present a simulation study supporting similar strategies in recommender systems. 
INI 1  
12:30 to 13:30  Lunch @ Wolfson Court  
13:30 to 14:00 
Harry Crane (Rutgers, The State University of New Jersey) 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 sizebiased 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. 
INI 1  
14:00 to 14:30 
Cameron Freer (Massachusetts Institute of Technology) Exchangeable constructions of countable structures
Coauthors: 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 AldousHooverKallenberg theorem and the theory of graph limits connect three kinds of objects: sequences of finite graphs, random countably infinite graphs, and certain continuumsized 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 twodimensional 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. 
INI 1  
14:30 to 15:30  Afternoon Tea  
15:30 to 16:00 
Lise Getoor (University of California, Santa Cruz) 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 multirelational and multimodel networks). In this talk, I will briefly review some SRL modeling techniques, and then I will introduce hingeloss Markov random fields (HLMRFs), a new kind of probabilistic graphical model that supports scalable collective inference from richly structured data. HLMRFs 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 HLMRFs highly scalable. Along the way, I will describe several successful applications of HLMRFs and I will describe probabilistic soft logic, a declarative language for defining HLMRFS.

INI 1  
16:00 to 16:30 
Nial Friel (University College Dublin) 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
contextindependent 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 modelchoice 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 realdata applications for the
stochastic block model and latent block model.
This is joint work with Riccardo Rastelli. 
INI 1  
16:30 to 17:30  Welcome Wine Reception 
09:00 to 09:30 
Adrian Raftery (University of Washington) Interlocking directorates in Irish companies using bipartite networks: a latent space approach
Coauthors: 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. 
INI 1  
09:30 to 10:00 
Pierre Latouche (Université Paris 1) 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, logistictype 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 Wgraph 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.

INI 1  
10:00 to 10:30 
Simon Lunagomez (University College London) 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. 
INI 1  
10:30 to 11:30  Morning Coffee  
11:30 to 12:00 
Brendan Murphy (University College Dublin) 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.

INI 1  
12:00 to 12:30 
Konstantina Palla (University of Oxford) A Bayesian nonparametric model for sparse dynamic networks
Coauthors: Francois Caron (Univ of OXford), Yee
Whye Teh (Univ of Oxford) We propose a Bayesian nonparametric prior for timevarying 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 timevarying 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. 
INI 1  
12:30 to 13:30  Lunch @ Wolfson Court  
13:30 to 14:00 
Tyler McCormick (University of Washington) 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 populationlevel 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).

INI 1  
14:00 to 14:30 
Yee Whye Teh (University of Oxford); (The Alan Turing Institute) Bayesian Hierarchical Community Discovery
Coauthor: Charles Blundell (Google DeepMind) We propose an efficient Bayesian nonparametric model for discovering hierarchical community structure in social networks. Our model is a treestructured 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 
INI 1  
14:30 to 15:00 
Daniel Roy (University of Toronto) 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 realvalued 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.

INI 1  
15:00 to 16:00  Afternoon Tea  
19:30 to 22:00  Formal Dinner at Emmanuel College 
09:30 to 10:00 
Gesine Reinert (University of Oxford) 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 realworld
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) 
INI 1  
10:00 to 10:30 
Mike West (Duke University) 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 statespace models for streaming count data, able to adaptively
characterize and quantify network dynamics in realtime. These are then "recoupled" to define
"emulation" of a second class of more structured, timevarying 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 ecommerce 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 modelbased 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. Coauthors: Xi Chen (Duke University), Kaoru Irie (University of Tokyo), David Banks (Duke University), Jewell Thomas (MaxPoint Interactive Inc.), and Rob Haslinger (The Sync Project). 
INI 1  
10:30 to 11:30  Morning Coffee  
11:30 to 12:00 
Benjamin BloemReddy (Columbia University) 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 welldefined, 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. 
INI 1  
12:00 to 12:30 
Diana Cai (University of Chicago) Edgeexchangeable 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 AldousHoover theorem guarantees that these graphs are dense or empty with probability one, whereas many realworld 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 edgeexchangeable 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. 
INI 1  
12:30 to 13:30  Lunch @ Wolfson Court  
14:00 to 14:30 
Natalia Bochkina (University of Edinburgh) 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). 
INI 1  
14:30 to 15:00 
Mikkel Schmidt (Technical University of Denmark) Inference in the infinite relational model
The infinite relational model and similar related nonparametric 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.

INI 1  
15:00 to 15:30 
Sonia Petrone (Bocconi University) On asymptotic exchangeability and graph evolution
Coauthor: 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 subregion of the sample space may tend to dominate, possibly explaining sparsity phenomena in exchangeable graphs. 
INI 1  
15:30 to 16:30  Afternoon Tea 