We can compute the likelihood for each node ordering and find the one that maximize the likelihood:

$p_{\theta}(G | \mathbf{z}_G) = \max_{\pi\in\Pi}\prod_{(u,v)\in \mathcal{V}} \tilde{A}^{\pi}[u,v] A[u,v]+(1-\tilde{A}^{\pi}[u,v]) (1-A[u,v])$

Where the $\tilde{A}^{\pi}$ is the predicted adjacency matrix using a specific node ordering. The drawback of this method is that its computationally expensive.


Find The Ordering That Gives The Highest Likelihood

We can order the nodes using some heuristic node ordering. For example, we can use depth-first search and breadth first-search and order from the highest degree nodes:

$p_{\theta}(G | \mathbf{z}_G) \approx \prod_{(u,v)\in \mathcal{V}} \tilde{A}^{\pi}[u,v] A[u,v]+(1-\tilde{A}^{\pi}[u,v]) (1-A[u,v])$

 Or we can also consider a small heuristic set of ordering and average over these orderings:

$p_{\theta}(G | \mathbf{z}_G) \approx \sum_{\pi_i\in\{\pi_1,…\pi_n\}}\prod_{(u,v)\in \mathcal{V}} \tilde{A}^{\pi_i}[u,v] A[u,v]+(1-\tilde{A}^{\pi_i}[u,v]) (1-A[u,v])$

 This method has been proven to work great in practice.


Use Heuristic Node Ordering 

There are two main challenges of the original decoder:

1)	Since we use MLP in the decoder, we need to assume that there is a fixed number of nodes in each graph. This  is typically done by setting a maximum number of nodes and masking the surplus nodes.

2)	When we use $\tilde{A}$ to compute the likelihood, we implicitly assume that there is some ordering over the nodes. But we don’t know the correct ordering of rows and columns when we compute reconstruction loss.

There ‘re two popular strategies to solve the second issue.


University of Notre Dame

The goal of graph level variational decoder is to define a posterior given a graph level latent embedding.  The original graph VAE proposed to combine a multi-layer perceptron (MLP) and Bernoulli distribution assumption to obtain the posterior:

$p_{\theta}(G | \mathbf{z}_G) = \prod_{(u,v)\in \mathcal{V}} \tilde{A}[u,v] A[u,v]+(1-\tilde{A}[u,v]) (1-A[u,v])$

Where $A$ is adjacency matrix and $\tilde{A}=\sigma(MLP(\mathbf{z}_G))$ is the predicted matrix of edge probabilities. The overall log-likelihood objective is equivalent to a set of independent binary cross-entropy loss.


Decoder For Graph-Level Latents

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

Learn Before

Related

Learn After