SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS

Thomas N. Kipf、MaxWelling

Published as a conference paper at ICLR 2017

论文笔记：2021-10-20

若有侵权，请在第一时间通知博主，博主会及时处理！

背景与结论

在图节点分类任务中（一张图有边、节点、节点特征和节点标签等等），只有一小部分的节点有标签，这个问题可以被建模成基于图的半监督学习，本文用的传播模块为卷积运算，并介绍了如何设计图卷积神经网络。
在计算机视觉，卷积的应用使得深度学习有了巨大突破。由于图片的平移不变性，CNN能够通过卷积运算来提取多尺度局部空间特征，但是很难定义局部卷积滤波器和池化算子，这阻碍了CNN从欧几里德域到非欧几里德域的转换。如何定义在图上的高效卷积是本篇论文研究的重点。

第一个问题：关于GCN损失函数的设计

在传统的图半监督学习，是通过监督损失+图拉普拉斯正则化项来计算loss，原理是想利用相邻的顶点倾向于拥有相同的标签这一假设来完成半监督学习过程。公式需要满足假设：图中的相邻节点可能具有相同的标签。

注意：这里的解释参考自博客2
但是有时图的边未必能够很好地表示顶点的相似性，比如在论文分类任务中，论文的引用关系作为图的边，一篇物理论文与数学论文和计算机论文相连，如果使用上述损失函数训练学习器, 则学习器很可能会把一篇物理类论文预测成一篇数学类论文或者计算机类论文。相邻的顶点倾向于拥有相同的标签这一假设太过严格, 会限制学习器的预测能力。

该论文的损失函数为交叉熵，只用有标签的结点。

YL表示有标签的节点集。公式中的Y为one-hot向量，该损失函数保障了对于带有标签的顶点, 其预测类别和真实类别尽量相同。而神经网络中蕴藏的图结构保障了在图上相近的顶点具有相同或相近的预测值（通过卷积来提取一个顶点及其相邻顶点的特征, 从而直接把图的结构用GCN来表示）, 但又不会像传统的方法一样因过于严格的假设而降低模型的预测能力。

第二个问题：关于图卷积核的设计

我们知道傅里叶变换可以将时域转换到频域分析。在图信号分析中，可以用拉普拉斯谱分解的正交矩阵U，将图从空间域变换到谱域，将空域中的拓扑图结构通过傅立叶变换映射到谱域中并相乘，然后利用逆变换返回空域，从而完成了图卷积操作。并且可以实现参数全局共享。
第一代卷积核公式：

但是U的计算复杂度为N^2，利用K阶切比雪夫多项式去近似gθ，，将其带入第一代卷积，又根据和，可以将公式中最难计算的U变成放到T中，避免计算。
第二代卷积核公式：

论文中对卷积核进行了简化，文章对上式进行了进一步近似: 只取切比雪夫多项式的前两项：
这里的一阶近似, 相当于提取取了图中每个顶点的一阶相邻顶点的特征.
并且假设前两项的参数：
此时有：
根据进一步化简
第三代卷积核公式：
传播的规则：

第三个问题：为什么是卷积公式用的是Ã而不是A

我们知道图卷积可以提取图的特征，聚合节点信息。当我们用A的时候，只聚合了邻居特征，却忽视了自身的节点信息，所以需要对邻接矩阵做进一步处理，引入自身节点信息。公式为：

第四个问题：怎么解释卷积公式的归一化

如果我们叠加了多层，经过多次AH(l)，其结果H(l+1)也会越来越大，和输入X的差距也会越来越大。度的大节点特征值会越来越大，度小的节点特征值会越来越小，传播过程对特征的尺度敏感。因此我们需要对其进行归一化，最简单的做法是将结果除以节点的度。在这篇论文中，使用的归一化方式是对称的归一化。

第五个问题：推导过程中的意义

注意：这里的解释参考自博客2和知乎3
的特征值范围在 [0, 2] 之间，所以如果在很深的网络中会引起梯度爆炸的问题，这样很可能会导致无法稳定收敛!原文也称renormalization trick

第六个问题：为什么是切比雪夫近似

注意：这里的观点来自于参考的博客2

根据作者得到的公式，既然只取前两项，为什么不可以看作是从普通多项式中取出的两项？
在作者的推导过程中，因为切比雪夫多项式的定义域在[-1, 1]之内，作者将L进行了放缩，以及在第五个问题中提到的替换。而普通的多项式方法对应的则是Table 3中的First-order term only，效果并不好。所以推到过程中利用切比雪夫多项式的条件对公式进行的变换是必不可少的，

第七个问题：关于模型的优势和缺陷

优势1：即使不训练，直接随机初始化参数也可以获得不错的效果

优势2：即使只有少量标注的样本，GCN也能得到很好的嵌入效果。

优势3：GCN的设计流程相对通用简单，基于skip-gram的方法需要随机游走生成和半监督训练的多步骤管道，其中每个步骤都必须单独优化。

缺陷1：内存限制，一次训练一整个图，内存需求随数据集大小呈线性增加

缺陷2：有向边和边特征，GCN不支持边的特征，并且仅限于无向图

缺陷3：过度平滑问题，在图神经网络的训练过程中，随着网络层数的增加和迭代次数的增加，每个节点的隐层表征会趋向于收敛到同一个值。

第八个问题：关于数据集

该论文提到了一些图神经网络常用的数据集，比如Citeseer、Cora、Pubmed还有NELL。
以Cora为例子来解释GCN的输入：X、A、Y。
Cora：“Collective classification in network data,” AI magazine,2008
Cora数据集是与论文相关的图，整个语料库共有2708篇论文。节点代表论文，边代表论文之间的引用关系。
X：表示节点的特征矩阵(1708,1433)，参与训练的节点有1708个。在所有论文的单词中，将文档频率小于10的所有单词都删除，并删除词尾等等，只剩下1433个独特单词，所以特征是1433维。0和1描述的是每个单词在paper中是否存在。（注意：训练节点有1433个，而计算损失时只用有label的标签，该数据集有label的标签有140个）
A：表示图的邻接矩阵。
Y：表示节点的标签，(140,7)，有140个节点有标签，共7有种label。

第九个问题：关于模型代码（pytorch实现）

注意：代码来自https://github.com/tkipf/pygcn/tree/master/data/cora

─pygcn # 模型文件夹
 │ .gitignore
 │ figure.png
 │ LICENCE
 │ README.md
 │ setup.py
 │
 ├─data # 数据
 │ └─cora
 │ cora.cites
 │ cora.content
 │ README
 │
 └─pygcn # 模型代码
    layers.py # 卷积层定义
    models.py # 模型定义
    train.py # 配置和启动训练
    utils.py # 相关工具，如one-hot编码、加载数据集等
    __init__.py # 将文件夹变为一个Python模块，批量引入

__init__.py：

from __future__ import print_function
from __future__ import division

from .layers import *
from .models import *
from .utils import *

layers.py：
在进行卷积的时候，因为adj是稀疏矩阵，所以先矩阵乘法得到XW，再用稀疏矩阵乘法计算adjXW，效率会更高。

import math

import torch

from torch.nn.parameter import Parameter
from torch.nn.modules.module import Module


class GraphConvolution(Module):
    """
    Simple GCN layer, similar to https://arxiv.org/abs/1609.02907
    """

    def __init__(self, in_features, out_features, bias=True):
        super(GraphConvolution, self).__init__()
        self.in_features = in_features
        self.out_features = out_features
        self.weight = Parameter(torch.FloatTensor(in_features, out_features))
        if bias:
            self.bias = Parameter(torch.FloatTensor(out_features))
        else:
            self.register_parameter('bias', None)
        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, input, adj):
        support = torch.mm(input, self.weight)
        output = torch.spmm(adj, support)
        if self.bias is not None:
            return output + self.bias
        else:
            return output

    def __repr__(self):
        return self.__class__.__name__ + ' (' \
               + str(self.in_features) + ' -> ' \
               + str(self.out_features) + ')'

models.py：
两层的GCN就可以取得很好的效果，过深的GCN因为过度平滑的问题会导致准确率下降，每个节点的隐层表征会趋向于收敛到同一个值，是模型的缺陷之一。
注意在前向传播的时候dropout防止过拟合。

import torch.nn as nn
import torch.nn.functional as F
from pygcn.layers import GraphConvolution


class GCN(nn.Module):
    def __init__(self, nfeat, nhid, nclass, dropout):
        super(GCN, self).__init__()

        self.gc1 = GraphConvolution(nfeat, nhid)
        self.gc2 = GraphConvolution(nhid, nclass)
        self.dropout = dropout

    def forward(self, x, adj):
        x = F.relu(self.gc1(x, adj))
        x = F.dropout(x, self.dropout, training=self.training)
        x = self.gc2(x, adj)
        return F.log_softmax(x, dim=1)

train.py：

from __future__ import division
from __future__ import print_function

import time
import argparse
import numpy as np

import torch
import torch.nn.functional as F
import torch.optim as optim

from pygcn.utils import load_data, accuracy
from pygcn.models import GCN

# Training settings
parser = argparse.ArgumentParser()
parser.add_argument('--no-cuda', action='store_true', default=False,
                    help='Disables CUDA training.')
parser.add_argument('--fastmode', action='store_true', default=False,
                    help='Validate during training pass.')
parser.add_argument('--seed', type=int, default=42, help='Random seed.')
parser.add_argument('--epochs', type=int, default=200,
                    help='Number of epochs to train.')
parser.add_argument('--lr', type=float, default=0.01,
                    help='Initial learning rate.')
parser.add_argument('--weight_decay', type=float, default=5e-4,
                    help='Weight decay (L2 loss on parameters).')
parser.add_argument('--hidden', type=int, default=16,
                    help='Number of hidden units.')
parser.add_argument('--dropout', type=float, default=0.5,
                    help='Dropout rate (1 - keep probability).')

args = parser.parse_args()
args.cuda = not args.no_cuda and torch.cuda.is_available()

np.random.seed(args.seed)
torch.manual_seed(args.seed)
if args.cuda:
    torch.cuda.manual_seed(args.seed)

# Load data
adj, features, labels, idx_train, idx_val, idx_test = load_data()

# Model and optimizer
model = GCN(nfeat=features.shape[1],
            nhid=args.hidden,
            nclass=labels.max().item() + 1,
            dropout=args.dropout)
optimizer = optim.Adam(model.parameters(),
                       lr=args.lr, weight_decay=args.weight_decay)

if args.cuda:
    model.cuda()
    features = features.cuda()
    adj = adj.cuda()
    labels = labels.cuda()
    idx_train = idx_train.cuda()
    idx_val = idx_val.cuda()
    idx_test = idx_test.cuda()


def train(epoch):
    t = time.time()
    model.train()
    optimizer.zero_grad()
    output = model(features, adj) # 前向传播
    loss_train = F.nll_loss(output[idx_train], labels[idx_train]) # 只选择训练节点进行监督计算损失值
    acc_train = accuracy(output[idx_train], labels[idx_train])
    loss_train.backward() # 反向传播计算参数的梯度
    optimizer.step() # 使用优化方法进行梯度更新

    if not args.fastmode:
        # Evaluate validation set performance separately,
        # deactivates dropout during validation run.
        model.eval()
        output = model(features, adj)

    loss_val = F.nll_loss(output[idx_val], labels[idx_val])
    acc_val = accuracy(output[idx_val], labels[idx_val])
    print('Epoch: {:04d}'.format(epoch+1),
          'loss_train: {:.4f}'.format(loss_train.item()),
          'acc_train: {:.4f}'.format(acc_train.item()),
          'loss_val: {:.4f}'.format(loss_val.item()),
          'acc_val: {:.4f}'.format(acc_val.item()),
          'time: {:.4f}s'.format(time.time() - t))


def test():
    model.eval()
    output = model(features, adj)
    loss_test = F.nll_loss(output[idx_test], labels[idx_test])
    acc_test = accuracy(output[idx_test], labels[idx_test])
    print("Test set results:",
          "loss= {:.4f}".format(loss_test.item()),
          "accuracy= {:.4f}".format(acc_test.item()))


# Train model
t_total = time.time()
for epoch in range(args.epochs):
    train(epoch)
print("Optimization Finished!")
print("Total time elapsed: {:.4f}s".format(time.time() - t_total))

# Testing
test()

utils.py：

import numpy as np
import scipy.sparse as sp
import torch


def encode_onehot(labels):
    classes = set(labels)
    classes_dict = {c: np.identity(len(classes))[i, :] for i, c in
                    enumerate(classes)}
    labels_onehot = np.array(list(map(classes_dict.get, labels)),
                             dtype=np.int32)
    return labels_onehot


def load_data(path="../data/cora/", dataset="cora"):
    """Load citation network dataset (cora only for now)"""
    print('Loading {} dataset...'.format(dataset))

    idx_features_labels = np.genfromtxt("{}{}.content".format(path, dataset),
                                        dtype=np.dtype(str))
    features = sp.csr_matrix(idx_features_labels[:, 1:-1], dtype=np.float32)
    labels = encode_onehot(idx_features_labels[:, -1])

    # build graph
    idx = np.array(idx_features_labels[:, 0], dtype=np.int32)
    idx_map = {j: i for i, j in enumerate(idx)}
    edges_unordered = np.genfromtxt("{}{}.cites".format(path, dataset),
                                    dtype=np.int32)
    edges = np.array(list(map(idx_map.get, edges_unordered.flatten())),
                     dtype=np.int32).reshape(edges_unordered.shape)
    adj = sp.coo_matrix((np.ones(edges.shape[0]), (edges[:, 0], edges[:, 1])),
                        shape=(labels.shape[0], labels.shape[0]),
                        dtype=np.float32)

    # build symmetric adjacency matrix
    adj = adj + adj.T.multiply(adj.T > adj) - adj.multiply(adj.T > adj)

    features = normalize(features)
    adj = normalize(adj + sp.eye(adj.shape[0]))

    idx_train = range(140)
    idx_val = range(200, 500)
    idx_test = range(500, 1500)

    features = torch.FloatTensor(np.array(features.todense()))
    labels = torch.LongTensor(np.where(labels)[1])
    adj = sparse_mx_to_torch_sparse_tensor(adj)

    idx_train = torch.LongTensor(idx_train)
    idx_val = torch.LongTensor(idx_val)
    idx_test = torch.LongTensor(idx_test)

    return adj, features, labels, idx_train, idx_val, idx_test


def normalize(mx):
    """Row-normalize sparse matrix"""
    rowsum = np.array(mx.sum(1))
    r_inv = np.power(rowsum, -1).flatten()
    r_inv[np.isinf(r_inv)] = 0.
    r_mat_inv = sp.diags(r_inv)
    mx = r_mat_inv.dot(mx)
    return mx


def accuracy(output, labels):
    preds = output.max(1)[1].type_as(labels)
    correct = preds.eq(labels).double()
    correct = correct.sum()
    return correct / len(labels)


def sparse_mx_to_torch_sparse_tensor(sparse_mx):
    """Convert a scipy sparse matrix to a torch sparse tensor."""
    sparse_mx = sparse_mx.tocoo().astype(np.float32)
    indices = torch.from_numpy(
        np.vstack((sparse_mx.row, sparse_mx.col)).astype(np.int64))
    values = torch.from_numpy(sparse_mx.data)
    shape = torch.Size(sparse_mx.shape)
    return torch.sparse.FloatTensor(indices, values, shape)

笔记参考的博客

1.https://aistudio.baidu.com/aistudio/projectdetail/1782074?channelType=0&channel=0
2.https://blog.csdn.net/qq_42013492/article/details/96462630
3.https://zhuanlan.zhihu.com/p/120311352
4.https://www.cnblogs.com/BlairGrowing/p/15323995.html
5.https://www.cnblogs.com/daztricky/p/15010350.html
6.https://github.com/tkipf/pygcn/