\begin{figure}
\centering
\label{fig:graphical}
\includegraphics[scale=.8]{graphical.pdf}
\caption{Graphical model representation of the Network Inference Problem in the
  case of a Gaussian product prior, with edge weights $\theta_{ij}$, observed
cascade indicator vectors $X^c_t$, edge prior parameters $\mu_{ij}$ and
$\sigma_{ij}$. The source distribution, parameterized by $\phi$, is considered
fixed here.}
\end{figure}

In this section, we develop a Bayesian approach to the Network Inference Problem
by placing priors on the edge weights of the graph. The quantity of interest is
the posterior distribution, given through Bayes' rule by:
\begin{equation}
  \label{eq:bayesrule}
  \Theta | \bx \propto \text{prior}(\Theta) \times \mathcal{L}_\Theta(\bx)
\end{equation}
where $\mathcal{L}_\Theta(\bx)$ is the likelihood expressed in
Eq.~\ref{eq:dist}.

\subsection{Advantages for Graph inference}

One advantage of the Bayesian approach is its ability to convey distributional
information about our belief of each parameter rather than the pointwise
estimates accessible by MLE.~For example, exploring the entropy of the
posterior on each parameter allows us to quantify the uncertainty on edge
weights. In the next section, we will exploit this information to improve the
rate at which we decrease the uncertainty (and hence learn the network) by
focusing on the most relevant parts of the network.

Another advantage of the Bayesian approach is the ability to encode
domain-knowledge through well-chosen prior distributions. For example, there is
an extensive literature~\cite{} on parametric representations of social
networks, which attempt to reproduce observed properties of such networks:
density of triangles, diameter, degree distribution, clustering coefficient
etc.  Accounting for known graph properties, such as reciprocal links or the
high density of triangles has the potential to greatly increase the information
we extract from each cascade.  Of course, such priors no longer allow us to
perform inference in parallel, which was leveraged in prior work.

\subsection{Inference}

Depending on the link function $f$, the GLC model may not possess conjugate
priors (this is for example the case in the IC model). Even if conjugate priors
exist, they may be restricted to product form. In these cases, we resort to the
use of sampling algorithms (MCMC) and approximate Bayesian methods (variational
inference), which we cover here.

\paragraph{MCMC.}
The Metropolis-Hastings (MCMC) algorithm allows us to draw samples from the
posterior directly using the un-normalized posterior distribution. The
advantage of this method is the ability to sample from the exact posterior and
the wide availability of software packages which will work `out-of-the-box'.
However, as we show in our experiments, vanilla MCMC scales badly and is
unsuitable for Bayesian learning of large networks ($\geq 100$ nodes).

\paragraph{Variational Inference.}

Variational inference algorithms consist in fitting an approximate family of
distributions to the exact posterior. The variational objective can be
decomposed as a sum between a divergence term with the prior and a likelihood
term:
\begin{equation}
  \begin{split}
    \mathcal{V}(\mathbf{\Theta}, \mathbf{\Theta'}, \{\mathbf{x}_c\}) =  &-
    \text{KL}(q_{\mathbf{\Theta'}}, p_{\mathbf{\Theta}}) \\ &+ \sum_{c = 1}^C
    \E_{q_{\mathbf{\Theta'}}} \log \mathcal{L}(\mathbf{x}_c | \mathbf{\Theta})
  \end{split}
\end{equation}

where $p_{\mathbf{\Theta}}$ is the prior distribution, parametrized by prior
parameters $\Theta = (\mathbf{\mu}^0 , \mathbf{\sigma}^0)$,
$q_{\mathbf{\Theta'}}$ is the approximate posterior distribution, parametrized
by variational parameters $\Theta' = (\mathbf{\mu}, \mathbf{\sigma})$,
$\log \mathcal{L}(x | \Theta)$ is the log-likelihood as written in
Eq.~\ref{eq:dist}, and $\text{KL}(p , q)$ is the Kullback-Leibler divergence
between distributions $p$ and $q$. The variational objective maximizes a lower
bound on the log marginal likelihood:
\begin{equation}
  \max_{\mathbf{\Theta'}} \mathcal{V}(\mathbf{\Theta}, \mathbf{\Theta'},
  \{\mathbf{x}_c\}) \leq \log p_\Theta(\{ \mathbf{x}_c\})
\end{equation}

\emph{Computational considerations.} Contrary to MCMC which outputs samples
from the exact posterior given all observed data. Optimizing the variational
inference objective is amenable to batch learning. For example, when using
Stochastic Gradient Descent (SGD), the observations can be processed one at
a time to incrementally approximate the posterior, thus improving scalability.
In many cases, however, the expectation term cannot be found in closed-form,
and approximation by sampling does not scale well with the number of
parameters. In those cases, we can borrow ideas from Bohning~\cite{} to propose
a linear/quadratic approximation to the log-likelihood for which the
expectation term can be written and analytically and efficiently optimized.

\subsection{Example}
\label{sec:example}
We develop the Variational Inference algorithm for the IC model (cf.
Section~\ref{sec:model}).  As mentioned above, the IC model with link function
$f: z \mapsto 1 - e^{-z}$ has no conjugate priors. We consider here a truncated
product gaussian prior:
\begin{equation}
  \label{eq:gaussianprior}
  \text{prior}(\Theta) = \prod_{ij} \mathcal{N}^+(\theta_{ij} | \mu_{ij},
  \sigma_{ij})
\end{equation}
where $\mathcal{N}^+(\cdot)$ is a gaussian truncated to lied on $\mathbb{R}^+$
since $\Theta$ is a transformed parameter $z \mapsto -\log(1 - z)$. This model
is represented in the graphical model of Figure~\ref{fig:graphical}.

The product-form of the prior implies that the KL term is entirely decomposable.
Since an easy closed-form formula exists for the KL divergence between two
gaussians, we approximate the truncated gaussians by their non-truncated
counterpart.
\begin{equation}
  \label{eq:kl}
  \begin{split}
    \text{KL}(q_{\mathbf{\Theta'}}, p_{\mathbf{\Theta}}) &= \sum_{ij}
  KL\left(\mathcal{N}^+(\mu_{ij}, \sigma_{ij}), \mathcal{N}^+(\mu^0_{ij},
  \sigma^0_{ij})\right) \\
  &\approx \sum_{ij}  \log \frac{\sigma^0_{ij}}{\sigma_{ij}} +
  \frac{\sigma^2_{ij} + {(\mu_{ij} - \mu_{ij}^0)}^2}{2{(\sigma^0_{ij})}^2}
  \end{split}
\end{equation}

Once again, the product form of the prior allows us to decompose the expected
log-likelihood term as such:
\begin{equation}
  \begin{split}
    &\mathbb{E}_{q_{\mathbf{\Theta'}}} \log \mathcal{L}(\mathbf{x}_c |
    \mathbf{\Theta}) = - \sum_{j,c , t } \mu_j \cdot x^t_c \\
    &+ \sum_{j, c, t} \mathbb{E}_{\theta_j \sim\mathcal{N}(\vec 0_n, I_n)}
    \left[ (x_c^{t+1})_j \log \left(1 - e^{-(\sigma_j \cdot \theta_j + \mu_j)
    \cdot x_c^t}\right) \right]
  \end{split}
\end{equation}

Note that by reparametrizing $\theta_j' = \sigma_j \cdot \theta_j + \mu_j$,
where $\sigma_j \cdot \theta_j$ is the elementwise multiplication operation, we
can easily compute the gradient of the variational objective with respect to
$\mu_j$ and $\sigma_j$.
