Taking a probabilistic view of graph data, we can assume that the graph structure we are given defines the dependencies between the different nodes. A graph $G=(V, E)$ defines a Markov random field: $$p({x_{v}}, {z_{v}}) \propto \Pi _{v \in V} \Phi ({x_{v}}, {z_{v}}) \Pi_{(u, v)\in E} \Psi  ({z_{u}}, {z_{v}})$$
This equation says that the distribution $p({x_{v}}, {z_{v}})$ over node features and node embeddings factorizes according to the graph structure. Thus we can assume that node features are determined by their latent embeddings, and assume that the latent embeddings for connected nodes are dependent on each other.

University of Michigan - Ann Arbor

One prominent example of alternative theoretical motivations for the GNN framework is the motivation of GNNs based on connections to variational inference in probabilistic graphical models (PGMs).

In this probabilistic perspective, we view the embeddings $z_{u}, \forall u \in V$ for
each node as latent variables that we attempt to infer. Assume that we observe the graph structure and the input node features X, and the goal is to infer the underlying latent variables hat can explain this observed data. Then the message passing operation that underlies GNNs can be viewed as a neural network analogue of certain message passing algorithms that are commonly used for variational inference to infer distributions over latent variables.

Probabilistic Graphical Models (PGM)

Hamilton, W.L. Graph Representation Learning. *Synthesis Lectures on Artificial Intelligence and Machine Learning*. 2020, 14(3), 1–159. https://doi.org/10.2200/S01045ED1V01Y202009AIM046

Graph Representation Learning by William Hamilton

Let $p(x)$ denote a probability density function defined over the random variable $x \in R^{m}$. Given an arbitrary feature map $\phi : R^{m} \rightarrow \textit{R}$, we can represent the density $p(x)$ based on its expected value under this feature map:
$\mu_{x}=\int_{R^{m}} \phi (x)p(x)dx$.

The key idea with Hilbert space embeddings of distributions is that this equation will be injective, as long as a suitable feature map $\phi$ is used. This means that $\mu_{x}$ can serve as a sufficient statistic for $p(x)$, and any computations we want to perform on $p(x)$ can be equivalently represented as functions of the embedding $\mu_{x}$.

Learn Before

Related