图神经网络已经成功地应用于许多节点或边的预测任务，然而，在超大图上进行图神经网络的训练仍然具有挑战。普通的基于SGD的图神经网络的训练方法，要么面临着随着图神经网络层数增加，计算成本呈指数增长的问题，要么面临着保存整个图的信息和每一层每个节点的表征到内存（显存）而消耗巨大内存（显存）空间的问题。
将首先对Cluster-GCN论文中提出的方法（后文中简称为Cluster-GCN方法）做简单概括，接着深入分析超大图上的节点表征学习面临的挑战，最后对Cluster-GCN方法做深入分析。
为了解决普通训练方法无法训练超大图的问题，Cluster-GCN论文提出：

利用图节点聚类算法将一个图的节点划分为c个簇，每一次选择几个簇的节点和这些节点对应的边构成一个子图，然后对子图做训练。
由于是利用图节点聚类算法将节点划分为多个簇，所以簇内边的数量要比簇间边的数量多得多，所以可以提高表征利用率，并提高图神经网络的训练效率。
每一次随机选择多个簇来组成一个batch，这样不会丢失簇间的边，同时也不会有batch内类别分布偏差过大的问题。
基于小图进行训练，不会消耗很多内存空间，于是我们可以训练更深的神经网络，进而可以达到更高的精度。

节点表征学习的问题

以往的训练方法需要同时计算所有节点的表征以及训练集中所有节点的损失产生的梯度（后文我们直接称为完整梯度）。这种训练方式需要非常巨大的计算开销和内存（显存）开销：在内存（显存）方面，计算公式(2)的完整梯度需要存储所有的节点表征矩阵\left{Z^{(l)}\right}_{l=1}^{L}，这需要O(NFL)的空间；在收敛速度方面，由于神经网络在每个epoch中只更新一次，所以训练需要更多的epoch才能达到收敛。

最近的一些工作证明，采用mini-batch SGD的方式训练，可以提高图神经网络的训练速度并减少内存（显存）需求。在参数更新中，SGD不需要计算完整梯度，而只需要基于mini-batch计算部分梯度。我们使用B⊆[N]来表示一个batch，其大小为b=|B|。SGD的每一步都将计算梯度估计值1|B|∑i∈B∇loss(yi,z(L)i)来进行参数更新。尽管在epoches数量相同的情况下，采用SGD方式进行训练，收敛速度可以更快，但此种训练方式会引入额外的时间开销，这使得相比于全梯度下降的训练方式，此种训练方式每个epoch的时间开销要大得多。

目标：

为了最大限度地提高表征利用率，理想的划分batch的结果是，batch内的边尽可能多，batch之间的边尽可能少。

显示了两种不同的节点划分策略：随机划分与聚类划分。两者都使用一个分区作为一个batch来进行神经网络训练。我们可以看到，在相同的epoches下，使用聚类分区可以达到更高的精度。

以往尝试训练更深的GCN的研究似乎表明，增加更多的层是没有帮助的。然而，那些研究的实验使用的图太小，所以结论可能并不正确。例如，其中有一项研究只使用了一个只有几百个训练节点的图，由于节点数量过少，很容易出现过拟合的问题。此外，加深GCN神经网络层数后，训练变得很困难，因为层数多了之后前面的信息可能无法传到后面。有的研究采用了一种类似于残差连接的技术，使模型能够将前一层的信息直接传到下一层。具体来说，他们修改了公式(1)，将第l层的表征添加到下一层，如下所示：
X(l+1)=σ(A′X(l)W(l))+X(l)(8)
在这里，我们提出了另一种简单的技术来改善深层GCN神经网络的训练。在原始的GCN的设置里，每个节点都聚合邻接节点在上一层的表征。然而，在深层GCN的设置里，该策略可能不适合，因为它没有考虑到层数的问题。直观地说，近距离的邻接节点应该比远距离的的邻接节点贡献更大。因此，Cluster-GCN提出一种技术来更好地解决这个问题。其主要思想是放大GCN每一层中使用的邻接矩阵A的对角线部分。通过这种方式，我们在GCN的每一层的聚合中对来自上一层的表征赋予更大的权重。这可以通过给A¯加上一个单位矩阵I来实现，如下所示，
X(l+1)=σ((A′+I)X(l)W(l))(9)
虽然公式(9)似乎是合理的，但对所有节点使用相同的权重而不考虑其邻居的数量可能不合适。此外，它可能会受到数值不稳定的影响，因为当使用更多的层时，数值会呈指数级增长。因此，Cluster-GCN方法提出了一个修改版的公式(9)，以更好地保持邻接节点信息和数值范围。首先给原始的A添加一个单位矩阵I，并进行归一化处理
A~=(D+I)−1(A+I)(10)
然后考虑，
X(l+1)=σ((A~+λdiag(A~))X(l)W(l))(11)
Cluster-GCN实践：
#下载数据库：
from torch_geometric.datasets import Reddit
from torch_geometric.data import ClusterData, ClusterLoader, NeighborSampler

dataset = Reddit('../dataset/Reddit')
data = dataset[0]
print(dataset.num_classes)
print(data.num_nodes)
print(data.num_edges)
print(data.num_features)

#图节点聚类与数据加载器生成

cluster_data = ClusterData(data, num_parts=1500, recursive=False, save_dir=dataset.processed_dir)
train_loader = ClusterLoader(cluster_data, batch_size=20, shuffle=True, num_workers=12)
subgraph_loader = NeighborSampler(data.edge_index, sizes=[-1], batch_size=1024, shuffle=False, num_workers=12)
# 图神经网络的构建
class Net(torch.nn.Module):
    def __init__(self, in_channels, out_channels):
        super(Net, self).__init__()
        self.convs = ModuleList(
            [SAGEConv(in_channels, 128),
             SAGEConv(128, out_channels)])

    def forward(self, x, edge_index):
        for i, conv in enumerate(self.convs):
            x = conv(x, edge_index)
            if i != len(self.convs) - 1:
                x = F.relu(x)
                x = F.dropout(x, p=0.5, training=self.training)
        return F.log_softmax(x, dim=-1)

    def inference(self, x_all):
        pbar = tqdm(total=x_all.size(0) * len(self.convs))
        pbar.set_description('Evaluating')

        # Compute representations of nodes layer by layer, using *all*
        # available edges. This leads to faster computation in contrast to
        # immediately computing the final representations of each batch.
        for i, conv in enumerate(self.convs):
            xs = []
            for batch_size, n_id, adj in subgraph_loader:
                edge_index, _, size = adj.to(device)
                x = x_all[n_id].to(device)
                x_target = x[:size[1]]
                x = conv((x, x_target), edge_index)
                if i != len(self.convs) - 1:
                    x = F.relu(x)
                xs.append(x.cpu())

                pbar.update(batch_size)

            x_all = torch.cat(xs, dim=0)

        pbar.close()

        return x_all

    #训练、验证和测试
        device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
model = Net(dataset.num_features, dataset.num_classes).to(device)
optimizer = torch.optim.Adam(model.parameters(), lr=0.005)

def train():
    model.train()

    total_loss = total_nodes = 0
    for batch in train_loader:
        batch = batch.to(device)
        optimizer.zero_grad()
        out = model(batch.x, batch.edge_index)
        loss = F.nll_loss(out[batch.train_mask], batch.y[batch.train_mask])
        loss.backward()
        optimizer.step()

        nodes = batch.train_mask.sum().item()
        total_loss += loss.item() * nodes
        total_nodes += nodes

    return total_loss / total_nodes


@torch.no_grad()
def test():  # Inference should be performed on the full graph.
    model.eval()

    out = model.inference(data.x)
    y_pred = out.argmax(dim=-1)

    accs = []
    for mask in [data.train_mask, data.val_mask, data.test_mask]:
        correct = y_pred[mask].eq(data.y[mask]).sum().item()
        accs.append(correct / mask.sum().item())
    return accs


for epoch in range(1, 31):
    loss = train()
    if epoch % 5 == 0:
        train_acc, val_acc, test_acc = test()
        print(f'Epoch: {epoch:02d}, Loss: {loss:.4f}, Train: {train_acc:.4f}, '
              f'Val: {val_acc:.4f}, test: {test_acc:.4f}')
    else:
        print(f'Epoch: {epoch:02d}, Loss: {loss:.4f}')