Variational inference for the Stochastic Block Model

S. Robin

Description

Variational inference for the Stochastic Block-Model S. Robin AgroParisTech / INRA Workshop on Random Graphs, April 2011, Lille S. Robin (AgroParisTech / INRA) Variational inference for SBM Random Graphs, Lille 1 / 37

• stochastic block


• general setting


• variational inference


• latent variable


• models allow


• independent conditionally

Sujets

• Latent variable

Informations

• Publié par: profil-urra-2012
• Nombre de lectures: 11
• Langue: English

Extrait

Variational inference for the Stochastic Block-Model
S. Robin
AgroParisTech / INRA
Workshop on Random Graphs, April 2011, Lille
S. Robin (AgroParisTech / INRA) Variational inference for SBM Random Graphs, Lille 1 / 37Stochastic block model
Stochastic block model (SBM)
S. Robin (AgroParisTech / INRA) Variational inference for SBM Random Graphs, Lille 2 / 37Stochastic block model
Modelling network heterogeneity
Latent variable models allow to capture the underlying structure of a
network.
S. Robin (AgroParisTech / INRA) Variational inference for SBM Random Graphs, Lille 3 / 37Stochastic block model
Modelling network heterogeneity
Latent variable models allow to capture the underlying structure of a
network.
General setting for binary graphs (Bolloba´s et al. (2007)):
S. Robin (AgroParisTech / INRA) Variational inference for SBM Random Graphs, Lille 3 / 37Stochastic block model
Modelling network heterogeneity
Latent variable models allow to capture the underlying structure of a
network.
General setting for binary graphs (Bolloba´s et al. (2007)):
an latent (unobserved) variable Z is associated with each node:i
{Z} i.i.d. ∼ πi
the edges X are independent conditionally to the Z ’s:ij i
{X } independent|{Z} : X ∼B[γ(Z ,Z )]ij i ij i j
S. Robin (AgroParisTech / INRA) Variational inference for SBM Random Graphs, Lille 3 / 37Stochastic block model
Modelling network heterogeneity
Latent variable models allow to capture the underlying structure of a
network.
General setting for binary graphs (Bollob´as et al. (2007)):
an latent (unobserved) variable Z is associated with each node:i
{Z} i.i.d. ∼ πi
the edges X are independent conditionally to the Z ’s:ij i
{X } independent|{Z} : X ∼B[γ(Z ,Z )]ij i ij i j
Continuous (Hoff et al. (2002)): (' PCA)
d 0 0Z ∈R , logit[γ(z,z )] = a−|z−z|i
S. Robin (AgroParisTech / INRA) Variational inference for SBM Random Graphs, Lille 3 / 37Stochastic block model
Modelling network heterogeneity
Latent variable models allow to capture the underlying structure of a
network.
General setting for binary graphs (Bolloba´s et al. (2007)):
an latent (unobserved) variable Z is associated with each node:i
{Z} i.i.d. ∼ πi
the edges X are independent conditionally to the Z ’s:ij i
{X } independent|{Z} : X ∼B[γ(Z ,Z )]ij i ij i j
Continuous (Hoff et al. (2002)): (' PCA)
d 0 0Z ∈R , logit[γ(z,z )] = a−|z−z|i
Discrete (Nowicki and Snijders (2001)): (→ finite mixture = SBM)
Z ∈{1,...,K}, γ(k,`) = γ .i k`
S. Robin (AgroParisTech / INRA) Variational inference for SBM Random Graphs, Lille 3 / 37Stochastic block model
(Weighted) Stochastic Block-Model (SBM)
Discrete-valued latent labels: each node i belong to class k with
probability π :k
{Z} i.i.d., Z ∼M(1;π)i i i
where π = (π ,...π ).1 K
S. Robin (AgroParisTech / INRA) Variational inference for SBM Random Graphs, Lille 4 / 37Stochastic block model
(Weighted) Stochastic Block-Model (SBM)
Discrete-valued latent labels: each node i belong to class k with
probability π :k
{Z} i.i.d., Z ∼M(1;π)i i i
where π = (π ,...π ).1 K
Observed edges: {X } are conditionally independent given the Z ’s:ij i,j i
(X | Z = k,Z = `)∼ f (·)ij i j k`
where f (·) is some parametric distribution f (x) = f(x;γ ), e.g.k` k` k`
(X | Z = k,Z = `)∼B(γ ) (binary graph)ij i j k`
We denote γ ={γ } .k` k,`
S. Robin (AgroParisTech / INRA) Variational inference for SBM Random Graphs, Lille 4 / 37Stochastic block model
(Weighted) Stochastic Block-Model (SBM)
Discrete-valued latent labels: each node i belong to class k with
probability π :k
{Z} i.i.d., Z ∼M(1;π)i i i
where π = (π ,...π ).1 K
Observed edges: {X } are conditionally independent given the Z ’s:ij i,j i
(X | Z = k,Z = `)∼ f (·)ij i j k`
where f (·) is some parametric distribution f (x) = f(x;γ ), e.g.k` k` k`
(X | Z = k,Z = `)∼B(γ ) (binary graph)ij i j k`
We denote γ ={γ } .k` k,`
Statistical inference: We want to estimate
θ = (π,γ) and P(Z|X).
S. Robin (AgroParisTech / INRA) Variational inference for SBM Random Graphs, Lille 4 / 37