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.


University of Notre Dame

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.


Drawback Of Original Graph Level Variational Decoder

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

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.


Learn Before

Related