专栏首页程序生活图神经网络06-基于Graph的传统机器学习方法

图神经网络06-基于Graph的传统机器学习方法

1 图学习任务

我们简单回顾下,上一节我们介绍了,图的机器学习任务主要是以下三种:

  • Node Level:节点级别
  • Link Level:边级别
  • Graph Level:图级别å 并且三部分难度依次是由浅入深的

2 传统ML流程

  • 定义和设计节点/边/图的特征
  • 对所有训练数据构造特征
  • 训练ML模型 (1)随机森林 (2)支持向量机 (3)神经网络等
  • 应用模型 给定一个新的节点、边、图,然后获取特征进行预测

我们总结下 基于Graph的机器学习相关概念和流程,首先明确下目标

目标:对一些对象集合进行预测,比如是分类或者回归任务 特征设计:

  • 特征:d-dimensional向量
  • 对象:Nodes,edges,或者是graps
  • 目标函数:结合具体任务设计目标函数,如下图所示给定一个图G(V,E),其中V代表节点集合,E代表边集合,然后学习节点到向量空间R的映射函数,也就是我们要学习权重参数W

为了方便,我们下面的例子是基于无向图(undirected grpah)进行解释的。

3 节点级别的相关任务

基于图中带有标签的节点训练模型,然后预测未标注节点的标签,

在这里我们主要阐述下Node的四种特征:

  • Node degree:节点的度
  • Node centrality:节点的中度
  • Clustering coefficient:相似性
  • Graphlets:图元

节点的度

  • kv代表是节点v与邻居节点相连边的个数
  • 所有邻居节点都是相等的

如下图所示,A的度为1,B的度为2,C的度为3,D的度为4

节点的中心度 Node Centrality

  • 节点的度只计算了相连节点的个数,但是没有评估节点的重要性
  • 节点的中心度

考虑了节点在图中的重要程度

  • 节点的中心度有很多种计算方式: (1) Engienvector centrality:特征向量中心性 (2) Betweenness centrality:中介中心性 (3) Closeness centrality:紧密中心性 (4) 其他方式

Eigenvector centrality:特征向量中心性

  • 如果一个节点的邻居节点们

越重要,那么该节点

就越重要

  • 我们将节点?的中心性建模为相邻节点的中心性之和:

其中

为一个正常数。

  • 我们注意到上面的等式是通过递归的方式来计算度度中心性的,所有我们应该怎么求解

其中

为正常数,

为邻接矩阵,如果

,那么

  • 我们可以看到度中心性是一个特征向量(eigenvector),根据非负矩阵定理(Perron-Frobenius Theorem)我们可以知道

是一个正值并且是唯一的,特征向量

当做度中心性。

通常来说,有许多不同的特征值

能使得一个特征方程有非零解存在。然而,考虑到特征向量中的所有项均为非负值,根据佩伦-弗罗贝尼乌斯定理,只有特征值最大时才能测量出想要的中心性。然后通过计算网络中的节点

其特征向量的相关分量

便能得出其对应的中心性的分数。

特征向量的定义只有一个公因子,因此各节点中心性的比例可以很好确定。为了确定一个绝对分数,必须将其中一个特征值标准化,例如所有节点评分之和为1或者节点数 n。幂次迭代是许多特征值算法中的一种,该算法可以用来寻找这种主导特征向量。此外,以上方法可以推广,使得矩阵A中每个元素可以是表示连接强度的实数,例如随机矩阵。---特征向量中心性wiki

这里其实涉及到比较多的线性代数的理论以及矩阵分析的算法,我特意查了一些文章帮大家去回顾和理解下这里涉及到的知识: (1) 线性代数之——特征值和特征向量 (2)非负矩阵之Perron-Frobenius定理 (3)非负矩阵 (4)干货 | 万字长文带你复习线性代数!

我们这里再通过文章谁是社会网络中最重要的人?解释特征向量中心性: 特征向量中心性的基本思想是,一个节点的中心性是相邻节点中心性的函数。也就是说,与你连接的人越重要,你也就越重要

特征向量中心性和点度中心性不同,一个点度中心性高即拥有很多连接的节点特征向量中心性不一定高,因为所有的连接者有可能特征向量中心性很低。同理,特征向量中心性高并不意味着它的点度中心性高,它拥有很少但很重要的连接者也可以拥有高特征向量中心性。

考虑下面的图,以及相应的5x5的邻接矩阵(Adjacency Matrix),A。

邻接矩阵的含义是,如果两个节点没有直接连接,记为0,否则记为1。

现在考虑x,一个5x1的向量,向量的值对应图中的每个点。在这种情况下,我们计算的是每个点的点度中心性(degree centrality),即以点的连接数来衡量中心性的高低。

矩阵A乘以这个向量的结果是一个5x1的向量:

结果向量的第一个元素是用矩阵A的第一行去“获取”每一个与第一个点有连接的点的值(连接数,点度中心性),也就是第2个、第3个和第4个点的值,然后将它们加起来。

换句话说,邻接矩阵做的事情是将相邻节点的求和值重新分配给每个点。这样做的结果就是“扩散了”点度中心性。你的朋友的朋友越多,你的特征向量中心性就越高。

我们继续用矩阵A乘以结果向量。如何理解呢?实际上,我们允许这一中心性数值再次沿着图的边界“扩散”。我们会观察到两个方向上的扩散(点既给予也收获相邻节点)。我们猜测,这一过程最后会达到一个平衡,特定点收获的数量会和它给予相邻节点的数量取得平衡。既然我们仅仅是累加,数值会越来越大,但我们最终会到达一个点,各个节点在整体中的比例会保持稳定。

现在把所有点的数值构成的向量用更一般的形式表示:

我们认为,图中的点存在一个数值集合,对于它,用矩阵A去乘不会改变向量各个数值的相对大小。也就是说,它的数值会变大,但乘以的是同一个因子。用数学符号表示就是:

满足这一属性的向量就是矩阵M的特征向量。特征向量的元素就是图中每个点的特征向量中心性。

特征向量中心性的计算需要读者具备矩阵乘法和特征向量的知识,但不影响这里读者对特征向量中心性思想的理解,不再赘述。

Betweenness centrality:中介中心性 如果一个节点位于很多条其他节点的最短路径上,那么改节点比较重要,定义如下:

我们可以看一个下面的例子:

假设我们要计算D的中介中心性:

  • 首先,我们计算节点D之外,所有节点对之间的最短路径有多少条,这里是1条(在5个节点中选择两个节点即节点对的个数)。
  • 然后,我们再看所有这些最短路径中有多少条经过节点D,例如节点A要想找到节点E,必须经过节点D。经过节点D的最短路径有3条(A-C-D-E,B-D-E,C-D-E)。
  • 最后,我们用经过节点D的最短路径除以所有节点对的最短路径总数,这个比率就是节点D的中介中心性。节点D的中介中心性是3/1=3。

4 PyTorch Geometric教程

官方文档:https://pytorch-geometric.readthedocs.io/en/latest/index.html

PyTorch Geometric(PyG)是PyTorch的扩展库。 它提供了有用的框架来开发图深度学习模型,包括各种图神经网络层和大量基准数据集。

如果我们暂时不了解某些概念,例如“ GCNConv”,请不要担心,之后我们将在以后的文章中介绍这些概念。

这个教程来自: https://colab.research.google.com/drive/1h3-vJGRVloF5zStxL5I0rSy4ZUPNsjy8?usp=sharing#scrollTo=ci-LpZWhRJoI by Matthias Fey

大家可以参照colab教程直接运行

4.1 PyG安装

  • 查看当前torch和cuda版本
!python -c "import torch; print(torch.__version__)"

输出:1.6.0

!python -c "import torch; print(torch.version.cuda)"

输出:10.1

  • 安装gpu版本
# 安装GPU版本
!pip install --no-index torch-scatter -f https://pytorch-geometric.com/whl/torch-1.7.0+cu101.html
!pip install --no-index torch-sparse -f https://pytorch-geometric.com/whl/torch-1.7.0+cu101.html
!pip install --no-index torch-cluster -f https://pytorch-geometric.com/whl/torch-1.7.0+cu101.html
!pip install --no-index torch-spline-conv -f https://pytorch-geometric.com/whl/torch-1.7.0+cu101.html
!pip install torch-geometric

可能安装gpu版本比较麻烦,大家可以多参照下官网进行安装: https://pytorch-geometric.readthedocs.io/en/latest/notes/installation.html

image

  • 安装cuda版本
!pip install torch-scatter==latest+cpu -f https://pytorch-geometric.com/whl/torch-1.6.0.html
!pip install torch-sparse==latest+cpu -f https://pytorch-geometric.com/whl/torch-1.6.0.html
!pip install torch-cluster==latest+cpu -f https://pytorch-geometric.com/whl/torch-1.6.0.html
!pip install torch-spline-conv==latest+cpu -f https://pytorch-geometric.com/whl/torch-1.6.0.html
!pip install torch-geometric

4.2 PyG数据集

PyTorch Geometric 可以通过 torch_geometric.datasets 快速的获取默认的数据集:

https://pytorch-geometric.readthedocs.io/en/latest/modules/datasets.html

image

一共有20+种数据,比较丰富~

# 导入空手道俱乐部数据集
from torch_geometric.datasets import KarateClub
dataset = KarateClub()
print(f'Dataset: {dataset}:')
print('======================')
print(f'Number of graphs: {len(dataset)}')
print(f'Number of features: {dataset.num_features}')
print(f'Number of classes: {dataset.num_classes}')

输出:

Dataset: KarateClub():
======================
Number of graphs: 1
Number of features: 34
Number of classes: 4

初始化[KarateClub](https://pytorch-geometric.readthedocs.io/en/latest/modules/datasets.html#torch_geometric.datasets.KarateClub) 数据集之后,我们首先可以检查其某些属性。 例如,我们可以看到该数据集恰好有一个Graph,并且该数据集中的每个节点都被分配了** 34维特征向量(唯一地描述了空手道俱乐部的成员)。 此外,该图正好包含 4个类别**,代表每个节点所属的社区。

现在让我们更详细地看一下这个Graph:

data = dataset[0]  # 获取graph对象.

print(data)
print('==============================================================')

# 获取一些graph的统计信息.
print(f'Number of nodes: {data.num_nodes}') # 节点的个数
print(f'Number of edges: {data.num_edges}') # 边的个属于
print(f'Average node degree: {data.num_edges / data.num_nodes:.2f}') # 节点的度平均数
print(f'Number of training nodes: {data.train_mask.sum()}')
print(f'Training node label rate: {int(data.train_mask.sum()) / data.num_nodes:.2f}')
print(f'Contains isolated nodes: {data.contains_isolated_nodes()}')
print(f'Contains self-loops: {data.contains_self_loops()}')
print(f'Is undirected: {data.is_undirected()}')

输出如下:

Data(edge_index=[2, 156], train_mask=[34], x=[34, 34], y=[34])
==============================================================
Number of nodes: 34
Number of edges: 156
Average node degree: 4.59
Number of training nodes: 4
Training node label rate: 0.12
Contains isolated nodes: False
Contains self-loops: False
Is undirected: True

通过上面的信息我们可以发现,这个KarateClub网络图一共有34个节点,边的个数为1,每个节点度的平均数有4.59,是一个无向图等等。

4.3 Data对象

PyTorch Geometric中的每个图形都由单个[Data](https://pytorch-geometric.readthedocs.io/en/latest/modules/data.html#torch_geometric.data.Data)对象表示,该对象包含所有 描述其图形表示的信息。 我们可以随时通过print(data)打印数据对象,以接收有关其属性及其形状的简短介绍:

Data(edge_index=[2, 156], x=[34, 34], y=[34], train_mask=[34])

我们可以看到这个data对象拥有4个属性: (1)“ edge_index”属性保存有关“图形连接性”(即)的信息,即每个边缘的源节点和目标节点索引的元组。 PyG进一步将 (2)节点特征称为x(向34个节点中的每个节点分配了34维度的特征向量),将 (3)节点标记*称为y(每个节点仅分配给一个类别)。 (4)还有一个名为“ train_mask”的附加属性,它描述了我们已经知道其社区归属的节点。 总体而言,我们只知道4个节点的基本标签(每个社区一个),任务是推断其余节点的社区分配。

数据对象还提供了一些“实用功能”来推断基础图的一些基本属性。 例如,我们可以轻松推断图中是否存在孤立的节点(* ie 任何节点都没有边),图是否包含自环(i.e.,

),或者图形是否是无向的( (i.e.*, for each edge

there also exists the edge

).

from IPython.display import Javascript  # Restrict height of output cell.
display(Javascript('''google.colab.output.setIframeHeight(0, true, {maxHeight: 300})'''))

edge_index = data.edge_index
# 打印节点
print(edge_index.t())

输出:

tensor([[ 0,  1],
        [ 0,  2],
        [ 0,  3],
        [ 0,  4],
        [ 0,  5],
        [ 0,  6],
        [ 0,  7],
        [ 0,  8],
        [ 0, 10],
        ....
        [33, 31],
        [33, 32]])

通过打印“ edge_index”,我们可以进一步了解PyG如何在内部表示图形连接。 我们可以看到,对于每个边缘,“ edge_index”都包含两个节点索引的元组,其中第一个值描述源节点的节点索引,第二个值描述边缘目标节点的节点索引。

这种表示称为** COO格式(坐标格式)**,通常用于表示稀疏矩阵。 代替以密集表示形式保存邻接信息

,,PyG稀疏地表示图形,这是指仅保存

中的条目为非零的坐标/值。

最后,我们可以通过将图形转换为networkx库格式来进一步可视化图形,该格式除了图形操作功能之外,还实现了强大的可视化工具。我们创建一个专门用于展示Graph的函数

%matplotlib inline
import torch
import networkx as nx
import matplotlib.pyplot as plt

# Visualization function for NX graph or PyTorch tensor
def visualize(h, color, epoch=None, loss=None):
    plt.figure(figsize=(7,7))
    plt.xticks([])
    plt.yticks([])

    if torch.is_tensor(h):
        h = h.detach().cpu().numpy()
        plt.scatter(h[:, 0], h[:, 1], s=140, c=color, cmap="Set2")
        if epoch is not None and loss is not None:
            plt.xlabel(f'Epoch: {epoch}, Loss: {loss.item():.4f}', fontsize=16)
    else:
        nx.draw_networkx(G, pos=nx.spring_layout(G, seed=42), with_labels=False,
                         node_color=color, cmap="Set2")
    plt.show()
from torch_geometric.utils import to_networkx

G = to_networkx(data, to_undirected=True)
visualize(G, color=data.y)

image

4.4 实战:基于GCN的Graph节点分类

接下来将通过Pytorch实现一个最基本的GCN网络用语节点分类,基于带有标签的节点数据进行训练模型,然后预测未带有标签的数据

在了解了PyG的数据处理之后,是时候实现我们的第一个Graph神经网络了!我们在这里将使用最简单的GNN网络之一,即GCN层**([Kipf等人(2017)](https://arxiv.org/abs/1609.02907))用于Graph节点分类。

PyG通过[GCNConv](https://pytorch-geometric.readthedocs.io/en/latest/modules/nn.html#torch_geometric.nn.conv.GCNConv)来实现此层,可以通过传入 节点要素表示形式“ x”和COO图形连接性表示形式“ edge_index”。

这样,我们就可以通过在torch.nn.Module类中定义我们的网络架构来创建我们的第一个图形神经网络:

import torch
from torch.nn import Linear
from torch_geometric.nn import GCNConv


class GCN(torch.nn.Module):
    def __init__(self):
        super(GCN, self).__init__()
        torch.manual_seed(12345)
        self.conv1 = GCNConv(dataset.num_features, 4)
        self.conv2 = GCNConv(4, 4)
        self.conv3 = GCNConv(4, 2)
        self.classifier = Linear(2, dataset.num_classes)

    def forward(self, x, edge_index):
        h = self.conv1(x, edge_index)
        h = h.tanh()
        h = self.conv2(h, edge_index)
        h = h.tanh()
        h = self.conv3(h, edge_index)
        h = h.tanh()  # Final GNN embedding space.
        
        # Apply a final (linear) classifier.
        out = self.classifier(h)

        return out, h

model = GCN()
print(model)

网络结构输出如下:

GCN(
  (conv1): GCNConv(34, 4)
  (conv2): GCNConv(4, 4)
  (conv3): GCNConv(4, 2)
  (classifier): Linear(in_features=2, out_features=4, bias=True)
)

在这里,我们首先在__init__中初始化所有构建块,并在“转发”中定义网络的计算流程。 我们首先定义并堆叠三层图卷积层,这对应于在每个节点周围(距离3个“跳”为止的所有节点)汇总3跳邻域信息。 另外,GCNConv层将节点特征维数减小为

, i.e.,

.。每个[GCNConv]层都通过[tanh](https://pytorch.org/docs/stable/generation/torch.nn.Tanh.html?highlight=tanh#torch.nn.Tanh)非线性进行了增强。

之后,我们应用单个线性变换([torch.nn.Linear](https://pytorch.org/docs/stable/generated/torch.nn.Linear.html?highlight=linear#torch.nn。线性)),用作将我们的节点映射到4个类/社区中的1个的分类器。

我们返回最终分类器的输出以及GNN生成的最终节点嵌入。 我们继续通过GCN()初始化最终模型,并打印我们的模型以产生所有使用过的子模块的概括。

获取隐藏层的表示:

model = GCN()

_, h = model(data.x, data.edge_index)
print(f'Embedding shape: {list(h.shape)}')

visualize(h, color=data.y)

输出:

Embedding shape: [34, 2]

image

在这里值得注意的是,即使在训练我们的模型权重之前,这个初始化的GCN网络也会产生节点的嵌入,并且这些嵌入与图的社区结构非常相似。尽管我们的模型的权重是“完全随机地初始化”的,并且到目前为止,我们还没有进行任何训练,但是相同颜色(社区)的节点已经在嵌入空间中紧密地聚集在一起。得出这样的结论,即GNN引入了强烈的节点偏差,从而导致在输入图中彼此靠近的节点具有相似的嵌入

但是,节点表示并不是很完美,我们可以看出来四种类别的节点还是混在一块了(对应途中是四种颜色),我们可以做得更好吗? 让我们看一个示例,该示例如何基于对图中4四种节点的社区分配(每个社区一个)的知识来训练我们的网络参数:

由于模型中的所有内容都是可区分的和参数化的,因此我们可以添加一些标签,训练模型并观察嵌入如何反应。 在这里,我们使用一种半监督学习程序:我们仅针对每个类训练一个节点,但是允许使用完整的输入图数据。

这个怎么理解呢,我们其实可以输出data.ydata.train_mask就明白了:

data.y
tensor([0, 0, 0, 0, 1, 1, 1, 0, 2, 2, 1, 0, 0, 0, 2, 2, 1, 0, 2, 0, 2, 0, 2, 2,
        3, 3, 2, 2, 3, 2, 2, 3, 2, 2])
data.train_mask
tensor([ True, False, False, False,  True, False, False, False,  True, False,
        False, False, False, False, False, False, False, False, False, False,
        False, False, False, False,  True, False, False, False, False, False,
        False, False, False, False])

大家可以看到相当于我们训练网络的时候只针对每一个类别下的token做优化,这样可以加速网络的训练和收敛。

训练我们的模型与任何其他PyTorch模型非常相似。 除了定义我们的网络架构之外,我们还定义了损失函数在这里[[CrossEntropyLoss]](https://pytorch.org/docs/stable/generate/torch.nn.CrossEntropyLoss.html)) 并初始化随机梯度优化器(此处为[Adam](https://pytorch.org/docs/stable/optim.html?highlight=adam#torch.optim.Adam))。 之后,我们执行多轮优化,其中每一轮都包含一个正向和反向传递,以计算模型参数w.r.t的梯度。从前向通行证产生的损失。 如果您对PyTorch并不陌生,则该方案应该对您来说很熟悉。 否则,PyTorch文档会提供[有关如何在PyTorch中训练神经网络的很好的介绍](https://pytorch.org/tutorials/beginner/blitz/cifar10_tutorial.html#define-a-loss-function-and-optimizer )。

请注意,我们的半监督学习场景是通过以下行实现的:

loss = criterion(out[data.train_mask], data.y[data.train_mask])

在计算所有节点的节点嵌入时,我们“仅利用训练节点来计算loss” **。 在这里,这是通过过滤分类器“ out”和真实性标签“ data.y”的输出以仅包含“ train_mask”中的节点来实现的。

现在让我们开始训练,看看我们的节点嵌入随时间如何演变(最好是显式地运行代码,打印出模型的训练效果):

import time
from IPython.display import Javascript  #画图.
display(Javascript('''google.colab.output.setIframeHeight(0, true, {maxHeight: 430})'''))

model = GCN()
criterion = torch.nn.CrossEntropyLoss()  # 定义loss
optimizer = torch.optim.Adam(model.parameters(), lr=0.01)  # 优化器

def train(data):
    optimizer.zero_grad()  # 梯度清零.
    out, h = model(data.x, data.edge_index)  # GCN模型.
    loss = criterion(out[data.train_mask], data.y[data.train_mask])  # 计算真实loss.
    loss.backward()  # 反向求导.
    optimizer.step()  # 参数更新.
    return loss, h

for epoch in range(401):
    loss, h = train(data)
    # 每10个epochs打印Graph
    if epoch % 10 == 0:
        visualize(h, color=data.y, epoch=epoch, loss=loss)
        time.sleep(0.3)

image

image

过了一段时间之后,我们可以看到GCN强大的效果:

image

image

可以看到,我们的3层GCN模型可以有效地社区发现并正确地对大多数节点进行分类。

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 图神经网络(02)-基于Graph的传统机器学习理论

    致Great
  • 图神经网络01-基于Graph的机器学习简介

    从上面一些例子我们可以看出,Graph的概念存在于这个世界的每个地方,我们每个人都或多或少地在Graph扮演某个角色或者正在利用Graph带来的便利,目前随着图...

    致Great
  • AAAI 2020 论文抢先看!图学习GNN火爆,谷歌、港科大、北邮最新力作

    今年的双十一,AAAI 2020 公布了接受的论文。这届 AAAI 可谓是火爆异常,一共收到了 8800 篇提交的论文,最终有效投稿为 7737 篇,接受的论文...

    新智元
  • 首篇NLP图神经网络综述来了! 127页文档让你全面了解这个领域

    近些年来,深度学习已经成为处理NLP各种任务的主要方法。由于用图(graph)来表征文本可以更好的获取文本的结构信息,且随着火热的图神经网络的兴起,各种各样的N...

    AI科技评论
  • 看其他GNN介绍我想转行,看完这篇我又可以了

    随着在线信息的爆炸式增长,推荐系统在缓解此类信息过载方面起着关键作用,同时由于推荐系统具有重要的应用价值,这方面的研究一直很热门。图神经网络GNN(Gr...

    炼丹笔记
  • 图与图学习(下)

    在中篇中,我们了解了图机器学习(GML:Graph Machine Learning)。下面,终于到了这个前置教程的重头戏,图神经网络(Graph Neural...

    致Great
  • Angel 3.1:高性能图计算的三体艺术

    | 导语 Angel是腾讯首个AI开源项目,2019年在基金会的孵化过程中,完成了3.0版本的发布,并于同年在基金会顺利毕业。作为面向机器学习的第三代高性能...

    腾讯大数据
  • GNN 相关资料记录;GCN 与 graph embedding 相关调研;社区发现算法相关;异构信息网络相关;

    最近做了一些和gnn相关的工作,经常听到GCN 和 embedding 相关技术,感觉很是困惑,所以写下此博客,对相关知识进行索引和记录:

    xuyaowen
  • 机器学习-基于Sklearn的神经网络实现

    简介:神经网络模型:Multi-layer Perceptron (MLP) :

    FindKey

扫码关注云+社区

领取腾讯云代金券