图扩散卷积：Graph_Diffusion_Convolution

图扩散卷积：Graph_Diffusion_Convolution

1. 论文：Klicpera J, Weißenberger S, Günnemann S. Diffusion improves graph learning[J]. arXiv preprint arXiv:1911.05485, 2019. https://arxiv.org/abs/1911.05485
2. 慕尼黑工业大学数据分析和机器学习小组官方介绍：https://www.cs.cit.tum.de/en/daml/research/gdc/
3. 博客：https://msrmblog.github.io/graph-diffusion-convolution/
4. 代码：https://github.com/gasteigerjo/gdc

在几乎所有科学和工业领域中，您都会发现用图(graph)（又名网络）很好地描述的应用程序。 这个列表几乎是无穷无尽的：有计算机视觉中的场景图，搜索引擎中的知识图，自然语言的解析树，代码的语法树和控制流图，分子图，交通网络，社交网络，家谱，电路， 还有更多。

Some examples of graphs. [Wikimedia Commons, Stanford Vision Lab]

虽然图确实是对这些数据的一个很好的描述，但许多数据结构实际上是人为创建的，底层的事实比图所捕获的更复杂。例如，分子可以用原子和键的图(graph)来描述，但其潜在的相互作用要复杂得多。更准确的描述应该是原子点云，甚至是每个电子的连续密度函数。

因此，处理图(graph)数据时的主要问题之一是如何在仅提供简单图(graph)的同时结合这种丰富的底层复杂性。 我们小组最近开发了一种利用这种复杂性的方法：图扩散卷积（GDC）。 该方法可用于改进任何基于图的算法，尤其针对图神经网络（GNN）。如何实现这一点呢？为什么可以？

GNN 最近在各种任务上表现出出色的性能，因此在研究人员中的受欢迎程度大幅上升。 在这篇博文中，我想首先简要介绍 GNN，然后展示如何利用 GDC 来增强这些模型。

1. 什么是图神经网络？

在每层中，节点$v$可以接收来自所有邻居节点$w$的消息，然后基于这些消息更新它自己的嵌入。在第一层之前的节点嵌入通常是由一些给定的节点特征获得的。在引文图(graph)中，论文通过引文联系在一起，这些特征通常是每篇论文摘要的一个词袋向量。

图神经网络 (GNN) 背后的想法相当简单：我们不是单独对每个节点进行预测，而是在神经网络的每一层之后在相邻节点之间传递消息。 这就是为什么一种流行的 GNN 框架被恰当地称为消息传递神经网络 (MPNN)。 MPNN 由以下两个等式定义：
$$\begin{gathered} m_v^{(t+1)}=\sum _{w\in N(v)}{f}_{\text{message}}^{(t+1)}\left(h_v^{(t)},h_w^{(t)},e_{vw}\right), \\ {h}_v^{(t+1)}=f_{\text{update}}^t\left(h_v^{(t)},m_v^{(t+1)}\right) \end{gathered}$$
此处$h_v$是节点嵌入，$e_{vw}$是边嵌入，$m_v$是输入信息，$N_v$表示节点$v$的邻居。在第一个方程中，所有输入信息被聚合，每个信息通过函数$f_{message}$转化，输入信息的聚合通常是通过神经网络来实现的。

节点嵌入通过聚合的信息并且通过$f_{update}$来实现，节点信息的更新通常也是通过神经网络来实现的。如你所见，在图神经网络中，单个信息在其邻居之间发送和聚合。每一层通过反向传播学习独立的权重值，例如$f_{message}$和$f_{update}$ 在每一层都是不一样的。可以说最简单的 GNN 是图卷积网络 (GCN)，它可以被认为是图上 CNN 的类似物。其他类型的图神经网络包括：

• personalized propagation of neural predictions (PPNP)：https://arxiv.org/abs/1810.05997
• graph attention networks (GATs)： https://arxiv.org/abs/1710.10903
• SchNet分子中的量子交互建模： https://arxiv.org/abs/1706.08566
• ChebNet具有快速局部谱过滤的卷积神经网络：https://proceedings.neurips.cc/paper/2016/hash/04df4d434d481c5bb723be1b6df1ee65-Abstract.html
• Graph Isomorphism Network (GIN)图同构网络：https://arxiv.org/abs/1810.00826

上述MPNN方程在几个方面有局限性。最重要的是，我们只使用每个节点的直接邻居，并赋予它们同等的权重。然而，正如我们前面讨论的那样，图(graph)背后的基本事实通常更复杂，图(graph)只捕获了这部分信息。这就是为什么其他领域的图(graph)分析长期以来都克服了这一限制，并转向了更具表现力的邻居(实际上从1900年左右开始)。我们还能做得比直接使用邻居更好吗?

2. 超越直接邻居:图扩散卷积

gnn和大多数其他基于图的模型将边解释为纯粹的二元，即它们要么存在，要么不存在。然而，真正的关系远比这复杂得多。例如，在一个社交网络中，你可能有一些与你联系紧密的好朋友，以及许多你只见过一面的熟人。

为了改进我们模型的预测，我们可以尝试通过图扩散重建这些连续的关系。直观地说，在图扩散中，我们首先把所有的注意力放在考虑的节点上。然后，我们不断地将一些注意力传递给节点的邻居，将注意力从开始节点上分散开。一段时间后，我们停下来，在那个点上的注意力分布定义了从开始节点到其他节点的边。通过对每个节点这样做，我们得到了一个矩阵，它定义了一个新的连续加权图。更准确地说，图扩散被定义为：
$$S=\sum _{k=0}^{\infty }{\theta }_k{T}^k$$
其中${\theta }_k$是系数，$T$定义了转移矩阵（通过$A{D}^{-1}$来定义)，其中$A$为邻接矩阵，$D$为对角度矩阵，其中$d_{ii}={\sum }_j{a}_{ij}$。

这些系数是由我们选择的特定扩散变量预定义的，例如个性化PageRank (personalized PageRank, PPR)或热核函数(the heat kernel)。不幸的是, 获得$S$

是稠密的，即在这个矩阵中每个节点都与其他节点相连。然而，我们可以通过忽略小的值来简化这个矩阵，例如，通过将在某个阈值$\epsilon$以下所有条目设置

为0。这样我们得到了一个由加权邻接矩阵$\tilde{S}$定义的新的稀疏图, 用这个图代替原来的。甚至有直接获取稀疏$\tilde{S}$的快速方法, 不需要先构造一个密集矩阵。

图扩散卷积(Graph diffusion convolution, GDC): 我们首先对原始图进行扩散，从某个节点$v$开始。扩散后的密度定义了起始节点$v$的边。 然后我们移除所有权值较小的边。通过对每个节点这样做一次，我们得到了一个新的稀疏的加权图$S$。

因此，GDC（Graph diffusion convolution，图扩散卷积）是一个预处理步骤，可以应用于任何图(graph)，并与任何基于图(graph)的算法一起使用。我们进行了大量的实验(超过10万次的训练)，以表明GDC在各种各样的模型和数据集上持续地提高了预测的准确性。但要记住，GDC基本上利用了大多数图(graph)中的同质性。同质性是指相邻节点趋于相似的属性，即物以类聚。因此，它并不适用于每个数据集和模型。

3. 为什么图扩散卷积有用？

到目前为止，我们对GDC只给出了直观的解释。但为什么它真的有效呢?为了回答这个问题，我们必须稍微研究一下图谱理论。

在图谱理论中，我们分析图的谱，即图的拉普拉斯特征值$L=D-A$, 其中$A$是邻接矩阵，$D$是对角度矩阵。 这些特征值的有趣之处在于，低值对应的特征向量定义了紧密连接的大群落，而高值对应的是小尺度结构和振荡，类似于正常信号中的小频率和大频率。这正是谱聚类(spectral clustering)所利用的优势。

当我们研究在应用GDC时的这些特征值变化时，我们发现GDC通常扮演**低通过滤器(low-pass filter)**的角色。换句话说，GDC放大了大型的、连接良好的社区，并抑制了与小规模结构相关的信号。这直接解释了为什么GDC能够帮助我们完成节点分类或集群等任务:它能够放大与图表中最主要结构相关的信号，也就是我们感兴趣的少数大型类或集群。

GDC作为图形信号的低通滤波器。与小特征值相关的特征向量对应大的紧密连接的群落。因此，GDC放大了与许多基于图的任务最相关的信号。

4. 图卷积神经网络的参考实现

图扩散卷积的官方实现：https://github.com/gasteigerjo/gdc

导入包：

import time
import yaml
import torch

import scipy.sparse as sp
import numpy as np
import seaborn as sns
import torch.nn.functional as F

from tqdm.notebook import tqdm
from torch.optim import Adam, Optimizer
from collections import defaultdict
from torch_geometric.data import Data, InMemoryDataset

from data import get_dataset, HeatDataset, PPRDataset, set_train_val_test_split
from models import GCN
from seeds import val_seeds, test_seeds
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

本教程展示了，用图扩散卷积如何提升图卷积网络。

核心的是，图卷积扩散的预处理仅仅是是这个函数。

def gdc(A: sp.csr_matrix, alpha: float, eps: float):
    N = A.shape[0]

    # Self-loops
    A_loop = sp.eye(N) + A

    # Symmetric transition matrix
    D_loop_vec = A_loop.sum(0).A1
    D_loop_vec_invsqrt = 1 / np.sqrt(D_loop_vec)
    D_loop_invsqrt = sp.diags(D_loop_vec_invsqrt)
    T_sym = D_loop_invsqrt @ A_loop @ D_loop_invsqrt

    # PPR-based diffusion
    S = alpha * sp.linalg.inv(sp.eye(N) - (1 - alpha) * T_sym)

    # Sparsify using threshold epsilon
    S_tilde = S.multiply(S >= eps)

    # Column-normalized transition matrix on graph S_tilde
    D_tilde_vec = S_tilde.sum(0).A1
    T_S = S_tilde / D_tilde_vec
    
    return T_S
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

我们将在本教程中使用GPU。如果你想用CPU，只需要将下面的行改为cpu。

device = 'cuda'
1

数据集和模型的参数设置以及训练例程都存储在config.yaml（https://github.com/gasteigerjo/gdc/blob/master/config.yaml）中。

with open('config.yaml', 'r') as c:
    config = yaml.safe_load(c)
1
2

加载数据集并使用图扩散卷积预处理：为了方便，我们将在本教程中使用PyTorch Geometric InMemoryDatase。 PPRDataset (和 HeatDataset) 提供比上述GDC方法更多的灵活性和功能。然而，它们的预处理在本质上是相同的。

datasets = {}

for preprocessing in ['none', 'heat', 'ppr']:
    if preprocessing == 'none':
        dataset = get_dataset(
            name=config['dataset_name'],
            use_lcc=config['use_lcc']
        )
        dataset.data = dataset.data.to(device)
        datasets[preprocessing] = dataset
    elif preprocessing == 'heat':
        dataset = HeatDataset(
            name=config['dataset_name'],
            use_lcc=config['use_lcc'],
            t=config[preprocessing]['t'],
            k=config[preprocessing]['k'],
            eps=config[preprocessing]['eps']
        )
        dataset.data = dataset.data.to(device)
        datasets[preprocessing] = dataset
    elif preprocessing == 'ppr':
        dataset = PPRDataset(
            name=config['dataset_name'],
            use_lcc=config['use_lcc'],
            alpha=config[preprocessing]['alpha'],
            k=config[preprocessing]['k'],
            eps=config[preprocessing]['eps']
        )
        dataset.data = dataset.data.to(device)
        datasets[preprocessing] = dataset
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

创建图卷积网络:

models = {}

for preprocessing, dataset in datasets.items():
    models[preprocessing] = GCN(
        dataset,
        hidden=config[preprocessing]['hidden_layers'] * [config[preprocessing]['hidden_units']],
        dropout=config[preprocessing]['dropout']
    ).to(device)
1
2
3
4
5
6
7
8

训练模型:

def train(model: torch.nn.Module, optimizer: Optimizer, data: Data):
    model.train()
    optimizer.zero_grad()
    logits = model(data)
    loss = F.nll_loss(logits[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()
1
2
3
4
5
6
7

def evaluate(model: torch.nn.Module, data: Data, test: bool):
    model.eval()
    with torch.no_grad():
        logits = model(data)
    eval_dict = {}
    keys = ['val', 'test'] if test else ['val']
    for key in keys:
        mask = data[f'{key}_mask']
        # loss = F.nll_loss(logits[mask], data.y[mask]).item()
        # eval_dict[f'{key}_loss'] = loss
        pred = logits[mask].max(1)[1]
        acc = pred.eq(data.y[mask]).sum().item() / mask.sum().item()
        eval_dict[f'{key}_acc'] = acc
    return eval_dict
1
2
3
4
5
6
7
8
9
10
11
12
13
14

def run(dataset: InMemoryDataset,
        model: torch.nn.Module,
        seeds: np.ndarray,
        test: bool = False,
        max_epochs: int = 10000,
        patience: int = 100,
        lr: float = 0.01,
        weight_decay: float = 0.01,
        num_development: int = 1500,
        device: str = 'cuda'):
    start_time = time.perf_counter()

    best_dict = defaultdict(list)

    cnt = 0
    for seed in tqdm(seeds):
        dataset.data = set_train_val_test_split(
            seed,
            dataset.data,
            num_development=num_development,
        ).to(device)
        model.to(device).reset_parameters()
        optimizer = Adam(
            [
                {'params': model.non_reg_params, 'weight_decay': 0},
                {'params': model.reg_params, 'weight_decay': weight_decay}
            ],
            lr=lr
        )

        patience_counter = 0
        tmp_dict = {'val_acc': 0}

        for epoch in range(1, max_epochs + 1):
            if patience_counter == patience:
                break

            train(model, optimizer, dataset.data)
            eval_dict = evaluate(model, dataset.data, test)

            if eval_dict['val_acc'] < tmp_dict['val_acc']:
                patience_counter += 1
            else:
                patience_counter = 0
                tmp_dict['epoch'] = epoch
                for k, v in eval_dict.items():
                    tmp_dict[k] = v

        for k, v in tmp_dict.items():
            best_dict[k].append(v)
            
    best_dict['duration'] = time.perf_counter() - start_time
    return dict(best_dict)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53

我们在不同的划分上训练这个模型100次，这将耗费几分钟时间。

results = {}

for preprocessing in ['none', 'heat', 'ppr']:
    results[preprocessing] = run(
        datasets[preprocessing],
        models[preprocessing],
        seeds=test_seeds if config['test'] else val_seeds,
        lr=config[preprocessing]['lr'],
        weight_decay=config[preprocessing]['weight_decay'],
        test=config['test'],
        num_development=config['num_development'],
        device=device
    )
1
2
3
4
5
6
7
8
9
10
11
12
13

HBox(children=(IntProgress(value=0), HTML(value=‘’)))
HBox(children=(IntProgress(value=0), HTML(value=‘’)))
HBox(children=(IntProgress(value=0), HTML(value=‘’)))

评估结果:使用自助法，计算统计结果。

for _, best_dict in results.items():
    boots_series = sns.algorithms.bootstrap(best_dict['val_acc'], func=np.mean, n_boot=1000)
    best_dict['val_acc_ci'] = np.max(np.abs(sns.utils.ci(boots_series, 95) - np.mean(best_dict['val_acc'])))
    if 'test_acc' in best_dict:
        boots_series = sns.algorithms.bootstrap(best_dict['test_acc'], func=np.mean, n_boot=1000)
        best_dict['test_acc_ci'] = np.max(
            np.abs(sns.utils.ci(boots_series, 95) - np.mean(best_dict['test_acc']))
        )

    for k, v in best_dict.items():
        if 'acc_ci' not in k and k != 'duration':
            best_dict[k] = np.mean(best_dict[k])
1
2
3
4
5
6
7
8
9
10
11
12

for preprocessing in ['none', 'heat', 'ppr']:
    mean_acc = results[preprocessing]['test_acc']
    uncertainty = results[preprocessing]['test_acc_ci']
    print(f"{preprocessing}: Mean accuracy: {100 * mean_acc:.2f} +- {100 * uncertainty:.2f}%")
1
2
3
4

none: Mean accuracy: 81.74 ± 0.25%
heat: Mean accuracy: 83.47 ± 0.21%
ppr: Mean accuracy: 83.64 ± 0.23%