Label Propagation with Random Walk
Sept 5, 2012 10:30 - 11:15

The heat diffusion is a popular model that inspires a family of methods for the problem of label propagation on graphs. It brings a tight relation to the random walk and harmonic functions on graphs, graph Laplacian and also gives a natural distance between graph vertices. We study this model in the family of random geometric graphs and show different aspects from shortcoming of this method in geometric graphs. Then we talk about the extension of these results to the p-heat diffusion, p-harmonic function, p-Laplacian operator and a graph distance induced by them. In particular we show that for different range of p, the corresponding graph distance shows several interesting properties. At the end we propose an underlying random walk model for this process.

Dynamic information routing in neuronal networks of the brain
Sept 4, 2012 9:00 - 9:45

Flexible transmission of information is a core feature of many biological systems. The timing of the exchanged signals is decisive for the correct routing of information through complex interaction networks. A naturally-emerging mechanism which is fit to temporally coordinate the transmission of information might be oscillatory synchronization, which can arise whenever the intrinsic dynamics of network nodes undergo cyclical fluctuations. Sustained interest has been raised in particular by local to brain-wide synchronization of neural oscillations, due to growing experimental evidence for its function in perception, attention or inter-circuit coordination.

Here we investigate the role played by dynamic long-range synchronization in the flexible control of inter-areal causal influences in different "brain states", given that anatomic inter-areal connections can be considered as fixed, on timescales relevant for behavior. We show that, thanks to the nonlinear interaction between brain rhythms, even simple modular circuits involving few interconnected local circuits (or "brain areas") can originate a multitude of effective circuits associated with alternative functions selectable "on demand'". Precisely timed (endogeneous or exogenous) inputs can be used to induce reliably controlled switching between effective circuits.

We furthermore demonstrate that different effective circuits enact alternative modalities of information routing between nodes of the underlying fixed structural circuit. Interestingly, the spiking of individual neurons can be very irregular even when the collective rate oscillations are regular. We show then that the self-organization of interacting "analog" firing rate oscillations allows to flexibly route streams of "digital-like" information encoded in complex spiking patterns.

Reference: Battaglia D., Witt A., Wolf F., Geisel T. (2012) Dynamic effective connectivity of inter-areal brain circuits, PLoS Comp Bio 8(3):e1002438

Assessing the organization of functional brain networks
Sept 4, 2012 9:45 - 10:30

Brain networks are characterized by strong recurrence and widespread connectivity. As a consequence it is inherently difficult to understand how information processing is distributed among the large number of brain structures. In this context, graph theoretic tools are a way to quantify the most prominent aspects of this organization.

In this work, we estimated functional network connectivity from functional Magnetic Resonance Imaging (fMRI) signals by computing statistical dependency measures between time series recorded in each part of the brain at a millimeter resolution. Then, assuming that a restricted set of core regions relaying information to the whole network, we identified the most important structures of this high dimensional network using the concept of eigenvector centrality. Further graph theoretic analysis based on random walk theory enabled to cluster these regions in robust groups having dedicated subnetworks of influence and to identify their hierarchical organization.

Graph theoretic concepts enables to synthetize the complex organization of brain functional networks around a restricted set of core regions. This mapping can be used by neuroscientists to understand brain dynamics at a system level.

Canonical Trend Analysis for Social Networks (slides)
Sept 6, 2012 9:30 - 10:15

Social network analysis can be used to assess the impact of information published on the web. The spatiotemporal dynamics of the impact a certain web source has can be of particular interest. Here we propose an simple but efficient approach to estimate the spatiotemporal impact profile of web sources on a social network. In an application example we extract Bag-of-Word (BoW) features from news articles and collected all twitter replies to each article. For each twitter reply we extracted geospatial and temporal information. We then compute the multivariate spatiotemporal response pattern of all twitter replies to a given web source. The result can be interpreted with respect to a) how much impact a certain web source has on the twitter-sphere b) where and c) when it reaches it maximal impact.

A Data-Based Approach to Social Influence Maximization
Sept 3, 2012 11:15 - 12:00

Influence maximization is the problem of finding a set of users in a social network, such that by targeting this set, one maximizes the expected spread of influence in the network. Most of the literature on this topic has focused exclusively on the social graph, overlooking historical data, i.e., traces of past action propagations. In this talk, we present a novel data-based perspective over the influence maximization problem. In particular, we introduce a new model, which we call credit distribution, that directly leverages available propagation traces to learn how influence flows in the network and uses this to estimate expected influence spread. Our approach also learns the different levels of influenceability of users, and it is time aware in the sense that it takes the temporal nature of influence into account. We present an approximation algorithm for solving the influence maximization problem that at once enjoys high accuracy compared to the standard approach, while being several orders of magnitude faster and more scalable.

Rumor Spreading in Social Networks (slides)
Sept 3, 2012 9:00 - 9:45

We study the classic randomized rumor spreading process in the preferential attachment graph model suggested by Barabasi and Albert. This is the first time such an analysis is done for a real-world network model (as opposed to complete topologies, hypercubes, Erdos-Renyi random graphs, etc.).

In the synchronized rumor spreading model, where in each time step each node calls a random neighbor, with high probability it takes only a logarithmic number of steps until a piece of information is disseminated to all nodes of the preferential attachment network. Surprisingly, if the random choice of the neighbors is done excluding the one previously called, the dissemination time reduces to O(log(n) / loglog(n)), which is the diameter of these graphs.

We also analyze an asynchronous rumor spreading model, where nodes call their neighbors at random times given by a Poisson process with rate one (hence again in average each node does one call per unit of time). We prove that the dissemination time now is at most O((log n)^(1/2)).

All these results give a theoretical justification for the often observed fast spread of information in social networks.

These results are joint work with Mahmoud Fouz and Tobias Friedrich.

Structure and Dynamics of Information Pathways in Online Media
Sept 4, 2012 11:15 - 12:00

Diffusion of information, spread of rumors and infectious diseases are all instances of stochastic processes that occur over the edges of an underlying network. Many times networks over which contagions spread are unobserved and need to be inferred from the diffusion data. Moreover, such networks are often dynamic and change over time.

We investigate the problem of inferring static and dynamic networks based on information diffusion data. We assume there is an unobserved network that may change over time, while we observe the results of a dynamic process spreading over the edges of the network. The task then is to infer the edges and the dynamics of the underlying network.

We develop an algorithm that relies on stochastic convex optimization to efficiently solve the static and the dynamic network inference problem. We apply our algorithm to information diffusion among 3.3 million mainstream media and blog sites and experiment with more than 179 million different pieces of information spreading over the network in a one year period. We study the evolution of information pathways in the online media space and find that information pathways for general recurrent topics are more stable across time than for on-going news events. Clusters of news media sites and blogs often emerge and vanish in matter of days for on-going news events. Major events involving civil population, such as the Libyan's civil war or Syria's uprise, lead to an increased amount of information pathways among blogs as well as in the overall increase in the network centrality of blogs and social media sites.

Joint work with Jure Leskovec, David Balduzzi and Bernhard Schoelkopf.

All Group Detection is Local: Analysing Detectability of Groups in Large Social Networks (slides)
Sept 6, 2012 10:15 - 11:00

A lot of recent research has focused on the problem of automatically detecting user groups that are meaningful clustering of users in social networks. Many of these approaches rely on detecting network communities, which are subgraphs in the network graph whose nodes are more tightly connected between themselves than to the rest of the network. Despite a large body of prior research on detecting communities, the extent to which arbitrary real-world groups in large social networks can be detected automatically remains unclear.

In this talk, we address this problem by gathering "ground truth" data about real-world groups in large social networks and analyzing their structural properties. Our analysis reveals that most user groups in large social networks do not form communities. Individual members of a group often have a large number of external links to nodes outsides the group making it impossibly hard to distinguish group members from the rest of the network. However, we discover that when we limit the graph to a local (say 1-hop) network neighborhood, group members lying within the neighborhood constitute a strong community as external links to nodes outside the local neighborhood are pruned. Our finding that most detectable groups are local has important implications for detecting groups and communities in large social networks.

Can causal models be evaluated? (slides)
Sept 5, 2012 16:00 - 16:45

Many problems can be formulated as finding a small set of factors, which influence significantly an outcome of interest. For instance, in heath care, nutritional and environmental factors may influence life expectancy; in epidemiology, geographic and societal factors may influence the spread of a disease; in economy, growth factors may influence unemployment; in social sciences, educational factors may influence criminality or wealth; in ecology, pollution factors may influence climate changes, etc. With the increasing number of databases made available by governments and non-governmental agencies, data scientist have the opportunity to discover candidate causal relationships and influence further research, which may ultimately lead to new policies. Superficially, this problem resembles a machine learning problem of variable selection. However, not all variable predictive of a given outcome are useful to induce changes in this outcome: causes can; effects or confounders (consequences of a common cause) cannot. Experimentation is the ultimate method of validation of causal relationships (considered by many scientist to be the only valid one). However, experiments are often costly, unethical, or impossible. Hence the importance of evaluating causal models by other means. In this presentation, we will take the point of view of a challenge organizer, which is similar to the point of view of a customer or a government agency seeking guarantees of model quality before investing in experimentation. We will examine methods of causal model evaluation not requiring any knowledge of the causal discovery algorithms used nor any experimentation, making use of available observational data, data simulators, partial prior knowledge, artificial distractor variables, data missing by design (occluded), and other artifacts.

A Dynamic Threshold Model of Collective Action in Social Networks (slides)
Sept 5, 2012 11:45 - 12:30

Recent uprisings in the Middle East pose a pressing question: howcan local organization networks facilitate large-scale collective action? To answer this question we propose a formalization of a threshold model for participation in collective action in networks, which takes both the network structure and belief updating into account. We solve the dynamic equations for action and belief updating in the context of canonical network structures, i.e. fully connected, star, ring, and path graphs. Using these solutions we demonstrate that full connectivity in a social network can hinder collective action. We find radius of action diffusion in networks in which a radical minority is mobilizing a risk-averse majority. We also explore extensions of the model to geometric random graphs and infinite grids, and examine the solutions to a variety of learning dynamics in the context of the aforementioned graphs.

Joint work with Ji Liu and Sekhar Tatikonda.

Causal inference using non-statistical information
Sept 3, 2012 16:45 - 17:30

The Causal Markov Condition employs statistical dependences among n random variables for inferring the underlying causal structure, formalized as a directed acyclic graph (DAG) or parts of it. It postulates conditional independence between every variable and its non-effects, given its direct causes. However, causal conclusions in every-day life are usually not based on statistical data analysis. Instead, we even infer causal links among single objects: Significant similarities between two texts or images, for instance, indicate that one author or artist has copied from the other, or that both have been influenced by common third party material. In such cases it is not clear how to interpret the observed similarities as statistical dependences of appropriate random variables. We argue that there is no need for such an interpretation because conditional independences can also be defined for non-statistical information measures, provided that they satisfy a certain submodularity condition [2]. Examples of such measures are Kolmogorov complexity [1], compression length after applying some existing data compression schemes, or number of elements in a set. Wether or not the Causal Markov Condition with respect to such a generalized information measure is a reasonable postulate, depends on the class of causal mechanisms under consideration. Our work suggests that Kolmogorov complexity puts almost no restrictions to the mechanisms, while others are only applicable to specific domains. Remarkably, Kolmogorov-complexity based causal inference also implies new principles for causal inference from statistical data [3].

[1] D. Janzing and B. Schoelkopf: Causal inference using the algorithmic Markov condition, IEEE TIT 2010.
[2] B. Steudel, D. Janzing, B. Schoelkopf: Causal Markov condition for submodular information measures, COLT 2010.
[3] D. Janzing and B. Steudel: Justifying additive-noise-based causal discovery via algorithmic information theory, OSID 2010.

Opinion Formation by Voter Models in Social Networks (slides)
Sept 3, 2012 12:00 - 12:45

Large scale social networking applications have made it possible for news, ideas, opinions and rumors to spread easily, which affects and changes our daily life style substantially. Massive data are constantly being produced and are made available to us, enabling the study of the spread of influence in social networks. Much of the work has treated information as one entity and nodes in the network are either active (influenced) or inactive (uninfluenced), i.e., there are only two states. In this work, we address a different type of information diffusion, which is ``opinion formation'', i.e., spread of opinions. This requires a model that handles multiple states. Since each opinion (what is said) has its own value and an opinion with a higher value propagates more easily/rapidly, we first extend the basic voter model to be able to handle multiple opinions, and incorporate the value for each opinion. We call this model the value-weighted voter (VwV) model, and investigate the problem of detecting the change in opinion share caused by an unknown external situation change under the VwV model with multiple opinions in a retrospective setting. Next, we investigate the problem of how different opinions with different values spread over a social network under the presence of anti-majority opinionists by the value-weighted mixture voter (VwMV) model which combines the VwV and the anti-voter models both with multiple opinions. We also analyze an extension of the basic voter model that incorporates the strength of each node (who says), which is modeled as a function of the node attributes.

Patterns of Information Diffusion (slides)
Sept 3, 2012 9:00 - 9:45

Most memes (information, jokes, and opinions) do not spread widely through the global social network -- but we do regularly observe certain memes that propagate extremely broadly. Still, the actual mechanics of how any single piece of information spreads on a global scale have largely remained mysterious. A major challenge lies in the difficulty of acquisition of large-scale data recording the diffusion of any particular single piece of information. This talk will focus on recent work, joint with Jon Kleinberg and Flavio Chierichetti, tracing such processes through online traces of information spreading. I will concentrate on the reconstruction of the propagation of massively circulated Internet chain letters, like one opposing the start of the Iraq war. These petitions do not fan out rapidly in the style of a small-world epidemic, but rather produce a narrow but very deep tree-like pattern. I will discuss these empirical observations and some mathematical models created to try to reproduce them.

Joint work with Jon Kleinberg and and Flavio Chierichetti.

Connectivity of random irrigation graphs (slides)
Sept 5, 2012 9:00 - 9:45

We study connectivity properties of the following random geometric graph model, called "irrigation networks" or "Bluetooth graphs". The graph has two parameters: r>0 and a positive integer c. The vertices of the graph are given by n random uniform points in [0,1]^d. First form a random geometric graph by connecting those pairs of points whose Euclidean distance is at most r. Then each vertex selects c of its neighbors uniformly at random without replacement. We obtain various conditions for values of the parameters r and c for which the obtained irrigation graph is connected, with high probability.

The talk is based on joint work with Nicolas Broutin, Lud Devroye, and Nicolas Fraiman.

Identifiability of Restricted Structural Equation Models (slides)
Sept 3, 2012 18:15 - 19:00

We consider structural equation models (SEMs) in which variables can be written as a function of their parents and noise terms (the latter are assumed to be jointly independent). Corresponding to each SEM, there is a directed acyclic graph (DAG) G_0 describing the relationships between the variables. In Gaussian SEMs with linear functions, the graph can be identified from the joint distribution only up to Markov equivalence classes (assuming faithfulness). It has been shown, however, that this constitutes an exceptional case. In the case of linear functions and non-Gaussian noise, the DAG becomes identifiable. In this work we present two alternative directions of deviating from the general linear Gaussian case: (i) apart from few exceptions identifiability also holds for non-linear functions and arbitrarily distributed additive noise. And (ii), if we require all noise variables to have the same variances, again, the DAG can be recovered from the joint distribution. Our results can be applied to the problem of causal inference. If the data follow one of the two model assumptions and given that all variables are observed, the causal structure can be inferred from observational data only. We present practical methods for solving this task.

Causal Clustering of Variables with Multiple Latent Causes (slides)
Sept 4, 2012 16:00 - 16:45

When scientists are interested in knowing the values of, or inferring causal relations between variables that they cannot directly measure, they typically record several survey or test items that are thought to be indicators of latent variables of interest, e.g. math ability or impulsiveness. Although it is rare that a latent variable is measured perfectly by any single indicator, estimates of the latent variables, and their associations with other latents, can be obtained by employing multiple indicators for each latent variable (multiple indicator models). If the multiple indicator model is correctly specified, then in a wide range of cases the estimates obtained are consistent and have desirable statistical properties, and these estimates can be used to search for causal models among the latents. If the model is mis-specified, then estimators are typically biased.

A number of problems make it difficult to find a correctly specified measurement model: a) associations among items are often confounded by additional unknown latent common causes, b) there are often a plethora of alternative models that are consistent with the data and with the prior knowledge of domain experts, c) there may be non-linear dependencies among latent variables, or linear relationships among non-Gaussian latent variables, and d) there may be feedback relationships among latent variables. This work will generalize previous work by Silva, et al., 2006 in JMLR in a way that overcomes many of these difficulties. In particular, I will sketch an outline to an approach that leverages algebraic work by Sullivant et al. (2010) in the Annals of Statistics that allows for models with several latent factors underlying each pair of items, that involve non-linearities and non-Gaussian variables (in parts of the model), and that involve feedback between latent variables of interest; I will also describe what the open problems for this approach are.

Causal and Anticausal Learning
Sept 3, 2012 16:00 - 16:45

We consider the problem of function estimation in the case where an underlying causal model can be identified. This has implications for popular scenarios such as covariate shift, concept drift, transfer learning and semi-supervised learning. We argue that causal knowledge may facilitate some approaches for a given problem, and rule out others. In particular, we formulate a hypothesis for when semi-supervised learning can help, and corroborate it with empirical results.

Representation and learning in directed mixed graph models (slides)
Sept 5, 2012 18:15 - 19:00

Directed mixed graph models encode independences arising from symmetric and asymmetric relationships. One motivation is to represent causal structures among a selected set of variables in a system where: i. asymmetry is a result of causal ordering; ii. symmetric dependencies are a result of unmeasured confounding. There are difficulties associated on constructing multivariate distributions following such independence models, such as the computational cost of estimation and the potential explosion in the number of parameters. We introduce an approach that integrates copula models and the combination of density functions with cumulative distributions in order to construct a tractable family of mixed graph models [1]. We also discuss approaches based on composite likelihood estimation for learning the structure of such models when some variables are unobserved, avoiding potentially expensive Markov chain Monte Carlo schemes [2].

[1] R. Silva, C. Blundell and Y-W Teh (2011). Mixed Cumulative Distribution Networks. 14th AISTATS.

[2] R. Silva (2012). Latent Composite Likelihood Learning for the Structured Canonical Correlation Model. 28th UAI.

Learning Networks of Heterogeneous Influence (slides)
Sept 4, 2012 12:00 - 12:45

Information, disease, and influence diffuse over networks of entities in both natural systems and human society. Analyzing these transmission networks plays an important role in understanding the diffusion processes and predicting future events. However, the underlying transmission networks are often hidden and incomplete, and we observe only the time stamps when cascades of events happen. In this paper, we address the challenging problem of uncovering the hidden network only from the cascades. The structure discovery problem is complicated by the fact that the influence among different entities in a network is heterogeneous, which can not be described by a simple parametric model. Therefore, we propose a kernel-based method which can capture a diverse range of different types of influence without any prior assumption. In both synthetic and real cascade data, we show that our model can better recover the underlying diffusion network and drastically improve the estimation of the transmission functions between networked entities.

Gated graphs and causal inference (slides)
Sept 4, 2012 17:30 - 18:15

Bayesian networks and factor graphs cannot represent context-specific independencies, that is, structure in the model which is present only when another variable has a particular value. For example, even the structure of a mixture model is lost when represented using such graphical models. Gates are general-purpose graphical structures that extend existing graphical models to allow such context- specific independencies to be represented. Gates have been used to represent mixtures, to do model comparison and to learn model structure, all within a single graphical model. Such gated graphical models are amenable to extended forms of standard inference algorithms, such as belief propagation and variational message passing. In addition, gated graphs allow an extended definition of d-separation that can detect a richer set of independencies than if the same model were represented without gates.
Causal inference involves predicting the effect of an intervention on a variable. This requires the ability to model context-specific independence because, in the context of an intervention, the normal structure between a variable and its parents is switched off. In this talk, I will describe how gated graphs can be used to model interventions. This use of gated graphs leads to many interesting results:
- The rules of do-calculus arise from testing d-separation in the gated graph,
- Causal inference can be achieved using probabilistic inference alone,
- Causal structure can be discovered using Bayesian model comparison alone.
These results show that, far from being separate from probabilistic reasoning, causal reasoning is in fact a special case of probabilistic inference - but in a model where context-specific independencies are explicitly represented.

Functional causal models: Beyond linear instantaneous relations
Sept 5, 2012 16:45 - 17:30

Functional causal models have served as one of the standard approaches for causal discovery from non-experimental data. We start with relating functional causal models to the invariance of the conditional distribution, and then discuss the conditions, benefits, and cautions of using this approach. After introducing a fundamental functional causal model, namely, the linear, nongaussian, and acyclic model (LiNGAM), we focus on two more practical models: Granger causality with instantaneous effects and the post-nonlinear (PNL) causal model. The former is an extension of the traditional Granger causality to incorporate the linear instantaneous causal relations, or equivalently, is a linear functional causal model with certain temporal constraints, and it can be efficiently estimated from data. The latter takes into account the nonlinear effect of the cause, the inner noise effect, and possible measurement distortion in the effect; we show its identifiability, its application in distinguishing cause from effect, and how to extend it to the case of many variables.