Variational Graph Autoencoder（VGAE）和Subgraphs, Embeddings, and Attributes for Link prediction（SEAL)

链接预测是使用图执行的最流行的任务之一。它被定义为预测两个节点之间是否存在链路的问题。这种能力是社交网络和推荐系统的核心。一个很好的例子是社交媒体网络如何展示你与他人共同拥有的朋友和追随者。直觉上，如果这个数字高，你就更有可能与这些人建立联系。这种可能性正是链接预测试图估计的。
在本文中，我们将探索两种方法。第一种方法，是基于节点嵌入，并执行矩阵分解的方法。第二种方法，侧重于子图表示。每个链路的邻接节点作为预测链路概率的输入。

---

前言

在静态网络中，链接预测任务用于预测图中缺失的链接。启发式技术被提出解决链接预测问题。首先，本文将基于本地和全局的邻接节点描述该启发式算法，之后，我们将介绍矩阵分解和DeepWalk以及Node2Vec之间的关系。

---

提示：以下是本篇文章正文内容，下面案例可供参考

一、启发式技术

启发式技术是预测节点间链接的一种简单实用的方法。它们很容易实现，并为这项任务提供了强有力的基线。我们可以根据它们执行的跳数对它们进行分类（参见图1）。其中一些只需要与目标节点相邻的1跳邻居。更复杂的技术还会考虑2跳邻居或整个图。在本节中，我们将它们分为两类—本地（1跳和2跳）和全局启发式。

图1 多跳邻接节点图 本地启发式通过考虑节点的本地邻接节点数目来计算节点之间的相似度。我们用N(u)来表示节点u的邻接节点。下面有三种方法来表示本地启发式：

• 共有邻居：通过统计两个节点共有的邻接节点数目（1-hop neighbors）。
  $$f\left(u,v\right)=\left|N\left(u\right)\cap N\left(v\right)\right|$$
• Jaccard系数：它沿用了共有邻居的思路，但是对结果进行了归一化。该方法给邻接节点较少的节点以更高的权重。
  $$f\left(u,v\right)=\frac{\left|N\left(u\right)\cap N\left(v\right)\right|}{\left|N\left(u\right)\cup N\left(v\right)\right|}$$
• Adamic-Adar指数：它将两个节点所共有的邻接节点进行逆对数变换后求和（2-hop neighbors）。该方法表示大社区的共有邻居没有小社区的邻居重要。
  $$f\left(u,v\right)=\sum _{x\in N\left(u\right)\cap N{\left(v\right)}_i}\frac{1}{\log \left|N\left(x\right)\right|}$$

全局启发式技术提供了基于全局网络解决问题的方法。

• Katz指数：计算了两个节点之间所有可能路径的权重之和。为了惩罚较长路径，其相应的权重系数会减小。该方法会使得用于更多较短相连路径的节点脱颖而出。在下式中：$A$代表了邻接矩阵，$\beta$代表了权重。
  $$f\left(u,v\right)=\sum _{i=i}^{\infty }{\beta }^i{A}^i$$
• 循环的随机行走：从目标节点开始随机行走，同时统计当前节点的访问次数。不断循环该过程直到达到自定义的行走次数。

全局启发式往往更加准确，但是它需要知道全局的节点分布情况。

二、矩阵分解

矩阵分解受链接问题的启发，通过矩阵分解方法，我们使用嵌入向量直接预测全局的邻接矩阵。在该方法下，相似的节点其嵌入向量也具有相似性。邻接节点的估计如下：
$$A_{uv}\approx z_v^T{z}_u$$
该方法的目标是通过学习节点嵌入使得预测与真实值之间的L2正则化最小。
$$\underset{z}{\mathrm{minimize}}\sum _{i\in V,j\in V}{\left(A_{uv}?z_v^T{z}_u\right)}^2$$

三、VGAE

在了解VGAE之前，我们首先了解其本体GAE。
GAE包含两个模块：

• 编码器（encoder）：在GAE中，编码器由两层GCN组成，用于计算嵌入向量。
  $$Z=GCN\left(X,A\right)$$
• 解码器（decoder）：解码器使用矩阵分解以及激活函数估计邻接矩阵。
  $$\hat{A}=\sigma \left(Z^{T}Z\right)$$

注意，我们并非去预测节点或者图的类别，而是去预测邻接矩阵中各个元素的概率。所以，我们需要用二进制交叉熵损失来评估预测的优劣：
$${\mathcal{L}}_{BCE}=\sum _{i\in V,j\in V}?A_{ij}\log \left({\hat{A}}_{ij}\right)?\left(1?A_{ij}\right)\log \left(1?{\hat{A}}_{ij}\right)$$
然而，邻接矩阵往往是稀疏的，这将会使得预测量向0偏移。为此，我们可以给上式的第一部分$A_{ij}=1$更高的权重，或者我们可以减少在训练过程中零值的采样，使得标签更加的平均。

VGAE和GAE的区别同自编码器和变体自编码器类似。VGAE不是直接学习嵌入，而是通过学习正态部分，并在正态分布中产生嵌入向量。它也有两个模块构成：

• 其编码器由三层GCN组成，后两层GCN共同分享第一层GCN得到的嵌入向量，进而产生正态部分中均值和方差的参数。
• 其解码器从学习到的正态分布中采样，并组成邻接矩阵。

在VGAE中，我们需要确保编码器的输出符合正态部分。为此，在损失函数的选择上我们需要考虑KL散度，该散度用于衡量两种分布的差异。我们将新的损失函数命名为$evidencelowerbound$（ELBO）。
$${\mathcal{L}}_{ELBO}={\mathcal{L}}_{BCE}?\mathrm{KL}[q(Z\mid X,A)\Vert p(Z)]$$
在上式中，$q(Z\mid X,A)$代表了编码器，$p(Z)$代表了先验概率。

四、应用VGAE

在GNN链接预测中，我们一般将链接预测转换为一个二分类问题：图中存在的边我们称之为正样本，不存在的边我们称之为负样本。在训练集、验证集和测试集中，正负样本的采样数量相同。另外，训练集中的边不能和测试集、验证集中的边存在较差。接下来，我们将以Cora数据集为例，实现VGAE。

1、导入数据库

import numpy as np
import torch
import matplotlib.pyplot as plt
import torch_geometric.transforms as T

from torch_geometric.datasets import Planetoid
from torch_geometric.nn import GCNConv, VGAE
from collections import Counter

torch.manual_seed(42)
torch.cuda.manual_seed(42)
torch.cuda.manual_seed_all(42)
torch.backends.cudnn.deterministic = True
torch.backends.cudnn.benchmark = False

2、数据预处理

device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')

transform = T.Compose([
    T.NormalizeFeatures(),
    T.ToDevice(device),
    T.RandomLinkSplit(num_val=0.05,         # val percentage
                      num_test=0.1,         # test percentage
                      is_undirected=True,   # undirected
                      split_labels=True,    # split positive and negative labels
                      add_negative_train_samples=False), # without pos and neg
                        ])

dataset = Planetoid('.', name='Cora', transform=transform)

train_data, val_data, test_data = dataset[0]

在上述内容中，我们利用了组合体$Compose$将需要用到的预处理函数整合。着重介绍一下$RandomLinkSplit$函数，该函数用于确定验证集和测试集占比以及是否为链路预测增加负样本。在该处我们选择否，因为训练集中已经有负样本。

三个数据集的输出结果如下。

Data(x=[2708, 1433], edge_index=[2, 8976], y=[2708], train_mask=[2708], val_mask=[2708], test_mask=[2708], 
pos_edge_label=[4488], pos_edge_label_index=[2, 4488])
Data(x=[2708, 1433], edge_index=[2, 8976], y=[2708], train_mask=[2708], val_mask=[2708], test_mask=[2708], 
pos_edge_label=[263], pos_edge_label_index=[2, 263], neg_edge_label=[263], neg_edge_label_index=[2, 263])
Data(x=[2708, 1433], edge_index=[2, 9502], y=[2708], train_mask=[2708], val_mask=[2708], test_mask=[2708], 
pos_edge_label=[527], pos_edge_label_index=[2, 527], neg_edge_label=[527], neg_edge_label_index=[2, 527])

通过观察上述输出结果，我们可以发现训练集、验证集和测试集中正样本的数量之和为总样本数10556的一半，另外一半为负样本。
在包含负样本边的$neg\_edge\_label\_index$中，每一条边都不属于原数据集中的任意一边，而在正样本边的$pos\_edge\_label\_index$，都是从原数据集边中采样而来。

3、编码器类

class Encoder(torch.nn.Module):
    def __init__(self, dim_in, dim_out):
        super().__init__()
        self.conv1 = GCNConv(dim_in, 2 * dim_out)
        self.conv_mu = GCNConv(2 * dim_out, dim_out)
        self.conv_logstd = GCNConv(2 * dim_out, dim_out)

    def forward(self, x, edge_index):
        x = self.conv1(x, edge_index).relu()
        # mu and logstd are parallel
        return self.conv_mu(x, edge_index), self.conv_logstd(x, edge_index)

model = VGAE(Encoder(dataset.num_features, 16)).to(device)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01)

def train():
    model.train()
    optimizer.zero_grad()
    z = model.encode(train_data.x, train_data.edge_index)
    loss = model.recon_loss(z, train_data.pos_edge_label_index) + (1 / train_data.num_nodes) * model.kl_loss()
    loss.backward()
    optimizer.step()
    return float(loss)

@torch.no_grad()
def test(data):
    model.eval()
    z = model.encode(data.x, data.edge_index)
    return model.test(z, data.pos_edge_label_index, data.neg_edge_label_index)

在上述$Encoder$类中，首先定义了$conv1$层，用于解析邻接矩阵，并求出对应维数的嵌入向量。$conv\_mu$和$conv\_logstd$共用第一层GCN，并生成均值和方差分布。

在模型训练函数$model.encode$中，首先经过$Encoder$类中的$forward$函数中生成分布向量，之后将$conv\_mu$和$conv\_logstd$相结合生成相应分布的嵌入向量。该嵌入向量的大小为（节点数目，$dim\_out$）。

之后在$model.recon\_loss$中，计算二进制交叉熵损失。在$model.kl\_loss()$函数中计算KL散度。

4、训练模型

val_aucs = []
val_aps = []

for epoch in range(301):
    loss = train()
    val_auc, val_ap = test(test_data)

    val_aucs.append(val_auc)
    val_aps.append(val_ap)

    if epoch % 50 == 0:
        print(f'Epoch {epoch:>2} | Loss: {loss:.4f} | Val AUC: {val_auc:.4f} | Val AP: {val_ap:.4f}')

test_auc, test_ap = test(test_data)
print(f'Test AUC: {test_auc:.4f} | Test AP {test_ap:.4f}')

# approximated adjacency matrix
# Graph Autoencoders
z = model.encode(test_data.x, test_data.edge_index)
Ahat = torch.sigmoid(z @ z.T)

得到训练结果如下。

Epoch  0 | Loss: 3.4287 | Val AUC: 0.6249 | Val AP: 0.6462
Epoch 50 | Loss: 1.3187 | Val AUC: 0.6155 | Val AP: 0.6439
Epoch 100 | Loss: 1.1214 | Val AUC: 0.7244 | Val AP: 0.7237
Epoch 150 | Loss: 1.0109 | Val AUC: 0.8101 | Val AP: 0.8073
Epoch 200 | Loss: 0.9973 | Val AUC: 0.8349 | Val AP: 0.8340
Epoch 250 | Loss: 0.9176 | Val AUC: 0.8724 | Val AP: 0.8719
Epoch 300 | Loss: 0.9202 | Val AUC: 0.8838 | Val AP: 0.8848
Test AUC: 0.8838 | Test AP 0.8848

Ahat:
tensor([[0.8776, 0.5316, 0.7546,  ..., 0.4816, 0.8691, 0.8491],
        [0.5316, 0.8972, 0.8204,  ..., 0.3673, 0.6740, 0.6628],
        [0.7546, 0.8204, 0.8655,  ..., 0.4450, 0.8585, 0.8423],
        ...,
        [0.4816, 0.3673, 0.4450,  ..., 0.6342, 0.4946, 0.4978],
        [0.8691, 0.6740, 0.8585,  ..., 0.4946, 0.9193, 0.9021],
        [0.8491, 0.6628, 0.8423,  ..., 0.4978, 0.9021, 0.8864]],
       device='cuda:0', grad_fn=<SigmoidBackward0>)

链接预测任务用于预测图中缺失的链接，通过上述预测的邻接节点矩阵，我们容易推断节点与节点之间可能存在的关系。

综上，训练VGAE是快速的，并且输出的结果是易于理解的。

四、SEAL

在VGAE，我们通过学习相关节点的嵌入来计算似然链接。在后文中，我们将介绍SEAL算法，通过查看目标节点周围的局部邻域，生成相应的子图。最后，将子图的嵌入和属性推广开来，作为输入引入到模型中。

SEAL是一个学习图结构特征以进行链接预测的框架。它将目标节点$\left(x,y\right)$以及其k-hop邻居节点看作一个封闭子图。每一个封闭子图都将被作为输入变量来预测链接。

整体架构由三个部分组成：

• 提取封闭子图：包含正负样本的训练数据。
• 构造节点信息矩阵：该矩阵包含三个部分–节点标签、嵌入向量和节点特征。
• GNN架构训练：将节点信息矩阵作为输入，输出似然链接。

整体流程图如图2所示。

图2 SELA架构图

在上图中，首先区分正负样本的数据集，之后选择相邻的核心节点提取对应的封闭子图，通过DRNL函数（见后文）求解邻接节点同中心节点之间的距离。将没有与中心节点间接连接的节点的距离设为0，中心节点同自身的距离设为1。最后，将距离向量转换为对应的独热编码，同原有的特征向量相连接组合成输入变量。

在实践中，目标节点$x$和$y$必须共享一个唯一的标签，以将它们标识为目标节点。对于上下文节点$i$和$j$，如果它们与目标节点的距离相同-- $d\left(i,x\right)=d\left(j,x\right),d\left(i,y\right)=d\left(j,y\right)$，则它们共享相同的标签。我们将该距离称为双半径（double radius），记为$\left(d\left(i,x\right),d\left(i,y\right)\right)$。

DRNL函数的定义如下：
$$f\left(i\right)=1+\min \left(d\left(i,x\right),d\left(i,y\right)\right)+\left(d/2\right)\left[\left(d/2\right)+\left(d\%2\right)?1\right]$$
其中，$d=d\left(i,x\right)+d\left(i,y\right)$，$min$中代表双半径。

最后，DGCNN架构（Deep Graph Convolutional Neural Network）利用封闭子图的信息和邻接矩阵做出预测。该架构分为三个部分：

• 同个GCN层计算节点嵌入（类似于GIN）。
• 全局排序池层在将这些嵌入输入到卷积层之前以一致的顺序对它们进行排序，卷积层不是排列不变的。
• 传统的卷积层和密集层应用于排序图表示并输出链接概率。

DGCNN架构用二进制交叉熵损失函数，输出的概率在（0，1）之间。

五、应用SEAL

SEAL框架需要大量的预处理来提取和标记封闭的子图。

1、导入数据库

import numpy as np
import torch.nn.functional as F
import torch

from sklearn.metrics import roc_auc_score, average_precision_score
from scipy.sparse.csgraph import shortest_path
from torch.nn import Conv1d, MaxPool1d, Linear, Dropout, BCEWithLogitsLoss
from torch_geometric.datasets import Planetoid
from torch_geometric.transforms import RandomLinkSplit
from torch_geometric.data import Data
from torch_geometric.loader import DataLoader
from torch_geometric.nn import GCNConv, aggr
from torch_geometric.utils import k_hop_subgraph, to_scipy_sparse_matrix

torch.manual_seed(42)
torch.cuda.manual_seed(42)
torch.cuda.manual_seed_all(42)
torch.backends.cudnn.deterministic = True
torch.backends.cudnn.benchmark = False

2、数据预处理

# Load Cora dataset
transform = RandomLinkSplit(num_val=0.05,
                            num_test=0.1,
                            is_undirected=True,
                            split_labels=True)

dataset = Planetoid('.', name='Cora', transform=transform)
# pos_edge_label means 1, neg means 0
train_data, val_data, test_data = dataset[0]

def seal_processing(dataset, edge_label_index, y):
    data_list = []

    for src, dst in edge_label_index.t().tolist():
        # relabel_nodes=True: 'edge_index' will be relabeled to hold consecutive indices
        # mapping means the center of new 'edge_index' which is 'sub_edge_index'
        # sub_nodes means the index of hops
        sub_nodes, sub_edge_index, mapping, _ = k_hop_subgraph([src, dst], 2, dataset.edge_index, relabel_nodes=True)
        src, dst = mapping.tolist()

        # Remove target link from the subgraph
        mask1 = (sub_edge_index[0] != src) | (sub_edge_index[1] != dst)
        mask2 = (sub_edge_index[0] != dst) | (sub_edge_index[1] != src)
        sub_edge_index = sub_edge_index[:, mask1 & mask2]

        # Double-radius node labeling (DRNL)
        # dst=max, src=min
        src, dst = (dst, src) if src > dst else (src, dst)
        # The inf value occurs because it is connected to only one other central node
        adj = to_scipy_sparse_matrix(sub_edge_index, num_nodes=sub_nodes.size(0)).tocsr()
        # list without src index
        idx = list(range(src)) + list(range(src + 1, adj.shape[0]))
        # adj was sparse matrix but still was matrix
        # adj_wo_src without src index
        adj_wo_src = adj[idx, :][:, idx]

        idx = list(range(dst)) + list(range(dst + 1, adj.shape[0]))
        adj_wo_dst = adj[idx, :][:, idx]

        # Calculate the distance between every node and the source target node
        d_src = shortest_path(adj_wo_dst, directed=False, unweighted=True, indices=src)
        d_src = np.insert(d_src, dst, 0, axis=0)
        d_src = torch.from_numpy(d_src)

        # Calculate the distance between every node and the destination target node
        d_dst = shortest_path(adj_wo_src, directed=False, unweighted=True, indices=dst-1)
        d_dst = np.insert(d_dst, src, 0, axis=0)
        d_dst = torch.from_numpy(d_dst)

        # Calculate the label z for each node
        dist = d_src + d_dst
        # DRNL function
        z = 1 + torch.min(d_src, d_dst) + dist // 2 * (dist // 2 + dist % 2 - 1)
        z[src], z[dst], z[torch.isnan(z)] = 1., 1., 0.
        z = z.to(torch.long)

        # Concatenate node features and one-hot encoded node labels (with a fixed number of classes)
        # Convert to a 200-dimensional eigenvector
        node_labels = F.one_hot(z, num_classes=200).to(torch.float)
        node_emb = dataset.x[sub_nodes]
        # combine features and encoded labels to build the node matrix
        node_x = torch.cat([node_emb, node_labels], dim=1)

        # Create data object with origin features
        data = Data(x=node_x, z=z, edge_index=sub_edge_index, y=y)
        data_list.append(data)

    return data_list

# Enclosing subgraphs extraction
train_pos_data_list = seal_processing(train_data, train_data.pos_edge_label_index, 1)
train_neg_data_list = seal_processing(train_data, train_data.neg_edge_label_index, 0)

val_pos_data_list = seal_processing(val_data, val_data.pos_edge_label_index, 1)
val_neg_data_list = seal_processing(val_data, val_data.neg_edge_label_index, 0)

test_pos_data_list = seal_processing(test_data, test_data.pos_edge_label_index, 1)
test_neg_data_list = seal_processing(test_data, test_data.neg_edge_label_index, 0)

# merge positive and negative data lists
train_dataset = train_pos_data_list + train_neg_data_list
val_dataset = val_pos_data_list + val_neg_data_list
test_dataset = test_pos_data_list + test_neg_data_list

train_loader = DataLoader(train_dataset, batch_size=32, shuffle=True)
val_loader = DataLoader(val_dataset, batch_size=32)
test_loader = DataLoader(test_dataset, batch_size=32)

针对上述预处理过程，我们逐一分析。首先是$RandomLinkSplit$函数，用于分割数据集，同前一个应用不同，本次分割时$add\_negativ{e}_{t}rain\_samples$为默认值，即训练集中包含了负样本。

$seal\_processing$函数主要是构建封闭子图，并提取子图中的信息同原有的特征向量相结合构建图数据集。接下来，我将该函数解剖成单独的部分并以训练集正样本为例说明函数流程。

首先，函数输入$(train\_data,train\_data.pos\_edge\_label\_index,1)$分别为训练集整体，标签为正的边两侧节点索引，正标签1。

    for src, dst in edge_label_index.t().tolist():
        sub_nodes, sub_edge_index, mapping, _ = k_hop_subgraph([src, dst], 2, dataset.edge_index, relabel_nodes=True)
        src, dst = mapping.tolist()

对于数据集中的每一对（源和目标），我们提取k-hop邻居（这里，k = 2）。由于设置超参数$relabel\_nodes$为正，所以每一个封闭子图中的节点索引将会从0开始重新编号。

得到$sub\_nodes,sub\_edge\_index,mapping$分别为封闭节点在$train\_data$中的索引，封闭子图中的边，封闭子图中中心节点的索引。

        # Remove target link from the subgraph
        mask1 = (sub_edge_index[0] != src) | (sub_edge_index[1] != dst)
        mask2 = (sub_edge_index[0] != dst) | (sub_edge_index[1] != src)
        sub_edge_index = sub_edge_index[:, mask1 & mask2]

为使用DRNL函数计算距离，我们从子图中移除目标节点。

        # Double-radius node labeling (DRNL)
        src, dst = (dst, src) if src > dst else (src, dst)
        adj = to_scipy_sparse_matrix(sub_edge_index, num_nodes=sub_nodes.size(0)).tocsr()
        
        idx = list(range(src)) + list(range(src + 1, adj.shape[0]))
        adj_wo_src = adj[idx, :][:, idx]
        
        idx = list(range(dst)) + list(range(dst + 1, adj.shape[0]))
        adj_wo_dst = adj[idx, :][:, idx]

将中心节点的索引重编号，使得$dst>src$。之后，根据封闭子图的边构建稀疏矩阵，同时构建没有目标节点的稀疏矩阵。

        # Calculate the distance between every node and the source target node
        d_src = shortest_path(adj_wo_dst, directed=False, unweighted=True, indices=src)
        d_src = np.insert(d_src, dst, 0, axis=0)
        d_src = torch.from_numpy(d_src)

        # Calculate the distance between every node and the destination target node
        d_dst = shortest_path(adj_wo_src, directed=False, unweighted=True, indices=dst-1)
        d_dst = np.insert(d_dst, src, 0, axis=0)
        d_dst = torch.from_numpy(d_dst)

计算封闭子图中的所有除中心节点以外的节点到中心节点之间的距离。

 		# Calculate the label z for each node
        dist = d_src + d_dst
        # DRNL function
        z = 1 + torch.min(d_src, d_dst) + dist // 2 * (dist // 2 + dist % 2 - 1)
        z[src], z[dst], z[torch.isnan(z)] = 1., 1., 0.
        z = z.to(torch.long)

计算DRNL函数，同时将没有与中心节点间接连接的节点的距离设为0，中心节点同自身的距离设为1。

        node_labels = F.one_hot(z, num_classes=200).to(torch.float)
        node_emb = dataset.x[sub_nodes]

        node_x = torch.cat([node_emb, node_labels], dim=1)

        data = Data(x=node_x, z=z, edge_index=sub_edge_index, y=y)
        data_list.append(data)

将计算得到的DRNL距离函数（封闭子图信息），转换为200维的独热编码，并同原数据集中的特征向量相结合组成新的输入向量。$sub\_edge\_index$用于说明图数据中的节点连接关系。

综上，可以将训练集、验证集和测试集分为正负样本相互独立的子图。子图通过$DataLoader$函数构建一个训练批次包含32个子图的数据集。

至此，数据预处理完毕。

3、DGCNN类

class DGCNN(torch.nn.Module):
    def __init__(self, dim_in, k=30):
        super().__init__()

        # GCN layers
        self.gcn1 = GCNConv(dim_in, 32)
        self.gcn2 = GCNConv(32, 32)
        self.gcn3 = GCNConv(32, 32)
        self.gcn4 = GCNConv(32, 1)

        # Global sort pooling
        self.global_pool = aggr.SortAggregation(k=k)

        # Convolutional layers
        self.conv1 = Conv1d(1, 16, 97, 97)
        self.conv2 = Conv1d(16, 32, 5, 1)
        self.maxpool = MaxPool1d(2, 2)

        # Dense layers
        self.linear1 = Linear(352, 128)
        self.dropout = Dropout(0.5)
        self.linear2 = Linear(128, 1)

    def forward(self, x, edge_index, batch):
        # 1. Graph Convolutional Layers
        h1 = self.gcn1(x, edge_index).tanh()
        h2 = self.gcn2(h1, edge_index).tanh()
        h3 = self.gcn3(h2, edge_index).tanh()
        h4 = self.gcn4(h3, edge_index).tanh()
        h = torch.cat([h1, h2, h3, h4], dim=-1)

        # 2. Global sort pooling
        h = self.global_pool(h, batch)

        # 3. Traditional convolutional and dense layers
        h = h.view(h.size(0), 1, h.size(-1))
        h = self.conv1(h).relu()
        h = self.maxpool(h)
        h = self.conv2(h).relu()
        h = h.view(h.size(0), -1)
        h = self.linear1(h).relu()
        h = self.dropout(h)
        h = self.linear2(h).sigmoid()

        return h

针对上述DGCNN类的流程，我们也同数据预处理一样逐一分析。

首先，由前文数据预处理我们可以知道，每一个批次的大小为32，即$batch=32$。

		# model = DGCNN(train_dataset[0].num_features).to(device)
        self.gcn1 = GCNConv(dim_in, 32)
        self.gcn2 = GCNConv(32, 32)
        self.gcn3 = GCNConv(32, 32)
        self.gcn4 = GCNConv(32, 1)

在类初始化部分，我们将数据集的特征向量维数输入，在$GCNConv$部分经过GCN层输出32个特征向量，并不断重复这个过程。该过程为的是多次考虑邻接节点，可以检验图是否同构问题，具体可查看 GIN。

# k=30
# h = torch.cat([h1, h2, h3, h4], dim=-1) # 32*3*1
elf.global_pool = aggr.SortAggregation(k=k)

我们在DGCNN架构的核心实例化了全局排序池，该层主要处理经过特征处理后的嵌入向量。该函数会分析节点特征中的最后一个特征通道，并将其以降序进行排序，并输出前$k$个节点的嵌入向量之和，同时由于一个批次有32个子图，所以经过该层后，$h$的大小为（32，2910），该形状是固定的。

		# h = h.view(h.size(0), 1, h.size(-1))
		# h -->(32, 1, 2910)
        self.conv1 = Conv1d(1, 16, 97, 97)
        self.maxpool = MaxPool1d(2, 2)
        self.conv2 = Conv1d(16, 32, 5, 1)

在处理完嵌入向量之后，通过$view$函数将输出$h$的形状变为（32，1，2910）以迎合Conv1d要求的三维输入形式，这三个输入我们分别用$N$、$C_{in}$和$L_{in}$表示。
同时Conv1d层输入的参数分别为（$C_{in}$, $C_{out}$, $kernel\_size$, $stride$）。
由Conv1d我们可以将Conv1d层的输出定义为$N$、$C_{out}$和$L_{out}$。其中$N$、$C_{out}$都是已知量，$L_{out}$同其他参量的对应关系如下。

其中$padding=0$，$dilation=1$为常量。
经过上述三层后会输出一个（32，32，11）维数的向量。
经过$view(h.size(0),?1)$后会得到形状为（32，352）的向量。

        # Dense layers
        self.linear1 = Linear(352, 128)
        self.dropout = Dropout(0.5)
        self.linear2 = Linear(128, 1)

该向量最后经过线性变换后得到唯一一个输出值，即为标签的预测值。

4、训练模型

device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
model = DGCNN(train_dataset[0].num_features).to(device)
optimizer = torch.optim.Adam(params=model.parameters(), lr=0.0001)
criterion = BCEWithLogitsLoss()

def train():
    model.train()
    total_loss = 0

    for data in train_loader:
        data = data.to(device)
        optimizer.zero_grad()
        out = model(data.x, data.edge_index, data.batch)
        loss = criterion(out.view(-1), data.y.to(torch.float))
        loss.backward()
        optimizer.step()
        total_loss += float(loss) * data.num_graphs

    return total_loss / len(train_dataset)

@torch.no_grad()
def test(loader):
    model.eval()
    y_pred, y_true = [], []

    for data in loader:
        data = data.to(device)
        out = model(data.x, data.edge_index, data.batch)
        y_pred.append(out.view(-1).cpu())
        y_true.append(data.y.view(-1).cpu().to(torch.float))

    auc = roc_auc_score(torch.cat(y_true), torch.cat(y_pred))
    ap = average_precision_score(torch.cat(y_true), torch.cat(y_pred))

    return auc, ap

for epoch in range(31):
    loss = train()
    val_auc, val_ap = test(val_loader)
    print(f'Epoch {epoch:>2} | Loss: {loss:.4f} | Val AUC: {val_auc:.4f} | Val AP: {val_ap:.4f}')

test_auc, test_ap = test(test_loader)
print(f'Test AUC: {test_auc:.4f} | Test AP {test_ap:.4f}')

经过上述模型训练可以得到训练过程以及测试集的输出为：

Epoch  0 | Loss: 0.6976 | Val AUC: 0.7727 | Val AP: 0.7841
Epoch  1 | Loss: 0.6301 | Val AUC: 0.8355 | Val AP: 0.8497
Epoch  2 | Loss: 0.5955 | Val AUC: 0.8528 | Val AP: 0.8707
Epoch  3 | Loss: 0.5862 | Val AUC: 0.8627 | Val AP: 0.8800
Epoch  4 | Loss: 0.5805 | Val AUC: 0.8662 | Val AP: 0.8826
Epoch  5 | Loss: 0.5771 | Val AUC: 0.8609 | Val AP: 0.8813
Epoch  6 | Loss: 0.5745 | Val AUC: 0.8623 | Val AP: 0.8831
Epoch  7 | Loss: 0.5713 | Val AUC: 0.8637 | Val AP: 0.8832
Epoch  8 | Loss: 0.5690 | Val AUC: 0.8655 | Val AP: 0.8865
Epoch  9 | Loss: 0.5675 | Val AUC: 0.8697 | Val AP: 0.8849
Epoch 10 | Loss: 0.5658 | Val AUC: 0.8725 | Val AP: 0.8882
Epoch 11 | Loss: 0.5639 | Val AUC: 0.8702 | Val AP: 0.8878
Epoch 12 | Loss: 0.5604 | Val AUC: 0.8694 | Val AP: 0.8742
Epoch 13 | Loss: 0.5574 | Val AUC: 0.8713 | Val AP: 0.8754
Epoch 14 | Loss: 0.5547 | Val AUC: 0.8716 | Val AP: 0.8807
Epoch 15 | Loss: 0.5529 | Val AUC: 0.8717 | Val AP: 0.8739
Epoch 16 | Loss: 0.5518 | Val AUC: 0.8686 | Val AP: 0.8810
Epoch 17 | Loss: 0.5512 | Val AUC: 0.8675 | Val AP: 0.8674
Epoch 18 | Loss: 0.5502 | Val AUC: 0.8644 | Val AP: 0.8783
Epoch 19 | Loss: 0.5496 | Val AUC: 0.8599 | Val AP: 0.8676
Epoch 20 | Loss: 0.5494 | Val AUC: 0.8588 | Val AP: 0.8638
Epoch 21 | Loss: 0.5484 | Val AUC: 0.8665 | Val AP: 0.8680
Epoch 22 | Loss: 0.5480 | Val AUC: 0.8592 | Val AP: 0.8609
Epoch 23 | Loss: 0.5480 | Val AUC: 0.8614 | Val AP: 0.8638
Epoch 24 | Loss: 0.5474 | Val AUC: 0.8570 | Val AP: 0.8605
Epoch 25 | Loss: 0.5469 | Val AUC: 0.8609 | Val AP: 0.8646
Epoch 26 | Loss: 0.5469 | Val AUC: 0.8599 | Val AP: 0.8640
Epoch 27 | Loss: 0.5469 | Val AUC: 0.8635 | Val AP: 0.8613
Epoch 28 | Loss: 0.5463 | Val AUC: 0.8572 | Val AP: 0.8570
Epoch 29 | Loss: 0.5456 | Val AUC: 0.8552 | Val AP: 0.8583
Epoch 30 | Loss: 0.5456 | Val AUC: 0.8533 | Val AP: 0.8570
Test AUC: 0.8827 | Test AP 0.8972

我们得到的结果与使用VGAE观察到的结果相似（测试AUC为0.8838，测试AP为0.8848）。理论上，基于子图的方法（如SEAL）比基于节点的方法（如VGAEs）更具表现力。它们通过显式地考虑目标节点周围的整个邻域来捕获更多信息。通过使用$k$参数增加考虑的邻居的数量也可以提高SEAL的精度。

SEAL模型预测的可视化结果如下。

图3 SELA预测结果可视化图 从图3中可以看出，当节点的邻接节点信息较多时，SEAL模型预测准确率较高；反之，较低。

---

总结

在本章中，我们探索了一个新的链接预测任务。我们通过介绍启发式和矩阵分解技术对这一领域进行了概述。启发式算法可以根据它们考虑的$k$跳邻居进行分类——从具有1跳邻居的局部算法到具有整个图的知识的全局算法。相反，矩阵分解使用节点嵌入近似邻接矩阵。我们还解释了该技术如何与前面描述的算法相关联章节（DeepWalk 和 Node2Vec）。
在介绍了链接预测之后，我们看到了如何使用GNN实现它。我们概述了两种基于节点嵌入（GAE和VGAE）和子图表示（SEAL）的技术。最后，我们在Cora数据集上使用边缘级随机实现了VGAE和SEAL分裂和负抽样。两种模型都获得了相当的性能，尽管SEAL严格地更具表现力。