To address the unknown node ordering in graph-level variational decoders, we can compute the likelihood for each possible node ordering and select the one that maximizes 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 $$\tilde{A}^{\pi}$$ is the predicted adjacency matrix using a specific node ordering $$\pi$$. The main drawback of this approach is that it is computationally expensive.

Maximum Likelihood Node Ordering

To address the unknown node ordering in graph-level variational decoders, nodes can be ordered using a heuristic approach. For example, depth-first search or breadth-first search can be used, ordering nodes starting from those with the highest degree:

$$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])$$

Alternatively, a small heuristic set of orderings can be considered, averaging the likelihood over these orderings:

$$p_{\theta}(G | \mathbf{z}_G) \approx \sum_{\pi_i\in\{\pi_1,\dots,\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])$$

These heuristic methods perform effectively in practice while remaining computationally tractable.

Heuristic Node Ordering

There are two main challenges with the original graph-level variational decoder. First, because it uses a multi-layer perceptron (MLP), it requires assuming a fixed number of nodes in each graph. This is typically addressed by setting a maximum number of nodes and masking the surplus nodes. Second, using the predicted adjacency matrix, $$\tilde{A}$$, to compute the likelihood implicitly assumes a specific node ordering. However, the correct ordering of rows and columns is unknown when computing the reconstruction loss. There are two popular strategies to address this second issue.

University of Notre Dame

Google

The goal of a graph-level variational decoder is to define a posterior given a graph-level latent embedding. The original graph VAE proposed combining a multi-layer perceptron (MLP) and a 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 the 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 losses.

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