


Talks
Morteza Alamgir  MPI for Intelligent Systems
http://www.kyb.mpg.de/~morteza


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 pheat
diffusion, pharmonic function, pLaplacian 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.




Demian Battaglia  MPI for Dynamics and Self Organization
http://www.nld.ds.mpg.de/~demian


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
naturallyemerging 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 brainwide synchronization of neural
oscillations, due to growing experimental evidence for its function in perception, attention or
intercircuit coordination.
Here we investigate the role played by dynamic longrange
synchronization in the flexible control of interareal causal
influences in different "brain states", given that anatomic
interareal 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 selforganization
of interacting "analog" firing rate oscillations allows to flexibly
route streams of "digitallike" information encoded in complex
spiking patterns.
Reference: Battaglia D., Witt A., Wolf F., Geisel T. (2012) Dynamic effective
connectivity of interareal brain circuits, PLoS Comp Bio 8(3):e1002438




Michel Besserve  MPI for Intelligent Systems
http://people.kyb.tuebingen.mpg.de/besserve/


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.




Felix Biessmann  TU Berlin
http://www.user.tuberlin.de/felix.biessmann/


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 BagofWord (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 twittersphere b) where and c) when it reaches it maximal
impact.
 


Francesco Bonchi  Yahoo Research Barcelona
http://www.francescobonchi.com


A DataBased 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
databased 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.




Benjamin Doerr  MPI for Informatics
http://www.mpiinf.mpg.de/~doerr/


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 realworld
network model (as opposed to complete topologies, hypercubes,
ErdosRenyi 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.




Manuel Gomez Rodriguez  MPI for Intelligent Systems
http://www.stanford.edu/~manuelgr/


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 ongoing news events. Clusters of news media sites and blogs often emerge and vanish in
matter of days for ongoing 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.




Krishna P. Gummadi  MPI Software Systems
http://www.mpisws.org/~gummadi


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 realworld groups in large
social networks can be detected automatically remains unclear.
In this talk, we address this problem by gathering "ground truth"
data about realworld 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 1hop) 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.




Isabelle Guyon  ClopiNet
http://clopinet.com/isabelle/


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 nongovernmental 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.




Navid Hassanpour  Yale University
http://pantheon.yale.edu/~nh255


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 largescale 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
riskaverse 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.




Dominik Janzing  MPI for Intelligent Systems
http://www.kyb.mpg.de/~janzing


Causal inference using nonstatistical 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
noneffects, given its direct causes. However, causal conclusions in everyday 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 nonstatistical 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, Kolmogorovcomplexity 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 additivenoisebased causal discovery via algorithmic information theory,
OSID 2010.




Masahiro Kimura  Ryukoku University
http://www.elec.ryukoku.ac.jp/~kimura


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 valueweighted
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 antimajority opinionists by the
valueweighted mixture voter (VwMV) model which combines the VwV
and the antivoter 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.




David LibenNowell  Carleton Collegue
http://cs.carleton.edu/faculty/dlibenno


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
largescale 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 smallworld epidemic, but rather produce a narrow but very deep treelike
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.




Gabor Lugosi  UPF
http://www.econ.upf.edu/~lugosi/pubs.html


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.




Jonas Peters  ETZH
http://www.kyb.mpg.de/nc/employee/details/jpeters.html


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
nonGaussian 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 nonlinear
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.




Peter Spirtes  CMU
http://www.hss.cmu.edu/philosophy/facultyspirtes.php


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 misspecified, 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
nonlinear dependencies among latent variables, or linear relationships
among nonGaussian 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
nonlinearities and nonGaussian 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.




Bernhard Schoelkopf  MPI for Intelligent Systems
http://www.kyb.mpg.de/~bs


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 semisupervised 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
semisupervised learning can help, and corroborate it with empirical results.




Ricardo Silva  UCL
http://www.homepages.ucl.ac.uk/~ucgtrbd


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 YW Teh (2011). Mixed Cumulative Distribution Networks. 14th
AISTATS.
[2] R. Silva (2012). Latent Composite Likelihood Learning for the
Structured Canonical Correlation Model. 28th UAI.




Le Song  Georgia Tech
http://www.cc.gatech.edu/~lsong


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 kernelbased 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.




John Winn  Microsoft Research Cambridge
http://research.microsoft.com/enus/people/jwinn/


Gated graphs and causal inference
(slides) Sept 4, 2012 17:30  18:15
Bayesian networks and factor graphs cannot represent
contextspecific 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 generalpurpose
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 dseparation 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 contextspecific 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 docalculus arise from testing dseparation 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 contextspecific independencies
are explicitly represented.




Kun Zhang  MPI for Intelligent Systems
http://www.kyb.mpg.de/nc/employee/details/kzhang.html


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 nonexperimental 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 postnonlinear (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.






