图神经网络 (Graph Neural Networks) 是一种针对图构造数据 (如社交图、网络安全网络或分子示意) 设计的机器学习算法。它在过来几年里倒退迅速,被用于许多不同的应用程序。在这篇文章中咱们将回顾 GNN 的基础知识,而后应用 Pytorch Geometric 解决一些常见的次要问题,并探讨一些算法和代码的细节。
常见的图神经网络应用
GNN 能够用来解决各种与图相干的机器学习问题:
- 节点的分类:预测节点的类别或标签。例如,在网络安全中检测网络中的欺诈实体可能是一个节点分类问题。
- 链接预测:预测节点之间是否存在潜在的链接(边)。例如,社交网络服务依据网络数据倡议可能的敌人分割。
- 图分类:将图形自身划分为不同的类别。比方通过观察一个化合物的图构造来确定它是有毒的还是无毒的。
- 社区检测:将节点划分为集群。比方在社交图中寻找不同的社区。
- 异样检测:以无监督的形式在图中查找离群节点。如果没有标签,能够应用这种办法。
在这篇文章中,咱们将回顾节点分类、链接预测和异样检测的相干常识和用 Pytorch Geometric 代码实现这三个算法。
图卷积
图神经网络在过来的几年里倒退迅速,并且有许多的变体。在这些 GNN 变体中图卷积网络可能是最风行和最根本的算法。在本节中咱们将对其进行回顾和介绍。
图卷积是一种基于图构造提取 / 汇总节点信息的无效办法。它是卷积神经网络卷积运算的一个变体,卷积神经网络通常用于解决图像问题。
在图像中,像素在网格中按构造排序,卷积操作中的过滤器或卷积核 (权重矩阵) 以预先确定的步幅在图像上滑动。像素的邻域由过滤器大小决定(下图中过滤器大小为 3 x 3,蓝色过滤器中的 8 个灰色像素为邻域),过滤器中的加权像素值被聚合为单个值。卷积运算的输入比输出图像的尺寸小,但对输出图像有更高层次的视图,这对预测图像问题很有用,比方图像分类。
在图中,节点以非结构化的形式排序,节点之间的邻域大小不同。图卷积取给定节点 (下图中的红色节点) 及其街坊 (蓝圈内的灰色节点) 的节点特色的平均值,计算更新后的节点示意值。通过这种卷积操作,节点示意捕捉部分的图信息。
下图显示了更多对于图卷积操作的细节。街坊节点 (蓝色) 的节点特色和指标节点 (红色) 的节点特色被均匀。而后与权重向量 (W) 相乘,其输入更新指标节点的节点特色(更新后的节点值也称为节点嵌入)。
对于那些相干的节点,节点特色应用度矩阵的逆进行归一化,而后再聚合而不是简略的均匀(原始论文公式 8 中提出)
这个卷积操作中须要留神的一点是,图卷积的数量决定了节点特色被聚合到每个节点的步数。在下图中,第一个卷积将蓝色节点的特色聚合到橙色节点中,第二个卷积将绿色节点的特色合并到橙色节点中。
能够看到卷积的数量决定了聚合的节点特色有多远
在接下来的几节中,咱们实现 GCN。然而在深入研究它们之前,先相熟一下将要应用的数据集。
Cora – 基准数据集
Cora 数据集是一个论文援用网络数据,蕴含 2708 篇科学论文。图中的每个节点代表一篇论文,如果一篇论文援用另一篇论文,则有节点间有一条边相连。
咱们应用 PyG (Pytorch Geometric)来实现 GCN, GCN 是 GNN 的风行库之一。Cora 数据集也能够应用 PyG 模块加载:
from torch_geometric.datasets import Planetoid
dataset = Planetoid(root='/tmp/Cora', name='Cora')
graph = dataset[0]
Cora 数据集来源于 Pytorch Geometric 的“Automating the Construction of Internet Portals with Machine Learning”论文。
节点特色和边缘信息如下所示。节点特色是 1433 个词向量,示意每个出版物中的词不存在 (0) 或存在 (1)。边在邻接列表中示意。
每个节点都是七个类别中的一个,这将就是分类的指标标签
利用 NetworkX 库能够实现图数据的可视化。节点色彩代表不同的类。
import random
from torch_geometric.utils import to_networkx
import networkx as nx
def convert_to_networkx(graph, n_sample=None):
g = to_networkx(graph, node_attrs=["x"])
y = graph.y.numpy()
if n_sample is not None:
sampled_nodes = random.sample(g.nodes, n_sample)
g = g.subgraph(sampled_nodes)
y = y[sampled_nodes]
return g, y
def plot_graph(g, y):
plt.figure(figsize=(9, 7))
nx.draw_spring(g, node_size=30, arrows=False, node_color=y)
plt.show()
g, y = convert_to_networkx(graph, n_sample=1000)
plot_graph(g, y)
节点分类
对于节点分类问题,能够应用 PyG 中的 RandomNodeSplit 模块将节点分为 train、valid 和 test(我替换数据中的原始宰割掩码,因为它的训练集太小了)。
import torch_geometric.transforms as T
split = T.RandomNodeSplit(num_val=0.1, num_test=0.2)
graph = split(graph)
数据宰割标记会被写入到图对象的掩码属性中(参见下图),而不是图自身。这些掩码用于训练损失计算和模型评估,而图卷积应用整个图数据。
节点分类基线模型(MLP)
在构建 GCN 之前,只应用节点特色来训练 MLP(多层感知器,即前馈神经网络)来创立一个基线性能。该模型疏忽节点连贯(或图构造),并试图仅应用词向量对节点标签进行分类。模型类如下所示。它有两个暗藏层(Linear),带有 ReLU 激活,前面是一个输入层。
import torch.nn as nn
class MLP(nn.Module):
def __init__(self):
super().__init__()
self.layers = nn.Sequential(nn.Linear(dataset.num_node_features, 64),
nn.ReLU(),
nn.Linear(64, 32),
nn.ReLU(),
nn.Linear(32, dataset.num_classes)
)
def forward(self, data):
x = data.x # only using node features (x)
output = self.layers(x)
return output
咱们用一个一般的 Pytorch 训练 / 验证流程来定义训练和评估函数。
def train_node_classifier(model, graph, optimizer, criterion, n_epochs=200):
for epoch in range(1, n_epochs + 1):
model.train()
optimizer.zero_grad()
out = model(graph)
loss = criterion(out[graph.train_mask], graph.y[graph.train_mask])
loss.backward()
optimizer.step()
pred = out.argmax(dim=1)
acc = eval_node_classifier(model, graph, graph.val_mask)
if epoch % 10 == 0:
print(f'Epoch: {epoch:03d}, Train Loss: {loss:.3f}, Val Acc: {acc:.3f}')
return model
def eval_node_classifier(model, graph, mask):
model.eval()
pred = model(graph).argmax(dim=1)
correct = (pred[mask] == graph.y[mask]).sum()
acc = int(correct) / int(mask.sum())
return acc
mlp = MLP().to(device)
optimizer_mlp = torch.optim.Adam(mlp.parameters(), lr=0.01, weight_decay=5e-4)
criterion = nn.CrossEntropyLoss()
mlp = train_node_classifier(mlp, graph, optimizer_mlp, criterion, n_epochs=150)
test_acc = eval_node_classifier(mlp, graph, graph.test_mask)
print(f'Test Acc: {test_acc:.3f}')
该模型的测试精度为 73.2%。
GCN 进行节点分类
接下来,咱们将对 GCN 进行训练并将其性能与 MLP 进行比拟。这里应用的是一个非常简单的模型,有两个图卷积层和它们之间的 ReLU 激活。此设置与论文原文雷同(公式 9)。
from torch_geometric.nn import GCNConv
import torch.nn.functional as F
class GCN(torch.nn.Module):
def __init__(self):
super().__init__()
self.conv1 = GCNConv(dataset.num_node_features, 16)
self.conv2 = GCNConv(16, dataset.num_classes)
def forward(self, data):
x, edge_index = data.x, data.edge_index
x = self.conv1(x, edge_index)
x = F.relu(x)
output = self.conv2(x, edge_index)
return output
gcn = GCN().to(device)
optimizer_gcn = torch.optim.Adam(gcn.parameters(), lr=0.01, weight_decay=5e-4)
criterion = nn.CrossEntropyLoss()
gcn = train_node_classifier(gcn, graph, optimizer_gcn, criterion)
test_acc = eval_node_classifier(gcn, graph, graph.test_mask)
print(f'Test Acc: {test_acc:.3f}')
该模型的测试集准确度为 88.0%。从 MLP 中取得了大概 15% 的精度进步。
链接预测
链接预测比节点分类更简单,因为咱们须要应用节点嵌入对边缘进行预测。预测步骤大抵如下:
- 编码器通过解决具备两个卷积层的图来创立节点嵌入。
- 在原始图上随机增加负链接。这使得模型工作变为对原始边的正链接和新增边的负链接进行二元分类。
- 解码器应用节点嵌入对所有边 (包含负链接) 进行链接预测(二元分类)。它从每条边上的一对节点计算节点嵌入的点积。而后聚合整个嵌入维度的值,并在每条边上创立一个示意边存在概率的值。
该模型构造来源于变分图主动编码器中原始的链接预测实现。代码改编自 PyG repo 中的代码示例,并基于 Graph Auto-Encoders 实现
from sklearn.metrics import roc_auc_score
from torch_geometric.utils import negative_sampling
class Net(torch.nn.Module):
def __init__(self, in_channels, hidden_channels, out_channels):
super().__init__()
self.conv1 = GCNConv(in_channels, hidden_channels)
self.conv2 = GCNConv(hidden_channels, out_channels)
def encode(self, x, edge_index):
x = self.conv1(x, edge_index).relu()
return self.conv2(x, edge_index)
def decode(self, z, edge_label_index):
return (z[edge_label_index[0]] * z[edge_label_index[1]]).sum(dim=-1) # product of a pair of nodes on each edge
def decode_all(self, z):
prob_adj = z @ z.t()
return (prob_adj > 0).nonzero(as_tuple=False).t()
def train_link_predictor(model, train_data, val_data, optimizer, criterion, n_epochs=100):
for epoch in range(1, n_epochs + 1):
model.train()
optimizer.zero_grad()
z = model.encode(train_data.x, train_data.edge_index)
# sampling training negatives for every training epoch
neg_edge_index = negative_sampling(
edge_index=train_data.edge_index, num_nodes=train_data.num_nodes,
num_neg_samples=train_data.edge_label_index.size(1), method='sparse')
edge_label_index = torch.cat([train_data.edge_label_index, neg_edge_index],
dim=-1,
)
edge_label = torch.cat([
train_data.edge_label,
train_data.edge_label.new_zeros(neg_edge_index.size(1))
], dim=0)
out = model.decode(z, edge_label_index).view(-1)
loss = criterion(out, edge_label)
loss.backward()
optimizer.step()
val_auc = eval_link_predictor(model, val_data)
if epoch % 10 == 0:
print(f"Epoch: {epoch:03d}, Train Loss: {loss:.3f}, Val AUC: {val_auc:.3f}")
return model
@torch.no_grad()
def eval_link_predictor(model, data):
model.eval()
z = model.encode(data.x, data.edge_index)
out = model.decode(z, data.edge_label_index).view(-1).sigmoid()
return roc_auc_score(data.edge_label.cpu().numpy(), out.cpu().numpy())
对于这个链接预测工作,咱们心愿将链接 / 边随机宰割为训练数据、无效数据和测试数据。咱们能够应用 PyG 的 RandomLinkSplit 模块来做到这一点。
import torch_geometric.transforms as T
split = T.RandomLinkSplit(
num_val=0.05,
num_test=0.1,
is_undirected=True,
add_negative_train_samples=False,
neg_sampling_ratio=1.0,
)
train_data, val_data, test_data = split(graph)
输入数据如下所示。
这个输入数据有以下 3 点须要留神:
1、在 edge_index 上执行宰割,这样训练和验证宰割不包含来自验证和测试宰割的边(即只有来自训练宰割的边),而测试宰割不包含来自测试宰割的边。这是因为编码器应用 edge_index 和 x 来创立节点嵌入,这种形式确保了在对验证 / 测试数据进行预测时,节点嵌入上没有指标透露。
2、向每个宰割数据增加两个新属性(edge_label 和 edge_label_index)。它们是与每次宰割绝对应的边标签和边索引。Edge_label_index 将用于解码器进行预测,edge_label 将用于模型评估。
3、向 val_data 和 test_data 增加与正链接雷同数量的负链接 (neg_sampling_ratio=1.0)。它们被增加到 edge_label 和 edge_label_index 属性中,但没有增加到 edge_index 中,因为咱们不心愿在编码器(或节点嵌入创立) 上应用负链接。咱们没有向这里的训练集增加负链接(设置 add_negative_train_samples=False),因为会在下面的 train_link_predictor 的训练循环中增加它们。训练过程中的这种随机化应该会使模型更强壮。
下图总结了如何对编码器和解码器执行边缘宰割(每个阶段应用黑白边缘)。
咱们当初能够用上面的代码来训练和评估模型。
model = Net(dataset.num_features, 128, 64).to(device)
optimizer = torch.optim.Adam(params=model.parameters(), lr=0.01)
criterion = torch.nn.BCEWithLogitsLoss()
model = train_link_predictor(model, train_data, val_data, optimizer, criterion)
test_auc = eval_link_predictor(model, test_data)
print(f"Test: {test_auc:.3f}")
该模型的测试 AUC 为 92.5%。
异样检测
再次应用 Cora 数据集进行异样检测工作,但它与后面的数据集略有不同: 咱们须要合成注入异样值。数据集有两种不同类型的异样值:
- 构造异样
- 密集连贯的节点,而不是稠密连贯的规定节点
- 上下文的异样值
- 属性与相邻节点显著不同的节点
对于这个异样检测工作,须要应用的是 PyGOD 库,它是建设在 PyG 之上的一个图异样值检测库。能够通过 PyGOD 模块加载曾经进行了异样值注入的 Cora 数据集。
from pygod.utils import load_data
graph = load_data('inj_cora')
上面的代码显示了异样值类型散布。
Counter(graph.y.tolist())
#Counter({0: 2570, 1: 68, 2: 68, 3: 2})
0: 失常,1: 仅上下文异样,2: 构造异样,3: 上下文和构造都异样
如果你对这些异样值是如何注入的感兴趣,能够查看对于异样值生成器模块的 PyGOD 文档,该文档解释了操作细节。这里咱们须要留神的是标签 y 将只用于模型评估,而不是用于训练标签,因为咱们正在训练一个无监督的模型。
为了检测这些异样点,咱们训练了 DOMINANT(Deep Anomaly Detection on Attributed Networks)模型。它是一个具备图卷积层的自编码器网络,其重构误差将是节点异样评分。该模型遵循以下步骤进行预测。
- 属性网络编码器应用三个图卷积层来解决输出图,从而创立节点嵌入。
- 构造重构解码器利用学习到的节点嵌入重构原始图边(即邻接矩阵)。它从每个可能的节点对计算节点嵌入的点积,在每个节点对上创立一个示意边缘存在的概率评分。
- 属性重构解码器应用取得的节点嵌入重构原始节点属性。它有一个图卷积层来预测属性值。
- 最初一步将上述两种解码器的重构误差在每个节点上进行加权均匀合并,合并后的误差即为最终的误差 / 损失。这些最终的误差也是节点的异样评分。
from pygod.models import DOMINANT
from sklearn.metrics import roc_auc_score, average_precision_score
def train_anomaly_detector(model, graph):
return model.fit(graph)
def eval_anomaly_detector(model, graph):
outlier_scores = model.decision_function(graph)
auc = roc_auc_score(graph.y.numpy(), outlier_scores)
ap = average_precision_score(graph.y.numpy(), outlier_scores)
print(f'AUC Score: {auc:.3f}')
print(f'AP Score: {ap:.3f}')
graph.y = graph.y.bool()
model = DOMINANT()
model = train_anomaly_detector(model, graph)
eval_anomaly_detector(model, graph)
模型的 AUC 为 84.1%,均匀精度为 20.8%。这种差别很可能是因为指标不均衡造成的。因为这是一个无监督的模型,咱们不可能冀望失去一个十分准确的模型,但能够在原始论文中看到,它依然优于任何其余风行的异样检测算法。
援用
本文的源代码能够在 colab 找到:
https://avoid.overfit.cn/post/31790c77e3984dce8667516f726cd4ed
援用如下:
- Benjamin Sanchez-Lengeling et al., A Gentle Introduction to Graph Neural Networks
- Ameya Daigavane et al., Understanding Convolutions on Graphs
- Francesco Casalegno, Graph Convolutional Networks — Deep Learning on Graphs
- Thomas N. Kipf, Max Welling, Semi-Supervised Classification with Graph Convolutional Networks (2017), ICLR 2017
- Thomas N. Kipf, Max Welling, Variational Graph Auto-Encoders (2016)
- Kaize Ding et al., Deep Anomaly Detection on Attributed Networks (2019)
- Kay Liu et al., Benchmarking Node Outlier Detection on Graphs (2022)
作者:Tomonori Masui