Latent Relational Point Process: Network Reconstruction from Discrete Event Data

Abstract

Digital interactions, such as Wi-Fi access, financial transactions, and social media activities, leave crumbs in their path. These vast quantities of fine-granularity data generated by complex real-world relational systems propound unprecedented alternatives to expensive and laborious surveys and studies for researchers who want to learn and understand the underlying network models. Point processes are well-suited for modelling the discrete data commonly observed from digital interactions of today’s complex systems. In this work, we present a latent relational point process framework for recovering the posterior probability of latent relations from discrete event data effectively and efficiently. Our proposed framework comprises a general definition of the latent relational point process, an algorithm for fitting the parameters of an evolutionary version of the model to the data, and goodness-of-fit tests to quantify the suitability of the model to the data. The proposed framework is evaluated for the modelling of a social network from the observations of social interactions.

A Appendix

1.1 A.1 The Lower Bound of the Posterior

The objective of this section is to derive the lower bound in Eq. 5, using the duality formula from [9]:

$$\begin{aligned} \begin{aligned}&\log \Pr (\theta \mid H_{T^-}) \\&= \log \left[ \int _{\mathbb {E}} \mathcal {L}(H_{T^-} \mid E, \theta ) \, d\mu _{\mathcal {E}} \, (E \mid \theta ) \right] + \log \Pr (\theta ) - \log \Pr (H_{T^-}) \\&\ge \int _{\mathbb {E}} \ell (H_{T^-} \mid E, \theta ) \, d\hat{\mu }_{\mathcal {E}} \, (E) - {\text {KL}}(\hat{\mu }_{\mathcal {E}} \Vert \mu _{\mathcal {E}}) + \log \Pr (\theta ) - \log \Pr (H_{T^-}) \\&= \int _{\mathbb {E}} \ell (H_{T^-} \mid E, \theta ) \hat{f}_{\mathcal {E}} \, (E) \, d\iota (\epsilon ) - \int _{\mathbb {E}} \log \left( \frac{\hat{f}_{\mathcal {E}} \, (E)}{f_{\mathcal {E}} \, (E \mid \theta )} \right) \hat{f}_{\mathcal {E}} \, (E) \, d\iota (\epsilon ) \\&\quad + \log \Pr (\theta ) - \log \Pr (H_{T^-}) \\ \end{aligned} \end{aligned}$$

(16)

1.2 A.2 The Surrogate is the Posterior Distribution

The objective of this section is to show that the surrogate distribution $\hat{f}_{\mathcal {E}} \, (E)$ in Eq. 7 is the posterior $\Pr (E \mid H_{T^-}, \theta )$. Applying Bayes theorem to Eq. 7 we have that it is equal to:

$$\begin{aligned} \frac{\frac{\Pr (E, \theta \mid H_{T^-}) \Pr (H_{T^-})}{f_{\mathcal {E}} \, (E \mid \theta ) \Pr (\theta )} \; f_{\mathcal {E}} \, (E \mid \theta )}{\int _{\mathbb {E}} \frac{\Pr (E, \theta \mid H_{T^-}) \Pr (H_{T^-})}{f_{\mathcal {E}} \, (E \mid \theta ) \Pr (\theta )} f_{\mathcal {E}} \, (E \mid \theta ) \, d\iota (\epsilon )} = \frac{\Pr (E, \theta \mid H_{T^-})}{\Pr (\theta \mid H_{T^-})} = \Pr (E \mid H_{T^-}, \theta ) \end{aligned}$$

(17)

1.3 A.3 Simple-Pair Model: Gilbert Graph

We obtain the conditional log-likelihood of the observed data by plugging Eqs. 11 and 12 into Eq. 2 and taking the logarithm:

$$\begin{aligned} \begin{aligned} \ell (H_{T^-} \mid A, \theta )&= \sum _{n=1}^N \left[ \log \lambda _g + \log (a_n \lambda _1 + (1 - a_n) \lambda _2) - \log \lambda ) \right] - \int _0^T \lambda _g du \\&= \sum _{i < j} \left[ a_{i,j} ( N_{i,j} \log \lambda _1 - T \lambda _1) + (1 - a_{i, j}) ( N_{i, j} \log \lambda _2 - T \lambda _2) \right] \end{aligned} \end{aligned}$$

(18)

Above, we are able to split the $\log$ because either $a_n = 1$ or 0. Also note, $\sum _{n=1}^N = \sum _{i < j} N_{i,j}$, $|E| = \sum _{i < j} a_{i,j}$ and $|\mathcal {K}_{\mathbb {V}}| - |E| = \sum _{i < j} (1 - a_{i,j})$.

By plugging Eqs. 10 and 18 into Eq. 6 and assuming uniform priors such that $\Pr (\theta )$ is a constatnt, we find expressions for the maximisation step:

$$\begin{aligned} {\left\{ \begin{array}{ll} \begin{aligned} &{}\sum _A \left[ \sum _{i< j} a_{i,j} \left( \frac{N_{i,j}}{\hat{\lambda }_1} - T \right) \right] \hat{f}_{\mathcal {E}} \, (A) + 0 = 0 \\ &{}\sum _A \left[ \sum _{i< j} (1 - a_{i,j}) \left( \frac{N_{i,j}}{\hat{\lambda }_2} - T \right) \right] \hat{f}_{\mathcal {E}} \, (A) + 0 = 0 \\ &{}\sum _A \left[ \frac{\sum _{i< j} a_{i,j}}{p} - \frac{\sum _{i < j} (1-a_{i,j})}{1-p} \right] \hat{f}_{\mathcal {E}} \, (A) + 0 = 0 \end{aligned} \end{array}\right. } \end{aligned}$$

(19)

Let $\hat{f}_{\mathcal {E}} \, (a_{i,j}) = \sum _A a_{i,j} \hat{f}_{\mathcal {E}} \, (A) = \Pr (a_{i,j} = 1 \mid H_{T^-}, \theta )$, then we can simplify the first equality in Eq. 19 to find an expression for updating $\lambda _1$:

$$\begin{aligned} \sum _{i< j} \left( \frac{N_{i,j}}{\hat{\lambda }_1} - T \right) \sum _A a_{i,j} \hat{f}_{\mathcal {E}} \, (A) = 0 \iff \hat{\lambda }_1 = \frac{\sum _{i< j} \hat{f}_{\mathcal {E}} \, (a_{i,j}) N_{i,j}}{T \sum _{i < j} \hat{f}_{\mathcal {E}} \, (a_{i,j})} \end{aligned}$$

(20)

Likewise, we find the remaining estimates of Eq. 13—note that $\left( {\begin{array}{c}|\mathbb {V}|\\ 2\end{array}}\right) = \sum _{i < j} 1$.

Finally, we obtain Eq. 14 by plugging the parameter estimates of Eq. 13, the network prior from Eq. 10 and the likelihood from Eq. 18 into Eq. 7:

$$\begin{aligned} \begin{aligned}&\hat{f}_{\mathcal {E}} \, (A) = \\&= \frac{\prod _{i< j} \left( \hat{\lambda }_1^{N_{i,j}} \exp (-T \hat{\lambda }_1) \, \hat{p} \right) ^{a_{i,j}} \left( \hat{\lambda }_2^{N_{i,j}} \exp (-T \hat{\lambda }_2) \, (1-\hat{p}) \right) ^{(1-a_{i,j})} }{\sum _A \prod _{i< j} \left( \hat{\lambda }_1^{N_{i,j}} \exp (-T \hat{\lambda }_1) \, \hat{p} \right) ^{a_{i,j}} \left( \hat{\lambda }_2^{N_{i,j}} \exp (-T \hat{\lambda }_2) \, (1-\hat{p}) \right) ^{(1-a_{i,j})}} \\&= \prod _{i< j} \frac{\left( \hat{\lambda }_1^{N_{i,j}} \exp (-T \hat{\lambda }_1) \, \hat{p} \right) ^{a_{i,j}} \left( \hat{\lambda }_2^{N_{i,j}} \exp (-T \hat{\lambda }_2) \, (1-\hat{p}) \right) ^{(1-a_{i,j})} }{ \left( \hat{\lambda }_1^{N_{i,j}} \exp (-T \hat{\lambda }_1) \, \hat{p} \right) + \left( \hat{\lambda }_2^{N_{i,j}} \exp (-T \hat{\lambda }_2) \, (1-\hat{p}) \right) } \\&= \prod _{i < j} \left[ \hat{f}_{\mathcal {E}} \, (a_{i,j}) \right] ^{a_{i, j}} \left[ 1 - \hat{f}_{\mathcal {E}} \, (a_{i,j}) \right] ^{(1 - a_{i,j})} \end{aligned} \end{aligned}$$

(21)