专栏首页阿泽的学习笔记【Code】关于 GCN,我有三种写法

【Code】关于 GCN,我有三种写法

本篇文章主要基于 DGL 框架用三种不同的方式来实现图卷积神经网络。手机看可能不太方便,可以点击阅读原文,移步到知乎上看(但是我忘了加 = =)。

1. DGL

DGL(Deep Graph Library)框架是由纽约大学和 AWS 工程师共同开发的开源框架,旨在为大家提供一个在图上进行深度学习的工具,帮助大家更高效的实现算法。

用现有的一些框架比如 TensorFlow、Pytorch、MXNet 等实现图神经网络模型都不太方便,同样现有框架实现图神经网络模型的速度不够快。

DGL 框架设计理念主要在于将图神经网络看作是消息传递的过程,每一个节点会发出它自己的消息,也会接收来自其它节点的消息。然后在得到所有信息之后做聚合,计算出节点新的表示。原有的深度学习框架都是进行张量运算,但是图很多时候并不能直接表示成一个完整的张量,需要手动补零,这其实很麻烦,不高效。

DGL 是基于现有框架,帮助用户更容易实现图神经网络模型。DGL 现在主要是以消息传递的接口作为核心,同时提供图采样以及批量处理图的接口。

关于 DGL 就不再进行过多介绍,感兴趣的同学可以去官网(http://dgl.ai/)了解。

2. Prepare

import torch
import time
import math
import dgl
import numpy as np
import torch.nn as nn
from dgl.data import citation_graph as citegrh
from dgl import DGLGraph
import dgl.function as fn
import networkx as nx
import torch.nn.functional as F

from dgl.nn import GraphConv
# from dgl.nn.pytorch import GraphConv
# from dgl.nn.pytorch.conv import GraphConv

这里有三种导入方法,建议用第一种,因为 DGL 的开发同学设计了一个机制,会自动 detect 用了什么 beckend,从而适配对应的 backend 的 api。

print(torch.__version__)
print(dgl.__version__)
print(nx.__version__)
1.4.0
0.4.3
2.3

3. GCN

3.1 First version

DGL 的第一种写法是利用 DGL 预定义的图卷积模块 GraphConv 来实现的。

GCN 的数学公式如下:

h_i^{(l+1)} = \sigma(b^{(l)} + \sum_{j\in\mathcal{N}(i)}\frac{1}{c_{ij}}h_j^{(l)}W^{(l)})

其中,

\mathcal{N}(i)

为节点的邻居集合,

c_{ij}=\sqrt{|\mathcal{N}(i)|}\sqrt{|\mathcal{N}(j)|}

表示节点度的平方根的乘积,用于归一化数据,

sigma

为激活函数

GraphConv 模型参数初始化参考 tkipf 大佬的原始实现,其中

W^{(l)}

使用 Glorot uniform 统一初始化,并将偏差初始化为零。

简单介绍下 Glorot 均匀分布(uniform)

Glorot 均匀分布,也叫 Xavier 均匀分布,该方法源于 2010 年的一篇论文《Understanding the difficulty of training deep feedforward neural networks》。其核心思想在于:为了使得网络中信息更好的流动,每一层输出的方差应该尽量相等。基于这个目标,权重 W 的方差需要满足

\forall i \; Var[W^i] = \frac{2}{n_{i}+n_{i+1}}

,我们知道均匀分布的方差为:

Var=\frac{(b-a)^2}{12}

。所以我们可以初始化 W 为 Xavier 均匀分布:

W \sim U[-\frac{\sqrt{6}}{\sqrt{n_j+n_{j+1}}}, \frac{\sqrt{6}}{\sqrt{n_j+n_{j+1}}}]

(具体证明见论文)

class GCN(nn.Module):
    def __init__(self,
                 g,
                 in_feats,
                 n_hidden,
                 n_classes,
                 n_layers,
                 activation,
                 dropout):
        super(GCN, self).__init__()
        self.g = g
        self.layers = nn.ModuleList()
        # input layer
        self.layers.append(GraphConv(in_feats, n_hidden, activation=activation))
        # output layer
        for i in range(n_layers - 1):
            self.layers.append(GraphConv(n_hidden, n_hidden, activation=activation))
        # output layer
        self.layers.append(GraphConv(n_hidden, n_classes))
        self.dropout = nn.Dropout(p=dropout)
    
    def forward(self, features):
        h = features
        for i, layers in enumerate(self.layers):
            if i!=0:
                h = self.dropout(h)
            h = layers(self.g, h)
        return h

3.2 Second version

3.2.1 ndata

DGL 的第二种写法:使用用户自定义的 Message 和 Reduce 函数

ndata 是 DGL 的一个特殊的语法,可以用于赋值(获得)某些节点的特征:

x = tourch.randn(10, 3)
g.ndata['x'] = x

如果指定某些节点的特征,可以进行切片操作:

g.ndata['x'][0] = th.zeros(1, 3)
g.ndata['x'][[0, 1, 2]] = th.zeros(3, 3)
g.ndata['x'][th.tensor([0, 1, 2])] = th.randn((3, 3))

当然也可以获得边的特征:

g.edata['w'] = th.randn(9, 2)

# Access edge set with IDs in integer, list, or integer tensor
g.edata['w'][1] = th.randn(1, 2)
g.edata['w'][[0, 1, 2]] = th.zeros(3, 2)
g.edata['w'][th.tensor([0, 1, 2])] = th.zeros(3, 2)

# You can get the edge ids by giving endpoints, which are useful for accessing the features.
g.edata['w'][g.edge_id(1, 0)] = th.ones(1, 2)                   # edge 1 -> 0
g.edata['w'][g.edge_ids([1, 2, 3], [0, 0, 0])] = th.ones(3, 2)  # edges [1, 2, 3] -> 0
# Use edge broadcasting whenever applicable.
g.edata['w'][g.edge_ids([1, 2, 3], 0)] = th.ones(3, 2)          # edges [1, 2, 3] -> 0

3.2.2 UDFs

在 DGL 中,通过用户自定义的函数(User-defined functions,UDFs)来实现消息传递和节点特征变换。

可以利用 Edge UDFs 来定义一个消息(Message)函数,其功能在于基于边传递消息。具体实现如下:

def gcn_msg(edge):
    msg = edge.src['h'] * edge.src['norm']
    return {'m': msg}

Edge UDFs 需要传入一个 edge 参数,其中 edge 有三个属性:src、dst、data,分别对应源节点特征、目标节点特征和边特征。

我们的 Message 函数,是从源节点向目标节点传递,所以只考虑源节点的特征。

节点中的 'norm' 用于归一化,具体计算方式后面会说。

对于每个节点来说,可能过会收到很多个源节点传过来的消息,所以可以将这些消息存储在邮箱中(mailbox)。

我们那再来定义一个聚合(Reduce)函数。

消息传递完后,每个节点都要处理下他们的“信箱”(mailbox),Reduce 函数的作用就是用来处理节点“信箱”的消息的。

Reduce 函数是一个 Node UDFs。

Node UDFs 接收一个 node 的参数,并且 node 有两个属性 data 和 mailbox,分别为节点的特征和用来接收信息的“信箱”。

def gcn_reduce(node):
    # 需要注意:消息存放在 mailbox 的第二个维上,第一维是消息的数量
    accum = torch.sum(node.mailbox['m'], dim=1) * node.data['norm']
    return {'h': accum}

Messge UDF 作用于边上,而 Reduce UDF 作用于节点上。两者的关系如下:

从左到右开始看,源节点通过 message 函数传递节点特征,并传递到目标节点的 Mailbox 中,在触发 Node UDF 时(这里为 Reduce 函数),Mailbox 将被清空。

上图中我们还可以看到作用于节点的有两个函数:Apply 函数和 Reduce 函数。

Reduce 函数我们上面介绍过了,那这个 Apply 函数是什么呢?

Apply 函数为节点更新的函数,可以用于「初始化参数」「对节点特征的进行非线形变换」

初始化参数:我们刚刚指出,参数分布服从 Glorot 均匀分布,所以要给节点加偏置的话,我们也需要将其初始化为并使其服从 Glorot 均匀分布,如下面代码中的 reset_parameters 函数

非线形变换:GCN 中每一层进行传递后,节点可能需要进行非线形变换,如下面代码中 forward 函数

class NodeApplyModule(nn.Module):
    def __init__(self, out_feats, activation=None, bias=True):
        super(NodeApplyModule, self).__init__()
        if bias:
            self.bias = nn.Parameter(torch.Tensor(out_feats))
        else:
            self.bias = None
        self.activation = activation
        self.reset_parameters()

    def reset_parameters(self):
        if self.bias is not None:
            stdv = 1. / math.sqrt(self.bias.size(0))
            self.bias.data.uniform_(-stdv, stdv)

    def forward(self, nodes):
        h = nodes.data['h']
        if self.bias is not None:
            h = h + self.bias
        if self.activation:
            h = self.activation(h)
        return {'h': h}

有了 Message 函数、Reduce 函数和节点的更新函数后,我们需要将其连贯起来:

g.update_all(message_func='default', 
             reduce_func='default', 
             apply_node_func='default') 

这个函数可以用于发送信息并更新所有节点,是 send() 和 recv() 函数的一个简单组合

3.2.3 GCNLayer

有了这些后,我们便可以定义 GCNLayer 了:

class GCNLayer(nn.Module):
    def __init__(self,
                 g,
                 in_feats,
                 out_feats,
                 activation,
                 dropout,
                 bias=True):
        super(GCNLayer, self).__init__()
        self.g = g
        self.weight = nn.Parameter(torch.Tensor(in_feats, out_feats))
        if dropout:
            self.dropout = nn.Dropout(p=dropout)
        else:
            self.dropout = 0.
        self.node_update = NodeApplyModule(out_feats, activation, bias)
        self.reset_parameters()

    def reset_parameters(self):
        stdv = 1. / math.sqrt(self.weight.size(1))
        self.weight.data.uniform_(-stdv, stdv)

    def forward(self, h):
        if self.dropout:
            h = self.dropout(h)
        self.g.ndata['h'] = torch.mm(h, self.weight)
        self.g.update_all(gcn_msg, gcn_reduce, self.node_update)
        h = self.g.ndata.pop('h')
        return h

然后我们把 GCNLayer 拼接在一起组成 GCN 网络

class GCN(nn.Module):
    def __init__(self,
                 g,
                 in_feats,
                 n_hidden,
                 n_classes,
                 n_layers,
                 activation,
                 dropout):
        super(GCN, self).__init__()
        self.layers = nn.ModuleList()
        # input layer
        self.layers.append(GCNLayer(g, in_feats, n_hidden, activation, dropout))
        # hidden layers
        for i in range(n_layers - 1):
            self.layers.append(GCNLayer(g, n_hidden, n_hidden, activation, dropout))
        # output layer
        self.layers.append(GCNLayer(g, n_hidden, n_classes, None, dropout))

    def forward(self, features):
        h = features
        for layer in self.layers:
            h = layer(h)
        return h

3.3 Third version

DGL 的第三种写法:使用 DGL 的内置(builtin)函数

由于 Messge 和 Reduce 函数使用的比较频繁,所以 DGL 了内置函数以方便使用,我们把刚刚的 Message 和 Reduce 函数改变为内置函数有:

  • dgl.function.copy_src(src, out):Message 函数其实就是把源节点的特征拷贝到目标节点,所以可以换用内置的 copy_src 函数。
  • dgl.function.sum(msg, out):Reduce 函数其实就是聚合节点 Mailbox 中的消息,所以可以换用内置的 sum 函数。
class GCNLayer(nn.Module):
    def __init__(self,
                 g,
                 in_feats,
                 out_feats,
                 activation,
                 dropout,
                 bias=True):
        super(GCNLayer, self).__init__()
        self.g = g
        self.weight = nn.Parameter(torch.Tensor(in_feats, out_feats))
        if bias:
            self.bias = nn.Parameter(torch.Tensor(out_feats))
        else:
            self.bias = None
        self.activation = activation
        if dropout:
            self.dropout = nn.Dropout(p=dropout)
        else:
            self.dropout = 0.
        self.reset_parameters()

    def reset_parameters(self):
        stdv = 1. / math.sqrt(self.weight.size(1))
        self.weight.data.uniform_(-stdv, stdv)
        if self.bias is not None:
            self.bias.data.uniform_(-stdv, stdv)

    def forward(self, h):
        if self.dropout:
            h = self.dropout(h)
        h = torch.mm(h, self.weight)
        # normalization by square root of src degree
        h = h * self.g.ndata['norm']
        self.g.ndata['h'] = h
        self.g.update_all(fn.copy_src(src='h', out='m'),
                          fn.sum(msg='m', out='h'))
        h = self.g.ndata.pop('h')
        # normalization by square root of dst degree
        h = h * self.g.ndata['norm']
        # bias
        if self.bias is not None:
            h = h + self.bias
        if self.activation:
            h = self.activation(h)
        return h

  • 这里的做了两次的标准化,对应 GCN 公式中的
c_{ij}=\sqrt{|\mathcal{N}(i)|}\sqrt{|\mathcal{N}(j)|}

  • 这里把 Node 的 Apply 函数的功能合并到 GCNLayer 中了。
class GCN(nn.Module):
    def __init__(self,
                 g,
                 in_feats,
                 n_hidden,
                 n_classes,
                 n_layers,
                 activation,
                 dropout):
        super(GCN, self).__init__()
        self.layers = nn.ModuleList()
        # input layer
        self.layers.append(GCNLayer(g, in_feats, n_hidden, activation, 0.))
        # hidden layers
        for i in range(n_layers - 1):
            self.layers.append(GCNLayer(g, n_hidden, n_hidden, activation, dropout))
        # output layer
        self.layers.append(GCNLayer(g, n_hidden, n_classes, None, dropout))

    def forward(self, features):
        h = features
        for layer in self.layers:
            h = layer(h)
        return h

4.Train

dropout=0.5
gpu=-1
lr=0.01
n_epochs=200
n_hidden=16  # 隐藏层节点的数量
n_layers=2  # 输入层 + 输出层的数量
weight_decay=5e-4  # 权重衰减
self_loop=True  # 自循环
# cora 数据集

data = citegrh.load_cora()
features = torch.FloatTensor(data.features)
labels = torch.LongTensor(data.labels)
train_mask = torch.BoolTensor(data.train_mask)
val_mask = torch.BoolTensor(data.val_mask)
test_mask = torch.BoolTensor(data.test_mask)

in_feats = features.shape[1]
n_classes = data.num_labels
n_edges = data.graph.number_of_edges()

# 构建 DGLGraph
g = data.graph

if self_loop:
    g.remove_edges_from(nx.selfloop_edges(g))
    g.add_edges_from(zip(g.nodes(), g.nodes()))
g = DGLGraph(g)

这里大家可能会有些疑惑:为什么要先移除自环?然后再加上自环。

这个主要是为了防止原本数据集中有一部分的自环,如果不去掉直接加上自环的话,会导致一些节点有两个自环,而有些只有一个。

# 加载 GPU
if gpu < 0:
    cuda = False
else:
    cuda = True
    torch.cuda.set_device(gpu)
    features = features.cuda()
    labels = labels.cuda()
    train_mask = train_mask.cuda()
    val_mask = val_mask.cuda()
    test_mask = test_mask.cuda()
# 归一化,依据入度进行计算
degs = g.in_degrees().float()
norm = torch.pow(degs, -0.5)
norm[torch.isinf(norm)] = 0
if cuda:
    norm = norm.cuda()
g.ndata['norm'] = norm.unsqueeze(1)
# 创建一个 GCN 的模型,可以选择上面的任意一个进行初始化
model = GCN(g,
            in_feats,
            n_hidden,
            n_classes,
            n_layers,
            F.relu,
            dropout)

if cuda:
    model.cuda()
# 采用交叉熵损失函数和 Adam 优化器
loss_fcn = torch.nn.CrossEntropyLoss()

optimizer = torch.optim.Adam(model.parameters(),
                             lr=lr,
                             weight_decay=weight_decay)
# 定义一个评估函数
def evaluate(model, features, labels, mask):
    model.eval()
    with torch.no_grad():
        logits = model(features)
        logits = logits[mask]
        labels = labels[mask]
        _, indices = torch.max(logits, dim=1)
        correct = torch.sum(indices == labels)
        return correct.item() * 1.0 / len(labels)
# 训练,并评估
dur = []
for epoch in range(n_epochs):
    model.train()
    t0 = time.time()
    # forward
    logits = model(features)
    loss = loss_fcn(logits[train_mask], labels[train_mask])

    optimizer.zero_grad()
    loss.backward()
    optimizer.step()

    dur.append(time.time() - t0)

    if epoch % 10 == 0:
        acc = evaluate(model, features, labels, val_mask)
        print("Epoch {:05d} | Time(s) {:.4f} | Loss {:.4f} | Accuracy {:.4f} | "
              "ETputs(KTEPS) {:.2f}". format(epoch, np.mean(dur), loss.item(),
                                             acc, n_edges / np.mean(dur) / 1000))

print()
acc = evaluate(model, features, labels, test_mask)
print("Test accuracy {:.2%}".format(acc))

Epoch 00000 | Time(s) 0.0178 | Loss 1.9446 | Accuracy 0.2100 | ETputs(KTEPS) 594.54
Epoch 00010 | Time(s) 0.0153 | Loss 1.7609 | Accuracy 0.3533 | ETputs(KTEPS) 689.33
Epoch 00020 | Time(s) 0.0150 | Loss 1.5518 | Accuracy 0.5633 | ETputs(KTEPS) 703.47
Epoch 00030 | Time(s) 0.0146 | Loss 1.2769 | Accuracy 0.5867 | ETputs(KTEPS) 721.28
Epoch 00040 | Time(s) 0.0143 | Loss 1.0785 | Accuracy 0.6567 | ETputs(KTEPS) 740.36
Epoch 00050 | Time(s) 0.0140 | Loss 0.8881 | Accuracy 0.7067 | ETputs(KTEPS) 754.21
Epoch 00060 | Time(s) 0.0138 | Loss 0.6994 | Accuracy 0.7533 | ETputs(KTEPS) 763.21
Epoch 00070 | Time(s) 0.0137 | Loss 0.6249 | Accuracy 0.7800 | ETputs(KTEPS) 770.54
Epoch 00080 | Time(s) 0.0137 | Loss 0.5048 | Accuracy 0.7800 | ETputs(KTEPS) 772.31
Epoch 00090 | Time(s) 0.0136 | Loss 0.4457 | Accuracy 0.7867 | ETputs(KTEPS) 778.78
Epoch 00100 | Time(s) 0.0135 | Loss 0.4167 | Accuracy 0.7800 | ETputs(KTEPS) 782.25
Epoch 00110 | Time(s) 0.0134 | Loss 0.3389 | Accuracy 0.8000 | ETputs(KTEPS) 786.52
Epoch 00120 | Time(s) 0.0134 | Loss 0.3777 | Accuracy 0.8100 | ETputs(KTEPS) 789.85
Epoch 00130 | Time(s) 0.0133 | Loss 0.3307 | Accuracy 0.8133 | ETputs(KTEPS) 792.00
Epoch 00140 | Time(s) 0.0133 | Loss 0.2542 | Accuracy 0.7933 | ETputs(KTEPS) 794.13
Epoch 00150 | Time(s) 0.0133 | Loss 0.2937 | Accuracy 0.8000 | ETputs(KTEPS) 795.73
Epoch 00160 | Time(s) 0.0132 | Loss 0.2944 | Accuracy 0.8333 | ETputs(KTEPS) 797.04
Epoch 00170 | Time(s) 0.0132 | Loss 0.2161 | Accuracy 0.8167 | ETputs(KTEPS) 799.74
Epoch 00180 | Time(s) 0.0132 | Loss 0.1972 | Accuracy 0.8200 | ETputs(KTEPS) 801.31
Epoch 00190 | Time(s) 0.0131 | Loss 0.2339 | Accuracy 0.8167 | ETputs(KTEPS) 802.92

Test accuracy 80.40%

5.Conclusion

以上便是本教程的全部,当然还有其他实现的方法,比如说,直接利用矩阵相乘来进行迭代。

6.References

  1. DGL Github
  2. DGL 官方文档
  3. 《深度学习——Xavier初始化方法》
  4. 《DGL 作者答疑!关于 DGL 你想知道的都在这里-周金晶》

本文分享自微信公众号 - 阿泽的学习笔记(aze_learning),作者:阿泽crz

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-09

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Code】GraphSAGE 源码解析

    本文代码源于 DGL 的 Example 的,感兴趣可以去 github 上面查看。

    阿泽 Crz
  • 【DL】初始化:你真的了解我吗?

    「固定初始化」是指将模型参数初始化为一个固定的常数,这意味着所有单元具有相同的初始化状态,所有的神经元都具有相同的输出和更新梯度,并进行完全相同的更新,这种初始...

    阿泽 Crz
  • 【Pytorch 】笔记六:初始化与 18 种损失函数的源码解析

    疫情在家的这段时间,想系统的学习一遍 Pytorch 基础知识,因为我发现虽然直接 Pytorch 实战上手比较快,但是关于一些内部的原理知识其实并不是太懂,这...

    阿泽 Crz
  • 用最小二乘法对多项式进行拟合并可视化

    本篇文章所讲代码是对2018年全国大学生数学建模比赛A题附件的数据进行拟合,代码如下:

    用户3577892
  • 跨平台PHP调试器设计及使用方法——通信

            首先引用《跨平台PHP调试器设计及使用方法——探索和设计》中的结构图(转载请指明出于breaksoftware的csdn博客)

    方亮
  • 5 分钟教你用 Python 实现贪吃蛇!

    贪吃蛇作为一款经典小游戏,早在 1976 年就面世了,我最早接触它还是在家长的诺基亚手机中。

    Python小二
  • 你的童年有俄罗斯方块吗?教你用 Python 实现俄罗斯方块!

    还是为数不多的游戏类电子产品,对小孩子更是有着不可抗拒的魔力,在当时如果哪个小孩买了一个小游戏机,大伙一定迅速围上去...

    Python小二
  • Python GUI项目实战(二)主窗体的界面设计与实现

    上一节我们介绍了登录窗体的GUI设计与功能实现,用户的账号和密码校验完成后应当跳转到主窗体内容,这一节我们将具体介绍主窗体界面的设计与功能实现!

    小雨编程
  • 我的小工具-远程读卡器web客户端(nodejs+websocket实现实时指令交互)

    之前的小工具,远程读卡器web客户端,实现原理是把读写卡服务装在远程(现场)的电脑上,这样有一些缺点,比如现场电脑必须开启端口映射,让客户端能否访问到。只能写好...

    特立独行的猫a
  • 我的小工具,用C和python实现远程读卡器,远程读写消费卡片

    这个远程读卡器就是一普通usb口或串口的读卡器,只不过配合一个电脑软件作为tcp服务器。这样,程序员可以在公司电脑上运行程序连到服务器上。服务器端操作控制现场...

    特立独行的猫a

扫码关注云+社区

领取腾讯云代金券