% !TEX TS-program = pdflatexmk
\documentclass{article}

\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage[a4paper, total={5.5in, 8in}]{geometry}
\usepackage{amsthm}
\usepackage{natbib}


\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem{example}{Example}[definition]
\newtheorem{remark}{Remark}

\newtheorem{theorem}[definition]{Theorem}
%\newtheorem{theorem}{Theorem} %This is the example presented in the introduction but it has the additional parameter [section] that restarts the theorem counter at every new section.
\newtheorem{corollary}{Corollary}[definition] %A environment called corollary is created, the counter of this new environment will be reset every time a new definition environment is used.
\newtheorem{lemma}[definition]{Lemma} %In this case, even though a new environment called lemma is created, it will use the same counter as the definition environment.

\title{Exchangeable Array and Random Graph}
\date{\today}
\author{Dongwoo Kim\\ANU}

\begin{document}

\maketitle

\section{Exchangeable array for graph}
\begin{definition}[Jointly exchangeable array] A random 2-array $(X_{ij})_{i,j\in \mathbb{N}}$
is jointly exchangeable if
\begin{align}
(X_{ij}) \stackrel{d}{=} (X_{\pi(i)\pi(j)}) \quad \text{for } i,j \in \mathbb{N}^2
\end{align}
for any permutation $\pi$ of $\mathbb{N}$.
\end{definition}

\begin{theorem}[\label{aldous_hoover}Aldous, Hoover Theorem \citep{aldous1981representations,hoover1979relations}] A random 2-array $(X_{ij})_{i,j\in \mathbb{N}}$
is jointly exchangeable if and only if there exists a random measurable function $f:[0,1]^3 \rightarrow \mathcal{X}$ such that
\begin{align}
(X_{ij}) \stackrel{d}{=} (f(U_i, U_j, U_{ij})),
\end{align}
where $(U_{i})_{i \in \mathbb{N}}$ and $(U_{ij})_{ij\in\mathbb{N}^2}$ with $U_{ij} = U_{ij}$ are a sequence and matrix of i.i.d. Uniform[0,1] random variables.
\end{theorem}
If the function $f$ is a symmetric in its first two argument, then the matrix $X$ is symmetric. In general, however, it does not need to be a symmetric (e.g. directed graph).

For the undirected graph case $\mathcal{X} = \{0,1\}$, the theorem can be simplified further through a random function called \textit{graphon} $W:[0,1]^2 \rightarrow [0,1]$, symmetric in its arguments, where
\[ f(U_i, U_j, U_{ij}) = 
  \begin{cases}
    1       & \quad U_{ij} < W(U_i, U_j)\\
    0  & \quad \mathrm{otherwise}\\
  \end{cases}
\]

\begin{example}[Random function prior on function $f$ \citep{Lloyd2013}] Lloyd et al. use a Gaussian process prior to define function $f$ for an undirected graph. They define $W(U_i, U_j) = \phi(\Theta(U_i,U_j))$ where $\phi$ is a logistic function, and $\Theta(\cdot, \cdot)$ is a continuous function with a Gaussian process prior. Thus, the probability of edge between node $i$ and $j$ is equal to Bernoulli$(\phi(\Theta(U_i,U_j)))$.
\end{example}

\begin{example}[Stochastic block model] The stochastic block model is another generative model for random graphs. The model assumes that each node belongs to a community and there is a edge probability between communities. Then the probability of edge between two different nodes are determined by the edge probability between communities where the two nodes belong. In stochastic block model with Aldous, Hoover Theorem, $U_i$ and $U_j$ determine the communities of node $i$ and $j$, respectively, and $U_{ij}$ determines the existence of edge between node $i$ and $j$ as done in graphon. The stick breaking process is one way to partition unit length interval into an infinite number of communities \citep{sethuraman1994constructive}.
\end{example}

\begin{definition}[Sparse Graph]
Let the number of nodes in a graph be $n$. The graph is sparse if the number of edges are $o(n^2)$ or dense if the number of edges are $\Theta(n^2)$.
\end{definition}

\begin{remark}[Graphon is trivially dense]
Every graph represented by graphon $W$ are either empty or dense. The asymptotic proportion of edges is $p = \frac{1}{2}\int W(x, y) dxdy$ and the graph is hence either empty $(p=0)$ or dense (since $O(pn^2) = O(n^2)$).
\end{remark}

In \citep{Lloyd2013}, the authors place a Gaussian process prior over graphon $W:[0,1]^2 \rightarrow \mathbb{R}$ and transform the output through the logistic function to model the edge probability between nodes.

For the undirected graph case where $X_{ij} = X_{ji}$, one can sample upper triangle of the adjacency matrix, and use the same result for the lower triangle. For the directed graph case, however, the adjacency matrix is no longer symmetric, also, by the theorem, both $X_{ij}$ and $X_{ji}$ rely on single parameter $U_{ij}$. Therefore, one should jointly sample ($X_{ij}$, $X_{ji}$) together from three parameters $U_{i}, U_{j}, U_{ij}$, which means $X_{ij}$ and $X_{ji}$ are not conditionally independent. In addition, asymmetric graphon $W$ could be employed for directed random graph. However, \citep{Cai2015} show that assymetric graphon is inappropriate to impose certain structures on a graph such as the partial ordering and propose a class of priors for directed graphs.

\section{Exchangeable array for matrix factorisation}
Jointly exchangeable array assume that both rows and columns index the same entities. However, the assumption does not hold for the general matrix where rows and columns represent different entities (e.g. users and items in recommendation system).

\begin{definition}[Separately exchangeable array]A random 2-array $(X_{ij})_{i,j\in \mathbb{N}}$ is separately exchangeable if
\begin{align}
(X_{ij}) \stackrel{d}{=} (X_{\pi(i)\sigma(j)}) \quad \text{for } i,j \in \mathbb{N}^2
\end{align}
for any permutation $\pi$ and $\sigma$ of $\mathbb{N}$.
\end{definition}

\begin{corollary}[\label{sea}Separately exchangeable array] A random 2-array $(X_{ij})$ is separately exchangeable if and only if there exists a random measurable function $f:[0,1]^3 \rightarrow \mathcal{X}$ such that
\begin{align}
(X_{ij})  \stackrel{d}{=} (f(U_i, U_j, U_{ij})),
\end{align}
where $(U_i)_{i\in \mathbb{N}}$, $(U_j)_{j\in \mathbb{N}}$, and $(U_{ij})_{ij\in \mathbb{N}^2}$ are i.i.d. Uniform[0,1] random variables.
\end{corollary}
In the separately exchangeable array case, function $f$ is not a symmetric in its first two arguments.

\begin{example}[Probabilistic matrix factorisation (PMF) \citep{Salakhutdinov2008}] 
PMF is one instantiation of Corollary \ref{sea}. Let the generative process of PMF be
\begin{align}
U_i &\sim \mathcal{MN}_d(0, \Sigma_U)\\
V_j &\sim \mathcal{MN}_d(0, \Sigma_V)\\
X_{ij} &\sim \mathcal{N}(U_i^\top V_j, \sigma_x)
\end{align}
where $\mathcal{MN}_d$ is a $d$-dimensional zero-mean multivariate normal distribution with covariance $\Sigma$. This corresponds to random measurable function
$f(U_i, U_j, U_{ij}) = \Phi_1(U_{ij}; \Phi_d(U_i;0, \Sigma_{U})^\top \Phi_d(U_j;0, \Sigma_{U}), \sigma^2_x)$, where $\Phi_d(\cdot;\mu, \sigma^2)$ is an inverse-CDF of $d$-dimensional multivariate function with mean $\mu$ and variance $\sigma^2$. Note that $\sigma$ here differs from the permutation notation.
\end{example}

\section{Exchangeable array for knowledge graph}

A knowledge graph can be represented as a 3-array tensor $X_{ijk}$, where the first two dimensions represent entities, and the third dimension represent relations. Therefore, $X_{ijk}$ is jointly exchangeable in its first two dimensions, and the third dimension is separately exchangeable to the first two dimensions.

\begin{definition}[$\pi$-exchangeable array for knowledge graph \citep{Orbanz2015}]A random 3-array $(X_{ijk})_{i,j,k\in \mathbb{N}}$ is jointly exchangeable in its first two dimensions and separately exchangeable with the third dimension if
\begin{align}
(X_{ijk}) \stackrel{d}{=} (X_{\pi(i)\pi(j)\sigma(k)}) \quad \text{for } i,j,k \in \mathbb{N}^3
\end{align}
for any permutation $\pi$ and $\sigma$ of $\mathbb{N}$.
\end{definition}


\begin{corollary}[$\pi$-exchangeable array for knowledge graph]
A random 3-array $X_{ijk}$ is jointly exchangeable in its first two dimension and separately exchangeable for the third dimension if and only if there exists a random measurable function $f:[0,1]^7 \rightarrow \mathcal{X}$ such that
\begin{align}
(X_{ijk})  \stackrel{d}{=} (f(U_i, U_j, U_k, U_{ij}, U_{ik}, U_{jk}, U_{ijk})),
\end{align}
where $(U_i)_{i\in \mathbb{N}}$, $(U_k)_{k\in \mathbb{N}}$, $(U_{ij})_{ij\in \mathbb{N}^2}$, $(U_{ik})_{ik\in \mathbb{N}^2}$, and $(U_{ijk})_{ijk\in \mathbb{N}^3}$  are i.i.d. Uniform[0,1] random variables.
\end{corollary}

\begin{remark}[Compositional model \citep{gu2015traversing}] Compositional vector space models cannot be modelled through the exchangeable array theorem because the dependency between triples breaks the exchangeability.
\end{remark}

\begin{example}[Bayesian RESCAL (BRESCAL)] The generative process of BRESCAL with normally distributed output variable $X_{ijk}$ is as follows:
\begin{align}
e_i, e_j &\sim \mathcal{MN}_d(0, \sigma_e^2 I_d)\\
R_k &\sim \mathcal{MN}_{d^2}(0, \sigma_r^2 I_{d^2})\\
X_{ijk} &\sim \mathcal{N}(R_k^\top (e_i \otimes e_j), \sigma_x^2).
\end{align}
Again, we can transform uniform random variables $U_i, U_j, U_k$ to $e_i, e_j, R_k$ via the inverse-CDF of zero-mean multivariate normal distribution. Then $X_{ijk}$ is determined by $U_{ijk}$ via the inverse-CDF of normal distribution with mean $R_k^\top (e_i \otimes e_j)$ and variance $\sigma_x^2$, i.e. $X_{ijk} = \Phi_1(U_{ijk};R_k^\top (e_i \otimes e_j), \sigma_x^2)$. The model is invariant w.r.t the changes in the other uniform variables $U_{ij}, U_{ik}$, and $U_{jk}$.
\end{example}

\section{Sparse exchangeable graph}
\citet{Caron2015} propose a symmetric simple point process on $\mathbb{R}^2_+$ as the edge set of a random graph, and \citet{Veitch2015} formalise the probabilistic symmetry as joint exchangeability of the point process.
\begin{definition}[Jointly exchangeable random measure on $\mathbb{R}^2$] A random measure $\xi$ on $\mathbb{R}^2$ is jointly exchangeable if for every measure preserving transformation $f$ on $\mathbb{R}_+$, we have
\begin{align}
\xi \circ (f \otimes f)^{-1} \stackrel{d}{=} \xi
\end{align}
\end{definition}
\begin{theorem}[\label{thm:kallenjoint}Kallenberg's jointly exchangeable theorem \citep{Kallenberg1990,kallenberg2005probabilistic}] A random measure $\xi$ on $\mathbb{R}^2$ is jointly exchangeable iff it has an almost surely representation
\begin{align}
\xi &= \sum_{i,j} f(\alpha, \vartheta_i, \vartheta_j, \zeta_{i,j})\delta_{\theta_i, \theta_j} \label{eqn:kallenjoint}\\
&+ \sum_{j,k}\{g(\alpha, \vartheta_j, \chi_{jk})\delta_{\theta_j,\sigma_{jk}} + g'(\alpha, \vartheta_j, \chi_{jk})\delta_{\sigma_{jk},\theta_j}\}\\
&+ \sum_{k}\{l(\alpha, \eta_k)\delta_{\nu_k,\nu'_k} + l'(\alpha, \eta_k)\delta_{\nu'_k, \nu}\}\\
&+\sum_j\{h(\alpha, \vartheta_j)(\delta_{\theta_j} \otimes \Lambda) + h'(\alpha, \vartheta_j)(\Lambda \otimes \delta_{\theta_j})\} + \beta\Lambda_D + \gamma \Lambda^2,
\end{align}
for some measurable function $f:\mathbb{R}_+^4 \rightarrow \mathbb{R}_+$, $g,g':\mathbb{R}_+^3 \rightarrow \mathbb{R}_+$, and $l, l', h, h': \mathbb{R}_+^2\rightarrow\mathbb{R}_+$, some collection of independent uniformly distributed random variables $(\zeta_{i,j})$ on $[0,1]$, some independent unit rate Poisson processes $\{(\theta_j, \vartheta_j)\}$ and $\{(\sigma_{ij}, \chi_{ij})\}$ on $\mathbb{R}_+^2$ and $\{(\nu, \nu'_j, \eta_j)\}$ on $\mathbb{R}^3$, and some independent set of random variables $\alpha, \beta, \gamma \geq 0$. $\Lambda$ is Lebesgue measure on $\mathbb{R}_+$, and $\Lambda_D$ is Lebesgue measure on the diagonal of $\mathbb{R}_+^2$.
\end{theorem}

If we only focus on an atomic measure, all terms with the Lebesgue measure have measure zero. The atomic measure will be symmetric if $f$ is symmetric in its the second and third arguments, $g = g'$, and $l=l'$. The atomic measure will be simple if $f, g, g', l,$ and $l'$ are $\{0,1\}$-valued. This random measure is locally finite under certain conditions, and a truncated measure is defined as a Kallenberg exchangeable graph by \cite{Veitch2015}. 

Each atomic term in Theorem \ref{thm:kallenjoint} uniquely contributes to a structure of the random measure.

\begin{example}[\label{caron2015}Caron and Fox model]
\cite{Caron2015} propose a simple point process on $\mathbb{R}^2$ as a product measure of a complete random measure. They propose a hierarchical model
\begin{align}
G_0 &= \sum_{i=1}^{\infty} w_i \delta_{\theta_i} & &G_0 \sim \text{CRM}(\rho, \lambda)\\
G &= \sum_{i,j} n_{ij} \delta_{\theta_i, \theta_j} & &G|G_0 \sim \text{PP}(G_0 \otimes G_0)\\
Z &=\sum_{i,j} \min(n_{ij} + n_{ji}, 1)\delta_{\theta_i, \theta_j}, &&
\end{align}
for L\'{e}vy intensity measure $\rho$ and $\lambda$ where $\rho$ is a jump part of the measure.
$Z$ can be directly specified as
\[ p(z_{ij}=1|w) = 
  \begin{cases}
    1 - \exp(-2w_iw_j)       & \quad i \neq j\\
    1 - \exp(-w_i^2) & \quad i = j\\
  \end{cases}
\]
This model can be reformulated in the Kallenberg's exchangeable theorem. The CRM $G_0$ can be constructed from a two-dimensional unit-rate Poisson process on $\mathbb{R}_+^2$ by the inverse L\'{e}vy method \cite{ferguson1972representation}. Let $(\theta_i, \vartheta_i)$ be a unit rate Poisson process on $\mathbb{R}_+^2$, and $\rho^{-1}$ be the inverse L\'{e}vy intensity of $\rho$, where $w_i = \rho^{-1}(\vartheta_i)$. The model can be formulated under the representation of Equation \ref{eqn:kallenjoint} as 
\[ f(\alpha, \vartheta_i, \vartheta_j, \zeta_{i,j}) =
	\begin{cases}
	1- \exp(-2\rho^{-1}(\vartheta_i)\rho^{-1}(\vartheta_j)) & \quad i \neq j\\
    1 - \exp( \rho^{-1}(\vartheta_i)^2) & \quad i = j\\
	\end{cases}
\]
and $g,g',l,l'=0$. 

They show that the resulting graph is sparse if intensity measure $\rho$ is infinite activity, i.e. $\int_{0}^{\infty} \rho(w)dw = \infty$ and dense if the intensity measure is finite activity, i.e. $\int_{0}^{\infty} \rho(w)dw < \infty$.
\end{example}

\begin{example}[Sparse block structured graphs \citep{Herlau2015}]
\end{example}

\begin{example}[Sparse graphs with overlapping communities \citep{Todeschini2016}]
\end{example}


Like \textit{graphon} in exchangeable random array, \citep{Veitch2015} also characterise the space of exchangeable atomic measure in terms of \textit{graphex}.

\begin{theorem}[Graphex \citep{Veitch2015}] Let $\xi$ be a random adjacency atomic measure. Then $\xi$ is jointly exchangeable iff it has a.s. representation
\begin{align}
\xi &= \sum_{i,j}\mathbf{1} [W_\alpha(\vartheta_i, \vartheta_j) \leq \zeta_{i,j}]\delta_{\theta_i, \theta_j} \\
&+\sum_{j,k} \mathbf{1} [\chi_{jk} \leq S(\alpha, \vartheta_j)](\delta_{\theta_j,\sigma_{jk}} +  \delta_{\sigma_{jk},\theta_j}) \\
&+\sum_{k} \mathbf{1} [\eta_{k} \leq I(\alpha)](\delta_{\nu_k,\nu'_k} + \delta_{\nu'_k, \nu_k}),
\end{align}
where $W:\mathbb{R}^3 \rightarrow [0,1]$, $S:\mathbb{R}^2 \rightarrow \mathbb{R}$, and $I:\mathbb{R}\rightarrow\mathbb{R}$, $(\zeta_{i,j})$ are collection of uniform random variable in [0,1], $\{(\theta_i, \vartheta_i)\}$, $\{(\sigma_{jk}, \chi_{jk})\}$, and $\{(\nu_k, \nu'_k, \eta_{k})\}$ are independent unit rate Poisson processes on $\mathbb{R}^2_+$ and $\mathbb{R}^3_+$, and $\alpha$ is an independent random variable on $\mathbb{R}_+$.
\end{theorem}

\begin{example}[Caron and Fox model with graphex] The model in Example \ref{caron2015} can be represented in terms of graphex notation.
\[ W_\alpha(\vartheta_i, \vartheta_j) =
	\begin{cases}
	1- \exp(-2\rho^{-1}(\vartheta_i)\rho^{-1}(\vartheta_j)) & \quad i \neq j\\
    1 - \exp( \rho^{-1}(\vartheta_i)^2) & \quad i = j\\
	\end{cases}
\]

\end{example}

\section{Sparse exchangeable bipartite graph}

\begin{theorem}[Kallenberg's separately exchangeable theorem \citep{Kallenberg1990}] A random measure $\xi$ on $\mathbb{R}^2$ is separately exchangeable iff it has an almost surely representation
\begin{align}
\xi &= \sum_{i,j} f(\alpha, \vartheta_i, \vartheta'_j, \zeta_{i,j})\delta_{\theta_i, \theta'_j} \\
&+ \sum_{j,k}\{g(\alpha, \vartheta_j, \chi_{jk})\delta_{\theta_j,\sigma_{jk}} + g'(\alpha, \vartheta'_j, \chi'_{jk})\delta_{\sigma'_{jk},\theta'_j}\}\\
&+ \sum_{k}l(\alpha, \eta_k)\delta_{\rho_k,\rho'_k} \\
&+\sum_j\{h(\alpha, \vartheta_j)(\delta_{\theta_j} \otimes \Lambda) + h'(\alpha, \vartheta'_j)(\Lambda \otimes \delta_{\theta'_j})\} + \gamma \Lambda^2
\end{align}
for some measurable function $f:\mathbb{R}_+^4 \rightarrow \mathbb{R}_+$, $g,g':\mathbb{R}_+^3 \rightarrow \mathbb{R}_+$, and $l, l', h, h': \mathbb{R}_+^2\rightarrow\mathbb{R}_+$, some collection of independent uniformly distributed random variables $(\zeta_{i,j})$ on $[0,1]$, some independent unit rate Poisson processes $\{(\theta_i, \vartheta_i)\}$, $\{(\theta'_j, \vartheta'_j)\}$, $\{(\sigma_{ij}, \chi_{ij})\}$ and $\{(\sigma'_{ij}, \chi'_{ij})\}$ on $\mathbb{R}_+^2$ and $\{(\rho_j, \rho'_j, \eta_j)\}$ on $\mathbb{R}^3$, and some independent set of random variables $\alpha, \gamma \geq 0$. $\Lambda$ is Lebesgue measure on $\mathbb{R}_+$.
\end{theorem}

\begin{example}[\citep{Caron2012}]
Matrix factorisation for the sparse bipartite graph has been partially discussed in \citep{Caron2012}, although the formal proof of the sparsity is lacking.
\end{example}

\bibliographystyle{apalike}
\bibliography{ref}

\end{document}
