text:
\section{New inference}
Each edge is associated with a cluster, $z_i$; a sender-table, $b_i^s$, and a receiver-table, $b_i^r$. These are determined by who the edge follows. The edge has three "following" relationships. $c_i$ is who the $i$th edge cluster-follows -- it determines $z_i$. $g_i^s$ and $g_i^r$ are who the edge sender-follows, and receiver-follows -- they determine the sender-table and the receiver-table.

Note that, an edge can only sender-follow and receiver-follow edges that are in the same cluster!

\subsection{Sampling the clusters}
We are going to propose a new cluster-follow $c_i^*$, and a new set of sender-follows and receiver-follows $\mathbf{g}^{s*}$ and $\mathbf{g}^{r*}$. We first propose an intermediate ``launch state'' $c_i^\circ, \mathbf{g}^{s\circ},\mathbf{g}^{r\circ}$ (similar to the launch state in the split-merge sampler for the DP):

\begin{itemize}
    \item Let $z_a \leftarrow z_i$
    \item $c_i^\circ = i$
    \item Update $\mathbf{z}^\circ$ to give the launch clusters.
    \item We might now have some edges who sender-follow or receiver-follow an edge that is no longer in the same cluster. Let
    $$\mathcal{M}^s = \{j: z_i^\circ \neq z_{g_i^s}^\circ \}$$
    and
    $$\mathcal{M}^r = \{j: z_i^\circ \neq z_{g_i^r}^\circ \}$$
    \item For every $j \in \mathcal{M}^s$, set $g_j^{s \circ} =j$; for every  $j \not\in \mathcal{M}^s$, set $g_j^{s \circ} =g_j^s$
    \item For every $j \in \mathcal{M}^r$, set $g_j^{r \circ} =j$; for every  $j \not\in \mathcal{M}^s$, set $g_j^{s \circ} =g_j^s$
\end{itemize}

Next, we will sample a proposal $c_i^*, \mathbf{g}^{s*}, \mathbf{g}^{r*}$ from our proposal distribution $q(c_i, \mathbf{g}^s, \mathbf{g}^r) = q(c_i)\prod_{j\in \mathcal{M}^s} q(g_j^s) \prod_{k\in \mathcal{M}^r} q(g_k^r)$. We first sample $c_i^* \sim q(c_i)$ where

$$q(c_i = k) \propto \begin{cases} f_1(d_{ik}) & k<i\\ \alpha & k=i\end{cases}$$

We record $q(c_i)$ and $q(c_i^*)$ (including normalizing constants)

We then update the clusters $\mathbf{z}^*$.

We then sample the sender-tables for $j\in\mathcal{M}^s$

$$q(g_j^s = k) := P(g_j^s = k | z_{\leq j}, g_{<j}^s, s_j) \propto \begin{cases}
f_2(d_{jk})  & k<j, z^*_i=z^*_k, s_j = s_k \\
\tau h_{s_j} & k=j\\
0 & z^*_i\neq z^*_k\\
0 & s_i \neq s_k \end{cases}$$

and similarly sample the receiver-tables for $j\in\mathcal{M}^r$.

We record $q(g_j^{s*})$ and $q(g_j^{s})$ for each $j\in \mathcal{M}^s$ -- note that the distributions will be different for the original state and the proposed state! Ditto for the receivers.

Now, we need to calculate the MH acceptance ratio. In general, we have an acceptance ratio of

$$\min\left(1, \frac{q(c_i, \mathbf{b}^s, \mathbf{b}^r)}{q(c_i^*, \mathbf{b}^{s*}, \mathbf{b}^{r*})}\frac{P(\mathbf{c}^*,\mathbf{b}^{s*},\mathbf{b}^{r*})}{P(\mathbf{c},\mathbf{b}^{s},\mathbf{b}^{r})}\right)$$

In our case, the c terms cancel, and we have

$$\min\left(1, \frac{\prod_{j\in \mathcal{M}^s} q(g_j^s) \prod_{k\in \mathcal{M}^r} q(g_j^r)}
{\prod_{j\in \mathcal{M}^s} q(g_j^{s*}) \prod_{k\in \mathcal{M}^r} q(g_j^{r*})}
\frac{\prod_i P(g_i^{s*}|g_{<i}^{s*}, h, z_{\leq i}) P(g_i^{r*}|g_{<i}^{r*}, h,z_{\leq i})}
{\prod_i P(g_i^{s}|g_{<i}^{s}, h,z_{\leq i}) P(g_i^{r}|g_{<i}^{r}, h,z_{\leq i})}\right)
$$
where

$$P(g_j^s = k|g_{<j}^s, h, z_{\leq i}) \propto \begin{cases}
f_2(d_{jk})  & k<j, z^*_i=z^*_k \\
\tau h_{s_j} & k=j\\
0 & z_j \neq z_k \end{cases}$$

Note this looks really similar to $q(g_j^s)$ above!! But it's not the same... because we are not conditioning on $s_i$. We do \textit{not} have zero probability for the case where $s_i\neq s_k$ -- so the normalizing constant will be different since we are summing over all pairs in the cluster, not just all pairs that are a match.

We can probably cancel some of the terms down here... but for now, I'd say let's not.

\subsection{Sampling the tables}
Conditioned on the cluster allocations $z_i$, we \textit{almost} have a hierarchical ddCRP as described in \cite{Ghosh2011} -- the only difference is that the top level of the hierarchy is a Pitman-Yor process, not a Dirichlet process. I will describe for sender-tables; receiver-tables are sampled analogously.

We consider the $i$th sender. It sender-follows $j$ with probability

$$P(g_i^s = j|g_{-i}^s, h, e) \propto \begin{cases} f_2(d_{ij} )P(s_i|g_i^s=j) & z_i=z_j, j<i\\
\tau P(s_i|g_i=i) & i=j\\
0 & z_i\neq z_j\end{cases}$$

Now, the likelihood is binary for an existing table (either the table ``serves'' $s_i$ or it doesn't), so this reduces to

\begin{equation}P(g_i^s = j|g_{-i}^s, h, e) \propto \begin{cases} f_2(d_{ij} )& z_i=z_j, j<i, s_i=s_j\\
\tau h_{s_i} & i=j\\
0 & z_i\neq z_j\\
0 & s_i \neq s_j\end{cases}\end{equation}

\subsection{Sampling the $h$}

The $g_i^s$ and $g_i^r$ define tables $b_i^s$, $b_i^r$. Let $\eta_v$ be the total number of tables (sender and recipient) associated with vertex $v$. Then, assuming we have $V$ distinct vertices in our graph, we have

$$(h_1, \dots, h_V, h_+) \sim \mbox{Dirichlet} (\eta_1 - \sigma, \dots, \eta_V - \sigma, \gamma + V \sigma)$$

(see Corollary 20 of \cite{Pitman1996})

\begin{algorithm}[tb]
	\begin{algorithmic}[1]
	\STATE $c_i$ represents who the $i$-th edge is following: $(z_i, g_i^s,g_i^r)$
	\STATE Initialize $c_i$, $g_i^s$, $g_i^r$ for each edge $i$, assign the cluster indicators $z_i$ based on the $c_i$, assign the table indicators $b_i^s$, $b_i^r$ based on $g_i^s$, $g_i^r$.
    \STATE Calculate $f_1(d_{ij})$ and $f_2(d_{ij})$ for every $i, j \in 1, \dots, N$
 	\FOR {$t \in \{1,\ldots,MAXIT\}$}
 	\FOR{$i \in \{1, \dots, N\}$}
 	\STATE \COMMENT{--Sampling the clusters--}
 	\STATE $\mathbf{c}^\circ \leftarrow \mathbf{c}$, $\mathbf{z}^\circ \leftarrow \mathbf{z}$, $\mathbf{g}^{s/r\circ} \leftarrow \mathbf{g}^{s/r} $
 	\STATE $c_i^{\circ} = i$
 	\STATE update all $z_i^{\circ}$ to be consistent with $c_i^{\circ}$
 	\STATE $\mathcal{M}^s = \{j: z_j^{\circ} \neq z_{g^s_j}^{\circ}\}$, $\mathcal{M}^r = \{j: z_j^{\circ} \neq z_{g^r_j}^{\circ}\}$

 	\STATE sample a proposal $c_i^*,g^{s*},g^{r*} \propto q(c_i, g^s, g^r) = q(c_i)\prod_{j\in \mathcal{M}^s} q(g_j^s) \prod_{k\in \mathcal{M}^r} q(g_k^r)$
 	\STATE sample $c_i^* \sim q(c_i), q(c_i=k) = \begin{cases} \frac{f_1(d_{ik})}{\sum_j f_1(d_{ij}) + \alpha} & k<i\\ \frac{\alpha}{\sum_j f_1(d_{ij}) + \alpha} & k=i\end{cases}$, then update $z^*$ from $c^*$
 	\FORALL{$j \in \mathcal{M}^{s/r}$}
 	\STATE sample $g_j^{*s/r} \sim q(g_j^{s/r})$ where
 	\STATE $q(g_j^s = k) := P(g_j^s = k | z_{\leq j}, g_{<j}^s, s_j) = \begin{cases}
\frac{f_2(d_{jk})}{\sum_{l:z_l=z_k,s_l=s_k} f_2(d_{jl}) + \tau h_{s_j}}  & k<j, z^*_j=z^*_k, s_j = s_k \\
\frac{\tau h_{s_j}}{\sum_{l:z_l=z_k,s_l=s_k} f_2(d_{jl}) + \tau h_{s_j}} & k=j\\
0 & z^*_j\neq z^*_k\\
0 & s_j \neq s_k \end{cases}$
 	\ENDFOR
    \STATE compute acceptance ratio $a(c^*,c) = \min \bigg(1, \frac{q(c_i,b^s,b^r)}{q(c^*_i,b^{*s},b^{*r}} \frac{P(c^*_i,b^{*s},b^{*r})}{P(c_i,b^s,b^r)}  \bigg)$
    \STATE $a(c^*,c)=
    \min\left(1, \frac{\prod_{j\in \mathcal{M}^s} q(g_j^s) \prod_{k\in \mathcal{M}^r} q(g_j^r)}
{\prod_{j\in \mathcal{M}^s} q(g_j^{s*}) \prod_{k\in \mathcal{M}^r} q(g_j^{r*})}
\frac{\prod_i P(g_i^{s*}|g_{<i}^{s*}, h, z_{\leq i}) P(g_i^{r*}|g_{<i}^{r*}, h,z_{\leq i})}
{\prod_i P(g_i^{s}|g_{<i}^{s}, h,z_{\leq i}) P(g_i^{r}|g_{<i}^{r}, h,z_{\leq i})}\right)$
    \STATE where $P(g_j^s = k | z_{\leq j}, g_{<j}^s) = \begin{cases}
\frac{f_2(d_{jk})}{\sum_{l:z_l=z_k} f_2(d_{jl}) + \tau }  & k<j, z_j=z_k\\
\frac{\tau h_{s_j}}{\sum_{l:z_l=z_k} f_2(d_{jl}) + \tau } & k=j\\
0 & z_j\neq z_k \end{cases}$
    \IF{rand < $a(c^*,c)$}
    \STATE accept new state
    \ENDIF
 	\STATE \COMMENT{--Sampling the tables--}
 	\STATE sample $g_i^{s/r} \sim P(g_i^{s/r}=j|g^{s/r}_{-i},h , e) = \begin{cases}
\frac{f_2(d_{ij})}{\sum_{l:z_l=z_j,s_l=s_j} f_2(d_{il}) + \tau h_{s_i}}  & j<i, z_i=z_j, s_i = s_j \\
\frac{\tau h_{s_i}}{\sum_{l:z_l=z_j,s_l=s_j} f_2(d_{il}) + \tau h_{s_i}} & j=i\\
0 & z_i\neq z_j\\
0 & s_i \neq s_j \end{cases}$
	\ENDFOR
 	\STATE \COMMENT{--Sampling the $h$--}
 	\FOR{$v \in V$}
 	\STATE $\eta_v = \sum_{i}\mathbbm{1}{(s_i=v,g_i^s=i)}+\mathbbm{1}{(r_i=v,g_i^r=i)}$
 	\STATE sample $h_v \sim \text{Dir}(\eta_1-\sigma,\ldots, \eta_V-\sigma, \gamma+V\sigma)$
 	\ENDFOR

 	\ENDFOR

	\end{algorithmic}
	\caption{MH}
	\label{alg:modified}
\end{algorithm}

\begin{algorithm}[th]
	\begin{algorithmic}[1]
	\STATE initialize $c_i$ uniformly at random from $\{1,\ldots,N\}$ for each edge $i$
	\FOR {$t \in \{1,\ldots,T\}$}
		\FOR {$i \in \{1,\ldots,N\}$}
		\FOR {$j \in \{1,\ldots,i-1\}$}
		    \STATE compute $f_{d_{ij}}$ \qquad \COMMENT{For the prior}
		\ENDFOR
		\STATE sample $z_i \propto \begin{cases} f_1(d_{ij})-\sigma \quad & j < i \\ \alpha+K\sigma \quad & j = i \end{cases}$
		\STATE $P(c^{*}_i) = \log p(z_i)$
		\IF{$z_i< K$}
		\STATE sample $b_i^{*(s/r)}|z_i \propto H = \begin{cases} \sum_{j:z_j=z_i}\frac{f_2(d_{ij})}{\sum_{j:z_j =z_i}f_1(d_{ij})+\tau} + \big(\frac{\tau}{\sum_{j:z_j =z_i}f_1(d_{ij})+\tau}\frac{t^{(s/r)}_i}{\sum_{l}t^{(s)}_l+t^{(r)}_l+\gamma} \big) \quad &t^{(s/r)}_i>0 \\ \frac{\tau}{\sum_{j:z_j =z_i}f_1(d_{ij})+\tau}\frac{\gamma}{\sum_{l}t^{(s)}_l+t^{(r)}_l+\gamma} \quad &t^{(s/r)}=0 \end{cases}$
		\ELSE
		\STATE sample $b_i^{*(s/r)}|z_i \propto H = \begin{cases} \frac{t^{(s/r)}_i}{\sum_{l}t^{(s)}_l+t^{(r)}_l+\gamma} \quad &t^{(s/r)}_i>0 \\ \frac{\gamma}{\sum_{l}t^{(s)}_l+t^{(r)}_l+\gamma} \quad &t^{(s/r)}=0 \end{cases}$
		\ENDIF
		\STATE $L(c^*_i|X) = \log p(b_i^{*(s)})+ \log p(b_i^{*(r)})$
		\STATE proposal = $q(c^{*}|c) = \big(P(c^{*}_i) + L(c^{*}_i|X)\big)-\big(P(c_i) + L(c_i|X)\big)$
		\STATE $a(c^{*},c) = \min(1, e^{q(c^{*}|c)})$
		\IF{rand < a}
		\STATE accept the proposal $c^{*}$
		\ELSE
		\STATE reject the proposal
		\ENDIF
		\ENDFOR
		\STATE \COMMENT{split-merge}
		\STATE pick $i$ and $j$ uniformly at random
		\STATE $S$ is the set of observations, $k \in \{1,\ldots,n\}$ for which $k \neq i, k \neq j$ and $z_k=z_i  \OR z_k=z_j$
		\IF{$z_i = z_j$}
		\STATE $c^{*}=c^{split}$
		\STATE set $c_i^{split}$ to a new component such that $c_i^{split} \not\in \{c_1,\ldots,c_n\}$
		\STATE set $c_j^{split}=c_j$
		\STATE sample $b^{split (s/r)}_i, b^{split (s/r)}_j \propto H$
		\FOR{$k \in S$}
		\STATE $c_k^{split} = $ randomly choose $c_i^{split} \OR c_j^{split}$
		\STATE sample $b^{split (s/r)}_k \propto H$
		\ENDFOR
		\STATE compute prior $P(c^{split})$ and the likelihood of this clustering $L(c^{split}|X)$ just for changed clusters
		\STATE $a(c^{split},c) = \min\bigg(1, \frac{1}{\big(\frac{1}{2}\big)^{n_{c_i^{split}}+n_{c_j^{split}}-2}}\frac{P(c^{split})L(c^{split}|X)}{P(c)L(c|X)}\bigg)$
		\ELSE
	    \STATE $c^{*}=c^{merge}$
		\STATE set $c_i^{merge} = c_j$
		\STATE set $c_j^{merge}=c_j$
		\STATE sample $b^{merge (s/r)}_i, b^{split (s/r)}_j \propto H$
		\FOR{$k \in S$}
		\STATE $c_k^{merge} = c_j$
		\STATE sample $b^{merge (s/r)}_k \propto H$
        \ENDFOR
        \STATE compute prior $P(c^{merge})$ and the likelihood of this clustering $L(c^{merge}|X)$ just for changed clusters
		\STATE $a(c^{merge},c) = \min\bigg(1, \big(\frac{1}{2}\big)^{n_{c_i}+n_{c_j}-2}\frac{P(c^{merge})L(c^{merge}|X)}{P(c)L(c|X)}\bigg)$
        \ENDIF
        \STATE accept/reject $c^{*}$ based on the acceptance ratio $a(c^{*},c)$
	\ENDFOR

	\end{algorithmic}
	\caption{MH}
	\label{alg:ll}
\end{algorithm}

\iffalse
\begin{table*}[ht]
\parbox{\textwidth}{
\caption{\small{AP@10}\vspace{-.2cm}}
\centering
\scriptsize
\resizebox{1\textwidth}{!}{
\begin{tabular}{|c|c|c|c|c|c|}
	\toprule
	Method & {\textsc{DNND}}\xspace & MDND & DRGPM & DPGM & DGPPF\\
	\midrule
	\textsc{CollegeMsg} & \textbf{0.466$$\pm$$0.030} & 0.267$$\pm$$0.132 & 0.118$$\pm$$0.105  & 0.037$$\pm$$0.007 & 0.052$$\pm$$0.016 \\
	\textsc{Email-Eu}  & \textbf{0.390$$\pm$$0.052} & 0.238$$\pm$$0.101 & 0.330$$\pm$$0.124 & 0.308$$\pm$$0.110 & 0.199$$\pm$$0.099\\
	\textsc{SocialEv} & \textbf{0.586$$\pm$$0.338}  & 0.179$$\pm$$0.104 & 0.001$$\pm$$0.000 & 0.033$$\pm$$0.008 & 0.008$$\pm$$0.003 \\
	\textsc{DBLP} & \textbf{0.493$$\pm$$0.274} & 0.205$$\pm$$0.039 & 0.388$$\pm$$0.263 & 0.451$$\pm$$0.228 & 0.374$$\pm$$0.204\\
	\hline
\end{tabular}
}\label{tbl:hitall}\vspace{5mm}
}
\hfill
\parbox{\textwidth}{
\caption{\small{AP@20}\vspace{-.2cm}}
\centering
\scriptsize
\resizebox{1\textwidth}{!}{
\begin{tabular}{|c|c|c|c|c|c|}
	\toprule
	Method & {\textsc{DNND}}\xspace & MDND & DRGPM & DPGM & DGPPF\\
	\midrule
	\textsc{CollegeMsg} & \textbf{0.504$$\pm$$0.033} & 0.295$$\pm$$0.118 & 0.091$$\pm$$0.060  & 0.071$$\pm$$0.064 & 0.085$$\pm$$0.070 \\
	\textsc{Email-Eu}  & 0.452$$\pm$$0.012 & 0.227$$\pm$$0.097 & \textbf{0.464$$\pm$$0.112} & 0.451$$\pm$$0.091 & 0.380$$\pm$$0.087 \\
	\textsc{SocialEv} & \textbf{0.515$$\pm$$0.232}  & 0.162$$\pm$$0.239 & 0.008$$\pm$$0.003 & 0.011$$\pm$$0.009 & 0.014$$\pm$$0.006 \\
	\textsc{DBLP} & 0.496$$\pm$$0.143 & 0.118$$\pm$$0.019 & 0.459$$\pm$$0.254 & \textbf{0.516$$\pm$$0.229} & 0.485$$\pm$$0.197\\
	\hline
\end{tabular}}
\label{tbl:apall}\vspace{5mm}
}
\hfill
\parbox{\textwidth}{
\caption{\small{AP@50}\vspace{-.2cm}}
\centering
\scriptsize
\resizebox{.9\textwidth}{!}{
\begin{tabular}{|c|c|c|c|c|c|}
	\toprule
	Method & {\textsc{DNND}}\xspace & MDND & DRGPM & DPGM & DGPPF\\
	\midrule
	\textsc{CollegeMsg} & \textbf{0.516$$\pm$$0.026} & 0.321$$\pm$$0.065  & 0.085$$\pm$$0.052  & 0.067$$\pm$$0.061 & 0.069$$\pm$$0.065 \\
	\textsc{Email-Eu}  & \textbf{0.585$$\pm$$0.036} & 0.318$$\pm$$0.125 & 0.494$$\pm$$0.117 & 0.490$$\pm$$0.104 & 0.451$$\pm$$0.091\\
	\textsc{SocialEv} & \textbf{0.423$$\pm$$0.151}  & 0.253$$\pm$$0.169 & 0.009$$\pm$$0.004 & 0.024$$\pm$$0.010 & 0.021$$\pm$$0.006 \\
	\textsc{DBLP} & 0.492$$\pm$$0.111 & 0.241$$\pm$$0.012 & 0.451$$\pm$$0.234 & \textbf{0.498$$\pm$$0.208} & 0.476$$\pm$$0.181\\
	\hline
\end{tabular}}
\label{tbl:hitmapk100}\vspace{5mm}
}
\hfill
\parbox{\textwidth}{
\caption{\small{AP@$\mathtt{k}$ of three decay functions}\vspace{-2mm}}
\centering
\scriptsize
\resizebox{1\textwidth}{!}{
\begin{tabular}{|c|ccc|ccc|ccc|}
	\toprule
	& \multicolumn{3}{|c|}{{\textsc{DNND}}\xspace-\textsc{Window}} &\multicolumn{3}{|c|}{{\textsc{DNND}}\xspace-\textsc{Logistic}} & \multicolumn{3}{|c|}{{\textsc{DNND}}\xspace-\textsc{Exponential}} \\
	\midrule
	\textit{MAP@$\mathtt{k}$} & @10 & @20 & @50& @10 & @20 & @50 & @10 & @20 & @50  \\
	\midrule
	\textsc{CollegeMsg} & \textbf{0.47$$\pm$$0.03} & \textbf{0.50$$\pm$$0.03} & \textbf{0.52$$\pm$$0.03} & 0.46$$\pm$$0.15 & 0.50$$\pm$$0.09 & 0.51$$\pm$$0.14 & 0.46$$\pm$$0.11 & 0.48$$\pm$$0.11 & 0.49$$\pm$$0.15  \\
	\textsc{Email-Eu}   & 0.25$$\pm$$0.04 & 0.39$$\pm$$0.01 & 0.46$$\pm$$0.09 & 0.33$$\pm$$0.08 & 0.43$$\pm$$0.04 & 0.50$$\pm$$0.10 & \textbf{0.39$$\pm$$0.05} & \textbf{0.45$$\pm$$0.01} & \textbf{0.50$$\pm$$0.04} \\
	\textsc{SocialEv}   & 0.34$$\pm$$0.16 & 0.32$$\pm$$0.02 & 0.28$$\pm$$0.03 & 0.50$$\pm$$0.36 & 0.51$$\pm$$0.30 & \textbf{0.49$$\pm$$0.27} & \textbf{0.59$$\pm$$0.34} &\textbf{0.51$$\pm$$0.23} & 0.42$$\pm$$0.15  \\
	\textsc{DBLP}       & 0.39$$\pm$$0.11 & 0.42$$\pm$$0.07 & 0.45$$\pm$$0.05 & 0.46$$\pm$$0.14 & 0.40$$\pm$$0.07 & 0.49$$\pm$$0.05 & \textbf{0.49$$\pm$$0.27} & \textbf{0.50$$\pm$$0.14} & \textbf{0.49$$\pm$$0.11} \\
	\hline
\end{tabular}
}\label{tbl:decay_Maps}
}
\end{table*}

\fi

\begin{algorithm}[tb]
	\begin{algorithmic}[1]
	\STATE initialize $c_i$ uniformly at random from $\{1,\ldots,N\}$ for each edge $i$
	\FOR {$t \in \{1,\ldots,T\}$}
		\FOR {$i \in \{1,\ldots,N\}$}
		\FOR {$j \in \{1,\ldots,i-1\}$}
		    \STATE compute $f_{d_{ij}}$ \qquad \COMMENT{For the prior}
		\ENDFOR
		\STATE sample $z_i \propto \begin{cases} f_1(d_{ij})-\sigma \quad & j < i \\ \alpha+K\sigma \quad & j = i \end{cases}$
		\STATE $P(c^{*}_i) = \log p(z_i)$
		\IF{$z_i< K$}
		\STATE sample $b^{*}_i^{(s/r)}|z_i \propto H = \begin{cases} \sum_{j:z_j=z_i}\frac{f_2(d_{ij})}{\sum_{j:z_j =z_i}f_1(d_{ij})+\tau} + \big(\frac{\tau}{\sum_{j:z_j =z_i}f_1(d_{ij})+\tau}\frac{t^{(s/r)}_i}{\sum_{l}t^{(s)}_l+t^{(r)}_l+\gamma} \big) \quad &t^{(s/r)}_i>0 \\ \frac{\tau}{\sum_{j:z_j =z_i}f_1(d_{ij})+\tau}\frac{\gamma}{\sum_{l}t^{(s)}_l+t^{(r)}_l+\gamma} \quad &t^{(s/r)}=0 \end{cases}$
		\ELSE
		\STATE sample $b^{*}_i^{(s/r)}|z_i \propto H = \begin{cases} \frac{t^{(s/r)}_i}{\sum_{l}t^{(s)}_l+t^{(r)}_l+\gamma} \quad &t^{(s/r)}_i>0 \\ \frac{\gamma}{\sum_{l}t^{(s)}_l+t^{(r)}_l+\gamma} \quad &t^{(s/r)}=0 \end{cases}$
		\ENDIF
		\STATE $L(c^{*}_i|X) = \log p(b^{*}_i^{(s)})+ \log p(b^{*}_i^{(r)})$
		\STATE proposal = $q(c^{*}|c) = \big(P(c^{*}_i) + L(c^{*}_i|X)\big)-\big(P(c_i) + L(c_i|X)\big)$
		\STATE $a(c^{*},c) = \min(1, e^{q(c^{*}|c)})$
		\IF{rand < a}
		\STATE accept the proposal $c^{*}$
		\ELSE
		\STATE reject the proposal
		\ENDIF
		\ENDFOR
		\STATE \COMMENT{split-merge}
		\STATE pick $i$ and $j$ uniformly at random
		\STATE $S$ is the set of observations, $k \in \{1,\ldots,n\}$ for which $k \neq i, k \neq j$ and $z_k=z_i  \OR z_k=z_j$
		\IF{$z_i = z_j$}
		\STATE $c^{*}=c^{split}$
		\STATE set $c_i^{split}$ to a new component such that $c_i^{split} \not\in \{c_1,\ldots,c_n\}$
		\STATE set $c_j^{split}=c_j$
		\STATE sample $b^{split (s/r)}_i, b^{split (s/r)}_j \propto H$
		\FOR{$k \in S$}
		\STATE $c_k^{split} = $ randomly choose $c_i^{split} \OR c_j^{split}$
		\STATE sample $b^{split (s/r)}_k \propto H$
		\ENDFOR
		\STATE compute prior $P(c^{split})$ and the likelihood of this clustering $L(c^{split}|X)$ just for changed clusters
		\STATE $a(c^{split},c) = \min\bigg(1, \frac{1}{\big(\frac{1}{2}\big)^{n_{c_i^{split}}+n_{c_j^{split}}-2}}\frac{P(c^{split})L(c^{split}|X)}{P(c)L(c|X)}\bigg)$
		\ELSE
	    \STATE $c^{*}=c^{merge}$
		\STATE set $c_i^{merge} = c_j$
		\STATE set $c_j^{merge}=c_j$
		\STATE sample $b^{merge (s/r)}_i, b^{split (s/r)}_j \propto H$
		\FOR{$k \in S$}
		\STATE $c_k^{merge} = c_j$
		\STATE sample $b^{merge (s/r)}_k \propto H$
        \ENDFOR
        \STATE compute prior $P(c^{merge})$ and the likelihood of this clustering $L(c^{merge}|X)$ just for changed clusters
		\STATE $a(c^{merge},c) = \min\bigg(1, \big(\frac{1}{2}\big)^{n_{c_i}+n_{c_j}-2}\frac{P(c^{merge})L(c^{merge}|X)}{P(c)L(c|X)}\bigg)$
        \ENDIF
        \STATE accept/reject $c^{*}$ based on the acceptance ratio $a(c^{*},c)$

	\ENDFOR

	\end{algorithmic}
	\caption{MH}
	\label{alg:ll}
\end{algorithm}

\section{Background and related work}\label{sec:related}

To provide appropriate context, in this section we introduce the notion of graph sparsity (Section~\ref{subsec:graphsparsity}, and discuss existing Bayesian models for multigraphs in the stationary (Section~\ref{subsec:bg_static}) and dynamic (Section~\ref{subsec:bg_dynamic}) setting. Finally, we review the ddCRP (Section~\ref{subsec:ddCRP}), which will be used in {\textsc{DNND}}\xspace.

\subsection{Graph sparsity}\label{subsec:graphsparsity}
The density of a graph with $E$ edges and $V$ vertices is the ratio of the number of edges to the number of potential edges. For binary, undirected graphs, this density is $2E/V(V-1)$. We can extend this notion to distributions over graphs, by looking at how the density behaves as the graph grows. We say a graph is sparse if the number of edges grows subquadratically with the number of vertices (see e.g. \cite{Orbanz:Roy:2014} for a discussion of sparsity and density in graphs).

Following \cite{CaiCampbellBroderick2016}, we extend this definition to multigraphs, saying a multigraph is sparse if the number of edges grows subquadratically with the number of vertices. Empirically, many large real-world graphs and multigraphs are sparse \cite{demaine2014structural,CaronFox2017}

\subsection{Vertex-exchangeable and sparse-exchangeable models for multigraphs}\label{subsec:bg_static}
Most Bayesian models for (multi)graphs exhibit a form of exchangeability, meaning that they are invariant to temporal reordering of the data. As we will see in Section~\ref{subsec:bg_dynamic}, while these models are inherently unsuited for dynamically evolving graphs, most dynamic Bayesian models are based on an exchangeable counterpart. The models described in this paper are no exception.

There are several forms of exchangeability that are appropriate in the context of graphs, depending on which aspect of the graph we consider reordering; each context of exchangeability leads to different model properties.  The models described in this paper are based on edge-exchangeable graphs, which we will describe
in Section~\ref{subsec:edge-exch}. Here, we review the two other families of exchangeable (multi)graphs.

\textbf{Vertex-exchangeable graphs} \cite{Aldous1981,Hoover:1979,Orbanz:Roy:2014} are graphs where the distribution over the adjacency matrix is invariant to jointly permuting the row and column indices. This occurs when the presence (or in the case of a multigraph, the number of instances) of an edge between vertices $u$ and $v$ is a random variable parameterized by the value of some function $\theta(u, v)$ and is conditionally independent from other edges given $\theta(u, v)$---for example, if $e_{u,v}\sim\mbox{Bernoulli}(\theta(u, v))$. This class includes the stochastic blockmodel \cite{Snijders:Nowicki:1997,Karrer:Newman:2011}; the infinite relational model \cite{irm}; the mixed-membership stochastic blockmodel \cite{airoldi2008mixed}; the latent feature relational model \cite{miller2009nonparametric}; and Poisson factor analysis \cite{ZhouCarin2013,gopalan2015scalable}. While these models are able to capture interesting community structure, the resulting graphs are dense almost surely, \cite{Aldous1981, Hoover:1979}. This makes them a poor choice for large real-world multigraphs, which are typically sparse.\looseness=-1

\textbf{Sparse exchangeable (multi)graphs} \cite{CaronFox2017,Veitch:Roy:2015,veitch2019sampling,borgs2019sampling} consider an alternative notion of exchangeability, based on increments of an underlying random measure. For example, \cite{CaronFox2017} describes a model for graphs and multigraphs based on an underlying Poisson process, whose rate measure is distributed according to a generalized gamma process \cite{brix1999generalized}; this family is generalized by \cite{Veitch:Roy:2015}. Such a construction yields sparse graphs with a power-law degree distribution, properties that are common in large social networks. \cite{lee2018bayesian} proposes an extension of such a model with community structure. Unlike the edge-exchangeable graphs that we will consider in Section~\ref{subsec:edge-exch}, sparse exchangeable graphs assume a fully observed graph where no new edges will be seen between existing vertices, making them poorly suited to prediction tasks in dynamically growing interaction networks.

\subsection{Edge-exchangeable multigraphs}\label{subsec:edge-exch}

Edge-exchangeable multigraphs \cite{CaiCampbellBroderick2016,CraneDempsey2018,Williamson2016} construct a multigraph based on an infinitely exchangeable sequence of edges. Edges are sampled from a distribution over pairs of vertices, which is typically constructed by sampling each vertex independently from some nonparametric probability distribution. Unlike vertex-exchangeable and sparse-exchangeable models, edge-exchangeable multigraphs can grow over time.
For certain choices of distribution over the vertices, edge-exchangeable multigraphs are sparse \cite{CaiCampbellBroderick2016,CraneDempsey2018}. Loosely, this occurs when the distribution is heavy-tailed, as this ensures the probability of a new edge adding a new vertex to the graph remains high enough to keep the number of edges subquadratic in the number of vertices. This holds for a class of completely random measures \cite{CaiCampbellBroderick2016} that includes the generalized gamma process \cite{brix1999generalized}, and for the Pitman-Yor process \cite{CraneDempsey2018,Pitman:Yor:1997}.

\textbf{Hierarchical edge-exchangeable multigraphs}. Edge-exchangeable multigraphs can exhibit sparsity and power-law degree distribution,  but they lack complex structure, since the two vertices that comprise each edge are chosen independently. The mixture of Dirichlet network distributions (MDND) \cite{Williamson2016} breaks this independence by using a mixture of edge-exchangeable models. Edges are associated with one of an unbounded number of clusters, with the cluster assignments distributed according to a Chinese restaurant process (CRP). Within each cluster, edges are generated according to an edge-exchangeable multigraph sequence. In this sequence, the directed edges are generated by sampling a ``sender'' and a ``recipient'' from two separate Dirichlet processes (DPs) to allow asymmetry in a directed setting which are coupled via a shared base measure.
However, the choice of DPs as distributions over vertices mean that MDND does not yield sparse graphs \cite{CaiCampbellBroderick2016,CraneDempsey2018}. As we show in Section \ref{sec:model1}, even if we were to replace the top-level DP with a heavy tailed distribution, this would not guarantee sparsity in the resulting multigraph.

\subsection{Models for dynamic graphs}\label{subsec:bg_dynamic}

Since real-world interaction networks often evolve over time, there has been significant research attention on dynamic graph models. A common approach relies on the extensions of \emph{stationary} network models to a \emph{dynamic} framework. Although, there have been many dynamic extensions of non-Bayesian models such as the exponential random graph model~\cite{guo2007recovering} and matrix and tensor factorization-based methods~\cite{dunlavy2011temporal}, here we focus on Bayesian models relevant to the present work.

Most dynamic Bayesian networks extend vertex-exchangeable graphs. \cite{xu2014dynamic} and \cite{durante2014nonparametric} extend the stochastic blockmodel to allow time-evolving parameters. \cite{xu2015sbtm} relaxes exchangeability assumptions, allowing the presence or absence of edges to directly influence future edge probabilities. Temporal dynamics have also been added to the mixed membership stochastic blockmodel framework \cite{fu2009dynamic,xing2010state,ho2011evolving}, the infinite relational model \cite{ng2017dynamic} and the latent feature relational model \cite{foulds2011dynamic,heaukulani2013dynamic,kim2013nonparametric}. Recently, several models have extended Poisson factor analysis. The dynamic gamma process Poisson factorization (DGPPF)~\cite{acharya2015nonparametric} introduces dependency by incorporating a Markov chain of marginally gamma random variables into the latent representation. The dynamic Poisson gamma model (DPGM)~\cite{yang2018poisson} extends a bilinear form of Poisson factor analysis~\cite{zhou2015infinite} in a similar manner. The dynamic relational gamma process model (DRGPM)~\cite{yang2018dependent} also incorporates a temporally dependent thinning process.

Much less work has been carried out on dynamic extensions of sparse-exchangeable or edge-exchangeable graphs. \cite{PallaCaronTeh2016} extends the sparse-exchangeable model of \cite{CaronFox2017} to use a time-dependent base measure, and assume edges have a geometric lifespan. In the edge exchangeable case, \cite{ng2017dynamic} incorporates temporal dynamics into the MDND by introducing a latent Gaussian Markov chain, and a Poisson vertex birth mechanism; while it offers empirical evidence of sparsity, it is not proven to yield sparse multigraphs. \cite{ghalebi2018dynamic} extends the MDND to partially observed data and use a temporally informed inference algorithm, but the underlying model is stationary.

\subsection{Distance-dependent Chinese restaurant process}\label{subsec:ddCRP}
Edge-exchangeable graphs generate edges according to either a single exchangeable distribution over vertices, or a collection of coupled exchangeable distributions over vertices. A natural way to incorporate temporal dependence in such a model is to replace the associated exchangeable distributions with temporally varying clustering mechanisms. In this paper, we choose to use the distance-dependent CRP (ddCRP) \cite{BleiFrazier2011}, since it yields desirable sparsity results.

Under the ddCRP with concentration parameter $\tau$ and non-negative, non-increasing decay function $f$ such that $f(\infty)=0$, the probability of an observation $x_i$ joining a cluster $k$ is,
\begin{equation}
P(z_i=k|z_{<i}) \propto \begin{cases} \sum_{j: z_j=k} f(d_{i,j}) & k\leq K_i\\
\tau & k=K_i + 1\end{cases}, ~~~ d_{i, j} = \begin{cases} t_i - t_j & t_i \geq t_j\\ \infty &
 \mbox{otherwise}\end{cases}
\label{eqn:ddcrp}
\end{equation}
where $z_i$ is the cluster assignment of the $i$-th edge, $K_i$ is the number of previously seen clusters
 and the distance $d_{i,j}$ captures how much time has elapsed between $x_i$ and $x_j$. The concentration parameter $\tau$ controls the expected number of clusters. The decay function means that new samples are more likely to be from the same component as recently seen samples than older samples, allowing the predictive distribution to evolve over time. A known limitation of the ddCRP is that it assumes that all data has been observed up to the current time point: the distribution is not invariant to adding edges at previously observed time points. This is not a concern in our setting, since we are typically able to observe past instances of the full graph, and are interested in predicting future edges.

\iffalse

\sinead{I don't think we need to introduce the PY process, it's pretty standard in BNP}
\subsection{Pitman-Yor process}
The DP distribution over $H$ and the CRPs used to assign edges to tables do not have sufficiently heavy tails to yield sparse multigraphs (see \cite{CaiCampbellBroderick2016} and \cite{CraneDempsey2018}). The Pitman-Yor process \cite{Pitman:Yor:1997} is an alternative distribution over probability distributions that has heavier tails than the DP. The Pitman-Yor process has previously been used in the construction of sparse, edge-exchangeable multigraphs, albeit without the structure of the MDND \cite{CraneDempsey2018}.

The exchangeable distribution over partitions implied by the Pitman-Yor process can be described using
a two-parameter CRP. With discount parameter $0 \leq \sigma < 1$ and concentration parameter $\gamma>-\sigma$, the clustering behavior of the two-parameter CRP is given by
\begin{equation}P(z_i = k|z_{<i}) \propto \begin{cases} m_k - \sigma & k\leq K_+ \\ \gamma + \sigma K_+ & k=K_+ + 1\end{cases}\label{eq:pycrp}\end{equation}
where $K_+$ is the number of existing clusters and $m_k$ is number of times we have seen cluster $k$. If $\sigma=0$, this reduces to the standard CRP with concentration parameter $\gamma$; as $\sigma$ increases, the distribution has increasingly heavy tails.
\fi

\iffalse
\begin{equation}\label{eqn:mdnd}
\begin{aligned}[c]
	H & \coloneqq \sum_{i=1}^\infty h_i\delta_{\theta_i} &\sim& ~\text{DP}(\gamma,\Theta)  \\
	A_k & \coloneqq \sum_{i=1}^\infty a_{i}\delta_{\theta_i} &\sim& ~\text{DP}(\tau, H) \\
	B_k & \coloneqq \sum_{i=1}^\infty b_{i}\delta_{\theta_i} &\sim& ~\text{DP}(\tau,H)
\end{aligned}
\qqua
\begin{aligned}[c]
	z_1, z_2, \dots \sim& ~ \mbox{CRP}(\alpha)\\
	s_n \sim& A_{z_n}\\
	r_n \sim& B_{z_n}
\end{aligned}
\end{equation}

\fi

\iffalse

Each edge $i$ is associated with a cluster $z_i$, governing which edge-exchangeable model it is generated from. The $z_i$ are distributed according to a Chinese restaurant process \cite[CRP,][]{griffiths2004hierarchical}, which describes the distribution over partitions in a DP mixture model, allowing an unbounded number of clusters.

Within the $k$-th cluster, each edge is associated with two ``tables'', $b_{i}^{(s)}$ and $b_{i}^{(r)}$, sampled from two separate CRPs.\footnote{While the original MDND paper describes this distribution in terms of Dirichlet processes, we will provide an equivalent construction in terms of CRPs, to provide consistency with later contributions.} These tables are associated with the sender and recipient of the edge, respectively. Each table $b_i^{(s)}$ (or $b_i^{(r)}$) in cluster $k$ is linked with a vertex $\phi_{k, b_i}^{(s)}$ (or $\phi_{k, b_i}^{(r)}$, so that, for example, all edges $i$ where $z_i=k$ and $b_i^{(s)}=c$ have the same sender $\phi_{k, c}^{(s)}$. To ensure that the cluster-specific multigraphs have common support, the vertices for each table are sampled from a global, DP-distributed probability measure $H$, that is shared across all clusters. The overall distribution over the $i$th directed edge $(s_i, r_i)$ can be written as
\begin{equation}\label{eqn:mdnd}
    \begin{aligned}[c]
        H &\sim ~\text{DP}(\gamma,\Theta)  \\
        P(z_i=k|z_{<i}) &\propto \begin{cases} m_{k} & k\leq K_+\\
        \alpha & k=K_++1
        \end{cases}\\
        P(b_i^{(s)}=c|z_i=k, b_{<i}^{(s)}) &\propto \begin{cases} \rho^{(s)}_{k,c} & c\leq C^{(s)}_{k+}\\
        \tau & k=C^{(s)}_{k+}+1
        \end{cases}\\
        P(b_i^{(r)}=c|z_i=k, b_{<i}^{(r)}) &\propto \begin{cases} \rho^{(r)}_{k,c} & c\leq C^{(r)}_{k+}\\
        \tau & k=C^{(r)}_{k+}+1
        \end{cases}\\
        \phi_{k, c}^{(s)}\sim H \qquad &\qquad  s_i = \phi_{z_i,b_i}^{(s)}\\
        \phi_{k,c}^{(r)}\sim H\qquad &\qquad  r_i = \phi_{z_i,b_i}^{(r)}\\
    \end{aligned}
\end{equation}
where $m_k$ is the number of times we have seen cluster $k$; $z_{<i} = (z_1,\dots, z_{i-1})$; $s_i(r_i)$ is the sender(recipient) of edge $i$; $\rho_{k,c}^{(s)}$ is the number of senders sat at table $c$ in cluster $k$ (with $\rho_{k,c}^{(r)}$ defined analogously); $K_+$ is the number of previously seen clusters; and $C^{(s)}_{k+}$ and $C^{(r)}_{k+}$ are the number of previously seen sender and recipient tables, respectively, in cluster $k$. Here, $\alpha>0$ controls the number of clusters, $\gamma>0$ controls the overall number of vertices, $\tau$ controls similarity between clusters, and $\Theta$ is some diffuse measure on the space of vertices.

\fi
\section{Discussion}
We have demonstrated that edge-based multigraphs constructed using the ddCRP are sparse for certain parameter settings, and have proposed a new distribution for sparse, temporally varying, structured networks based on these edge-based multigraphs. As we saw in Section~\ref{sec:experiments}, these properties translate into impressive predictive performance compared with state-of-the-art Bayesian models.
While we focus here on the ddCRP, we note that  alternative dependent nonparametric priors could also be used. For example, the P\"{o}lya urn-based model of \cite{caron2007generalized} randomly deletes either previously seen clusters or observations, and could yield sparse graphs under appropriate deletion schemes.
An interesting avenue for future research would be to explore alternative forms of dependency, and incorporate mechanisms that can capture link reciprocity \cite{blundell2012modelling}.

An alternative path towards sparse, dynamic graphs would be to use a dependent nonparametric process with heavy-tailed marginals, such as a dependent Pitman-Yor process \cite{sudderth2009shared}. While replacing the distribution in a simple edge-exchangeable multigraph with such a distribution would yield sparse graphs, this sparsity would not necessarily carry over to hierarchical models such as {\textsc{DNND}}\xspace.

\section*{Broader impacts}
Our work joins a growing body of research that aims to explain the complex connectivity structure of real graph data. By incorporating sparsity and temporal dynamics in a nonparametric Bayesian framework, we provide tools that can improve link prediction and structure elucidation in interaction networks. We hope that this model will inspire researchers to use Bayesian modelling in their work and help facilitate the modeling of more complex and diverse graph-structured data.

While we have shown good predictive performance on real-world data, it is important to remember that this is not the only metric on which an algorithm should be judged. While interaction networks, such as email networks and social networks, have clear communication benefits, they also pose potential risks to users. Like most machine learning algorithms, graph algorithms risk leaking private information about users. While a Bayesian approach provides some protection against such leakage \cite{DimNelZhaMitRub2017}, our algorithm is not designed to protect user privacy. We refer the reader to \cite{BorChaSmi2015} for a discussion of privacy in sparse graphs

Two other concerns appropriate to interaction networks---which often involve sensitive user information, and can impact the lives and decisions of their users---are the interpretability of the algorithm, and the fairness of its predictions. Since our model is based on a hierarchical clustering model, its latent structure is naturally fairly interpretable, allowing the user to explain predictions in terms of these latent clusters.

While we do not explore the fairness of our predictions in this work, it is known that the ``filter bubble'' effect can cause systemic bias \cite{MasWilYanTanEsf2020}. This occurs when a link prediction algorithm predicts that a user will interact with similar users, and so only suggests such connections. As a result, groups tend to become segregated. If, for example, men are significantly more likely to belong to a bubble including influential individuals, this puts them at a clear advantage. The clustering behavior underlying our model means that, if it were used to recommend connections, it could lead to such a filter bubble. We do not, therefore, recommend that our algorithm be the sole method used for recommending interactions to individuals, and care should be taken to avoid such undesirable consequences.

\section{Introduction}\label{sec:intro}
Many social interaction networks can be represented in terms of a multigraph---\textit{i.e.} a graph where there can be multiple edges between two vertices. For example, vertices might correspond to individuals, with each edge representing an email between two individuals.
In large-scale applications, such multigraphs are typically sparse, with the number of edges being small relative to the number of unconnected pairs of vertices. Concretely, we call a distribution over graphs or multigraphs sparse if the number of edges grows sub-quadratically with the number of vertices.

Edge-exchangeable models \cite{CaiCampbellBroderick2016,CraneDempsey2018} have been proposed as models for sparse multigraphs, and hierarchical variants allow the incorporation of community-type structure \cite{Williamson2016}. Such models assume that more edges and vertices will be seen in the future, making them appropriate for growing graphs, and under certain settings they are provably sparse. However, they assume that the distribution over multigraphs is stationary, and that the resulting multigraph is invariant to reordering the arrival times of the edges. In practice, most real-world networks are dynamic, with the underlying distribution evolving over time. Despite this, there is a lack of models for sparse, dynamically evolving  multigraphs.

We show that the basic edge-exchangeable framework of \cite{CaiCampbellBroderick2016} can be adapted to yield dynamically evolving multigraphs with provable sparsity, replacing the underlying distribution on the space of vertices with a time-dependent process \cite{BleiFrazier2011}. This construction allows the distribution to evolve over time, in a manner that encourages new edges to contain recently visited vertices. We incorporate this basic dynamic multigraph into a dynamic, hierarchical model that retains this sparsity while capturing complex, time-evolving interaction structure. The Dynamic Nonparametric Network Distribution ({\textsc{DNND}}\xspace) uses a temporally evolving clustering structure and a  hierarchical Bayesian nonparametric framework to capture both global changes in cluster popularity and shifting dynamics within clusters. A judicious choice of base measure for the cluster-specific distributions means that our distribution can generate either sparse or dense multigraphs, with the degree of sparsity controlled by a single parameter.  The increased flexibility allowed by our model leads to improved performance over both its exchangeable counterpart and over a range of state-of-the-art dynamic network models.

\textbf{Contributions:} (1) We show that a sequence of edges whose distributions are governed by a distance-dependent Chinese restaurant process \cite{BleiFrazier2011} form sparse, non-stationary multigraphs---even though comparable, edge-exchangeable multigraphs based on the Chinese restaurant process are not sparse;  (2) we construct a flexible hierarchical model, {\textsc{DNND}}\xspace, appropriate for dynamically evolving, structured multigraphs. We show that this distribution can be used to model sparse or dense interaction networks, and propose an MCMC algorithm for inference; (3) we show that {\textsc{DNND}}\xspace outperforms state-of-the-art Bayesian dynamic network models over three real-world network datasets.

\iffalse
\sinead{I'm cutting this for space... I don't feel roadmaps are particularly important}
After covering appropriate background and related work in Section~\ref{sec:related}, we show that edge-based random multigraphs based on the ddCRP are sparse in Section~\ref{sec:basic_model}. In Section~\ref{sec:model}, we use such multigraphs as building blocks to construct our dynamic Bayesian model for sparse dynamic multigraphs, providing theoretical sparsity results in Section~\ref{sec:sparsity} which are reinforced by empirical sparsity evaluations.  In Section~\ref{sec:experiments}, we experimentally evaluate the performance of our model both on held-out edge prediction and graph forecasting tasks, demonstrating improved performance over state-of-the-art Bayesian methods.
\fi
\section{Experiments}\label{sec:experiments}
In this section, we address the following questions: (1) How well does {\textsc{DNND}}\xspace capture the underlying multigraph behavior to predict unseen held-out edges? and (2) How accurate is {\textsc{DNND}}\xspace in terms of forecasting future interactions, compared to state-of-the-art dynamic interaction graph models? We include code to reproduce our results within the supplementary material.

\textbf{Datasets.} We evaluated our model on three real-world temporal multigraphs;
\\
(1) \textit{Email-Eu-core temporal network (Email-Eu)}
\cite{snapnets} consists of all incoming and outgoing emails in a large European research institution. $986$ individuals exchange about $332$\,k separate e-mails over $803$ days. We considered the first $T=7$ months of all departments of the institute, with $120121$
edges and $844$ vertices, with an average monthly density ($\frac{2}{T}\sum_{t=1}^T E_t/V_t(V_t-1)$) of $0.06$.
\\
(2) \textit{CollegeMsg network} \cite{snapnets} records private messages in an online social multigraph at the University of California, Irvine. We evaluated the performance of our model on all $T=7$ months with $1899$ vertices and $59835$ interactions over $193$ days. The average monthly density is $0.02$.
\\
(3) \textit{Social Evolution network (SocialEv)} \cite{madan2011sensing} tracks the everyday life of 70 students within a dormitory, based on mobile phone data. We consider Bluetooth connections, calls and SMSs as interactions, yielding a multigraph with high clustering coefficient and about $1M$ events over $T=10$ months. In practice, there are $187K$ edges and $74$ vertices, with average monthly density of $0.82$.

\textbf{Experimental settings.}
For {\textsc{DNND}}\xspace, we considered three decay functions: (1) \textsc{Window} decay: $f(d)=1[d<\lambda]$ only considers dependency with edges that are distant at most $\lambda$ from the current edge, (2) \textsc{Exponential} decay: $f(d) = e ^{-d/\lambda}$ decays exponentially with time, and (3) \textsc{Logistic} decay: $f(d) = \frac{e ^{-d+\lambda}}{1+e ^{-d+\lambda}}$ is a smooth version of window decay. We used the same decay function for $f_1$ and $f_2$.
We used a $\mbox{Gamma}(5, 1)$ prior for both $\alpha$ and $\gamma$, a $\mbox{Gamma}(1,1)$ prior for $\tau$, a $\mbox{Beta}(1, 1)$ prior for $\sigma$ and a $\mbox{Gamma}(50,1)$ prior for $\lambda$. Empirically, we found that varying these priors did not dramatically impact performance.

We ran all algorithms for 1000 iterations for each dataset and each time slot (month). For the baseline methods, we used the optimization or sampling methods, settings and hyperparameters described in the relevant papers. All the experiments were run on a standard desktop, an Intel Xeon with \SI{2.5}{GHz} CPU and \SI{128}{GB} RAM. We include the scripts used in these experiments with our submission, and will make these publically available after publication.

\textbf{Baselines.}
For the held-out edge prediction task, we compared against stationary MDND, described in Section~\ref{subsec:edge-exch}. We implemented MDND using the inference algorithm in Appendix~\ref{sec:inference_app}, with $\sigma=0$ and $d_{i, j}=1$ for all $i\geq j$. We found that this algorithm gave comparable results to the implementation of \cite{Williamson2016}.
For the graph forecasting task, we also compared against three recent Bayesian dynamic network models, introduced in Section~\ref{subsec:bg_dynamic}: the dynamic relational gamma process model (DRGPM) \cite{yang2018dependent}, the dynamic Poisson gamma model (DPGM) \cite{yang2018poisson}, and the dynamic gamma process Poisson factorization (DGPPF) \cite{acharya2015nonparametric}. These models are not applicable to the held-out edge prediction task, since they assume all vertices are observed. However, they can be used to predict the entire graph at the next time slot over seen vertices. We modify this distribution to be appropriate to our forecasting task by predicting the $n_T$ edges with the highest probability at time slot $T$.

\textbf{Evaluation metrics.}
We consider four evaluation metrics: Log likelihood of held-out data, F1 score for predicted future interactions, hits ratio at $k$ (hits@$k$) and average precision at $k$ (AP@$k$) for predicted future interactions.
The held-out log likelihood allows us to evaluate whether our model is a good fit for the data. We use this to evaluate whether incorporating time-dependence and sparsity allows us to better capture variation in the data compared to MDND. Estimating test set log likelihood can be tricky in models where we have latent variables for each data point, since the likelihood depends heavily on the assignments of those latent variables, and the state space of assignments is too large to explore exhaustively. We estimate the log predictive likelihood using the ``left to right'' algorithm \cite{Wallach:2009:EMT:1553374.1553515} explained in Appendix~\ref{app:results}.

While log likelihood allows us to compare models, it does not provide a quantitative measure of how much better a model will perform on a concrete prediction task for future observations. To assess this, we consider two metrics for evaluating future predictions when we have all observations before time $T$, and want to predict the edges arriving at time $T$. To allow comparison with vertex-exchangeable models, which predict the entire adjacency matrix for a single time step, we set the time stamp for all test set edges to the time of the first test set edge. We assume that we know the total number, $N_{\mbox{\small{test}}}$, of edges in the test set, allowing us to return a predicted set of appropriate size, along with their probability of appearance. For comparison methods, we selected the $N_{\mbox{\small{test}}}$ edges with highest probability of appearing.

The F1 score---calculated as the harmonic mean of precision and recall---gives a general measure of the accuracy of the predictor, assigning equal importance to Type I and Type II errors. Average precision at $k$ looks at the proportion of the held-out edges that appear in the top $k$ predictions, averaged over samples and hits ratio at $k$ is the proportion of correct predicted edges in top-$k$ ranked edges \cite{yang2012top}.
This allows us to dig deeper into the model's performance, considering whether the edges assigned high probability under the model are correct. The higher the F1 on the test set, the better.

\begin{table*}[t]
\centering
\caption{\small{Predictive log likelihood of held-out edges on three real-world datasets (mean $\pm$ standard deviation over time slots).}}\label{tbl:log_lhood}
\vspace{-.4cm}
\medskip
\footnotesize
\begin{tabular}{
  c|
  S[table-format=5.1(4), detect-weight, detect-shape, detect-mode]
  S[table-format=5.1(4), detect-weight, detect-shape, detect-mode]
  S[table-format=5.1(4), detect-weight, detect-shape, detect-mode]
  S[table-format=5.1(4), detect-weight, detect-shape, detect-mode]
 }
\toprule
\diag{.068em}{1.5cm}{\scriptsize{Dataset}}{\scriptsize{Method}}
&{\textsc{MDND}} &{\textsc{{\textsc{DNND}}\xspace-Window}} &{\textsc{{\textsc{DNND}}\xspace-Logistic}} &{\textsc{{\textsc{DNND}}\xspace-Exponential}} \\
\midrule
\text{Email-Eu}  &  -26868.9  \pm 375.0 & -25270.8 \pm 422.9 &  -2288.4 \pm 469.0 &  \bfseries -22260.2 \pm 399.9\\
\text{SocialEv}  &  -1181.8 \pm 152.4 &   -709.4 \pm 84.1  & -749.9 \pm 90.6  & \bfseries -699.7 \pm 84.4\\
\text{CollegeMsg}&  -4416.6 \pm 227.8 & \bfseries -3757.9 \pm 213.3  & -5041.9 \pm 375.7  & -3882.0 \pm 233.0\\
\bottomrule
\end{tabular}
 \vspace{-.4cm}
\end{table*}
\begin{figure*}[t!]
	\centering
	\subfigure[Email-Eu\label{subfig:email}]{\includegraphics[width=.3\textwidth,trim=10mm 15mm 10mm 10mm]{plots/email_log_predictive_timeslots.pdf}}
    \subfigure[SocialEv\label{subfig:social}]{\includegraphics[width=.3\textwidth,trim=10mm 15mm 10mm 10mm]{plots/social_log_predictive_timeslots.pdf}}
    \subfigure[CollegeMsg\label{subfig:college}]{\includegraphics[width=.3\textwidth,trim= 10mm 15mm 10mm 10mm] {plots/college_log_predictive_timeslots.pdf}}
\vspace{-.2cm}
\caption{\small{Predictive log likelihood vs.~time slots. Each evaluation is the average value over 10 runs.}}
\label{fig:AvgPredLike}
\vspace{-3mm}
\end{figure*}

\begin{table*}[t]
\hfill
\parbox{\textwidth}{
\caption{\small{hits@$\mathtt{k}$ for the future interaction prediction task (mean value over samples).}\vspace{-.2cm}}
\centering
\scriptsize
\resizebox{1\textwidth}{!}{
\begin{tabular}{|c|ccc|ccc|ccc|ccc|ccc|}
	\toprule
	& \multicolumn{3}{|c|}{{\textsc{DNND}}\xspace} &\multicolumn{3}{|c|}{MDND} & \multicolumn{3}{|c|}{DRGPM} & \multicolumn{3}{|c|}{DPGM}& \multicolumn{3}{|c|}{DGPPF}\\
	\midrule
	\textit{hits@$\mathtt{k}$} & @10 & @20 & @50& @10 & @20 & @50 & @10 & @20 & @50 & @10 & @20 & @50 & @10 & @20 & @50 \\
	\midrule
	\textsc{Email-Eu} & \textbf{0.96} & 0.92 & \textbf{0.99}  & 0.94 & \textbf{0.96} & 0.96 & 0.3 & 0.21 & 0.23 & 0.28 & 0.21 & 0.25 & 0.32 & 0.2 & 0.2\\
	\textsc{SocialEv} & \textbf{0.78} & \textbf{0.98} & \textbf{1.0}  & 0.74 & 0.91 & \textbf{1.0} & 0.21 & 0.21 & 0.21 & 0.16 & 0.16 & 0.1 & 0.36 & 0.36 & 0.35\\
	\textsc{CollegeMsg} & \textbf{0.62} & \textbf{0.78} & \textbf{0.98}  & 0.5 & 0.63  & 0.96 & 0.06  & 0.06  & 0.06 & 0.14 & 0.15 & 0.14  & 0.17 & 0.17  & 0.16 \\
	\hline
\end{tabular}}
\label{tbl:hits}\vspace{.1cm}
}
\hfill
\parbox{\textwidth}{
\caption{\small{AP@$\mathtt{k}$ for the future interaction prediction task (mean value over samples).}\vspace{-.2cm}}
\centering
\scriptsize
\resizebox{1\textwidth}{!}{
\begin{tabular}{|c|ccc|ccc|ccc|ccc|ccc|}
	\toprule
	& \multicolumn{3}{|c|}{{\textsc{DNND}}\xspace} &\multicolumn{3}{|c|}{MDND} & \multicolumn{3}{|c|}{DRGPM} & \multicolumn{3}{|c|}{DPGM}& \multicolumn{3}{|c|}{DGPPF}\\
	\midrule
	\textit{AP@$\mathtt{k}$} & @10 & @20 & @50& @10 & @20 & @50 & @10 & @20 & @50 & @10 & @20 & @50 & @10 & @20 & @50 \\
	\midrule
	\textsc{Email-Eu} & \textbf{0.73} & \textbf{0.43} & \textbf{0.18}  & 0.66 & 0.41 & 0.18 & 0.21 & 0.14 & 0.10 & 0.16 & 0.14 & 0.12 & 0.22 & 0.17 & 0.10\\
	\textsc{SocialEv} & \textbf{0.25} & \textbf{0.16} & \textbf{0.13}  & 0.17 & 0.10 & 0.04 & 0.06 & 0.03 & 0.01 & 0.05 & 0.02 & 0.01 & 0.06 & 0.03 & 0.01\\
	\textsc{CollegeMsg} & \textbf{0.64} & \textbf{0.39} & \textbf{0.21}  & 0.43 & 0.33  & 0.2 & 0.09  & 0.05  & 0.02 & 0.1 & 0.05 & 0.02  & 0.1 & 0.05  & 0.02 \\
	\hline
\end{tabular}
}\label{tbl:aps}
}\vspace{-.4cm}
\end{table*}
\begin{figure*}[t]
	\centering
	\subfigure[Email-Eu\label{subfig2:email}]{\includegraphics[width=.3\textwidth]{plots/email_FNP_F1_score.png}}
	\subfigure[SocialEv\label{subfig3:social}]{\includegraphics[width=.3\textwidth]{plots/social_FNP_F1_score.png}}
	\subfigure[CollegeMsg\label{subfig1:college}]{\includegraphics[width=.3\textwidth] {plots/college_FNP_F1_score.png}}
	\vspace{-.2cm}
	\caption{\small{F1 score for future interaction prediction. Decay functions for {\textsc{DNND}}\xspace are \textsc{Window} (W), \textsc{Exponential} (E), and \textsc{Logistic} (L) (averaged over time slots).}}
\label{fig:log-f1}
\vspace{-3mm}
\end{figure*}

\subsection{Prediction of held-out edges}
We consider how the test-set log likelihood varies between {\textsc{DNND}}\xspace and MDND, which can be seen as a special case of {\textsc{DNND}}\xspace where $\sigma=0$ and the ddCRPs reduce to CRPs, and explore how the choice of decay function affects performance. We split each data set into time slots (one month for all datasets), and train on $85\%$ of the interactions in each time slot.

Table~(\ref{tbl:log_lhood}) shows the predictive log likelihood computed by {\textsc{DNND}}\xspace using three different decays (\textsc{Window}, \textsc{Exponential} and \textsc{Logistic}) in comparison to the CRP decay function used in \cite{Williamson2016} on three real multigraphs. Values for each dataset and each decay function represent the mean value of log likelihoods across time slots. We see that in each case, all three dynamic {\textsc{DNND}}\xspace multigraphs outperform the stationary MDND.
In Figure~(\ref{fig:AvgPredLike}), we illustrate the predictive log likelihood per time slot, separately. Again, we see that {\textsc{DNND}}\xspace consistently outperforms the stationary MDND model across all time slots in terms of the predicted log likelihood of held-out edges. The best-performing decay function differs across datasets, likely due to different forms of temporal variation. This demonstrates that considering important properties observed in real-world data (\textit{i.e.} time dependency and sparsity) results in a better model fit.

\subsection{Forecasting future interactions}
We evaluated the F1 score, average precision at $k$ and hits ratio at $k$ using networks of time slot $T$ as the training set and testing by predicting the network edges at time slot $T+1$. To allow comparison with vertex-exchangeable methods, we assumed in all cases that all test-set observations arrive at the same time as the first test-set observation. To predict each interaction, we estimate its likelihood based on 10 posterior samples and we report the mean value over these samples for each interaction.

Tables~(\ref{tbl:hits}) and (\ref{tbl:aps})  show the average precision and hits ratio at $k$ for {\textsc{DNND}}\xspace and the four comparative methods. Due to limited space, the numbers reported for {\textsc{DNND}}\xspace represent the best result out of the three decay functions; complete tables are included in Appendix~\ref{app:results}. Figure~(\ref{fig:log-f1}) summarizes the corresponding F1 scores. The results show that {\textsc{DNND}}\xspace performs comparably or better on both metrics across all datasets. We hypothesize that this is due to several reasons. First, {\textsc{DNND}}\xspace is explicitly designed in terms of a predictive distribution over edges, making it well-suited to predicting future edges. Second, {\textsc{DNND}}\xspace is able to increase the number of vertices over time, and is likely better able to capture natural multigraph growth. Conversely, the other methods assume the number of vertices is fixed and known---and explicitly incorporate the absence of edges at earlier time points into the likelihood. Third, unlike the other methods, {\textsc{DNND}}\xspace allows us to capture sparsity. If the underlying multigraph is sparse, then this should lead to a more accurate model.

\section{Edge sequence distributions for sparse, dynamic multigraphs}\label{sec:basic_model}
In the context of edge-exchangeable multigraphs,
we can achieve sparsity if the underlying distribution over vertices has sufficiently heavy tails \cite{CaiCampbellBroderick2016, CraneDempsey2018}. Loosely, edge-exchangeable multigraphs obtain sparsity if the probability of incorporating a new vertex remains sufficiently large as the graph grows, so that the number of vertices is large relative to the number of edges. However, by their nature, edge-exchangeable models are not appropriate for data whose distribution varies over time, since their distributions are invariant to reordering the arrival times. In this section, we describe an alternative way of ensuring sparsity in a non-exchangeable setting, by allowing the probability of resampling an existing vertex to decay over time.

Let us define $\mathcal{E} = (e_1, e_2,\dots)$ to be a collection of directed edges, each expressed as an ordered tuple $e_i = (s_i, r_i)$. Using the language of an email communication network, we consider an edge as originating at a sender $s_i$, and leading to a recipient $r_i$.
In the basic edge-exchangeable multigraph \cite{CaiCampbellBroderick2016}, both sender and recipient are sampled i.i.d.\ from some discrete distribution,
$s_i, r_i \stackrel{\scriptscriptstyle{iid}}{\sim} f$.

Instead of sampling from a fixed $f$, we can sample the two end points of an edge from a dynamically evolving distribution. We choose to use the ddCRP (Equation \ref{eqn:ddcrp}), meaning that the probability of selecting vertex $v$ as either the $i$th sender, or the $i$th recipient, is
\begin{equation}
    P(s_i = v| s_{<i}, r_{<i}) = P(r_i = v| s_{<i}, r_{<i}) \propto
    \begin{cases}\textstyle\sum_{j: s_j=v}  f(d_{i, j}) + \sum_{j: r_j=v} f(d_{i, j}) \quad &v\leq V_i \\
    \tau \quad &v = V_i +1
    \end{cases}
    \label{eqn:ddCRPgraph}
\end{equation}
where the distance $d_{i,j}$ and decay function $f$ are as described in Section~\ref{subsec:ddCRP}, and vertices are numbered in order of appearance with $V_i$ being the number of previously seen vertices.
A number of other dependent or dynamic nonparametric processes could be used in place of the ddCRP. We choose the ddCRP because, under certain mild conditions on $f$, it yields sparse multigraphs, as we show below.

\begin{assumption}
The decay function $f$ in Equation~\ref{eqn:ddCRPgraph}, and the rate of arrival of edges $e_i$, satisfies $\sum_{i<n}f(d_{i,n})\leq D n^a$ for some $D<\infty$, $a<0.5$, and all $n$.
\end{assumption}

\begin{theorem}\label{the:sparsity}
If Assumption 1 holds, then the number of edges grows subquadratically with the number of vertices, and so the multigraph is sparse.\label{thm:sparsesimple}
\end{theorem}
The proof is provided in Appendix \ref{sec:proofs}.

\section{Sparse, structured multigraphs with temporal dynamics}\label{sec:model1}
While the edge sequence distribution described in Section~\ref{sec:basic_model} is sparse, it lacks structure. In the context of edge-exchangeable graphs, MDND, described in Section~\ref{subsec:edge-exch}, brings clustering structure and incorporates asymmetry between senders and recipients, yet it sacrifices sparsity. Further, since edges in MDND are exchangeable (\textit{i.e.}~the probability of the multigraph is invariant to reordering of the edge arrival times),  MDND is not a good fit for dynamically growing multigraphs, where the underlying mechanism is non-stationary.

Inspired both by MDND and the dynamic distribution discussed in Section~\ref{sec:basic_model}, we propose a new model, the Dynamic Nonparametric Network Distribution ({\textsc{DNND}}\xspace), for dynamic multigraphs with community structure. Like MDND, {\textsc{DNND}}\xspace clusters edges into an unbounded number of clusters, and within each cluster, has separate distributions for sender and recipient; however the nature of these distributions are modified to ensure the resulting graph is sparse and that the underlying distribution evolves over time.

The MDND uses a CRP to cluster edges. {\textsc{DNND}}\xspace replaces this with a ddCRP, meaning that the cluster probabilities can evolve over time. We also use a ddCRP (rather than a CRP) to model the distribution over edges within each cluster, so that the behavior within each cluster also evolves over time.

As with MDND, the cluster-specific distributions are coupled via a global, discrete distribution to ensure shared support. In the case of MDND, this distribution is a DP. Here, to allow sparsity in the resulting graph, we use a heavy-tailed
distribution. We choose to use the Pitman-Yor process \cite{Pitman:Yor:1997} with concentration parameter $\gamma$ and discount parameter $\sigma$, although as we discuss later, other heavy-tailed distributions such as the generalized gamma process could also be used. The resulting distribution over directed edges $(s_i, r_i)$ takes the form
\begin{equation}
\begin{aligned}
    P(z_i = k|z_{<i}) &\propto \begin{cases} \textstyle\sum\limits_{j: z_j=k} f_1(d_{i,j}) & k \leq K_i\\ \alpha & k = K_i+1\end{cases}\qquad H  \coloneqq \sum_{i=1}^\infty h_i\delta_{\theta_i} \sim ~\text{PY}(\gamma,\sigma,\Theta)
    \\
    s_i|z_i, s_{<i}, H &\begin{cases} = s & \mbox{w.p. }\propto \textstyle\sum\limits_{\stackrel{j: z_j=z_i}{s_j=s}}f_2(d_{i,j})\\
    \sim H & \mbox{w.p. }\propto \tau\end{cases}\qquad
    r_i|z_i, r_{<i}, H \begin{cases} = r &\mbox{w.p. }\propto \displaystyle\sum\limits_{\stackrel{j: z_j=z_i,}{r_j=r}} f_2(d_{i,j})\\
    \sim H & \mbox{w.p. }\propto \tau\end{cases}
\label{eqn:our_model}
\end{aligned}
\end{equation}

where $K_i$ is the number of previously seen clusters, $\alpha>0$, $\gamma>0$, $\tau>0$, $\sigma\in [0, 1)$, and $d_{i,j}$ is as defined in Equation~\ref{eqn:ddcrp}. $\Theta$ is some diffuse base measure on the space of vertices.
The decay functions $f_1$ and $f_2$ (see Section~\ref{subsec:ddCRP}) control the amount of influence past data points have on the current distribution over clusters and the current per-cluster distributions over vertices, respectively. For example, we might choose a window decay function $f(d) = 1[d<\lambda]$ that only allows data points within a size-$\lambda$ window to influence the current distribution, or an exponential decay function $f(d) = e^{-d/\lambda}$, where the influence decays smoothly with time. We note that, if $\sigma=0$ and $f_1(d) = f_2(d) = 1$ for all $d<\infty$,
then Equation~\ref{eqn:our_model} is equivalent to the MDND

The parameters $\alpha$, $\gamma$, and $\tau$ have a similar effect here as in MDND: $\alpha$ governs the number of clusters; $\gamma$ governs the overall number of vertices; and $\tau$ governs the similarity between clusters. $\sigma$ controls the sparsity of the multigraph. Under the mild constraints on $f_2$  and the rate of arrival of edges described in Assumption~\ref{ass:1}, the multigraph will be sparse if $\sigma>0.5$:
we do not require any assumptions on the global, clustering ddCRP with decay function $f_1$.

\begin{assumption}\label{ass:1}
The decay function $f_2$ in Equation~\ref{eqn:our_model} satisfies $\sum_{i=1}^j f_2(d_{i,j})\leq D$ for some $D<\infty$ and all $j$.
\end{assumption}

\begin{remark}
While this condition is stricter than the condition in Assumption 1, it is easily satisfied provided the rate of arrival of edges is bounded. For example, if $f_2$ is a window function of size $\lambda$, then $D$ is the maximum number of edges arriving in a period of length $\lambda$. If $f_2(d) = e^{-d/\lambda}$, and $m$ is the maximum number of edges arriving per unit time, then
\begin{equation*}
 \textstyle \sum_{i< j} f_2(d_{i,j})
\leq \sum_{i<j} e^{-\left \lfloor{d_{i,j}}\right \rfloor/\lambda }
\leq \sum_{\ell=0}^\infty m e^{-\ell/\lambda} = \frac{me^{-\lambda}}{e^{-\lambda}-1}
\end{equation*}
where the final inequality is due to the fact that there are at most $m$ observations with  $\lfloor{d_{i, j}}\rfloor=\ell$ for $\ell=1,\dots, \infty$. If $f$ is a logistic function, $f(d) = e^{-d+\lambda} / (1+e^{-d+\lambda})$, then $\sum_{i< j} f(d_{i,j})$ is bounded above by $\sum_{\ell=0}^\infty e^{\lambda} e^{-\ell} = e^{\lambda+1}/(e-1)$.

\end{remark}

\begin{theorem}\label{the:sparsity2}
If $f_2$ satisfies Assumption 2, and if $\sigma > 0.5$, multigraphs distributed according to Equation~\ref{eqn:our_model} are sparse.\label{thm:sparseDND}
\end{theorem}
The proof is given in Appendix \ref{sec:proofs}.

We note that, while we use a Pitman-Yor process in this paper, any base measure that can be used to construct a sparse, edge-exchangeable multigraph could be used here, since the incorporation of the ddCRP components does not affect the expected number of vertices. We demonstrate the resulting sparsity empirically, along with empirical demonstration of power-law behavior, in Appendix \ref{sec:eval_sparsity}.

\iffalse
\subsection{Discussion of modeling choices}
A number of dynamic extensions to the DP and other nonparametric priors have been proposed, that could be used to introduce temporal dependency into the MDND. We choose the ddCRP for three reasons. First, it allows us to guarantee sparsity, as described in Section~\ref{sec:sparsity}. Second, it captures behavior that we are likely to see in a dynamic network context: recent communications are likely to be more influential than more distant communications. Finally, its construction easily lends itself to an easy-to-implement sampler, as described in Section~\ref{sec:inference}; by contrast, many other dependent Dirichlet processes have much more complicated inference algorithms, which would limit scalability.

A known limitation of the ddCRP is that it assumes that all data has been observed up to the current time point; the distribution is not invariant to adding edges at previously observed time points. This is not a concern in our setting, since we are typically able to observe past instances of the full graph, and are interested in predicting future edges.

We note that the hierarchical structure over the cluster-specific distributions is similar to the spatial ddCRP proposed by \cite{Ghosh2011}, where a collection of ddCRPs are coupled using a shared Dirichlet process. We choose to use a Pitman-Yor process in place of the Dirichlet process to ensure sparsity. Alternative heavy-tailed nonparametric distributions with the base measure following a power-law such as the Normalized generalized gamma process (NGGP) could be used in place of the Pitman-Yor process; we chose the Pitman Yor process for ease of inference (it admits an urn representation). Inference for NGGP (e.g. \cite{favaro2013mcmc}) involves sampling an auxiliary variable that does not correspond to a standard distribution.
\fi

\textbf{Inference.} We perform inference via a MCMC algorithm that combines aspects of the ddCRP inference algorithm proposed by \cite{BleiFrazier2011} and the hierarchical Dirichlet process algorithms proposed by \cite{Teh:Jordan:Beal:Blei:2006}. Full details are provided in Appendix~\ref{sec:inference_app}.

\textbf{Complexity.} The complexity of our model is $O(E\times K)$, where $K$ is the number of clusters. The complexity of blockmodel-based models is $O(V^2 \times K)$. For sparse graphs, we have $E << V^2$. In practice, the runtimes of the different models were comparable on the datasets we considered.
\section{Proofs}\label{sec:proofs}
\textbf{Theorem \ref{the:sparsity}, restated}. If Assumption 1 holds, then the number of edges grows subquadratically with the number of vertices, and so the multigraph is sparse.

\begin{proof}
Consider first samples $x_1, x_2, \dots$ from a ddCRP with decay function $f$ and concentration parameter $\tau$, such that $\sum_{i<n}f(d_{i,n})\leq D n^a$ for some $D<\infty$ and all $n$. The probability that $x_i \neq x_j$ for all $j<i$ is $\frac{\tau}{\tau + \sum_{j<i}f(d_{i,j})}$, therefore, the expected number of distinct values, $K_n$, in $n$ observations is
$$
    \mathbb{E}[K_n] = \sum_{i=1}^n \frac{\tau}{\tau + \sum_{j<i}f(d_{i,j})}\geq \frac{n\tau}{\tau + Dn^{a}}.\
$$
If we use this ddCRP to construct a multigraph as described in Section~\ref{subsec:ddCRP}, then the expected number of distinct vertices $V_n$ in $E_n$ edges will be
$$
\begin{aligned}
    \mathbb{E}[V_n] =&\sum_{i=1}^{E_n} \frac{\tau}{\tau + 2 \sum_{j<i}f(d_{i,j})}
    + \sum_{i=1}^{E_n}\frac{\tau}{\tau + 2\sum_{j<i}f(d_{i,j}) + f(d_{i,i})}\\
    \geq& \frac{2E_n\tau}{\tau + 2DE_n^{a}} \sim O(E_n^{1-a}) .\
    \end{aligned}
$$
Therefore, the multigraph will be sparse provided $a<0.5$.
\end{proof}

\textbf{Theorem \ref{the:sparsity2}, restated}.
If $f_2$ satisfies Assumption 2, and if $\sigma > 0.5$, multigraphs distributed according to Equation~\ref{eqn:our_model} are sparse.

\begin{proof}
Within each cluster, senders and recipients are assigned to components according to two cluster-specific ddCRPs. If these ddCRPs were independent of one another, then each component would be associated with a unique vertex (as in the model described in Section~\ref{sec:basic_model}). Following Theorem~1 with $a=1$, by linearity of expectation, the expected total number of components would be linear in the number of edges.

However, the ddCRPs are not independent; instead they are coupled via the discrete base measure $H$. This means that, rather than sampling a vertex from some diffuse distribution, each component samples a vertex from $H$---meaning that multiple components are associated with the same vertex. As a result, the distribution over the number of distinct vertices per edge is equivalent, up to a multiplicative constant, to that of the edge-exchangeable graph of \citet{CraneDempsey2018}, who prove that the resulting graph is sparse. We restate their argument below:

Since $H$ is distributed according to a Pitman-Yor process, the number of distinct values associated with $k$ samples from $H$ (and hence, the number of edges with degree $k$ in a Pitman-Yor edge exchangeable model) is \cite{Pitman2002}
\begin{equation}
    \frac{\Gamma(\gamma + k + \sigma)\Gamma(\gamma+1)}{\sigma\Gamma(\gamma+k)\Gamma(\gamma+\sigma)} - \frac{\gamma}{\sigma} \simeq \frac{\Gamma(\gamma+1)}{\sigma\Gamma(\gamma+\sigma)}k^\sigma \, .\label{eqn:py_num_clusters}
\end{equation}

Since, in our model,  the number of components grows linearly with the number of edges $E_n$, by the law of iterated expectations the expected number distinct vertices $V_n$ grows as $O(E_n^\sigma)$ for $\sigma>0$. Therefore, the multigraph will be sparse provided $\sigma>0.5$.
\end{proof}

\section{Empirical evaluation of sparsity and power-law degree distribution}\label{sec:eval_sparsity}
In Figure~(\ref{fig:multigraph}), we empirically investigate the effect of $\sigma$ on the sparsity of multigraphs generated according to Equation~(\ref{eqn:our_model}). Recall that a model is considered sparse if the number of edges grows subquadratically with the number of vertices. Figure~(\ref{fig:multigraph}) plots the number of edges and number of vertices (on a log-log scale) for multigraphs with $\alpha=1$, $\gamma=1$, $\tau=0.2$, and various values of $\sigma$. Each dot represents a single sampled multigraph, and the blue dashed line has slope 2---providing the boundary between sparse and dense graphs. We see that, for $\sigma>0.5$, the number of edges grows subquadratically with the number of vertices, as expected according to Theorem~\ref{thm:sparseDND}. As we decrease $\sigma$, the graphs become denser. With $\sigma=0.3$, the number of edges is approximately quadratic in the number of vertices. With $\sigma=0$, corresponding to a DP-distributed base measure, the number of edges is superquadratic in the number of vertices.
\begin{figure*}[ht]
\centering
  \includegraphics[width=.4\textwidth] {plots/Multi_alpha_500_sigma_0-2.pdf}
  \includegraphics[width=.4\textwidth] {plots/Multi_alpha_500_sigma_30-2.pdf} \\
  \includegraphics[width=.4\textwidth] {plots/Multi_alpha_500_sigma_60_2.pdf}
  \includegraphics[width=.4\textwidth] {plots/Multi_alpha_500_sigma_70_2.pdf}
\caption{\small{Relationship between the number of edges and the number of vertices in {\textsc{DNND}}\xspace multigraphs generated according to Equation~(\ref{eqn:our_model}), for various values of $\sigma$. Plots are shown on a log-log scale. Different colors correspond to different random seeds. The blue dashed line has a slope of 2, indicating a quadratic relationship. We see that the multigraphs become increasingly sparse as $\sigma$ increases.}}\label{fig:multigraph}
\vspace{-3mm}
\end{figure*}

In Figure (\ref{fig:powerlaw}) we look at the degree distribution of simulated graphs generated according to {\textsc{DNND}}\xspace with a window decay function, with various settings of $\sigma$ and the window length $\lambda$, plotted on a log-log scale. As $\sigma$ increases, we see a clear power law distribution.  The shorter the window, the harder it is for the tables associated with vertices to persist long enough to obtain a high degree. Interestingly, for small values of $\lambda$, we seem to see a double power law distribution, something that has been observed in real-world communication networks. Exploring this power law behavior in more detail is an area for future research.

\begin{figure*}[ht]
\centering
  \includegraphics[width=.4\textwidth] {plots/pw_5_0_line.pdf}
  \includegraphics[width=.4\textwidth] {plots/pw_5_3_line.pdf} \\
  \includegraphics[width=.4\textwidth] {plots/pw_5_6_line.pdf}
  \includegraphics[width=.4\textwidth] {plots/pw_5_8_line.pdf}
\caption{\small{Degree distribution of simulated networks generated by {\textsc{DNND}}\xspace with $100K$ edges, for various values of $\sigma$. Plots are shown on a log-log scale. Different colors correspond to different window lengths for both decay functions, $f_1$ and $f_2$.}}\label{fig:powerlaw}
\end{figure*}

\section{Inference}\label{sec:inference_app}

In order to define our MCMC algorithm, we begin by introducing some auxiliary variables. Conditioned on the cluster assignments $z_i$, we follow a Chinese restaurant franchise-style representation, where we imagine each cluster as a restaurant, with two sets of tables: one for senders $s_i$ and one for recipients $r_i$. We let $g_i^s$ represent the table allocation of $s_i$, and $g_i^r$ represent the table allocation of $r_i$. All customers at a table are assigned to the same vertex; let $\eta_v$ be the total number of tables associated with vertex $v$.

Following \cite{BleiFrazier2011}, rather than sampling the cluster indicators $z_i$ directly, we instead assume each edge ``follows'' another edge, specified by a variable $c_i$.
Cluster assignments are then obtained as $z_i = i$ if $c_i=i$, or $z_i = z_{c_i}$ otherwise.
We sample the $c_i$, $g_i^s$, and $g_i^r$, along with a representation of $H$, by iterating through the following steps:

\paragraph{Sampling $\pmb{H}$.} Inspired by augmented representation schemes for the hierarchical Dirichlet process \cite{Teh:Jordan:Beal:Blei:2006}, we represent the infinite measure $H$ using a finite-dimensional vector $(h_1, h_2, \dots, h_{V_n}, h_{+})$, where $h_v$ for $v\leq V_{n}$ is the probability mass associated with vertex $v$, and $h_{+}$ is the probability mass associated with previously unseen vertices. Note that, in practice, $V_n$ is constant during training. Following Corollary 20 of \cite{Pitman1996}, we can sample
\begin{equation*}
(h_1, \dots, h_V, h_+) \sim \mbox{Dirichlet} (\eta_1 - \sigma, \dots, \eta_V - \sigma, \gamma + V \sigma).\
\end{equation*}

\paragraph{Sampling $\pmb{g_i^s}$ and $\pmb{g_i^r}$.} Conditioned on the clusters, all allowable table assignments (\textit{i.e.} all assignments where each table is associated with a single node) have equal likelihood, so we can Gibbs sample $g_i^s$ (and similarly, $g_i^r$) based on the conditional distribution
\begin{equation}
P(g_i^s|\{z_i, s_i\}) \propto \begin{cases} \sum_{j<i:z_j=z_i, s_j=s_i} f_2(d_{ij}) & \{j<i:z_j=z_i, s_j=s_i\} \neq \emptyset \\
\tau h_{s_i} & \mbox{otherwise}\end{cases}.\
\label{eqn:p_g}\end{equation}
We only sample the table assignments as auxiliary variables to allow us to sample the $h_v$; we discard them before sampling the cluster assignments $z_i$.

\paragraph{Sampling $\pmb{c_i}$/$\pmb{z_i}$.}
Following \cite{BleiFrazier2011}, we first set the $i$th link to follow itself, \textit{i.e.} $c_i=i$, and then sample a new value for $c_i$ based on the conditional probability that $c_i = j$,

\begin{equation}
P(c_i = j | E, c_{\neg i}, (h_1,\dots, h_V, h_+)) \propto
\begin{cases} f(d_{ij}) P(\mathcal{E}|c_i=j, c_{\neg i}, (h_1,\dots, h_V, h_+)) & i\neq j \\
\alpha P(\mathcal{E}|c_i=j, c_{\neg i}, (h_1,\dots, h_V, h_+)) & i=j\end{cases}\label{eqn:p_c}
\end{equation}
where $\mathcal{E} = \left((s_1, r_1), (s_2, r_2), \dots \right)$ represents the edge structure of the graph. We can write
\begin{equation}
P(\mathcal{E}|\{c_i\}, (h_1,\dots, h_V, h_+)) = \prod_k P_k
\end{equation}
where $P_k$ is the likelihood associated with the $k$\textsuperscript{th} cluster,

$$P_k = \prod_{i:z_i = k} P(s_i|\{s_j, r_j: j<i, z_j=k\})P(r_i|\{s_j, r_j: j<i, z_j=k\})$$

where

$$P(s_i = v|\{c_{<i}, s_{<i}, r_{<i}) \propto \tau h_v +  \sum_{j<i:s_j=v} f_2(d_{ij}).$$

In practice, we only need to calculate the likelihoods associated with clusters whose occupancy changes based on the proposed move.

Pseudo-code is given in Algorithm \ref{alg:inference}. We assume gamma priors on $\alpha$, $\tau$, $\gamma$ and both decay windows $\lambda$, and a beta prior on $\sigma$, and sample from their posterior distributions using Metropolis-Hastings, as shown in Algorithm~\ref{alg:inference}.

\begin{algorithm}[t!]
	\begin{algorithmic}[1]
	\STATE Initialize $h_v \leftarrow \frac{1}{|V|+1}$ for $v=1,\ldots,|V|$
	\STATE Initialize $z_i \leftarrow 0$, for every edge $i$
	\STATE Initialize $c_0 \leftarrow 0; c_i \leftarrow c_{i-1}$
	\FOR {each epoch}
	\FOR {$i \in \{1,\ldots,N\}$}
	\STATE Sample table allocations $g_i^s, g_i^r$ following Equation~\ref{eqn:p_g}
	\ENDFOR
	\STATE Sample $(h_1,\ldots,h_V, h_+) \sim DP(\eta_1-\sigma,\ldots, \eta_V-\sigma, \gamma+|V|\sigma )$

	\FOR {$i \in \{1,\ldots,N\}$}
	\STATE Let $c_i\leftarrow i$, and update all affected cluster assignments.
	\STATE Sample $c_i$ according to Equation~\ref{eqn:p_c}
	\STATE Update all affected cluster assignments.
	\ENDFOR
	\STATE Propose $\alpha^{*} \sim \mathcal{N}(\alpha,\nu^2)$ for some step size $\nu$
	\STATE Set $\alpha \leftarrow \alpha^*$ with probability $\min(1, \frac{\mbox{Gamma}(\alpha^*|\alpha_0, \alpha_1) \prod_i p(c_i|\alpha^*, c_{<i})}{\mbox{Gamma}(\alpha|\alpha_0, \alpha_1) \prod_i p(c_i|\alpha, c_{<i})})$
	\STATE Propose $\tau^{*} \sim \mathcal{N}(\tau,\nu^2)$
	\STATE Set $\tau \leftarrow \tau^*$ with probability $\min(1, \frac{\mbox{Gamma}(\tau^*|\tau_0, \tau_1) \prod_i p(s_i, r_i|\tau^*, \{h_v\}, s_{<i}, r_{<i}, c_{<i})}{\mbox{Gamma}(\tau|\tau_0, \tau_1) \prod_i p(s_i, r_i|\alpha, \{h_v\}, s_{<i}, r_{<i}, c_{<i})})$
	\STATE Propose $\gamma^{*} \sim \mathcal{N}(\gamma,\nu^2)$
	\STATE Set $\gamma \leftarrow \gamma^*$ with probability $\min(1, \frac{\mbox{Gamma}(\gamma^*|\gamma_0, \gamma_1) \mbox{Dirichlet}(h_1, \dots, h_V, h_+|\eta_1-\sigma, \dots, \eta_V-\sigma, \gamma^*+|V|\sigma)}{\mbox{Gamma}(\gamma|\gamma_0, \gamma_1) \mbox{Dirichlet}(h_1, \dots, h_V, h_+|\eta_1-\sigma, \dots, \eta_V-\sigma, \gamma+|V|\sigma)}$
	\STATE Propose $\sigma^{*} \sim \mathcal{N}(\gamma,\nu^2)$
	\STATE Set $\sigma \leftarrow \sigma^*$ with probability $\min(1, \frac{\mbox{Beta}(\sigma^*|\sigma_0, \sigma_1) \mbox{Dirichlet}(h_1, \dots, h_V, h_+|\eta_1-\sigma^*, \dots, \eta_V-\sigma^*, \gamma+|V|\sigma^*)}{\mbox{Beta}(\sigma|\sigma_0, \sigma_1) \mbox{Dirichlet}(h_1, \dots, h_V, h_+|\eta_1-\sigma, \dots, \eta_V-\sigma, \gamma+|V|\sigma)}$
	\STATE Propose $\lambda^{*} \sim \mathcal{N}(\lambda_{f_1},\nu^2)$ for some step size $\nu$
	\STATE Set $\lambda_{f_1} \leftarrow \lambda^*$ with probability $\min(1, \frac{\mbox{Gamma}(\lambda^*|\lambda_0, \lambda_1) \prod_i p(c_i|\lambda^*, c_{<i})}{\mbox{Gamma}(\lambda_{f_1}|\lambda_0, \lambda_1) \prod_i p(c_i|\lambda, c_{<i})})$
	\STATE Propose $\lambda^{*} \sim \mathcal{N}(\lambda_{f_2},\nu^2)$ for some step size $\nu$
	\STATE Set $\lambda_{f_2} \leftarrow \lambda^*$ with probability $\min(1, \frac{\mbox{Gamma}(\lambda^*|\lambda_0, \lambda_1) \prod_i p(s_i, r_i|\lambda^*, \{h_v\}, s_{<i}, r_{<i}, c_{<i})}{\mbox{Gamma}(\lambda_{f_2}|\lambda_0, \lambda_1) \prod_i p(s_i, r_i|\alpha, \{h_v\}, s_{<i}, r_{<i}, c_{<i})})$
	\ENDFOR

	\end{algorithmic}
	\caption{{\textsc{DNND}}\xspace-Inference}
	\label{alg:inference}
\end{algorithm}

\subsection{Left-to-Right Evaluation Algorithm}\label{subsec:letfright}
\begin{algorithm}[t!]
	\begin{algorithmic}[1]
		\STATE initialize $l \leftarrow 0$
		\FOR {$i=N+1, \ldots,N+n$}
		\STATE initialize $p_i \leftarrow 0$
		\FOR {$m=1\ldots M$}
		\FOR {$i' < i$}
		\STATE Sample $c_{i'}^{(m)} \sim P(c_{i'}^{(m)} |(s_{i'},r_{i'}),c_{<i'}^{(m)}, \mathcal{C} , \mathcal{C'}_{<i'},\mathcal{G},\mathcal{G}'_{<i'})$
		\STATE Sample $g_{i'}^{s,(m)} \sim P(g_{i'}^{s,(m)} |c_{i'}^{(m)},(s_{i'},r_{i'}),g_{<i'}^{s,(m)}, \mathcal{C} , \mathcal{C'}_{<i'},\mathcal{G},\mathcal{G}'_{<i'})$
		\STATE Sample $g_{i'}^{r,(m)} \sim P(g_{i'}^{r,(m)} |c_{i'}^{(m)},(s_{i'},r_{i'}),g_{<i'}^{r,(m)}, \mathcal{C} , \mathcal{C'}_{<i'},\mathcal{G},\mathcal{G}'_{<i'})$
		\ENDFOR
		\STATE $\begin{aligned}
              p_i \leftarrow p_i &+ \sum_k^{K_i} P(s_i,r_i|c_i^{(m)}=k, g_{i}^{s,(m)}, g_{i}^{r,(m)}) \\
                &\times P(c_i^{(m)}=k,g_{i}^{s,(m)}, g_{i}^{r,(m)} |\mathcal{C}'_{<i}, \mathcal{G}'_{<i}, \mathcal{C}, \mathcal{G})\end{aligned}$
		\ENDFOR
		\STATE $p_n \leftarrow p_n/M$
		\STATE $l \leftarrow l+\log p_n$
		\ENDFOR
	    \STATE $\log P(\mathcal{E}'|\mathcal{C},\mathcal{G}) \simeq l$
	\end{algorithmic}
	\caption{``left-to-right'' evaluation algorithm}
	\label{alg:left-to-right}
\end{algorithm}
In our experimental analysis, we compare different edge-based models in terms of their estimated test set probabilities: higher probabilities suggests we have better captured the structure underlying the data. In unsupervised models for sequences of observations---such as the graph models considered in this paper, or language models---it is hard to estimate the probability of a new sequence, since the probability of any specific sequence is vanishingly small, and often depends on the setting of latent variables such as the cluster allocations in our model, or the topic allocations in topic models. \citet{Wallach:2009:EMT:1553374.1553515} consider a number of methods to estimate these probabilities. The paper looks at the setting of topic models, but the findings generalize to sequences of edges. We use their ``left-to-right'' algorithm, which they found to be a good estimator of the true test set probability. We summarize this algorithm below, in the context of our model.

Given a sequence of edges $\mathcal{E} = (s_1,r_1),  \dots, (s_N, r_N)$, with their associated cluster assignments $\mathcal{C} = c_1, \dots, c_N$ and table assignments $\mathcal{G} = (g_1^s, g_1^r), \dots, (g_N^s, g_N^r)$, then the probability of a held-out data set $\mathcal{E}' = (s_{N+1},r_{N+1}), \dots, (s_{N+n}, r_{N+n})$ is given by

\begin{equation}\label{eqn:lda}
\begin{aligned}
    P(\mathcal{E}'|\mathcal{C}, \mathcal{G}) =& \sum_{\mathcal{C'},\mathcal{G}'} P(\mathcal{E}'|\mathcal{C'},\mathcal{G}')P(\mathcal{C'},\mathcal{G}'|\mathcal{C},\mathcal{G})  \\
    =& \prod_{i=N+1}^{N+n}\sum_{\mathcal{C}'_{<i},\mathcal{G}'_{<i}}P(s_i, r_i|c_i, g_i^s, g_i^r)P(c_i, g_i^s, g_i^r|\mathcal{C}'_{<i},\mathcal{G}'_{<i}, \mathcal{C}, \mathcal{G})
    \end{aligned}
\end{equation}
where $\mathcal{C}' = c_{N+1}, \dots, c_{N+n}$, $\mathcal{C}'_{<i} = c_{N+1}, \dots, c_{i}$, and $\mathcal{G}', \mathcal{G}'_{<i}$ are defined analogously, and the summations are over all possible values of $\mathcal{C}'$ and $\mathcal{G}'$ (or $\mathcal{C}'_{<i}$. and $\mathcal{G}'_{<i}$).

We can then approximate the terms in Equation~\ref{eqn:lda} using the sequential algorithm described in Algorithm \ref{alg:left-to-right}, where $M$ can be seen as analogous to the number of particles in a particle filtering algorithm.
\section{Additional experimental results}\label{app:results}
Table~(\ref{tbl:hitall}) expands Tables~(\ref{tbl:hits}) and (\ref{tbl:aps}) to include standard deviation across 10 repeats and results for each of the three decay functions.

\begin{table*}[ht]
\parbox{\textwidth}{
\caption{\small{hits@$\mathtt{k}$ and AP@$\mathtt{k}$ of three decay functions}\vspace{-2mm}}
\centering
\scriptsize
\resizebox{1\textwidth}{!}{
\begin{tabular}{|c|ccc|ccc|ccc|}
	\toprule
	& \multicolumn{3}{|c|}{CollegeMsg} &\multicolumn{3}{|c|}{EmailEu} & \multicolumn{3}{|c|}{SocialEv} \\
	\midrule
	\textit{hits@$\mathtt{k}$} & @10 & @20 & @50& @10 & @20 & @50 & @10 & @20 & @50  \\
	\midrule
	{\textsc{DNND}}\xspace-\textsc{MDND}&
	0.5 $\pm$ 0.08 & 0.63 $\pm$ 0.1 & 0.96 $\pm$ 0.02 &
	0.94 $\pm$ 0.04 & \textbf{0.96 $\pm$ 0.06} & 0.96 $\pm$ 0.05 &
    0.74 $\pm$ 0.25 &0.91 $\pm$ 0.12 & \textbf{1.0 $\pm$ 0.01}  \\
	{\textsc{DNND}}\xspace-\textsc{Window} &
	0.32 $\pm$ 0.12 & 0.67 $\pm$ 0.18 & 0.91 $\pm$ 0.07 &
	\textbf{0.98 $\pm$ 0.04} & 0.94 $\pm$ 0.06 & 0.97 $\pm$ 0.04 &
	0.72 $\pm$ 0.29 &0.92 $\pm$ 0.13 & 0.98 $\pm$ 0.05 \\
	{\textsc{DNND}}\xspace-\textsc{Logistic}&
	\textbf{0.62 $\pm$ 0.17} & \textbf{0.78 $\pm$ 0.08} & \textbf{0.98 $\pm$ 0.01} &
	0.92 $\pm$ 0.11 & 0.89 $\pm$ 0.05 & 0.94 $\pm$ 0.11&
	0.78 $\pm$ 0.22 & \textbf{0.98 $\pm$ 0.03} & \textbf{1.0 $\pm$ 0.0} \\
	{\textsc{DNND}}\xspace-\textsc{Exponential}&
	0.55 $\pm$ 0.15 & 0.7 $\pm$ 0.07 & 0.92 $\pm$ 0.05 &
	0.96 $\pm$ 0.08 & 0.92 $\pm$ 0.06 & \textbf{0.99 $\pm$ 0.02} &
	0.68 $\pm$ 0.28 &0.93 $\pm$ 0.13 & 0.99 $\pm$ 0.01  \\
	\midrule
	{\textsc{DNND}}\xspace-\textsc{DRGPM}&
	0.06 $\pm$ 0.09 & 0.06 $\pm$ 0.07 & 0.06 $\pm$ 0.05&
	0.3 $\pm$ 0.01 & 0.21 $\pm$ 0.01 & 0.23 $\pm$ 0.03&
	0.21 $\pm$ 0.4 &0.21 $\pm$ 0.4 &0.21 $\pm$ 0.4\\
	{\textsc{DNND}}\xspace-\textsc{DPGM}&
	0.14 $\pm$ 0.07 & 0.15 $\pm$ 0.06 & 0.14 $\pm$ 0.06 &
	0.28 $\pm$ 0.03 & 0.21 $\pm$ 0.01 & 0.25 $\pm$ 0.02 &
	0.16 $\pm$ 0.22 &0.16 $\pm$ 0.22 &0.1 $\pm$ 0.22 \\
	{\textsc{DNND}}\xspace-\textsc{DGPPF}&
	0.17 $\pm$ 0.12 & 0.17 $\pm$ 0.09 & 0.16 $\pm$ 0.05 &
	0.32 $\pm$ 0.01 & 0.2 $\pm$ 0.02 & 0.2 $\pm$ 0.01  &
	0.36 $\pm$ 0.47 &0.36 $\pm$ 0.47 &0.35 $\pm$ 0.47\\
	\midrule
	\textit{AP@$\mathtt{k}$} & @10 & @20 & @50& @10 & @20 & @50 & @10 & @20 & @50  \\
	\midrule
	{\textsc{DNND}}\xspace-\textsc{MDND}&
	0.43 $\pm$ 0.02 & 0.33 $\pm$ 0.04 & 0.2 $\pm$ 0.03 &
	0.66 $\pm$ 0.08 & 0.41 $\pm$ 0.03 & \textbf{0.18 $\pm$ 0.02} &
    0.17 $\pm$ 0.05 & 0.1  $\pm$ 0.03 & 0.04 $\pm$ 0.01 \\
	{\textsc{DNND}}\xspace-\textsc{Window} &
	0.63 $\pm$ 0.07 & 0.39 $\pm$ 0.06 & 0.23 $\pm$ 0.04 &
	0.66 $\pm$ 0.06 & 0.42 $\pm$ 0.03 & \textbf{0.18 $\pm$ 0.01} &
	\textbf{0.25 $\pm$ 0.05} & \textbf{0.16 $\pm$ 0.03} & \textbf{0.13 $\pm$ 0.01} \\
	{\textsc{DNND}}\xspace-\textsc{Logistic}&
	0.63 $\pm$ 0.09 & \textbf{0.43 $\pm$ 0.06} &  \textbf{0.26 $\pm$ 0.04} &
	0.66 $\pm$ 0.06 & 0.42 $\pm$ 0.06 & \textbf{0.18 $\pm$ 0.02} &
	0.18 $\pm$ 0.02 & 0.12 $\pm$ 0.03 & 0.1  $\pm$ 0.01 \\
	{\textsc{DNND}}\xspace-\textsc{Exponential}&
	\textbf{0.64 $\pm$ 0.15} & 0.39 $\pm$ 0.09 & 0.21 $\pm$ 0.04 &
	\textbf{0.73 $\pm$ 0.06} & \textbf{0.43 $\pm$ 0.04} & \textbf{0.18 $\pm$ 0.02} &
	0.18 $\pm$ 0.03 & 0.13 $\pm$ 0.03 & 0.09 $\pm$ 0.02  \\
	\midrule
	{\textsc{DNND}}\xspace-\textsc{DRGPM}&
	0.09 $\pm$ 0.03 & 0.05 $\pm$ 0.01 & 0.02 $\pm$ 0.01&
	0.21 $\pm$ 0.0 & 0.14 $\pm$ 0.0 & 0.1 $\pm$ 0.0  &
	0.06 $\pm$ 0.05 & 0.03 $\pm$ 0.02 & 0.01 $\pm$ 0.01\\
	{\textsc{DNND}}\xspace-\textsc{DPGM}&
	0.1 $\pm$ 0.02 & 0.05 $\pm$ 0.01 & 0.02 $\pm$ 0.0&
	0.16 $\pm$ 0.0 & 0.14 $\pm$ 0.0 & 0.12 $\pm$ 0.0 &
	0.05 $\pm$ 0.06 & 0.02 $\pm$ 0.03 & 0.01 $\pm$ 0.01\\
	{\textsc{DNND}}\xspace-\textsc{DGPPF}&
	0.1 $\pm$ 0.0 & 0.05 $\pm$ 0.0 & 0.02 $\pm$ 0.0&
	0.22 $\pm$ 0.0 & 0.17 $\pm$ 0.0 & 0.1 $\pm$ 0.0&
	0.06 $\pm$ 0.05 & 0.03 $\pm$ 0.03 & 0.01 $\pm$ 0.01\\
	\hline
\end{tabular}
}
\label{tbl:hitall}
}
\end{table*}

\section{Inference}\label{sec:inference}

We provide pseudo-code in Appendix \ref{sec:inference_app}.

\paragraph{Complexity.} The complexity of our model is $O(|E|\times K)$, where $K$ is the number of clusters. The complexity of blockmodel-based models is $O(|V|^2 \times K)$. For sparse graphs, we have $|E| << |V|^2$. In practice, the runtimes of the different models were comparable on the datasets we considered. We note that only hyperparameter sampling uses Metropolis Hastings; the cluster assignments are sampled directly from the posterior conditioned on the hyperparameters.

\iffalse
We perform inference using a sequential Monte Carlo algorithm that approximates the posterior distribution using a swarm of sequentially updated particles \cite{doucet2001introduction}. Using a familiar restaurant analogy, we say that the per-cluster ddCRPs assign senders or recipients of edges to tables, and each table selects a vertex indicator from $H$. Let $b_i^s$ and $b_i^r$ be the table assignments of the $i$th sender and recipient, respectively, and let $\phi_i = (z_i, b_i^{s}, b_i^{r})$ be the set of edge-specific latent parameters for the $i$th edge. Each particle $p$ proposes values for $\phi_i$ according to a proposal distribution $Q(\phi_i^{(p)}|s_i, r_i, \phi_{<i}^{(p)})$, and calculates appropriate importance weights.

In our case, we can analytically evaluate $P(\phi_i^{(p)}|s_i, r_i, \phi_{<i}^{(p)})$, so we use this as our proposal distribution. We can then calculate the importance weights $w_i$ as
$$\begin{aligned}\frac{w_i}{w_{i-1}} \propto& \frac{P(s_i, r_i|\phi_i^{(p)}) pP\phi_i^{(p)}|\phi_{<i}^{
(p)})}{Q(\phi_i^{(p)}|s_i, r_i, \phi_{<i}^{(p)})}\\
=&P(s_i, r_i|\phi^{(p)}_{<i}) .\ \end{aligned}$$
We resample our particles based on the weights $w_i$ whenever the effective sample size drops below 10\% of the number of particles. We include pseudocode and provide analytic expressions for $Q(\phi_i^{(p)}|s_i, r_i, \phi_{<i}^{(p)})$ and $p(s_i, r_i|\phi^{(p)}_{<i})$ in the appendix, and include code with this submission

Evaluating the necessary probabilities scales as $O(EK)$, where $E$ is the number of edges and $K$ is the number of clusters. The resampling step adds a cost of $O(P^2)$, where $P$ is the number of particles, making the overall complexity $O(P(EK+P))$. For comparison, the complexity of obtaining $P$ MCMC samples in blockmodel-based  models is $O(PV^2K)$, where $V$ is the number of vertices. For sparse graphs, we have $|E| \ll |V|^2$.

\fi

redpajama_set_name: RedPajamaArXiv


Speaking at the Capital Club Business meeting in Bahrain, President Rodrigo Duterte tells all Filipinos working in Bahrain to follow their laws and rules religiously so that there won't be troubles.
"So that's one commitment, the second commitment is I'd like to ask every Filipino listening now. We are here on the good graces of Bahrain, Kingdom of Saudi Arabia, just follow rules just like in my country and nothing really troubles us," he said.
" Follow regulation, respect the culture, respect the law and we will have the best of the relations. I give that commitment," Duterte added.
The President urged Filipino workers to show their best behavior in Bahrain because they respect the Filipinos there.
"I will be talking to them again after this. And I will remind of your goodness, your goodwill, your kindness and just to pay back what do you have enjoying so far is just, do not create trouble for the government of Bahrain, just follow the rules, respect the culture and you have a good paying job here indirectly," he said.
"Do you know why, Your Excellency, your Royal Highness? Indirectly, you have helped educate the Filipino back home. We can go to school, they can get a good education. Maybe a comfortable life better than the others.," he said.
Duterte also pointed out how OFWs help in the economic development.
"Because of the millions of Filipinos here in the Middle East. They remit the money to support their children acquire an education which they cannot afford if they are there. So it's the job opportunity that by itself is a debt of gratitude. We want to repay," he added.


text:
Todd McKenney
Australia - NSW
Singer / Musician
Inspiring, provocative, compelling radio host, film actor, musical theatre performer, television personality, Todd McKenney knows showbiz from every angle. Todd has worked across stage, screen, television and radio.
Todd has enjoyed his role as a judge on Channel 7's immensely popular "Dancing with the Stars". He has also hosted Channel 7's National Spelling Bee and been a guest presenter on The Morning Show with Kylie Gillies.
Todd has been in the entertainment industry for years. He has represented Australia in ballroom and Latin American dancing, winning many international dancing titles - perfect training for his role as Nathan Starkey in Baz Luhrmann's internationally acclaimed film Strictly Ballroom.
He was cast in his first professional musical, Andrew Lloyd Webber's Song and Dance. From here Todd's career has followed a very neat trajectory. From chorus roles in shows like Born Yesterday for The Sydney Theatre Company, Pirates of Penzance and Camelot, he moved on to small roles like Phaedra in La Cage Aux Folles and Tumblebrutus and Rum Tum Tugger in Cats during its Melbourne season. He then landed lead roles in 42nd Street (Billy Lawlor) and West Side Story (Riff). The role of Emcee in Cabaret was a huge success for Todd. In Crazy for You he proved he had what it takes to become a star when he took over the lead role from American actor Jim Walton, who broke his leg on opening night, with only one days notice.
After landing the prized role of Peter Allen in the critically acclaimed Australian hit The Boy from Oz, Todd played the role for 766 performances.
It was for his portrayal as Peter that Todd received two Mo Awards, the Variety Club Heart Award, the Glugg Award, the Green Room Award, the Australian Dance Award and 2 Helpmann Awards. Todd also won the Mo Award in the Versatile Variety Performer of the Year category.
Singin' In The Rain was a huge opportunity to see Todd at his dancing best as he recreated Gene Kelly's original choreography on stage. Todd received a further Australian Dance Award for his performance.
Todd then starred opposite stage legend Nancye Hayes in The Ensemble Theatre's production of the play Six Dance Lessons in Six Weeks which toured Australia to huge critical acclaim.
Whilst balancing his roles as breakfast radio host for Sydney radio station Mix 106.5 and judge on Dancing With The Stars Todd starred in the musical hit Priscilla Queen Of The Desert for which he received rave reviews and another Helpmann Award nomination.
Todd also constructed his own show Todd McKenney Live which played to full houses for a year all around Australia including Sydney's Star City Casino, Melbourne's Crown Casino and Jupiters Casino on the Gold Coast.
He has been studying 'Auslan' sign language and works within the deaf community all around Australia. He has also recently joined 'The Diamond Ball Committee' for the Children's Cancer Institute Australia and hopes to help the CCIA to raise much needed funds to help research and fight childhood cancer.
Todd is an accomplished MC and corporate host who is always in high demand.
Thanks again for organising Todd McKenny for the Australian International Movie Convention, he was fantastic and such a professional to deal with.
- CEO, SCREAM
Presenter Type: Speaker, Entertainer
Fee Range: $10,000-$15,000
Travels From: Australia - NSW
Abbey Gelmi
Abbey is an outstanding and experienced MC and is available to MC at various events Australia-wide. Abbey is also a part of the wider Seven Sport family being a part of the network's AFL, Motorsport, Cricket and Racing coverage throughout the year. Having worked nationally as a presenter, host, MC and report, Abbey not only brings a wealth of experience and knowledge to any role.
Award-winning entrepreneur, author and inspiring keynote speaker on a global mission to unlock creativity, increase productivity and accelerate innovation.
Stephanie Brantz
Freelance television sport presenter, reporter, producer and commentator and sits on the Board of Directors of Football NSW.
Kemi Nekvapil
Regarded as one of Australia's most sought after speakers and facilitators, and recognised as a leading coach for female executives and entrepreneurs, Kemi is known for her unique ability to empower meaningful action and sustainable growth. Having trained with Dr. Brene Brown, she is a Certified Dare to Lead™ Facilitator and a powerful advocate for courageous leadership in life.
Ruby & Steele
Bringing glamour & stadium experience to your event.

redpajama_set_name: RedPajamaCommonCrawl


Join us on March 2nd and hit the slopes or just enjoy a day in the mountains. Meet up in the morning at 9:30am and again for lunch from 12:00pm-1:00pm. This event is a Free RMRPPA Member Meet-Up, and make sure to sign up so you can get the complete details. There is an option to take a FREE shuttle up and back! Spots are limited, so rsvp as soon as possible. Once in Breckenridge we will meet at the TBar Restaurant at Peak 8 in the morning and at lunch (see map below). Contact Julie at info@rmrppa.org or 800-819-1208 for more details. Pro Tip: Get your lift ticket before heading up to save some cash!
Enjoy the slopes without the stress and ride the Free RMRPPA Ski Shuttle! Space is limited so sign up soon to reserve your spot! We'll meet at 6:45 AM at the Wooly Mammoth Parking Lot in Golden. You must RSVP to Julie Schoenbauer (email) to ride the shuttle. On the day of the event, please contact Andrew at 970-294-1974 with questions about the shuttle.
Thank you to the shuttle company, Mountain Grit, and to our event sponsors below!