GMNN: Graph Markov Neural Networks
GMNN: Graph Markov Neural Networks
Meng Qu, Yoshua Bengio, Jian Tang
Intro
Problem Definition & Preliminary
Problem Definition
一个Graph $$G=(V, E, x_v)$$，$$x_v$$是attribute matrix。而$$E$$中的edges有很多不同的类型，代表object之间不同的relation types。这篇paper假设所有的edge都只有一个类型。给定一些object/node $$L \subset V$$ 的label $$y_L$$，目标是预测其余object $$U = V \backslash L$$ 的label $$y_U$$。
这个问题在statistical relation learning (SRL) 和 graph neural network (GNN)中同时都研究过。本质上，两个类型的方法都是为了求 给定object attributes和graph structure的情况下，object label的分布。下面我们结束这两种方法更一般的想法。
Statistical Relational Learning
$$ p(yV|x_V) = \frac{1}{Z(x_V)} \prod{(i,j) \in E} \phi_{i,j}(y_i, y_j, x_V)
$$
其中$$(i,j)$$是图上相邻的两个点，而$$\phi_{i,j}(y_i, y_j, x_V)$$则表示定义在edge上的potential score。
在这个定义下，predict label就成了一个inference problem，也就是inferring posterior label distribution of the unlabeled objects $$p(y_U | y_L, x_V)$$。
Graph Neural Network (GNN)
GCN, GAT, 或者neural message passing layer都可以使用。
GMNN的目标是学习一个joint distribution（而不是GNN的independent distribution），也就是$$p(y_V | x_V)$$。
GMNN: Graph Markov Neural Network
GMNN的目标是学习一个joint distribution（而不是GNN的independent distribution），也就是$$p(y_V | x_V)$$。
- E-step: 用一个GNN来学习object representation
- M-step: 用另外一个GNN来model local dependency
Pseudolikelihood Variational EM
使用conditional random field来给object label的joint distribution建模，也就是$$p_\phi(y_V | x_V)$$。
我们通过学习最大化的log－likelihood of observed object labels，也就是$$\log p_\phi (y_L | x_V)$$。然而直接计算likelihood是比较难的，因此我们选择优化ELBO，因此有 (?)
$$\log p\phi (y_L | x_V) \ge \mathbb{E}{q\theta(y_U | x_V) [ \log p\phi(yV | x_V) - \log q\theta(y_U | x_V) ]}$$
其中$$q_\theta(y_U | x_V)$$ 可以是在 $$y_U$$ 上任意的分布。这一步的优化可以用variational EM求解。
- Variational E-step (inference): 固定$$p\phi$$，然后更新variational distribution $$q\theta(yU|x_V)$$，从而估计真实的posterior distribution $$p\phi(y_U | y_L, x_V)$$(?)
- M-step (learning): 固定$$q\theta$$，然后通过最大化下面的likelihood来更新$$p\phi$$
$$\ell(\phi) = \mathbb{E}{q\theta(yU | x_V)} [ \log p\phi (y_V | x_V) ]$$
但是因为有partition function，所以直接进行优化是比较困难的。我们使用pseudolikelihood
$$ \ell{PL}(\phi) = \mathbb{E}{q\theta(y_U | x_V)} [ \sum{n \in V} (yn | y{V \backslash n}, xV) ]\ = \mathbb{E}{q\theta(y_U | x_V)} [ \sum{n \in V} (yn | y{NB(n)}, x_V) ]
$$
其中$$NB(n)$$表示$$n$$的邻居。
Inference
inference的步骤主要是计算posterior distribution $$p\phi(y_U | y_L, x_V)$$。因为直接计算比较困难，因此用另外一个variational distribution进行估计: $$q\theta (y_U | x_V)$$。更具体地说，使用mean-field method:
$$q\theta(y_U | x_V) = \prod{n \in U} q_\theta (y_n | x_V)$$
在variational distribution中，所有的objective label都被假设为相互独立的。
然后给每一个object label model distribution时，我们根据amortized inference的想法，并且用GNN来表示$$q_\theta (y_n | x_V)$$，因此有了:
$$q\theta (y_n | x_V) = Cat(y_n | softmax(W\theta h_{\theta, n}))$$
$$h_{\theta, n}$$就是GNN的latent representation。
通过上面mean-field公式，$$q_\theta$$的最优解符合了fixed-point condition:
$$\log q\theta(y_n | x_V) = \mathbb{E}{q\theta (y{NB(n) \cap U} | xV) } [\log p\phi (yn | y{NB(n)}, x_V)] + C$$
具体证明在附录。这个公式的右手边包含了对于$$q_\theta$$的期望。为了进一步简化这个condition，我们通过样本取样来估计这个期望，就有
$$\mathbb{E}{q\theta (y{NB(n) \cap U} | x_V) } [\log p\phi (yn | y{NB(n)}, xV)] \approx \log p\phi(yn | \hat y{NB(n)}, x_V)$$
根据公式8和公式9，我们有 $$q\theta(y_n | x_V) \approx p\phi(yn | \hat y{NB(n)}, x_V)$$