【论文阅读】Variational Graph Auto-Encoder

0、基本信息

• 会议：2016-NIPS
• 作者：Thomas N. Kipf，Max Welling
• 文章链接：Variational Graph Auto-Encoder
• 代码链接：Variational Graph Auto-Encoder

1、介绍

本文提出一个变分图自编码器，一个基于变分自编码（VAE）的，用于在图结构数据上无监督学习的框架。其基本思路是：用已知的图（graph）经过编码（图卷积）学到节点向量表示的分布，在分布中采样得到节点的向量表示，然后进行解码（链接预测）重新构建图。

2、创新点

• 将变分自编码器（VAE）迁移到图领域

3、准备工作

3.1、自编码器（AE）

自编码器由两个部分组成，分别是编码器和解码器，其中编码器通过神经网络，得到原始数据的低维向量表示；解码器也通过神经网络，将低维向量表示还原为原始数据。
下图是自编码器的一个例子：
![[AE.png]]
自编码器的训练目标是最小化重建误差，即使输入和输出保持尽量一致。

3.2、变分自编码器

如果将解码器看做一个生成模型，我们只要有低维向量表示，就可以用这个生成模型得到近似真实的样本。但是，这样的生成模型存在一个问题：低维向量表示必须是由真实样本通过编码器得到的，否则随机产生的低维向量表示通过生成模型几乎不可能得到近似真实的样本。
那么，如果能将低维向量表示约束在一个分布（比如正态分布）中，那么从该分布中随机采样，产生的低维向量表示通过生成模型不是就能产生近似真实的样本了吗？

变分自编码器就是这样的一种自编码器：变分自编码器通过编码器学到的不是样本的低维向量表示，而是低维向量表示的分布。假设这个分布服从正态分布，然后在低维向量表示的分布中采样得到低维向量表示，接下来经过解码器还原出原始样本。
变分自编码器将真实样本

X

X

X输入变分图自编码器，通过编码器学到每个样本对应的低维向量表示的均值

μ

mu

μ和方差

σ

2

sigma^2

σ2，然后再

N

(

μ

,

σ

2

)

N(mu,sigma^2)

N(μ,σ2)中采样出变量的表征，再通过解码器（生成器）生成样本

X

^

hat{X}

X^。均值描述了概率分布的期望值，而标准差描述了概率分布的广度。

3.3、图自编码器（GAE）

图自编码器，即Graph Auto-Encoders，简写GAE。图自编码器也由两部分组成，编码器和解码器。

（1）编码器
GAE的编码器是一个简单的两层GCN模型：

Z

=

G

C

N

(

A

,

X

)

mathrm{Z} = mathrm{GCN}mathrm(A,mathrm{X})

Z=GCN(A,X)
更具体一些，两层的GCN在论文中定义如下：

G

C

N

(

A

,

X

)

=

A

~

R

e

L

U

(

A

^

X

W

0

)

W

1

mathrm{GCN(A,X)}=tilde{A}mathrm{ReLU(hat{A}mathrm{X}mathrm{W^0})W^1}

GCN(A,X)=A~ReLU(A^XW0)W1
其中，

A

~

=

D

−

1

2

A

D

−

1

2

tilde{A}=D^{-frac{1}{2}}AD^{-frac{1}{2}}

A~=D−21​AD−21​，即对称归一化邻接矩阵，

W

1

W^1

W1和

W

0

W^0

W0是GCN需要学习的参数。
通过编码器，我们可以得到结点的嵌入向量

Z

Z

Z.
（2）解码器
编码器得到节点表示的向量后，通过解码器通过向量的内积来重构邻接矩阵：

A

^

=

σ

(

Z

Z

T

)

hat{A} = sigma{(ZZ^T)}

A^=σ(ZZT)
在GAE中，我们需要优化编码器中的

W

0

W^0

W0和

W

1

W^1

W1进而使得经解码器重构出的邻接矩阵

A

^

hat{A}

A^ 与原始的邻接矩阵A尽量相似。因为邻居矩阵决定了图的结构，经节点向量表示重构出的邻接矩阵与原始邻接矩阵越相似，说明节点的向量表示越符合图的结构。因此，GAE中的损失函数可以定义如下：

L

=

−

1

N

∑

(

y

l

o

g

(

y

^

)

+

(

1

−

y

)

l

o

g

(

1

−

y

^

)

)

mathcal{L}=-frac{1}{N}sum (ylog(hat{y})+(1-y)log(1-hat{y}))

L=−N1​∑(ylog(y^​)+(1−y)log(1−y^​))
这里

y

y

y表示原始邻接矩阵A中的元素，其值为0或1；

y

^

hat{y}

y^​ 为重构的邻接矩阵

A

^

hat{A}

A^中的元素。从上述损失函数可以看出，损失函数的本质就是两个交叉熵损失函数之和。
当然，我们可以对原始论文中的GAE进行扩展，例如编码器可以使用其他的GNN模型。
2.4、KL散度（又叫相对熵）：
如果我们对于同一个随机变量 x有两个单独的概率分布 P(x) 和 Q(x)，我们可以使用 KL 散度（Kullback-Leibler (KL) divergence）来衡量这两个分布的差异。

在机器学习中，P往往用来表示样本的真实分布，Q用来表示模型所预测的分布，那么KL散度就可以计算两个分布的差异，也就是Loss损失值。其公式定义如下：

K

L

(

p

∣

∣

q

)

=

∑

i

=

1

n

p

(

x

i

)

l

o

g

(

p

(

x

i

)

q

(

x

i

)

)

KL(p||q)=sum_{i=1}^np(x_i)log(frac{p(x_i)}{q(x_i)})

KL(p∣∣q)=i=1∑n​p(xi​)log(q(xi​)p(xi​)​)
从KL散度公式中可以看到Q的分布越接近P（Q分布越拟合P），那么散度值越小，即损失值越小。

4、变分图自编码器（VGAE）

变分图自编码器也有两部分组成，分别是推理模型（编码器）和生成模型（解码器）。

4.1、推理模型

在GAE中，可训练的参数只有

W

0

W^0

W0 和

W

1

W^1

W1 ，训练结束后只要输入邻接矩阵

A

A

A和节点特征矩阵

X

X

X，就能得到节点的向量表征

Z

Z

Z。

与GAE不同，在变分图自编码器VGAE中，节点表征

Z

Z

Z不是由一个确定的GCN得到，而是从一个多维高斯分布中采样得到。

多维高斯分布的均值和方差由两个GCN确定：

μ

=

G

C

N

μ

(

X

,

A

)

mu=mathrm{GCN}_mu(mathrm{X,A})

μ=GCNμ​(X,A)
以及

l

o

g
  

σ

=

G

C

N

σ

(

X

,

A

)

log ;sigma = mathrm{GCN}_sigma(mathrm{X,A})

logσ=GCNσ​(X,A)
论文中，这两个不同的GCN都是两层，并且第一层的参数

W

0

W^0

W0是共享的。

有了均值和方差后，我们就能唯一地确定一个多维高斯分布，然后从中进行采样以得到节点的向量表示

Z

Z

Z，也就是说，向量表征的后验概率分布为：

q

(

Z

∣

X

,

A

)

=

∏

i

=

1

N

q

(

z

i

∣

X

,

A

)

,

q(mathbf{Z}|mathbf{X},mathbf{A})=prod_{i=1}^Nq(mathbf{z}_i|mathbf{X},mathbf{A}),

q(Z∣X,A)=i=1∏N​q(zi​∣X,A),
其中，

q

(

z

i

∣

X

,

A

)

=

N

(

z

i

∣

μ

i

,

diag

⁡

(

σ

i

2

)

)

q(mathbf{z}_i|mathbf{X},mathbf{A})=mathcal{N}(mathbf{z}_i|boldsymbol{mu}_i,operatorname{diag}(boldsymbol{sigma}_i^2))

q(zi​∣X,A)=N(zi​∣μi​,diag(σi2​))
其中 和

μ

i

mu_i

μi​和

σ

i

2

sigma^2_i

σi2​分别表示节点向量的均值和方差。也就是说，通过两个GCN我们得到了所有节点向量的均值和方差，然后再从中采样形成节点向量。具体来讲，编码器得到多维高斯分布的均值向量和协方差矩阵后，我们就可以通过采样来得到节点的向量表示，但是，采样操作无法提供梯度信息，这对神经网络来讲是没有意义的，因此作者做了重采样：

z

=

μ

+

ϵ

σ

mathrm{z=mu+epsilonsigma}

z=μ+ϵσ
这里

ϵ

epsilon

ϵ服从

N

(

0

,

1

)

mathcal{N}(0,1)

N(0,1)，也就是标准高斯分布，因为

ϵ

epsilon

ϵ服从标准高斯分布，所以

μ

+

ϵ

σ

mu+epsilon sigma

μ+ϵσ服从

N

(

μ

,

σ

2

)

mathcal{N}(mu,sigma^2)

N(μ,σ2).

反复从训练集中抽取样本，并对每个样本重新拟合感兴趣的模型，以获得有关拟合模型的其他信息。

4.2、生成模型

生成模型，通过计算图中任意两个节点间存在边的概率来重构图，

p

(

A

∣

Z

)

=

∏

i

=

1

N

∏

j

=

1

N

p

(

A

i

j

∣

z

i

,

z

j

)

,

with

p

(

A

i

j

=

1

∣

z

i

,

z

j

)

=

σ

(

z

i

⊤

z

j

)

,

pleft(mathbf{A}|mathbf{Z}right)=prod_{i=1}^Nprod_{j=1}^Npleft(A_{ij}|mathbf{z}_i,mathbf{z}_jright),quadtext{with}quad pleft(A_{ij}=1|mathbf{z}_i,mathbf{z}_jright)=sigma(mathbf{z}_i^topmathbf{z}_j),

p(A∣Z)=i=1∏N​j=1∏N​p(Aij​∣zi​,zj​),withp(Aij​=1∣zi​,zj​)=σ(zi⊤​zj​),

也就是说，解码器通过计算任意两个节点向量表示的相似性来重建图结构。

4.3、学习

损失函数定义如下：

L

=

E

q

(

Z

∣

X

,

A

)

[

log

⁡

p

(

A

∣

Z

)

]

−

K

L

[

q

(

Z

∣

X

,

A

)

∣

∣

p

(

Z

)

]

mathcal{L}=mathbb{E}_{q(mathbf{Z}midmathbf{X},mathbf{A})}big[log pleft(mathbf{A}midmathbf{Z}right)big]-mathrm{KL}big[q(mathbf{Z}midmathbf{X},mathbf{A})||p(mathbf{Z})big]

L=Eq(Z∣X,A)​[logp(A∣Z)]−KL[q(Z∣X,A)∣∣p(Z)]

• 第一部分与GAE中类似，为交叉熵函数，也就是经分布$q$
• 第二部分表示利用GCN得到的分布$q(\cdot )$

损失函数展开形式下：

∑

i

=

1

n

{

−

p

(

x

)

l

o

g

(

p

(

x

)

)

−

(

1

−

p

(

x

)

)

l

o

g

(

1

−

p

(

x

)

)

+

1

/

2

(

μ

(

i

)

2

+

σ

(

i

)

2

−

l

o

g

σ

(

i

)

2

−

1

)

}

sum_{i=1}^n{-p(x)log(p(x))-(1-p(x))log(1-p(x)) +1/2(mu_{(i)}^{2}+sigma_{(i)}^{2}-logsigma_{(i)}^{2}-1)}

i=1∑n​{−p(x)log(p(x))−(1−p(x))log(1−p(x))+1/2(μ(i)2​+σ(i)2​−logσ(i)2​−1)}

5、模型实现

import torch
import torch.nn as nn
import torch.nn.functional as F
import os
import numpy as np
import args
class VGAE(nn.Module):
    def __init__(self,adj) -> None:
        super(VGAE,self).__init__()
        self.adj = adj
        self.share_gcn = GraphConvLayer(args.infeat,args.hidfeat1)
        self.gcn_mean  = GraphConvLayer(args.hidfeat1,args.hidfeat2,activation = lambda x: x)
        self.gcn_logstd = GraphConvLayer(args.hidfeat1,args.hidfeat2,activation = lambda x:x)

    def encode(self,x,adj):
        hidden = self.share_gcn(x,adj)
        self.mean = self.gcn_mean(hidden,adj)
        self.logstd = self.gcn_logstd(hidden,adj)
        gaussian_noise = torch.randn(x.shape[0],args.hidfeat2)
        sampled_z = gaussian_noise * torch.exp(self.logstd) + self.mean
        return sampled_z
    @staticmethod
    def decode(z):
        '''静态方法'''
        A_pred = F.sigmoid(torch.matmul(z,z.T))
        return A_pred
    def forward(self,x):
        Z = self.encode(x,self.adj)
        A_pred = self.decode(Z)
        return A_pred
class GraphConvLayer(nn.Module):    
    def __init__(self, infeat,outfeat,activation = F.relu) -> None:
        super(GraphConvLayer,self).__init__()
        self.activation = activation
        self.layer = nn.Linear(infeat,outfeat,bias=False)
        self.init_param()
        pass
    def init_param(self):
        self.layer.reset_parameters()
    def forward(self,x,adj):
        AX = torch.mm(adj,x)
        AXW = self.layer(AX)
        return self.activation(AXW)

参考链接

• 参考链接1
• 参考链接2
• 参考链接3