A Flexible Generative Framework for Graph-based Semi-supervised Learning

A Flexible Generative Framework for Graph-based Semi-supervised Learning

Intro

传统的ML方法会将每一个数据点考虑为independent（但其实在training的过程中，有些算，比如NN，会implicitly share一些信息）。

这篇paper就考虑graph-based semi-supervised learning，并且用generative model来explicitly model joint relationship。joint relationship会涉及feature，label，和graph。

Related Work

Graph-based Regularization for Semi-supervised Learning

graph smoothness就是说每一个数据点的neighbor nodes的label或者feature都比较相似／smooth。这个假设就可以带来一个graph-based regularization term，而且其实非常依赖于数据本身。

Graph Neural Networks for Semi-supervised Learning

在graph上进行modeling。

Approach

Problem Setup

一共n个点，前m个是observed，后面的都是missing。

考虑了transductive setting。

A Flexible Generative Framework for Graph-based Semi-supervised Learning

考虑joint distribution $$p(X,Y,G)$$

Generation process.

$$ p(X,Y,G) = p(G|X,Y) p(Y|X) p(X)

$$

其中$$p(G|X,Y),p(Y|X)$$会通过一些flexible parametric families distribution，即$$p\theta(G|X,Y),p\theta(Y|X)$$，来建模。这里flexible指的是在这几个conditional probabilities上的PMF 唯一的限制就是对 $$\theta$$ 要能够可导。为了简洁，我们并不假设$$p(X)$$是某一个特定的分布。

Model inference. 为了infer missing labels $$Y{miss}$$，我们需要posterior distribution $$p\theta(Y{miss}|X, Y{obs}, G)$$。但这个的计算通常是intractable。这里我们用了scalable variational inference的方法，使用$$q\phi(Y{miss}|X, Y_{obs}, G)$$来估计true posterior分布。

Model learning. 优化ELBO来学习$$\theta, \phi$$。ELBO是observed data ($$Y_{obx}, G$$) conditioned on X。

recall ELBO是:

$$ \log p(x) \ge E_q \big[ \log p(x,z) - \log q(z) \big]\

$$

进行替换：$$x = Y{obx},G|x$$，和 $$z = Y{miss}|X,Y_{obx},G$$。因此negative ELBO定义如下：

$$ \log p (Y{obs}, G | X) \ \ge E{q\phi(Y{miss}|X,Y{obx},G)} \big[ \log p\theta(Y{obs},Y{miss},G|X) - \log q\phi(Y{miss}|X,Y{obx},G) \big]\ = -\mathcal{L}{ELBO} (\theta, \phi; X, Y_{obs}, G)

$$

Instantiations 实例化

实际建模的时候，还是需要确定parametric form of generative model $$p\theta(G|Y,X), p\theta(Y|X)$$，和估计的posterior model $$q\phi(Y{miss} | Y_{obs}, X, G)$$。

Instantiations of the Generative Model

对于$$p_\theta(Y|X)$$ 我们使用非常简单的MLP建模。

对于$$p_\theta(G|X,Y)$$ 我们主要考虑两个 latent space models (LSM) 和 stochastic block models (SBM)。

两类network framework都假设edge是conditionally independent，也就是

$$ p\theta(G|X,Y) = \prod{ij} p\theta(e{i,j} | X, Y)

$$

下面我们会讨论 $$p\theta(e{i,j} | X, Y)$$ 的实例。

Instantiation with a LSM. latent space model假设node都在一个latent space上，且edge distribution仅仅依赖于node i和node j。即为$$p\theta(e{i,j}|X,Y) = p\theta(e{i,j}|x_i, x_j, y_i, y_j)$$。我们将PMF定义为一个logit model

$$ p\theta(e{i,j}=1 | x_i, x_j, y_i, y_j) = \sigma([(U x_i)^T, y_i^T, (U x_j)^T, y_j^T] w)

$$

$$U$$是一个可以学习的linear transformation matrix。

Instantiation with a SBM. stochastic block model假设有C种node，每一种node对应于一个latent type variable $$zi \in {1, 2, ..., C}$$，且每一个edge $$e{i,j}$$ 的概率仅依赖于两个node的类型，即$$zi, z_j$$。在general SBM中，$$p\theta(e{i,j}=1 |z_i, z_j) = p{zi, z_j}$$，其中$$p{u,v}$$组成了一个probability matrix $$P$$。

我们假设node type就是class type，也就是$$C=K, zi = \arg \max y_i$$，且$$p\theta(e{i,j}|X,Y) = p\theta (e{i,j} | y_i, y_j)$$。我们用最简单的SBG来给 $$p\theta (e_{i,j} | y_i, y_j)$$ 建模，也就是planted partition model

$$ e_{i,j} | y_i, y_j = \begin{cases} Bernoulli(p_0) & y_i = y_j\ Bernoulli(p_1) & y_i \ne y_j \end{cases}

$$

这也就是说probability matrix $$P$$的主对角线是$$p_0$$，其余都是$$p_1$$。

Instantiations of the Approximate Posterior Model

对于approximate posterior model $$q\phi(Y{miss} | Y{obs}, X, G)$$，理论上我们需要一个很强的function，将($$X,Y{obs},G$$)作为输入，然后输出$$Y{miss}$$的概率。这里我们考虑两个模型：Graph Convolutional Network (GCN)和Graph Attention Network (GAT)。这里需要说明的是，我们infer的是 $$q\phi(Y_{miss} | X, G)$$，因为graph neural network的输入是$$(X,G)$$。

Training

Supervised loss

$$ \mathcal{L}s(\phi; X, Y{obs}, G) = - \log q\phi(Y{obs}|X, G)

$$

total loss就是将两个加起来

$$ \mathcal{L} (\theta, \phi) = \mathcal{L}{ELBO} (\theta, \phi; X, Y{obs}, G) + \eta \mathcal{L}s(\phi; X, Y{obs}, G)

$$

Negative edge sampling. 标准操作。

Appendix

Under review.

其实看最后的total loss，就是supervised loss + reconstruction loss。这里的reconstruction loss ／ ELBO 就有LSM和SBM两种设定，其实都比较简单。

严格来说，不算第一个这么做的（joint relationship）。Multi-Task Graph Autoencoders by Phi Vu Tran也考虑了将node和edge结合训练的想法。